---
title: Rate Limiter Algorithms
summary: Sliding window and token bucket rate limiting implementations for gateway authentication and request throttling
---

# Rate Limiter Algorithms

## Overview

SophiaClaw implements two rate limiting algorithms:

1. **Sliding Window Rate Limiter** - Used for authentication attempt throttling
2. **Fixed Window Rate Limiter** - Used for general request throttling

Both algorithms are designed for in-memory operation within a single gateway process, with automatic cleanup to prevent unbounded memory growth.

---

## Sliding Window Rate Limiter

### Purpose

Track failed authentication attempts by client IP and scope, providing brute-force protection for gateway authentication.

**Location:** `src/gateway/auth-rate-limit.ts`

### Algorithm Design

#### Key Characteristics

- **Pure in-memory Map** - No external dependencies; suitable for single gateway process
- **Scope-based isolation** - Independent counters for different credential classes (shared token, device token, hook auth)
- **Loopback exemption** - Local CLI sessions (127.0.0.1 / ::1) are exempt by default
- **Side-effect-free module** - Callers create instances via `createAuthRateLimiter()`
- **Automatic pruning** - Periodic cleanup to prevent unbounded Map growth

#### Data Structures

```typescript
interface RateLimitEntry {
  attempts: number[]; // Timestamps (epoch ms) of failed attempts within window
  lockedUntil?: number; // If set, block requests until this epoch-ms instant
}

interface RateLimitCheckResult {
  allowed: boolean; // Whether request is allowed to proceed
  remaining: number; // Remaining attempts before limit reached
  retryAfterMs: number; // Ms until lockout expires (0 when not locked)
}
```

#### Configuration

```typescript
interface RateLimitConfig {
  maxAttempts?: number; // Default: 10 - Max failed attempts before blocking
  windowMs?: number; // Default: 60_000 (1 min) - Sliding window duration
  lockoutMs?: number; // Default: 300_000 (5 min) - Lockout duration after limit exceeded
  exemptLoopback?: boolean; // Default: true - Exempt loopback addresses
  pruneIntervalMs?: number; // Default: 60_000 - Background prune interval; <= 0 disables
}
```

#### Sliding Window Algorithm

```
┌─────────────────────────────────────────────────────────┐
│  Sliding Window Calculation (windowMs = 60_000)        │
│                                                         │
│  Now = 1000ms                                           │
│  Window = [Now - windowMs, Now] = [940ms, 1000ms]      │
│                                                         │
│  Attempts: [920, 945, 960, 980]                        │
│           └──┘ └───────────┘                            │
│         expired    within window                        │
│                                                         │
│  After slide: [945, 960, 980]                          │
│  Count = 3 remaining attempts in window                │
└─────────────────────────────────────────────────────────┘
```

#### Core Operations

**1. Window Sliding (`slideWindow`)**

```typescript
function slideWindow(entry: RateLimitEntry, now: number): void {
  const cutoff = now - windowMs;
  // Remove attempts that fell outside the window
  entry.attempts = entry.attempts.filter((ts) => ts > cutoff);
}
```

**Time Complexity:** O(n) where n = number of attempts in window
**Space Complexity:** O(n) for storing attempt timestamps

**2. Check Operation**

```typescript
function check(rawIp: string | undefined, rawScope?: string): RateLimitCheckResult {
  const { key, ip } = resolveKey(rawIp, rawScope);

  // Exempt loopback addresses
  if (isExempt(ip)) {
    return { allowed: true, remaining: maxAttempts, retryAfterMs: 0 };
  }

  const now = Date.now();
  const entry = entries.get(key);

  if (!entry) {
    return { allowed: true, remaining: maxAttempts, retryAfterMs: 0 };
  }

  // Still locked out?
  if (entry.lockedUntil && now < entry.lockedUntil) {
    return {
      allowed: false,
      remaining: 0,
      retryAfterMs: entry.lockedUntil - now,
    };
  }

  // Lockout expired - clear it
  if (entry.lockedUntil && now >= entry.lockedUntil) {
    entry.lockedUntil = undefined;
    entry.attempts = [];
  }

  slideWindow(entry, now);
  const remaining = Math.max(0, maxAttempts - entry.attempts.length);
  return { allowed: remaining > 0, remaining, retryAfterMs: 0 };
}
```

**3. Record Failure Operation**

```typescript
function recordFailure(rawIp: string | undefined, rawScope?: string): void {
  const { key, ip } = resolveKey(rawIp, rawScope);
  if (isExempt(ip)) return;

  const now = Date.now();
  let entry = entries.get(key);

  if (!entry) {
    entry = { attempts: [] };
    entries.set(key, entry);
  }

  // If currently locked, do nothing (already blocked)
  if (entry.lockedUntil && now < entry.lockedUntil) {
    return;
  }

  slideWindow(entry, now);
  entry.attempts.push(now);

  if (entry.attempts.length >= maxAttempts) {
    entry.lockedUntil = now + lockoutMs;
  }
}
```

