Time-series chunk storage

Deep dive

How it works

Parts:

• head chunk — per series, in-memory buffer of up to N samples that takes appends
• WAL — log of accepted samples, replayed after a crash to rebuild the heads
• sealed chunk — header (min_t, max_t, count, optional stats) plus a payload compressed per column
• chunk index — per series, chunks in time order with min_t, max_t and location
• series directory — maps a series key (instrument, or metric plus labels) to its id
• compactor — merges chunks into blocks, deletes expired blocks, writes rollups

 append(series,t,v) -> WAL (batched fsync) -> head[series]  <= N samples, RAM
                                                  | full, or older than the window
                                                  v  seal: delta-of-delta | XOR
 chunks[series]: [min_t max_t n |payload] [..] [..]     immutable, in time order
       ^ query(series,lo,hi): binary-search headers,    | compact: merge,
       | decode only the overlap, then scan the head    | retire, roll up

1. Append. Find the series (the first sample creates it), check order, log to the WAL, push to the head.
2. Seal. At N samples or a time boundary encode each column: timestamps as delta-of-delta (a regular grid gives zeros), values as XOR with the previous one. Write header, payload and checksum, add the index entry, truncate the WAL.
3. Range query. Binary-search the index for the first chunk with max_t ≥ lo, decode until min_t ≥ hi, filter the two edge chunks, scan the head. Header stats (min/max/sum, first/last for OHLC) answer covered chunks without decoding.
4. Out-of-order sample. Reject (the code below), sort inside a small reorder window in the head, or write a separate out-of-order chunk merged by queries and compaction. Prometheus rejects by default (out_of_order_time_window is 0s) and can accept a window of late samples.
5. Compaction and retention. Merge small chunks into larger blocks; drop whole blocks past retention (a file delete); write rollups (count, min, max, sum, first, last per bucket) so coarse queries skip raw samples. Prometheus compacts two-hour blocks into spans of up to 10 % of retention or 31 days.

Code

Std-only Rust: zig-zag varint delta-of-delta timestamps; values XOR-ed with the previous value, stored byte-aligned (control byte, then the non-zero middle bytes), not full Gorilla bit packing. No WAL; the index is the chunk list.

use std::time::Instant;

fn put(o: &mut Vec<u8>, mut v: u64) { // LEB128 varint
    while v >= 0x80 { o.push(v as u8 | 0x80); v >>= 7; }
    o.push(v as u8);
}
fn get(b: &[u8], p: &mut usize) -> u64 {
    let (mut v, mut s) = (0u64, 0);
    loop { let x = b[*p]; *p += 1; v |= ((x & 0x7f) as u64) << s; if x < 0x80 { return v; } s += 7; }
}
fn zz(v: i64) -> u64 { ((v << 1) ^ (v >> 63)) as u64 }
fn unzz(v: u64) -> i64 { (v >> 1) as i64 ^ -((v & 1) as i64) }

/// Immutable sealed chunk: the header stays in memory/index, `data` is the payload.
struct Chunk { min_t: i64, max_t: i64, count: usize, data: Vec<u8> }

impl Chunk {
    fn seal(s: &[(i64, f64)]) -> Chunk {
        let (mut d, mut pt, mut pd, mut pv) = (Vec::new(), s[0].0, 0i64, 0u64);
        for &(t, v) in s {
            let delta = t - pt;
            put(&mut d, zz(delta - pd)); // delta-of-delta: 0 on a regular grid, 1 byte
            (pt, pd) = (t, delta);
            let x = v.to_bits() ^ pv; // XOR with the previous value's bits
            pv = v.to_bits();
            // control byte = leading zero bytes <<4 | trailing zero bytes, then only the middle bytes
            let (lead, trail) = if x == 0 { (8, 0) } else { (x.leading_zeros() / 8, x.trailing_zeros() / 8) };
            d.push((lead << 4 | trail) as u8);
            for k in (trail..8 - lead).rev() { d.push((x >> (8 * k)) as u8); }
        }
        Chunk { min_t: s[0].0, max_t: s[s.len() - 1].0, count: s.len(), data: d }
    }
    fn decode(&self) -> Vec<(i64, f64)> {
        let (mut p, mut t, mut pd, mut pv) = (0, self.min_t, 0i64, 0u64);
        (0..self.count).map(|_| {
            pd += unzz(get(&self.data, &mut p));
            t += pd;
            let ctl = self.data[p] as u32; p += 1;
            let mut x = 0u64;
            for k in (ctl & 15..8 - (ctl >> 4)).rev() { x |= (self.data[p] as u64) << (8 * k); p += 1; }
            pv ^= x;
            (t, f64::from_bits(pv))
        }).collect()
    }
}

