Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a production-grade architecture for a distributed rate limiting system using Redis and Lua scripting, focusing on the trade-offs between accuracy and memory cost. It compares the Rolling Window algorithm's performance against Token Bucket and Fixed Window algorithms, demonstrating its accuracy with manageable memory overhead. The system employs a three-layer architecture for managing and updating rate-limiting rules, deployed on a Redis Cluster for availability and scalability.
Achieve scalable and accurate rate limiting by trading off memory for precision using a Redis-based rolling window approach, outperforming traditional algorithms.
Designing a rate limiter that is simultaneously accurate, available, and scalable presents a fundamental challenge in distributed systems, primarily due to the trade-offs between algorithmic precision, availability, consistency, and partition tolerance. This article presents a concrete architecture for a distributed rate limiting system in a production-grade environment. Our design chooses the in-memory cache database, the Redis, along with its Sorted Set data structure, which provides $O(log (N))$ time complexity operation for the key-value pair dataset with efficiency and low latency, and maintains precision. The core contribution is quantifying the accuracy and memory cost trade-off of the chosen Rolling Window as the implemented rate limiting algorithm against the Token Bucket and Fixed Window algorithms. In addition, we explain how server-side Lua scripting is critical to bundling cleanup, counting, and insertion into a single atomic operation, thereby eliminating race conditions in concurrent environments. In the system architecture, we propose a three-layer architecture that manages the storage and updating of the limit rules. Through script load by hashing the rule parameters, rules can be changed without modifying the cached scripts. Furthermore, we analyze the deployment of this architecture on a Redis Cluster, which provides the availability and scalability by data sharding and replication. We explain the acceptance of AP (Availability and Partition Tolerance) from the CAP theorem as the pragmatic engineering trade-off for this use case.