A choice the fences cannot make

A levelled store keeps its keys in levels of growing size, each with a range filter, and a range query that a level’s filter rules out costs that level nothing to read. The filters share a budget of bits a key. A division chosen before the queries arrive found the best way to split it by searching every assignment against the store’s own sample of queries, and every essay since has tried to reach that fitted division with a rule a store can apply when it writes a level, from what it knows then.

The rule that has survived is the size rule: each level gets a base number of bits plus a slope times how many factors of four smaller it is than the largest level, the base chosen to spend the budget, and every setting snapped to a grid of nought, half a bit, one, two, three, four, six, eight, twelve and sixteen bits a key. A floor under every level added a floor of half a bit a key and brought it within five points of the fitted division from one bit a key up, on a store filled in shuffled order and on one filled a cluster at a time.

At half a bit a key the two stores pulled apart. A level scaled by the queries it meets found the shuffled store best served by the size rule with no floor and a gentler slope, about three and a half, which leaves its deepest level bare and was 2.2 points behind the fitted division; and the clustered store best served by the floor, which gives every level exactly half a bit and was 9.1 behind. It also found the quantity that tells the two stores apart. A level’s reach is the share of the workload’s queries that can land between its fences — half the share of the key space it spans plus half the share of the stored keys inside it, since half the queries start at a uniform point and half at a stored key. On the shuffled store every level reaches about 91% of queries; on the clustered store the newest level reaches 3%.

Its closing section proposed the obvious composite. Compute the ratio of the smallest level’s reach to the largest’s when a level is written, use the gentle unfloored division when the ratio is a half or more and the floored one below. It predicted, at half a bit and at three quarters, within three points of the fitted division on the shuffled store and within ten on the clustered — and, as the test it was not shaped on, within ten on a third store. It named the way it could fail: a store whose ratio sits near the switch, where a small error in the ratio is a whole division’s difference.

A third store #

The third store holds the same sixteen clusters of keys, 2^20 of them, in the same cluster order as the clustered store, but merged two clusters at a time: the store sees a pair of clusters with their keys interleaved, then the next pair. That is an order between the shuffled store, which sees every cluster at once, and the clustered one, which sees one. It is filled into the same levelled store — a buffer of 4,096 keys, each level four times the one above, each level’s filter rebuilt with every write, as the filter rebuilt with every write laid out — and stopped at the same six points of its fill.

Three quarters of a bit is not on the grid, so it has no even split, and the fitted division and every rule still snap each level’s setting to the grid. That makes it a budget at which the floor of half a bit is affordable with a quarter of a bit to spare, which is the one thing it was chosen to be.

What the ratio sees #

The ratio separates the two stores it was designed on, cleanly. The shuffled store sits at 1.00 at every checkpoint, since all its levels reach the same queries, and it wants the unfloored division at every one, by 14 to 35 points. The clustered store sits between 0.04 and 0.44, below the switch everywhere, and wants the floored division at three of the six checkpoints.

The store filled two clusters at a time is where the ratio stops being informative. It reads 1.00 at an eighth of the fill, 0.20 at a quarter, 0.45 at three eighths, 0.55 at a half, 0.42 at three quarters and 0.04 full. Half way through the fill its newest level holds a pair of clusters whose fences span 0.31 of the key space and half the store’s keys, so its reach is six times the clustered store’s newest level’s; at the end of the fill its ratio is the clustered store’s, 0.04. And the division it wants follows none of that: floored by 4.9 and 3.3 points at the first two checkpoints, unfloored by 9.5 to 15.7 at the last four.

Across the three stores at half a bit the switch picks the worse division six times in eighteen. Four are on the paired store. The other two are on the clustered store — at the end of the fill, where its fitted division leaves the deepest level bare and the unfloored rule is better by 9.1 points, and at the first checkpoint by 1.7.

The store the switch was not shaped on #

On the paired store at half a bit the unfloored division is within 4.1 points of the fitted division at every checkpoint, and within 2 at five of the six. The switch takes the floored division at the quarter, three-eighths, three-quarters and full checkpoints because the ratio is below a half there, and at three quarters of the fill it falls 15.9 points behind, giving every level half a bit where the fitted division gives its four levels 12, 3, 2 and nought bits a key, newest first.

