Cheat sheet · Scaling
Cache invalidation
The problem
An account API keeps each account's plan in a cache in front of the database. A TTL alone keeps a customer who just paid on the old plan for up to ten minutes. Deleting the key after the write fixes the usual case but leaves a race in which an old value is written back after the delete. Delete twice, leases and invalidation from the database change log close the gaps one by one, and on the read side a hot key is served stale while one request refreshes it, and rows that do not exist are cached too.
What you learn
- Why a TTL limits how long data is wrong but does not make it right, and how delete-after-write differs from writing the new value into the cache
- The race between a slow reader and a writer that leaves an old value in the cache after the delete, and three ways to close it: delete twice, versions, leases
- Invalidating from the database change log (CDC), so writers that never call the API cannot leave the cache stale
- Stale-while-revalidate with jitter for a hot key, and negative caching for lookups that find nothing
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_app(["Web app"])
n_api["Account API"]
n_cache{{"Cache"}}
n_db[("Accounts DB")]
n_batch("Billing job")
n_cdc("CDC worker")
n_app -->|"call"| n_api
n_api -->|"call"| n_cache
n_api -->|"call"| n_db
n_batch --> n_db
n_cdc -->|"async"| n_db
n_cdc --> n_cacheMermaid: request sequence
sequenceDiagram
participant n_app as Web app
participant n_api as Account API
participant n_cache as Cache
participant n_db as Accounts DB
participant n_batch as Billing job
participant n_cdc as CDC worker
Note over n_app,n_api: The plan of every account, cached for ten minutes
n_app->>n_api: GET /v1/accounts/4821/plan HTTP/1.1
n_api-->>n_app: HTTP/1.1 200 OK
Note over n_api,n_cache: The customer paid, the cache still says Free
n_api->>n_cache: 10:00:00 UPDATE accounts SET plan = 'pro' WHERE id = 4821#59; COMMIT
Note over n_api,n_db: After the commit, delete the key
n_api->>n_db: PATCH /v1/accounts/4821/plan {#34;plan#34;: #34;pro#34;}
Note over n_api,n_cache: A slow reader writes the old value back
n_api->>n_cache: acct:4821:plan two requests, one key
Note over n_api,n_cache: Delete again a little later
n_api->>n_cache: W COMMIT#59; DEL acct:4821:plan#59; schedule DEL in 500 ms
Note over n_api,n_cache: A lease: the cache refuses a fill it did not expect
n_api->>n_cache: R get acct:4821:plan -#62; MISS, lease 7731
Note over n_batch,n_db: A writer that never calls the API
n_batch->>n_db: -- billing job, 02:00 every night
Note over n_cdc,n_db: Invalidate from the database change log
n_cdc->>n_db: change accounts lsn 0/5B10A2C8
n_db-->>n_cdc: DEL acct:4821:plan acct:4821:limits -#62; (integer) 2
Note over n_api,n_cache: Everyone waits for one rebuild
n_api->>n_cache: 11:00:00.000 config:tariffs expired (read 18 000/s by every request)
Note over n_api,n_cache: Serve the old value while one request refreshes it
n_api->>n_cache: GET config:tariffs (EX 3600)
n_cache-->>n_api: 11:00:00.001 past fresh_until: answer with this value now
Note over n_api,n_cache: Cache #34;not found#34; too
n_api->>n_cache: GET acct:4821:limits -#62; (nil)D2
direction: right
n_app: "Web app" {
shape: rectangle
}
n_api: "Account API" {
shape: rectangle
}
n_cache: "Cache" {
shape: hexagon
}
n_db: "Accounts DB" {
shape: cylinder
}
n_batch: "Billing job" {
shape: rectangle
style.multiple: true
}
n_cdc: "CDC worker" {
shape: rectangle
style.multiple: true
}
n_app -> n_api: "call"
n_api -> n_cache: "call"
n_api -> n_db: "call"
n_batch -> n_db
n_cdc -> n_db: "async"
n_cdc -> n_cachePlantUML: request sequence
@startuml
participant "Web app" as n_app
participant "Account API" as n_api
collections "Cache" as n_cache
database "Accounts DB" as n_db
participant "Billing job" as n_batch
participant "CDC worker" as n_cdc
note over n_app, n_api : The plan of every account, cached for ten minutes
n_app -> n_api : GET /v1/accounts/4821/plan HTTP/1.1
n_api --> n_app : HTTP/1.1 200 OK
note over n_api, n_cache : The customer paid, the cache still says Free
n_api -> n_cache : 10:00:00 UPDATE accounts SET plan = 'pro' WHERE id = 4821; COMMIT
note over n_api, n_db : After the commit, delete the key
n_api -> n_db : PATCH /v1/accounts/4821/plan {"plan": "pro"}
note over n_api, n_cache : A slow reader writes the old value back
n_api -> n_cache : [duplicate] acct:4821:plan two requests, one key
note over n_api, n_cache : Delete again a little later
n_api -> n_cache : W COMMIT; DEL acct:4821:plan; schedule DEL in 500 ms
note over n_api, n_cache : A lease: the cache refuses a fill it did not expect
n_api -> n_cache : R get acct:4821:plan -> MISS, lease 7731
note over n_batch, n_db : A writer that never calls the API
n_batch -> n_db : -- billing job, 02:00 every night
note over n_cdc, n_db : Invalidate from the database change log
n_cdc ->> n_db : change accounts lsn 0/5B10A2C8
n_db -->> n_cdc : DEL acct:4821:plan acct:4821:limits -> (integer) 2
note over n_api, n_cache : Everyone waits for one rebuild
n_api -> n_cache : 11:00:00.000 config:tariffs expired (read 18 000/s by every request)
note over n_api, n_cache : Serve the old value while one request refreshes it
n_api -> n_cache : GET config:tariffs (EX 3600)
n_cache --> n_api : 11:00:00.001 past fresh_until: answer with this value now
note over n_api, n_cache : Cache "not found" too
n_api -> n_cache : GET acct:4821:limits -> (nil)
@endumlPlantUML: components
@startuml
left to right direction
agent "Web app" as n_app
component "Account API" as n_api
stack "Cache" as n_cache
database "Accounts DB" as n_db
collections "Billing job" as n_batch
collections "CDC worker" as n_cdc
n_app --> n_api : call
n_api --> n_cache : call
n_api --> n_db : call
n_batch --> n_db
n_cdc --> n_db : async
n_cdc --> n_cache
@endumlRecap
Six rules for cache invalidation.
1) A TTL only limits how long data is wrong; keep it as a safety net. 2) After a write, delete the key after the commit, do not write the new value. 3) A slow reader can put an old value back after the delete: delete twice narrows the window, a lease or a version check closes it. 4) Invalidate from the change log, so every writer is covered, and commit the log offset only after the delete. 5) For hot keys, serve the old value while one request refreshes it, and jitter the TTL. 6) Cache "not found" with a short TTL, and invalidate it on insert.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Stale cache fills | 0/day | 0/day |
| Longest stale window | 0 s | 0 s |
| DB reads | 900/s | 300/s |
| Cache hit ratio | 94% | 98% |
| p99 latency | 6 ms | 6 ms |
Steps
- Case The plan of every account, cached for ten minutes
Every page of the web app asks the account API which plan the account is on: 15 000 reads a second.
- Problem The customer paid, the cache still says Free
At 10:00 account 4821 upgrades to Pro and the database commits.
- Fix After the commit, delete the key
The API now deletes the key right after the transaction commits.
- Problem A slow reader writes the old value back
Reader R misses and reads the row while it still says
free. - Fix Delete again a little later
A cheap fix: after the first delete, the writer schedules a second one 500 ms later.
- Fix A lease: the cache refuses a fill it did not expect
With a lease, a miss returns a token.
- Problem A writer that never calls the API
Every night at 02:00 a billing job downgrades accounts whose payment has run out: 1 900 rows in one
UPDATE. - Fix Invalidate from the database change log
A CDC worker reads the database's change log.
- Problem Everyone waits for one rebuild
Every request also reads
config:tariffs, 18 000 times a second. - Fix Serve the old value while one request refreshes it
The value now has two lifetimes.
- Fix Cache "not found" too
Every page also asks for the account's custom limits, and 96% of accounts have none.
- Recap Recap
Six rules for cache invalidation.
Terms
- Cache invalidation
- Removing the old cached copy when the data changes. The key is deleted after the commit, so the next read fetches the fresh value.
- Stale-while-revalidate
- A cached value has a soft and a hard TTL: after the soft one the old value is still served at once while one request refreshes it in the background, so nobody waits for the rebuild.
- Negative caching
- Caching a "not found" answer with a short TTL, so lookups of rows that do not exist stop hitting the database every time. Inserting the row must delete the entry.
- Cache lease
- A token handed out with a cache miss: a fill is accepted only with a token that is still valid, and deleting the key cancels it, so a slow reader cannot write an old value back.
- Delayed double delete
- Deleting a cache key right after a write and once more a little later, to remove an old value a slow reader put back in between. It narrows the race window but does not close it.