Phase 4: Distributed Systems
Explore the concepts of Distributed Systems.
Consistency Models
A consistency model is the contract a distributed data store makes about when and in what order writes become visible to reads. Strong, eventual, and causal consistency are three common models that trade freshness guarantees against latency and availability. 🧠 Mental model: Strong consistency = a shared Google Doc where every keystroke appears instantly for everyone. Eventual consistency = sending a group text - everyone gets the message, but not at the exact same millisecond.
CAP Theorem
The CAP theorem states that a distributed data store can provide at most two of three guarantees at the same time: consistency, availability, and partition tolerance. Because network partitions are unavoidable in any real distributed system, the practical meaning of CAP is a forced choice between consistency and availability whenever a partition occurs. 🧠 Mental model: Imagine two bank branches during a phone outage (partition). CP = both branches refuse transactions to avoid giving out wrong balances. AP = both branches keep serving customers, knowing the balances might briefly disagree.
PACELC Theorem
The PACELC theorem extends the CAP theorem by describing the trade-off a distributed system makes even when the network is healthy. It reads: if there is a Partition (P), choose between Availability (A) and Consistency (C); Else (E), when the system runs normally, choose between Latency (L) and Consistency (C). 🧠 Mental model: CAP only asks "what do you do during a fire drill?" PACELC also asks "what do you do on a normal day?" - because even without a fire, you still choose between speed and double-checking everything.
Consistent Hashing
Consistent hashing is a technique for distributing keys across a changing set of nodes so that adding or removing a node remaps only a small fraction of keys instead of nearly all of them. It maps both keys and nodes onto the same circular hash space and assigns each key to the next node found clockwise. 🧠 Mental model: Musical chairs where removing one chair only displaces the person in that seat - everyone else stays put. Compare that to normal chairs-in-a-row, where removing one shifts everyone down.
Distributed Consensus (Paxos/Raft)
Distributed consensus is the process by which a cluster of machines agrees on a single value or state, even if some of the machines crash or the network drops messages. It is the hardest problem in distributed systems and the foundation of strongly consistent stores. Paxos and Raft are the two dominant algorithms used to achieve it. 🧠 Mental model: Imagine a committee of 5 people trying to agree on what to order for lunch while they are in different rooms, communicating only by passing notes. Some notes get lost, and some people fall asleep. Consensus algorithms ensure that once a majority agrees on "Pizza," no one will ever be told the lunch is "Sushi," no matter what happens.
Leader Election
Leader election is the process by which a group of distributed nodes picks exactly one node to act as the coordinator - the leader - for some task, such as writing to a partition, scheduling work, or making decisions on behalf of the group. When the current leader fails, the remaining nodes detect the failure and elect a new one. 🧠 Mental model: Think of it like a substitute teacher protocol. When the teacher (leader) doesn't show up, the class (cluster) follows a pre-agreed rule to pick who takes charge - and if that substitute also leaves, they pick another, without chaos.
Distributed Locks
A distributed lock lets multiple processes on different machines agree that only one of them may act on a shared resource at a time. Unlike an in-process mutex, it must survive crashes, network delays, and the reality that the lock holder might freeze at the worst possible moment - so correct designs use expiring leases and fencing tokens, not just a flag in a shared store. 🧠 Mental model: A distributed lock is the single key to a meeting room in a building with unreliable phones. You must be able to reclaim the key if someone walks off with it (a lease that expires), and the door must reject an old key after the locks are changed (a fencing token), so a forgetful ex-holder can't wander back in.
Gossip Protocol
A gossip protocol (or epidemic protocol) is a decentralized communication method where nodes in a distributed system randomly share information with a few peers at regular intervals. Like a rumor spreading through a crowd, the information propagates exponentially fast until all nodes agree on the cluster state, without needing a central coordinator. 🧠 Mental model: Imagine an office where every hour, each person chats by the water cooler with two random coworkers and shares the latest news. Within a few hours, everyone in the 100-person office knows the news, even though no single person made an office-wide announcement.
Vector Clocks & Logical Clocks
In a distributed system there is no single global clock, so you cannot trust wall-clock timestamps to tell you the true order of events across machines. Logical clocks - Lamport timestamps and vector clocks - order events by causality instead of by time, and hybrid approaches (HLC, Google's TrueTime) combine physical and logical time to get the best of both. 🧠 Mental model: Imagine two people writing letters back and forth, each dated by their own wristwatch. If the watches disagree, the dates lie about who replied to whom. To reconstruct the true conversation, you track "this letter is a reply to that one" (causality) rather than trusting the printed dates.
Quorum
In a distributed system, a quorum is the minimum number of nodes that must agree on an operation (like a read or a write) for it to be considered successful. Quorums are the mechanism used to guarantee consistency in replicated data stores, ensuring that reading data will always return the most recent write. 🧠 Mental model: Imagine a 5-person committee. If a new rule requires 3 votes to pass (a write quorum), and someone wants to know the latest rule, they only need to ask 3 people (a read quorum). Because 3+3=6, and there are only 5 people, they are mathematically guaranteed to speak to at least one person who voted on the newest rule.
Idempotency
An operation is idempotent when performing it multiple times has the same effect as performing it once. In distributed systems, idempotency is what makes retries safe, so that a client or broker can resend a request after a timeout without causing duplicate side effects such as a double charge. 🧠 Mental model: An elevator button is idempotent - pressing it 10 times has the same effect as pressing it once. A vending machine button is not - pressing it 10 times gives you 10 sodas (and a big bill).
Distributed Transactions (2PC/Saga)
A distributed transaction coordinates a single logical change across multiple services or databases so the work either fully completes or fully unwinds. Two-phase commit enforces this with a coordinator that locks participants until all agree, while the Saga pattern breaks the work into local steps with compensating actions that undo prior steps on failure. 🧠 Mental model: 2PC is like a wedding - the officiant asks both parties "do you?" and only pronounces them married if both say yes. A Saga is like a trip booked step by step - book the flight, then the hotel; if the hotel is full, cancel the flight.
Probabilistic Data Structures
Probabilistic data structures answer set-membership and cardinality questions using far less memory than exact structures, in exchange for a bounded, tunable error rate. The Bloom filter is the canonical example: it can report that an item is possibly present or definitely absent, meaning it may return false positives but never false negatives. 🧠 Mental model: A Bloom filter is like a bouncer with a guest list written in smudgy ink. He can definitely tell you "you are NOT on the list," but sometimes says "I think you might be on the list" when you're not (false positive).
Unique ID Generation
Distributed ID generation is the problem of handing out unique identifiers across many servers without a single bottleneck and, ideally, keeping them roughly time-sortable. It sounds trivial until you need billions of IDs per day, no collisions, no central chokepoint, and IDs that sort by creation time for efficient indexing. 🧠 Mental model: A single ticket counter at a deli hands out numbers in perfect order but jams when the line is long (one machine, one bottleneck). Distributed ID generation is like giving every counter its own numbered block so they never collide and customers can still tell who arrived first.
Merkle Trees (Anti-Entropy)
A Merkle Tree (or Hash Tree) is a data structure used in distributed systems to efficiently verify data integrity and detect inconsistencies between replicas. Instead of sending raw data over the network to compare databases, nodes exchange and compare tree nodes containing hashes, minimizing bandwidth usage. 🧠 Mental model: Imagine two giant encyclopedias. To find a single typo, you don't read the whole thing word by word to each other over the phone. Instead, you compare a hash of the entire book. If it differs, you compare hashes of the volumes, then the chapters, then the pages, quickly zooming in on the exact typo using a process of elimination.