Delta-of-delta crushes timestamps

Build a Prometheus-style time-series database (12 scenes)

Scene 03 · Delta-of-delta crushes timestamps

Scrapers run on a fixed cadence, so the second derivative of timestamps is almost always zero — encoding ~96% of timestamps in a single bit.

Previously

Labels stored once is the easy half. The hard half is timestamps — we have billions of 8-byte integers, but they arrive on a schedule.

Scene 03

Delta-of-delta crushes timestamps

Watch

Diagram

Top: input timestamps as numeric pills. Below: their first differences (Δ). Below that: differences of differences (ΔΔ) — a row of zeros means cadence is steady. Bottom: the encoded bitstring as a row of cells — control-prefix bits (`0`, `10`, `110`, `1110`, `1111`) in one tone, signed payload bits in another, with a bracket below each group naming the bit cost. A 'bits used so far' counter on the right tracks the running total against a 64-bit-per-timestamp naive budget.

Five timestamps from a 60 s scraper, animating one row at a time. First the Δ row, then the ΔΔ row — and the ΔΔ row is mostly zeros, because cadence is the rule. The encoder treats `0` as a single bit. The name for this trick is delta-of-delta encoding.

Implementation

Encoder.encode_dod

Compute ΔΔ, then dispatch on its magnitude.

1def encode_dod(t_curr, t_prev, prev_delta):
2    delta = t_curr - t_prev      # seconds since last scrape
3    dod   = delta - prev_delta   # change in cadence
4    write_prefix_code(dod)       # variable-length emit
5    return delta                 # carry forward as prev_delta

Encoder.write_prefix_code

Self-delimiting prefix tree: shorter codes for smaller dod.

1def write_prefix_code(dod):
2    if dod == 0:
3        write_bit(0)                          # 1 bit total
4    elif -63 <= dod <= 64:
5        write_bits(0b10, 2);   write_signed(dod, 7)
6    elif -255 <= dod <= 256:
7        write_bits(0b110, 3);  write_signed(dod, 9)
8    elif -2047 <= dod <= 2048:
9        write_bits(0b1110, 4); write_signed(dod, 12)
10    else:
11        write_bits(0b1111, 4); write_signed(dod, 32)

Decoder.decode_dod

Inverse: peek prefix bits, read matching signed payload.

1def decode_dod(prev_delta, t_prev):
2    if read_bit() == 0:        dod = 0
3    elif read_bit() == 0:      dod = read_signed(7)
4    elif read_bit() == 0:      dod = read_signed(9)
5    elif read_bit() == 0:      dod = read_signed(12)
6    else:                      dod = read_signed(32)
7    delta = prev_delta + dod
8    return t_prev + delta, delta

PreviousWhy one row per point is wrong NextXOR crushes adjacent floats