To build a hit counter for the last 5 minutes with support for multiple keys, we can use a data structure like a HashMap where keys are the service identifiers (e.g., "a", "b") and values are queues of timestamps. Each queue will store the timestamps of hits for its corresponding service.
When a hit occurs for a specific key, we add the current timestamp to that key's queue. To maintain the 5-minute window, we periodically iterate through each queue and remove timestamps older than 5 minutes from the current time. The size of the queue then represents the number of hits in the last 5 minutes for that key.
For the rate limiter, we can leverage this hit counter. A common approach is the token bucket or leaky bucket algorithm. For instance, using a token bucket, we can associate a certain number of "tokens" with each key. When a hit occurs, we check if there are available tokens. If yes, we consume a token and allow the request; otherwise, we deny it. Tokens can be replenished over time, or in this context, the number of available tokens can be directly related to the hit count within the 5-minute window. If the hit count exceeds a predefined limit within the window, the rate limiter denies subsequent requests.
Regarding the rate limiter potentially using a different instance of a counter, this is a valid consideration for distributed systems. If the hit counter and rate limiter need to be scaled independently or if they are deployed on different servers, each might manage its own counter instance. However, this introduces challenges in maintaining consistency across instances. Solutions like using a distributed cache (e.g., Redis) for the counters can help ensure a single source of truth and consistent rate limiting behavior across all instances.
Uber