The block already open

The keys a capped chain leaves behind stopped a cuckoo table’s kick chain after two kicks and kept the key still displaced in an overflow block belonging to its region. At 95% load that halved the bytes an insertion moves. The lookups a filter turns away then put a Bloom filter in front of each block, so a lookup for an absent key reads a block only on the filter’s false yes, about 2% of the time at eight bits an overflow key. Filing each stopped key under its first bucket’s region halved even that. What was left was the successful lookups. A key that lives in an overflow costs its lookup one more block beyond the two buckets two probes are two misses priced, every time, and no filter can turn that lookup away, because the key is really there. So the price of the cap, once the filter is in place, is set by one number: the share of keys living in overflow.

That page measured the share after one fill, and a table that only fills can only add to it. A bucket never loses a key, so a key once stopped never finds room to return to. Its closing section pointed out that a table in use deletes. Every deletion frees a slot in some bucket, and a stopped key whose bucket gains a free slot could move back into it. The proposal compared two policies at 95% load under deletions and insertions in equal numbers: a stopped key stays in its overflow for life, or a deletion from a bucket checks its region’s overflow for a key that hashes to the freed bucket and moves it home. It predicted that without homing the share climbs under churn, and that with homing it settles near its value after one fill, at the price of reading the block on every deletion. The question was whether a structure built to spare insertions their kicks can keep its overflow small without charging every deletion a block read, or whether churn quietly turns the cap back into a scan.

The table, and what churn means here #

The table has the earlier pages’ geometry: 16,384 entries in buckets of eight, 2,048 buckets in regions of sixteen, two hash functions choosing a key’s buckets. An insertion tries its first bucket. If that is full it kicks a random resident to the resident’s other bucket, and so on, at most twice. The key still displaced after two kicks goes to the overflow block of the region of its first bucket. Filled this way to 95%, 3.7% of the keys end in overflow, close to the 3.9% the packed table of the earlier pages measured with a different stream of keys.

The packed layout’s bytes are not modelled. The questions here are how many keys live in overflow and how many blocks each policy reads and writes, and neither depends on where in a region an entry sits. Churn is 131,072 operations in pairs, eight times the table’s size. Each pair deletes a key chosen uniformly from those stored, wherever it lives, then inserts a fresh one. Three policies are compared:

• keys stay: a stopped key is never moved again;
• home at every deletion: a deletion from bucket $b$ in region $R$, when $R$’s overflow is not empty, reads $R$’s block and moves home the first key in it whose first or second bucket is $b$. Whether a region’s overflow is empty is in the region’s metadata, so asking costs nothing; reading the block costs one;
• home when the block is open: whenever a region’s block is read or written for another reason — a deletion of a key that lives there, or an insertion that stopped and is being filed — every key in it whose first bucket has room is moved home. The bucket counts are in the same region’s metadata, the counts entries found by the rank of their tag already keeps to find an entry, so this reads nothing more.

The third policy was not in the proposal. It was added after the second was measured, because of what the second cost.

The overflow settles #

When keys stay, the overflow climbs from 3.7% to 9.2% within one table’s worth of operations and then holds there for the remaining seven; it does not climb without limit. The proposal had the table’s only exit right and its rate wrong. Deletions are chosen uniformly from the stored keys, so a key in overflow is deleted as often as any other. The overflow loses keys at a rate proportional to its own size, and it gains them at the rate insertions stop. The share settles where the two balance. At 95% load an insertion into a churned table stops 9.5% of the time, and the share settles at 9.2%.

That balance is a prediction anyone can make from one number, and it holds at every load measured. If each pair deletes one key chosen uniformly and inserts one that stops with probability $p$, the overflow of $s n$ keys loses $s$ keys a pair on average and gains $p$, so it settles at $s = p$. The stop rate under churn is 4.3% at 85% load, 6.7% at 90% and 9.5% at 95%; the settled shares are 4.2%, 6.5% and 9.2%. They sit a little below the stop rates because a deletion that lands in a bucket frees a slot for the very next insertion, which then stops less often than the average insertion does. What the balance does not give is the stop rate itself, and it is not what a count of full buckets would suggest. After the fill 69% of buckets are full; after churn with keys staying, 42% are, because a tenth of the keys now live outside the buckets. Insertions stop more often in a table with fewer full buckets. The stop comes from the kick chain: a key placed under churn kicks a resident whose other bucket is full, and that is a property of the pairs of buckets the keys tie together, which no count of full buckets sees. The rate was measured, not derived.

