The window that is even in the wrong currency

A window that is a duration established that a window of $W$ arrivals and a window of $D$ milliseconds are the same object on an evenly spaced stream and on nothing else, and measured how far apart their answers get. The approximate windowed structures — the ones that keep blocks and retire them — are all built on the first kind, and the claim made for them at the time was that they do not remove the problem a varying rate creates but move it.

That claim had no number attached to it. It has one now, and the number is larger than the phrasing suggested.

What is being measured #

A block-window summary keeps $b$ blocks of $W/b$ arrivals and retires the oldest when the newest fills. The retirement is triggered by a count, so its timing is a property of the stream.

The arrivals are timestamped and the timestamps are carried alongside — the structure never sees them, which is the point of the arrangement. It cannot be blamed for a duration it has no access to, and the reader who set $W$ to four thousand and wrote the alert in seconds has been relying on one anyway.

Four processes at a mean of a hundred arrivals a second on a millisecond clock: evenly spaced, Poisson, a burst-and-silence pattern, and a rate that rises and falls by a factor of eight over a slow cycle. Each block is five hundred and twelve arrivals.

On the even stream every block covers 5,110 ticks. Every one, to the tick, which is the control and the check that the instrument is not manufacturing spread.

On the Poisson stream they run from 4,733 to 5,486 — a ratio of 1.16, which is the square-root fluctuation anybody would expect from five hundred independent gaps.

On the drifting stream they run from 565 to 14,769. A factor of 26.

Why 26 is the right kind of number #

The stream’s rate multiplies between one eighth and eight times its mean over a cycle, so the fastest stretch is sixty-four times the slowest and a fixed number of arrivals takes a sixty-fourth of the time. Twenty-six is the realised figure because a block straddles part of a cycle rather than sitting entirely inside its extreme.

Which is to say the effect is not a subtlety to be teased out. It is the rate ratio, arriving in the duration because the duration is what a count of arrivals leaves free.

A rate that varies by a factor of eight over a slow cycle is a diurnal load. It is the most ordinary thing a monitoring stream does. And the effect is not confined to slow variation: any process whose gaps are not independent and identically distributed will do some version of it, which is every real arrival pattern that has ever been fitted. The even stream is the only one of the four here on which the two window models are the same object, and it is the only one that does not occur.

The structure has no clock, and that is the design #

It is worth being precise about what the structure does and does not know, because the failure here is not a bug in any implementation.

A block-window summary holds $b$ tables and a counter. On each arrival it increments the counter, adds the key to the newest table, and retires the oldest table when the counter passes a boundary. There is no timestamp anywhere in it — not per key, not per block, not per structure — and the whole reason to build it this way is that stamps are the expensive part of a windowed structure.

What a window costs in bits has the accounting: for a windowed count over a stream of any length, the stamps outweigh the answer by a wide margin, and the arrival-counted design exists to avoid paying for them. A block boundary is one integer comparison; a time boundary is a stamp per block at least, and a stamp per key if the question needs it.

So the structure’s blindness to time is not an oversight. It is what was bought. The mistake is downstream, in a monitoring rule that reads a window of four thousand events and writes over the last forty seconds, and neither the structure nor any gate on it can see that happen.

The dual #

The obvious response is that the other model has no such problem, and it does not — it has the same problem on the other axis.

A time window holds a fixed duration and whatever number of items arrived in it. On a stream whose rate moves, that count moves with the rate. The window that is not full measured it: a duration chosen so that an even stream holds two hundred and fifty-six items holds between 79 and 1,736 on a drifting one.

So the pairing is exact in shape:

$$\text{a window of } D \text{ milliseconds} \;\to\; \text{duration exact, occupancy varies}$$

$$\text{a window of } W \text{ arrivals} \;\to\; \text{occupancy exact, duration varies}$$

Neither model is uneven. Each is exactly even in its own currency and pays for it in the other, and choosing between them is choosing which axis to take the unevenness on rather than whether to have it.

The comparison has to be made at the same grain #

Getting that pairing to come out required fixing a mistake worth recording, because the wrong version is the natural one and it produces a clean and false result.

