tsz :: Compact Integral Time-Series Compression

A portable implementation for bit-packing and precise framing on space-constrained systems for periodic time-series integral data.

Inspiration drawn from IC FIFO compression and Gorilla timestamp compression. https://www.vldb.org/pvldb/vol8/p1816-teller.pdf

Pros and Cons

✅ tsz is designed to lean heavily on delta and delta-delta compression. As shown by Gorilla in practice, data points that change the same way compress very well (96% of timestamps could be represented by 1 bit in the Gorilla block). Periodic integral data, like those from embedded sensor data, that changes with low noise rates will mostly follow the same compression patterns as the timestamps generated by consitently clocked intervals.

✅ tsz is designed to take advantage of the integral data patterns produced by ICs that generate consistent bit-width integral data over time with similar magnitudes of change.

✅ tsz is designed to emit framed packets that would be considered very small outside of the embedded space, targetting <255 bytes per block.

❌ tsz is not designed to handle oscillating change or irregularly event time streams optimally but can encode that information about as well as uncompressed.

❌ tsz is not designed to prioritize (de)compression rates over memory usage or compression ratio.

Interface

With a macro (or manually), implement the 2 traits for compression Compress and IntoCompressBits and/or 2 traits for decompression Decompress and FromCompressBits.

From the end-to-end tests using a procedural macro to generate the delta encoding match and trait implementations, we have a functional example

// Import proc_macros and trait definitions
use tsz_compress::prelude::*;

// `Row` must be a `Copy` struct of integral primitives
// `DeltaEncodable` generates a `RowDelta` struct to represent the difference between rows and how to add/subtract them
// `Compressible` generates `Compress` and `IntoCompressBits` implementations for a `Row` and `RowDelta` struct
// `Decompressible` generates `Decompress` and `FromCompressBits` implementations for a `Row` and `RowDelta` struct
#[derive(Copy, Clone, DeltaEncodable, Compressible, Decompressible)]
pub struct Row {
    pub ts: i64,
    pub val0: i8,
    pub val1: i16,
    pub val2: i32,
    pub val3: i64,
}

// Create a compressor instance to hold compression state
let mut c = Compressor::new();

// Insert a bunch of rows
let lower = -100000;
let upper = 100000;
for i in lower..upper {
    let row = AnotherRow {
        ts: i,
        val0: i as i8,
        val1: i as i16,
        val2: i as i32,
        val3: i as i64,
    };
    c.compress(row);
}

// Emit the final encoded bits
let bits = c.finish();

// Create a decompressor instance to hold decompression state
let mut d = Decompressor::new(&bits);

// Iterate through rows, decompressing each subsequent row on the Iterator::next call
// All rows don't have to be read all at once, but typically are using the iterator pattern
for (i, row) in d.decompress::<AnotherRow>().unwrap().enumerate() {
    let row = row.unwrap();
    let i = i as isize + lower as isize;
    assert_eq!(row.ts, i as i64);
    assert_eq!(row.val0, i as i8);
    assert_eq!(row.val1, i as i16);
    assert_eq!(row.val2, i as i32);
    assert_eq!(row.val3, i as i64);
}

Example

The following example encodes 2 timestamps and 4 values. The first timestamp is an SoC uptime ms. The second timestamp is UTC us. The values are 4 channels of int16_t data incrementing slowly and sometimes resetting. Data in this example is collected at 1 Hz.

Compresses down by 3.2x in example here, extrapolating to 5.9x per 251 byte packet if example continued.

See the docs for more info.

Best-case Compression Example

For maximal compression ratio, an incrementing integer requires 1 bit per value to represent after the delta and delta-delta header. In this trivialized example, we have 63.999x compression at 1.5GBps.

use tsz_compress::prelude::*;

#[derive(Clone, Copy, DeltaEncodable, Compressible, Decompressible)]
struct Row {
    a: i64,
}

fn main() {
    let start = std::time::Instant::now();
    let mut c = Compressor::new();
    for i in 0..1000000000 {
        let row = Row { a: i };
        c.compress(row);
    }

    // Prints: 'compressed size: 125000002 bytes
    println!("compressed size: {} bytes", c.len());
    let bytes = c.finish();
    // Prints: `5.232524s`
    println!("{:?}", start.elapsed());

    let mut d = Decompressor::new(&bytes);
    d.decompress::<Row>()
        .unwrap()
        .enumerate()
        .for_each(|(i, row)| {
            assert_eq!(row.a, i as i64);
        });

    // Prints: `10.380991875s`
    println!("{:?}", start.elapsed());
}

Benchmarks

Initial benchmark results for compression on M1 Max Pro (not target platform)

Consistent delta and delta-delta compresses faster than continuously changing data.

19000 bytes per iteration yields between 173MiB/s to 960MiB/s on "good" hardware.

compress monotontic 500 time:   [109.46 µs 109.77 µs 110.06 µs]
                        change: [-0.2060% +0.0239% +0.2984%] (p = 0.85 > 0.05)
                        No change in performance detected.
Found 18 outliers among 100 measurements (18.00%)
  1 (1.00%) low mild
  5 (5.00%) high mild
  12 (12.00%) high severe

compress linear 500     time:   [19.752 µs 19.791 µs 19.838 µs]
                        change: [+0.0169% +0.2636% +0.4882%] (p = 0.03 < 0.05)
                        Change within noise threshold.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high severe