The clock that cannot see the burst

This essay begins with a bug that was not a bug.

Building the arrival processes for a window that is a duration, the bursty generator was asked for sixty-four arrivals in rapid succession followed by a proportionate silence, at a mean rate of a thousand per second, on a millisecond clock. It produced a stream whose index of dispersion was 0.00 — the value of a perfectly even stream, for a process whose entire purpose was to be uneven.

The arithmetic explains it in one line. At a thousand arrivals per second on a millisecond clock the mean gap is one tick. A burst ten times faster than the mean would need a gap of a tenth of a tick, which the clock cannot express, so the gap rounds to one. The silence that restores the mean rate is then zero ticks, which rounds to one. Every gap is one tick and the stream is even.

The clock’s resolution is a ceiling on the burstiness anything can observe, and a generator running at the ceiling reports that there is none.

What the generator does now #

The response was not to make the generator cleverer. It was to make it refuse.

Both the Poisson and the bursty generators now check the mean gap against the clock before producing anything, and throw if the process being asked for cannot be represented:

a mean gap of 1.00 ticks cannot carry a burst 10× faster than itself — the clock’s resolution is coarser than the burstiness being asked for, so lower the rate or refine the clock

That is a deliberate choice and it is the one this collection makes everywhere: an instrument that cannot measure something should say so rather than return the value it would return if the thing were absent. A limit is not a prediction makes the same move about extrapolation; the refusal here is about resolution, and the failure it prevents is worse, because a flattened burst does not look like a failure at all. It looks like a well-behaved stream.

The Poisson generator refuses for a related reason worth stating separately. Exponential gaps are drawn by inversion and then floored at one tick, and when the mean is near the resolution a large fraction of the draws round to zero and are forced to one. The realised mean gap is then higher than the mean asked for, and the stream runs slower than its own label — the measured shortfall at a mean of one tick was 35%. So the generator refuses any mean gap under four ticks, and every figure in the family prints the mean gap in ticks beside the resolution so a reader can see the margin.

The mean gap is the margin, and it is a dial #

The refusal above is stated in ticks per mean gap, so the honest way to show what it is protecting is to run the same four processes at three of them.

Both of those are one number a stream. The raster is the same measurement without the summary, and it is the plate that shows what the number is a summary of.

What a stamp costs as the clock is refined #

If a coarse clock hides structure, the obvious response is to refine it, and refinement has a price that is easy to state and easy to forget.

A stamp that must stay ordered across a window of duration $D$ at resolution $r$ takes $\lceil \log_2 2D/r \rceil$ bits. Over a sixty-second window:

Refining by a factor $f$ costs $\log_2 f$ bits, so the whole range from seconds to microseconds — a factor of a million — is twenty bits. That is cheap in absolute terms and it is not nothing relative to what it is stored beside: at microsecond resolution the clock is nearly half of every entry, and the entry’s other half is the thing the structure is actually about.

That last note is worth expanding, because it is the same lesson as the burst.

The first version of this figure asserted that each step in its list of clocks cost between three and four bits, on the grounds that each step was a decade and $\log_2 10 \approx 3.32$. The assertion refused the plate: the step from milliseconds to microseconds is a thousand-fold and costs ten bits. The list was not a list of decades and the caption said it was. The claim was wrong and the drawing was right, which is the direction an assertion is for.

The count window’s stamp, for comparison #

The two window models charge for time differently, and putting the two widths side by side is the clearest way to see that the clock has become a separate parameter.

An arrival-counted window of $W$ arrivals needs $\lceil \log_2 2W \rceil$ bits per stamp, because there are exactly $W$ arrivals inside it to distinguish. At $W = 4{,}096$ that is thirteen bits, and it is forced by the window’s own parameter — there is no clock in it at all.

A time window of sixty seconds needs seventeen bits at millisecond resolution and seven at second resolution, for the same window, holding the same items. The same window has three different stamp widths depending on a parameter that is not about the window.

That is the concrete form of the separation. In the arrival-counted model the stamp width is a function of the thing being measured; in the time model it is a function of the instrument. A structure whose state is 35% clock is 35% instrument, and refining the instrument makes it more so without making the answer better in any way the structure’s own accuracy parameter can express.

The resolution nobody chose #

Here is what makes the trade above mostly theoretical: the resolution is almost never selected.

