Sliding-window counters

Deep dive

How it works

In: key, cost, now (monotonic ns) · Out: allow or deny, and the windowed estimate · State: a ring of n counters plus the newest bucket index per key (8n bytes) · Cost: O(1) per add; O(n) per estimate, O(1) with a running total.

Pick a window W and split time into buckets of width b. Bucket index = floor(t / b). Keep the last n bucket counters in a ring, indexed index % n.

1. Add: compute the bucket index; if it is newer than the newest one, zero the slots that fell out of the ring (at most n); then increment the slot.
2. Estimate at time t, with elapsed = t mod b: the window (t − (n−1)·b, t] covers the current bucket and the n−2 before it completely, and the fraction 1 − elapsed/b of the oldest one. Sum them. Events in the oldest bucket are assumed uniform over it.
3. Limit: allow if estimate + cost ≤ limit, then add.

For n = 2 (window = one bucket) this is the classic form:

          prev bucket        current bucket
  |-------------------|-------------------|
                 [  window = b  ]            elapsed = 0.3 b
estimate = prev * 0.7 + current

Fixed window is n = 1: no weighting, hard reset. Sliding log is the limit b → 0: one bucket per event.

Code

/// Ring of `n` sub-buckets, each `bucket_ns` wide. Window = (n-1) buckets;
/// the oldest slot is weighted by the part of it still inside the window.
/// n = 2 is the classic "previous + current" sliding-window counter.
pub struct SlidingCounter {
    slots: Vec<u64>,
    bucket_ns: u64,
    newest: u64, // absolute index of the newest bucket (now / bucket_ns)
}

impl SlidingCounter {
    pub fn new(n_slots: usize, bucket_ns: u64) -> Self {
        assert!(n_slots >= 2 && bucket_ns > 0);
        SlidingCounter { slots: vec![0; n_slots], bucket_ns, newest: 0 }
    }

    /// Move the ring forward, zeroing slots that left the window (lazily).
    fn advance(&mut self, b: u64) {
        if b > self.newest {
            let n = self.slots.len() as u64;
            for i in 1..=(b - self.newest).min(n) {
                self.slots[((self.newest + i) % n) as usize] = 0;
            }
            self.newest = b;
        }
    }

    pub fn add(&mut self, now_ns: u64, count: u64) {
        let b = now_ns / self.bucket_ns;
        self.advance(b);
        let n = self.slots.len() as u64;
        if self.newest - b < n { // late events land in their own bucket; too old: drop
            self.slots[(b % n) as usize] += count;
        }
    }

    /// Estimated events in (now - window, now]. Assumes the oldest bucket's
    /// events were spread evenly over it.
    pub fn estimate(&mut self, now_ns: u64) -> f64 {
        let b = (now_ns / self.bucket_ns).max(self.newest);
        self.advance(b);
        let n = self.slots.len() as u64;
        let elapsed = if now_ns / self.bucket_ns >= b { now_ns % self.bucket_ns } else { 0 };
        let oldest = self.slots[((b + 1) % n) as usize] as f64; // bucket b-(n-1)
        let rest: u64 = self.slots.iter().sum::<u64>() - oldest as u64;
        let kept = (self.bucket_ns - elapsed) as f64 / self.bucket_ns as f64;
        rest as f64 + oldest * kept
    }

    /// Rate limiter use: admit if the estimate stays within `limit`.
    pub fn allow(&mut self, now_ns: u64, limit: u64) -> bool {
        if self.estimate(now_ns) + 1.0 <= limit as f64 {
            self.add(now_ns, 1);
            true
        } else {
            false
        }
    }
}


fn main() {
    // Exact weighting: 4 buckets of 10 ns, 8 events in each.
    let mut c = SlidingCounter::new(4, 10);
    for t in [5, 15, 25, 35] { c.add(t, 8); }
    assert_eq!(c.estimate(35), 24.0 + 8.0 * 0.5); // oldest bucket half expired
    assert_eq!(c.estimate(40), 24.0);             // bucket 0 gone, bucket 1 fully in
    assert_eq!(c.estimate(1_000), 0.0);           // idle longer than the window

    // Two buckets = previous + current. Limit 10 per 1000 ns.
    let mut l = SlidingCounter::new(2, 1000);
    for _ in 0..10 { assert!(l.allow(999, 10)); }
    assert!(!l.allow(1000, 10));  // a fixed window would reset here and admit 10 more
    assert!(l.allow(1500, 10));   // previous bucket now weighs 0.5 -> estimate 5
    for _ in 0..4 { assert!(l.allow(1500, 10)); }
    assert!(!l.allow(1500, 10));

    // Late event goes to its own bucket; too-old event is dropped.
    let mut c = SlidingCounter::new(3, 10);
    c.add(25, 1);
    c.add(15, 1);
    c.add(5, 1);                                  // bucket 0 is still in the ring
    assert_eq!(c.estimate(25), 1.0 + 1.0 + 0.5);  // oldest bucket weighs 0.5
    c.add(35, 1);
    c.add(5, 1);                                  // bucket 0 is gone: dropped
    assert_eq!(c.estimate(35), 1.0 + 1.0 + 0.5);  // buckets 3, 2 + half of 1
    println!("ok");
}