The first comparison set the time window’s duration to the mean duration of the whole four-thousand-arrival window and found the arrival window varying by 26 times against an occupancy varying by 1.2 — which reads as one model is twenty times worse than the other and is not a comparison of models at all.

A window of forty-one seconds on a stream whose rate cycles over about the same period averages the rate out. It holds a nearly constant count because it always contains one whole cycle, wherever in the cycle it starts. The block it is made of — five seconds — does not, and the block is what the structure retires.

So the two must be compared at the grain the structure operates at. Matched at the block, the spreads are 26.1 and 17.7, within a factor of one and a half of each other, and the conservation is a conservation.

The general lesson is one this collection keeps meeting. The floor moves when the question does is the same observation about lower bounds: a quantity measured at one scale is not a quantity measured at another, and a comparison across scales will produce a difference that belongs to the scales.

The measurement refuses the neat version #

There is a version of this result that would be tidier and it is not what the numbers say.

The tidy version is that the two spreads are equal — that the unevenness is conserved exactly, so many parts of one buying so many parts of the other. The measured pairs are 1.16 against 1.21, 1.00 against 1.14, and 26.1 against 17.7. Close, in the sense that no other pair of quantities on this site would be called close, and not equal.

The gap has a cause and the cause is the same one that produced the wrong comparison above at a larger scale. A block covers a stretch of time and the time window covers a stretch of arrivals, and neither stretch is short compared with the rate’s variation — so both average a little, and they average different amounts because they are anchored differently.

Shrinking both would drive the pair together and would also drive both towards the sampling noise of a handful of arrivals. There is no scale at which the two are exactly the same measurement, which is the honest reading: they are dual quantities rather than one quantity in two units, and the check that ships requires them within a factor of four of each other rather than asserting an identity that is not there.

What follows for a structure that keeps blocks #

Three things, and the third is the one a design review would want.

The slack is not what it says it is. A block window’s answer is about between $W$ and $W + W/b$ arrivals, and that bound is exact and checked. Converted into the clock it becomes the duration of the oldest surviving block, which on the drifting stream is up to 2.8 times the typical one and is bounded by nothing the structure knows.

More blocks buys arrival resolution and not time resolution. Doubling $b$ halves the slack in arrivals and halves the duration of a block, so the ratio between the longest and shortest block is unchanged. The dial that tightens the guarantee does not touch the spread — which is worth setting against the block that is not a block, where the same dial is the one that decides the whole trade in the arrival-counted currency. A parameter that is the answer to one question and irrelevant to another is the usual outcome once a second axis is admitted.

And the answer is about a different stretch of time on every query. Two queries a minute apart on the drifting stream are answered over stretches that may differ by an order of magnitude, both correctly, both to specification.

What a timestamp would cost #

There is a structure that has neither problem: keep the timestamps and expire by time. It is exact in duration and exact about which arrivals it holds, and it is not used, for reasons already measured here.

A stamp wide enough to order events across a window of $D$ at a resolution $r$ needs $\lceil \log_2 2D/r \rceil$ bits, and that expression contains no arrival rate. So a quiet stream watched at fine resolution pays for its clock out of all proportion to what it is holding — which is the clock that cannot see the burst’s subject and the reason the arrival-counted structures exist at all.

So the trade is real in both directions and this essay is not an argument for one model. It is an argument for knowing which currency a given structure is exact in, because the guarantee is always stated in that one.

Sizing a structure against the wrong one #

The two exactness properties are not merely different; they are the two things a capacity decision might want, and each model gives one of them.

A structure sized for memory wants the occupancy exact, because the occupancy is what it allocates for. A structure whose answers feed an alert wants the duration exact, because the alert’s threshold is in events per second and the denominator is the duration.

An arrival-counted window gives the first and a time window gives the second, and a deployment nearly always wants both. What it gets is one of them plus a distribution, and the distribution is wide enough to matter: a factor of twenty-six on the duration or a factor of twenty on the occupancy, on a load pattern nobody would describe as pathological.