That is the failure the proposal named, in a stronger form than it named it. The ratio did not sit near the switch and flicker; at three quarters it read 0.42, comfortably on the floored side, and the store wanted the opposite division by 15.7 points. The ratio is not a noisy measurement of the right quantity. On this store it is a clean measurement of a quantity that does not decide the division.

What the paired store’s fitted divisions have in common with the shuffled store’s is the deepest level left bare: nought at all six checkpoints, as on the shuffled store, where the clustered store’s fitted division gives the deepest level half a bit at four. A level that is mostly old clusters, on a workload half of whose queries are aimed at stored keys, is reached often and ruled out rarely by any filter half a bit a key can buy; the bits do more on the small levels. Whether that holds for a store’s deepest level depends on how its keys and the queries’ keys overlap, and the ratio between the newest level’s reach and the largest’s does not measure that.

Three quarters of a bit #

At three quarters of a bit a key the floored division is within 1.7 points of the fitted division at every checkpoint on all three stores. The unfloored division falls up to 23.5 points behind on the shuffled store, 34.6 on the paired and 35.3 on the clustered. The switch, which reads the shuffled store’s ratio of 1.00 and takes the unfloored division there, is 23.5 points behind on the store it was supposed to suit best.

The half-bit disagreement was never a disagreement between stores about how to divide memory. It was a disagreement about what to do when the floor is the whole budget. At half a bit a key the floor of half a bit leaves nothing to divide — every level gets exactly the budget — and the only way to give any level more is to give some level nothing, which the shuffled store’s fitted division does and the floor forbids. At three quarters the floor costs two thirds of the budget and leaves a quarter of a bit a key to move, and every store’s fitted division uses it the same way: half a bit or more on every level, the remainder on the small ones, at seventeen of the eighteen checkpoints. The fitted division at three quarters gives the shuffled store’s deepest level half a bit at five checkpoints of six, which it never did at half a bit.

So the switch’s premise holds only on a narrow band of budgets, the ones at which the floor exhausts the budget or nearly does. The sizes a store passes through found a budget of a bit a key or less was where every rule went wrong; this plate narrows that to the band where a floor cannot be paid for and something else must be done, and at three quarters of a bit it can.

Any threshold #

A switch at a half was the proposal’s choice, not a measured one. The next plate moves it.

With the threshold anywhere from 0.2 to 0.4, the switch at half a bit is 2.2 points behind on the shuffled store, 9.5 on the paired store and 9.1 on the clustered. That is inside the proposal’s bounds, by half a point on the paired store. Below 0.2 the clustered store’s quarter checkpoint, whose ratio is 0.16 and which wants the floor by 16.5 points, switches to the unfloored division; above 0.4 the paired store’s three-eighths and three-quarter checkpoints switch to the floor and it loses 15.9.

A threshold chosen after the fact, on the three stores it is then scored on, at six checkpoints each, that clears a bound of ten by half a point, is not a rule that has been tested. It has been fitted. And no threshold does better than 9.5 on the worst store, because the reach ratio orders the checkpoints in a way the right division does not follow: the paired store wants the unfloored division at ratios of 0.04 and 0.42 and the floored one at 0.20; the clustered store wants the floor at 0.16 and 0.44 and the unfloored division at 0.04.

Pricing the two on the queries #

The quantity both divisions approximate is the store’s own cost on its queries. One bit a key, divided and the filter each run carries set out what each level’s bits are worth: the queries the level meets, times what a false positive costs there, over the bits its keys take. The fitted division finds the best assignment by pricing every combination of grid settings on a sample of queries — the choosing seed — and charging the winner on a second sample, so that its score is not fitted to its own queries.

A store choosing between two divisions does not need every combination. It can price both on the same sample and take the cheaper, and charge it on the second sample as everything else is charged.

Chosen on the sample, the same two divisions are within 3.6 points of the fitted division on every store at both budgets: 2.2 on the shuffled store at half a bit and 1.7 at three quarters, 1.9 and 0.3 on the paired store, 3.6 and 0.9 on the clustered. In every row that is the better of the two divisions chosen after the fact, to the tenth of a point. The switch on the reach ratio is 23.5 on the shuffled store at three quarters, 17.9 and 15.9 on the paired store.

