Hot key detection hysteresis for databases

Hot key detection hysteresis for databases needs two thresholds, not one. A key should become hot at a high threshold and return to normal only after it stays below a lower threshold.

One threshold makes a controller flap when sampled traffic sits near the boundary. Replicas warm, routes change, the estimate moves slightly, and the controller immediately reverses work it just paid for.

The fix is a small state machine: promote after sustained evidence, hold the mitigation long enough to work, and demote after sustained evidence below a separate threshold.

Hot key detection hysteresis starts with capacity

A hot key is operationally hot when keeping it on the normal path threatens a resource limit. Popularity relative to other keys is useful for ranking, but it does not define that limit.

Redis HOTKEYS ranks keys by their share of CPU time and network bytes during a tracking period. Those metrics are closer to pressure than a raw request count.

Start with the bottleneck you need to protect: shard CPU, network bandwidth, storage operations, or request latency. Convert its safe headroom into the same unit your detector reports.

Suppose one shard can sustain 12,000 operations per second. You reserve 20 percent for bursts, so the operating ceiling is 9,600 operations per second.

Other traffic already uses 5,000 operations per second. A candidate key should enter the hot state near 4,600 operations per second because 9,600 minus 5,000 equals 4,600.

Call the result H, the promote threshold. It follows capacity and headroom rather than an arbitrary rule such as "ten times the median key."

Relative share still matters. A key at 40 percent of shard CPU is worth inspecting even if current latency is fine, especially when the remaining traffic is growing.

Fanout's consistent hashing explainer shows why adding ordinary ring capacity does not split one indivisible key. The detector must trigger a key-specific mitigation.

Sampling error sets the hysteresis band

Production detectors often sample accesses because counting every request adds work to the path being protected.

The current Valkey hot-key configuration exposes a sampling percentage p and a reporting window W.

Its expected sample count for a key is q times p times W, where q is the true requests per second. The smallest nonzero reported rate is about 1 divided by p times W.

At one percent sampling and a one-second window, one sampled hit represents about 100 requests per second. A key at 4,000 requests per second produces only about 40 samples per window.

Extend W to ten seconds and the same key produces about 400 samples. The estimate reacts more slowly, but random sampling noise falls.

For independent Bernoulli sampling, the standard deviation of the rate estimate is approximately the square root of q times (1 minus p), divided by p times W.

At q = 4,000, p = 0.01, and W = 10 seconds, that standard deviation is about 199 requests per second.

A promote threshold of 4,600 and a demote threshold of 3,500 leave a 1,100-request band. Near the middle, that is more than five standard deviations wide under this simplified model.

With W = 1 second, the standard deviation rises to about 629 requests per second. The same band is less than two standard deviations wide and will cross more often by chance.

Real traffic is bursty, so this calculation is only a floor. Replay a production trace and measure crossings before choosing the band.

Require dwell before changing state

Hysteresis separates thresholds. Dwell time asks the estimate to remain on one side for multiple completed windows.

Use three states: normal, warming, and hot. A normal key enters warming after one window at or above H. It becomes hot only after K consecutive qualifying windows and a successful mitigation warm-up.

If a window falls below H during warming, return to normal and cancel work that is still safe to cancel. Do not route traffic to an incomplete replica or an empty local cache.

For W = 10 seconds and K = 2, promotion needs roughly two full windows of evidence, plus alignment with the window boundary. This is too slow for an overload that exhausts headroom in five seconds.

In that case, shorten W, raise p, or add a separate emergency threshold. An emergency path can promote immediately when shard latency or CPU crosses a hard safety limit.

The normal detector should not carry both jobs. A stable optimization controller and a fast overload circuit breaker have different tolerance for false positives.

Google's Slicer paper describes dynamic sharding that watches load hotspots while minimizing key movement.

Minimizing movement matters here. A detector that finds the right hot keys but moves them every few windows can spend more capacity on churn than it recovers.

Cooldown must cover mitigation warm-up

