The lookups a filter turns away

The keys a capped chain leaves behind capped a packed cuckoo table’s kick chain at two kicks and put each key the cap stopped into a separate overflow block belonging to its region. At 95% load that halved the bytes an insertion moves, from 1,502 to 734, and moved the cost to lookups. A lookup for a key that is not in the table can no longer answer no after reading its two buckets, which two probes are two misses priced at two cache lines, because the key might have been stopped by the cap and put aside. It has to read the overflow too.

Its closing section proposed a filter. Keep, for each region, a small Bloom filter over the keys in that region’s overflow, stored with the region’s other metadata. A filter allowed to be wrong described the bargain: a filter never says no about a key it holds, and says yes about a key it does not hold at a rate set by its bits. A failed lookup asks the filter, and follows the pointer to the block only when the filter says the key might be there. The section predicted that at eight bits for each overflow key the share of failed lookups that still reach a block would fall from 100% to about 2%. That would move the rate at which the cap pays for itself from a handful of failed lookups an insertion to several hundred.

The table, and what is added to it #

The table is the earlier page’s, filled by the same keys in the same order to the byte. It has $2^{14}$ slots in buckets of eight, two hash functions, one-byte tags kept sorted in each bucket, and 32-byte entries packed by tag rank in a region for every sixteen buckets, so 128 regions. Each insertion’s kick chain is capped at two kicks, and the key still displaced goes to its region’s overflow block, allocated four entries at a time. At 95% load the table holds 15,565 keys, and 609 of them, 3.9%, sit in overflow blocks — 4.76 to a region on average, from none in four regions to eleven in one.

The addition is a Bloom filter in each region that has an overflow, over that overflow’s keys. Its size is stated in bits for each overflow key, and it grows with the block, by four keys’ worth of bits whenever the block gains a chunk of four entries. It uses $k = \mathrm{round}(b \ln 2)$ probe positions at $b$ bits a key, which is the textbook choice. Each probe position is taken from the top bits of a 32-bit hash by multiplying by the filter’s length, the reduction that two hashes that shared their low bits found safe. The filter’s hash is a full avalanche mix of the key, unrelated to the two bucket hashes, so the filter cannot inherit anything from where the key was placed.

Each measurement asks 16,384 keys that are not in the table. A lookup for one of them checks the filter of each of its two buckets’ regions. A region with no overflow has no filter and answers no; one with an overflow and no filter answers yes. The count is of lookups where at least one region answers yes, and of blocks read, one for every region that does.

Every failed lookup reads two blocks, not one #

With no filter, a failed lookup at 95% load reads 1.93 blocks. The earlier page counted the cost as one extra line, on the reasoning that the 9.4 overflow entries a failed lookup must compare would fit in one line if their tags were packed. They would, but they are not in one place. A key stopped by the cap is put in the overflow of the region of the bucket it was bound for when the cap stopped it, and that can be either of its two buckets. A lookup does not know which, so it has to read both regions’ overflows. At 95% load 93% of absent keys have an overflow in both regions, so 93% of failed lookups read two blocks, and the average is 1.93.

That halves the exchange rate the earlier page gave. The cap of two in a block saves 768 bytes an insertion between 90% and 95% load, twelve 64-byte lines. At one line a failed lookup, it paid for a table that saw fewer than twelve failed lookups for every insertion. At 1.93 lines it pays below about six. That page has been corrected. The correction matters here because it is also the reason a filter cannot do what the prediction said it would do by itself.

The same structure appears in a block the lookup can work out. There a Bloom filter that sent each key to the emptier of two blocks doubled its false positives, because a lookup could not know which block had been chosen and had to ask both. A capped cuckoo table makes the same choice without meaning to. Where a stopped key ends up depends on where its chain was when the cap stopped it, and a lookup cannot recover that.

Two per cent, for two reasons that cancel #

At eight bits an overflow key, 2.07% of failed lookups at 95% load reach a block. The prediction said about 2%. The number is right, and the reasoning that produced it is wrong in two places, in opposite directions.

The first error is the one above. The prediction treated a failed lookup as asking one filter. It asks two, so the share that reaches a block is about twice one filter’s rate. At the 2.16% that the textbook formula gives for one Bloom filter at eight bits a key, two filters would let about 4.3% through.

The second error runs the other way. A filter here does not hold eight bits a key. It grows with its block, four keys at a time, so a region whose overflow holds five keys has a block of eight entries and a filter of 64 bits, 12.8 bits a key. Averaged over the table, eight nominal bits hold 10.35 bits for each overflow key, a third more than stated. At 10.35 bits a key the formula gives one filter a rate of 0.72%, and two filters about 1.45%.

