System Design Algorithms
Algorithms overview
System design is full of named tools: Raft, quorums, hashing rings, gossip, Bloom filters. This shelf gathers those tools so you can learn each one clearly, then use it inside a larger design.
Think of pattern notes (Leader Election, Replication, CAP) as the story: when you need something and what can go wrong. Think of this Algorithms section as the toolbox: how the named algorithm actually works.
Try it: pick an algorithm tool and check its invariant
This overview lab is a switchboard for the Algorithms shelf. Tune quorum math, watch how many keys move when a ring node joins, probe a Bloom filter, or compare vector clocks.
- Tool
- quorum
- Quorum safe
- yes
- Keys remapped (+D)
- 2/4
- Clock relation
- concurrent
Quorum overlap
R+W>NSafe when every read set intersects every write set. That is the formula behind “majority” stories.
Ring remap
~1/NMembership change should move a slice of keys, not reshuffle the whole keyspace like naive modulo.
Maybe vs no
hintsBloom negatives are certain; positives need a store check. Concurrent clocks need an application merge rule.
Pick a toolbox item. Quorum, hashing rings, Bloom filters, and vector clocks show up inside larger designs—practice the core rule of each here.
Use the linked notes for depth. Each tool below has a dedicated topic. Here you only verify the one rule you must recite in an interview before drawing the larger box diagram.
How to use this shelf
1. Start from a problem
Begin with the behavior the product must preserve. For a job scheduler, two workers must not both perform an exclusive action after a network partition. That requirement leads to leader election or coordination; a membership list that merely says which nodes appear healthy is insufficient. Writing the failure scenario first prevents choosing an algorithm just because its name is familiar.
2. Open the algorithm
Read each algorithm as a small protocol: identify the participants, the information each participant keeps, the messages exchanged, and the condition for returning success. In a quorum example, name the three replicas, show which two acknowledged a write, and then choose two replicas for a read. Tracing concrete participants makes the overlap argument easier to understand than memorizing a formula.
3. Go back to the design
Return to the design and connect the algorithm’s guarantee to the operation that matters. An elected scheduler can still pause, lose its lease, and later resume an old job. A fencing token checked by the storage system prevents that stale worker from changing protected data. Also decide how retries are identified, how long failures may block users, and which state survives a restart.
Browse by algorithm
Choose a lesson by the question you need to answer. Consensus and quorums concern agreement; gossip concerns spreading information; vector clocks concern causal relationships; hashing and spatial indexes concern placement or retrieval; Bloom filters concern inexpensive approximate membership. These guarantees are different, so replacing one with another requires explaining which behavior the product can give up.
Consensus (Raft / Paxos)
How a group of machines agrees on one next fact, even when some crash or messages are late.
Use when: You need one ordered history (a log) that every healthy replica will eventually share.
Quorum
The “majority must agree” math behind safe reads and writes.
Use when: You want committed data to survive node loss without two sides inventing different truths.
Consistent hashing
A ring that maps keys to servers so adding or removing a server moves only a small slice of keys.
Use when: You shard caches or data across machines and hate reshuffling the whole keyspace on every scale-out.
Gossip
Each node tells a few peers what it knows; rumors of membership and state spread like a social network.
Use when: You need membership or lightweight state to spread without one boss broadcasting to everyone.
Bloom filters
A tiny “maybe / no” membership check. “No” is certain. “Maybe” means check the real store.
Use when: You want to skip expensive lookups for keys that are definitely absent, and you can tolerate rare false maybes.
Vector clocks
Version stamps that show whether two updates happened one-after-another or at the same time.
Use when: Several writers can change the same object and you must detect conflicts without one global clock.
Unique ID generation
Ways many machines mint IDs that never collide, often roughly sorted by time.
Use when: You need IDs at high rate across hosts without a single central counter becoming a bottleneck.
Proximity search
Indexes and encodings that find “near me” points without scanning the whole map.
Use when: Queries ask for nearby drivers, places, or devices, not one-dimensional ranges like age or price.
A common path: Leader Election → Raft
A term is an election generation, a candidate is a node requesting votes, and a majority is more than half the configured voters. Two majorities intersect, but that fact prevents two winners in one term only because each voter durably votes at most once per term. Preserving committed data across later terms also requires rules about candidate log freshness. Work through both rules before treating “majority” as a complete safety argument.
Suggested order: Leader Election → Consensus (Raft / Paxos) → Quorum.
Wrap-up
Patterns tell you what problem you are solving. Algorithms tell you which named tool fits. Use this shelf to deepen one tool at a time, then return to the design that needs it.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Use the Algorithms shelf as the catalog for consensus, quorum, hashing, gossip, Bloom filters, vector clocks, IDs, and proximity search.
Explain the decision
When do you open Algorithms vs Leader Election?
Read the reasoning
Leader Election for when/why/fencing; Algorithms for protocol mechanics such as Raft log rules or quorum overlap math.
Apply it to a production scenario
A design mentions Raft terms and majority votes. Where do you deepen?
Read one approach
Start from Leader Election or Replication, then follow the Algorithms overview into Consensus and Quorum notes.
Work through the numbers
Why keep algorithm URLs stable when moving sidebar sections?
Read the worked calculation
Roadmaps and embeds store note paths; moving only navigation parents avoids broken links.
Reason through a failure
What goes wrong if topic notes duplicate full Raft?
Read the recovery reasoning
Two sources of truth drift; keep sketches on pattern pages and depth on algorithm pages.
Sources and further study
Continue with Consensus Algorithms.