From Entropy to Lempel-Ziv

Entropy, an Information Theory term coined by Claude Shannon in 1948, describes the minimum number of bits, on average, needed to encode a dataset. Think of entropy as the number of yes/no questions that would need to be answered in order to describe any one piece of information within a dataset.

Compression aims to reduce that ceiling of bits by transforming data in such a way that patterns emerge exposing duplication within a given dataset.

The act of producing optimally large, repeating tokens within a dataset was the key concept behind Abraham Lempel's and Yaakov Ziv's work on the LZ77 and LZ78 algorithms developed in 1977 and 1978 respectively. Their work has had a huge impact on the field of lossless compression. Many algorithms used in popular software today are variations and tweaks to those two algorithms developed in the late 1970s.

Below is a family tree of related dictionary-based compression algorithms which trace their linages back to LZ77 and LZ78. I've also included the year of earliest publication I could find for each of them and a few noteworthy software and file format implementations.

├── LZ77 (1977)
│   ├── LZR (1981)
│   ├── LZSS (1982, WINRAR)
│   │   ├── LZB (1987)
│   │   └── LZH (1987)
│   ├── DEFLATE (1989, ZIP, gzip, PNG, zlib)
│   │   └── DEFLATE64 (1999)
│   ├── ROLZ (1991)
│   │   ├── LZP (1995)
│   │   └── LZRW1 (1991)
│   │       ├── LZJB (1998, ZFS)
│   │       └── LZRW1-A, 2, 3, 3-A, 4, 5 (<1996 and onward)
│   ├── LZS (1994, Cisco IOS)
│   ├── LZX (1995, CHM files)
│   ├── LZO (1996, Nintendo 64, PlayStation)
│   ├── LZMA (1998, 7ZIP, xz)
│   │   ├── LZMA2 (2009)
│   │   └── LZHAM (2009)
│   ├── Statistical Lempel-Ziv (2001)
│   ├── SLZ (<2009)
│   ├── LZ4 (2011, Hadoop, ZFS, bcolz)
│   │   └── ZStandard (2015, Redshift, ORC, Parquet, RocksDB, bcolz)
│   ├── Snappy (2011, ORC, Parquet, MariaDB, Cassandra, MongoDB, Lucene, bcolz)
│   └── Brotli (2013, Google Chrome, Firefox, nginx)
│       └── LZFSE (2015, iOS, Mac OSX)
└── LZ78 (1978)
    ├── LZW (1984, PKZIP, GIF, TIFF, PDF)
    │   ├── LZMW (1985)
    │   │   └── LZAP (1988)
    │   ├── LZC (2007)
    │   │   └── LZT (1987)
    │   └── LZWL (2006)
    └── LZJ (1985)

In contrast, these are a few non-dictionary-based compression systems.

├── PPM (1984)
│   └── PAQ (2002)
│      └── 20+ Variants (2003-2009)
└── bzip2 (1996)

As you can see, the compression world may not be fast-moving but rarely does a year pass without some sort of iteration and improvement.

Lossless Compression Benchmarks

In 2015, Przemyslaw Skibinski started a project on GitHub called lzbench. This project aims to compile the source code of a wide range of lossless compression algorithms into a single binary and then benchmark them against various workloads. The project's README contains benchmark results for a 212 MB file extracted from the Silesia compression corpus. Each of the compression methods used is run with a variety of settings; this gives an idea of what sort of results could be expected from a performance tuning exercise.

In the above benchmark results, blosclz, density, lz4, lz4fast, lzo1x and shrinker were all tuned to compress at more than 400 MB/s while maintaining at least a 5:3 compression ratio.