/// One series: open head (append-only, would be backed by a WAL) + sealed chunks in time order.
struct Series { cap: usize, head: Vec<(i64, f64)>, chunks: Vec<Chunk> }

impl Series {
    fn append(&mut self, t: i64, v: f64) -> Result<(), &'static str> {
        let last = self.head.last().map(|s| s.0).or(self.chunks.last().map(|c| c.max_t));
        if last.is_some_and(|l| t < l) { return Err("out of order: rejected"); }
        self.head.push((t, v));
        if self.head.len() == self.cap { self.chunks.push(Chunk::seal(&self.head)); self.head.clear(); }
        Ok(())
    }
    /// Samples with lo <= t < hi, plus the number of chunks that had to be decoded.
    fn query(&self, lo: i64, hi: i64) -> (Vec<(i64, f64)>, usize) {
        let first = self.chunks.partition_point(|c| c.max_t < lo); // binary search on headers
        let (mut out, mut decoded) = (Vec::new(), 0);
        for c in self.chunks[first..].iter().take_while(|c| c.min_t < hi) {
            decoded += 1;
            out.extend(c.decode().into_iter().filter(|&(t, _)| t >= lo && t < hi));
        }
        out.extend(self.head.iter().copied().filter(|&(t, _)| t >= lo && t < hi));
        (out, decoded)
    }
}

fn main() {
    let mut rng = 0x9E3779B97F4A7C15u64; // xorshift64
    let mut rnd = move || { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; (rng >> 11) as f64 / (1u64 << 53) as f64 };
    let same = |a: &[(i64, f64)], b: &[(i64, f64)]| // bit-exact, also for NaN and -0.0
        a.len() == b.len() && a.iter().zip(b).all(|(x, y)| x.0 == y.0 && x.1.to_bits() == y.1.to_bits());
    let n = 1_000_000;
    let cases: [(&str, bool, fn(f64) -> f64); 4] = [ // (name, irregular times, price transform)
        ("regular 1 s, integer gauge", false, |w| w.round()),
        ("regular 1 s, f64 walk    ", false, |w| w),
        ("ticks, price k/100 f64   ", true, |w| w.round() / 100.0),
        ("ticks, price in cents    ", true, |w| w.round()),
    ];
    for (name, irregular, f) in cases {
        let mut s = Series { cap: 120, head: vec![], chunks: vec![] };
        let (mut t, mut w, mut all) = (1_700_000_000_000i64, 10_000.0f64, Vec::new());
        for _ in 0..n {
            t += if irregular { 1 + (-(1.0 - rnd()).ln() * 200.0) as i64 } else { 1000 };
            w += rnd() * 2.0 - 1.0;
            all.push((t, f(w)));
            s.append(t, f(w)).unwrap();
        }
        let bytes: usize = s.chunks.iter().map(|c| c.data.len()).sum();
        assert!(same(&s.query(i64::MIN, i64::MAX).0, &all)); // round trip
        let (lo, hi) = (all[n / 2].0, all[n / 2 + 600].0);
        let (part, decoded) = s.query(lo, hi);
        let want: Vec<_> = all.iter().copied().filter(|&(t, _)| t >= lo && t < hi).collect();
        assert!(same(&part, &want) && decoded <= 6); // exactly the in-range samples, 6 of 8333 chunks
        let t0 = Instant::now();
        for _ in 0..5 { s.query(i64::MIN, i64::MAX); }
        let ns = t0.elapsed().as_nanos() as f64 / (5 * n) as f64;
        println!("{name} {:.2} B/sample | decoded {decoded}/{} chunks | {ns:.1} ns/sample", bytes as f64 / (s.chunks.len() * 120) as f64, s.chunks.len());
    }
    let sp = [0.0, -0.0, f64::NAN, f64::INFINITY, 1e-300, f64::MIN];
    let c = Chunk::seal(&sp.iter().enumerate().map(|(i, &v)| (i as i64 * 7, v)).collect::<Vec<_>>());
    assert!(c.decode().iter().zip(sp).all(|(a, b)| a.1.to_bits() == b.to_bits()));
    let mut s = Series { cap: 4, head: vec![], chunks: vec![] };
    s.append(10, 1.0).unwrap();
    assert!(s.append(9, 1.0).is_err()); // out-of-order policy: reject
}

