CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 5 of 6 · 3 min read

Choosing a pattern

A short procedure for picking a read and a write pattern, with two worked cases.

Choosing a pattern

Think of a menu in a restaurant that lists a starter, a main and a dessert. Each course has a rule of thumb. Reads and writes in a cache also come in pairs: one rule for loading, another for changing.

A procedure:

  1. Pick the read pattern. Use cache-aside with a separate cache server unless a library already offers read-through. Cache-aside keeps the application working if the cache fails.
  2. Pick the write pattern from the data. - Must never lose a write: write-through, or write-around with delete. - Many repeated writes to the same item and a small loss is acceptable: write-back. - Written once, read rarely: write-around.
  3. Set a TTL whatever the pattern, to bound staleness.
  4. Decide what happens when the cache fails. Reads fall back to the database, which must be able to cope (module 4).

Case 1: user profiles. A profile is read on every page and changed a few times a year. Reads: cache-aside. Writes: write to the database, then delete the key. TTL: 1 hour. A lost cache means slower pages, not lost data.

  • 1,000,000 profile reads an hour with a 98 percent hit ratio: 20,000 database reads.
  • 100 profile updates an hour: 100 database writes and 100 deletes.

Case 2: counters of video views. A popular video gets 5,000 views a second. Writing each to the database means 5,000 writes per second. Instead, count in the cache and flush the total every 5 seconds: 1 write of +25,000 per 5 seconds for that video, or 0.2 writes per second. The risk is losing up to 5 seconds of counts after a crash, which is acceptable for a view counter and not for money. Make the cache durable where needed, for example with a log, as in-memory stores do (book "Designing Data-Intensive Applications": some in-memory stores write a log or take snapshots to survive restarts, while Memcached is meant for caching, where losing data on restart is accepted).

A table of common systems:

Data Read Write Why
Product pages Cache-aside Database, then delete Read often, changed rarely
Session data Read-through or direct Write-through Must not vanish mid-login
View counters Cache-aside Write-back Many writes, small loss ok
Uploaded files, read rarely Cache-aside Write-around Avoid filling the cache
Bank balance Usually no cache, or very short TTL Database first Staleness not acceptable

Interview angle

Answer in your head first, then open it.

How does your cache get filled?

Cache-aside: check the cache, on a miss read the database and store the value, with a TTL. Say what happens to the system if the cache is down.

What happens on a write?

Write the database, then delete the key. Explain why not update the cache, with the two-writer race.

When would you use write-back?

For counters and bursts of repeated writes, where a small loss is acceptable or the buffer is stored safely. Name the flush interval and the loss window.

What if the cache and database disagree?

A TTL bounds the disagreement, and a delete after the write narrows it. Name the race that remains.

Check yourself:

  • Which write pattern would you choose for a shopping cart that must not lose items, and which read pattern?
  • A counter receives 8,000 increments a second. With a flush every 10 seconds, how many database writes per second?

Words you will meet

Word Plain meaning
Cache-aside (side cache) The application loads the cache on a miss
Read-through (inline cache) The cache loads from the database on a miss
Write-through Writes go to cache and database together
Write-back (write-behind) Writes go to the cache first and reach the database later
Write-around Writes skip the cache and go to the database
Cache invalidation Removing a cached copy because the source changed
Flush Sending buffered writes on to the database
Race A bug that depends on the timing of two actions
Cold cache A cache with no useful entries yet