System Atlas
the atlas

Algorithms for system design

The handful of algorithms and data structures that keep showing up inside real distributed systems.

the gist

Behind the boxes of a system diagram sit a small set of recurring algorithms: consistent hashing for sharding, bloom filters for cheap membership tests, quadtrees and geohashes for nearby search, token and leaky buckets for rate limiting, HyperLogLog for counting uniques, Raft/Paxos for consensus, tries for autocomplete, and Merkle trees for integrity. Each one exists to make a specific hard problem cheap enough to solve at scale.

ANALOGY // These algorithms are the specialized hand tools inside a workshop — you don't invent a new saw for every cut, you reach for the one shaped for consistent hashing, membership, geospatial search, or rate limiting.
living diagram01 / 08
Each layer is an algorithm and the system-design problem it makes cheap
01
Consistent hashing
sharding · rebalancing
02
Bloom filter
probabilistic membership
03
Quadtree & geohash
nearby / geospatial search
04
Leaky & token bucket
rate limiting
05
HyperLogLog
cardinality estimation
06
Raft / Paxos
consensus & replication
07
Trie
autocomplete / prefix search
08
Merkle tree
integrity · anti-entropy
01

Consistent hashing

The problem is sharding: given N servers, which one owns a key? Plain modulo hashing (key mod N) reshuffles almost every key the moment N changes, which is catastrophic when you add or lose a node. Consistent hashing maps both keys and nodes onto a ring so that adding or removing a node only relocates the keys between it and its neighbor — a small, bounded fraction of the data.

02

Bloom filter

The problem is fast membership on a huge set without storing the set. A bloom filter hashes each item to several bits in a bitmap; to test membership it checks those bits. It can say 'definitely not present' with certainty or 'possibly present' with a tunable false-positive rate, in a tiny fixed space. Databases and caches use it to skip disk lookups for keys that surely don't exist.

03

Quadtree & geohash

The problem is geospatial search: 'find the drivers near me'. A quadtree recursively splits a map into four quadrants, so dense areas subdivide further and a query only walks the relevant cells. A geohash instead encodes latitude and longitude into a short string where shared prefixes mean physical proximity, turning 'nearby' into a cheap prefix range scan on an ordinary index.

04

Leaky bucket & token bucket

The problem is rate limiting: cap how fast a client may act. A leaky bucket drains requests at a fixed rate and overflows when the queue is full, enforcing a perfectly smooth output. A token bucket refills tokens at a steady rate and lets a caller spend saved-up tokens, allowing short bursts while bounding the long-run average. Most APIs choose token bucket for its friendlier burst behavior.

05

HyperLogLog

The problem is cardinality: how many distinct users visited today? Storing every unique ID to count them exactly costs gigabytes. HyperLogLog watches the pattern of leading zeros in hashed values — rare long runs of zeros imply many distinct items — and estimates the count within a percent or two using only kilobytes. It's how systems report unique visitors or distinct search terms at scale.

06

Raft / Paxos consensus

The problem is agreement: many replicas must decide on one value (a leader, the next log entry) despite crashes and network delays. Consensus algorithms like Paxos and the more understandable Raft elect a leader and replicate an ordered log to a majority quorum, so the cluster stays consistent as long as most nodes are alive. They are the backbone of etcd, ZooKeeper, and every strongly-consistent datastore.

07

Trie (prefix tree)

The problem is autocomplete and prefix search. A trie stores strings as a tree of characters where every path from the root spells a prefix, so finding all words starting with 'sys' is just walking to that node and reading its subtree. Lookups cost time proportional to the length of the query, not the size of the dictionary, which is what makes search-as-you-type feel instant.

08

Merkle tree

The problem is comparing or verifying large data cheaply. A Merkle tree hashes data blocks at the leaves and hashes pairs of hashes up to a single root. If two replicas have the same root hash, their data is identical; if not, you descend only the branches whose hashes differ to pinpoint the exact block. This anti-entropy trick powers Git, Bitcoin, and Dynamo-style replica repair.

the full picture
01

Why a systems engineer needs algorithms

System design and algorithms are usually taught as separate subjects — one is about boxes and arrows, the other about Big-O on a whiteboard — but real distributed systems are held together by a surprisingly small set of clever data structures. When you draw a load balancer, a cache, a geo-search service, or a rate limiter, each of those boxes is only feasible because someone found an algorithm that makes an otherwise impossible problem cheap.

The pattern is always the same: a naive approach is correct but does not scale (store every unique ID to count them, rehash every key when a server joins, scan every row to find nearby points), and a specialized algorithm trades a little exactness or a little complexity for an enormous win in memory, latency, or coordination cost. Knowing this toolbox is what lets you answer the follow-up question in a design interview — not just "put a cache here" but "how does that cache decide it doesn't need to hit disk?" The answer is a bloom filter, and that specificity is what separates a memorized diagram from real understanding.

