What a bound is

A share that is a clock

A file kept in six background parts and allowed to split two of them at once came within 2% to 4% of the nine-part square-root law on jumping traffic, but from about 650 queries after a jump it paid some forty transfers a query more than a background with one split, because it kept the old band's part split until merging it back paid for the rewrite. Releasing that split as soon as the old part's decayed density fell under a tenth of the new part's was predicted to bring the late cost down to the one-split background's, about 230, and the jump costs within 1% of the law. Released at a tenth it pays 262 from 650 on, the same as never releasing, because a decayed density's share is a clock: with a half-life of 250 queries the old band falls under a tenth of the new one only 865 queries after the jump, two hundred after the gap opened. A quarter, which the clock puts at 580 queries, brings the late cost to 236 for 19 transfers of the early gain, and every design stays 3.6% or more above the law.

A file of four million keys answers selection queries that fall, nine times in ten, in a band 2% of the ranks wide, and the band moves. A file written once for the queries after found that keeping the file in parts, so a query reads only its own, is what makes later queries cheap, and what a pass costs when it is a file made the block transfer the unit of every cost. Parts cut where the questions are found the square-root law, which sizes nine parts so that each part’s share of the keys times its share of the queries is the same. Every design here descends from the pass that was never a parameter, which made the number of passes a dial, and a recut the law decides recut the file when a decayed density of recent queries said the saving over a half-life of 250 queries would pay for rewriting the parts that change.

The two parts the law was not given kept most of the file fixed: six background parts by keys, and only the band’s part cut in four. A background that holds two bands let the background split two parts at once, the old band’s in three and the new band’s in two, choosing whichever of the thirty-six configurations paid most, and came within 2% to 4% of the nine-part law on jumping traffic. It had one weakness, late. From about 650 queries after a jump it paid some forty transfers a query more than the background with one split, because it kept the old band’s part split until merging it back paid for the rewrite, and by then the saving of cutting the new band in four rather than two was small.

Its closing section proposed letting go sooner. The design could drop the old band’s split as soon as the old part’s decayed density falls below a share of the new part’s, releasing its pieces to the new band without waiting for the saving to exceed the rewrite. It predicted that at a share of a tenth the late cost would fall to the one-split background’s, about 230 a query, without giving back the early gain, and that the jump costs would come within 1% of the law. The named risk was drift: there the two splits are a straddle, a band lying across a background cut, and the half of a straddling band in the emptier part might fall below a tenth of the other half for a moment and lose its split while it is still being queried.

A release that skips the test

The design is the two-split background with one rule added. At every check, every hundred queries, it looks at its partition. If two background parts are split, and the weaker’s decayed query density is under the share of the stronger’s, it recuts at once: the stronger part cut in four, the weaker merged back whole. The recut is charged its rewrite like any other, but it does not have to pass the law’s test, the saving over the half-life against the price. Otherwise the two-split design decides as before.

Three shares are measured, a quarter, a tenth and a twentieth, beside the law in nine parts, the one-split background and the two-split background with no release. Everything else is the earlier essays’: four seeds a stream, jumps every 1,000, 2,500, 5,000 or 10,000 queries on average, drift at five speeds, the decayed density’s half-life of 250 queries, the check every hundred. The cost after a jump is averaged over every jump that is not followed by another within a thousand queries.

A tenth changes nothing

Released at a tenth, the two-split background pays 262 transfers a query from 650 queries after a jump, the same as holding both splits, 264, and not the one-split background's 226; released at a quarter it pays 236Transfers a query in each stretch of 50 queries after a jump, one jump in 2,500 queries on average, averaged over every clean jump on four seeds, half-life 250. the law, nine parts: from 650, 247; to 300, 557; at 100, 300, 600 and 900: 685, 369, 313, 254; one split in four: from 650, 226; to 300, 1,057; at 100, 300, 600 and 900: 1,190, 626, 256, 225; two splits, held: from 650, 264; to 300, 670; at 100, 300, 600 and 900: 854, 446, 318, 251; released at a quarter: from 650, 236; to 300, 689; at 100, 300, 600 and 900: 853, 445, 312, 230; released at a tenth: from 650, 262; to 300, 664; at 100, 300, 600 and 900: 830, 445, 316, 251.2004006008001e+31.2e+3100250400550700850queries after a jump (one in 2,500)transfers a query650the law, nine partstwo splits, heldreleased at a tenthreleased at a quarterone split in fourone jump in 2,500; four seedstransfers a query
Fig. 1 Transfers a query in each stretch of 50 queries after a jump, one jump in 2,500, four seeds. From 650 queries on: the law 247, one split 226, two splits held 264, released at a quarter 236, released at a tenth 262. In the first 300 queries: 557, 1,057, 670, 689 and 664. The vertical line is 650 queries.

