1. Introduction & Motivation

Every public-facing API needs rate limiting. Without it, a single misbehaving client can starve resources for all other users, trigger cascading failures, and run up infrastructure costs. Rate limiting is the first line of defense in building resilient, fair, and cost-effective distributed systems.

Consider these scenarios: a mobile app client hitting your API 10,000 times per second due to a bug, a DDoS attack flooding your endpoints, or a batch job consuming all available database connections. Rate limiting protects against all of these. But implementing rate limiting correctly in a distributed environment — where multiple API gateway nodes must coordinate to enforce a single global limit — is a genuinely hard problem.

This article covers every algorithm (fixed window, sliding window log, sliding window counter, token bucket, leaky bucket), distributed coordination strategies (Redis-based, Lua scripting, consensus-based), and production considerations like multi-tenancy, tiered limits, graceful degradation, and observability. We provide complete C# implementations throughout, alongside the language-agnostic system design discussion.

2. Interview Context

Why Interviewers Ask This

• Algorithmic thinking: Multiple rate limiting algorithms exist, each with different trade-offs. Can you explain the differences?
• Distributed coordination: How do you enforce a global rate limit across multiple API gateway nodes?
• Trade-off analysis: Accuracy vs performance, memory vs precision, local vs global limits.
• Production awareness: Multi-tenancy, tiered limits, graceful degradation, and observability.
• API design: How do you expose rate limit headers and handle limit violations?

What Interviewers Look For

3. Functional Requirements

Core Features

• Rate limiting by API key: Each client gets a per-second and per-minute limit
• Rate limiting by endpoint: Different endpoints can have different limits
• Tiered limits: Free tier (100 req/min), Pro tier (1000 req/min), Enterprise (10000 req/min)
• Graceful rejection: Return HTTP 429 with Retry-After header
• Rate limit headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset
• Admin dashboard: View and modify rate limits per client

Use Cases

4. Non-Functional Requirements

5. Requirement Prioritization

MoSCoW Analysis

6. Capacity Estimation

Throughput

Storage

Bandwidth

7. Rate Limiting Algorithms

The choice of algorithm is the most fundamental decision in rate limiter design. Each algorithm has different trade-offs in terms of accuracy, memory usage, burst tolerance, and implementation complexity.

Algorithm 1: Fixed Window Counter

The simplest approach: divide time into fixed windows (e.g., 1-minute intervals) and count requests in each window. Reject when count exceeds the limit.

public class FixedWindowRateLimiter
{
    private readonly ConcurrentDictionary<string, long> _counters = new();
    private readonly int _limit;
    private readonly TimeSpan _window;

    public FixedWindowRateLimiter(int limit, TimeSpan window)
    {
        _limit = limit;
        _window = window;
    }

    public RateLimitResult Allow(string key)
    {
        var now = DateTimeOffset.UtcNow.ToUnixTimeSeconds();
        var windowKey = $"{key}:{now / (long)_window.TotalSeconds}";

        var count = _counters.AddOrUpdate(windowKey, 1, (k, v) => v + 1);

        var resetTime = ((now / (long)_window.TotalSeconds) + 1) * (long)_window.TotalSeconds;

        return new RateLimitResult
        {
            Allowed = count <= _limit,
            Remaining = Math.Max(0, _limit - (int)count),
            Limit = _limit,
            ResetAt = DateTimeOffset.FromUnixTimeSeconds(resetTime),
            RetryAfter = count > _limit
                ? TimeSpan.FromSeconds(resetTime - now)
                : TimeSpan.Zero
        };
    }
}

Pros: Simple, O(1) memory, O(1) time. Cons: Boundary burst problem — a client can send 100 requests at 12:00:59 and 100 more at 12:01:00, effectively getting 200 requests in 1 second.

Algorithm 2: Sliding Window Log

Store timestamps of every request in a sorted set. Count requests in the last N seconds. Eliminates the boundary problem but costs more memory.

public class SlidingWindowLogRateLimiter
{
    private readonly ConcurrentDictionary<string, SortedList<long, int>> _logs = new();
    private readonly int _limit;
    private readonly TimeSpan _window;

    public SlidingWindowLogRateLimiter(int limit, TimeSpan window)
    {
        _limit = limit;
        _window = window;
    }

    public RateLimitResult Allow(string key)
    {
        var now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
        var windowStart = now - (long)_window.TotalMilliseconds;

        var log = _logs.GetOrAdd(key, _ => new SortedList<long, int>());

        lock (log)
        {
            // Remove entries outside the window
            var keysToRemove = log.Keys.Where(k => k <= windowStart).ToList();
            foreach (var k in keysToRemove)
                log.Remove(k);

            var currentCount = log.Count;

            if (currentCount >= _limit)
            {
                var oldestEntry = log.Keys.First();
                var retryAfter = TimeSpan.FromMilliseconds(oldestEntry + (long)_window.TotalMilliseconds - now);

                return new RateLimitResult
                {
                    Allowed = false,
                    Remaining = 0,
                    Limit = _limit,
                    RetryAfter = retryAfter
                };
            }

            log.Add(now, currentCount + 1);

            return new RateLimitResult
            {
                Allowed = true,
                Remaining = _limit - currentCount - 1,
                Limit = _limit,
                RetryAfter = TimeSpan.Zero
            };
        }
    }
}

Pros: Exact counting, no boundary problem. Cons: O(N) memory per client (N = limit), lock contention under high concurrency.

Algorithm 3: Sliding Window Counter (Recommended)

A hybrid approach: use the current window count plus a weighted portion of the previous window. Best balance of accuracy and performance.

public class SlidingWindowCounterRateLimiter
{
    private readonly ConcurrentDictionary<string, WindowBucket> _windows = new();
    private readonly int _limit;
    private readonly TimeSpan _window;

    public SlidingWindowCounterRateLimiter(int limit, TimeSpan window)
    {
        _limit = limit;
        _window = window;
    }

