Design a Rate Limiter

Java (Jedis) — Token bucket enforced atomically via Lua script

// Token Bucket in Redis via Lua script (Jedis)
// Lua executes atomically on Redis — no race conditions

private static final String TOKEN_BUCKET_SCRIPT = """
    local key        = KEYS[1]
    local capacity   = tonumber(ARGV[1])
    local refillRate = tonumber(ARGV[2])   -- tokens per second
    local now        = tonumber(ARGV[3])   -- current epoch seconds

    local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
    local tokens     = tonumber(bucket[1]) or capacity
    local lastRefill = tonumber(bucket[2]) or now

    -- Refill tokens proportional to elapsed time
    local elapsed = math.max(0, now - lastRefill)
    tokens = math.min(capacity, tokens + elapsed * refillRate)

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

    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / refillRate) + 10)

    return { allowed, math.floor(tokens) }
    """;

public RateLimitResult checkTokenBucket(Jedis jedis, String clientId,
                                         int capacity, int refillRate) {
    String key = "rl:tb:" + clientId;
    long now = Instant.now().getEpochSecond();

    List<Object> result = (List<Object>) jedis.eval(
        TOKEN_BUCKET_SCRIPT,
        List.of(key),
        List.of(String.valueOf(capacity),
                String.valueOf(refillRate),
                String.valueOf(now))
    );

    boolean allowed   = ((Long) result.get(0)) == 1L;
    long remaining    = (Long) result.get(1);
    return new RateLimitResult(allowed, remaining);
}

Java (Jedis) — Fixed window counter with automatic TTL cleanup

// Fixed Window Counter (Jedis)
public RateLimitResult checkFixedWindow(Jedis jedis, String clientId,
                                         int limit, int windowSeconds) {
    // Key includes the window start time, e.g. "rl:fw:user42:1710000060"
    long windowStart = (Instant.now().getEpochSecond() / windowSeconds) * windowSeconds;
    String key = "rl:fw:" + clientId + ":" + windowStart;

    // INCR is atomic — safe across multiple gateway nodes
    long count = jedis.incr(key);

    if (count == 1) {
        // First request in this window — set expiry
        jedis.expire(key, windowSeconds + 5); // +5s buffer for clock skew
    }

    boolean allowed  = count <= limit;
    long remaining   = Math.max(0, limit - count);
    long resetAt     = windowStart + windowSeconds;

    return new RateLimitResult(allowed, remaining, resetAt);
}

Java (Jedis) — Sliding window log with Redis sorted set

// Sliding Window Log via Redis ZSET + Lua (atomic)
private static final String SLIDING_LOG_SCRIPT = """
    local key     = KEYS[1]
    local now     = tonumber(ARGV[1])   -- current epoch milliseconds
    local window  = tonumber(ARGV[2])   -- window size in milliseconds
    local limit   = tonumber(ARGV[3])

    local cutoff  = now - window

    -- 1. Evict old entries
    redis.call('ZREMRANGEBYSCORE', key, '-inf', cutoff)

    -- 2. Count entries in window
    local count   = redis.call('ZCARD', key)

    local allowed = 0
    if count < limit then
        -- 3. Log this request (score = timestamp, member = unique request ID)
        redis.call('ZADD', key, now, now .. '-' .. math.random(1000000))
        redis.call('PEXPIRE', key, window + 1000)
        allowed = 1
        count   = count + 1
    end

    return { allowed, limit - count }
    """;

public RateLimitResult checkSlidingLog(Jedis jedis, String clientId,
                                        int limit, int windowMs) {
    String key = "rl:sl:" + clientId;
    long now   = Instant.now().toEpochMilli();

    List<Object> result = (List<Object>) jedis.eval(
        SLIDING_LOG_SCRIPT,
        List.of(key),
        List.of(String.valueOf(now),
                String.valueOf(windowMs),
                String.valueOf(limit))
    );

    boolean allowed = ((Long) result.get(0)) == 1L;
    long remaining  = (Long) result.get(1);
    return new RateLimitResult(allowed, remaining);
}

Java (Jedis) — Sliding window counter with weighted overlap approximation