The measured rate of one region’s filter is neither of those numbers. It is 1.08%, half as much again as the formula gives for the bits it holds. The formula is a limit for large filters, and at eight bits a key these hold between 32 and 96. The formula everybody sizes filters with found a filter of four thousand random keys within 4% of it. A filter of five keys is a different object. Its fill varies from region to region, and because the rate grows with the fill raised to the sixth power, the regions that come out fuller than average raise the mean by more than the emptier ones lower it. Two filters at 1.08% give 2.07%: a third more bits than stated, spent in filters too small to use them as well as the formula assumes, and asked twice.

At 90% load the overflow is thinner, 81% of absent keys meet an overflow in both regions rather than 93%, and eight bits let 1.6% of failed lookups through. The shape of the curve is the same at both loads. Each two bits a key cut the rate by a factor of about three, a little steeper than the formula’s 2.6, starting from a level twice as high as one filter’s.

A shortcut that costs half as much again #

The measurement above computes every probe position from its own mix of the key. With the textbook shortcut — two hashes, and probe $i$ at $h_1 + i\,h_2$ — eight bits let 3.0% of failed lookups through, not 2.07%, and twelve bits let 0.93% through, not 0.26%. The shortcut is standard because in a large filter it is as good as independent probes and costs two hash computations instead of $k$. In a filter of a few dozen bits it is not.

The reason is how the probes are spaced. Reduced to a filter of $m$ bits, the step $h_2$ becomes a step of $h_2 m / 2^{32}$ bits between consecutive probes. When $h_2$ is small enough that this step is under one bit, several of a key’s probes land on the same bit, and the key is effectively tested at fewer positions than $k$. The chance of that is about one in $m$, which is negligible in a filter of a million bits and is several per cent in a filter of forty. It sets a floor under the rate that adding bits lowers only slowly, because a key whose probes collapse onto one or two bits is a false positive whenever those bits are set. The two curves agree at two and four bits, where the rate is set by fill, and separate from six bits on, where it is set by the collapsed keys. By twelve bits the shortcut lets through three and a half times as many lookups.

A filter this small can afford $k$ separate mixes. At eight bits a key, $k$ is six, and six multiplications of a 32-bit word are cheap next to the cache line they decide whether to read. Every other measurement here uses the separate mixes.

Bits in every region, or bits for every key #

The proposal placed the filter in the region’s metadata. The simplest version of that gives every region the same number of bits, whatever its overflow holds, and never has to grow or rebuild anything. Sixty-four bits in every region hold 13.5 bits for each overflow key and let 2.53% of failed lookups through. A filter sized to its region’s overflow at ten nominal bits holds 12.9 and lets 0.76% through, a third as many, on fewer bits.

A fixed filter loses because the overflow is uneven. At 95% load a region’s overflow holds anywhere from none to eleven keys. A fixed filter must choose its number of probes once, for the table, and the choice is made for the mean of 4.76 keys: nine probes in 64 bits. A region with two keys has a nearly empty filter and a rate far below what it needs. A region with eleven has a filter nearly half full, and nine probes into a half-full filter pass one lookup in about five hundred at best and many more at the fill these regions reach. A failed lookup is as likely to land in a crowded region as in a sparse one, so the crowded regions set the average. A sized filter spends its bits where the keys are, and every region’s filter sits near the same fill.

Doubling a fixed filter to 128 bits a region brings its rate to 0.14%, at 26.9 bits for each overflow key, which is 1.05 bits for every key in the table. That is still small beside 32-byte entries, and a designer who wants a filter that never grows could simply buy it. But at every size the sized filter reaches the same rate on a quarter to a third fewer bits, and the price of sizing is only that the filter grows when the block does. Growing a Bloom filter means building it again from the keys, and the keys are in the block, which the insertion that grows it is already writing.

One region to ask #

The factor of two comes from not knowing which region a stopped key went to, and that is a choice the table makes, not a property of cuckoo hashing. File every stopped key under the region of its first bucket, whichever bucket its chain had reached when the cap stopped it, and a failed lookup asks one region. With no filter it reads 0.98 blocks instead of 1.93, and at eight bits an overflow key 0.90% of failed lookups reach a block instead of 2.07%.

The change costs nothing measurable. With the overflow in a separate block, putting a key into an overflow writes one entry and a tag wherever the block is, so writing it to the first bucket’s region’s block moves the same 33 bytes as writing it to the other region’s. The table’s content, meaning which keys are in buckets and which are in overflow, is identical. Only the filing differs. The one filter each lookup now asks holds 10.6 bits for each overflow key at eight nominal bits and passes 0.98% of the lookups that ask it, much as before, since the keys are redistributed rather than changed.

This is the threshold of a block the lookup can work out in its simplest form. There a two-block filter recovered one block read by letting the lookup compute which block a key had gone to. Here the choice was never needed at all. The cap stops a key wherever its chain happens to be, but nothing about the overflow requires it to be stored near that point. A key can be filed under any rule a lookup can recompute. The first bucket is the obvious one.