The benchmark shows memcpy, which simply copied the data from one memory location to another, running at ~8.5 GB/s. Given the computational overheads of each of the compressors, this transfer rate can be seen as a ceiling on the hardware used (C-Blosc claims it can get past memory-bound performance issues but I've yet to study their claim in detail). The density and lz4fast benchmarks stand out as their compression speeds of 800 and 785 MB/s respectively, were the fastest of any compressor able to achieve a 3:2 compression ratio.

Of the compressors that are able to achieve a 3:1 compression ratio, only Zstandard could do so at 88 MB/s. More than 75% of the other compressors that could achieve that compression ratio couldn't do so at any more than 15 MB/s, some 6x slower than Zstandard.

The vast majority of decompressors could break the 250 MB/s barrier, 25% of the decompressors broke the 1 GB/s barrier and a few, including LZ4, could be tuned to decompress in excess of 2 GB/s. Decompression at this rate would demand either RAM drives, RAID 0 or NVMe storage in order to keep up with these levels of throughput. The SATA bus on most systems is limited to 1.2 GB/s so this would be a bottleneck in need of addressing if it were included in the storage pipeline.

Lastly, the compression ratio of more than 4:1 that xz achieved is interesting. This compressor is popular in packaging software. A software package could be downloaded 100s of millions of times so it's worth the effort to find the best compression ratio possible given the amount of bandwidth and the diversity of network connections involved in software distribution. This goal can excuse the 2 MB/s compression rate xz managed during the compression process.

Do bear in mind that some decompression tools can require an excessive amount of memory and compute power. The high-ratio compression systems can suffer from this greatly so this trade-off should be considered as well.

Sort, then Compress

Many lossless compression systems can be aided by being fed sorted data. The sliding window compressors use rarely cover the entire dataset and the more clustered the values the easier it is to detect repeating patterns. Most SQL-based systems don't guarantee the order of rows returned without an ORDER BY clause so the sorted form of the data on disk should be of little concern (with Redshift's sort key a notable exception).

Below I've set up a standalone Hadoop system running HDFS and Presto using the instructions from my Hadoop 3 Install Guide. I've taken the first 6 ORC files representing 120 million of the 1.1 billion taxi rides that have taken place in New York City over six years. This post describes how I produced this dataset in CSV format and I've run a large number of benchmarks where I've converted that CSV data into ORC format before examining query performance.

Below are a few modifications I've made to the Presto configuration in my stand-alone guide. First, to sort 120M rows of data in Presto will require a memory limit of at least 8 GB.

$ sudo vi /opt/presto/etc/config.properties

coordinator=true
node-scheduler.include-coordinator=true
http-server.http.port=8080
query.max-memory=8GB
query.max-memory-per-node=8GB
query.max-total-memory-per-node=8GB
discovery-server.enabled=true
discovery.uri=http://localhost:8080

$ sudo /opt/presto/bin/launcher restart

Next, I'll create a warehouse folder as the tables created below will run via the Hive connector and it defaults to store tables it helps create in /user/hive/warehouse on HDFS.

$ hdfs dfs -mkdir -p /user/hive/warehouse

I'll then copy the first six ORC files I have saved in my home folder onto HDFS.

$ hdfs dfs -mkdir /trips_orc
$ hdfs dfs -copyFromLocal \
    ~/orc/00000[0-5]_0 \
    /trips_orc/

I'll create a schema for the trips_orc table in Hive. This lets Presto do schema-on-read and understand the column layout of the ORC files.

$ hive