    public RateLimitResult Allow(string key)
    {
        var now = DateTimeOffset.UtcNow;
        var currentWindowStart = now - now.TimeOfDay
            .Subtract(now.TimeOfDay)
            .Add(TimeSpan.FromSeconds(
                (long)(now - DateTimeOffset.UnixEpoch).TotalSeconds
                / (long)_window.TotalSeconds * (long)_window.TotalSeconds));

        var windowSeconds = (long)_window.TotalSeconds;
        var nowSeconds = (long)(now - DateTimeOffset.UnixEpoch).TotalSeconds;
        var currentWindowId = nowSeconds / windowSeconds;
        var previousWindowId = currentWindowId - 1;
        var positionInWindow = nowSeconds % windowSeconds;
        var weight = 1.0 - ((double)positionInWindow / windowSeconds);

        var bucket = _windows.AddOrUpdate(key,
            _ => new WindowBucket { Current = 0, Previous = 0, CurrentWindowId = currentWindowId },
            (k, existing) =>
            {
                if (existing.CurrentWindowId == currentWindowId)
                    return existing;

                return new WindowBucket
                {
                    Previous = existing.CurrentWindowId == previousWindowId ? existing.Current : 0,
                    Current = 0,
                    CurrentWindowId = currentWindowId
                };
            });

        long count;
        lock (bucket)
        {
            if (bucket.CurrentWindowId == currentWindowId)
                bucket.Current++;
            else
            {
                bucket.Previous = bucket.Current;
                bucket.Current = 1;
                bucket.CurrentWindowId = currentWindowId;
            }
            count = (long)(bucket.Previous * weight) + bucket.Current;
        }

        var resetAt = DateTimeOffset.FromUnixTimeSeconds((currentWindowId + 1) * windowSeconds);

        return new RateLimitResult
        {
            Allowed = count <= _limit,
            Remaining = Math.Max(0, _limit - (int)count),
            Limit = _limit,
            ResetAt = resetAt,
            RetryAfter = count > _limit
                ? resetAt - now
                : TimeSpan.Zero
        };
    }
}

public class WindowBucket
{
    public long Previous { get; set; }
    public long Current { get; set; }
    public long CurrentWindowId { get; set; }
}

Pros: Good accuracy (~99%), O(1) memory, no boundary problem. Cons: Approximate (weighted interpolation is an estimate).

Algorithm 4: Token Bucket

A bucket holds tokens. Each request consumes one token. Tokens are added at a fixed rate. Allows bursts up to bucket capacity, then throttles to the refill rate.

public class TokenBucketRateLimiter
{
    private readonly ConcurrentDictionary<string, TokenBucket> _buckets = new();
    private readonly int _capacity;
    private readonly double _refillRate; // tokens per second

    public TokenBucketRateLimiter(int capacity, int refillRatePerSecond)
    {
        _capacity = capacity;
        _refillRate = refillRatePerSecond;
    }

    public RateLimitResult Allow(string key)
    {
        var now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();

        var bucket = _buckets.GetOrAdd(key, _ => new TokenBucket
        {
            Tokens = _capacity,
            LastRefillTime = now
        });

        lock (bucket)
        {
            // Refill tokens
            var elapsed = (now - bucket.LastRefillTime) / 1000.0;
            var tokensToAdd = elapsed * _refillRate;
            bucket.Tokens = Math.Min(_capacity, bucket.Tokens + tokensToAdd);
            bucket.LastRefillTime = now;

            if (bucket.Tokens >= 1)
            {
                bucket.Tokens -= 1;
                return new RateLimitResult
                {
                    Allowed = true,
                    Remaining = (int)bucket.Tokens,
                    Limit = _capacity,
                    RetryAfter = TimeSpan.Zero
                };
            }
            else
            {
                var waitTime = (1 - bucket.Tokens) / _refillRate;
                return new RateLimitResult
                {
                    Allowed = false,
                    Remaining = 0,
                    Limit = _capacity,
                    RetryAfter = TimeSpan.FromSeconds(waitTime)
                };
            }
        }
    }
}

public class TokenBucket
{
    public double Tokens { get; set; }
    public long LastRefillTime { get; set; }
}

Pros: Allows controlled bursts, smooth rate over time. Cons: More complex, floating-point precision issues, requires lock for thread safety.

Algorithm 5: Leaky Bucket

Requests enter a queue (bucket). They are processed at a fixed rate. If the queue is full, new requests are rejected. Provides smooth, predictable output rate.

public class LeakyBucketRateLimiter
{
    private readonly ConcurrentDictionary<string, LeakyBucket> _buckets = new();
    private readonly int _capacity;
    private readonly double _leakRate; // requests per second

    public LeakyBucketRateLimiter(int capacity, int leakRatePerSecond)
    {
        _capacity = capacity;
        _leakRate = leakRatePerSecond;
    }

    public RateLimitResult Allow(string key)
    {
        var now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();

        var bucket = _buckets.GetOrAdd(key, _ => new LeakyBucket
        {
            Water = 0,
            LastLeakTime = now
        });

        lock (bucket)
        {
            // Leak water (process queued requests)
            var elapsed = (now - bucket.LastLeakTime) / 1000.0;
            var leaked = elapsed * _leakRate;
            bucket.Water = Math.Max(0, bucket.Water - leaked);
            bucket.LastLeakTime = now;

            if (bucket.Water + 1 <= _capacity)
            {
                bucket.Water += 1;
                return new RateLimitResult
                {
                    Allowed = true,
                    Remaining = (int)(_capacity - bucket.Water),
                    Limit = _capacity,
                    RetryAfter = TimeSpan.Zero
                };
            }
            else
            {
                var waitTime = (bucket.Water + 1 - _capacity) / _leakRate;
                return new RateLimitResult
                {
                    Allowed = false,
                    Remaining = 0,
                    Limit = _capacity,
                    RetryAfter = TimeSpan.FromSeconds(waitTime)
                };
            }
        }
    }
}

public class LeakyBucket
{
    public double Water { get; set; }
    public long LastLeakTime { get; set; }
}

Pros: Smooth output rate, protects downstream services. Cons: Adds latency (queued requests wait), doesn't handle bursts well.

Algorithm Comparison

8. High-Level Architecture

Key Components

