Precompute or compute on the fly
Paying at write time or at read time, and how to tell which is cheaper.
01The intuition
The problem it solves
A restaurant can cook each dish when it is ordered, or cook a large pot of dal in the morning and ladle it out all day. Cooking to order gives a fresh plate but a 20-minute wait; the pot serves in 20 seconds but was made before anyone ordered. Which is right depends on how many people order dal and how much they mind it being three hours old.
Every system faces this choice. A result can be computed when someone asks (on the fly) or computed ahead of time and stored (precomputed). Both answer the same question. The difference is who waits: the writer at write time or the reader at read time, and how stale the answer is allowed to be.
Build it one piece at a time
Step 1: measure the two sides. Take "how many degrees apart are two LinkedIn members?". On the fly means a breadth-first search over the friend graph at query time: a member with 500 connections has about 250,000 second-degree and 125 million third-degree contacts to look through. That is seconds, not milliseconds.
Step 2: precompute the expensive part. Every night, compute and store each member's set of second-degree contacts. A query "are A and B within two degrees?" becomes a set lookup.
| Approach | Write cost | Read cost | Freshness | Storage |
|---|---|---|---|---|
| On the fly | none | seconds per query | exact, right now | graph only |
| Precompute second degree | a nightly batch over every member | one lookup, milliseconds | up to a day old | 250,000 ids per member |
| Hybrid | nightly batch plus a small live delta | lookup plus a small check | minutes | same plus the delta |
Step 3: decide by the ratio. If a member's connections change once a day but their degree is queried 1,000 times a day, precomputing turns 1,000 expensive reads into 1 expensive write. If the data changed 1,000 times a day and was read once, the reverse would hold.
Step 4: bound the staleness. Store the precomputed result with the time it was computed. Serve it if it is younger than the allowed age; otherwise recompute, or recompute in the background and serve the old value meanwhile (the stale-while-revalidate idea from caching).
Step 5: precompute only what is read. Nobody asks about most pairs. Precompute per member, not per pair; or precompute only for active members; or precompute the heavy intermediate (second-degree sets) and finish the last step on the fly. The state now: a batch job, a store of results with timestamps, and a read path that is a lookup.
Why it works, with the numbers
The decision is one inequality. With r reads and w changes per item per day, cost c to compute on the fly and cost p to precompute once:
precompute when w × p < r × c, that is, when reads are frequent and the result is expensive to build
For the degrees example, w = 1, r = 1,000, p is one graph walk and c is the same walk: precomputing wins a thousand to one. For a feed where each user reads twice a day but follows 500 accounts that post constantly, w is in the hundreds and the balance tips, which is why feeds use the hybrid (the fan-out article). The guarantee of precomputation is bounded read latency; its failure modes are stale answers after a change the batch has not seen, storage that grows with every precomputed result, and a nightly job that misses its window and leaves everything a day older than promised.
The trade-off you must say out loud
Precomputing trades freshness and storage for read speed. Say the allowed staleness in seconds or hours, say how big the precomputed store is, and say what happens between a change and the next batch. The next question is "can you do it incrementally?", and often the right answer is a streaming update for the common change plus a periodic full rebuild to fix drift.
Where it shows up in the 100 Google problems
- Design LinkedIn-style connection degrees: precomputed second-degree sets make a milliseconds answer possible on a graph that cannot fit in memory.
- Design Google Maps: shortest paths over a planet are precomputed into contraction hierarchies so a route is answered in milliseconds.
- Visualize 100 million points on a map: clusters per zoom level are precomputed into tiles instead of aggregated per request.