Gorilla XOR compression

Deep dive

How it works

In: a stream of (timestamp, f64) points in time order · Out: a bit stream per chunk · State: previous timestamp and delta, previous value bits, and the previous leading/trailing-zero window · Cost: O(1) per point, bit-serial; typically 1-2 bytes per point

Timestamps (first stored raw):

1. d = t − t_prev, dd = d − d_prev.
2. dd = 0 → 0; small ranges → 10 + 7 bits, 110 + 9 bits, 1110 + 12 bits; otherwise 1111 + full width. (The paper's ranges are [−63, 64] etc. with 32 bits in the last case; the code below uses two's complement ranges and 64 bits.)

Values (first stored raw):

1. x = bits(v) XOR bits(v_prev).
2. x = 0 → 0.
3. Else 1, then: if x's leading and trailing zero counts are at least those of the previous stored window → 0 + the bits inside the previous window.
4. Otherwise 1 + 5 bits leading-zero count + 6 bits length of the meaningful block + the block; this becomes the new window.

v_prev = 24.0  0x4038000000000000
v      = 24.5  0x4038800000000000
xor            0x0000800000000000   lead = 16, trail = 47, meaningful = 1 bit
stored: 11 [10000] [000000] [1]  = 14 bits instead of 64

Code

pub struct BitWriter { buf: Vec<u8>, acc: u64, n: u32 }

impl BitWriter {
    pub fn put(&mut self, v: u64, bits: u32) { // MSB-first, bits <= 64
        if bits > 32 { self.put(v >> 32, bits - 32); return self.put(v & 0xFFFF_FFFF, 32); }
        self.acc = (self.acc << bits) | (v & ((1u64 << bits) - 1));
        self.n += bits;
        while self.n >= 8 { self.n -= 8; self.buf.push((self.acc >> self.n) as u8); }
    }
}

pub struct Encoder { w: BitWriter, n: usize, t: i64, d: i64, v: u64, lead: u32, trail: u32 }

impl Encoder {
    pub fn new() -> Self {
        let w = BitWriter { buf: Vec::new(), acc: 0, n: 0 };
        Encoder { w, n: 0, t: 0, d: 0, v: 0, lead: u32::MAX, trail: 0 } // lead MAX = no window yet
    }
    pub fn push(&mut self, t: i64, v: f64) {
        let bits = v.to_bits();
        if self.n == 0 {
            self.w.put(t as u64, 64);
            self.w.put(bits, 64);
        } else {
            let d = t - self.t;
            let dd = d - self.d;
            match dd {
                0 => self.w.put(0, 1),
                -64..=63 => { self.w.put(0b10, 2); self.w.put(dd as u64, 7); }
                -256..=255 => { self.w.put(0b110, 3); self.w.put(dd as u64, 9); }
                -2048..=2047 => { self.w.put(0b1110, 4); self.w.put(dd as u64, 12); }
                _ => { self.w.put(0b1111, 4); self.w.put(dd as u64, 64); }
            }
            self.d = d;
            let x = bits ^ self.v;
            if x == 0 {
                self.w.put(0, 1);
            } else {
                let (lead, trail) = (x.leading_zeros().min(31), x.trailing_zeros()); // lead has 5 bits
                if self.lead != u32::MAX && lead >= self.lead && trail >= self.trail {
                    self.w.put(0b10, 2); // fits the previous window
                    self.w.put(x >> self.trail, 64 - self.lead - self.trail);
                } else {
                    let len = 64 - lead - trail; // 1..=64, stored as len-1 in 6 bits
                    self.w.put(0b11, 2);
                    self.w.put(lead as u64, 5);
                    self.w.put((len - 1) as u64, 6);
                    self.w.put(x >> trail, len);
                    (self.lead, self.trail) = (lead, trail);
                }
            }
        }
        (self.t, self.v, self.n) = (t, bits, self.n + 1);
    }
    pub fn finish(mut self) -> Vec<u8> { // point count is stored by the caller (chunk header)
        if self.w.n > 0 { self.w.buf.push((self.w.acc << (8 - self.w.n)) as u8); }
        self.w.buf
    }
}

struct BitReader<'a> { buf: &'a [u8], pos: usize }

impl BitReader<'_> {
    fn get(&mut self, bits: u32) -> u64 { // bit-serial for clarity; real decoders refill a u64
        (0..bits).fold(0, |v, _| {
            let b = self.buf[self.pos >> 3] >> (7 - (self.pos & 7)) & 1;
            self.pos += 1;
            (v << 1) | b as u64
        })
    }
    fn bit(&mut self) -> bool { self.get(1) == 1 }
}

fn sext(v: u64, bits: u32) -> i64 { ((v << (64 - bits)) as i64) >> (64 - bits) }