Complexity and constants

• Append O(1) amortized; seal O(N); query O(log C + k·N) for k overlapping chunks; edge chunks waste up to 2(N−1) decoded samples (arithmetic).
• Head memory is 16 bytes per sample: 1 million series at N = 120 take about 1.9 GB (arithmetic). Header: 20 bytes per chunk here, 0.17 per sample at N = 120 (arithmetic).
• Measured on this Mac (Apple M4 Pro), release build, 1 million synthetic samples each, N = 120, payload only (typical of several runs; single runs had outliers up to 14 ns):

• Pruning (same machine): a 600-sample range decoded 6 of 8,333 chunks; at N = 1,000, 1 of 1,000, with payload 2.75 bytes per sample (gauge).

Efficiency

• Cost: 16 bytes per sample raw; sealed, 1-2 bytes with Gorilla-style coding (Prometheus docs) or 2.8-7.3 bytes with the codec above, decoded at 6-9 ns per sample, order of 100 M samples/s per core (measured on this Mac (Apple M4 Pro), synthetic data). Bound: ingest by WAL fsync, queries by chunks decoded (CPU) and read (I/O).
• Levers:
  • scaled integers for decimal prices — 5.58 → 3.50 bytes per sample (measured on this Mac, this codec) — fixed-tick instruments, counters
  • bit-level Gorilla coding instead of byte-aligned — 1.37 bytes per sample on production monitoring data (Gorilla paper) — slowly changing values
  • one WAL fsync per batch (group commit) — fsync shared by many series (no figure) — many series
  • rollups and header stats — coarse and OHLC queries skip raw samples (no figure) — long ranges
  • chunk size N — header 20/N bytes per sample against up to 2(N−1) extra decoded samples (arithmetic) — tune per read pattern
• Naive → standard → state of the art:
  • one row per sample in a B-tree or heap · at least 16 bytes per sample plus row overhead
  • chunks of about 120 samples, delta-of-delta plus XOR, time index · 1-2 bytes per sample (Prometheus docs)
  • WAL, time-partitioned columns, cold Parquet tier, rollups (QuestDB's tiers) · coarse queries skip raw data

Implementation notes

• Per column: time, price, size (or bid, ask, sizes) in separate runs; scaled integers for decimals.
• Spill full head chunks to disk and memory-map them (Prometheus chunks_head/).
• Seal by count (equal sizes at any rate); group by time (aligned blocks, Gorilla's two hours, make retention a file delete).
• Checksum each chunk (Prometheus: CRC32).

Pitfalls

• Cardinality: each series costs a head and an index entry; an unbounded key (user id, order id) exhausts memory before disk.
• Late data after sealing: with reject, count and alert; reconnecting feeds replay old samples.
• Duplicate timestamps are legal for ticks: require non-decreasing time.
• Half-open ranges [lo, hi) everywhere, or adjacent OHLC buckets double count.

Variants and alternatives

In production

Monitoring: Prometheus, Facebook Gorilla, InfluxDB. Financial and energy data: TimescaleDB (tutorials for tick data and energy consumption), QuestDB (OHLC views). IoT: TimescaleDB (sensor-dataset tutorial).

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, PVLDB 8(12), 2015. paper · code
• Prometheus: storage docs · index format · head chunks · head.go
• InfluxData, InfluxDB v1 storage engine. docs
• Tiger Data (Timescale), Understand hypertables. docs
• QuestDB, Architecture overview. docs