Understanding CAP Theorem through Distributed Rate Limiting
This article explains the CAP theorem (Consistency, Availability, Partition Tolerance) by demonstrating its practical implications in building a distributed rate limiter. It contrasts a naive in-memory approach with a more robust Redis-backed solution, highlighting the explicit trade-offs between consistency and availability in distributed systems during network partitions.
Read original on Dev.to #systemdesignThe CAP Theorem Explained
The CAP theorem states that a distributed data store can only guarantee two out of three properties during a network partition: Consistency, Availability, and Partition Tolerance. Partition Tolerance (P) is a given in any distributed system, meaning systems must continue to operate despite network failures that split the system into isolated sub-systems. Therefore, the core trade-off is between Consistency (C) and Availability (A).
- Consistency: Every read receives the most recent write or an error. All clients see the same data at the same time, regardless of which node they connect to.
- Availability: Every request receives a (non-error) response, without guarantee that the response contains the most recent write. The system remains operational and responsive.
- Partition Tolerance: The system continues to operate even if there are arbitrary losses of messages or temporary network failures between nodes.
CP vs. AP Systems
When a network partition occurs, a system must choose to prioritize either Consistency (CP) or Availability (AP):
- CP (Consistent & Partition Tolerant): In the event of a partition, the system will cease to take writes and may return errors on reads to guarantee that all data is consistent across the network. Operations might be blocked until the partition is resolved.
- AP (Available & Partition Tolerant): In the event of a partition, the system will continue to process requests, potentially returning stale or divergent data. The system remains responsive, but clients might see different states.
Applying CAP to Distributed Rate Limiting
The article uses the example of a distributed API rate limiter to illustrate the CAP theorem. A naive in-memory rate limiter on multiple service instances behind a load balancer inherently becomes an AP system by accident. Each instance maintains its own counter, leading to inconsistent rate limits where a user can exceed their quota by switching instances. This provides availability but sacrifices consistency.