CREATE EXTERNAL TABLE trips_orc (
    trip_id                 INT,
    vendor_id               STRING,
    pickup_datetime         TIMESTAMP,
    dropoff_datetime        TIMESTAMP,
    store_and_fwd_flag      STRING,
    rate_code_id            SMALLINT,
    pickup_longitude        DOUBLE,
    pickup_latitude         DOUBLE,
    dropoff_longitude       DOUBLE,
    dropoff_latitude        DOUBLE,
    passenger_count         SMALLINT,
    trip_distance           DOUBLE,
    fare_amount             DOUBLE,
    extra                   DOUBLE,
    mta_tax                 DOUBLE,
    tip_amount              DOUBLE,
    tolls_amount            DOUBLE,
    ehail_fee               DOUBLE,
    improvement_surcharge   DOUBLE,
    total_amount            DOUBLE,
    payment_type            STRING,
    trip_type               SMALLINT,
    pickup                  STRING,
    dropoff                 STRING,

    cab_type                STRING,

    precipitation           SMALLINT,
    snow_depth              SMALLINT,
    snowfall                SMALLINT,
    max_temperature         SMALLINT,
    min_temperature         SMALLINT,
    average_wind_speed      SMALLINT,

    pickup_nyct2010_gid     SMALLINT,
    pickup_ctlabel          STRING,
    pickup_borocode         SMALLINT,
    pickup_boroname         STRING,
    pickup_ct2010           STRING,
    pickup_boroct2010       STRING,
    pickup_cdeligibil       STRING,
    pickup_ntacode          STRING,
    pickup_ntaname          STRING,
    pickup_puma             STRING,

    dropoff_nyct2010_gid    SMALLINT,
    dropoff_ctlabel         STRING,
    dropoff_borocode        SMALLINT,
    dropoff_boroname        STRING,
    dropoff_ct2010          STRING,
    dropoff_boroct2010      STRING,
    dropoff_cdeligibil      STRING,
    dropoff_ntacode         STRING,
    dropoff_ntaname         STRING,
    dropoff_puma            STRING
) STORED AS orc
  LOCATION '/trips_orc/';

The following SQL will create four new tables. Each will be in GZIP-compressed, ORC format. Each one will pick a different field to sort on. Note I'm only storing four columns from the original table for the sake of both time and memory consumption during this operation.

$ vi sort.sql

CREATE TABLE sorted_by_vendor_id
WITH (format='ORC') AS
    SELECT trip_id,
           vendor_id,
           pickup_datetime,
           pickup_longitude
    FROM trips_orc
    ORDER BY vendor_id;

CREATE TABLE sorted_by_trip_id
WITH (format='ORC') AS
    SELECT trip_id,
           vendor_id,
           pickup_datetime,
           pickup_longitude
    FROM trips_orc
    ORDER BY trip_id;

CREATE TABLE sorted_by_pickup_datetime
WITH (format='ORC') AS
    SELECT trip_id,
           vendor_id,
           pickup_datetime,
           pickup_longitude
    FROM trips_orc
    ORDER BY pickup_datetime;

CREATE TABLE sorted_by_pickup_longitude
WITH (format='ORC') AS
    SELECT trip_id,
           vendor_id,
           pickup_datetime,
           pickup_longitude
    FROM trips_orc
    ORDER BY pickup_longitude;

I'll execute the above with Presto.

$ presto \
    --server localhost:8080 \
    --catalog hive \
    --schema default \
    --file sort.sql

The resulting table sizes were as follows:

  GB | sorted by
----------------------
0.91 | pickup_longitude
1.06 | trip_id
1.12 | pickup_datetime
1.33 | vendor_id

The largest table is 1.46x bigger than the smallest.

There is an argument that one should test the first 50K-odd records of any table against all possible sort keys when compressing a given dataset. There is no speeding up a solid-state drive by 1.46x but the above happily reduced the throughput requirements by that amount.

If the memory usage of sorting your entire dataset exceeded your cluster's capacity you could look to sort on each table partition one at a time instead. Good is not the enemy of perfect and reclaiming storage and throughput capacity will help make the most of your cluster's hardware.

An Attack Vector

Compression has also been an attack vector for decades now. There have been "Compression Fuzzing" efforts to help uncover vulnerabilities but given decompression utilities are some of the most widely-deployed software in the world, any exploit can have a global impact.

A few examples include the "ZIP of death" which is a 42 KB ZIP file that extracts 4.5 PB of data. Unsuspecting web applications that decompressed user-submitted content need to be hardened for this sort of attack. BREACH exploited an HTTPS compression vulnerability and CRIME was another exploit disclosed around the same time that worked over HTTPS and SPDY connections that used compression.

Incidents like the above are making compression designers contemplate what attack vectors could result from forth-coming dictionary encoding methods.