Implementing a Token Bucket Rate Limiter in JavaScript

Rate limiting is a crucial technique for protecting APIs and services from abuse, preventing denial-of-service attacks, and ensuring fair usage. This challenge asks you to implement a token bucket rate limiter in JavaScript, a common and effective algorithm for controlling the rate of requests. A token bucket rate limiter allows a certain number of requests within a given time window, simulating a bucket that is filled with tokens at a constant rate.

Problem Description

You are tasked with creating a RateLimiter class in JavaScript that implements the token bucket algorithm. The rate limiter should control the number of requests allowed within a specified time window.

What needs to be achieved:

• Create a RateLimiter class with a constructor that accepts two parameters: capacity (the maximum number of tokens the bucket can hold) and refillRate (the number of tokens added to the bucket per second).
• Implement a allowRequest() method that checks if a request can be allowed based on the current number of tokens in the bucket. If there are enough tokens, the method should decrement the token count and return true. Otherwise, it should return false.
• The allowRequest() method should also automatically refill the bucket at a rate defined by refillRate after each call, simulating the continuous addition of tokens.

Key Requirements:

• The rate limiter should accurately enforce the specified rate limit.
• The bucket should be refilled continuously, even when requests are not being made.
• The implementation should be efficient and avoid unnecessary computations.
• The class should be thread-safe (although in a single-threaded JavaScript environment, this primarily means avoiding race conditions if the rate limiter is accessed concurrently).

Expected Behavior:

• When a request is allowed, the token count should decrease.
• When a request is denied, the token count should remain unchanged.
• The bucket should be refilled at the specified rate, even when no requests are made.
• The token count should never exceed the capacity.

Edge Cases to Consider:

• capacity and refillRate being zero.
• capacity being a very large number.
• refillRate being a very small number.
• Concurrent access to the rate limiter (although JavaScript is single-threaded, consider how the logic would behave if it were used in a multi-threaded environment).

Examples

Example 1:

Input: capacity = 5, refillRate = 1
allowRequest(); // true (tokens = 4)
allowRequest(); // true (tokens = 3)
allowRequest(); // true (tokens = 2)
allowRequest(); // true (tokens = 1)
allowRequest(); // true (tokens = 0)
allowRequest(); // false (tokens = 0.5)
allowRequest(); // false (tokens = 1)

Explanation: The bucket starts with 5 tokens. Each allowRequest() call consumes a token. The bucket refills at a rate of 1 token per second. After 5 requests, the bucket is empty. The 6th request is denied. After a short delay, the bucket refills to 0.5 tokens, then 1 token.

Example 2:

Input: capacity = 2, refillRate = 0.5
allowRequest(); // true (tokens = 1)
allowRequest(); // true (tokens = 0)
allowRequest(); // false (tokens = 0)
setTimeout(() => allowRequest(), 1000); // true (tokens = 1)

Explanation: The bucket starts with 2 tokens. The first two requests are allowed. The third is denied. After 1 second, the bucket refills to 1 token, allowing the fourth request.

Example 3: (Edge Case)

Input: capacity = 0, refillRate = 1
allowRequest(); // false
allowRequest(); // false

Explanation: With a capacity of 0, no requests can ever be allowed.

Constraints

• capacity must be a positive integer.
• refillRate must be a positive number (floating-point is acceptable).
• The implementation should be reasonably efficient; avoid excessive memory usage or computationally expensive operations. A simple, clear implementation is preferred over a highly optimized one.
• The time between calls to allowRequest() can be arbitrary.

Notes

• Consider using setTimeout or setInterval to simulate the continuous refilling of the bucket. However, be mindful of the accuracy of these functions, as they are not guaranteed to be perfectly precise.
• You can use a timestamp to track the last time the bucket was refilled.
• Think about how to handle the case where the refillRate is very small compared to the capacity.
• The goal is to create a functional and understandable rate limiter, not necessarily the most performant one. Focus on correctness and clarity.
• You do not need to handle external errors or edge cases beyond those explicitly mentioned.