It would not be free with the overflow in the region’s spare. There, the earlier page found, an overflow insertion shifts entries across much of a region, and the region is the one the key was bound for because that is where the chain left it. Filing it under another region would add a second region’s shift to the cost. The block design makes the choice of region free, and that is a second reason, after the halving of bytes moved, to keep the overflow out of the regions.

Where the saving is spent #

With eight bits an overflow key, the cap of two pays for itself up to 574 failed lookups for every insertion near full load, and with the keys filed under their first bucket up to 1,329. Without a filter the figure was 6.2. The prediction said the filter would take it to several hundred, and it does. The filter’s memory is small beside what it buys: at eight nominal bits it holds 0.41 bits for every key in the table, where a floor on the bits would allow a filter of the same rate about two thirds of that.

Lookups that find their key are the other half of a table’s reads, and the filter does nothing for them. A lookup for a key that lives in the overflow reads its two buckets, finds nothing, asks the filter, is told yes — correctly — and reads the block. At a cap of two, 3.9% of the table’s keys live in overflow blocks, so a successful lookup reads 0.039 blocks on average. That is more than a failed lookup reads with the filter, 0.021 filed as built and 0.009 filed first. Once the filter is in place, the lookups that pay most for the overflow are the ones that find what they were looking for, and the cap of two breaks even at 307 successful lookups an insertion.

The caps then trade differently. With no filter, failed lookups set the exchange rate, and every cap breaks even at between four and nine failed lookups an insertion. With a filter, successful lookups set it: the lower the cap, the more keys in overflow and the lower the break-even, from 155 successful lookups an insertion at a cap of zero, where 12.0% of keys are in overflow, to 631 at a cap of eight, where 0.8% are. A table that is read far more than it is written wants a high cap even with a filter, because the filter protects the failed lookups and leaves the successful ones exposed. A table that is written about as often as it is read can take a cap of zero, and saves eighteen lines an insertion. The figures at a cap of eight rest on a handful of false positives in 16,384 lookups, and only their order of magnitude should be read.

The filter each run carries found the same shape in a log-structured store. There a filter on every run buys back most of a missing key’s reads, and what remains is the reads that find something. The read a filter has no key for found the other limit: a range query names no key, so no filter helps it. A capped cuckoo table has no range queries, but it has the same asymmetry between a lookup that ends in no and one that ends in yes. A filter is a device for making no cheap, and it cannot touch yes.

What the numbers rest on #

One fill, one seed. Every number is one fill of the earlier page’s table, and every filter rate is measured over 16,384 absent keys. At rates near 1% that is about 160 false positives, enough for the curves’ shape and for differences of a third, not for the second significant figure at twelve bits, and not for the cap-of-eight points.

The filter’s placement is assumed free. The proposal put the filter with the region’s metadata, in a line a lookup reads anyway, and every blocks-read figure here charges the filter nothing. With 128 regions and filters of about fifty bits, it fits beside a region’s pointer. Whether a given layout reads that line on a failed lookup is a property of the layout, not measured here.

The filter’s upkeep is described, not charged. An overflow insertion sets $k$ bits in its region’s filter, and a block that gains a chunk rebuilds its filter from the block’s keys. Neither is added to the bytes an insertion moves. Both are small beside the 768 bytes an insertion the cap saves, but they are not zero.

The table only fills. Keys are inserted and never deleted, so a key put in an overflow stays there, and the 3.9% is the share after one fill to 95%. An insertion that can fail kept a stash for the rare chain that never settles; the overflow here is that stash made routine, and it inherits the stash’s one-way door. A table that deletes as well as inserts frees room in buckets, and whether its overflow grows or shrinks under that churn is the question below.

Still open: a table that deletes, and keys that go home #

With a filter in place, the successful lookups set the cost of the cap, and they are set by one number: the share of keys living in overflow. In a table that only fills, that share can only rise, since a bucket never loses a key and no stopped key ever has room to return to. A table in use deletes. Every deletion frees a slot in some bucket, and a stopped key whose first or second bucket gains a free slot could move back into it, leaving the overflow and the filter.

The measurement that follows holds the table at 95% load under a stream of deletions and insertions in equal numbers, with the cap of two, and compares two policies. In one, a stopped key stays in its overflow for life. In the other, a deletion from a bucket checks its region’s overflow for a key that hashes to that bucket and moves it home. The prediction is that without homing the overflow share climbs under churn, because every insertion near full load has a third of a chance of adding to it and a deletion from the overflow is rarer than one from the buckets. With homing it should settle near the share after one fill, 3.9%. The price is a read of the overflow on every deletion. The block and its filter make that cheaper, since the filter is keyed on the key and a deletion knows its bucket, not the key it hopes to find — so it has to read the block. The question is whether a structure built to spare insertions their kicks can keep its overflow small under deletions without charging every deletion a block read, or whether churn quietly turns the cap back into a scan.