The counter with no window in it

The sliding window is not the only way to stop counting the distant past, and on the evidence of what is deployed it is not the usual one.

A monitoring system almost always runs an exponentially decayed counter. Every count fades by half every $H$ seconds; there is no $W$, no ring buffer, no timestamp per item, and no moment at which anything is expired. The state per key is a number and the time it was last touched, and that is the whole structure.

It is a different question with a similar-sounding answer, and this essay is about keeping the two apart.

The one place they agree #

Start with the correspondence, because it is exact and it is the reason the two get confused.

Take a steady stream at $\lambda$ arrivals per tick. Each arrival adds one to the counter, and everything already in the counter fades by $2^{-1/H}$ per tick. In the limit the counter settles where the inflow balances the fade:

$$v_\infty = \frac{\lambda}{1 - 2^{-1/H}}$$

For any half-life worth having — many ticks — the denominator is very close to $\ln 2 / H$, so $v_\infty \approx \lambda H / \ln 2 = 1.44\,\lambda H$. That is the count a window of $1.44H$ would hold on the same steady stream.

So a decayed counter with half-life $H$ and a window of $1.44H$ give the same number, in the mean, on a steady stream.

The site’s gate checks that the exact expression and the $1.44H$ approximation agree to within a per cent at every half-life the figures use, which is the sort of thing worth asserting rather than trusting, because the approximation fails when $H$ approaches a single tick and that is a regime a badly configured system can reach.

And every place they do not #

That table invites a substitution — a half-life of $D/1.44$ is a window of $D$ — and the substitution is wrong in three separate ways, each worth its own sentence.

It holds in the mean and not on a run. The steady-state value is a limit of an expectation. On any particular stream the decayed counter fluctuates around it, and on a bursty stream it fluctuates a long way: the opening plate shows it climbing through a burst and falling through a silence while the windowed count jumps and drops. The two curves cross repeatedly and are rarely equal.

It holds on a steady stream and not otherwise. The derivation assumes a constant $\lambda$. When the rate moves — which is a window that is a duration’s whole subject — the decayed counter is tracking a moving quantity with a lag of about $H$, and the windowed count is tracking it with a hard cutoff at $D$. Those are different filters and they respond differently to the same change.

And it is a correspondence of values, not of questions. This is the important one. A window’s count is how many arrived in the last $D$, and it is a count: an integer, exactly determined by the window’s contents, and it is zero when nothing arrived. A decayed counter’s value is a weighted total in which every arrival ever seen still contributes something, and it is never zero after the first arrival. There is no $D$ for which the second is an estimator of the first, because the second is not estimating anything — it is computing a different function, exactly.

The weighting, drawn out #

It helps to write down what a decayed counter is computing, because the phrase a weighted total is doing a lot of work.

At time $t$ the counter’s value is

$$v(t) = \sum_{i} 2^{-(t - t_i)/H}$$

summed over every arrival $i$ that ever happened, at its own time $t_i$. Every term is positive. An arrival from ten half-lives ago contributes $2^{-10} \approx 0.001$, an arrival from thirty contributes $10^{-9}$, and none of them contributes zero.

A window’s count is the same sum with a different weight: one inside the window, zero outside. Both are weighted sums over the whole history; they differ in the shape of the weight, and the shapes are a box and an exponential.

That framing makes several things obvious at once. The box has a hard edge, which is why a windowed count steps; the exponential has none, which is why a decayed value is smooth. The box has bounded support, so it can be computed from bounded state; the exponential does not, which is why the decayed counter must be computed recursively rather than by remembering its terms — and why its state is one number rather than an occupancy.

And it makes the correspondence legible: $1.44H$ is simply the width of the box with the same area as the exponential. Two filters with the same total weight, and every other property different.

What the decayed family is actually for #

Given all that, the fact that decay is what gets deployed needs explaining, and the explanation is not that anybody confused it with a window.

It has no expiry. A sliding window has to remove things, and removing means touching state that nothing has asked about. A decayed counter’s value at any instant is a function of its stored value and the elapsed time, so it can be computed on the way past — which is the fading nobody computes’s subject and is worth an order of magnitude.

Its state is constant and small. A number and a timestamp per key, whatever the arrival rate. An exact time window’s state is the occupancy, which the window that is not full measured swinging by a factor of twenty-two on an ordinary stream. A decayed counter meets that stream without growing.

