Building Resilient Rate Limiters: The Token Bucket Algorithm in Node.js and Redis

Modern distributed systems are constantly under siege. Whether from malicious DDoS attacks, aggressive web scrapers, or a misconfigured microservice firing requests in an infinite loop, protecting your API endpoints is a non-negotiable requirement for backend engineers.

At the core of API protection lies the Rate Limiter. While simple in theory, implementing a rate limiter that is both performant under heavy loads and accurate across a distributed cluster of backend instances presents significant architectural challenges.

In this post, we will design and implement a production-grade rate limiter in Node.js and Redis using the Token Bucket algorithm, backed by atomic Redis Lua scripting to prevent race conditions.

Why the Token Bucket Algorithm?

Before writing code, let’s look at why the Token Bucket algorithm is the gold standard for HTTP APIs compared to alternatives like Fixed Window Counters or Sliding Logs:

• Fixed Window Counters suffer from the “spike at window boundary” problem, where a client can send double the allowed requests right at the edge of two time windows.
• Sliding Window Logs offer high accuracy but consume memory proportional to the number of requests, making them impractical for high-traffic systems.
• Token Bucket allows for controlled bursts of traffic while enforcing a steady-state average rate, all while maintaining an $O(1)$ memory footprint on the server.

How Token Bucket Works

1. A bucket has a maximum capacity ($C$).
2. Tokens are added to the bucket at a constant refill rate ($R$ tokens per second).
3. When a request arrives, we check if enough tokens are available in the bucket.
4. If yes, we consume $N$ tokens (usually 1) and let the request pass. If no, the request is rejected with a 429 Too Many Requests status code.

The Distributed Challenge and Race Conditions

In a distributed Node.js architecture running behind a load balancer, your application servers are stateless. State must be externalized, and Redis is the ideal data store for this due to its in-memory performance.

However, a naive implementation using multiple Redis commands (GET, evaluate, SET) introduces a classic Read-Modify-Write race condition:

Client A (Read): Bucket has 1 token
Client B (Read): Bucket has 1 token
Client A (Write): Consumes token, 0 left
Client B (Write): Consumes token, -1 left (OVERFLOW/BUGS!)

To guarantee atomicity without locking the entire Redis instance, we must execute our rate-limiting logic inside a Redis Lua script. Redis executes Lua scripts as a single, atomic operation.

Designing the Lua Script

Our Lua script needs to calculate the number of elapsed seconds since the last request, refill the bucket up to its maximum capacity, check if enough tokens remain, and update the state.

Here is the robust Lua script we will use:

-- KEYS[1]: Redis key for the bucket (e.g., 'ratelimit:user_123')
-- ARGV[1]: Maximum capacity of the bucket
-- ARGV[2]: Refill rate (tokens per second)
-- ARGV[3]: Current timestamp (epoch seconds with millisecond precision)
-- ARGV[4]: Number of tokens requested

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

-- Retrieve current bucket state
local bucket = redis.call('HMGET', key, 'tokens', 'last_refreshed')

local tokens
local last_refreshed

if not bucket[1] then
    -- Bucket doesn't exist yet; initialize to full capacity
    tokens = capacity
    last_refreshed = now
else
    tokens = tonumber(bucket[1])
    last_refreshed = tonumber(bucket[2])
end

-- Calculate elapsed time and tokens to add
local delta = math.max(0, now - last_refreshed)
local tokens_to_add = delta * refill_rate

-- Refill bucket, capped at maximum capacity
tokens = math.min(capacity, tokens + tokens_to_add)
last_refreshed = now

local allowed = 0
if tokens >= requested then
    tokens = tokens - requested
    allowed = 1
end

-- Save state back to Redis with a TTL to free memory
local ttl = math.ceil(capacity / refill_rate)
redis.call('HMSET', key, 'tokens', tokens, 'last_refreshed', last_refreshed)
redis.call('EXPIRE', key, ttl)

return { allowed, tokens }

Implementing the Node.js Client

Let’s integrate this script into a production-ready Node.js service using ioredis, which provides native support for loading and executing Lua scripts.

First, install the required dependency:

npm install ioredis

Next, write the rate limiter class:

const Redis = require('ioredis');

class TokenBucketRateLimiter {
  /**
   * @param {Redis} redisClient - Instance of ioredis
   */
  constructor(redisClient) {
    this.redis = redisClient;
    
    // Define the Lua script and its SHA digest for optimization
    this.luaSha = null;
    this.script = `
      local key = KEYS[1]
      local capacity = tonumber(ARGV[1])
      local refill_rate = tonumber(ARGV[2])
      local now = tonumber(ARGV[3])
      local requested = tonumber(ARGV[4])

      local bucket = redis.call('HMGET', key, 'tokens', 'last_refreshed')
      local tokens
      local last_refreshed

      if not bucket[1] then
          tokens = capacity
          last_refreshed = now
      else
          tokens = tonumber(bucket[1])
          last_refreshed = tonumber(bucket[2])
      end

      local delta = math.max(0, now - last_refreshed)
      local tokens_to_add = delta * refill_rate

      tokens = math.min(capacity, tokens + tokens_to_add)
      last_refreshed = now

      local allowed = 0
      if tokens >= requested then
          tokens = tokens - requested
          allowed = 1
      end

      local ttl = math.ceil(capacity / refill_rate) + 60
      redis.call('HMSET', key, 'tokens', tokens, 'last_refreshed', last_refreshed)
      redis.call('EXPIRE', key, ttl)

      return { allowed, tokens }
    `;
  }

