The filter rebuilt with every write

Two lengths that do the work of eleven gave each level of a log-structured store a range filter made of two prefix lengths. It used a coarse length to say no to the empty stretches of key space and a fine length to say no near the stored keys, both chosen together for the store, the workload and the memory. On a million keys in sixteen clusters, asked half with ranges in the gaps and half with ranges at the keys, the pair beat a filter holding every length from 12 to 24 bits, by 0.23 transfers a range query at ten bits a key.

Every choice on that page was made once, on a store that already held all its keys. The page’s closing section pointed out that a real store never looks like that. A log-structured store is written as data arrives: a buffer fills, is merged into the smallest level, and levels that grow past their size are merged into the next. A filter’s lengths are chosen when its level is written, from the keys the level holds then, and a small level’s keys are the ones that arrived most recently. If keys arrive in time order, as timestamps and sequence numbers do, a small level may hold two or three clusters and nothing else.

The proposal was to build the store by insertion, choose each level’s pair from its own keys whenever the level is written, and compare that with the pair chosen once on the full store. It predicted that on shuffled arrivals the levels would choose the full store’s pairs. On arrivals that come a cluster at a time, it predicted the small levels would choose pairs for a store of wide gaps and few clusters, and pay for it, about a tenth of the pair’s saving, when the next batch landed elsewhere.

A levelled store, filled one key at a time #

The keys are the earlier page’s: 2²⁰ distinct 32-bit keys in sixteen windows that together cover a sixteenth of key space, two of which happen to touch, so a level can see at most fifteen separate clusters. They go into a levelled store one at a time. A buffer of 4,096 keys is flushed by merging it into level 0. Whenever level $i$ holds more than $4096 \cdot 4^{i+1}$ keys, it is merged whole into level $i+1$, which is rewritten. The deepest level grows without limit. This is the same shape as the earlier pages’ four-level store, a run of 4,096 at the top and a size ratio of four, but grown rather than cut: the writes nobody counted priced that growth, and here it comes to 9.7 keys written for every key inserted. On the full store the levels hold 4,096, 61,440 and 983,040 keys, where the earlier pages’ static store held 16,384, 65,536, 262,144 and 704,512.

Two orders of arrival are run. Shuffled: the million keys in a random order, so every flush carries keys from every cluster. One cluster at a time: all of one cluster’s keys, shuffled among themselves, then all of the next, the clusters in a random order. That is the time-ordered case at its most extreme, where every batch lands in one place.

The store is stopped at six points of each fill, an eighth of the keys in, a quarter, three eighths, a half, three quarters and all, and charged on the earlier pages’ workload: ranges expected to hold 0.1, 1, 10 and 100 keys of the full store, half placed anywhere in key space and half centred on a key the store holds. A level that is read costs one transfer to find the range’s start and one more for every 64 of its keys inside the range, the charge the read a filter has no key for set when it found that a filter over whole keys cannot help a range at all. Filters get ten bits a key unless stated, and a candidate pair is a coarse length of 12, 14, 16 or 18 bits with a fine length from 20 to 26. Twenty-eight candidates in all, covering every pair the earlier page chose. Two policies are compared. Chosen at each write: each level carries the pair that cost it least on one sample of queries, chosen from the keys it held when last written. Chosen once: one pair for every level, the pair that costs the full shuffled store least, kept for the whole fill on both orders; at ten bits it is 12 and 22 bits. Both are charged on a second sample of queries that neither was chosen on.

The choice that cannot go stale #

The prediction’s mechanism has a problem, and it is in the store rather than the filter. The filter each run carries was built once per run for the same reason: a levelled store never adds keys to a level in place. A level changes only when a merge rewrites it, and a rewrite builds a new filter. So the keys a level’s filter was chosen from are always exactly the keys the level holds now. A small level that chose a pair for two clusters still holds those two clusters when the next batch arrives elsewhere, and when the batch reaches the level, the level is rewritten and chooses again. There is no moment at which a filter describes keys the level no longer has.

That leaves the prediction’s question smaller than it was asked, but not empty. Choosing at each write fits each level’s pair to its own keys, and the keys of a small level in a time-ordered store look nothing like the full store’s. Whether fitting them buys anything over one pair for everything is a measurement.

