The primitives that recur

1. The point of this chapter

You've now read twenty-four company chapters. If you went straight through, you saw the same handful of tools come up over and over. Token buckets at Stripe, AWS, Cloudflare, OpenAI. Consistent hashing at Amazon, Cassandra at Apple, DynamoDB's partitions. Sagas at Uber and Stripe Connect. Idempotency keys everywhere.

These are the primitives that recur. There are about a dozen of them. Once you know them cold, you stop re-learning the same idea in twelve different costumes and start recognizing it when an interviewer reaches for it.

This chapter is the catalog. Each unit covers one primitive in depth. Not as an interview scenario — there's no green/yellow/red rubric here, no 10-beat skeleton. Just the mechanism, the variants, the pitfalls, and the signal panels are listening for when the primitive shows up.

Use this chapter two ways. Read it straight through once to lock in the vocabulary. Then come back to a specific unit before any round where you expect the primitive to show up. The Stripe loop next week? Re-read 25.6 on idempotency. AWS? Re-read 25.5 on leader election. The catalog is built to be re-read.

2. The dozen, in one paragraph each

Rate limiting — token bucket, sliding window, leaky bucket ([[rate-limiting-token-bucket-sliding-window]])

The most-asked algorithm in the catalog. Token bucket is the default — every API service you'd recognize uses some variant. The interview test is whether you can defend the choice between token bucket, sliding window log, and leaky bucket, and whether you can extend the single-node version to multi-region without claiming the limit is exact. Shows up in [[take-home-multi-tenant-rate-limiter]] (Microsoft), the AWS gateway, Cloudflare's edge, every LLM serving stack, and the Stripe API.

Consistent hashing ([[consistent-hashing]])

How a distributed store survives a node joining or leaving without re-shuffling everything. The ring, the virtual nodes, the bounded load. Comes up in any distributed KV: DynamoDB ([[dynamodb-partitioned-kv]]), Cassandra at Apple ([[cassandra-replication-and-quorum]]), Redis Cluster, the data plane of any object store. Panels test whether you understand why naive hash(key) mod N falls apart on N changing.

Sagas and distributed transactions ([[sagas-and-distributed-transactions]])

When you need atomicity across services and two-phase commit isn't on the table. Compensating actions instead of rollbacks. Choreography (services react to events) versus orchestration (a coordinator drives the steps). Shows up in Stripe Connect ([[stripe-connect-multi-party-transfers]]), Uber's trip state machine ([[trip-state-machine-and-payments]]), Amazon's order fulfillment ([[order-fulfillment-inventory-holds]]).

Distributed locking and the Redlock controversy ([[distributed-locking-redlock-controversy]])

When exactly one process has to do something. Redis SETNX, the Redlock algorithm, and Martin Kleppmann's critique that started a decade of arguments. Zookeeper and etcd as the conservative alternative. Fencing tokens. Comes up wherever you need leader election, inventory holds, or single-flight cache fill.

Leader election — Raft and Paxos ([[leader-election-raft-paxos]])

The consensus problem. Raft if you want to be able to explain it on a whiteboard; Paxos if you want to cite the canonical paper. Quorums, terms, election rounds. Shows up in every database failover, every leader-elected scheduler ([[take-home-leader-elected-job-scheduler]] at AWS), every replicated log.

Idempotency — the universal grading criterion ([[idempotency-the-universal-criterion]])

So universal it's almost a separate signal on every rubric. Per-request keys, per-resource keys, time-windowed dedup. The retry-storm story. Stripe's idempotency-key contract ([[idempotency-keys]]) is the canonical version, but the primitive shows up at Google's distributed counter ([[distributed-counter-ad-impressions]]), Meta's like button ([[the-like-button-deceptively-hard]]), every webhook system ([[webhook-delivery-retries-ordering]]).

CAP and PACELC in practice ([[cap-and-pacelc-in-practice]])

CAP stated honestly (which is rarer than it should be). PACELC as the more useful framing — during partition, choose availability or consistency; otherwise, choose latency or consistency. When to invoke the theorem (justifying a consistency choice) and when to shut up about it (most rounds). The over-invocation mistake is its own anti-signal.

Bloom filters and probabilistic structures ([[bloom-filters-and-probabilistic-structures]])

Bloom filter for "have I seen this?" with no false negatives. Cuckoo for "and let me delete." Count-min sketch for frequency. HyperLogLog for cardinality. Shows up at Google's web crawler ([[web-crawler-at-planet-scale]]) for dedup, X's trending topics ([[trending-topics]]) for top-K, every real-time analytics pipeline.

Sharding strategies and rebalancing ([[sharding-strategies-and-rebalancing]])

Hash-based, range-based, lookup-based. How to reshard without downtime. Hot-shard mitigation. The dynamic case (which is consistent hashing) versus the static case. Every storage system at scale: Bigtable's tablets ([[bigtable-row-locality-and-tablet-splits]]), DynamoDB's partitions, Vitess, Cassandra.

3. The two that didn't get their own unit (but should still be on your radar)

Two more primitives recur often enough to mention, but they're covered well enough in the company chapters that a standalone catalog entry would repeat the same material.

Write-ahead logging and the LSM tree. Every modern storage engine writes to a log first, then applies. The LSM tree (memtable, SSTables, compaction) is the standard read-optimized variant. Covered in depth in [[cassandra-replication-and-quorum]] (Apple) and [[bigtable-row-locality-and-tablet-splits]] (Google).

Caching strategies — cache-aside, write-through, write-around, write-back. The four patterns, with TTL and invalidation as the cross-cutting concerns. Covered in [[cdn-and-cache-invalidation]] (Cloudflare) and [[checkout-and-the-black-friday-spike]] (Shopify).

If a primitive isn't called out here, it's probably either a domain detail (and lives in the company chapter where it was introduced) or it's a sub-component of one of the dozen above.

4. How to read the rest of this chapter

Each entry follows the same six-section shape:

1. What it is — one paragraph naming the primitive in plain language.
2. Where it shows up — the cross-references to every company unit that touches it.
3. The mechanism — how it works, with a diagram or two.
4. The variants — a table comparing flavors.
5. The implementation pitfalls — what goes wrong in practice.
6. The interview signal — what the panel is listening for.

The chapter takes about three hours to read end-to-end. The drill afterward: for each primitive, write the five-component tradeoff sentence from [[tradeoffs-as-the-answer]]. Choice, reason, alternative, inversion constraint, cost. If you can produce those for all nine catalog entries, the depth round on any company chapter is yours.