• Rate Limiter Middleware: Intercepts every API request before it reaches the backend. Checks rate limits and either allows or rejects.
• Redis Cluster: Stores rate limit counters with sub-millisecond access. Provides atomic operations for concurrent access.
• Configuration Store: Stores per-client and per-endpoint rate limit configurations. Supports dynamic updates.
• Admin Dashboard: Allows operators to view usage, modify limits, and manage client tiers.

9. Production Architecture Diagram

Request Flow with Rate Limiting

Rejection Flow

10. Component Deep Dive

Redis-Based Sliding Window with Lua Script

The core rate limiting logic runs as a single atomic Lua script inside Redis, eliminating race conditions and network round-trips.

public class RedisSlidingWindowRateLimiter
{
    private readonly IConnectionMultiplexer _redis;
    private readonly ILogger<RedisSlidingWindowRateLimiter> _logger;

    private static readonly string RateLimitScript = @"
        local key = KEYS[1]
        local now = tonumber(ARGV[1])
        local window = tonumber(ARGV[2])
        local limit = tonumber(ARGV[3])

        local window_start = now - window

        -- Remove entries outside the window
        redis.call('ZREMRANGEBYSCORE', key, 0, window_start)

        -- Count requests in current window
        local current = redis.call('ZCARD', key)

        if current < limit then
            -- Add current request
            redis.call('ZADD', key, now, now .. '-' .. math.random(1000000))
            redis.call('EXPIRE', key, window)
            return {1, limit - current - 1, 0}
        else
            -- Calculate retry-after from oldest entry in window
            local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
            local retry_after = 0
            if #oldest > 0 then
                retry_after = math.ceil((tonumber(oldest[2]) + window - now) / 1000)
            end
            return {0, 0, retry_after}
        end
    ";

    public RedisSlidingWindowRateLimiter(IConnectionMultiplexer redis,
        ILogger<RedisSlidingWindowRateLimiter> logger)
    {
        _redis = redis;
        _logger = logger;
    }

    public async Task<RateLimitResult> CheckAsync(string key, int limit, TimeSpan window)
    {
        var db = _redis.GetDatabase();
        var now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();

        var result = await db.ScriptEvaluateAsync(
            RateLimitScript,
            new RedisKey[] { $"ratelimit:{key}" },
            new RedisValue[] { now, (long)window.TotalMilliseconds, limit });

        var values = (long[])result;
        var allowed = values[0] == 1;
        var remaining = (int)values[1];
        var retryAfter = (int)values[2];

        _logger.LogDebug("Rate limit check for {Key}: {Allowed}, remaining: {Remaining}",
            key, allowed, remaining);

        return new RateLimitResult
        {
            Allowed = allowed,
            Remaining = remaining,
            Limit = limit,
            RetryAfter = TimeSpan.FromSeconds(retryAfter)
        };
    }
}

Distributed Token Bucket with Redis

public class DistributedTokenBucket
{
    private readonly IConnectionMultiplexer _redis;

    private static readonly string TokenBucketScript = @"
        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 state = redis.call('HMGET', key, 'tokens', 'last_refill')
        local tokens = tonumber(state[1]) or capacity
        local last_refill = tonumber(state[2]) or now

        -- Refill tokens
        local elapsed = (now - last_refill) / 1000.0
        local refill = elapsed * refill_rate
        tokens = math.min(capacity, tokens + refill)
        last_refill = now

        if tokens >= requested then
            tokens = tokens - requested
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
            redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2)
            return {1, math.floor(tokens)}
        else
            local wait_ms = ((requested - tokens) / refill_rate) * 1000
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
            return {0, 0, math.ceil(wait_ms)}
        end
    ";

    public DistributedTokenBucket(IConnectionMultiplexer redis)
    {
        _redis = redis;
    }

    public async Task<RateLimitResult> AllowAsync(string key, int capacity,
        int refillRatePerSecond, int tokensRequested = 1)
    {
        var db = _redis.GetDatabase();
        var now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();

        var result = await db.ScriptEvaluateAsync(
            TokenBucketScript,
            new RedisKey[] { $"tokenbucket:{key}" },
            new RedisValue[] { capacity, refillRatePerSecond, now, tokensRequested });

        var values = (long[])result;
        return new RateLimitResult
        {
            Allowed = values[0] == 1,
            Remaining = values.Length > 1 ? (int)values[1] : 0,
            Limit = capacity,
            RetryAfter = values.Length > 2
                ? TimeSpan.FromMilliseconds(values[2])
                : TimeSpan.Zero
        };
    }
}

Multi-Tier Rate Limiter

public class MultiTierRateLimiter
{
    private readonly RedisSlidingWindowRateLimiter _redisLimiter;
    private readonly ConcurrentDictionary<string, ClientTierConfig> _tierCache = new();
    private readonly IConfigurationStore _configStore;

    public async Task<RateLimitResult> CheckAsync(string apiKey, string endpoint)
    {
        var config = await GetTierConfig(apiKey);

        // Check per-second limit first (fast path)
        var secondKey = $"{apiKey}:s";
        var secondResult = await _redisLimiter.CheckAsync(
            secondKey, config.PerSecondLimit, TimeSpan.FromSeconds(1));

        if (!secondResult.Allowed)
            return secondResult;

        // Then check per-minute limit
        var minuteKey = $"{apiKey}:m";
        var minuteResult = await _redisLimiter.CheckAsync(
            minuteKey, config.PerMinuteLimit, TimeSpan.FromSeconds(60));

        if (!minuteResult.Allowed)
            return minuteResult;

        // Then check per-hour limit
        var hourKey = $"{apiKey}:h";
        var hourResult = await _redisLimiter.CheckAsync(
            hourKey, config.PerHourLimit, TimeSpan.FromSeconds(3600));

        return new RateLimitResult
        {
            Allowed = true,
            Remaining = Math.Min(
                Math.Min(secondResult.Remaining, minuteResult.Remaining),
                hourResult.Remaining),
            Limit = config.PerMinuteLimit,
            RetryAfter = TimeSpan.Zero
        };
    }

    private async Task<ClientTierConfig> GetTierConfig(string apiKey)
    {
        if (_tierCache.TryGetValue(apiKey, out var cached))
            return cached;

        var config = await _configStore.GetClientConfig(apiKey);
        _tierCache[apiKey] = config;
        return config;
    }
}