At every point of both fills the two policies lie on top of each other: on the full store 5.994 transfers a range query against 6.032 shuffled, and 4.969 against 4.971 one cluster at a time. Both sit within a hundredth of a transfer or two of a perfect filter, which skips exactly the levels holding nothing of the range, and far below the store with no filter at all. At half full, shuffled, choosing at each write saves 0.057 transfers a query over choosing once. That is the largest gap on either fill, 2.3% of what a perfect filter saves there.

The curves have the shape of the store rather than of the filter. Each one rises as the deepest level grows and falls when a merge collapses a level into the next; the shuffled store has four levels at half full and three at the end, and the end is cheaper. The two orders of arrival differ by one to two transfers a query, far more than either policy moves its own, and not always in the same direction. An eighth of the way in, the store filled a cluster at a time is the dearer one, 4.50 against 2.56: it holds two clusters, every level holds keys from both, and a range centred on a key finds keys in every level, where the shuffled store’s keys are still spread thin over fifteen clusters. By the end the order has reversed.

Where the transfers go, level by level #

The deepest level holds 94% of the keys and is read on almost every query, and no filter can change that: with a perfect filter it still costs 4.635 transfers a query shuffled, of 5.945. A range centred on a stored key nearly always finds keys there, and a range in the gaps is answered by the coarse prefix for that level as for every other. What a filter decides is the small levels, and on the small levels the order of arrival decides how much there is to save.

Filled a cluster at a time, the smallest level holds one cluster and the next holds two. A range anywhere else in key space finds nothing in them, and a perfect filter reads the smallest level for 0.069 transfers a query where the shuffled store’s smallest level, holding keys from every cluster, costs 0.404. The level-1 pair captures the whole of that: 0.357 against a perfect 0.357. A level whose keys sit in one place in key space is the easiest thing a prefix filter is ever asked about. Its coarse prefixes are a handful, and almost every range is ruled out by one of them.

The small levels’ share of a range filter found on the static store that the small levels are where a range filter’s memory pays most per bit. The filling store says something stronger about the case where keys arrive in order. There, the small levels need almost no memory at all.

The valley a choice is made in #

On the shuffled store’s smallest level, the cost rises with both lengths, from 0.432 transfers a query at 12 and 20 bits to 0.632 at 18 and 26; filled a cluster at a time, every pair with a coarse length of 16 bits or less lands between 0.071 and 0.092. A level of 4,096 keys spread over fifteen clusters has many distinct prefixes at every length, so its ten bits a key are thin over any of them, and the shortest fine length is the one its memory can afford. The same level holding one cluster has a few dozen coarse prefixes and a few thousand fine ones, and almost any pair rules almost everything out. Only a coarse length of 18 bits beside a fine one of 24 bits or more costs noticeably more, up to 0.198, and there the coarse filter holds about a thousand prefixes against seventeen at twelve bits.

The choosing policy picks the bottom of this valley on its own sample of queries. The pair chosen once, 12 and 22 bits, sits a couple of hundredths up its side on the shuffled level and on the floor of the clustered one. Those few hundredths are on a level that costs 0.4 transfers a query out of six. That is why the totals on the first plate barely move.

Thirteen choices with one cost #

Across the two fills the levels chose thirteen different pairs, and the pair chosen once only three times out of thirty-eight. Read alone, this plate would suggest that the right pair depends heavily on a level’s keys and its moment in the fill, and that a store choosing once is wrong at almost every level almost all the time. The first plate says otherwise. The choices wander because the valley is shallow, and a choice made on 960 sample queries a level is decided by which of a dozen nearly equal pairs happened to do best on that sample.

The one regularity is the coarse length. Twelve bits wins 28 times out of 38, and 17 of 19 times on the store filled a cluster at a time. A coarse filter of twelve bits divides key space into 4,096 cells, each a sixteenth of a cluster’s width here, so a cluster occupies sixteen or seventeen cells and the other four thousand are empty. One length for the gaps and the clusters found the coarse filter doing its work in exactly those empty cells. It is a property of the cluster size, not of a level’s contents, and a property that does not change with the contents does not need to be re-chosen.

Choosing at every write, priced #