The sample gets every checkpoint where the choice matters right. It picks the worse division at one checkpoint in thirty-six: the paired store at a quarter of the fill at half a bit, where the floored division is 3.3 points better on the charging seed and the sample priced the unfloored one cheaper. A sample of queries is a sample, and a result the size of its own noise is the reminder that a choice between two options a few points apart is a choice a second sample might reverse. The choices that matter, ten to thirty-five points apart, no sample measured here gets wrong.

The clustered store, checkpoint by checkpoint #

Even on the store the switch was shaped on, the sample does better. The reach switch gives the clustered store the floored division at all six checkpoints, because its ratio never rises above 0.44, and that costs it 9.1 points at the end of the fill and 5.3 at the first checkpoint. The sample takes the unfloored division at both and is within 3.6 and nought. At the end of the fill the clustered store’s newest level reaches 3% of queries, the smallest reach anywhere, and its fitted division is the shuffled store’s shape — 12, 6 and nought bits a key — because a level of 4,096 keys is cheap enough to protect heavily however rarely it is reached, and protecting it heavily leaves nothing for the deepest level at half a bit. The reach ratio was designed to say protect every level, and at that checkpoint it says it about the one fill state where it is least true.

What the fences know and what they do not #

A level’s fences are free: a store knows its first and last keys when it writes it, and one length for the gaps and the clusters used the same kind of knowledge to choose a filter’s prefix length. They tell a store how much of the key space a level covers and how many of its keys lie in that span. What they cannot tell it is how the workload’s queries fall relative to the keys inside the span — whether the key-aimed half land on the level’s own keys, where a filter cannot help, or between them, where it can. That is the quantity the division turns on at half a bit, because at half a bit a key the only question is which level to leave bare, and the answer is the level whose filter would rule out least for its bits.

The size rule’s slope encodes the cheapness of protecting a small level. The reach ratio encodes how often a level is asked. Neither encodes how often a level’s filter would say no to a query that reached it, and two lengths that do the work of eleven showed on the same sixteen clusters that this is the number that moves when the arrival order moves.

The cost of asking the queries #

Choosing by the sample is not free, and the reason it is affordable is specific to the choice being between two. The fitted division prices every level at every one of ten grid settings and searches every combination — ten to the fourth for four levels. The two-way choice prices each level at the two settings the two divisions give it and adds them up: at most eight filters built against the sample instead of forty, and two sums instead of ten thousand. A store that keeps a sample of recent queries for any other reason already has what it needs.

What it gives up is the third and better division. In this study the better of the two is within 3.6 points of the fitted division everywhere, so there was little to give up; on a store whose fitted division is neither shape — some level at three bits that both rules snap to two or four — the two-way choice would be bounded by the better of two wrong answers.

What the measurement does not settle #

Three stores of one kind. Sixteen clusters, three arrival orders that differ in how many clusters arrive together. A store whose clusters arrive in bursts of varying size, or that receives updates to old clusters, would give the ratio and the sample new cases.

One workload. Half uniform and half aimed at stored keys, a few keys wide. The sample the choice is priced on is drawn from the same workload as the charge; a workload that drifts between choosing and charging would cost the sample and not the fences.

Six checkpoints and two budgets. Every worst gap is the worst of six. The band where the floor exhausts the budget was located at half a bit and shown gone at three quarters; where between them it closes is not measured.

Still open: a level priced on its own sample #

The two-way choice works because both divisions are good somewhere and the sample tells them apart. It still divides by the size rule’s shape, with the sample used only to pick between two settings of that shape. A store with a sample of queries could go further at almost no cost: price each level alone at the grid settings either side of what the size rule gives it, and move a step of bits from the level whose filter saves least per bit to the one that saves most, until no move helps — a descent from the size rule rather than a search from nothing.

The measurement that follows starts from the floored division at half a bit, three quarters and one bit a key on all three stores, takes single-step moves between levels while the sample says they help, and charges the result on the second sample. The prediction is that it ends within two points of the fitted division everywhere, in at most four moves, building fewer than a quarter of the filters the full search builds. It could fail at half a bit, where the floored division and the fitted one differ on every level at once, and a descent of single steps can stall at an assignment where no one move helps and two together would. The question is whether the division a store needs is reachable from the rule it already has by moves its own sample can price, or whether at the smallest budgets only a search finds it.