10 parts · 10 chapters

Algorithms Backends Run On

The backend mirror of the frontend Algorithms course: the algorithms inside the infrastructure you use every day. Every rate limiter, cache cluster, database, queue and service mesh is built from a small set of them. Measured here: Redis's HyperLogLog counted a million distinct ids with 0.40% error in 14 KB.

Ten parts: rate limiters; consistent and rendezvous hashing; Bloom and cuckoo filters, HyperLogLog and count-min sketches; B-trees and LSM trees side by side; skip lists; schedulers, priority queues and timing wheels; compression; Merkle trees and anti-entropy; backoff, jitter and load-balancing algorithms; and Raft implemented in code.

Start reading · Part 0 Present as slides
rate limiters · consistent and rendezvous hashing · probabilistic structures · B-trees and LSM trees · skip lists · schedulers and timing wheels · compression · Merkle trees · backoff and load balancing · Raft in codemid → staff · backend and infrastructure engineers
limitsToken bucket, leaky bucket, fixed and sliding windows.
placementConsistent hashing, rendezvous hashing, jump hash.
sketchesBloom, cuckoo, HyperLogLog, count-min: approximate answers in tiny memory.
storageB-trees, LSM trees and skip lists in real databases.
timeHeaps and timing wheels for millions of timers.
agreementMerkle trees for repair; Raft for consensus, in code.
00

Rate Limiters

Four algorithms
1 ch · ~8 min01

Consistent and Rendezvous Hashing

Placing keys on changing node sets
1 ch · ~8 min02

Bloom Filters, HyperLogLog and Count-Min Sketches

Small memory, bounded error
1 ch · ~8 min03

B-Trees and LSM Trees, Side by Side

Two families of storage engine
1 ch · ~8 min04

Skip Lists

Express lanes by coin flip
1 ch · ~8 min05

Schedulers, Priority Queues and Timing Wheels

Timers and fairness
1 ch · ~8 min06

Compression

Matching repeats, coding symbols
1 ch · ~8 min07

Merkle Trees and Anti-Entropy

Comparing large datasets cheaply
1 ch · ~8 min08

Backoff, Jitter and Load Balancing

Spreading load and retries
1 ch · ~8 min09

Raft in Code

The core rules
1 ch · ~8 min
Built on DSA and Distributed SystemsUses DSA for foundations and Distributed Systems for the theory; each part points at the course where the algorithm appears in production.