// Sliding Window Counter — Lua script (Jedis)
private static final String SLIDING_COUNTER_SCRIPT = """
    local curr_key  = KEYS[1]   -- current window counter key
    local prev_key  = KEYS[2]   -- previous window counter key
    local limit     = tonumber(ARGV[1])
    local window    = tonumber(ARGV[2])  -- window size in seconds
    local now       = tonumber(ARGV[3])  -- current epoch seconds

    local window_start = math.floor(now / window) * window
    local elapsed      = now - window_start            -- seconds into current window
    local overlap      = (window - elapsed) / window   -- fraction of prev window still relevant

    local curr_count = tonumber(redis.call('GET', curr_key)) or 0
    local prev_count = tonumber(redis.call('GET', prev_key)) or 0

    local estimated  = prev_count * overlap + curr_count

    if estimated >= limit then
        return { 0, 0 }   -- rejected
    end

    -- Allow and increment current window counter
    local new_count  = redis.call('INCR', curr_key)
    if new_count == 1 then
        redis.call('EXPIRE', curr_key, window * 2)  -- survives one full extra window as "prev"
    end

    local remaining  = math.floor(limit - estimated - 1)
    return { 1, remaining }
    """;

public RateLimitResult checkSlidingCounter(Jedis jedis, String clientId,
                                            int limit, int windowSeconds) {
    long now          = Instant.now().getEpochSecond();
    long windowStart  = (now / windowSeconds) * windowSeconds;
    long prevStart    = windowStart - windowSeconds;

    String currKey = "rl:sc:" + clientId + ":" + windowStart;
    String prevKey = "rl:sc:" + clientId + ":" + prevStart;

    List<Object> result = (List<Object>) jedis.eval(
        SLIDING_COUNTER_SCRIPT,
        List.of(currKey, prevKey),
        List.of(String.valueOf(limit),
                String.valueOf(windowSeconds),
                String.valueOf(now))
    );

    boolean allowed = ((Long) result.get(0)) == 1L;
    long remaining  = (Long) result.get(1);
    return new RateLimitResult(allowed, remaining);
}

Java (Jedis) — Race condition illustration and Lua-based atomic fix

// Race condition demo: what NOT to do (non-atomic)
// Two threads can both read 49 and both increment to 50 — count exceeds limit
public boolean checkUnsafe(Jedis jedis, String key, int limit) {
    long count = Long.parseLong(jedis.get(key) != null ? jedis.get(key) : "0");
    if (count < limit) {
        jedis.incr(key);  // NOT atomic with the read above!
        return true;
    }
    return false;
}

// Correct: MULTI/EXEC with WATCH (optimistic locking — fragile under contention)
public boolean checkWithWatch(Jedis jedis, String key, int limit) {
    jedis.watch(key);
    long count = Long.parseLong(jedis.get(key) != null ? jedis.get(key) : "0");
    if (count >= limit) {
        jedis.unwatch();
        return false;
    }
    Transaction tx = jedis.multi();
    tx.incr(key);
    tx.expire(key, 60);
    List<Object> result = tx.exec();
    // result is null if another client modified key between WATCH and EXEC
    return result != null;
}

// Best: Lua script — single atomic operation, no retries needed
private static final String ATOMIC_INCR_SCRIPT = """
    local key    = KEYS[1]
    local limit  = tonumber(ARGV[1])
    local window = tonumber(ARGV[2])

    local count  = redis.call('INCR', key)
    if count == 1 then
        redis.call('EXPIRE', key, window)
    end
    if count > limit then
        return 0   -- rejected
    end
    return limit - count  -- remaining
    """;

public RateLimitResult checkAtomic(Jedis jedis, String clientId,
                                    int limit, int windowSeconds) {
    String key   = "rl:fw:" + clientId + ":" +
                   (Instant.now().getEpochSecond() / windowSeconds);
    long result  = (Long) jedis.eval(
        ATOMIC_INCR_SCRIPT,
        List.of(key),
        List.of(String.valueOf(limit), String.valueOf(windowSeconds))
    );
    boolean allowed   = result >= 0;
    long remaining    = Math.max(0, result);
    return new RateLimitResult(allowed, remaining);
}