Choosing at every write never buys more than 2.3% of what a perfect filter saves, and at two bits a key on the shuffled store it loses, by up to 2.1%. The loss is the honest part of the measurement. A pair chosen on one sample of queries is charged on another, and where the valley is flat and the memory thin, the pair that won the first sample is often a pair that did well by chance. The pair chosen once was chosen on the same kind of sample, but on the whole store’s levels together. That is three or four times as many level-queries, so it is a less noisy choice of something that barely matters.

The cost of choosing is not in transfers, which is why it does not appear on the plate. Over the fill the store writes 322 levels and 10.1 million keys. Building one pair of filters at each write hashes every written key twice, 20.3 million prefixes in all; trying twenty-eight candidates at each write hashes 568 million. A real store would choose from a sample of the level rather than all of it. Even so, a store that chooses at every write pays a large multiple of its filter-building work, at every merge, for at most a fortieth of the reads a perfect filter would save. The resolution a range filter can afford found a filter given every length from 16 to 24 bits losing to one given a single length, because the freedom divided the memory the single length kept whole. Freedom in a filter is paid for in memory or in work, and here it is paid for in work and moves nothing.

What the order of arrival does #

At two bits a key the pair captures 68% of what a perfect filter saves on a shuffled store and 94% on one filled a cluster at a time. At ten bits both orders are within a few per cent of perfect and the difference closes, but a store with two bits a key to spend is the case the filter exists for, and there the order of arrival is worth twenty-six points of the saving. The choice of lengths is worth two.

The difference is the small levels. In the shuffled store every level holds keys from every cluster, so every level’s filter has to say no near keys, which is the expensive part of the job. In the store filled a cluster at a time, the small levels hold one or two clusters and their filters say no to almost every range with a single coarse question. Their thin memory goes almost entirely to the fine filter around one cluster’s keys. The store is also cheaper to query outright, perfect filter or none: 4.961 transfers a query against 5.945 with a perfect filter, and 7.395 against 7.835 with no filter. Its levels overlap less in key space, so fewer of them hold anything of a given range. The runs a range query can skip asked how many runs a range can avoid reading; a store that arrives in order has made many of them avoidable before any filter is built.

The prediction was right about which levels would see few clusters and wrong about what that would cost. A small level holding two clusters is not a level about to be wrong. It is the easiest level in the store, and it stays that way until it is rewritten.

What the fill left out #

One merge policy. The store here is levelled: each level is one sorted run, rewritten whole, the setting at one end of the dial one dial between two structures turned. A tiered store keeps several runs a level and merges them less often, so a run lives longer, and its filter outlives more arrivals elsewhere. Even so, a run’s keys never change between merges in either policy, and a run’s filter cannot describe keys it does not hold. A store that builds filters over partitions of a run, as many do, chooses per partition, and a partition’s keys are even more concentrated than a level’s. Neither was run.

Queries that do not follow the arrivals. Ranges centred on stored keys pick a key uniformly from the whole store, so the newest cluster is asked about no more than the oldest. A time-ordered workload usually asks about recent data more often, which sends more queries to the small levels and makes their cheapness matter more. The arrival order and the query order were varied together nowhere here.

Two arrival orders at their extremes. Real time-ordered keys drift across key space rather than jumping from one cluster to the next, and real shuffled keys are rarely uniform. Every intermediate order lies between the two measured here, and nothing says where.

Still open: memory taken from the levels the order already filters #

The store filled a cluster at a time leaves a perfect filter almost nothing to do on its small levels, and its filters there already capture nearly all of that nothing at two bits a key. Every bit a key of filter memory on those levels is spent on a question the coarse prefix has mostly answered. The deepest level, meanwhile, holds fourteen clusters and costs 4.537 transfers a query with its pair against a perfect filter’s 4.535. It has nothing left to gain from memory either. So the place memory could still pay is the middle level, which holds two clusters and part of the fill’s history, and the earlier pages’ even split of bits a key across levels was never measured against a store whose levels differ this much.

The measurement that follows gives the filling store a fixed total of filter memory and divides it among the levels in proportion to what each level’s filter would save per bit, re-dividing at every write. It runs both orders at two and four bits a key on average. The prediction is that on the store filled a cluster at a time almost all of the memory moves to the middle level and the deepest, and the store’s total falls by a few hundredths of a transfer a query, while on the shuffled store the even split is already close to right. The question is whether a store that knows its keys arrive in order should stop paying for filters on the levels the order has already filtered, or whether the memory moved there buys as little as the choice of lengths did.