It arrives with the timestamp format the system already had. A log line carries whatever its formatter emitted. A metrics pipeline carries whatever its ingestion path preserved. A database column is a TIMESTAMP with whatever precision the schema was written with, and the schema was written by somebody who was not thinking about burst detection.

So the chain is: a format is chosen for unrelated reasons, it fixes the resolution, the resolution fixes the finest structure observable in the arrivals, and the finest structure observable fixes what any windowed measurement over those arrivals can possibly say. Four decisions, one of them made, three of them inherited.

The consequence has a shape worth recognising. A system whose timestamps are at second resolution cannot distinguish a smooth thousand-per-second stream from a thousand arrivals in the first millisecond of each second, and those two streams have very different queue depths, tail latencies and failure behaviours. The measurement will report them as identical, and it will do so with no indication that a distinction was lost.

The ratio that says whether a clock is adequate #

The check is one division and it can be done before anything is built.

Take the mean gap between arrivals, in ticks of whatever clock the system has. If it is comfortably above one, structure finer than the mean is representable down to a factor of about that ratio. If it is near one, nothing finer than the mean is representable at all.

The generators here enforce two thresholds derived from that: a mean gap of at least four ticks for an exponential draw, and a mean gap at least twice the burst’s own gap for a burst. Both are stated in the code and both throw. They are not universal constants — they are the points at which the distortion in these processes becomes larger than the effect being drawn — and the reason to name them is that a reader checking their own system needs a number to compare against rather than an instruction to be careful.

A worked case: a service taking ten thousand requests a second, logging at millisecond resolution. The mean gap is 0.1 ticks. Every measurement of that stream’s unevenness is meaningless, because ten arrivals share every tick on average and the timestamps have thrown away the ordering within a tick as well as the spacing. The fix is not statistical; it is a finer clock or a coarser question.

Where the ceiling actually binds #

Being fair about it: most systems are nowhere near this ceiling, and the ones that are, are near it for a reason.

A metrics pipeline at second resolution over a five-minute window has three hundred distinguishable instants. Anything faster than a second is invisible, and for a dashboard read by a person that is usually the right trade — nobody acts on sub-second structure in a five-minute average.

A request tracer at microsecond resolution over a one-second window has a million. Here the resolution is the point, and the twenty-seven-bit stamps are the smallest part of a span record that carries identifiers, names and attributes.

A rate limiter at millisecond resolution over a one-second window is the interesting middle. It has a thousand distinguishable instants, its stamps are eleven bits, and whether that is enough depends entirely on whether the traffic it is limiting arrives in sub-millisecond bunches — which is a property of the clients and is not something the limiter can find out, because finding out would require the resolution in question.

That last one is the honest shape of the problem. The measurement needed to decide whether the resolution is adequate is the measurement the resolution makes impossible. There is no way out of that from inside the system; it takes an instrument finer than the one being evaluated, used once, offline.

What quantisation does to a measured quantity #

The flattened burst is one instance of something general enough to be worth stating on its own, because it recurs whenever a measurement’s resolution approaches the structure being measured.

Quantising a signal at a step comparable to its variation does not add noise to the measurement. It removes variation, and the direction of the error is always the same: the measured spread is smaller than the true spread, never larger. Two arrivals separated by less than a tick become simultaneous; a gap smaller than a tick becomes a tick or nothing.

So every statistic of unevenness computed from quantised timestamps is biased downward. The index of dispersion, the coefficient of variation of the gaps, the peak-to-mean ratio of a rate: all of them under-report, and all of them under-report most exactly when the stream is burstiest, because that is when the most gaps fall below the resolution.

A measurement that is most wrong when the thing measured is most extreme is the worst shape a measurement can have, and it is the shape this one has. It is the reason the generator refuses rather than warning: a warning would be read as a caveat on a number, and the number is not slightly wrong, it is wrong in the direction that makes the situation look safe.

The same effect in the other direction #

One more case, because it is the mirror and it is easy to miss.

A clock too fine for the window causes no loss of structure and does cause a different problem: the stamps get wide, and past a point the structure is mostly clock. At microsecond resolution over a one-minute window the stamp is twenty-seven bits, and beside a thirty-two-bit key that is a structure that is 46% timestamps.

The bits that say when found the same shape in the arrival-counted model — a windowed cardinality estimator that spends more on clocks than on registers — and the mechanism there was that the accuracy dial does not touch the stamp width. Here there is a dial that touches it, and it is the one nobody turns.

