Delta-of-delta crushes timestamps

Scrapers run on a fixed cadence, so the second derivative of the timestamp stream is almost always zero — and a 0 ΔΔ encodes as a single bit.

Previously

Labels stored once is the easy half. The hard half is timestamps — billions of 8-byte integers eating gigabytes of disk. But they arrive on a fixed schedule, and that regularity is the storage win this screen collects.

Scene 03

Delta-of-delta crushes timestamps

Watch
Try it
Predict
Capture

What to watch for

A metrics firehose writes billions of 64-bit timestamps — gigabytes spent just on the clock. So store the gap since the previous timestamp instead of the timestamp itself: on a 60 s scraper that gap is 60 every time — a few bits, not 64. Then watch ΔΔ, the change in that gap, collapse to zeros on steady cadence, which the encoder writes as a single 0 bit. That trick is delta-of-delta encoding.

Implementation

Highlighted lines are the ones running in the diagram right now.

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

Where this sits in Build a Prometheus-style time-series database

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

Up next. Timestamps are crushed. Now what about the floats riding alongside them — are they random, or do they have structure we can exploit?

All 12 scenes in Build a Prometheus-style time-series database · Every curriculum

Built with Arqly

Every scene in Build a Prometheus-style time-series database builds on the one before it.All 12 Build a Prometheus-style time-series database scenes