pub fn decode(buf: &[u8], n: usize) -> Vec<(i64, f64)> {
    let mut r = BitReader { buf, pos: 0 };
    if n == 0 { return Vec::new(); }
    let (mut t, mut v) = (r.get(64) as i64, r.get(64));
    let (mut d, mut lead, mut trail) = (0i64, 0u32, 0u32);
    let mut out = vec![(t, f64::from_bits(v))];
    for _ in 1..n {
        d += if !r.bit() { 0 }
            else if !r.bit() { sext(r.get(7), 7) }
            else if !r.bit() { sext(r.get(9), 9) }
            else if !r.bit() { sext(r.get(12), 12) }
            else { r.get(64) as i64 };
        t += d;
        if r.bit() {
            if r.bit() { lead = r.get(5) as u32; trail = 64 - lead - (r.get(6) as u32 + 1); }
            v ^= r.get(64 - lead - trail) << trail;
        }
        out.push((t, f64::from_bits(v)));
    }
    out
}

Complexity and constants

• Best case per point: 2 bits (dd = 0, same value). Typical: 1-2 bytes. Worst: ~4 + 64 + 13 + 64 bits.
• Encode and decode are O(1) per point but bit-serial with data-dependent branches: order of 10-50 ns per point, i.e., tens of millions of points per second per core. Fine for ingest; slow for analytics scans over billions.
• Chunk sizing: Gorilla blocks cover 2 hours; Prometheus cuts chunks at 120 samples. Smaller chunks mean faster random access and more header overhead.

Efficiency

• Cost: best case 2 bits per point (dd = 0, same value), typical 1-2 bytes, worst about 4 + 64 + 13 + 64 bits. Facebook reported 1.37 bytes per point against 16 raw (about 12x). Encode and decode are O(1) per point but bit-serial with data-dependent branches: order of 10-50 ns per point, tens of millions of points per second per core. Bound: branch misprediction and bit-level serial dependency, not memory bandwidth.
• Levers:
  • 64-bit refill buffer with leading_ones() on peeked bits — reads the timestamp prefix in one step — decode path
  • chunk size (Gorilla 2 hours, Prometheus 120 samples) — larger means less header overhead, smaller means faster random access — tune per query pattern
  • zstd over closed chunks — more ratio for cold data — immutable chunks
  • ALP or delta of scaled integers — far better ratio and SIMD speed — doubles that hold decimals
  • Chimp128 — smaller output by comparing against one of the last 128 values — noisier series
• Naive → standard → state of the art:
  • raw (int64, f64) pairs · 16 bytes per point
  • Gorilla delta-of-delta + XOR · 1.37 bytes per point (Facebook), about 1-2 bytes in Prometheus
  • Chimp/Chimp128 for XOR-style series, ALP for decimal-like doubles · smaller output than Gorilla; ALP also decodes with SIMD

Implementation notes

• Refill reads: decode from a 64-bit buffer with leading_ones() on the peeked bits to read the timestamp prefix in one step, instead of bit-by-bit.
• Prometheus widened the timestamp buckets to 14, 17 and 20 bits because it stores millisecond timestamps where scrape jitter makes dd non-zero.
• Integer metrics (counters) stored as float64 compress well because consecutive integers share exponent bits; delta-of-delta on integer values directly (as many TSDBs do for int columns) is better still.
• Append-only: keep the encoder state per open chunk; closed chunks are immutable and can be further compressed (e.g., zstd) for cold storage.
• Out-of-order samples break delta-of-delta; buffer and sort a small window, or open a separate chunk.

Pitfalls

• The 6-bit length field cannot hold 64: store len − 1 (as above) or map 0 to 64; the original description leaves this open and implementations differ.
• The 5-bit leading-zero field caps at 31; clamp before comparing with the stored window, or the reuse test is wrong.
• Reusing the previous window when the new XOR has fewer leading zeros silently drops bits; the test must check both ends.
• Using the paper's [−63, 64] ranges with plain two's complement 7-bit fields mis-decodes 64; pick one convention and test the boundaries.
• Irregular timestamps (event data) make every dd large; Gorilla then costs more than plain delta + varint.

Variants and alternatives

In production

Monitoring: Facebook Gorilla and Beringei, Prometheus TSDB (XOR chunks, see the Prometheus storage docs). Databases: InfluxDB TSM float encoding, M3DB (M3TSZ), TimescaleDB (Gorilla for floats, delta-of-delta for integers and timestamps). IoT and industrial telemetry: Apache IoTDB.

Implementations

Sources

• T. Pelkonen, S. Franklin, J. Teller, P. Cavallaro, Q. Huang, J. Meza, K. Veeraraghavan, Gorilla: A Fast, Scalable, In-Memory Time Series Database, VLDB, 2015. paper · code
• P. Liakos, K. Papakonstantinopoulou, Y. Kotidis, Chimp: Efficient Lossless Floating Point Compression for Time Series Databases, VLDB, 2022. paper · code
• A. Afroozeh, L. X. Kuffó, P. Boncz, ALP: Adaptive Lossless floating-Point Compression, SIGMOD, 2024. paper · code
• Prometheus, Storage documentation, prometheus.io/docs/prometheus/latest/storage. docs