public class ClientTierConfig
{
    public string ApiKey { get; set; }
    public string Tier { get; set; }  // "free", "pro", "enterprise"
    public int PerSecondLimit { get; set; }
    public int PerMinuteLimit { get; set; }
    public int PerHourLimit { get; set; }
    public List<string> BypassEndpoints { get; set; } = new();
}

11. Data Modeling

Redis Data Structures

Configuration Store Schema

public class RateLimitConfig
{
    public string Id { get; set; }
    public string ApiKey { get; set; }
    public string ClientName { get; set; }
    public string Tier { get; set; }

    // Global limits
    public int GlobalPerSecond { get; set; } = 10;
    public int GlobalPerMinute { get; set; } = 100;
    public int GlobalPerHour { get; set; } = 10000;

    // Per-endpoint overrides
    public Dictionary<string, EndpointLimit> EndpointLimits { get; set; } = new();

    // Metadata
    public DateTime CreatedAt { get; set; }
    public DateTime UpdatedAt { get; set; }
    public bool IsActive { get; set; } = true;
}

public class EndpointLimit
{
    public string Pattern { get; set; }  // "/api/v1/orders"
    public int PerSecond { get; set; }
    public int PerMinute { get; set; }
    public bool IsBypassed { get; set; }  // No rate limiting
}

12. API Design

HTTP Response Headers

HTTP/1.1 200 OK
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 742
X-RateLimit-Reset: 1705312860
X-RateLimit-Policy: 1000;w=60

Content-Type: application/json

{"status": "success", "data": {...}}

Rate Limit Exceeded Response

HTTP/1.1 429 Too Many Requests
Retry-After: 12
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1705312860
Content-Type: application/json

{
    "error": {
        "code": "RATE_LIMIT_EXCEEDED",
        "message": "Rate limit exceeded. Try again in 12 seconds.",
        "details": {
            "limit": 1000,
            "window": "60s",
            "retry_after": 12
        }
    }
}

Admin API for Managing Limits

// ASP.NET Core middleware for rate limiting
public class RateLimitMiddleware
{
    private readonly RequestDelegate _next;
    private readonly IMultiTierRateLimiter _limiter;
    private readonly ILogger<RateLimitMiddleware> _logger;

    public RateLimitMiddleware(RequestDelegate next,
        IMultiTierRateLimiter limiter,
        ILogger<RateLimitMiddleware> logger)
    {
        _next = next;
        _limiter = limiter;
        _logger = logger;
    }

    public async Task InvokeAsync(HttpContext context)
    {
        var apiKey = context.Request.Headers["X-API-Key"].FirstOrDefault()
            ?? context.Request.Query["api_key"].FirstOrDefault();

        if (string.IsNullOrEmpty(apiKey))
        {
            context.Response.StatusCode = 401;
            await context.Response.WriteAsJsonAsync(new { error = "API key required" });
            return;
        }

        var endpoint = $"{context.Request.Method}:{context.Request.Path}";

        var result = await _limiter.CheckAsync(apiKey, endpoint);

        // Always set rate limit headers
        context.Response.Headers["X-RateLimit-Limit"] = result.Limit.ToString();
        context.Response.Headers["X-RateLimit-Remaining"] = result.Remaining.ToString();
        context.Response.Headers["X-RateLimit-Reset"] =
            DateTimeOffset.UtcNow.Add(result.RetryAfter).ToUnixTimeSeconds().ToString();

        if (!result.Allowed)
        {
            context.Response.StatusCode = 429;
            context.Response.Headers["Retry-After"] =
                ((int)result.RetryAfter.TotalSeconds).ToString();

            _logger.LogWarning("Rate limit exceeded for {ApiKey} on {Endpoint}",
                apiKey, endpoint);

            await context.Response.WriteAsJsonAsync(new
            {
                error = new
                {
                    code = "RATE_LIMIT_EXCEEDED",
                    message = $"Rate limit exceeded. Retry after {result.RetryAfter.TotalSeconds} seconds.",
                    retry_after = (int)result.RetryAfter.TotalSeconds
                }
            });
            return;
        }

        await _next(context);
    }
}

// Registration in Program.cs
public static class RateLimitServiceExtensions
{
    public static IServiceCollection AddRateLimiting(this IServiceCollection services,
        IConfiguration configuration)
    {
        services.AddSingleton<IConnectionMultiplexer>(sp =>
            ConnectionMultiplexer.Connect(configuration["Redis:ConnectionString"]));

        services.AddScoped<RedisSlidingWindowRateLimiter>();
        services.AddScoped<DistributedTokenBucket>();
        services.AddScoped<IMultiTierRateLimiter, MultiTierRateLimiter>();

        return services;
    }
}

13. Database Design

Rate Limit State Storage

PostgreSQL Schema for Config

CREATE TABLE rate_limit_clients (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    api_key VARCHAR(64) UNIQUE NOT NULL,
    client_name VARCHAR(255) NOT NULL,
    tier VARCHAR(32) NOT NULL DEFAULT 'free',
    global_per_second INT NOT NULL DEFAULT 10,
    global_per_minute INT NOT NULL DEFAULT 100,
    global_per_hour INT NOT NULL DEFAULT 10000,
    is_active BOOLEAN DEFAULT TRUE,
    created_at TIMESTAMPTZ DEFAULT NOW(),
    updated_at TIMESTAMPTZ DEFAULT NOW()
);

CREATE TABLE rate_limit_endpoint_overrides (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    client_id UUID REFERENCES rate_limit_clients(id),
    endpoint_pattern VARCHAR(255) NOT NULL,
    per_second INT,
    per_minute INT,
    is_bypassed BOOLEAN DEFAULT FALSE,
    created_at TIMESTAMPTZ DEFAULT NOW()
);

CREATE INDEX idx_clients_api_key ON rate_limit_clients(api_key);
CREATE INDEX idx_overrides_client ON rate_limit_endpoint_overrides(client_id);

Config Cache with Invalidation

