Key Distributed System Design Patterns and Concepts

1. Bloom Filter A Bloom filter is a space‑efficient probabilistic data structure used to test whether an element is a member of a set, commonly employed in systems like BigTable and Cassandra to reduce disk reads.

2. Consistent Hashing Consistent hashing enables easy scaling by distributing data across nodes on a hash ring, allowing minimal data movement when nodes join or leave, thus improving availability and fault tolerance.

3. Quorum In a distributed environment, a quorum is the minimum number of servers that must successfully complete an operation before it is considered committed, ensuring stronger consistency.

4. Leader and Follower Leader‑follower replication copies data across multiple servers; the leader makes decisions and propagates them to followers, providing fault tolerance.

5. Heartbeat Heartbeat mechanisms detect leader failures, triggering new leader elections when necessary.

6. Fencing Fencing prevents a previously active leader from accessing cluster resources after it has failed, avoiding split‑brain scenarios.

7. Write‑Ahead Log (WAL) WAL records operations before they are applied to disk, ensuring recoverability after crashes, a technique borrowed from database systems.

8. Segmented Log Instead of a single large log file, logs are split into smaller segments to improve performance and simplify cleanup.

9. High‑Water Mark The high‑water mark tracks the last log entry replicated to a quorum of followers, defining the data that the leader can safely expose.

10. Lease A lease acts like a lock with an expiration time; clients must renew it before it expires to retain access.

11. Gossip Protocol Gossip is a peer‑to‑peer communication mechanism where nodes periodically exchange state information about themselves and others.

12. Phi Accrual Failure Detection This algorithm adapts its suspicion threshold based on historical heartbeat data, providing a probabilistic view of node health.

13. Split‑Brain Split‑brain occurs when multiple leaders are active simultaneously; generation clocks or epoch numbers help resolve which leader is authoritative.

14. Checksum Checksums verify data integrity during transfer; systems store the checksum alongside data and recompute it on reads.

15. CAP Theorem CAP states that a distributed system can provide at most two of Consistency, Availability, and Partition tolerance; systems choose CA, CP, or AP trade‑offs.

16. PACELC Theorem Extends CAP by adding a trade‑off between Latency and Consistency when there is no partition.

17. Hinted Handoff When a node is down, other nodes store hints for missed writes and replay them once the node recovers.

18. Read‑Repair During reads, stale replicas are identified and updated with the latest version, ensuring eventual consistency.

19. Merkle Trees Merkle trees are hash‑based binary trees that enable efficient comparison of large data sets by comparing root hashes and recursing only on differing branches.

These patterns collectively address scalability, consistency, fault detection, and recovery in modern distributed systems.