Hone logo
Hone
Problems

Implement a Simple Rate Limiter in JavaScript

Building a rate limiter is crucial for protecting your applications from abuse, ensuring fair usage, and maintaining system stability. This challenge asks you to implement a basic in-memory rate limiter that restricts the number of times a specific action can be performed within a given time window.

Problem Description

You need to create a JavaScript class, RateLimiter, that can track and limit the number of requests made by different "clients" (identified by a string key). The rate limiter should allow a specified number of requests within a defined time period.

Key Requirements:

  • Client Identification: The rate limiter must support multiple clients, each identified by a unique string key.
  • Time Window: A fixed time duration (in milliseconds) over which the request count is tracked.
  • Maximum Requests: A limit on the number of requests allowed per client within the time window.
  • canRequest(key) Method: A method that takes a client key and returns true if the client is allowed to make a request, and false otherwise.
  • State Management: The rate limiter needs to internally manage the timestamps of requests for each client.

Expected Behavior:

  • When canRequest(key) is called for a client that has not exceeded its limit within the current time window, it should return true and record the current request's timestamp.
  • When canRequest(key) is called for a client that has already reached its limit within the current time window, it should return false.
  • Requests made outside the current time window should not count towards the limit for the current window.

Edge Cases:

  • What happens if canRequest is called for a key that has never been seen before?
  • How does the rate limiter handle the transition between time windows?

Examples

Example 1:

const limiter = new RateLimiter(3, 1000); // Allow 3 requests per second

// Simulate requests
console.log(limiter.canRequest('user1')); // Output: true (1st request)
console.log(limiter.canRequest('user1')); // Output: true (2nd request)
console.log(limiter.canRequest('user1')); // Output: true (3rd request)
console.log(limiter.canRequest('user1')); // Output: false (4th request - limit reached)

// Wait for more than 1 second
setTimeout(() => {
  console.log(limiter.canRequest('user1')); // Output: true (New window, request allowed)
}, 1100);

Explanation: The user1 client makes 3 requests within the 1000ms window, all of which are allowed. The 4th request within the same window is denied. After 1100ms, a new time window has started, and the next request is allowed.

Example 2:

const limiter = new RateLimiter(2, 500); // Allow 2 requests per 500ms

console.log(limiter.canRequest('user2')); // Output: true
console.log(limiter.canRequest('user3')); // Output: true (Different client, independent limit)
console.log(limiter.canRequest('user2')); // Output: true
console.log(limiter.canRequest('user2')); // Output: false
console.log(limiter.canRequest('user3')); // Output: true
console.log(limiter.canRequest('user3')); // Output: false

Explanation: Each client (user2 and user3) has its own independent limit of 2 requests per 500ms. The output shows that each client's requests are tracked separately and correctly.

Example 3: Window Transition

const limiter = new RateLimiter(1, 1000); // Allow 1 request per second

console.log(limiter.canRequest('user4')); // Output: true (Request 1 at t=0)

setTimeout(() => {
  console.log(limiter.canRequest('user4')); // Output: false (Request 2 at t=500, still within the first window)
}, 500);

setTimeout(() => {
  console.log(limiter.canRequest('user4')); // Output: true (Request 3 at t=1000, new window starts)
}, 1000);

setTimeout(() => {
  console.log(limiter.canRequest('user4')); // Output: false (Request 4 at t=1500, limit of 1 reached in the new window)
}, 1500);

Explanation: The first request is allowed. The second request at 500ms falls within the same 1000ms window and is denied as the limit of 1 is reached. The third request at 1000ms starts a new window and is allowed. The fourth request at 1500ms is denied because it exceeds the limit in the second window.

Constraints

  • maxRequestsPerWindow will be an integer between 1 and 100.
  • timeWindowMs will be an integer between 100 and 10000 (milliseconds).
  • Client keys will be non-empty strings.
  • Your implementation should be efficient and avoid excessive memory usage for a reasonable number of clients.

Notes

  • You will need to use Date.now() or similar to get the current timestamp.
  • Consider how you will store the request timestamps for each client. A Map or a plain JavaScript object could be useful.
  • Think about how to efficiently remove old timestamps that are no longer relevant to the current time window. This is key to preventing memory leaks.
  • The RateLimiter class should be instantiated with maxRequestsPerWindow and timeWindowMs.
Loading editor...
javascript