System Design Case Studies · Part 1 of 7

System Design - Rate Limiter

Tisan Das · · 3 min read

Contents

    Rate limiter is a vital component in large-scale web applications, as it controls traffic to the application servers to ensure a smooth experience for the majority of the users. It has become a critical component due to the rise in DDoS attacks, and it also helps limit computationally intensive operations for users.

    Requirements

    • Low latency: The rate-limiting component shouldn’t slow down the HTTP response
    • Memory footprint should be minimal to accommodate a large number of concurrent requests
    • Distributed rate limiting
    • Exception Handling: Show proper response message for rate-limited requests
    • High Fault tolerance: The requests shouldn’t fail in case the rate-limiting component fails

    Draft Design

    Where to put the rate limiter?
    • Client-side: Generally, client requests can be easily tampered with and bypassed, so it’s better not to place an important component like rate-limiting on the client side
    • Server-side:

    Where to put the rate limiter?: rate limiter hld Where to put the rate limiter?: rate limiter hld Where to put the rate limiter?: rate limiter hld

    Rate-limiting Algorithm

    There are several rate-limiting algorithms, such as Token-bucket and leaking bucket. However, here we discuss specifically the token bucket algorithm only, as it’s the most commonly used one.

    It involves two parameters:

    • Bucket size: A bucket is maintained for each type of request of each user. The bucket size represents the number of maximum tokens allowed in the bucket. Each request consumes a token from the bucket, and if there are no tokens left in the bucket, then the request is rejected.
    • Refill rate: number of tokens put into the bucket every unit time.

    Rate-limiting Algorithm: token bucket flow Rate-limiting Algorithm: token bucket flow

    Rate-limiting Algorithm: rate limiter tokrn bucket algo Rate-limiting Algorithm: rate limiter tokrn bucket algo Rate-limiting Algorithm: rate limiter tokrn bucket algo

    Using a database to store the token bucket-specific parameter isn’t advisable, as it requires disk access. Instead, it would be better to use an in-memory cache.

    Rate-limiting Algorithm: rate limiter hld2 Rate-limiting Algorithm: rate limiter hld2 Rate-limiting Algorithm: rate limiter hld2

    Detailed Design

    Detailed Design: rate limiter hld3 Detailed Design: rate limiter hld3 Detailed Design: rate limiter hld3

    Handling Race Condition

    Locks on the whole system generally slow down the system. Redis provides an alternative way to achieve atomicity through Lua scripting, where the Lua script is executed atomically on the server side. This is a common way to perform checks on Redis, as the scripts for the token bucket are executed ideally within 0.3 ms.

    Synchronization

    It’s recommended to use a centralized cache data store; otherwise, synchronization between cache service deployments is a difficult task. Generally, the synchronization is achieved in eventual consistency.

    Cloud Service Provider Offerings

    All the prominent cloud service providers offer cache service. AWS offers ElastiCache, which internally uses Redis, and Azure also provides a similar offering through Azure Cache. GCP offers Memorystore service for both Memcached and Redis.

    References

    1. Should I rate-limit packets with iptables?
    2. Rate Limit Requests with Iptables
    3. Scaling your API with rate limiters
    4. Scaling your API with rate limiters
    5. Better Rate Limiting With Redis Sorted Sets
    6. How we built rate limiting capable of scaling to millions of domains
    7. Lua scripting in Redis for performance gain
    8. Rate Limiting using Redis + Golang
    9. Atomicity with Lua
    10. Ratelimit code opensourced by Lyft
    11. Announcing Ratelimit : Go/gRPC service for generic rate limiting
    12. Amazon ElastiCache

    Open mail app

    Write in Gmail · Outlook