Released at a tenth, the two-split background pays 262 transfers a query from 650 queries after a jump, the same as holding both splits, 264, and not the one-split background’s 226; released at a quarter it pays 236. The tenth’s curve and the no-release curve lie on top of each other until about 800 queries, part company briefly and rejoin. The release fires so late that by the time it does the late cost has already been paid.

A quarter does most of what a tenth was supposed to. Its curve falls away from the two-split curve at about 650 queries and runs within ten transfers of the one-split background’s from there. It pays a little for it early: in the first 300 queries after a jump it costs 689 against 670 when both splits are held, because it sometimes releases the new band’s split on a jump that comes soon after another, while the new band is still the weaker one.

The prediction picked its share as if a tenth were a small amount and the question were how small a share the old band could reach before it no longer mattered. The measurement says the share’s size is not the right axis.

How long a share takes

A share is a clock: with a half-life of 250 queries the old band's decayed density falls under a quarter of the new band's 580 queries after a jump, under a tenth after 865 and under a twentieth after 1,098 — so a tenth releases two hundred queries after the late gap opensAfter a clean jump the old band's queries stop and the new band's begin, so with a half-life of 250 queries the old part's decayed density is 2^(−x/250) of what it was and the new part's 1 − 2^(−x/250); their ratio falls under a share s after 250·log2(1 + 1/s) queries: 0.5: 396, 0.25: 580, 0.1: 865, 0.05: 1,098, 0.02: 1,418. The two-split design's late cost opens at about 650 queries.00.2500.5000.750102505007501e+31.25e+31.5e+3queries after a jumpold band's density over the new band'sthe late gap opens0.5 at 3960.25 at 5800.1 at 8650.05 at 1,0980.02 at 1,418half-life 250density ratio after a jump
Fig. 2 After a clean jump, with a half-life of 250 queries, the old part’s decayed density is 2^(−x/250) of what it was and the new part’s 1 − 2^(−x/250), so their ratio falls under a share s after 250·log₂(1 + 1/s) queries: a half at 396, a quarter at 580, a tenth at 865, a twentieth at 1,098, a fiftieth at 1,418. The late gap opens at about 650.

A share is a clock: with a half-life of 250 queries the old band’s decayed density falls under a quarter of the new band’s 580 queries after a jump, under a tenth after 865 and under a twentieth after 1,098 — so a tenth releases two hundred queries after the late gap opens. After a jump the old band receives no new queries, so its decayed density falls by half every 250 queries, and the new band’s rises toward the whole. Their ratio is a deterministic function of the time since the jump, and every share is a time.

Read that way, the proposal chose a time without knowing it. It wanted the release to come when the old band no longer mattered, at about 650 queries, and a tenth arrives at 865. A quarter arrives at 580, which is just before the gap. The design that was asked for was “release at 650 queries”, and the share that says that is about a fifth.

The clock also explains why a smaller share is not a safer one. A smaller share waits longer, and a design that waits longer is the two-split design that does not release at all. The twentieth releases 0.3 times a stream at one jump in 2,500 and its costs are the no-release design’s to the transfer.

The law is still four per cent away

