Handling Clock Skew in Distributed Limiters

Any limiter whose state includes a timestamp inherits the clock problem: if two nodes disagree about the current time, they disagree about how much capacity a client has. The fix is almost always the same one line — read the clock where the state lives — and this page works through why, and what to do when that is not possible, extending the consistency material in distributed algorithm sync.

The problem in concrete numbers

Twelve pods enforce 60 requests per minute per key using a token bucket refilled from each pod’s local clock. NTP keeps them within ±50 ms normally; after a hypervisor migration one pod is 900 ms ahead.

That pod writes ts = now values 900 ms in the future. When the next request lands on a correctly-synced pod, it computes elapsed = now − ts = −900 ms, which — if unclamped — subtracts 0.9 tokens, and if clamped, simply skips a refill. Either way the client’s real rate wobbles by 1.5% per skewed pod per request. With four skewed pods in a rolling migration, the advertised limit is neither 60 nor a stable number: it depends on which pod answers.

Shared state written by clocks that disagree Three pods with clocks offset by different amounts write timestamps into one shared bucket, so each subsequent read computes a different elapsed time and the effective limit varies by which pod handled the request. One bucket, three writers, three clocks pod A: clock +0 ms pod B: clock +900 ms pod C: clock −120 ms shared bucket tokens + ts effective limit depends on the writer the state is shared but the clock is not — that mismatch is the whole bug

Options, in order of preference

Approach Skew eliminated Cost Notes
Read the clock inside the store script Yes, entirely None redis.call('TIME') — the default choice
Store-issued token on write Yes One extra field Useful when the algorithm needs both times
Application clock + NTP discipline No, bounded Operational Skew becomes a bounded error, not zero
Application clock + skew clamp Partly One comparison Prevents lockouts, not drift
Logical counters instead of timestamps Yes Different algorithm Window counters with INCR need no clock at all
Hybrid logical clocks Mostly Complexity Overkill for rate limiting

Two of these deserve emphasis. Window counters keyed by an epoch bucket avoid the problem structurally: INCR ratelimit:{key}:{floor(now/60)} still uses a clock, but only to pick a key name, and a 900 ms skew changes the chosen bucket only for requests within 900 ms of a boundary. And reading the clock in the script costs nothing — the script already runs on the machine holding the state.

Step-by-step: removing skew from the decision

lua
-- One clock, one state, one machine. The caller supplies no time at all.
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cost = tonumber(ARGV[3]) or 1

local t   = redis.call('TIME')                     -- the only time source
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local st     = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(st[1]) or cap
local ts     = tonumber(st[2]) or now

-- Even with one clock, clamp: a failover to a node with a slightly different
-- clock, or a restored snapshot, can still produce a stale future timestamp.
local elapsed = math.max(0, now - ts)
tokens = math.min(cap, tokens + elapsed / 1000 * rate)

local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { allowed, math.floor(tokens), allowed == 1 and 0 or math.ceil((cost - tokens) / rate * 1000) }

When the store cannot supply the clock — an in-memory limiter, an edge worker, a database without server-side scripting — bound the damage instead:

typescript
// Defensive clock handling when a local timestamp is unavoidable.
const MAX_PLAUSIBLE_ELAPSED_MS = 60 * 60 * 1000;      // one hour
const MAX_ACCEPTED_SKEW_MS = 2_000;

export function safeElapsed(now: number, ts: number, observedSkewMs = 0): number {
  // 1. Never negative: a backwards correction must not subtract capacity.
  let elapsed = Math.max(0, now - ts);
  // 2. Never implausible: a resumed VM reporting a week of elapsed time
  //    should refill to capacity, which a one-hour cap already achieves.
  elapsed = Math.min(elapsed, MAX_PLAUSIBLE_ELAPSED_MS);
  // 3. Discount known skew so a fast node does not credit itself extra time.
  if (observedSkewMs > MAX_ACCEPTED_SKEW_MS) {
    metrics.increment("ratelimit.clock_skew_exceeded");
    elapsed = Math.max(0, elapsed - observedSkewMs);
  }
  return elapsed;
}

