Capstone — Quarry's Record Codec
In short: the record codec is every earlier lesson in one pipeline — pack each record's fields with shifts and width checks (lessons 1–2) in O(1) per record, OR each accepted record's shard into a 64-bit bitset (lessons 3–4) for an O(1) "worth opening" test, and compare epochs with masked subtraction so the ring they count around (lesson
- doesn't break "newer than". Encoding n records is O(n) time and O(n) space for the output words, with O(1) extra space per record beyond that.
Eight lessons ago Quarry was a promise: a storage engine that keeps a hundred million record headers in 400 MB instead of 20 GB. You now have every piece that takes. This capstone joins them into the record codec, the part that turns a batch of incoming records into a segment. That's a list of packed 32-bit header words plus a small index that lets queries skip segments without reading them.
Here's what the codec has to do, and the lesson each part comes from:
| Job | Tool | From |
|---|---|---|
| Pack id, shard, type and epoch into one word | shifts, OR, width checks | lessons 1–2 |
| Refuse a record that doesn't fit | value >> width must be 0 |
lesson 2 |
| Answer "which shards are in this segment?" in one word | a bitset, |=, popcount |
lessons 3–4 |
| Compare epochs that wrap around at 2,048 | masked subtraction | lesson 1 |
| Skip whole segments at query time | masks as sets, & |
lessons 4 and 8 |
The layout, as data
Hard-coding shifts like << 20 in four places is how layouts drift apart. The codec
keeps the layout as a table and derives every shift and mask from it. Changing the
layout (lesson 2's repack) is then a one-line edit:
Packing walks the same table from the top. A field that doesn't fit makes the whole record invalid, and the codec rejects it instead of corrupting it:
LAYOUT = [("id", 12), ("shard", 6), ("type", 3), ("epoch", 11)]
def encode(record):
w = 0
for (name, width), value in zip(LAYOUT, record):
if value < 0 or value >> width:
return None
w = (w << width) | value
return w
print([encode(r) is None for r in ([4095, 63, 7, 2047], [4096, 0, 0, 0], [1, 2, 8, 3])])Querying without unpacking
A query such as "type 5 records" doesn't need all four fields. One shift and one mask reads the type, so the codec compares fields right inside the packed words:
words = [0xAB496CD2, 0x0110CFFF, 0x00530800]
print([(w >> 11) & 0x7 for w in words], [w >> 20 for w in words])The shard bitset
Quarry has 64 shards, so "which shards does this segment touch?" is a subset of 64
things, and that fits in one word. The codec ORs in 1 << shard for every record it
accepts. At query time a request for shards {3, 12} becomes a mask too, and a single
AND tells the planner whether the segment is worth opening:
A set of 22 small ints costs a couple of kilobytes, and the bitset costs 8 bytes. The
set's membership test is a hash lookup, while the bitset's is a shift and an AND.
Union and intersection of two segments' shards are one | or &. The bitset only
loses when the universe is huge and sparse. A bitset over 2³² ids would be 512 MB even
if it held three of them, and then a Bloom filter or a real set is the answer.
Interview corner — the shards two segments share
Given two segments' shard masks, list the shards they have in common, in increasing order, in time proportional to the number of shared shards rather than to 64. AND the masks, then peel off set bits with the lowbit trick from lesson 3. Each pass removes exactly one:
Epochs wrap around
The epoch field is 11 bits, so after epoch 2,047 comes epoch 0 again. That's lesson 1's
wraparound, and it's deliberate: counting forever would need an ever-wider field.
It means a > b is the wrong test for "a is newer". Epoch 5 written just after epoch
2,040 is newer. The standard fix, serial-number arithmetic, measures the forward
distance from b to a modulo 2,048. If it's between 1 and 1,023, a is newer. This
works as long as two live versions of a record are never more than half the ring apart:
Epochs count round a ring of 2,048 values. Newer means a short hop forward, not a bigger number.
A record was last written at epoch 2044. 10 cells. b at index 0.
The masked subtraction (a - b) & 0x7FF is the same as % 2048 for a power of two. It
also gives exactly what an 11-bit register would hold after the subtraction. This
merge keeps the "newest" version of each record, but it trips over the wrap:
It prints {7: 2040, 9: 101}. Epoch 5 came after 2040, because the counter wrapped past 2047, but a plain > says it's older.
Watch your codec pack a stream
Here's the whole codec running over a small stream of records. Each frame shows one record's 32-bit word, with the lanes lit. A rejected record lights the field that didn't fit. Change the stream, give the shard field 7 bits and the id 11, or remove the width check and see what reaches the word:
Your codec, one record per frame. An accepted record lights its shard lane, and a rejected one lights the field that didn't fit.
Quick practice
mask = (1 << 1) | (1 << 3) | (1 << 6)
query = (1 << 3) | (1 << 9)
print(mask, mask & query != 0)It prints 7 8, the bit lengths, not the shard counts. Fix shard_count to count set bits.
🎯 Your turn
Write build_segment(records). Each record is [id, shard, type, epoch] with widths
12, 6, 3 and 11. Return a dict:
"words": the packed header words of the records that fit, in input order"rejected": the indices of the records that don't fit (any field negative or too wide)"shard_mask": a bitset with bitsset for every shardsused by an accepted record"shard_count": how many distinct shards that is
For example, build_segment([[2740, 37, 5, 1234], [4096, 1, 0, 0], [17, 3, 1, 2047]]) →
{"words": [2873715922, 17879039], "rejected": [1], "shard_mask": 137438953480, "shard_count": 2}.
Hint — pack each record with the width check from lesson 2. For accepted ones,
append the word and OR 1 << shard into the mask. Count the mask's bits at the end.
Then press ▶ Run, try the Live App chips, and hit ✓ Check. Green = Quarry's record encoder is complete. ✅