public class CachedConfigStore : IConfigurationStore
{
    private readonly PostgreSQLConfigStore _db;
    private readonly IDistributedCache _cache;
    private readonly IMemoryCache _localCache;

    private static readonly TimeSpan LocalCacheTtl = TimeSpan.FromSeconds(30);
    private static readonly TimeSpan DistributedCacheTtl = TimeSpan.FromMinutes(5);

    public async Task<ClientTierConfig> GetClientConfig(string apiKey)
    {
        // L1: Local in-memory cache (fastest)
        if (_localCache.TryGetValue<ClientTierConfig>($"config:{apiKey}", out var local))
            return local;

        // L2: Redis distributed cache
        var cached = await _cache.GetStringAsync($"config:{apiKey}");
        if (cached != null)
        {
            var config = JsonSerializer.Deserialize<ClientTierConfig>(cached);
            _localCache.Set($"config:{apiKey}", config, LocalCacheTtl);
            return config;
        }

        // L3: PostgreSQL (source of truth)
        var dbConfig = await _db.GetByApiKey(apiKey);
        if (dbConfig != null)
        {
            var json = JsonSerializer.Serialize(dbConfig);
            await _cache.SetStringAsync($"config:{apiKey}", json,
                new DistributedCacheEntryOptions { AbsoluteExpirationRelativeToNow = DistributedCacheTtl });
            _localCache.Set($"config:{apiKey}", dbConfig, LocalCacheTtl);
        }

        return dbConfig;
    }

    public async Task UpdateClientConfig(string apiKey, ClientTierConfig config)
    {
        await _db.Update(config);
        await _cache.RemoveAsync($"config:{apiKey}");
        _localCache.Remove($"config:{apiKey}");
    }
}

14. Read/Write Path (Data Flow)

Rate Limit Check Path

Async Rate Limit Update Path

15. Distributed Rate Limiting

The fundamental challenge: multiple API gateway nodes must agree on a single global counter. There are several approaches, each with different trade-offs.

Approach 1: Centralized Counter (Redis)

All gateway nodes query a central Redis cluster. This is the most common approach in production.

public class CentralizedRateLimiter
{
    private readonly IConnectionMultiplexer _redis;
    private readonly int _retryCount = 3;

    public async Task<RateLimitResult> CheckAsync(string key, int limit, TimeSpan window)
    {
        for (int i = 0; i < _retryCount; i++)
        {
            try
            {
                var db = _redis.GetDatabase();
                var now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
                var windowMs = (long)window.TotalMilliseconds;

                var script = @"
                    local key = KEYS[1]
                    local now = tonumber(ARGV[1])
                    local window = tonumber(ARGV[2])
                    local limit = tonumber(ARGV[3])
                    local window_start = now - window

                    redis.call('ZREMRANGEBYSCORE', key, 0, window_start)
                    local current = redis.call('ZCARD', key)

                    if current < limit then
                        redis.call('ZADD', key, now, now .. '-' .. ARGV[4])
                        redis.call('PEXPIRE', key, window)
                        return {1, limit - current - 1, 0}
                    else
                        local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
                        local retry = 0
                        if #oldest > 0 then
                            retry = math.ceil((tonumber(oldest[2]) + window - now) / 1000)
                        end
                        return {0, 0, retry}
                    end
                ";

                var result = await db.ScriptEvaluateAsync(script,
                    new RedisKey[] { $"rl:{key}" },
                    new RedisValue[] { now, windowMs, limit, Guid.NewGuid().ToString("N") });

                var values = (long[])result;
                return new RateLimitResult
                {
                    Allowed = values[0] == 1,
                    Remaining = (int)values[1],
                    Limit = limit,
                    RetryAfter = TimeSpan.FromSeconds((int)values[2])
                };
            }
            catch (RedisException ex)
            {
                _logger.LogWarning("Redis error on attempt {Attempt}: {Error}", i + 1, ex.Message);
                if (i == _retryCount - 1)
                {
                    // Fail open on Redis failure
                    return RateLimitResult.Allow(limit);
                }
                await Task.Delay(TimeSpan.FromMilliseconds(10 * (i + 1)));
            }
        }

        return RateLimitResult.Allow(limit);
    }
}

Approach 2: Local Counter with Periodic Sync

Each gateway node maintains a local counter and periodically syncs with other nodes. Better latency but less accurate.

public class LocalSyncRateLimiter
{
    private readonly ConcurrentDictionary<string, LocalCounter> _localCounters = new();
    private readonly IMultiNodeSync _sync;
    private readonly int _nodeCount;

    public LocalSyncRateLimiter(IMultiNodeSync sync, int nodeCount)
    {
        _sync = sync;
        _nodeCount = nodeCount;
    }

    public RateLimitResult Allow(string key, int globalLimit)
    {
        // Each node gets 1/N of the global limit
        var localLimit = globalLimit / _nodeCount;

        var counter = _localCounters.GetOrAdd(key, _ => new LocalCounter
        {
            WindowStart = DateTimeOffset.UtcNow,
            Count = 0
        });

        lock (counter)
        {
            if (DateTimeOffset.UtcNow - counter.WindowStart > TimeSpan.FromSeconds(60))
            {
                counter.WindowStart = DateTimeOffset.UtcNow;
                counter.Count = 0;
            }

            counter.Count++;

            if (counter.Count > localLimit)
            {
                return new RateLimitResult
                {
                    Allowed = false,
                    Remaining = 0,
                    Limit = globalLimit,
                    RetryAfter = counter.WindowStart.AddSeconds(60) - DateTimeOffset.UtcNow
                };
            }

            return new RateLimitResult
            {
                Allowed = true,
                Remaining = globalLimit - (counter.Count * _nodeCount),
                Limit = globalLimit
            };
        }
    }
}

public class LocalCounter
{
    public DateTimeOffset WindowStart { get; set; }
    public long Count { get; set; }
}

Approach 3: Consensus-Based (Raft)

Use a consensus algorithm to replicate counters. Provides strong consistency but adds latency. Suitable for financial use cases.

Approach Comparison

16. Caching Strategy

Multi-Level Caching for Rate Limits

