appendonly

This is the most interesting caching problem I have worked on in years. In a normal service the cache sits off to the side and makes things faster. Here it decides your throughput, your cost per token, and how many people fit on a GPU at once.

goal

Serve a 70B model to a chat product and a code assistant on the same fleet, at p95 time-to-first-token under 400ms.

traffic

Roughly 3k requests/sec at peak. Median prompt 2,400 tokens, p95 around 18,000. Heavy prefix sharing: system prompts, few-shot blocks, repo files.

hardware

H100 80GB nodes, 8 GPUs each. The model weights eat about 140GB across two GPUs with tensor parallelism, so the cache gets what is left.

hard part

Memory is the bottleneck, not compute, and the working set is shaped by which prompts share prefixes.

What is actually being cached

During generation, every previously seen token contributes a key and a value vector at each attention layer. Recomputing them for every new token would be quadratic, so you keep them. That is the KV cache, and it grows linearly with sequence length, per request.

The arithmetic decides the design. For a model with 80 layers, 8 key/value heads after grouped query attention, and a head dimension of 128, one token costs roughly 2 (K and V) × 80 × 8 × 128 × 2 bytes in fp16, which is about 320 KB per token. A 20,000 token conversation is around 6.4 GB of cache for one user. On a node with maybe 50GB free after weights, that is eight concurrent long sessions before you are out of memory. Eight. On a machine that cost more than a house deposit.

Everything below follows from that number.

Paging, because contiguous allocation is a disaster

The naive implementation reserves a contiguous block sized to the maximum possible sequence length for every request. If your max context is 128k and the median request uses 2.4k, you are wasting more than 95 percent of the memory you reserved. Internal fragmentation kills you before load does.

The fix is the one operating systems landed on in the 1960s. Chop the cache into fixed size blocks, typically 16 or 32 tokens, keep a per-sequence block table mapping logical positions to physical blocks, and allocate blocks lazily as the sequence grows. This is what vLLM calls paged attention, and the effect on memory utilization is not subtle. Fragmentation drops to at most one partly filled block per sequence, and batch sizes go up several times over for the same hardware.

Prefix sharing is where the real win lives

Once blocks are the unit of allocation, two sequences with the same prefix can point at the same physical blocks. In our traffic that is not a rare case, it is the common one. The chat product prepends a 900 token system prompt to every request. The code assistant sends the same repository files across dozens of turns. Measured on a week of real traffic, about 62 percent of prompt tokens were a prefix somebody else had already computed.

To exploit it you need a lookup structure keyed on token sequences, and a radix tree over token ids works well: each node holds a run of tokens plus the blocks that back them, and inserting a new prompt walks down the tree until it diverges. On a hit you skip the prefill for those tokens entirely, which is the expensive quadratic part. Time to first token for a repeat system prompt drops from a few hundred milliseconds to tens.

Two details that bit me. Hashing must include position and any prefix before it, so a block is only reusable if the entire preceding context is identical. And the tree must be keyed per model and per LoRA adapter, since identical tokens produce different K and V vectors under different weights. I have watched someone spend a day on a "model is answering wrong" bug that was a cache key missing the adapter id.

Eviction

Classic LRU is wrong here, or at least incomplete, because entries have wildly different values. Evicting a leaf node that one idle session might resume costs you a small prefill. Evicting the shared 900 token system prompt block costs every request that arrives in the next second.

What worked: evict leaves first, never evict a node with a live refcount, and weight by (tokens saved on hit × recent hit rate) rather than recency alone. In effect it is closer to GDSF than LRU. Keep the hottest few prefixes pinned outright, since a dozen system prompts cover a large share of traffic and the memory cost is trivial.

Routing, or how the cache changes your load balancer

Here is the part that surprised me. Once the cache is this valuable, round robin routing is actively harmful. Sending a request to a node that does not have its prefix means recomputing work that already exists three racks away.