And its answer is smooth, which is what a threshold wants. A windowed count is a step function: an arrival leaving the window changes the answer discontinuously, so an alert on a windowed count near its threshold flaps. A decayed value moves continuously, so the same alert has hysteresis for free.

Those are three real advantages and none of them is accuracy. The decayed counter is not a cheaper approximation to a window. It is a different summary whose properties happen to suit the job a window is usually asked to do.

What it costs in bits #

The state accounting is short enough to give in full, and it is where the decayed family looks best.

Per key: a value and a timestamp. The value is a float — thirty-two bits is generous, since the quantity is an approximation of nothing and its precision requirement comes from the ratio between the largest and smallest counts anybody will compare. The timestamp needs enough range to distinguish instants within a few half-lives, because beyond that the fade has taken the contribution to nothing anyway.

So a table of $k$ decayed counters is $k \times (\text{key} + \text{value} + \text{stamp})$, and it does not move with the arrival rate, the window length, the burstiness or the occupancy. Every one of those moved something in the two previous essays.

Compare against the exact time window it corresponds to. At a hundred arrivals a second and a 5.77-second equivalent window, the exact window holds about 577 entries of a key and a stamp each; the decayed table holds $k$, and $k$ is whatever the operator chose — thirty-two in the figures here. Eighteen times smaller, on a steady stream, and unboundedly smaller on a stream that spikes, because the window’s state follows the spike and the table’s does not.

That is the trade in one line: the window can answer exactly and its size is the stream’s business; the decayed table answers a different question and its size is the operator’s.

Eighteen times is the wrong ratio #

The state comparison above puts 577 window entries against 32 table entries and calls it eighteen times smaller. The two numbers count different things, and correcting for that changes both the figure and what it depends on.

The window’s 577 are items: one entry per arrival still inside the window, whatever key it belongs to. The table’s 32 are keys: one entry each, however many times each arrived. So the window is holding every key that arrived in the last 5.77 seconds and the table is holding thirty-two of them — and on the stream these figures use, whose key space is sixty-four, the table is evicting at nearly every arrival.

A structure that has dropped half the key space is not answering the same question more cheaply. It is answering a smaller question.

Hold the coverage fixed and the arithmetic changes. A decayed table covering all sixty-four keys needs $k = 64$, and 577 against 64 is nine times, not eighteen. The other nine were bought by shrinking the table, and could have been bought the same way in either family.

Written generally, the saving is

$$\frac{\text{arrivals in the window}}{\text{distinct keys in the window}},$$

which is the mean number of arrivals per key over the equivalent window — nine here, and a property of the workload rather than of either structure.

That reads the advantage the opposite way round from the usual telling. A decayed table is cheapest against a stream where each key arrives many times inside a window, because each of those arrivals costs the window an entry and costs the table nothing. And on a stream of mostly-unique keys — where the mean is near one — there is no state saving at all: the window holds one entry per key and so does the table, and the table additionally has to evict.

Which is worth saying plainly, because a stream of mostly-unique keys is precisely the case where a windowed structure’s state looks alarming and somebody reaches for decay to fix it. It does not fix it. The occupancy swing the window that is not full measures is still real, and it is a swing in the number of keys on that kind of stream — which the decayed table meets by evicting rather than by growing, so the state stays flat and the answer quietly stops covering the stream.

The flat state is a cap, not a compression. The three advantages this page lists — no expiry, constant state, a smooth answer — survive; the second is a decision to hold $k$ keys rather than a discovery that $k$ suffice, and the ratio to a window is whatever a window that is a duration’s occupancy divided by its distinct keys happens to be.

The half-life is not an accuracy parameter #

One more distinction, because it is the one that decides how a decayed counter is configured.

Every other structure in this collection has an accuracy dial: more registers, more counters, a smaller $\varepsilon$, more bits. Turn it and the answer gets closer to the truth. The decayed counter has no such dial, and $H$ is not one.

$H$ decides what question is asked. A half-life of a second and a half-life of an hour are both exact — the value each computes is the exactly correct weighted sum for its own weighting — and they answer different questions about the same stream. There is no setting of $H$ at which the counter is more nearly right, because it is never wrong.

