Gossip Protocol & Distributed Cache

A distributed cache in the rate limiting context is a shared, low-latency store that multiple rate-limiter nodes read/write to maintain globally consistent counters — replacing local-only or gossip-propagated state with a centralized source of truth.

-- Fixed Window Counter (Lua, atomic)
local key = "rl:{clientID}:{window}"      -- e.g. rl:user123:202403191400
local count = redis.call('INCR', key)
if count == 1 then
    redis.call('EXPIRE', key, 60)          -- TTL = window size
end
return count <= limit

-- Sliding Window Log (ZSET)
local now = tonumber(ARGV[1])             -- current timestamp ms
local window = tonumber(ARGV[2])          -- e.g. 60000ms
local limit = tonumber(ARGV[3])

redis.call('ZREMRANGEBYSCORE', KEY, 0, now - window)
local count = redis.call('ZCARD', KEY)
if count < limit then
    redis.call('ZADD', KEY, now, now)      -- score=timestamp, member=timestamp
    redis.call('EXPIRE', KEY, window/1000)
    return 1                               -- allowed
end
return 0                                   -- denied

To shard rate-limit counters across cache nodes without global coordination:

type HashRing struct {
    replicas int
    ring     map[uint32]string   // hash → nodeID
    sorted   []uint32
}

func (h *HashRing) GetNode(clientID string) string {
    hash := crc32(clientID)
    // find first ring position >= hash (clockwise)
    idx := sort.Search(len(h.sorted), func(i int) bool {
        return h.sorted[i] >= hash
    })
    if idx == len(h.sorted) { idx = 0 }   // wrap around
    return h.ring[h.sorted[idx]]
}

// clientID "user:123" always routes to same cache node
// Node failure → only that node's keys re-routed, not all

Rate limiting is the enforcement of a maximum request count per client per time window. The core challenge at scale: counters must be globally consistent, fast, and fault-tolerant — an impossible triad under CAP.

func (rl *SlidingWindowRL) Allow(ctx context.Context, clientID string) (bool, error) {
    now := time.Now()
    currWindow := now.Truncate(rl.windowSize).Unix()
    prevWindow := currWindow - int64(rl.windowSize.Seconds())

    currKey := fmt.Sprintf("rl:%s:%d", clientID, currWindow)
    prevKey := fmt.Sprintf("rl:%s:%d", clientID, prevWindow)

    pipe := rl.redis.Pipeline()
    incrCmd  := pipe.Incr(ctx, currKey)
    prevCmd  := pipe.Get(ctx, prevKey)
    pipe.Expire(ctx, currKey, rl.windowSize*2)
    pipe.Exec(ctx)

    curr := incrCmd.Val()
    prev, _ := strconv.ParseInt(prevCmd.Val(), 10, 64)

    // weighted count: prev_count × overlap_fraction + curr_count
    elapsed := float64(now.UnixNano()-currWindow*1e9) / float64(rl.windowSize)
    estimated := float64(prev)*(1-elapsed) + float64(curr)

    return estimated <= float64(rl.limit), nil
}

type TokenBucket struct {
    capacity   int64
    refillRate  float64  // tokens per second
}

var tokenBucketScript = redis.NewScript(`
  local tokens = tonumber(redis.call('GET', KEYS[1]) or ARGV[1])
  local last   = tonumber(redis.call('GET', KEYS[2]) or ARGV[3])
  local now    = tonumber(ARGV[3])
  local rate   = tonumber(ARGV[4])
  local cap    = tonumber(ARGV[1])

  -- refill tokens based on elapsed time
  local elapsed = math.max(0, now - last)
  tokens = math.min(cap, tokens + elapsed * rate)

  if tokens >= 1 then
    tokens = tokens - 1
    redis.call('SET', KEYS[1], tokens, 'EX', 86400)
    redis.call('SET', KEYS[2], now,    'EX', 86400)
    return 1   -- allowed
  end
  return 0     -- denied
`)

How gossip and distributed cache fit together — and the exact tradeoffs you need to articulate in a Staff-level system design interview.

1. REQUIREMENTS CLARIFICATION
   → Hard limit (billing) or soft limit (API quota)?
   → Per-user, per-IP, or per-API-key?
   → Single region or multi-region?
   → What's acceptable accuracy? (exact vs ~5% overage)
   → What's target latency budget for RL check? (<1ms? <5ms?)

2. ALGORITHM CHOICE
   → Soft limit at scale → Sliding Window Counter + Gossip
   → Hard limit, low scale → Token Bucket + Redis
   → Smooth traffic → Leaky Bucket

3. DATA LAYER
   → Redis Cluster for strong consistency
   → Local CRDT + Gossip for eventual consistency
   → Two-tier: local L1 + Redis L2

4. FAILURE MODES
   → Redis down: fail-open or local fallback?
   → Network partition: accept stale reads?
   → Node crash: counter loss → sticky routing helps

5. SCALING & OPERATIONS
   → Consistent hashing for shard assignment
   → Gossip for node membership (like Cassandra)
   → Metrics, alerting, sync lag monitoring

Click a node to inject a rate-limit counter update. Watch it propagate via gossip rounds.

Simulate requests hitting multiple RL nodes with gossip-based counter sync. Observe how counters converge.