**4. Prune Operation (Background Cleanup)**

```typescript
function prune(): void {
  const now = Date.now();
  for (const [key, entry] of entries) {
    // Keep entry if still locked out
    if (entry.lockedUntil && now < entry.lockedUntil) {
      continue;
    }

    slideWindow(entry, now);
    // Remove entry if no attempts remain in window
    if (entry.attempts.length === 0) {
      entries.delete(key);
    }
  }
}
```

#### State Machine

```
┌──────────────┐
│   Normal     │ ◄─────── Entry created on first failure
│  (allowed)   │
└──────┬───────┘
       │ recordFailure()
       │ attempts < maxAttempts
       ▼
┌──────────────┐
│  Throttled   │ ◄─────── attempts >= maxAttempts
│  (denied)    │         lockedUntil = now + lockoutMs
└──────┬───────┘
       │
       │ lockout expires OR prune() removes old attempts
       ▼
┌──────────────┐
│   Normal     │
│  (allowed)   │
└──────────────┘
```

#### Rate Limiting Scopes

```typescript
// Built-in scope constants
AUTH_RATE_LIMIT_SCOPE_DEFAULT = "default";
AUTH_RATE_LIMIT_SCOPE_SHARED_SECRET = "shared-secret";
AUTH_RATE_LIMIT_SCOPE_DEVICE_TOKEN = "device-token";
AUTH_RATE_LIMIT_SCOPE_HOOK_AUTH = "hook-auth";
```

**Key design:** Scopes allow independent rate limits for different credential types while sharing one limiter instance.

#### Example Usage

```typescript
const rateLimiter = createAuthRateLimiter({
  maxAttempts: 5,
  windowMs: 60_000,
  lockoutMs: 300_000,
});

// Check before allowing auth attempt
const result = rateLimiter.check(clientIp, AUTH_RATE_LIMIT_SCOPE_DEVICE_TOKEN);
if (!result.allowed) {
  return { error: "Too many failed attempts", retryAfterMs: result.retryAfterMs };
}

// Record failed attempt
rateLimiter.recordFailure(clientIp, AUTH_RATE_LIMIT_SCOPE_DEVICE_TOKEN);

// Reset on successful auth
rateLimiter.reset(clientIp, AUTH_RATE_LIMIT_SCOPE_DEVICE_TOKEN);
```

---

## Fixed Window Rate Limiter

### Purpose

General-purpose request throttling for API endpoints and gateway methods.

**Location:** `src/infra/fixed-window-rate-limit.ts`

### Algorithm Design

#### Key Characteristics

- **Time-based windows** - Fixed duration windows that reset at predictable intervals
- **Simple counters** - Lower memory overhead than sliding window
- **Deterministic reset** - Windows align to wall-clock time boundaries
- **Stateless design** - No timestamp arrays, just count + window start

#### Data Structures

```typescript
interface FixedWindowRateLimiter {
  consume: () => {
    allowed: boolean;
    retryAfterMs: number;
    remaining: number;
  };
  reset: () => void;
}
```

#### Configuration

```typescript
interface FixedWindowConfig {
  maxRequests: number; // Maximum requests per window
  windowMs: number; // Window duration in milliseconds
  now?: () => number; // Optional time function (for testing)
}
```

#### Fixed Window Algorithm

```
┌─────────────────────────────────────────────────────────┐
│  Fixed Window Timeline (windowMs = 60_000)             │
│                                                         │
│  Window 1: [0ms, 60s)     count = 0 → 10               │
│  Window 2: [60s, 120s)    count = 0 → 10               │
│  Window 3: [120s, 180s)   count = 0 → 10               │
│                                                         │
│  At t=65s: window reset, count = 0                      │
│  At t=125s: window reset, count = 0                     │
└─────────────────────────────────────────────────────────┘
```

#### Core Operations

```typescript
export function createFixedWindowRateLimiter(params: {
  maxRequests: number;
  windowMs: number;
  now?: () => number;
}): FixedWindowRateLimiter {
  const maxRequests = Math.max(1, Math.floor(params.maxRequests));
  const windowMs = Math.max(1, Math.floor(params.windowMs));
  const now = params.now ?? Date.now;

  let count = 0;
  let windowStartMs = 0;

  return {
    consume() {
      const nowMs = now();

      // Check if window has expired and needs reset
      if (nowMs - windowStartMs >= windowMs) {
        windowStartMs = nowMs;
        count = 0;
      }

      // Check if limit exceeded
      if (count >= maxRequests) {
        return {
          allowed: false,
          retryAfterMs: Math.max(0, windowStartMs + windowMs - nowMs),
          remaining: 0,
        };
      }

      // Consume one request
      count += 1;
      return {
        allowed: true,
        retryAfterMs: 0,
        remaining: Math.max(0, maxRequests - count),
      };
    },
    reset() {
      count = 0;
      windowStartMs = 0;
    },
  };
}
```

