Building an AP Rate Limiter with CAP Theorem Considerations

Understanding CAP Theorem for Distributed Systems

The CAP theorem states that a distributed data store can only simultaneously guarantee two out of three properties: Consistency, Availability, and Partition tolerance. In real-world distributed systems, network partitions are inevitable, making Partition tolerance (P) a mandatory choice. This forces a decision between Consistency (C) and Availability (A).

Consistency vs. Availability in Rate Limiting

For a rate limiter, choosing Consistency (CP system) means ensuring every node sees the exact same request count. This guarantees no user ever exceeds their limit, but during a network partition, the system might reject legitimate requests to maintain consistency. Conversely, choosing Availability (AP system) prioritizes keeping the system operational, even if it means a slight over-limit during a partition, with eventual reconciliation of counts once the partition heals. The article argues that for many user-facing APIs, temporary over-limits are less impactful than rejecting valid users.

Designing an AP Rate Limiter with Redis

A common approach for an AP rate limiter involves using a shared, eventually consistent store like Redis. Each application node increments a counter in Redis, and if Redis is unreachable due to a network partition, the system defaults to allowing the request to maintain availability. This trades strong consistency for eventual consistency, where all nodes eventually converge on the correct count when network issues resolve.

package ratelimit
import (
	"context"
	"time"
	"github.com/go-redis/redis/v8"
)
var lua = redis.NewScript(` local current = redis.call("INCR", KEYS[1]) if current == 1 then redis.call("EXPIRE", KEYS[1], ARGV[2]) end return current `)
type Limiter struct {
	client *redis.Client
	limit  int
	window time.Duration
}
func NewLimiter(client *redis.Client, limit int, window time.Duration) *Limiter {
	return &Limiter{client: client, limit: limit, window: window}
}
func (l *Limiter) Allow(ctx context.Context, key string) (bool, error) {
	now := time.Now()
	expire := int(l.window.Seconds())
	count, err := lua.Run(ctx, l.client, []string{key}, 1, expire).Int()
	if err != nil {
		// Redis down 	return true, err
	}
	return count <= l.limit, nil
}

• Atomicity: Redis Lua scripts ensure `INCR` and `EXPIRE` operations are atomic, preventing race conditions.
• Partition Tolerance: If Redis is unavailable, the fallback allows requests, ensuring the system remains responsive.
• Eventual Consistency: Counters converge across nodes once network partitions are resolved.