Rate Limiting and Consistent Hashing: From Provided Source

The source lists six goals for the limiter. We will test every algorithm against them.

1. R1Accurately limit excessive requests.
2. R2Low latency. Do not slow HTTP response.
3. R3Use as little memory as possible.
4. R4Distributed rate limiting across servers or processes.
5. R5Exception handling. Show clear throttle signal.
6. R6High fault tolerance. Cache failure must not take down system.

A public API faces intentional flood and accidental loops. Bots retry. Users misbehave. Paid third party calls charge per call. Examples from text are credit check, payment, and health record retrieval.

Without a gate, one caller starves others. This breaks (1). It also breaks (2) because queues grow. It breaks cost because more servers are needed for junk.

The gate can sit in two places. Option A is inside API servers. Option B is rate limiter middleware in front of them. A common realization of B is an API gateway. Gateway choice depends on stack, control of algorithm, existing auth use, and engineering time.

Picture two tools.

A bucket holds tokens. Requests spend tokens. A refiller adds tokens on a timer. Full bucket means extra tokens overflow and vanish.

A window remembers timestamps or counts. New request asks if recent history is over quota. Old history expires.

Token bucket and leaking bucket are bucket tools. Fixed window counter, sliding window log, and sliding window counter are window tools. Buckets allow short bursts if tokens remain. Windows enforce rate over time.

A. Token bucket.

Parameters are bucket size and refill rate. Example from text is size 4 and refill 4 per 1 minute. Start full with 4.

• At 1:00:00 one request arrives. One token is consumed. Request goes through.
• At 1:00:05 three requests arrive. Three tokens remain. All three go through. Bucket is now 0.
• At 1:00:20 one request arrives. Zero tokens remain. Request is dropped.
• At 1:01:00 four tokens are refilled.

Rule per endpoint needs its own bucket. Example is 1 post per second plus 150 friends per day plus 5 likes per second needs 3 buckets per user. Per IP needs one bucket per IP. Global limit of 10,000 requests per second needs one shared bucket.

B. Leaking bucket.

Think FIFO queue plus fixed outflow. Parameters are queue size and outflow rate.

• Arrival checks if queue is full. If not full, enqueue.
• If full, drop.
• Worker pulls from queue at fixed rate.

Shopify uses this shape when stable outflow matters.

C. Fixed window counter.

Divide time into fixed windows. Keep one counter per window. Each request increments. Over threshold means drop until next window. Example allows 3 per second.

Failure case included. Limit is 5 per minute with reset on round minute. Five arrive 2:00:00 to 2:01:00. Five more arrive 2:01:00 to 2:02:00. Rolling interval 2:00:30 to 2:01:30 sees 10. That is twice quota. This breaks (1).

D. Sliding window log.

Store each request timestamp, often in Redis sorted sets. On new request, remove timestamps older than start of current window. Insert new timestamp. If log size is within allowed count, accept. Else reject.

Trace with limit 2 per minute:

• 1:00:01 arrives. Log empty. Insert 1:00:01. Size 1. Allow.
• 1:00:30 arrives. Insert 1:00:30. Size 2. Allow.
• 1:00:50 arrives. Insert 1:00:50. Size 3. Reject. Timestamp stays in log per text.
• 1:01:40 arrives. Window is [1:00:40, 1:01:40). Remove 1:00:01 and 1:00:30. Size becomes 2 after insert. Allow.

This is accurate in any rolling window.

E. Sliding window counter.

This is a hybrid of fixed counter and sliding log. Formula from text:

estimate = current_window_count + previous_window_count * overlap_fraction

Worked example: limit 7 per minute. Previous has 5. Current has 3. New request at 30% into current minute means overlap with previous is 70%. Estimate is 3 + 5 * 0.7 = 6.5. Round down to 6 in example. Allow because 6 is under 7. Next request would hit limit.

High level storage uses Redis. INCR adds 1 to counter. EXPIRE sets timeout so counter deletes itself. Flow is client to middleware to Redis check to API servers or 429. Headers returned are X-Ratelimit-Remaining and X-Ratelimit-Limit and X-Ratelimit-Retry-After.

Rules live on disk as config. Workers pull rules into cache. Example Lyft rules are 5 marketing messages per day and 5 logins per minute. Exceeded requests return 429. Some use cases enqueue to message queue for later instead of drop, such as overload limited orders.

Weaknesses stated honestly:

• Token and leaking need tuning of two knobs. Wrong size or rate means too strict or too loose. Token allows bursts. Leaking queues old requests so new bursts get dropped behind old work.
• Fixed window is cheap and simple but allows edge double count. This breaks (1).
• Sliding log is accurate but stores even rejected timestamps. This breaks (3).
• Sliding counter is cheap but approximate. It assumes even spread in previous window. This breaks (1) for strict lookback.
• Naive hash serverIndex = hash(key) % N breaks on membership change. With 4 servers and 8 keys, removing one server remaps most keys, not just keys on dead server. That storm breaks (2) and (6).
• Basic ring has uneven partitions. Example is removal of s1 doubles s2 partition. Keys can also clump, with most keys on server 2 and none on server 1 and 3.
• Concurrent read, check, increment has race condition. Counter is 3. Two threads read 3. Both write 4. Correct is 5. Locks fix it but slow system and break (2).
• Multiple limiters without sync break (4). Client 1 hits limiter 1. Client 2 hits limiter 2. Then clients swap limiters. No limiter has full count.
• Far data center adds latency. This breaks (2).

Fixes and their price:

• Use central Redis for counters and timestamps. Price is extra hop and Redis becomes critical. Mitigate with high fault tolerance so cache outage does not halt APIs, per (6).
• Fix race with Redis Lua script or sorted set atomic ops. Price is Lua complexity and Redis load.
• Do not use sticky sessions to pin client to one limiter. It is inflexible and unscalable. Use shared store instead.
• Use multi data center edge routing to closest edge. Price is more sites to run.
• Sync edges with eventual consistency model. Price is short disagreement between edges.
• Monitor effectiveness. If valid traffic drops, relax rules. If flash sale needs bursts, switch toward token bucket.
• Fix hash imbalance with virtual nodes. Each real server gets many points on ring. Price is more metadata. Tune count to fit needs.
• Fix rehash storm with consistent hashing. Only neighbors of added or removed node move.

Hash both servers and keys with same function onto ring. SHA-1 space wraps from max back to 0. To locate a key, walk clockwise from key position to first server. Example mapping is key0 to server 0, key1 to server 1, key2 to server 2, key3 to server 3.

Add server 4 near key0. Only key0 moves from server 0 to server 4. Others stay. Remove server 1. Only key1 moves to server 2. Others stay. Quote from text is only k/n keys remap on average, where k is keys and n is slots.

Affected range rule:

• Add: start at new node s4. Move anticlockwise until existing server s3. Keys in (s3, s4] move to s4.
• Remove: start at removed s1. Move anticlockwise until s0. Keys in (s0, s1] move to successor s2.

Virtual nodes make partitions fine grained. Instead of s0, place s0_0, s0_1, s0_2. Lookup finds first virtual node, then maps to real server. More replicas lower variance but cost storage.

Key value context from text start: pair size is small, under 10 KB. Operations are put(key, value) and get(key). Goals are big data, high availability, high scalability, automatic scaling, tunable consistency, low latency. Hashing provides the scaling and auto membership part.

import time
from bisect import bisect

# --- Token bucket: capacity 4, refill 4 per 60s (text example) ---
class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_per_sec = refill_per_sec
        self.last = time.monotonic()
    def allow(self):
        now = time.monotonic()
        # Line that matters: refill by elapsed time, cap at capacity (overflow vanishes)
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.refill_per_sec)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

# --- Fixed window counter: 3 per 1s (text example) ---
class FixedWindow:
    def __init__(self, limit, window_sec):
        self.limit = limit
        self.window_sec = window_sec
        self.window_start = int(time.time())
        self.count = 0
    def allow(self):
        now = int(time.time())
        # Line that matters: reset on window boundary (cause of edge burst)
        if now - self.window_start >= self.window_sec:
            self.window_start = now
            self.count = 0
        self.count += 1
        return self.count <= self.limit

# --- Sliding counter estimate: 3 + 5*0.7 = 6.5 (text example) ---
def sliding_estimate(current, previous, overlap_frac):
    # Line that matters: weight previous window by overlap
    return current + previous * overlap_frac

# --- Consistent hash ring with virtual nodes ---
class Ring:
    def __init__(self):
        self.points = []  # list of (hash, server)
    def add_server(self, server, replicas):
        # Line that matters: many points per server smooth partitions
        for i in range(replicas):
            h = hash(f"{server}#{i}") % (2**32)  # illustrative hash, not SHA-1
            self.points.append((h, server))
        self.points.sort()
    def lookup(self, key):
        hs = [p[0] for p in self.points]
        h = hash(key) % (2**32)  # illustrative
        # Line that matters: clockwise walk = first point >= h, wrap to 0
        idx = bisect(hs, h) % len(hs)
        return self.points[idx][1]

if __name__ == "__main__":
    b = TokenBucket(capacity=4, refill_per_sec=4/60)
    print([b.allow() for _ in range(5)])  # expect 4 True then False
    print(sliding_estimate(3, 5, 0.7))  # expect 6.5
    r = Ring()
    r.add_server("s0", 3); r.add_server("s1", 3)
    print(r.lookup("k0"))

[True, True, True, True, False]
6.5
s0 or s1 (depends on illustrative hash)

• Notes focus on refill cap, window reset, overlap weighting, and clockwise wrap. Hash here is illustrative. Text uses SHA-1.

Field guide, each with WHY from text:

• Amazon and Stripe use token bucket for API throttle. WHY: simple, memory efficient, allows short bursts.
• Shopify uses leaking bucket. WHY: needs stable outflow rate.
• Lyft open sourced rate limit component with domain descriptors. WHY: flexible rules like 5 per day versus 5 per minute need config files plus cache.
• Redis with INCR plus EXPIRE. WHY: fast memory plus auto expiry beats disk DB.
• Cloudflare sliding counter at scale. WHY: smooths spikes with little memory, error only 0.003% in test.
• Amazon Dynamo partitioning component. WHY: minimize remap on scale.
• Apache Cassandra data partitioning. WHY: same scale reason.
• Discord chat, Akamai CDN, Maglev load balancer. WHY: even spread plus easy horizontal scale plus hotspot mitigation. Example hotspot is celebrity data landing on one shard.

Interview ears:

• Q: Where to put limiter, server or gateway?A: No absolute answer. Server gives full algorithm control. Gateway fits if already doing auth and IP allow lists. Own service costs time. Commercial gateway saves time.
• Q: Hard versus soft limiting?A: Hard never exceeds threshold. Soft allows short exceed. Choose soft for flash sale bursts, hard for paid quota.
• Q: What layer?A: Chapter covers layer 7 HTTP. IP tables can limit at layer 3. OSI has 7 layers listed in text.
• Q: How to avoid being limited as client?A: Cache to avoid calls, respect limit, catch 429, add backoff retry.
• Q: How to fix race without locks?A: Lua script or Redis sorted set atomic update. Locks break (2).
• Q: Sticky sessions for sync?A: Works but not scalable or flexible. Central store is better.
• Q: How many virtual nodes?A: More lowers stddev but costs space. 100 gives about 10%. 200 gives about 5%. Tune to requirement.