ADR-0042: Redis-Based Rate Limiting

Status

Accepted - 2025-01-26

---

Context

TVL Platform APIs need rate limiting to prevent abuse, ensure fair usage, and protect against DoS attacks.

---

Decision

Token Bucket algorithm with Redis for distributed rate limiting.

Rationale

1. Distributed: Works across API replicas
2. Flexible: Per-user, per-org, per-endpoint limits
3. Fast: <1ms overhead
4. Industry Standard: Used by Stripe, GitHub, AWS

---

Alternatives Considered

Alternative 1: In-Memory Rate Limiting

Rejected - Doesn't work across replicas

Alternative 2: Fixed Window

Rejected - Allows burst at window boundary

Alternative 3: API Gateway Rate Limiting

Rejected - Adds latency, vendor lock-in

---

Implementation

Token Bucket Algorithm

// src/rateLimit/tokenBucket.ts
export async function checkRateLimit(
  key: string,
  limit: number, // Max tokens
  window: number // Window in seconds
): Promise<{ allowed: boolean; remaining: number; resetAt: Date }> {
  const now = Date.now();
  const windowMs = window * 1000;

  // Lua script for atomic rate limiting
  const script = `
    local key = KEYS[1]
    local limit = tonumber(ARGV[1])
    local window = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])

    local current = redis.call('GET', key)

    if current == false then
      -- First request - set count to 1
      redis.call('SET', key, 1, 'PX', window)
      return {1, limit - 1, now + window}
    else
      local count = tonumber(current)
      if count < limit then
        -- Increment count
        redis.call('INCR', key)
        local ttl = redis.call('PTTL', key)
        return {1, limit - count - 1, now + ttl}
      else
        -- Rate limit exceeded
        local ttl = redis.call('PTTL', key)
        return {0, 0, now + ttl}
      end
    end
  `;

  const result = await redis.eval(
    script,
    1,
    key,
    limit,
    windowMs,
    now
  ) as [number, number, number];

  const [allowed, remaining, resetAt] = result;

  return {
    allowed: allowed === 1,
    remaining,
    resetAt: new Date(resetAt),
  };
}

Rate Limit Middleware

// src/middleware/rateLimit.ts
import { FastifyRequest, FastifyReply } from 'fastify';

export function rateLimitMiddleware(options: {
  limit: number;
  window: number;
  keyGenerator?: (req: FastifyRequest) => string;
}) {
  return async (req: FastifyRequest, reply: FastifyReply) => {
    // Generate rate limit key
    const key = options.keyGenerator
      ? options.keyGenerator(req)
      : `ratelimit:${req.user?.orgId}:${req.url}`;

    // Check rate limit
    const result = await checkRateLimit(key, options.limit, options.window);

    // Set headers
    reply.header('X-RateLimit-Limit', options.limit);
    reply.header('X-RateLimit-Remaining', result.remaining);
    reply.header('X-RateLimit-Reset', result.resetAt.toISOString());

    if (!result.allowed) {
      return reply.status(429).send({
        error: 'Too Many Requests',
        retryAfter: Math.ceil((result.resetAt.getTime() - Date.now()) / 1000),
      });
    }
  };
}

Apply to Routes

// src/routes/bookings.ts
app.get(
  '/api/v1/bookings',
  {
    preHandler: rateLimitMiddleware({
      limit: 100, // 100 requests
      window: 60, // per 60 seconds (1 minute)
    }),
  },
  async (req, reply) => {
    // Handler logic
  }
);

// Higher limit for admins
app.get(
  '/api/v1/admin/analytics',
  {
    preHandler: rateLimitMiddleware({
      limit: 1000,
      window: 60,
      keyGenerator: (req) => `ratelimit:admin:${req.user.id}`,
    }),
  },
  async (req, reply) => {
    // Admin handler
  }
);

---

Rate Limit Tiers

Per-Endpoint Limits

Endpoint	Free Tier	Paid Tier	Enterprise
List Properties	100/min	1000/min	Unlimited
Create Booking	10/min	100/min	1000/min
Search	30/min	300/min	3000/min
Webhooks	100/min	1000/min	10000/min

export const RateLimits = {
  FREE: {
    listProperties: { limit: 100, window: 60 },
    createBooking: { limit: 10, window: 60 },
    search: { limit: 30, window: 60 },
  },
  PAID: {
    listProperties: { limit: 1000, window: 60 },
    createBooking: { limit: 100, window: 60 },
    search: { limit: 300, window: 60 },
  },
  ENTERPRISE: {
    listProperties: { limit: 10000, window: 60 },
    createBooking: { limit: 1000, window: 60 },
    search: { limit: 3000, window: 60 },
  },
};

Dynamic Tier Selection

export function getRateLimitForOrg(orgId: string, endpoint: string) {
  // Fetch org tier from database
  const org = await getOrganization(orgId);

  switch (org.tier) {
    case 'free':
      return RateLimits.FREE[endpoint];
    case 'paid':
      return RateLimits.PAID[endpoint];
    case 'enterprise':
      return RateLimits.ENTERPRISE[endpoint];
    default:
      return RateLimits.FREE[endpoint];
  }
}

// Apply dynamic limit
app.get('/api/v1/properties', {
  preHandler: async (req, reply) => {
    const limits = getRateLimitForOrg(req.user.orgId, 'listProperties');
    await rateLimitMiddleware(limits)(req, reply);
  },
}, handler);