That is two and a half times the share one fill leaves, and the reason the fill leaves less is that a fill is not a steady state. Early in a fill almost every bucket has room, and the stopped keys come only from the last stretch of it. Under churn the table is at 95% all the time, so every insertion meets a nearly full table and the stops come at the fill’s worst rate continuously.

Homing at every deletion holds the share at 4.0%, which is what the proposal predicted: near the share after one fill. Homing when the block is open holds it at 4.9%.

What homing at every deletion pays #

Homing at every deletion reads a block on 98% of deletions, and moves home a key on 21% of them. The proposal named the block read as the price and expected it to be paid often. It did not expect it to be paid almost always. A region holds 128 entries, and at 95% load with even a 4% overflow it holds five stopped keys on average, so a region with an empty overflow is rare. The metadata’s count is nearly always non-zero, and the block is nearly always read. Of the keys in that block, the one wanted is a key whose first or second bucket is exactly the freed one, one bucket of sixteen in the region, and most of the time there is none. Five block reads buy one key moved home.

The second cost is less obvious, and it is the reason the share does not fall further. A key moved home takes the slot the deletion freed, so the insertion that follows meets a table that is as full as before the deletion. Under the other two policies the freed slot is there for the new key, or for a key it kicks. Homing at every deletion takes away that slot, and the insertion pays: it kicks 0.99 times on average against 0.63, and it stops 25% of the time against 9.5%. Homing moves keys out of the overflow and the insertions put them back, at more than two and a half times the rate they did when keys stayed. The share settles at 4.0% only because homing is faster still.

Spare where a bucket can use it found the same conservation in the packed table’s spare entries: room given to one bucket is room another bucket does not have. A freed slot is room, and only one key can have it.

Moving keys home when the block is open #

The cost of homing at deletion is almost entirely the reading. Every key in overflow has its block read and written for other reasons. Its own deletion opens the block, and so does every insertion in its region that stops and is filed there. Each of those already pays for the block. While the block is open, the region’s metadata says which of its sixteen buckets have room, and any key in the block whose first bucket has room can be moved home for the price of writing the bucket.

That is the third policy. It reads a block on 4.9% of deletions, the share of deletions that fall on a key in overflow, and writes one on the 20% of insertions that stop. It moves home 0.15 keys a pair. It does not look for the freed bucket’s own keys, and it does not look at a key’s second bucket, which is in another region fifteen times in sixteen and whose room is not in this region’s metadata. It is a policy built only of reads the table was already making. The overflow settles at 4.9%, between the other two, with fewer block reads than leaving keys where they stopped. Fewer keys in overflow means fewer deletions that land on one.

It settles above homing at every deletion for a plain reason: it looks less often and at less. A block is open for it on about a quarter of pairs rather than nearly all of them, and when it looks it can move only keys whose first bucket has room at that moment. A key whose first bucket is full and whose second has room stays where it is. Those keys are about a quarter of the overflow it leaves, 26% at the end of the churn, and reaching them would mean reading a bucket in another region, which is the read the policy exists to avoid.

Three loads #

At every load the overflow of keys that stay settles at two and a half to three times what one fill leaves, and at every load homing at each deletion holds it near the fill’s value. At 85% homing at deletion brings it below, 1.0% against 1.3%, and at 95% just above, 4.0% against 3.7%. The order of the three policies is the same at every load and the gaps scale with the overflow.

The block reads behind homing at deletion fall with the load, because an empty overflow is commoner in a lighter table: 63% of deletions read a block at 85%, 87% at 90% and 98% at 95%. Even at 85%, a table whose overflow holds one key in a hundred reads a block on most deletions to move a key home on one deletion in fourteen.

