Mastering Rate Limiting: Token Bucket, Leaky Bucket, and Real‑World Implementations

When building high‑concurrency systems three tools protect stability: caching, degradation, and rate limiting. Caching boosts speed, degradation temporarily disables problematic services, and rate limiting controls request volume to avoid overload.

Rate‑Limiting Algorithms

Common algorithms include the token‑bucket and leaky‑bucket; a simple counter can also enforce coarse limits.

Token‑Bucket Algorithm

Assume a limit of 2r/s and add tokens every 500 ms.

The bucket holds up to b tokens; excess tokens are discarded.

When a packet of n bytes arrives, n tokens are removed; if insufficient tokens exist, the request is throttled.

Leaky‑Bucket Algorithm

A fixed‑capacity bucket leaks tokens at a constant rate.

If the bucket is empty, no tokens leak.

Incoming requests add tokens; overflow tokens are dropped.

Comparison: token‑bucket allows bursts while leaky‑bucket smooths traffic; both can achieve the same limiting effect with opposite directions.

Application‑Level Rate Limiting

Limits can be set on total concurrency, total resources (e.g., DB connections, threads), or per‑endpoint request counts. Example using Java AtomicLong:

try { if (atomic.incrementAndGet() > limit) { // reject } // process request } finally { atomic.decrementAndGet(); }

Guava’s RateLimiter implements token‑bucket smoothing:

RateLimiter limiter = RateLimiter.create(5); // 5 permits per second
System.out.println(limiter.acquire()); // blocks until a permit is available

Two Guava modes: SmoothBursty (allows bursts) and SmoothWarmingUp (gradual ramp‑up).

Distributed Rate Limiting

Implement atomic limits across machines using Redis + Lua or Nginx + Lua.

Redis + Lua Example

local key = KEYS[1]
local limit = tonumber(ARGV[1])
local current = tonumber(redis.call('INCRBY', key, 1))
if current > limit then return 0 else if current == 1 then redis.call('expire', key, 2) end return 1 end

Java integration:

String lua = Files.readString(Paths.get("limit.lua"));
Jedis jedis = new Jedis("192.168.147.52", 6379);
String key = "ip:" + System.currentTimeMillis()/1000;
boolean allowed = (Long)jedis.eval(lua, Collections.singletonList(key), Collections.singletonList("3")) == 1L;

Nginx + Lua Example

local locks = require "resty.lock"
local function acquire()
  local lock = locks:new("locks")
  lock:lock("limit_key")
  local counter = ngx.shared.limit_counter
  local key = "ip:" .. os.time()
  local limit = 5
  local current = counter:get(key)
  if current and current + 1 > limit then lock:unlock(); return 0 end
  if not current then counter:set(key, 1, 1) else counter:incr(key, 1) end
  lock:unlock()
  return 1
end
ngx.print(acquire())

Both approaches require careful handling of atomicity and clock synchronization.

Reference links: Wikipedia token bucket, leaky bucket; Redis INCR command; Nginx limit modules; OpenResty lua‑resty‑limit‑traffic.