Cooldown is often implemented as an alert timer. That suppresses repeated pages, but it does not stop the routing controller from undoing a live mitigation.

Give the hot state a minimum hold time. Start the timer only when the new path is ready, not when the first threshold crossing occurs.

Assume a replica needs 25 seconds to load data and pass health checks. With a ten-second detector window, the minimum useful hold is at least 35 seconds: warm-up plus one clean observation window.

A 60-second hold is easier to reason about. It gives the new path time to receive traffic and lets several complete windows describe the post-mitigation load.

Warm-up time must come from measurement. Include data loading, connection establishment, cache fill, route propagation, and any health-check grace period used by the serving path.

If the mitigation is a two-second application cache rather than a replica, its warm-up may be short. Its cooldown may still need to cover invalidation traffic and backend recovery.

The Redis observability guide warns that MONITOR can have high impact and recommends it only as a secondary diagnostic.

Do not turn an expensive diagnostic into a continuous controller. Prefer sampled metrics already collected on the request path or the database's dedicated hot-key facility.

Demotion needs its own evidence

After the minimum hold, a hot key should demote only when its pre-mitigation demand estimate stays at or below L for M completed windows.

Measure demand before the mitigation if possible. Backend QPS after adding a local cache is not the original key demand. Demoting because the mitigation successfully reduced backend traffic is a control error.

Client-side request counters, router counters, or the sum across replicas preserve demand. Backend-only counters measure the load that remains after the controller acted.

Choose L below the rate that justifies the mitigation economically, not merely below H. Replica cost, cache staleness, and route complexity all affect that point.

In the example, H is 4,600 operations per second. Set L to 3,500 and require three ten-second windows below it after the 60-second hold.

The key must then show about 30 seconds of low demand before teardown. A single quiet window cannot discard a replica that took 25 seconds to prepare.

If demand rises above H during the demotion dwell, remain hot and reset the low-window counter. Values between L and H keep the current state.

The middle band is deliberately indecisive. Preserving the current state is cheaper than reacting to ambiguous evidence.

Test the controller with worked traces

Unit tests should feed completed windows, not individual requests. The detector's input is an estimate with window boundaries, missing intervals, and measurement lag.

Test a steady key below L, a step above H, a burst shorter than K windows, and traffic oscillating inside the band. Confirm that only the sustained step promotes.

Then test a hot key that drops below L for M minus one windows and rebounds. It must remain hot. Test another that stays low through M windows after the minimum hold and confirm one demotion.

Valkey drops a reporting window if a server stall stretches it past twice the configured length. Treat a missing or invalid window as unknown, not as zero demand.

Unknown evidence should usually preserve state and reset dwell counters. Otherwise a monitoring stall can demote protection during the incident that caused the stall.

Run the controller against historical traces and count promotions, aborted warm-ups, demotions, emergency trips, and total time in the hot state.

Price each transition. A false promotion spends replica or cache capacity. A false demotion can overload the shard and pay warm-up again.

Fanout's virtual-node variance guide separates ownership balance from request skew. Use that distinction when a hot key remains dominant after the ring itself is well balanced.

A practical tuning order

First, choose the protected resource and its safe operating ceiling. Subtract baseline shard load to get H.

Second, choose p and W so a key near H produces enough samples. Check both the quantization step and the estimated sampling variance.

Third, set L far enough below H to absorb sampling error and ordinary burstiness. Validate the band on recorded traffic rather than assuming independent requests.

Fourth, choose promotion dwell from the fastest safe reaction time. Add a separate hard threshold when that dwell cannot protect the shard from a rapid overload.

Fifth, measure mitigation warm-up and set a minimum hold. Require multiple low windows after the hold before demotion.

Finally, keep alert cooldown separate from control cooldown. One limits notifications. The other protects a state transition that consumes real capacity.

Hot key detection hysteresis is not a decorative debounce. It turns a noisy rank or sampled rate into a controller that can pay for replicas, caches, or routing changes without repeatedly reversing them.