public class CachedRateLimiter
{
    private readonly IMultiTierRateLimiter _inner;
    private readonly IMemoryCache _localCache;
    private readonly TimeSpan _localCacheTtl = TimeSpan.FromMilliseconds(100);

    public CachedRateLimiter(IMultiTierRateLimiter inner)
    {
        _inner = inner;
        _localCache = new MemoryCache(new MemoryCacheOptions
        {
            SizeLimit = 10000,
            CompactionPercentage = 0.25
        });
    }

    public async Task<RateLimitResult> CheckAsync(string apiKey, string endpoint)
    {
        var cacheKey = $"{apiKey}:{endpoint}";

        // Check local cache for very recent results
        if (_localCache.TryGetValue<RateLimitResult>(cacheKey, out var cached)
            && cached != null)
        {
            // Only use cache if result is very recent (within 100ms)
            if (DateTimeOffset.UtcNow - cached.CheckedAt < _localCacheTtl)
            {
                return cached;
            }
        }

        var result = await _inner.CheckAsync(apiKey, endpoint);
        result.CheckedAt = DateTimeOffset.UtcNow;

        _localCache.Set(cacheKey, result, new MemoryCacheEntryOptions
        {
            AbsoluteExpirationRelativeToNow = _localCacheTtl,
            Size = 1
        });

        return result;
    }
}

Cache Invalidation for Config Changes

public class ConfigChangeWatcher : BackgroundService
{
    private readonly IConnectionMultiplexer _redis;
    private readonly IConfigurationStore _configStore;
    private readonly ILogger<ConfigChangeWatcher> _logger;

    protected override async Task ExecuteAsync(CancellationToken stoppingToken)
    {
        var subscriber = _redis.GetSubscriber();
        await subscriber.SubscribeAsync("rate_limit:config_changes", async (channel, message) =>
        {
            var change = JsonSerializer.Deserialize<ConfigChange>(message);

            _logger.LogInformation("Rate limit config changed for {ApiKey}", change.ApiKey);

            // Invalidate local caches
            _configStore.InvalidateCache(change.ApiKey);
        });

        await Task.Delay(Timeout.Infinite, stoppingToken);
    }
}

public class ConfigChange
{
    public string ApiKey { get; set; }
    public string ChangeType { get; set; }  // "update", "delete", "tier_change"
    public DateTime Timestamp { get; set; }
}

17. Scalability

Scaling the Rate Limiter

Redis Cluster Sharding

public class ShardedRateLimiter
{
    private readonly Dictionary<int, IConnectionMultiplexer> _shards = new();

    public ShardedRateLimiter(IConfiguration config)
    {
        var shardConnections = config.GetSection("Redis:Shards").Get<string[]>();
        for (int i = 0; i < shardConnections.Length; i++)
        {
            _shards[i] = ConnectionMultiplexer.Connect(shardConnections[i]);
        }
    }

    private IConnectionMultiplexer GetShard(string key)
    {
        var hash = Math.Abs(key.GetHashCode());
        var shardIndex = hash % _shards.Count;
        return _shards[shardIndex];
    }

    public async Task<RateLimitResult> CheckAsync(string apiKey, int limit, TimeSpan window)
    {
        var shard = GetShard(apiKey);
        var db = shard.GetDatabase();

        // Execute Lua script on the appropriate shard
        var result = await db.ScriptEvaluateAsync(LuaScript,
            new RedisKey[] { $"rl:{apiKey}" },
            new RedisValue[] {
                DateTimeOffset.UtcNow.ToUnixTimeMilliseconds(),
                (long)window.TotalMilliseconds,
                limit
            });

        return ParseResult(result, limit);
    }
}

18. Distributed Systems Design

Failure Scenarios

public class ResilientRateLimiter : IMultiTierRateLimiter
{
    private readonly RedisSlidingWindowRateLimiter _primary;
    private readonly LocalSyncRateLimiter _fallback;
    private readonly CircuitBreaker _circuitBreaker;
    private readonly ILogger<ResilientRateLimiter> _logger;

    public ResilientRateLimiter(
        RedisSlidingWindowRateLimiter primary,
        LocalSyncRateLimiter fallback,
        ILogger<ResilientRateLimiter> logger)
    {
        _primary = primary;
        _fallback = fallback;
        _logger = logger;

        _circuitBreaker = new CircuitBreaker(
            failureThreshold: 5,
            recoveryTimeout: TimeSpan.FromSeconds(30),
            onStateChange: (state) =>
            {
                _logger.LogWarning("Rate limiter circuit breaker state changed to {State}", state);
            });
    }

    public async Task<RateLimitResult> CheckAsync(string apiKey, string endpoint)
    {
        try
        {
            return await _circuitBreaker.ExecuteAsync(() =>
                _primary.CheckAsync(apiKey, endpoint));
        }
        catch (CircuitOpenException)
        {
            _logger.LogWarning("Circuit open, using local fallback for {ApiKey}", apiKey);

            // Fall back to local rate limiting
            var config = await GetConfigFromCache(apiKey);
            return _fallback.Allow($"{apiKey}:{endpoint}", config.PerMinuteLimit);
        }
        catch (Exception ex)
        {
            _logger.LogError(ex, "Rate limit check failed, failing open for {ApiKey}", apiKey);

            // Fail open - allow the request
            return RateLimitResult.Allow(int.MaxValue);
        }
    }
}

19. Consistency Models

Consistency in Rate Limiting

20. Reliability

Reliability Targets

Fail-Open Design

public class FailOpenRateLimiter
{
    private readonly RedisSlidingWindowRateLimiter _redisLimiter;
    private readonly ILogger<FailOpenRateLimiter> _logger;

    public async Task<RateLimitResult> CheckAsync(string key, int limit, TimeSpan window)
    {
        try
        {
            using var timeout = new CancellationTokenSource(TimeSpan.FromMilliseconds(100));
            return await Task.Run(
                () => _redisLimiter.CheckAsync(key, limit, window),
                timeout.Token);
        }
        catch (OperationCanceledException)
        {
            _logger.LogWarning("Rate limit check timed out for {Key}, failing open", key);
            return RateLimitResult.Allow(limit);
        }
        catch (RedisConnectionException ex)
        {
            _logger.LogWarning("Redis connection failed for {Key}, failing open: {Error}",
                key, ex.Message);
            return RateLimitResult.Allow(limit);
        }
    }
}

