Key Distributed System Concepts: Bloom Filter, Consistent Hashing, Quorum, Leader/Follower, and More

1. Bloom Filter

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

2. Consistent Hashing

Consistent hashing enables easy scaling by mapping data items to positions on a ring and assigning them to the next clockwise node, providing incremental stability where only neighboring nodes are affected by joins or leaves.

3. Quorum

In distributed environments, a quorum is the minimum number of servers that must successfully complete an operation before it is considered successful, used in Cassandra writes, Paxos leader election, and Dynamo’s relaxed quorum.

4. Leader and Follower

Leader/follower replication provides fault tolerance by electing a single leader to make decisions and propagate them to followers; election occurs at server startup and must succeed before the cluster accepts client requests.

5. Heartbeat

Heartbeat mechanisms detect leader failures so that a new leader election can be triggered promptly.

6. Fencing

Fencing prevents a failed leader that may still be active from accessing cluster resources, using either resource fencing or node fencing techniques.

7. Write‑Ahead Log (WAL)

WAL records operation summaries before they are applied to disk, enabling recovery after crashes by replaying the log.

8. Segment Log

Segmented logs split a large log file into smaller files to avoid performance bottlenecks and simplify cleanup.

9. High‑Water Mark

The high‑water mark tracks the last log entry replicated to a quorum of followers; systems like Kafka expose only entries up to this mark.

10. Lease

A lease acts like a lock with a limited lifetime; clients must renew it before expiration, as used in Chubby sessions.

11. Gossip Protocol

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

12. Phi Accrual Failure Detection

This algorithm adapts its suspicion threshold based on historical heartbeat intervals; Cassandra uses it to assess node health.

13. Split‑Brain

Split‑brain occurs when multiple leaders are active; generation clocks (monotonically increasing numbers) help resolve which leader is authoritative.

14. Checksum

Checksums (e.g., MD5, SHA‑256) verify data integrity during transfer between components; systems like HDFS and Chubby store checksums alongside data.

15. CAP Theorem

CAP states that a distributed system can provide at most two of Consistency, Availability, and Partition tolerance; Dynamo is AP, BigTable is CP.

16. PACELC Theorem

PACELC extends CAP by adding latency vs. consistency trade‑offs when there is no partition.

17. Hinted Handoff

If a node is down, the leader stores hints for missed requests; once the node recovers, the leader forwards the stored writes.

18. Read‑Repair

During reads, stale replicas are identified and updated with the latest version, as used by Cassandra and Dynamo.

19. Merkle Trees

Merkle trees are hash‑based binary trees that enable efficient comparison of large data sets; Dynamo uses them for anti‑entropy and conflict resolution.