02

Distributing data: consistent hashing

The first hard problem in any horizontally scaled system is placement: with N servers, which one holds a given key? The obvious answer, hash(key) % N, works until N changes. Add or remove a single node and the modulus shifts, so almost every key now maps somewhere new — a near-total reshuffle that would move terabytes and blow away every cache at once.

Consistent hashing fixes this by placing both nodes and keys on an abstract ring (the output space of the hash). A key belongs to the first node found clockwise from it. When a node joins or leaves, only the keys sitting between it and its neighbor move; every other key stays put. To keep the load even and avoid one node owning a huge arc, each physical node is placed at many points on the ring using virtual nodes. This single idea underpins distributed caches like Memcached clients, databases like Cassandra and DynamoDB, and any system that must rebalance gracefully rather than catastrophically.

03

Cheap answers: bloom filters and HyperLogLog

Two problems look similar — questions about a huge set — and both are solved by giving up exactness for tiny memory.

A bloom filter answers "is this item in the set?" using a bit array and several hash functions. Adding an item sets a few bits; testing an item checks those bits. If any is unset the item is *definitely absent*; if all are set it is *probably present*, with a false-positive rate you tune by sizing the array. Because it never says "absent" wrongly, a storage engine can consult a bloom filter before touching disk: a negative answer means the key truly isn't there, so the expensive lookup is skipped entirely. LSM-tree databases and CDNs lean on this constantly.

HyperLogLog answers a different question — "how many *distinct* items?" — without storing them. It exploits a statistical fact: in a stream of hashed values, the more distinct items you see, the more likely you are to have seen a hash with many leading zeros. By tracking the longest run of leading zeros across buckets, it estimates cardinality within roughly 1-2% error using only kilobytes, where exact counting would need gigabytes. It is how analytics systems report "unique visitors" at web scale.

04

Location, order, and prefixes

Some problems are about the shape of the data rather than its size.

  • Geospatial search ("find drivers near me") is hard because latitude and longitude are two dimensions and ordinary indexes are one-dimensional. A quadtree recursively splits the map into four quadrants, subdividing only where points are dense, so a proximity query walks just the relevant cells. A geohash takes a complementary approach: it interleaves the bits of latitude and longitude into a short string where a shared prefix means physical closeness, turning "nearby" into a cheap prefix range scan on a normal B-tree index.
  • Autocomplete is a prefix problem, and the natural structure is a trie: a tree where each edge is a character and each root-to-node path spells a prefix. Finding every completion of "sys" means walking to that node and reading its subtree, at a cost proportional to the query length rather than the dictionary size — which is why search-as-you-type feels instant.
  • Rate limiting is about shaping a stream over time. A leaky bucket drains at a fixed rate and drops overflow, producing a perfectly smooth output. A token bucket refills tokens steadily and lets callers spend accumulated tokens, permitting short bursts while capping the long-run average — the friendlier choice most public APIs adopt.
05

Agreement and integrity across machines

The deepest problems appear once multiple machines must cooperate despite failures.

Consensus is the problem of getting a cluster of replicas to agree on a single value — who is the leader, what is the next entry in the replicated log — even though machines crash and messages arrive late or out of order. Paxos proved it was possible; Raft made it teachable by structuring it as leader election plus log replication to a majority quorum. As long as more than half the nodes are alive and can talk, the cluster stays consistent. This machinery lives inside etcd, ZooKeeper, Consul, and the metadata layer of nearly every strongly-consistent database.

Merkle trees solve integrity and comparison. Data blocks are hashed at the leaves, and each parent hashes its children, up to a single root hash that fingerprints the entire dataset. If two replicas share a root hash, their data is provably identical; if not, you descend only the branches whose hashes disagree, isolating the differing block in logarithmic time instead of comparing everything. This anti-entropy mechanism is how Dynamo-style stores repair diverged replicas, how Git identifies changed content, and how blockchains verify transactions.

None of these algorithms is exotic on its own — but reaching for the right one is the difference between a design that scales and one that quietly falls over under load.

what to remember
01

Consistent hashing spreads keys across nodes so adding or removing a node moves only a small slice of data, not everything.

02

A bloom filter answers 'have I definitely never seen this?' in a few bits, trading false positives for tiny memory.

03

Quadtrees and geohashes turn 2D location into something you can index and range-scan for 'what's near me'.

04

Token bucket and leaky bucket shape traffic: one allows controlled bursts, the other enforces a smooth constant rate.

05

HyperLogLog estimates the count of distinct items in kilobytes instead of gigabytes, with a known error margin.

06

Raft and Paxos let a cluster agree on one value even when machines crash; tries power prefix autocomplete; Merkle trees pinpoint which block of data differs.

check yourself

Quick quiz

Q1

Why is consistent hashing preferred over 'key mod N' for sharding?

Q2

What can a bloom filter guarantee?

follow the thread