So the resolution has an optimum and it is not at either end. Fine enough that the structure in the arrivals is representable; coarse enough that the stamps are not most of the state. Nothing about a system’s default timestamp format has any relationship to where that optimum is.

Why this belongs in a collection about space #

A reader might reasonably ask what a clock’s resolution is doing in a field whose subject is how many bits a structure holds. The answer is that it is one of the two factors in that count, and it is the one nobody attributes.

A time window’s state is occupancy × (key width + stamp width). The window that is not full took the first factor apart and found a distribution where the model had a constant. This essay takes the second apart and finds an inherited parameter where the model had nothing at all — the arrival-counted model has no clock, so it has nowhere to put this.

Multiply the two findings together and the range is wide. On the drifting stream at a duration chosen for 256 items, the occupancy runs from 79 to 1,736; across the clocks in the table above, the stamp runs from 7 bits to 27. A structure’s state is therefore anywhere between 79 × 39 = 3,081 bits and 1,736 × 59 = 102,424, for the same window over the same stream — a factor of thirty-three, with neither factor visible in the bound the sizing came from.

Neither is an error. Both are consequences of asking for a duration instead of a count, and both are computable in advance from things a system already knows: its rate profile, and its timestamp format.

One bit a stamp buys one doubling of visible burstiness #

The optimum is named here and left unlocated on the grounds that locating it needs a model of what a lost distinction costs. It needs less than that, because the two sides of the trade can be put in the same unit and the exchange rate is exact.

The burst ratio a clock can represent is the mean gap in ticks: a stream whose gaps average $g/r$ ticks can express a burst up to about that many times faster than its own mean before the fine gaps round to one. And the stamp costs $\lceil\log_2 2D/r\rceil$ bits.

Halve $r$ and both move by exactly one step: the representable ratio doubles, and the stamp gains one bit. So

one bit a stamp buys one doubling of the burstiness the system can see, at every resolution, over the whole range.

That is a far easier question to answer than what a lost distinction is worth. Nobody can price a distinction; everybody can say roughly how bursty their traffic gets. A service whose worst bursts are a hundred times its mean rate needs a mean gap of about two hundred ticks and gains nothing at all from anything finer.

Put the numbers in. At a hundred arrivals a second on a millisecond clock the mean gap is ten ticks, so bursts up to about tenfold are visible and anything faster is flattened. Refining to a microsecond takes the mean gap to ten thousand ticks — bursts up to ten-thousandfold — and costs ten bits. Against a real ceiling of a hundredfold, seven of those ten bits are buying resolution the traffic does not have, on every entry, for the life of the structure.

So the optimum has a location after all: the resolution at which the mean gap in ticks is a small multiple of the worst burst ratio the traffic actually reaches. Below it, structure is being flattened and every unevenness statistic is biased downward. Above it, bits are being spent on distinctions nothing in the stream can make.

The range between the two ends is also bounded, and narrowly. The generator’s own floor is a mean gap of four ticks, and no plausible traffic bursts more than a millionfold, so the whole useful span of the dial is about twenty bits — which is precisely the seconds-to-microseconds range the table above covers. There is no regime outside that table, which is a more useful thing to know about a parameter than that it has an optimum somewhere.

Two consequences follow for a system that has inherited its resolution rather than chosen it.

Over-provisioning is the common case and it is cheap to detect. A mean gap of ten thousand ticks against a traffic pattern nobody believes bursts more than a hundredfold is seven wasted bits an entry, and both quantities are measurable from the data already being stored.

And under-provisioning is invisible, which is why it is the dangerous one. A mean gap of one tick reports an even stream and gives no sign that it has done so — the failure this essay opens with. The bits that say when prices the stamps and the window that is not full prices the occupancy; the exchange rate above is what makes the third factor a decision rather than an inheritance.

What is not established #

No real traffic is measured here. The burstiness ceiling is arithmetic, and the processes exercising it are generators. That a real load has structure at a millisecond scale is asserted from general knowledge and is not measured on this page.

The stamp cost is a model. It is $\lceil \log_2 2D/r \rceil$ bits, which is what distinguishing instants within one wrap requires. A real system storing a sixty-four-bit epoch value is spending more than that and is not spending it for this reason, and the difference between what a model charges and what an implementation stores is a gap this collection’s window field has carried since it opened.

And the optimum is named rather than located. That there is a best resolution follows from the two effects pulling opposite ways. Where it sits for a given stream and window is a computation this essay does not do, and it would need a stated model of what a lost distinction costs — which is a different subject and probably not a computable one.