So the router became cache aware. It keeps an approximate view of which prefixes live where (each node publishes a compact summary of its radix tree roots every few hundred milliseconds), and it scores candidate nodes on prefix overlap against current queue depth. The scoring function needs a load term with real teeth, otherwise every request piles onto whichever node happens to hold the popular prompt and you have rebuilt the hot key problem from offset 007. We ended up capping the cache bonus so it can never outweigh a queue that is more than about twice the fleet median.

Offloading and the memory hierarchy

Blocks that fall out of GPU memory do not have to die. Host RAM is roughly an order of magnitude cheaper per gigabyte and a PCIe transfer of a few hundred megabytes takes single digit milliseconds, which is far less than recomputing prefill for 20k tokens. So there is a second tier in CPU memory, and for the code assistant, a third tier on local NVMe holding the repository prefixes that get reused across a working day.

Quantizing the cache to fp8 roughly halves it and, for most chat workloads, the quality difference is hard to detect. I would still gate it behind an eval on your own traffic, since long context retrieval tasks are noticeably more sensitive than short chat.

What DDIA already told me

None of this is new, which is the point. The block table is a page table. Copy-on-write is a filesystem trick. Refcounted shared prefixes are a persistent data structure. Cache aware routing is consistent hashing with a load penalty. The radix tree is a trie. The systems ideas transferred almost unchanged. What moved is the constants, and they are brutal. At 320 KB a token, a memory decision is a headcount decision, and you feel it on the invoice.

Every company I have talked to in the last two years has built roughly this system, and most of them, including one I worked on, learned the same lessons in the same order. The first version works beautifully on a laptop with 100k vectors. Everything after that is a different problem.

corpus

400M text chunks from documents, tickets, and wiki pages across 12k customer tenants. 1024-dimensional embeddings.

queries

800/sec, always filtered by tenant, usually filtered further by document type or date. p95 budget of 120ms for retrieval.

freshness

An edited document should be searchable within about a minute. Deletes must be immediate, for legal reasons.

hard part

Filtering. Nearly everything published about ANN benchmarks assumes an unfiltered search, and almost no production query is unfiltered.

Size it before you design it

400M vectors × 1024 dims × 4 bytes in fp32 is 1.6 TB of raw vectors. An HNSW graph adds edge lists on top, typically another 30 to 50 percent depending on M. You are not fitting that in RAM on one machine at any sane price, so the question becomes compress, shard, or spill to disk. In practice, all three.

Product quantization at 8x compression brings it to roughly 200 GB, which is a fleet of a dozen machines rather than a hundred. The recall cost is real but recoverable, because you rerank: retrieve 200 candidates with the compressed representation, then rescore the top candidates against full precision vectors fetched from disk or a separate store. Recall at 10 comes back to within a point or two of exact search, and you only pay full precision reads on 200 rows instead of 400 million.

Picking the index

We landed on HNSW with product quantized vectors held in memory and full precision vectors on NVMe for reranking. M of 32 and efConstruction of 200 built in a bit under a day per shard on a 64 core box, which is fine because you rebuild rarely. efSearch is the knob you actually tune in production; ours sits around 100 and moves with load, since it trades recall for latency almost linearly.

The filtering problem

This is the part that separates a demo from a product. A query is never "find similar chunks". It is "find similar chunks that belong to tenant 8842, are of type wiki, and were updated in the last year".

Pre-filtering means computing the allowed set first, then searching only within it. Correct, but if the filter is selective the HNSW graph becomes disconnected: you walk into a region where every neighbour is filtered out and the search stalls with terrible recall. Post-filtering means searching normally and dropping disallowed results, which is fast and returns three results when you asked for fifty, because the top 200 were all other tenants.

What we do instead, in order of preference. If a filter is high cardinality and always present, make it a physical partition. Tenant id was exactly this, so every tenant gets its own index segment, small tenants share a segment, and the twenty largest get dedicated ones. That single decision solved most of the filtering problem, because the dominant filter stopped being a filter at all.

For remaining filters we do filtered traversal: evaluate the predicate during the graph walk using a bitmap, and if the pass rate drops below roughly one percent, abandon the ANN path and do a brute force scan over the filtered set, which by then is small enough to be cheap. Having both paths and a cost model to choose between them is what a query planner does, and it turns out you need one here too.

