A share that is a clock
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 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 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%. 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 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 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 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.
- A buffer that does not shift its tail block transfer · external-memory
- A check as slow as what it checks half life · prediction
- A checker told only what it showed prediction · workload
- A choice the fences cannot make prediction · workload
- A heap that keeps its levels in a line block transfer · external-memory
- A hold that never lets go half life · prediction
The objects this essay names
Each one links to every other essay that touches it.
Block transferExternal-memoryHalf lifePartitionPredictionSelectionWorkload