21. Security

Security Considerations

• API key validation: Never trust client-provided keys without validation. Use HMAC-signed keys.
• IP spoofing prevention: Rate limit by API key, not IP alone (IPs can be spoofed or shared).
• Key rotation: Support seamless API key rotation without losing rate limit state.
• Encryption: API keys in transit (TLS) and at rest (encrypted in Redis/DB).
• Audit logging: Log all rate limit violations for security analysis.

public class SecureApiKeyValidator
{
    private readonly byte[] _hmacKey;

    public bool ValidateKey(string apiKey)
    {
        if (string.IsNullOrEmpty(apiKey) || apiKey.Length < 32)
            return false;

        // Check format: prefix HMAC-SHA256 signature
        var parts = apiKey.Split('.');
        if (parts.Length != 2)
            return false;

        var prefix = parts[0];
        var signature = parts[1];

        using var hmac = new HMACSHA256(_hmacKey);
        var expectedSignature = Convert.ToBase64String(
            hmac.ComputeHash(Encoding.UTF8.GetBytes(prefix)));

        return CryptographicOperations.FixedTimeEquals(
            Encoding.UTF8.GetBytes(signature),
            Encoding.UTF8.GetBytes(expectedSignature));
    }
}

22. Observability

Key Metrics

Prometheus Configuration

scrape_configs:
  - job_name: 'rate-limiter'
    static_configs:
      - targets: ['rate-limiter:8080']
    metrics_path: /metrics
    scrape_interval: 15s

alerting:
  rules:
    - alert: HighRateLimitRejectionRate
      expr: rate(ratelimit_rejections_total[5m]) / rate(ratelimit_checks_total[5m]) > 0.1
      for: 5m
      labels:
        severity: warning
      annotations:
        summary: "High rate limit rejection rate"
        description: "Rejection rate is {{ $value | humanizePercentage }}"

    - alert: RateLimiterCircuitOpen
      expr: ratelimit_circuit_open_total > 0
      for: 1m
      labels:
        severity: critical
      annotations:
        summary: "Rate limiter circuit breaker is open"
        description: "Rate limiter is using local fallback. Redis may be down."

Distributed Tracing

public class TracedRateLimiter : IMultiTierRateLimiter
{
    private readonly IMultiTierRateLimiter _inner;
    private readonly Tracer _tracer;

    public async Task<RateLimitResult> CheckAsync(string apiKey, string endpoint)
    {
        using var span = _tracer.StartActiveSpan("rate_limit_check");
        span.SetAttribute("api_key", apiKey);
        span.SetAttribute("endpoint", endpoint);

        var sw = Stopwatch.StartNew();
        var result = await _inner.CheckAsync(apiKey, endpoint);
        sw.Stop();

        span.SetAttribute("ratelimit.allowed", result.Allowed);
        span.SetAttribute("ratelimit.remaining", result.Remaining);
        span.SetAttribute("ratelimit.latency_ms", sw.ElapsedMilliseconds);

        if (!result.Allowed)
            span.SetStatus(Status.Error.WithDescription("Rate limit exceeded"));

        return result;
    }
}

23. High Availability

Multi-Region Rate Limiting

Multi-Region Strategy

24. Performance

Latency Breakdown

Optimization Techniques

public class OptimizedRateLimiter
{
    // 1. Connection pooling - reuse Redis connections
    private readonly Lazy<IConnectionMultiplexer> _redis = new(() =>
        ConnectionMultiplexer.Connect(new ConfigurationOptions
        {
            EndPoints = { "redis:6379" },
            AbortOnConnectFail = false,
            ConnectTimeout = 100,
            SyncTimeout = 50,
            KeepAlive = 60,
            MaxAzureCacheClientsPerEndpoint = 20
        }));

    // 2. Pipeline multiple operations
    public async Task<List<RateLimitResult>> BatchCheckAsync(List<string> keys, int limit)
    {
        var db = _redis.Value.GetDatabase();
        var tasks = new List<Task>();

        // Pipeline all checks into a single round-trip
        var batch = db.CreateBatch();
        foreach (var key in keys)
        {
            tasks.Add(batch.ScriptEvaluateAsync(
                LuaScript,
                new RedisKey[] { $"rl:{key}" },
                new RedisValue[] { DateTimeOffset.UtcNow.ToUnixTimeMilliseconds(), 60000, limit }));
        }
        batch.Execute();
        await Task.WhenAll(tasks);

        return tasks.Select(t => ParseResult(((Task<RedisResult>)t).Result, limit)).ToList();
    }

    // 3. Async processing for non-critical path
    public void LogRateLimitEvent(string apiKey, bool allowed)
    {
        // Fire-and-forget analytics logging
        _ = Task.Run(async () =>
        {
            await _analyticsStore.LogAsync(new RateLimitEvent
            {
                ApiKey = apiKey,
                Allowed = allowed,
                Timestamp = DateTimeOffset.UtcNow
            });
        });
    }
}

25. Cost Analysis

Infrastructure Cost

26. Failure Scenarios

Hot Key Mitigation

public class HotKeyRateLimiter
{
    private readonly IMemoryCache _localCounters;
    private readonly RedisSlidingWindowRateLimiter _redisLimiter;

    public async Task<RateLimitResult> AllowAsync(string key, int limit, TimeSpan window)
    {
        // Check local counter first for potential hot keys
        var localKey = $"local:{key}";
        if (_localCounters.TryGetValue<int>(localKey, out var localCount))
        {
            // If local count is high, use local counting to avoid Redis overload
            if (localCount > 100)  // Threshold for "hot key"
            {
                return CheckLocal(key, limit, window);
            }
        }

        _localCounters.Set(localKey,
            _localCounters.Get<int>(localKey) + 1,
            TimeSpan.FromSeconds(5));

        return await _redisLimiter.CheckAsync(key, limit, window);
    }