  /**
   * Consume tokens from a user's bucket
   * @param {string} identifier - Unique key (e.g., IP address or User ID)
   * @param {number} capacity - Max bucket size
   * @param {number} refillRate - Tokens added per second
   * @param {number} cost - Number of tokens to consume for this request
   * @returns {Promise<{allowed: boolean, remainingTokens: number}>}
   */
  async consume(identifier, capacity, refillRate, cost = 1) {
    const key = `ratelimit:${identifier}`;
    // High-resolution epoch time in seconds
    const now = Date.now() / 1000;

    try {
      // EVALSHA can be used for optimization, but EVAL is safer if scripts change across deployments
      const result = await this.redis.eval(
        this.script,
        1,
        key,
        capacity,
        refillRate,
        now,
        cost
      );

      const allowed = result[0] === 1;
      const remainingTokens = parseFloat(result[1]);

      return { allowed, remainingTokens };
    } catch (error) {
      console.error('Rate limiter Redis error:', error);
      // Fail-open strategy: allow requests if Redis goes down, preventing cascading failures
      return { allowed: true, remainingTokens: capacity };
    }
  }
}

module.exports = TokenBucketRateLimiter;

Integrating into an Express Middleware

Now, let’s wrap our rate limiter inside an Express.js middleware to secure our API endpoints.

const express = require('express');
const Redis = require('ioredis');
const TokenBucketRateLimiter = require('./TokenBucketRateLimiter');

const app = express();
const redis = new Redis({ host: 'localhost', port: 6379 });
const limiter = new TokenBucketRateLimiter(redis);

// Rate limit middleware factory
const rateLimitMiddleware = (options) => {
  const { capacity, refillRate, cost = 1 } = options;

  return async (req, res, next) => {
    // Identify client by User ID if authenticated, otherwise fall back to IP
    const identifier = req.user?.id || req.ip;

    const { allowed, remainingTokens } = await limiter.consume(
      identifier,
      capacity,
      refillRate,
      cost
    );

    // Set standard rate-limiting HTTP headers
    res.setHeader('X-RateLimit-Limit', capacity);
    res.setHeader('X-RateLimit-Remaining', Math.max(0, Math.floor(remainingTokens)));

    if (!allowed) {
      return res.status(429).json({
        error: 'Too Many Requests',
        message: 'Rate limit exceeded. Please try again later.'
      });
    }

    next();
  };
};

// Apply to an expensive API route: Max 10 tokens, refilling at 2 tokens per second
app.api('/v1/resource', rateLimitMiddleware({ capacity: 10, refillRate: 2 }), (req, res) => {
  res.json({ data: 'Protected resource payload' });
});

app.listen(3000, () => {
  console.log('Server running on port 3000');
});

Edge Cases and Production Considerations

When deploying rate limiters at scale, you must account for several operational realities:

1. Clock Drift Across Redis Instances

If you are using Redis Cluster, ensure that time synchronization (NTP) is strictly managed across your nodes. Since our Lua script relies on Date.now() / 1000 passed from Node.js rather than Redis’s internal system clock (TIME), minor inconsistencies can occur if application servers have drifted clocks. Passing the timestamp from Node keeps behavior predictable, but ensure your app servers are synced via NTP.

2. Fail-Open vs. Fail-Closed

In our Node.js implementation, we wrapped the Redis call in a try/catch block that defaults to allowed: true. This is a fail-open strategy. For non-critical APIs, availability is preferred over strict rate enforcement if Redis experiences an outage. For financial transactions or security login routes, you may want a fail-closed strategy.

3. Memory Management and TTLs

Notice this line in our Lua script:

local ttl = math.ceil(capacity / refill_rate) + 60
redis.call('EXPIRE', key, ttl)

Without an explicit expiration time, inactive user keys would accumulate in Redis memory indefinitely, leading to a memory leak. Setting a TTL equal to the time it takes to completely refill the bucket ensures stale keys are automatically evicted.

Conclusion

By pairing the mathematical elegance of the Token Bucket algorithm with the atomic execution guarantees of Redis Lua scripts, you can build a rate limiter that is resilient, incredibly fast, and completely safe for distributed microservice architectures.

Always remember to design for failure: incorporate fail-open logic, set appropriate TTLs on your Redis keys, and monitor your rate limit metrics closely to fine-tune your bucket capacities for optimal user experience.