On every jump rate the release moves the cost by about a transfer a query: released at a quarter the background comes within 3.6% of the nine-part law at worst, holding both splits within 4.0% — not the 1% predicted — and the one-split background 16.3%Transfers a query, four seeds, half-life 250, against the nine-part law (the tick): one jump in 1,000: law 400.1; one split in four 465.3, two splits, held 407.2, released at a quarter 406.6, released at a tenth 406.7; one jump in 2,500: law 325.8; one split in four 364.9, two splits, held 333.4, released at a quarter 332.3, released at a tenth 333.2; one jump in 5,000: law 270.2; one split in four 301.6, two splits, held 276.9, released at a quarter 275.3, released at a tenth 276.6; one jump in 10,000: law 257.0; one split in four 282.9, two splits, held 267.4, released at a quarter 266.3, released at a tenth 267.3.one split in fourtwo splits, heldreleased at a quarterreleased at a tenthtransfers a query (axis from 240); tick: the law1 in 1,000465.3407.2406.6406.71 in 2,500364.9333.4332.3333.21 in 5,000301.6276.9275.3276.61 in 10,000282.9267.4266.3267.3four seedstransfers a query
Fig. 3 Transfers a query against the nine-part law’s (the tick), four seeds. One jump in 1,000: law 400.1; one split 465.3, two held 407.2, released at a quarter 406.6, at a tenth 406.7. In 2,500: 325.8; 364.9, 333.4, 332.3, 333.2. In 5,000: 270.2; 301.6, 276.9, 275.3, 276.6. In 10,000: 257.0; 282.9, 267.4, 266.3, 267.3.

On every jump rate the release moves the cost by about a transfer a query: released at a quarter the background comes within 3.6% of the nine-part law at worst, holding both splits within 4.0% — not the 1% predicted — and the one-split background 16.3%. The late gap the release closes is a stretch of a few hundred queries after each jump, worth thirty transfers a query while it lasts, and averaged over a stream it is worth about one.

Where the rest of the gap to the law lies is visible in the first plate. In the first 300 queries after a jump the law pays 557 transfers a query and the two-split background 670; the release cannot touch that stretch, since nothing has decayed yet. The law recuts all nine parts around the new band; the background keeps six fixed and can only split them. Its early cost is the price of a fixed background, and no rule about when to let go of the old band can change it.

So the prediction’s second number was asking the release to close a gap it was never placed to close. The background’s distance from the law on jumps is almost entirely early, and the release acts late.

On drift, almost nothing either way

On drift the release the risk feared does little harm: released at a quarter the background costs at most 0.6% more than holding both splits at any speed, releasing 12 times a stream at mostCost a query over the nine-part law's on drifting traffic at speeds 0.02, 0.05, 0.1, 0.2, 0.5, four seeds: speed 0.02: one split in four 0.996, two splits, held 0.996, released at a quarter 0.996 (0.0 releases), released at a tenth 0.996 (0.0 releases); speed 0.05: one split in four 0.992, two splits, held 0.992, released at a quarter 0.992 (0.0 releases), released at a tenth 0.992 (0.0 releases); speed 0.1: one split in four 1.022, two splits, held 0.939, released at a quarter 0.945 (5.0 releases), released at a tenth 0.939 (2.3 releases); speed 0.2: one split in four 0.983, two splits, held 0.920, released at a quarter 0.922 (8.3 releases), released at a tenth 0.917 (3.0 releases); speed 0.5: one split in four 0.973, two splits, held 0.906, released at a quarter 0.904 (11.5 releases), released at a tenth 0.906 (4.3 releases).0.9501drift speedcost over the law's0.020.050.10.20.5one split in fourtwo splits, heldreleased at a tenthreleased at a quarterthe lawfour seedscost over the law's
Fig. 4 Cost a query over the nine-part law’s on drifting traffic, four seeds. Speed 0.02: every background design 0.996. Speed 0.05: 0.993. Speed 0.1: one split 1.022, two held 0.939, released at a quarter 0.945, at a tenth 0.939. Speed 0.2: 0.983, 0.920, 0.922, 0.917. Speed 0.5: 0.973, 0.906, 0.904, 0.906.

On drift the release the risk feared does little harm: released at a quarter the background costs at most 0.6% more than holding both splits at any speed, releasing 12 times a stream at most. On the slow drifts nothing releases, because the band never straddles a background cut long enough for two splits to form. On the fast ones the quarter releases five to twelve times a stream and costs between 0.6% more and 0.2% less than holding both, and the tenth slightly less in both directions.

The risk named a real mechanism: a straddling band’s lesser half can fall under a share of its greater half while still being queried, and a release then takes away its split. It happens; it costs almost nothing, because a half that has fallen under a quarter of the other is a small share of the queries, and the background’s two-split advantage on fast drift, 6% to 9% under the law, survives it intact.

The drift plate is therefore the reassuring one. A rule that is a clock on jumps is, on drift, a rule about how lopsided a straddle has become, and at a quarter it lets go of the lesser half only when that half is small.

Early against late

