An alternative approach to rate limiting | Figma Blog (opens in new tab)

Figma built a Redis-backed rate limiter to protect its web application from excessive traffic and spam. The system needed to work across multiple servers, add minimal latency, remove stale data efficiently, remain accurate, and use little memory. Common algorithms each met some of these goals, but introduced trade-offs involving atomicity, burst behavior, or memory consumption.

Requirements and Redis

• Rate limits cap requests from a user or IP within a time period.
• Figma needed shared state because its application ran on multiple machines.
• Redis was preferred over PostgreSQL because it provides:
  • Faster in-memory reads and writes
  • Built-in expiration for stale tracking data
  • Efficient storage for rate-limit state

Token Bucket

• Stores each user’s last-request timestamp and remaining token count in a Redis hash.
• Tokens refill over time; a request is rejected when no tokens remain.
• It is memory-efficient and conceptually elegant.
• Its read-then-write operations are not atomic:
  • Two servers can read the same remaining token count.
  • Both may accept a request even though only one token was available.
• Redis locks could prevent this race but would slow concurrent requests and add complexity.
• Lua scripting could make the operations atomic, but Figma avoided introducing that complexity.

Fixed Window Counters

• Stores a request count for each user and fixed time interval, such as one Redis key per minute.
• Each request atomically increments its interval’s counter.
• Keys expire after the interval, preventing stale data from accumulating.
• The approach is simple, memory-efficient, and avoids the token bucket’s race condition.
• Its major flaw is boundary bursts:
  • With a five-request-per-minute limit, a user could send five requests at the end of one minute and five more immediately afterward.
  • This allows up to twice the intended traffic over a short sliding period.

Sliding Window Logs

• A sliding window log records the timestamps of individual requests.
• Older timestamps can be removed as the window advances, and the remaining entries provide an accurate count.
• This avoids the boundary problem of fixed windows.
• The trade-off is memory usage: users making many requests require many timestamps to be stored.

The Central Trade-off

• Token buckets use little memory but require careful handling of distributed atomicity.
• Fixed counters are atomic and efficient but can permit bursts at window boundaries.
• Sliding logs are accurate but consume more memory.
• Figma’s rate limiter was designed around balancing these competing concerns rather than choosing the theoretically simplest algorithm.

The practical lesson is to select a rate-limiting strategy based on the required accuracy, concurrency model, storage system, and memory budget. Redis is a strong fit for distributed rate limiting, but the algorithm must account for both race conditions and burst behavior.