The window that is not full

Every space bound this collection has stated about a sliding window is a bound per item, multiplied by the number of items. What a window costs in bits compares an exact structure at $W$ keys against an approximate one at $O(\log^2 W)$; the bits that say when charges $\lceil \log_2 2W \rceil$ per stamp. Both multiply by $W$, and both are correct.

A window that is a duration took $W$ away. What replaces it is not a different number; it is a distribution.

The ranges #

At a duration chosen so that an evenly spaced stream would hold 256 items:

Two of those need a note before the third can be read properly.

The bursty stream is flat at 256 because the window is four whole bursts long. A window that holds an integer number of bursts holds the same count at every instant, which is the same threshold effect a window that is a duration found in the disagreement sweep, seen from the other side. Shorten the window below the burst size and the range opens to 4 – 64.

The Poisson stream’s range of 1.3 is the square root doing its job. At an expected 256 items, the standard deviation is sixteen, and a range of ±30 over sixteen samples is about what that predicts. This is the well-behaved case and it is worth knowing that even here the occupancy is not the number the bound is stated in.

The drifting stream’s factor of twenty-two is the finding. Nothing about that stream is adversarial. Its rate rises and falls by a factor of eight over a period of a few thousand arrivals, which is a gentler diurnal cycle than most systems see.

Why the even stream is the only flat row #

It is worth noticing that two rows of that table are flat and only one of them is flat for a reason that generalises.

The evenly spaced stream is flat because the model assumes it. That is the definition of the control, and it holds at every window length.

The bursty stream is flat by coincidence — a coincidence between the window length and the burst period. Change either and it stops. That is the more instructive case, because it is the shape of an entire class of measurement error: a quantity measured at a period commensurate with a periodicity in the source reports no variation at all. A sampling rate that lands on a multiple of a cycle sees a constant; the constant is an artefact of the two periods, not a property of the source.

A monitoring system whose window happens to be a multiple of a load’s period is in exactly this position. It will report a beautifully stable occupancy, and a small change in either period — a deployment that shifts a cron by thirty seconds — will make it swing without anything having gone wrong.

Which number a structure has to be sized for #

A structure holding the window has to hold whatever is in the window. There is no averaging available: at the instant the drifting stream has 1,736 items inside $D$, an exact structure has 1,736 keys and 1,736 stamps, or it has dropped something and stopped being exact.

So the sizing is the maximum occupancy over the life of the deployment, and the mean occupancy — which is the number the duration was chosen to produce, and the number anybody would quote — is seven times smaller.

That is not a small discrepancy in a field whose entire subject is space. Measuring what an algorithm keeps established the collection’s convention: peak state, not total, because peak is what has to exist at once. The same convention applied to a time window says the peak occupancy is the sizing quantity, and the model the sizing formula came from does not contain it.

A structure sized from a bound in $W$, deployed against a duration, is sized for the mean. That is the sentence, and its consequence is that the structure is undersized by whatever ratio the stream’s occupancy swings by — a factor of 1.3 on a Poisson stream, twenty-two on this drifting one.

The three quantities that were one symbol #

Untangling this is easier with the parts named, because the arrival-counted model uses a single letter for three things that have come apart.

The window’s length. A duration, in seconds. Set by whoever wrote the alert.

The window’s occupancy. How many items are in it, which is the length times the rate and is therefore a random variable. This is the sizing quantity.

The stamp’s range. How many distinguishable instants the window spans, which is the length divided by the clock’s resolution. This sets the stamp width and has no rate in it.

In the arrival-counted model all three are $W$. The window is $W$ arrivals long, it holds $W$ items, and it spans $W$ distinguishable positions, so one symbol does three jobs and no confusion is possible because there is nothing to confuse.

Once they separate, a structure’s total state is occupancy × (key width + stamp width), and the occupancy and the stamp width move independently — one with the rate, the other with the clock. A sixty-second window at a thousand arrivals a second on a millisecond clock holds sixty thousand entries of seventeen clock bits each; at one arrival a second it holds sixty entries of the same seventeen. The per-entry cost is identical and the total differs by a factor of a thousand, and neither number is derivable from the other.

Every per-item bound in the previous phases is a statement about the middle quantity and is written as though it were about the first. That is the whole confusion, and writing the three down separately dissolves it.