Freshness, deletes, and the segment trick

HNSW does not really support deletion. You can tombstone a node so it is skipped in results while still being traversable, but tombstones accumulate and degrade both recall and speed.

The answer is the same one Lucene has used for two decades, which is also the LSM tree from offset 004. Write into small immutable segments. New documents land in a fresh in-memory segment that is searchable within seconds. Deletes go into a bitmap per segment, applied at query time, so a delete is immediate and cheap. A background merge rewrites segments, physically dropping deleted rows and rebuilding the graph. A query fans out to all segments and merges the top k.

Once we had that, the embedding model upgrade problem solved itself. Reindexing 400M chunks with a new model is a replay, not a migration: build new segments in the background, run both indexes in parallel behind a flag, compare on an eval set, flip the read path, drop the old segments. That is the derived data idea from offset 010, doing its job.

Hybrid retrieval, because embeddings cannot spell

Pure vector search loses to BM25 on exact identifiers. Error codes, part numbers, function names, someone's surname. The embedding has no idea that ERR_4471 and ERR_4417 are different in a way that matters, and it will happily return one for the other.

So run both and fuse. Reciprocal rank fusion is the boring choice and is hard to beat without training something: score each document as the sum over retrievers of 1/(60 + rank). No score normalization, no tuning, works immediately. Then rerank the top 50 with a cross encoder if your latency budget allows, which in our case added about 40ms and was worth more than any index tuning we did.

If I could send one message back in time to the start of this project it would be: build the evaluation set before the index. We spent weeks tuning efSearch and M with no ground truth, arguing about whether results felt better. Two hundred labelled queries would have settled every one of those arguments in an afternoon.

Money systems are where the transaction chapter stops being academic. The requirement is not "usually correct". It is that after any combination of crashes, timeouts, duplicate requests, and a client that gave up and tried again, the balance is right and you can explain it to an auditor.

scope

Internal ledger for wallet transfers and card settlements. Low volume by internet standards, around 400 writes/sec, but every write is load bearing.

invariant

Every transfer sums to zero across accounts. No account goes below its allowed floor. Nothing is ever deleted or updated in place.

hard part

The upstream network retries aggressively and its timeouts are shorter than our worst case latency, so duplicate requests are normal traffic, not an edge case.

Append only, always

The ledger is a table of immutable entries. A balance is not a column you update, it is a fold over entries. That sounds expensive and it is not, because you keep periodic checkpoint rows and read the entries after the latest checkpoint.

create table entry (
  id            bigserial primary key,
  transfer_id   uuid        not null,
  account_id    bigint      not null,
  amount_minor  bigint      not null,   -- signed, always integers
  currency      char(3)     not null,
  created_at    timestamptz not null default now()
);

-- double entry: every transfer inserts >= 2 rows summing to zero
create index on entry (account_id, id desc);

Two rules I would fight for. Store money as integers in the minor unit, never floats, and carry the currency alongside every amount so nobody can add pence to cents. And never allow an UPDATE or DELETE on this table; revoke the grants so the rule is enforced by the database rather than by code review. A correction is a new compensating entry, which is also what accountants have done since the fifteenth century.

Idempotency, done properly

The client sends an idempotency key with each transfer. The obvious implementation, check whether the key exists and insert if not, has a race in it wide enough to lose money through, because two concurrent retries both check before either inserts.

Let the database do the work. A unique constraint on the key, an insert that hits the conflict, and the second caller reads the original result:

-- attempt to claim the key; only one caller wins
insert into idempotency (key, request_hash, state)
values ($1, $2, 'in_progress')
on conflict (key) do nothing
returning id;

-- no row returned means someone else owns it:
--   state = 'done'        -> return the stored response
--   state = 'in_progress' -> 409, tell the client to retry shortly
--   request_hash differs  -> 422, same key with different body is a client bug