// Measure the offset once per minute against the store, and export it.
export async function measureSkew(redis: Redis): Promise<number> {
  const before = Date.now();
  const [sec, micro] = await redis.time();
  const after = Date.now();
  const storeMs = Number(sec) * 1000 + Math.floor(Number(micro) / 1000);
  const localMid = (before + after) / 2;            // discount round-trip time
  const skew = localMid - storeMs;
  metrics.gauge("ratelimit.clock_skew_ms", skew);
  return skew;
}
Three strategies ranked by how much skew survives Reading the clock inside the store removes skew entirely, epoch-keyed window counters confine it to requests near a boundary, and application clocks with clamping merely bound the damage. How much skew each approach leaves behind clock in the store skew remaining: none cost: none use this unless you cannot epoch-keyed counters skew affects only requests near a window boundary no timestamp state at all local clock + clamps skew remaining: bounded prevents lockouts only last resort, plus a metric clamping is damage control; colocating the clock with the state is the actual fix

Gotchas and edge cases

  • TIME is not replicated verbatim. With effect replication this is a non-issue on modern Redis, but a deployment pinned to an old version may require redis.replicate_commands() before calling it.
  • Round-trip time inflates a skew measurement. Comparing local time before the call against store time makes every node look slow by the network latency. Use the midpoint of before and after.
  • Alerting on drift rate instead of offset. A node can be stably 900 ms off with zero drift. Alert on absolute offset.
  • Virtual machine snapshots. A restored snapshot resumes with an old clock and an old view of state; the clamp handles the first request, and the store clock handles everything after.
  • Multiple stores in a cluster. Different Redis nodes have their own clocks. Keeping one identity’s keys in one slot means one clock decides that identity’s limit, which is what matters.
  • Edge workers with no store clock. Approximate counting is already the accepted trade there; do not attempt precise timestamp arithmetic across points of presence.
  • Skew inside the store’s own failover. A promoted replica with a different clock can produce one stale-future timestamp per key; the clamp absorbs it.
Measuring offset without counting the round trip as skew Comparing local time before the call against the store's time makes every node look slow by the network latency; comparing against the midpoint of the times before and after the call isolates the true offset. Measure the offset, not the latency local before store TIME local after midpoint of before and after — compare THIS with the store's reading using “before” alone reports every node as slow by half the round trip

Verification and testing

bash
# 1. Measure the real offset from every node, not just the one you are logged into.
for pod in $(kubectl get pods -l app=api -o name); do
  kubectl exec "$pod" -- node -e '
    const t0 = Date.now();
    require("ioredis").prototype;             // illustrative: use your client
  ' 2>/dev/null
done
# In practice: export ratelimit_clock_skew_ms as a gauge and read it from Prometheus:
#   max by (pod) (abs(ratelimit_clock_skew_ms))   -> should stay under ~100 ms

# 2. Prove the limiter is immune: deliberately skew one node and re-measure the ceiling.
kubectl exec deploy/api-canary -- date -s "+2 seconds"      # requires privileges
LIMIT_RPS=100 k6 run ratelimit.test.js | grep rl_accepted
# accepted must stay within a few per cent of 100/s: the store clock decides, not the pod
kubectl exec deploy/api-canary -- ntpdate -u pool.ntp.org   # restore

The second test is the one worth automating in a scheduled drill. A limiter that reads the store clock is unaffected by a skewed node; one that does not will show a measurably different ceiling, which is exactly the signal you want before a hypervisor migration finds it for you.

Frequently Asked Questions

How much clock skew is acceptable?

If the limiter reads time from the store, any amount — node clocks stop mattering entirely. If it cannot, keep offsets under roughly a tenth of the emission interval, so the error stays well below one request's worth of capacity, and alert on absolute offset rather than drift rate.

Do window-counter algorithms avoid the problem?

Largely. Keying a counter by an epoch bucket uses the clock only to choose a key name, so skew changes the chosen bucket only for requests within the skew of a boundary. That is a much smaller blast radius than timestamp arithmetic, which is one reason window counters remain popular despite their boundary behaviour.

What should happen when a node detects large skew?

Emit a metric and an alert, and — if the limiter depends on the local clock — discount the known offset when computing elapsed time. Do not silently continue: a node several seconds off will hand out or withhold capacity in a way no dashboard explains.

Is NTP enough on its own?

It bounds the problem but does not remove it, and it fails exactly when you least expect: after a virtual machine migration, a container resume, or a network partition that stops synchronisation. Treat NTP as a hygiene requirement and colocating the clock with the state as the actual design decision.