What the approximate structures do instead #

The bounded-space structures are supposed to be the answer to exactly this, and it is worth being careful about which part of it they answer.

An exponential histogram or a block-window summary does not hold the window. It holds a bounded number of buckets whose contents summarise stretches of it, and its space is a function of the accuracy parameter and the window’s length, not its occupancy. So a structure of that kind meets the drifting stream without growing.

What it gives up is different and is worth naming precisely. Its buckets are sized in arrivals — a bucket holds a count, and the structure’s error is the oldest bucket’s contribution. When the rate drifts, the buckets covering the busy stretch hold many arrivals and the ones covering the quiet stretch hold few, so the temporal resolution of the summary varies with the rate: the structure is fine-grained about the recent busy period and coarse about the quiet one, or the reverse, depending on how its merging rule is written.

Neither is wrong, and neither is what the bound describes. The approximate structures convert an occupancy problem into a resolution problem, and the resolution is uneven in a way that the arrival-counted analysis has no term for, because in that model every bucket covers the same number of arrivals and the same stretch of time.

What sizing for the peak costs #

Suppose the sizing is done honestly: measure the stream, find the peak occupancy, size for it. What does that cost?

On the drifting stream, sizing for 1,736 items rather than 256 is a structure 6.8 times larger, and it is idle most of the time — the mean occupancy is around the intended figure, so most of the allocation is unused at any instant. That is the ordinary cost of provisioning for a peak and it is a familiar trade.

What is less familiar is that the peak is not a property of the stream alone. It is a property of the stream and the window length, and the two interact in a direction that is not obvious: lengthening the window raises the mean occupancy proportionally and raises the peak less than proportionally, because a longer window averages over more of the rate’s variation. On the plate above, quartering the window from 256 to 64 turned the bursty stream’s occupancy from a constant into a range of sixteen to one.

So a longer window is cheaper per item of peak capacity, which is the reverse of the usual intuition that a longer window costs more. It costs more in total and less in headroom, and a system with a hard memory ceiling and a choice of window lengths has a real optimisation available that the arrival-counted model cannot express.

The bound is not wrong, its subject is #

It would be easy to read this as an argument that the window bounds are broken. They are not, and being precise about what they say is more useful than a complaint.

$\lceil \log_2 2W \rceil$ bits per stamp is exactly right for a window of $W$ arrivals. A structure over a time window at the instant it holds 1,736 items is a structure over a window of 1,736 arrivals, and the bound applies to it, and it is right. What is missing is that $W$ is not a constant of the deployment, so the bound has to be evaluated at the maximum rather than at the intended value — and nothing in the way it is written suggests that there is a choice.

That is the same shape as a guarantee names its model has been making all along. The bound has a model in it; the model has a constant in it; the deployment replaces the constant with a distribution and keeps the bound.

The repair is not a new bound. It is a habit: state the occupancy the structure was sized for, next to the duration it was configured with, and measure the actual occupancy. The second number is cheap — it is the length of a list — and it is the one that says whether the first is fiction.

The query that has no denominator #

Occupancy is not only a sizing quantity. It is the denominator of most of the questions a window is asked, and when it moves the questions move with it.

A heavy-hitter query asks for keys above $\phi n$ where $n$ is the number of items in the window. On the drifting stream that threshold is 1.6 items at the quiet instant and 35 at the busy one, for the same $\phi$ and the same alert. The same configuration is asking two different questions eight seconds apart, and neither is wrong — $\phi$ was always a fraction, and the fraction was always of whatever was in the window.

An error rate is worse, because it has a denominator that can reach zero. Over a window holding seventy-nine items, one error is 1.3%; over a window holding 1,736, one error is 0.06%. A threshold set at 1% fires on a single error during the quiet period and needs eighteen during the busy one — which is exactly backwards from what anybody wants, since the busy period is when eighteen errors matter less and one error matters least.

This is the error names its denominator applied to a quantity nobody thought of as a denominator. The repair is the same as it always is: report the numerator and the denominator, not the ratio, and let the reader see that the window held seventy-nine.

Two sources of spread, and only one of them a longer window cures #

