A window that is a duration

Every window in this collection so far has been counted in arrivals. The summary that has to forget asked for the count over the last thousand arrivals; what a window costs in bits priced a window of $W$ items; the bits that say when charged $\lceil \log_2 2W \rceil$ per timestamp. $W$ is a number of things.

That is the model the theory is written in, and it is written that way for a good reason: it makes the window’s occupancy a constant, which makes the space bounds clean. It is not the model anything is deployed in.

Why the substitution is usually invisible #

Before the disagreements, it is worth being fair to the substitution, because it is made constantly and is usually harmless.

A system that wants the last five minutes and implements the last four thousand and ninety-six requests is making an assumption with a name: that the arrival rate is roughly constant over the window. Under that assumption the two are interchangeable up to the square-root noise of a Poisson process, and the arrival-counted version is cheaper in every respect — no clock, a fixed-size ring buffer, no expiry decision that depends on comparing a stamp against a moving cutoff, and a stamp width that comes from a parameter rather than from an accident of the timestamp format.

Those are real advantages and they are why the substitution is the default. What makes it worth measuring is that the assumption is not stated anywhere, and that the case where it fails is not exotic. It is not a pathological adversarial stream; it is Tuesday afternoon.

The control, and the fact that it is only a control #

The flat line at zero is an evenly spaced stream, and it is exactly zero at every window length on the plate. That is not an approximation or a small number: with a fixed gap between arrivals, the last $W$ arrivals and the last $W \times \text{gap}$ of time are the same set of items, always, and the two models are one object.

Every other row is a stream in which they are not.

The three others are stated processes rather than recordings, and each is a different way for the past to stop being a guide to the present:

Poisson. Memoryless gaps at a constant mean rate — the textbook stream, and the mildest departure. Its index of dispersion is one by definition, which is what makes it a check on this site’s own generator rather than only a description of it; the measured value is 1.03.

Bursty. Silence, then sixty-four arrivals in rapid succession, then silence. Index of dispersion 8.8. This is what a request stream looks like when it is driven by anything periodic.

Drifting. A rate that rises and falls slowly, by a factor of eight either way. Index of dispersion 274. This is a diurnal load, and it is what almost every real system’s traffic does.

All four carry the same thirty thousand arrivals at the same mean rate over the same three hundred seconds, so nothing on the plate is a difference in volume.

Where the disagreement is, and where it is not #

The sweep has a shape worth reading carefully, because the naive expectation — burstier streams disagree more — is right about the ordering and wrong about the structure.

The bursty stream disagrees by 52% at $W = 16$, by 39% at $W = 32$, and by exactly nothing from $W = 64$ upward.

Sixty-four is the burst size. A window that holds at least a whole burst always holds whole bursts, and a window of whole bursts contains the same items whether it was cut by count or by clock. The threshold is sharp because the process is: below the burst size the two windows land in different parts of a burst, and above it they cannot.

That is the general rule the plate is really about. The two window models disagree when the window is short compared with the timescale on which the rate varies, and agree when it is long compared with it. The Poisson row falls off slowly — 16% at $W = 16$ to 2% at $W = 4096$ — because there is no timescale in a Poisson process, only the square-root averaging of a longer window. The drifting row stays near 57% across nearly the whole sweep and only starts to fall at $W = 4096$, because its rate varies on a timescale of thousands of arrivals.

A system whose window is minutes and whose load varies by the hour is in the flat part of the drifting curve. That is the ordinary case.

If that reading is right, the curves should not move when the rate moves, because none of the reasoning above mentioned one. Ten times the arrival rate is a different stream by every measure a capacity planner uses — the same thirty thousand arrivals in a tenth of the time, ten times the throughput, a tenth of the mean gap in seconds — and the burst is still sixty-four arrivals long, so the prediction is that the plate is unchanged.

That is worth stating as a rule, because it is the one that makes the finding portable. The two window models disagree by an amount that depends on the shape of the arrivals and not on how fast they come. A system that doubles its traffic does not move along this curve; a system whose traffic becomes burstier does, and those are different things to monitor.

What the arrival-counted window turns out to be about #

The comparison has a mirror image, and the mirror image is the one that ships.

A structure keeping the last $W$ arrivals is answering a question about a stretch of time, and nobody chose which stretch. On these streams a window of $W = 256$ arrivals covers:

The drifting row is a factor of twenty-seven. An alert configured as the error rate over the last 256 requests is an alert whose window shrinks exactly when the traffic rises — which is the moment it was written for, and the moment its sample gets smallest.

The obvious repair is to make the window longer, on the reasoning that a longer window averages over more of the variation. It is worth measuring, because the reasoning is right about the mechanism and wrong about the size of the effect: four times the window is four times the averaging on a Poisson stream, where the variation is independent arrival to arrival, and no averaging at all on a drifting one, where a window four times as long simply sits inside four times as much of the same drift.

