19 Essential Distributed System Design Patterns You Must Know

1. Bloom Filter

Bloom filter is a space‑efficient probabilistic data structure used to test whether an element is a member of a set, useful when only membership checks are needed.

In BigTable (and Cassandra), every read must fetch data from SSTables that compose a tablet; if SSTables are not in memory, many disk accesses may be required. Bloom filters reduce these disk reads.

2. Consistent Hashing

Consistent hashing enables easy scaling and efficient data replication, improving availability and fault tolerance.

Keys are hashed to positions on a ring; traversing clockwise finds the first node with a position greater than the key, assigning the data item to that node. Only the immediate neighbors are affected when nodes join or leave.

3. Quorum

In a distributed environment, a quorum is the minimum number of servers that must successfully complete an operation before it is considered successful.

In Cassandra, a write can be configured to succeed only after being written to at least one quorum (or majority) replica. Leader election in Chubby uses Paxos, which also relies on quorum for strong consistency.

Dynamo uses a relaxed quorum for writes, while reads and writes are performed on the first healthy node in the preference list, which may not be the first node encountered in the consistent‑hash ring.

4. Leader and Follower

To achieve fault tolerance, data is replicated across multiple servers. One server is elected as the leader, which makes decisions for the cluster and propagates them to followers.

In a three‑to‑five‑node cluster, leader election occurs internally at startup; the system does not accept client requests until a leader is elected.

5. Heartbeat

The heartbeat mechanism detects whether the current leader has failed, allowing a new leader election to be triggered.

6. Fencing

When a leader fails, it is impossible to know whether it has truly stopped. Fencing prevents a previously active leader from accessing cluster resources.

Resource fencing: the system blocks the former leader from accessing essential resources.

Node fencing: the system cuts off all resources to the former leader, often by powering off or resetting the node.

7. Write‑Ahead Log (WAL)

WAL records operations in a log before they are applied to disk, inspired by database systems, ensuring consistency after crashes by replaying the log.

8. Segmented Log

Logs are split into multiple smaller files (segments) instead of a single large file, facilitating easier management, cleanup, and avoiding performance bottlenecks.

9. High‑Water Mark

The high‑water mark tracks the last log entry on the leader that has been successfully replicated to a quorum of followers; the leader only exposes data up to this index.

Kafka uses the high‑water mark to ensure consumers see only committed messages.

10. Lease

A lease acts like a lock with an expiration time; clients request a lease for a limited period and can renew it before it expires. Chubby clients hold time‑bounded session leases with the leader.

11. Gossip Protocol

Gossip is a peer‑to‑peer communication mechanism where nodes periodically exchange state information about themselves and known peers.

Each node initiates a gossip round each second, selecting a random peer to exchange state.

12. Phi Accrual Failure Detection

This algorithm adapts its failure detection threshold based on historical signal information, outputting a suspicion level rather than a binary up/down status.

Cassandra uses the Phi detector to assess node health.

13. Split‑Brain

A split‑brain occurs when a distributed system has two or more active leaders.

Generation clocks (monotonically increasing numbers) help resolve split‑brain by allowing nodes to trust the leader with the highest generation number.

Kafka uses epoch numbers; HDFS uses ZooKeeper to ensure a single active NameNode.

14. Checksum

Checksums detect data corruption when moving data between components. A cryptographic hash (MD5, SHA‑1, SHA‑256, SHA‑512) is computed and stored with the data; upon retrieval, the checksum is recomputed and compared.

HDFS and Chubby store checksums alongside each file.

15. CAP Theorem

The CAP theorem states that a distributed system cannot simultaneously provide Consistency, Availability, and Partition tolerance; it must choose two.

Dynamo is an AP system (high availability, weak consistency); BigTable is a CP system (strong consistency, partition tolerance).

16. PACELC Theorem

PACELC extends CAP: during a partition (P) the system trades Availability vs. Consistency (A vs. C); otherwise (E) it trades Latency vs. Consistency (L vs. C).

If a partition occurs, choose between availability and consistency.

When no partition, choose between latency and consistency.

17. Hinted Handoff

If a node is down, the system stores hints (annotations) for missed requests. When the node recovers, the leader forwards the stored hints to it.

18. Read Repair

During reads, the system detects stale replicas and repairs them by pushing the latest version to outdated nodes. Cassandra and Dynamo use read repair to achieve consistency.

19. Merkle Trees

Merkle trees are hash‑based binary trees used to compare large data sets efficiently. Each internal node hashes its two children; leaf nodes hash data chunks.

To compare replicas, first compare root hashes; if they differ, recursively compare child hashes.