The four ranges look like four points on one scale and they are not. Two mechanisms produce them, they scale differently in the window’s length, and separating them turns the sizing question into arithmetic.

Counting noise at a fixed rate. The occupancy of a window over a stationary process has variance $D\mu$, where $\mu$ is the mean occupancy and $D$ is the arrivals’ index of dispersion — one for Poisson. So the spread is $\pm z\sqrt{D\mu}$ and the relative spread is $z\sqrt{D/\mu}$, which falls as the window lengthens. At $\mu = 256$ and $D = 1$ that is about ±12% at two standard deviations: 224 to 288 against the measured 225 to 285.

Variation in the rate itself. Here the occupancy is the instantaneous rate times the duration, so its relative spread is the rate’s relative spread and contains no $\mu$ at all. Lengthening the window multiplies both the mean and the extremes by the same factor and changes nothing — until the window is long enough to contain a whole cycle, at which point it averages the variation away and the term vanishes abruptly.

That is the whole of why the plates behave as they do. Poisson’s 1.3 is the first term and would be 1.6 at a quarter of the window, smoothly. The bursty stream’s collapse from a single value to sixteen-to-one when the window is quartered is the second term switching on as the window drops below the burst period — not a smooth degradation but a boundary crossed. And the drifting stream’s factor of twenty-two is the second term at a window far shorter than its cycle.

So the sizing question has two regimes and the boundary between them is computable before anything is deployed.

Window longer than the rate’s variation timescale. Only the counting term survives, and the peak is $\mu + z\sqrt{D\mu}$ — headroom of a few per cent on a large window, and the honest allocation is close to the mean after all.

Window shorter than it. The peak is the peak rate times the duration, and the mean rate is irrelevant to it. Sizing from the mean is then wrong by the rate’s peak-to-mean ratio, which is the twenty-two here and is a property of the load rather than of the window.

Two things follow that the single-scale reading hides.

The instruction “measure the actual occupancy” is right and incomplete: what has to be measured is the rate’s variation timescale, because that decides which of the two formulas applies, and it is a property of the arrivals that no observation of one window length reveals. A window that is a duration is where that timescale first decides whether two window models agree at all, and it decides this too.

And the earlier claim that a longer window is cheaper per item of headroom is true in the first regime and true in a stronger way at the boundary: crossing it does not reduce the headroom gradually, it removes the whole second term. A window sized just under a diurnal cycle and one sized just over it are different structures, and sized for a rate that does not hold still is what the choice costs on the other side.

Two more settings say what the spread is a function of, and neither of them is the rate.

The version that has no maximum #

There is a case this measurement cannot bound at all, and it is worth ending on because it is the honest limit.

The maximum occupancy of a time window over an unbounded stream is unbounded. Nothing about a duration constrains how many arrivals can fall inside it; a burst of ten million requests in five minutes is a legal stream, and any structure that holds the window holds ten million items. The drifting stream’s factor of twenty-two is a property of a generator with a stated swing, and a real load has no such parameter.

So a system that must not run out of memory cannot hold a time window. It has to either bound the occupancy — by dropping arrivals, by sampling, or by refusing them — or use a structure whose space is a function of the duration rather than of what arrived in it. Both of those are decisions with visible consequences, and the reason to state the alternative plainly is that the third option, hold the window and size it from the mean rate, looks like neither a decision nor a risk right up until the burst.

What is not established #

Sixteen instants is a sample. The ranges quoted are the minimum and maximum over sixteen sampled query times, spread over the last three-quarters of each stream. A longer run or a denser sample would widen them, never narrow them, so every range here is a lower bound on the range.

The processes are generators. Their swings are parameters — a factor of eight in rate, a burst of sixty-four — chosen to span a range rather than to imitate a measured load.

The four ranges come from one duration. Every occupancy quoted is for a window chosen so that an even stream holds 256 items. The ranges at other durations are shown at one other setting and not swept, so the relationship between window length and occupancy spread is asserted from two points rather than fitted.

And the approximate structures are described rather than measured here. The claim that they convert an occupancy problem into a resolution problem follows from how they are built, and this essay does not put a number on the unevenness of that resolution. It is the sharpest open question the time-window field has, and it needs a corpus with a stated rate profile and a structure instrumented per bucket.