The price in blocks, against the lookups that pay it back #

Homing when the block is open touches fewer blocks than leaving keys in place as soon as each deletion comes with one and a half successful lookups; homing at every deletion needs twenty to beat leaving them in place, and over a hundred to beat homing when open. A successful lookup of a key in overflow reads its block, the filter letting it through, so a lookup costs a block with probability equal to the overflow share. Every policy’s line rises with the lookups at its own settled share, and the cheaper intercept wins until a steeper line crosses it.

The difference between 4.0% and 4.9% is what homing at every deletion buys over homing when the block is open: 0.009 blocks a lookup. It pays 0.98 blocks a pair more to get it. A table would need more than a hundred successful lookups for each deletion before that trade paid, and at that ratio of reads to writes, a table that deletes so seldom has an overflow that changes so seldom that the fill’s share is near enough.

The failed lookups, which the filter page fixed, are unchanged in kind. Each still reads a block only on a false yes, at a rate set by the filter’s bits a key, which the formula everybody sizes filters with predicts closely for hashed keys like these. A larger overflow needs more filter memory to hold the same rate, so keys that stay at 9.2% cost two and a third times the filter memory of keys homed to 4.0%, at any fixed rate. A filter allowed to be wrong priced that trade of bits for a rate, and it applies to each region’s filter unchanged. That is a cost in bits rather than blocks, and it was not drawn.

What homing does to the insertions #

Every key moved home is a slot an insertion does not get, and at 95% load an insertion under homing at every deletion stops 25% of the time against 9.5% when keys stay. The cap was introduced to spare insertions their kicks. Homing gives part of them back: 0.99 kicks an insertion against 0.63, more than half again. The policy that homes when the block is open sits between, at 0.89 kicks and 20% stopped, because it too fills freed slots, a little later and a little less often.

This is the trade the proposal’s question was really about. A key in overflow is cheap to keep and costs every lookup of it a block. A key moved home is free to look up and costs the next insertion a kick, sometimes a stop. Homing at every deletion moves the cost from lookups to deletions and insertions at once. Homing when the block is open moves less of it, from fewer places, and leaves the deletions alone.

Two simplifications the counts depend on #

Uniform deletions. Every stored key is equally likely to be deleted, so a key in overflow leaves at the same rate as any other. A workload that deletes old keys first, as caches and queues do, would empty the overflow faster, because stopped keys are older than average, and a workload that deletes recent keys would empty it slower. The settled share of keys that stay is a fact about uniform deletion.

Blocks, not bytes. The packed table’s insertion cost in bytes moved, which the cap was introduced to cut, was not recounted under churn. A key moved home is an insertion into a packed bucket and shifts the entries after it; the second and third policies make 0.21 and 0.15 such moves a pair beyond the insertions themselves. That cost is real and is not on these plates.

Still open: room kept for the keys that will need it #

Homing failed to keep its gains because a freed slot can hold one key, and homing gave it to an old key rather than the new one. Every policy here treats a free slot as free for whoever asks first. A table could instead keep a slot in each region aside for stopped keys, as the slack an insertion can reach kept spare entries for insertions. A key stopped by the cap would go to its region’s reserved slot before the overflow block, and a key moved home would return to it. The reserve is a few entries in every region of 128, and it is paid for in load.

The measurement that follows reserves one, two and four entries a region at the same total memory, so the buckets hold fewer keys at the same number of stored keys, and churns it under the same three policies. It counts the overflow share, block reads and kicks. The prediction is that a reserve of two entries a region removes most of the overflow, since a region at 95% load with keys staying holds about eleven stopped keys and with homing about five. The reserve should cost each insertion about a tenth of a kick more, because the buckets are slightly fuller. It could fail on the kicks: a table whose buckets are fuller than 95% may stop insertions faster than any reserve can catch them, and then the reserve fills in the first table’s worth of churn and the overflow climbs back to where it would have been. The question is whether a few entries kept back for the cap’s victims do more than every policy for moving them, or whether in a table this full there is no room to keep.