Complexity and constants

• Add: one division, one modulo, one increment; zeroing is amortized O(1) (at most n slots per advance, and an idle key is zeroed once).
• Estimate: O(n) as written; keep a running total (subtract slots as they are zeroed) to make it O(1). The oldest slot still needs one multiply.
• Memory: 8n bytes per key with u64 slots, plus the newest index; u32 slots halve it. Two buckets = 16 bytes + 8. A key idle for W is all zeros and can be dropped.
• Accuracy: the error is at most the oldest bucket's count (the part the uniform assumption mis-weights). With smooth traffic and n buckets that is order of 1/(n−1) of the window total; a burst concentrated at one end of a bucket is the worst case.

Efficiency

• Cost: Measured on an Apple M4 Pro (one key, hot cache, release build): allow() took about 2 ns with n = 2 or 8 and about 5 ns with n = 60 (the O(n) sum). Memory is 8 bytes per bucket. For large key tables the bound is memory latency (one cache line per key), not compute.
• Levers:
  • Running total instead of summing the ring — O(n) → O(1) per estimate — large n.
  • Small slots (u32/u16) and n that fits one 64-byte cache line (8 × u64) — one cache miss per key — millions of keys.
  • Local counting with periodic sync — one round trip per batch instead of per event — distributed limits (see Distributed rate limiting).
  • Fewer, wider buckets — less memory and sync traffic, more error — approximate limits are acceptable.
• Naive → standard → state of the art:
  • Sorted set of timestamps (sliding log) · O(limit) memory, exact.
  • Fixed-window counter · 8 bytes, up to 2× burst at boundaries.
  • Two-bucket weighted estimate · 16 bytes, small error (Cloudflare).
  • Ring of sub-buckets · 8n bytes, tunable error.
  • Exponential histogram (DGIM) · O(log² N) bits for counts over the last N items, bounded relative error.

Implementation notes

• Use a monotonic clock in integer ns; derive the bucket index once per call and pass the same now to estimate and add.
• Make b a power of two ns if the division shows up in profiles (>> and & replace / and %).
• Time going backwards or late events: add to their own bucket if still in the ring, drop otherwise (the code above does this; never move newest backwards).
• Shared state: pack the slots in an array and update with atomics; zeroing races with adds, so for strict correctness use a lock or CAS on (newest, slots). Per-thread rings merged at read time avoid sharing.
• Redis form, as commonly built: two keys id:floor(t/W) with INCR and a TTL of about 2W; read the previous key, weight it, compare; do it in one Lua script or pipeline (one round trip).
• Retry-After: the time to the next bucket boundary is a simple, conservative answer.

Pitfalls

• Weighted estimates can be a few events off in either direction: do not use them as exact quotas.
• Reading the estimate before advancing the ring double-counts expired buckets; always advance first.
• Idle gap longer than the ring: zero at most n slots, not gap / b (the loop above caps it).
• Window length vs bucket width: with n = 2 the window equals the bucket width, so a "per minute" limit needs minute buckets. For per-minute limits with 1-second resolution use n = 61.
• Wall-clock jumps (NTP) corrupt bucket indices; use monotonic time on one machine, one time source across machines.
• Sliding log in a Redis sorted set is exact but costs memory per event and three commands per request (ZREMRANGEBYSCORE, ZCARD, ZADD): fine for small limits, bad for large ones.

Variants and alternatives

In production

Cloudflare's rate limiting uses the two-bucket weighted estimate (described in their blog post below). Upstash's ratelimit offers fixed window, sliding window and token bucket modes and notes that its sliding window assumes a uniform flow in the previous window. Kong ships fixed-window counters in its open-source rate-limiting plugin and sliding windows in Rate Limiting Advanced.

Implementations

Sources

• Julien Desgats, How we built rate limiting capable of scaling to millions of domains, Cloudflare blog 2017. post
• Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Maintaining Stream Statistics over Sliding Windows, SIAM Journal on Computing 31(6), 2002. paper
• Leskovec, Rajaraman, Ullman, Mining of Massive Datasets, ch. 4 (Mining Data Streams), Cambridge University Press. book
• Upstash, Ratelimit algorithms (fixed window, sliding window, token bucket). docs