System Design Essentials - Distributed Systems & Scalability Patterns

States that a distributed system can guarantee at most two of three properties simultaneously during a network partition: Consistency ($C$), Availability ($A$), and Partition Tolerance ($P$). Since network partitions ($P$) are inevitable in distributed systems, architects must trade off between $CP$ (consistency over availability) and $AP$ (availability over consistency).

An extension of the CAP theorem. States that If there is a Partition ($P$), trade off Availability ($A$) vs Consistency ($C$); Else ($E$), trade off Latency ($L$) vs Consistency ($C$).

A distributed hashing technique where keys and nodes are mapped onto a logical 360-degree ring using a hash function. Minimizes key remapping when scaling nodes up or down to only $O(K/n)$ keys on average, where $K$ is the number of keys and $n$ is the number of nodes.

To prevent uneven data distribution ('hotspots') and non-uniform node capacity in consistent hashing, each physical node is assigned multiple virtual nodes across the hash ring. This ensures a uniform hash distribution and better load balance.

An algorithm that allows traffic bursts up to a fixed bucket capacity $B$. Tokens are added at a constant fill rate $r$ tokens/sec. A request consumes a token to pass; if no tokens remain, the request is dropped or delayed.

Requests enter a FIFO queue (the bucket) of capacity $b$ and are processed at a smooth, constant output rate $r$. If the queue overflows, incoming requests are dropped.

The application directly interacts with both the cache and database. On read, the app checks the cache; on a cache miss, it reads from the DB, writes the result to the cache, and returns it.

Data is written to the cache and the backing database synchronously in a single transaction before returning success to the caller.