So use a longer window is not a fix for the drifting case, and it is the case almost every deployment is in. What lengthening changes is the state, which rises with $W$ exactly, and what it does not change is the thing the alert was configured to hold fixed.

The stamp a count window pays, and the one a time window pays #

Put the two stamp widths side by side and the models separate cleanly.

An arrival-counted window of $W = 4{,}096$ needs $\lceil \log_2 8192 \rceil = 13$ bits per stamp. It has to distinguish the arrivals inside the window and there are exactly 4,096 of them, so thirteen bits is not a choice — it is what the model’s own parameter forces.

A time window of sixty seconds on a millisecond clock needs $\lceil \log_2 120{,}000 \rceil = 17$ bits per stamp, and it needs seventeen whether the window holds six items or six million. The occupancy and the stamp width have come apart, and they were the same parameter one model ago.

That has two consequences worth separating.

A busy time window is cheaper per item than the count window it resembles. At a thousand arrivals a second, a sixty-second window holds sixty thousand items at seventeen bits of clock each; an arrival-counted window of sixty thousand would need $\lceil \log_2 120{,}000 \rceil = 17$ too, so they are level. Push the rate up and the time window’s stamp stays put while the count window’s rises — the count window is charging for a longer window it did not ask for.

And a quiet one is absurdly expensive per item. At one arrival a second the same structure holds sixty items, still at seventeen bits each, and the clock is 35% of every entry. An arrival-counted window of sixty items would pay seven bits. The extra ten are the price of insisting on a duration when almost nothing is arriving.

Neither of those is a defect. They are what it costs to answer the question that was asked rather than the one the model finds convenient, and the point of stating them is that the arrival-counted model cannot express either, because in it the two quantities are one symbol.

The clock is part of the model now #

An arrival-counted window has one parameter. A time window has three, and the two extra ones are not free.

The duration $D$. The thing the operator wanted.

The clock’s resolution $r$. A stamp must order the arrivals inside the window, which takes $\lceil \log_2 2D/r \rceil$ bits — and the arrival rate is not in that expression. In the arrival-counted model $W$ sets both the occupancy and the stamp width, so the two cannot be separated; here they are independent, and a quiet stream watched at fine resolution pays for stamps out of all proportion to what it holds.

And the arrival process. Which is not a parameter anybody sets, and which the two previous sections have shown decides the answer.

The resolution is the one that catches people out, because it is almost never chosen. It arrives with whatever timestamp the system already had, and it costs what it costs: over a sixty-second window, a second-resolution clock takes seven bits per stamp and a microsecond clock takes twenty-seven. Beside a thirty-two-bit key, that is the difference between the clock being 18% of an entry and 46% of it.

The dial, named #

There is a single quantity that predicts everything on the sweep, and it is neither the process nor the window length but the ratio between them.

Call it the variation timescale: the length of time over which the arrival rate changes appreciably. For the bursty stream it is the burst period — 640 milliseconds. For the drifting stream it is the drift period, thousands of arrivals. For a Poisson process it is undefined, which is why that row decays smoothly instead of having a knee.

The rule the plate supports is that the two window models agree when $D$ is comfortably longer than the variation timescale and disagree when it is shorter. That is a statement about a ratio, so it can be checked against a system without simulating anything: take the window the system uses, take the timescale on which its traffic varies, and divide.

Most monitoring windows are shorter than most traffic’s variation timescale. A five-minute window against a load that varies over an hour is a ratio of one twelfth, which on this plate is the flat, high part of the drifting curve.

The dial, checked against the plate #

That rule is asserted above and the sweep already contains its proof, which is worth extracting because it turns a description into a number.

Take the ratio the section names — the window’s duration divided by the variation timescale — and evaluate it at the two knees the plate has.

The bursty row goes to zero at $W = 64$. At a hundred arrivals a second, sixty-four arrivals is 640 milliseconds, and the burst period is 640 milliseconds. The knee is at a ratio of exactly one.

The drifting row starts falling at $W = 4{,}096$, which at the same rate is 41 seconds. The drift timescale was described as thousands of arrivals rather than measured, and this is where it gets measured: the knee locates it at about four thousand arrivals, so that ratio is one as well.

Two processes whose timescales differ by a factor of sixty-four, and both knees land at the same place on a ratio neither of them is drawn against. That is the collapse the rule claims, and it is the difference between a rule of thumb and a quantity anybody can compute for their own system.

The shapes of the two knees then say something the ratio alone does not, and it is the more useful half.