That last case matters more than it looks. If a client reuses an idempotency key with a different payload, silently returning the old response is worse than an error, because it hides a bug in their code that will eventually charge the wrong person. Store a hash of the request and reject mismatches loudly.

Expire keys, but slowly. We keep them 30 days, which is longer than any retry policy upstream and long enough that a support engineer investigating a week old complaint can still see what happened.

Getting the event out without dual writes

The moment a transfer commits, five other systems want to know: notifications, fraud scoring, the data warehouse, the customer statement service, the reconciliation job. The tempting implementation is to commit the transaction and then publish to Kafka. That is a dual write, and it fails in both directions. Publish before commit and you can announce a transfer that got rolled back. Publish after commit and a crash in between loses the event silently.

The outbox pattern removes the problem. Insert the event into an outbox table inside the same transaction as the ledger entries, so it is atomic by construction. A separate relay reads the outbox, either by polling or by tailing the WAL with logical decoding, and publishes to Kafka.

Delivery is at least once, so consumers must be idempotent. For the warehouse that means upserting on transfer id. For notifications it means a sent-notifications table keyed on the same id, checked before sending, because customers do notice two identical texts about the same payment.

Isolation, concretely

Checking a balance and then inserting a debit is a textbook write skew: two concurrent transfers each read a balance of 100, each approves a withdrawal of 80, and the account ends at negative 60. Read committed will not stop it and neither will snapshot isolation, because they touch different rows.

Three options that work. Lock the account row with SELECT ... FOR UPDATE before reading the balance, which serializes per account and is usually fine because contention is per account rather than global. Use serializable isolation and retry on 40001, which is clean if your transactions are short. Or make the invariant a constraint on a materialized balance row, so the database rejects the write.

We picked row locks on the account, ordered by account id to avoid deadlocks between two transfers touching the same pair in opposite directions. That ordering rule is three lines of code and it eliminated an entire class of 3am pages.

Reconciliation, because you will still be wrong

Every ledger I have seen eventually disagrees with the bank, usually because of something outside your transaction boundary: a settlement file with a different cutoff time, a chargeback posted with yesterday's date, a partner who rounds differently.

So there is a job that recomputes every account balance from entries and compares it against the checkpoint, and a second job that compares our totals against the provider's settlement file. Both write their findings to a table rather than logging them, because a discrepancy needs an owner and a resolution, not a line in Datadog that scrolls away. The first time it fired, it caught a rounding difference on foreign exchange fees worth about eleven pounds a day, which nobody would ever have noticed and which had been running for four months.

The Twitter example in chapter one is the one everybody quotes, so it is worth writing down what actually changes when you build it rather than describe it.

Fanout on read is one row per post and a join at query time: fetch everyone you follow, fetch their recent posts, merge, sort. Writes are trivial, reads are expensive and get worse as people follow more accounts. Fanout on write precomputes each user's timeline at post time, so reads are a single sequential scan of one list, and writes cost one insert per follower.

Neither survives on its own. A user with 30M followers turns one post into 30M writes, which at any reasonable rate takes minutes and floods the write path. A user who follows 5,000 accounts turns one timeline read into a 5,000 way merge.

The hybrid everyone converges on: fan out on write for ordinary accounts, and for a small set of very high follower accounts, keep their posts out of the precomputed lists and merge them in at read time. The threshold is a business decision more than a technical one. Somewhere around 100k followers made sense for us, and the number of accounts above it was small enough to hold in memory on every reader.

Practical things that are not in the diagram. Timelines are capped, typically at 800 entries, since nobody scrolls further and unbounded lists are unbounded storage. Deletes are lazy, filtered at read time against a tombstone set, because chasing 30M copies of a deleted post is worse than checking on the way out. And the fanout job must be idempotent and resumable, because it will crash halfway through a large account and you need to restart from an offset rather than from the beginning.

If it were a ranked feed rather than reverse chronological, most of this stays, but the merge step becomes a scoring step, and the capped list becomes a candidate pool rather than the answer. The storage design does not change much. It is the read path that grows a model in the middle of it.