**Time Complexity:** O(1) for all operations
**Space Complexity:** O(1) - Only stores count and window start time

#### Usage Example

```typescript
const limiter = createFixedWindowRateLimiter({
  maxRequests: 100,
  windowMs: 60_000, // 100 requests per minute
});

function handleRequest() {
  const { allowed, retryAfterMs, remaining } = limiter.consume();

  if (!allowed) {
    return Response.json(
      { error: "Rate limit exceeded", retryAfterMs },
      { status: 429, headers: { "Retry-After": String(Math.ceil(retryAfterMs / 1000)) } },
    );
  }

  // Process request...
  return Response.json({ success: true, remaining });
}
```

---

## Algorithm Comparison

| Aspect                | Sliding Window                    | Fixed Window                            |
| --------------------- | --------------------------------- | --------------------------------------- |
| **Accuracy**          | Precise - tracks each attempt     | Approximate - can burst at boundaries   |
| **Memory**            | O(n) - stores timestamps          | O(1) - single counter                   |
| **Use Case**          | Auth brute-force protection       | API rate limiting                       |
| **Boundary Behavior** | Smooth - no burst at window edges | Can allow 2x burst at window boundaries |
| **Implementation**    | `src/gateway/auth-rate-limit.ts`  | `src/infra/fixed-window-rate-limit.ts`  |

### Boundary Burst Problem (Fixed Window)

```
┌─────────────────────────────────────────────────────────┐
│  Fixed Window Boundary Burst                            │
│                                                         │
│  Window 1: [0s, 60s)     - Request at 59s (count=100)  │
│  Window 2: [60s, 120s)   - Request at 61s (count=100)  │
│                                                         │
│  Result: 200 requests in 2 seconds!                     │
│  (100 at end of window 1 + 100 at start of window 2)   │
└─────────────────────────────────────────────────────────┘
```

**Solution:** Use sliding window for security-sensitive rate limiting where precision matters.

---

## Performance Considerations

### Memory Management

**Sliding Window:**

- Memory grows with number of tracked IPs × attempts per IP
- Prune interval controls cleanup frequency
- Unref'd timer allows process exit even with active timer

**Fixed Window:**

- Constant memory footprint
- No cleanup required
- Suitable for high-throughput scenarios

### Thread Safety

Both implementations are **single-threaded** (Node.js event loop model):

- No mutex/lock needed
- Operations are atomic within event loop turn
- Safe for concurrent HTTP requests in same process

### Scaling Considerations

**Single Process:**

- Both algorithms work well for single gateway instances
- Memory usage scales with unique client IPs

**Distributed Systems:**

- For multi-instance deployments, consider Redis-backed rate limiting
- Sliding window can be implemented with Redis sorted sets
- Fixed window can use Redis INCR + EXPIRE

---

## Testing Strategies

### Sliding Window Tests

```typescript
// Test basic sliding window behavior
describe("sliding window rate limiter", () => {
  it("blocks after maxAttempts within window", () => {
    const limiter = createAuthRateLimiter({ maxAttempts: 3, windowMs: 60_000 });

    limiter.recordFailure("192.168.1.1");
    limiter.recordFailure("192.168.1.1");
    limiter.recordFailure("192.168.1.1");

    const result = limiter.check("192.168.1.1");
    expect(result.allowed).toBe(false);
    expect(result.retryAfterMs).toBeGreaterThan(0);
  });

  it("allows after window expires", () => {
    let time = 0;
    const limiter = createAuthRateLimiter({
      maxAttempts: 2,
      windowMs: 60_000,
      now: () => time,
    });

    limiter.recordFailure("192.168.1.1");
    limiter.recordFailure("192.168.1.1");

    expect(limiter.check("192.168.1.1").allowed).toBe(false);

    time += 61_000; // Move past window
    expect(limiter.check("192.168.1.1").allowed).toBe(true);
  });
});
```

### Fixed Window Tests

```typescript
describe("fixed window rate limiter", () => {
  it("resets count at window boundary", () => {
    let time = 0;
    const limiter = createFixedWindowRateLimiter({
      maxRequests: 5,
      windowMs: 60_000,
      now: () => time,
    });

    // Consume all requests in first window
    for (let i = 0; i < 5; i++) {
      expect(limiter.consume().allowed).toBe(true);
    }
    expect(limiter.consume().allowed).toBe(false);

    // Move to next window
    time += 60_000;
    expect(limiter.consume().allowed).toBe(true);
  });
});
```

---

## Related Documentation

- [Gateway Authentication](/gateway/authentication)
- [Trusted Proxy Auth](/gateway/trusted-proxy-auth)
- [Gateway Security](/gateway/security)
- [Client IP Resolution](/algorithms/gateway-network/client-ip-resolution)