---

Rate Limit Keys

Key Patterns

export const RateLimitKeys = {
  // Per-org, per-endpoint
  orgEndpoint: (orgId: string, endpoint: string) =>
    `ratelimit:org:${orgId}:${endpoint}`,

  // Per-user, per-endpoint
  userEndpoint: (userId: string, endpoint: string) =>
    `ratelimit:user:${userId}:${endpoint}`,

  // Global per-endpoint (public endpoints)
  globalEndpoint: (endpoint: string) =>
    `ratelimit:global:${endpoint}`,

  // Per-IP (unauthenticated requests)
  ip: (ip: string, endpoint: string) =>
    `ratelimit:ip:${ip}:${endpoint}`,
};

---

Advanced Features

Burst Allowance

Allow short bursts above limit:

export async function checkRateLimitWithBurst(
  key: string,
  limit: number,
  burstLimit: number,
  window: number
): Promise<{ allowed: boolean; remaining: number }> {
  const result = await checkRateLimit(key, burstLimit, window);

  if (result.allowed) {
    return result;
  }

  // Burst exceeded - check sustained limit
  const sustainedKey = `${key}:sustained`;
  return await checkRateLimit(sustainedKey, limit, window);
}

// Usage: 100 sustained, 200 burst
await checkRateLimitWithBurst(key, 100, 200, 60);

Cost-Based Rate Limiting

Different endpoints cost different tokens:

export const EndpointCosts = {
  'GET /properties': 1,
  'POST /bookings': 10,
  'GET /analytics': 50,
};

export async function checkCostBasedRateLimit(
  orgId: string,
  endpoint: string
): Promise<boolean> {
  const cost = EndpointCosts[endpoint] || 1;
  const key = `ratelimit:org:${orgId}:tokens`;

  const result = await checkRateLimit(key, 1000, 60); // 1000 tokens/min

  if (result.remaining >= cost) {
    // Deduct tokens
    await redis.decrby(key, cost - 1); // -1 because checkRateLimit already incremented
    return true;
  }

  return false;
}

---

Monitoring

Track Rate Limit Hits

export async function recordRateLimitHit(
  orgId: string,
  endpoint: string
) {
  const key = `metrics:ratelimit:hits:${orgId}:${endpoint}`;
  await redis.incr(key);
  await redis.expire(key, 86400); // 24h retention

  logger.warn({ orgId, endpoint }, 'Rate limit exceeded');
}

// Alert if org hits limit >100 times/hour

Dashboard Metrics

Rate Limiting Metrics:
- Rate limit hits/hour (per org, per endpoint)
- Top rate-limited orgs
- Top rate-limited endpoints
- Burst usage vs sustained

---

Bypass for Internal Services

export const INTERNAL_SERVICE_TOKEN = process.env.INTERNAL_SERVICE_TOKEN;

export function rateLimitMiddleware(options: RateLimitOptions) {
  return async (req: FastifyRequest, reply: FastifyReply) => {
    // Bypass for internal services
    if (req.headers['x-internal-token'] === INTERNAL_SERVICE_TOKEN) {
      return; // Skip rate limiting
    }

    // Normal rate limiting
    const result = await checkRateLimit(/* ... */);
    // ...
  };
}

---

Testing

// tests/rateLimit/rateLimit.test.ts
describe('Rate Limiting', () => {
  it('should allow requests within limit', async () => {
    const key = 'test:ratelimit';

    // Send 10 requests (limit: 10/min)
    for (let i = 0; i < 10; i++) {
      const result = await checkRateLimit(key, 10, 60);
      expect(result.allowed).toBe(true);
    }
  });

  it('should block requests over limit', async () => {
    const key = 'test:ratelimit:exceeded';

    // Send 11 requests (limit: 10/min)
    for (let i = 0; i < 10; i++) {
      await checkRateLimit(key, 10, 60);
    }

    // 11th request should be blocked
    const result = await checkRateLimit(key, 10, 60);
    expect(result.allowed).toBe(false);
    expect(result.remaining).toBe(0);
  });

  it('should reset after window', async () => {
    const key = 'test:ratelimit:reset';

    // Hit limit
    for (let i = 0; i < 10; i++) {
      await checkRateLimit(key, 10, 1); // 1 second window
    }

    // Wait for window to expire
    await sleep(1100);

    // Should allow requests again
    const result = await checkRateLimit(key, 10, 1);
    expect(result.allowed).toBe(true);
  });
});

---

Consequences

Positive

• ✅ Abuse Prevention: Protects against DoS attacks
• ✅ Fair Usage: Ensures all orgs get fair access
• ✅ Distributed: Works across replicas
• ✅ Flexible: Per-org, per-user, per-endpoint

Negative

• ❌ Latency: Adds 1-2ms per request
• ❌ Redis Dependency: Requires Redis uptime

Mitigations

• Use Redis pipelining for multiple limits
• Cache rate limit checks for 1s (trade-off: slightly inaccurate)
• Graceful degradation if Redis down (allow requests)

---

Validation Checklist

• Token bucket algorithm implemented
• Rate limit middleware on all public endpoints
• Per-org, per-endpoint limits configured
• X-RateLimit-* headers returned
• Rate limit hit monitoring enabled
• Bypass for internal services
• Tests for limits and resets

---

References

• Token Bucket Algorithm
• Stripe Rate Limiting
• Redis Rate Limiting