Distributions, not averages is the standing note about quoting a mean where a range is what the decision needs, and this is the case where both quantities want the treatment at once. The essay that prices it is sized for a rate that does not hold still; what matters here is that no choice of window model avoids the question.

What a reader of a dashboard sees #

The gap between the two currencies has a specific place where it does damage, and it is not inside any structure.

A dashboard shows a rate: events per second, over some window. The numerator comes from the structure and the denominator is the window’s duration, which for an arrival-counted window is not a constant and is not reported. So the rate displayed is the count divided by a nominal duration, and on the drifting stream that nominal duration is wrong by up to a factor of twenty-six.

The direction of the error is the one that hides trouble. When the rate is high the window covers a short stretch, so the true denominator is small and the displayed rate — computed with the nominal denominator — is too low. When the rate is low the window covers a long stretch and the displayed rate is too high. The instrument compresses the variation it is supposed to be reporting, and it compresses it towards the mean of the very quantity being watched.

An arrival-counted structure is therefore a poor choice for anything whose output is a rate, and a fine one for anything whose output is a ranking. Which keys are heavy over the last four thousand events is a question the structure answers exactly as specified; how fast they arrived is not.

The displayed rate is flat by construction, and the repair is eight stamps #

The dashboard argument above understates its own case, and the structure’s guarantee is what sharpens it.

A rate on a dashboard is a count divided by a duration. The count comes from the structure and is between $W$ and $W + W/b$ — that is the guarantee, it is exact, and it is checked. The denominator is the nominal duration, which is a constant somebody wrote down. So the displayed rate is a bounded quantity divided by a constant, and it cannot vary by more than $1/b$ whatever the stream does.

At eight blocks that is twelve and a half per cent. On the drifting stream the true rate varies by a factor of sixty-four. The instrument is not compressing the variation towards the mean; it is reporting a flat line, and the flatness is not a coincidence or an artefact of a particular implementation — it is the arrival-counted guarantee, working exactly as specified, in the wrong currency. The better the structure holds its promise, the flatter the wrong answer.

That reading also says where the repair is, and it is much cheaper than the earlier accounting suggests. What a window costs in bits prices a timestamp per key, which is what makes stamped windows expensive and is the reason these structures exist. But the denominator does not need a stamp per key. It needs the age of the oldest surviving block, which is one stamp per block.

Put numbers on it. A stamp spanning a window of forty-one seconds at millisecond resolution is seventeen bits, by the width formula the bits that say when derives, and eight blocks is a hundred and thirty-six bits for the whole structure — against tables holding thousands of keys. It is not a rounding error in the budget; it is below the rounding error.

What those eight stamps buy is precisely the missing denominator. Retirement stays arrival-counted, so nothing about the guarantee, the slack bound or the memory changes; the structure simply becomes able to say what stretch of time this answer is about. A rate computed against that number is a real rate, and the twenty-six-fold spread that was invisible becomes a reported quantity a reader can see moving.

It is worth being clear that this does not make it a time window. The duration still varies by twenty-six times and the answer is still about a different stretch on every query — the conservation above is not repealed by measuring one of its two halves. What changes is that the varying quantity stops being silently assumed constant, which is the whole of the damage this essay is about.

So the design rule is narrower than “arrival-counted structures are bad for rates”. It is: stamp the boundaries, not the keys. The expensive stamps are the ones that scale with the data; the one that fixes the denominator scales with a parameter somebody chose and is a handful of integers.

The one number to carry #

The unevenness is conserved, at the grain the structure works at. On the Poisson stream the two spreads are 1.16 and 1.21; on the bursty one 1.00 and 1.14; on the drifting one 26.1 and 17.7. Never more than a factor of one and a half apart, on any stream measured, and asserted as a two-sided claim, so that a result showing one model simply better would fail rather than be written up as a recommendation.

The bursty row is the exception and it is not a small one — the arrival window reports a perfectly even stream while the arrivals have an index of dispersion of 0.57. That is not conservation with a residual; it is the instrument reporting nothing at all, and it has a mechanism. The boundary that hides the burst takes it up.