The bursty knee is a step: 39% at $W = 32$ and nothing at all at $W = 64$. The drifting knee is a slow bend that has barely begun by the end of the sweep. Both are at a ratio of one, so what separates them is not scale — it is that a burst process has one timescale and a drift has a spread of them. A stream whose rate varies at a single period agrees exactly once the window covers that period; a stream whose rate varies at many periods keeps disagreeing at the longer ones however wide the window gets.

So the falloff reports the shape of the variation and not merely its size, which makes the sweep a diagnostic rather than a calibration. A measured stream whose disagreement drops to zero at some window length has a period in it, and the length is the period. One that decays slowly and never reaches zero has no period, and there is no window at which the substitution becomes exact.

Both readings point at the same practical conclusion and it is narrower than the section above it. The substitution is safe at ratios comfortably above one, and only for streams whose variation has a scale, because a stream without one — a Poisson process is the extreme case, decaying from 16% to 2% across a 256-fold increase in the window — never quite stops disagreeing. Sixteen per cent to two is real improvement and it is not convergence.

And the ratio is computable from things a system already records. The window is a configured number. The variation timescale is the period of whatever drives the traffic — an hourly batch, a diurnal load, a poll interval — and it is usually known to the person who configured the window, who has simply never been asked to divide one by the other. A five-minute window against an hourly load is a ratio of one twelfth, which is the flat part of both curves, and the window that is not full is what that costs a structure sized on the assumption it is not.

Two models, and which one a bound is about #

The point of all this is not that one window is better. It is that the two are different questions, and that every bound in this collection’s window field is a bound about the first one.

The floor under a window proves a lower bound in terms of $W$. What a window costs in bits compares an exact structure against an approximate one as a function of $W$. Both are correct and both are statements about a model in which the number of items in the window is a constant known in advance — and in a time window it is neither.

That does not invalidate them. It locates them. A bound stated in $W$ applies to a time window at the instant the time window happens to hold $W$ items, and a structure sized from that bound has to be sized for the largest occupancy the stream will produce, not the mean. On the drifting stream at $D$ chosen for 256 items, that largest is 1,736.

A structure sized for the mean is undersized by a factor of seven on an ordinary stream, and the model that produced the sizing has no vocabulary for saying so. What that costs, and what a structure can do about it, is the window that is not full’s subject.

The window that can be empty #

There is one thing a time window does that an arrival-counted window cannot do at all, and it is worth naming because it breaks an assumption rather than bending one.

A time window can be empty. If nothing arrives for longer than $D$, the correct answer to what is in the window is nothing, and every query against it has to have a defined behaviour for that case. An arrival-counted window is never empty after the first $W$ arrivals — that is what counting arrivals means — so no structure written against that model has ever had to decide what an empty answer looks like.

The queries that break are the ones with a denominator. An error rate over the last five minutes is errors divided by requests, and when the window is empty it is zero over zero. A ninety-ninth percentile over an empty window has no value to return. A heavy-hitter query above a threshold $\phi n$ has $n = 0$, so everything is above the threshold and nothing is in the structure.

Each of those has a sensible answer and none of them has a default. What the model provides is the observation that the case exists, which is more than the arrival-counted model provides, and the reason this collection’s quantile structures throw on an empty summary rather than returning a number is exactly this: a query with no data is a different event from a query whose answer is small, and a structure that returns zero for both has thrown the distinction away.

The frequency of the case is a property of the stream and of $D$ together. On the drifting stream at $D$ chosen for 256 items, the emptiest instant sampled held seventy-nine — not empty, but a third of the intended occupancy, and the same arithmetic applied to a shorter window or a quieter stream reaches zero.

What is not established #

The processes are stated, not observed. Even, Poisson, bursty and drifting are four generators with parameters chosen to span a range. They are not a sample of real traffic, and the numbers attached to them are properties of those parameters.

The disagreement measure is one of several. It is the share of the counts on which the two windows differ, sampled at sixteen instants. A measure weighted by the keys anybody actually queries would give different numbers, and the shape of the curves is the claim rather than their heights.

Two rates, and both of them comfortable. The sweep is drawn at a hundred arrivals a second on a millisecond clock and again at a thousand on a microsecond one — mean gaps of ten and a thousand ticks — and the two agree to the digit, which is the evidence for the rate-independence claimed above. What neither can show is a stream whose mean gap approaches the clock’s resolution, because the site’s own generators refuse to produce one: at that rate the one-tick floor flattens the process being asked for, and the clock that cannot see the burst is the essay about what that costs.

And the clock is exact here. Every timestamp in these figures is an integer number of ticks and every arrival is ordered. A real clock skews between machines, jumps when it is corrected, and has a resolution its documentation overstates — and a window whose expiry decision depends on comparing stamps from two machines is a structure with a failure mode nothing on this page can see.