That has a consequence for how such a system fails. A structure with an accuracy dial set too coarse produces answers that are visibly noisy, and somebody turns the dial. A decayed counter with $H$ set wrong produces answers that are perfectly smooth, perfectly stable and about the wrong timescale, and nothing about them looks like a misconfiguration. The failure mode of a parameter that is not an accuracy parameter is that it never looks like an error.

The family, and the ones this essay is not about #

Exponentially decayed names a family rather than a structure, and it is worth marking the boundaries so the claims above are read at the right scope.

The counter here decays by a fixed factor per unit of time. That is the version monitoring systems run, and it is what everything above measures.

A forward-decay scheme decays relative to a landmark rather than relative to now — weights are computed against a fixed origin and the origin is advanced periodically. It computes the same thing without the drift in floating-point that the fixed version accumulates, and it pays for it with a rescaling event.

And an exponentially decayed sample keeps items rather than counts, giving a sample of the stream biased toward the recent, which supports quantiles and not merely totals. It is a different object with the same adjective.

All three share the property this essay is about — the weight is exponential in age, so nothing is ever fully forgotten — and they differ in what they hold and in when they do work. What is measured here is the first, and the arithmetic of the correspondence applies to all three because it is a property of the weight function rather than of the implementation.

What the correspondence is good for anyway #

None of this makes the $1.44H$ relation useless, and it is worth saying what it is good for, since it is the only bridge between the two families.

It is a sizing relation. If a system currently runs a five-minute window and wants to move to decay for the operational reasons above, $H = D/1.44 \approx 3.5$ minutes gives a counter whose steady-state value matches the window’s count, so the existing thresholds keep roughly their existing meanings. That is a genuinely useful migration and it is the reason to know the constant.

What it is not is a licence to describe the result as a five-minute window. The thresholds carry over; the semantics do not, and a report generated from the new counter and compared against a report from the old window will differ by whatever the stream was doing, in the ways above.

Where the smoothness is a liability #

The smoothness is listed above as an advantage and it is worth turning over, because it costs something specific.

A windowed count forgets completely. Five minutes after a spike, a five-minute window contains no trace of it, and a query answered then is a query about a period the spike is not in. That is often exactly what is wanted: is it happening now has a clean answer.

A decayed counter never forgets completely. Five minutes after a spike at a three-minute half-life, about a third of the spike is still in the number, and a threshold crossed during the spike may still be crossed. The alert that fired during the incident keeps firing into the recovery, and the operator watching it cannot tell from the number whether the thing is still happening.

Which behaviour is wanted depends on the question, and the two are not interchangeable:

• “Is the error rate above 1% right now?” wants the box. The exponential answers a question about the recent past weighted by recency, and it will say yes for a while after the answer is no.
• “Has this key been consistently hot?” wants the exponential. The box answers only about the last $D$, and a key that has been hot for an hour looks exactly like a key that became hot $D$ ago.

A dashboard showing one labelled as the other is the ordinary case, and the reason it survives is that on a steady stream — which is what most systems look like most of the time — the two agree. They diverge exactly during an incident, which is when the number is being read.

The parameter a reader should be told #

If a decayed counter’s half-life decides what question is asked, then the half-life is not an implementation detail and belongs next to the number wherever it is shown.

That is a small editorial rule with a real consequence. A graph labelled requests per second computed from a decayed counter is labelled wrongly — it is a decayed weighted total divided by a normalising constant, and its relationship to any rate depends on the half-life and on how steady the traffic was. A graph labelled requests per second, three-minute half-life is honest and is no longer than the wrong one.

The same rule has been applied throughout this collection to every structure with a model parameter in it: a cache miss count without a line size is not a measurement, an ε without a denominator is not an error, and a decayed value without a half-life is not a rate. The parameter is part of the quantity, not part of how it was computed.

What is not established #

No bound is proved here. The steady-state identity is exact and is derived rather than fitted. Everything else on this page is a measurement of specific streams: how far the two curves separate on a bursty stream, how much lag appears on a drifting one. Neither is a bound on the difference and neither could be, since the difference is unbounded on a stream that is sufficiently uneven.

One key, followed. The trace figures follow a single key through the stream. A table of decayed counters has a further problem — evicting the smallest requires comparing counters at a common instant — and that is measured in the next essay rather than this one.

And the arithmetic assumes exact reals. The fade is a floating-point multiply, and a value faded across many half-lives becomes denormal and then zero. That is a second kind of forgetting, it is not the decay, and it is the other half of what the next essay measures.