    private RateLimitResult CheckLocal(string key, int limit, TimeSpan window)
    {
        // Local sliding window for hot keys
        // Trades accuracy for Redis protection
        var counter = _localCounters.GetOrCreate(key, _ =>
        {
            return new SlidingWindowCounter(limit, window);
        });

        return counter.Allow();
    }
}

27. Technology Choices (C# & Alternatives)

C# Implementation Stack

NuGet Packages

<PackageReference Include="StackExchange.Redis" Version="2.7.*" />
<PackageReference Include="Microsoft.Extensions.Caching.Memory" Version="8.0.*" />
<PackageReference Include="Npgsql.EntityFrameworkCore.PostgreSQL" Version="8.0.*" />
<PackageReference Include="Polly" Version="8.3.*" />
<PackageReference Include="prometheus-net" Version="8.2.*" />
<PackageReference Include="OpenTelemetry.Extensions.Hosting" Version="1.7.*" />

Alternative Implementations

28. Alternatives & Trade-offs

Build vs Buy

29. Real-World Case Studies

Stripe API Rate Limiting

• Strategy: Per-key limits with burst allowance. 100 requests/second for most endpoints.
• Headers: Returns RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset, Retry-After.
• Special handling: Write operations (charges, refunds) have stricter limits than reads.
• Lesson: Tiered limits based on endpoint cost, not just volume.

Twitter API Rate Limiting

• Strategy: Application-level and user-level limits. 15-minute sliding windows.
• Complexity: Different endpoints have wildly different limits (search: 450/15min, tweet: 300/15min).
• Lesson: Per-endpoint limits are essential for APIs with varying backend costs.

GitHub API Rate Limiting

• Strategy: 5000 requests/hour for authenticated users. Uses sliding window.
• Special features: Secondary rate limits for specific actions (e.g., creating issues).
• Lesson: Support both global and action-specific rate limits.

30. Interview Follow-ups

Common Deep-Dive Questions

31. Senior/Staff/Principal Engineering Discussion

Architectural Decisions

• Rate limiting at gateway vs service level: Gateway-level is simpler but less precise. Service-level allows per-endpoint customization. Recommendation: gateway for global limits, service for business-specific limits.
• Centralized vs distributed state: Centralized (Redis) is simpler but a single point of failure. Distributed (local + sync) is more complex but more resilient. Recommendation: start centralized, add distributed fallback.
• Accuracy requirements: For billing, you need exact counts (use database). For DDoS protection, approximate is fine (use Redis). For most APIs, sliding window counter (99% accurate) is sufficient.

Operational Considerations

• Capacity planning: Redis memory usage = 200 bytes × active_keys × window_count. For 1M keys with 3 windows: ~600MB.
• Monitoring dashboards: Rate limit hit rate, rejection rate by client tier, Redis latency, fallback activation count.
• Runbooks: Redis down procedure, hot key mitigation, config change rollout, circuit breaker tuning.
• Chaos engineering: Regularly kill Redis to test fail-open behavior. Simulate hot keys to test fallback.

32. Architecture Evolution

33. Key Takeaways

Interview Quick Reference

34. References & Further Reading

• Designing Data-Intensive Applications (Kleppmann, 2017) — Chapter on distributed systems
• Stripe API Rate Limiting Documentation — Real-world production rate limiting
• GitHub REST API Rate Limiting — Sliding window implementation
• Cloudflare Rate Limiting — Edge-based rate limiting at scale
• Redis Documentation: Sorted Sets — Implementation basis for sliding window log
• Token Bucket Algorithm (RFC 2697) — Original specification
• Leaky Bucket Algorithm (RFC 2698) — Traffic shaping specification
• Microsoft: Rate Limit Pattern — Azure architecture center guidance
• Polly Project — .NET resilience and circuit breaker library
• StackExchange.Redis — High-performance Redis client for .NET

35. Conclusion

Rate limiting is a deceptively simple concept with deep distributed systems implications. The core question — "how many requests has this client made in the last minute?" — requires careful consideration of algorithms (fixed window vs sliding window vs token bucket), coordination (centralized Redis vs local counters vs consensus), and failure modes (fail open vs fail closed).

The recommended approach for most production systems is a sliding window counter backed by Redis with Lua scripts. This gives ~99% accuracy, sub-3ms latency, and natural support for distributed coordination. Combined with a circuit breaker pattern, local fallback counters, and comprehensive observability, this design provides robust rate limiting that protects your backend services without becoming a bottleneck.

In your interview, start with the simplest solution (fixed window counter), then evolve to sliding window when the interviewer asks about the boundary problem. Discuss distributed coordination with Redis, then address failure modes with the circuit breaker pattern. This progressive deepening demonstrates both algorithmic knowledge and production awareness.

36. Rate Limiter Observability and Alerting

Rate limiting is invisible until it breaks. Comprehensive observability is essential for detecting misconfigurations, understanding traffic patterns, and identifying abuse. The monitoring system must track rejection rates, accuracy metrics, and per-client rate limit consumption in real-time.

public class RateLimiterMetrics
{
    private readonly IMetricsCollector _metrics;

    public void RecordRateLimitCheck(
        string clientId, string endpoint, bool allowed,
        long currentCount, long limit, double windowProgress)
    {
        var tags = new Dictionary<string, string>
        {
            ["client"] = clientId,
            ["endpoint"] = endpoint,
            ["result"] = allowed ? "allowed" : "rejected"
        };

        _metrics.IncrementCounter("rate_limit.checks", tags);
        _metrics.SetGauge("rate_limit.current_count", currentCount, tags);
        _metrics.SetGauge("rate_limit.utilization",
            (double)currentCount / limit, tags);

        if (!allowed)
        {
            _metrics.IncrementCounter("rate_limit.rejections", tags);
        }

        _metrics.RecordHistogram("rate_limit.check_latency_ms",
            GetCheckLatency(), tags);
    }

    public void RecordLimiterHealth(
        string node, bool isHealthy, double accuracy)
    {
        _metrics.SetGauge("rate_limit.health", isHealthy ? 1 : 0,
            new Dictionary<string, string> { ["node"] = node });
        _metrics.SetGauge("rate_limit.accuracy", accuracy,
            new Dictionary<string, string> { ["node"] = node });
    }
}

Key Rate Limiting Metrics