Released at a quarter, the two-split background keeps most of its early gain — 689 transfers a query in the first 300 queries against 670 holding both and 1,057 for one split — and pays 236 from 650 on against 226: the early gain and the late cost are traded, not both wonFor each design, one jump in 2,500, four seeds: mean transfers a query over the first 300 queries after a clean jump, and from 650 to 1,000 queries after. the law, nine parts: 557 and 247; one split in four: 1,057 and 226; two splits, held: 670 and 264; released at a quarter: 689 and 236; released at a tenth: 664 and 262.2202302402502602705006007008009001e+31.1e+3transfers a query, first 300 queries after a jumptransfers a query, from 650 onthe law, nine partsone split in fourtwo splits, heldreleased at a quarterreleased at a tenthone jump in 2,500early against late
Fig. 5 For each design, one jump in 2,500, four seeds: mean transfers a query over the first 300 queries after a clean jump against the mean from 650 to 1,000 queries after. The law: 557 and 247. One split: 1,057 and 226. Two splits held: 670 and 264. Released at a quarter: 689 and 236. Released at a tenth: 664 and 262.

Released at a quarter, the two-split background keeps most of its early gain — 689 transfers a query in the first 300 queries against 670 holding both and 1,057 for one split — and pays 236 from 650 on against 226: the early gain and the late cost are traded, not both won. The proposal asked for both: the one-split background’s late cost without giving back the two-split background’s early gain. The quarter comes within ten transfers late and within twenty early, which is most of both and all of neither.

The law sits apart from every background, cheapest early by more than a hundred transfers and in the middle late. It pays its rewrites to be right early, and its late cost carries the few recuts it still makes as the new band settles. A background trades those rewrites for a fixed partition, and the plate shows the exchange rate.

What the release adds is a point between the two backgrounds on the line they already define. A quarter is near the bottom-left corner of what a background with one release rule can reach, and the law is below it.

Releases a stream

The smaller the share, the rarer the release: at one jump in 2,500 a quarter releases 9.0 times a stream, a tenth 2.0 and a twentieth 0.3, most likely because by the time the old band falls that far the design's own rule has often merged it back alreadyReleases a stream, four seeds, at each share: 1 in 1,000: 0.25 20.5, 0.1 6.0, 0.05 1.0; 1 in 2,500: 0.25 9.0, 0.1 2.0, 0.05 0.3; 1 in 5,000: 0.25 4.5, 0.1 1.3, 0.05 0.3; 1 in 10,000: 0.25 3.5, 0.1 1.0, 0.05 0.0; drift 0.02: 0.25 0.0, 0.1 0.0, 0.05 0.0; drift 0.05: 0.25 0.0, 0.1 0.0, 0.05 0.0; drift 0.1: 0.25 5.0, 0.1 2.3, 0.05 0.5; drift 0.2: 0.25 8.3, 0.1 3.0, 0.05 0.0; drift 0.5: 0.25 11.5, 0.1 4.3, 0.05 0.0.share 0.25share 0.1share 0.051 in 1,00020.5 · 6.0 · 1.01 in 2,5009.0 · 2.0 · 0.31 in 5,0004.5 · 1.3 · 0.31 in 10,0003.5 · 1.0 · 0.0drift 0.020.0 · 0.0 · 0.0drift 0.050.0 · 0.0 · 0.0drift 0.15.0 · 2.3 · 0.5drift 0.28.3 · 3.0 · 0.0drift 0.511.5 · 4.3 · 0.0four seedsreleases a stream
Fig. 6 Releases a stream, four seeds, at shares of a quarter, a tenth and a twentieth. Jumps every 1,000: 20.5, 6.0 and 1.0. Every 2,500: 9.0, 2.0 and 0.3. Every 5,000: 4.5, 1.3 and 0.3. Every 10,000: 3.5, 1.0 and none. Drift 0.02 and 0.05: none. Drift 0.1: 5.0, 2.3 and 0.5. Drift 0.2: 8.3, 3.0 and none. Drift 0.5: 11.5, 4.3 and none.

The smaller the share, the rarer the release: at one jump in 2,500 a quarter releases 9.0 times a stream, a tenth 2.0 and a twentieth 0.3, most likely because by the time the old band falls that far the design’s own rule has often merged it back already. A stream of 20,000 queries at one jump in 2,500 has about eight jumps, so a quarter releases about once a jump and a tenth after one jump in four.

The counts also show where the release is doing its work. At one jump in 1,000 the quarter releases twenty times a stream, about once a jump, which is why it gives back a little early cost there: some of those releases come on a jump that follows another quickly, when the old band is the band that just left and the new band has hardly arrived. A rule that reads only densities cannot tell a band that has left from one that has not yet come.

On drift the releases are rarer and do less, and on the slow drifts there are none at all, which is the straddle never becoming lopsided enough.

Time disguised as a ratio

The proposal asked whether one rule can tell a band that is leaving from half a band that is still there, or whether the price-over-a-half-life rule is slow on jumps because it is right on drift. The measurement gives a sharper answer to a different question. A threshold on a ratio of decayed densities is a threshold on time since the change that produced the ratio, at least when the change is a clean jump, and a designer choosing a share is choosing a delay whether or not the delay is written down.

That reading generalises past this file. Any rule that compares two exponentially decayed quantities, one fed and one starved, converts its threshold into a waiting time of half-life × log₂(1 + 1/threshold). The law’s own saving test is a clock of the same kind, with the rewrite’s price setting the threshold. Every cut the law moves found the law slow after a jump for the same reason: a decayed density cannot believe a move until the old evidence has decayed.

The consequence for this design is that the right share is not a matter of how little an old band matters but of when the late gap opens, and that depends on the half-life. Halve the half-life and a tenth arrives at 432 queries; double it and a quarter arrives at 1,160. A release rule worth keeping should be stated in queries since the jump, or in half-lives, and the share derived from it.

The law’s own test is a clock too

The release was meant to bypass the law’s test, the saving over a half-life against the price of the rewrite, because that test kept the old band’s split too long. Read the way the clock plate reads the share, the test is itself a delay. After a jump, the saving from merging the old band’s part back and cutting the new band in four grows as the old band’s density decays, and the law recuts once that saving times the half-life exceeds the price of rewriting the parts that change. The price is fixed, the saving grows on the decaying schedule, and so the recut comes a fixed number of queries after the jump, set by the half-life and the rewrite’s price. On these streams that number falls after the late gap has opened, which is why the two-split design’s late curve sits above the one-split background’s until it does.

So the proposal replaced one clock by another and called the new one a share. Both are deterministic after a clean jump; both scale with the half-life; and the only thing the share changed was where the clock’s zero sits relative to the gap. That is useful to know before trying a third rule. A rule that is not a clock would have to read something other than decayed densities, such as the queries since the band’s centre last moved, which the partition does not currently keep.

What the streams do not settle

Clean jumps only. The clock is exact after a jump with no other change for a thousand queries. On traffic that jumps and drifts, or jumps to a band that partly overlaps the old one, the ratio falls on no clean schedule.

One half-life. Every design reads a density decayed with a half-life of 250 queries. The late gap’s opening, at about 650 queries, is itself a fact about that half-life, and both would move together.

Released means merged. A release merges the weaker part whole and cuts the stronger in four. A design that released into a three-and-two split on a different pair was not offered.

Four seeds. The late-cost differences of ten to forty transfers a query rest on about fifty clean jumps at one jump in 2,500.

Still open: a release stated in half-lives

The share was a clock in disguise, and the clock the late gap wants reads about 650 queries after a jump, two and a half half-lives. A rule could say that directly: release the weaker split a fixed number of half-lives after it last held the majority of the two, whatever its density then. On a clean jump that is the same as some share; on a jump that follows another quickly it is not, because the half-lives are counted from the moment the old band lost the lead, not from a density that the earlier jump has already depressed.

The measurement that follows releases at 1.5, 2, 2.5 and 3 half-lives after the weaker split lost the lead, on every jump rate and drift speed, beside the quarter. The prediction is that at 2.5 half-lives the late cost after a jump is within five transfers of the one-split background’s 226, and that at one jump in 1,000 the early cost falls back to the two-split background’s 670 from the quarter’s higher figure there, because a band that has just arrived has not yet lost a lead it never held. It could fail on drift, where a straddle’s two halves trade the lead back and forth as the band crosses a cut, and a release timed from the last change of lead may fire just as the band returns. The question is whether a delay can be counted from an event the densities only imply, or whether any rule built on decayed densities is a clock whose zero it cannot see.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Block transferExternal-memoryHalf lifePartitionPredictionSelectionWorkload