0% completed
Caching
On This Page
Why a Cache Is Fast
Where Caches Live
Reading Through a Cache
Writing Through a Cache
Keeping the Cache Correct
When the Cache Is Full
Two Problems Worth Knowing
Key Takeaways
A cache is a small, fast store that keeps a copy of data you have already fetched. The next request for the same data is answered from the cache, so the slow work is not repeated.
The idea works because requests are not spread evenly. A small number of items are asked for again and again. A popular product page may be read a million times a day and changed once a month.
Two words describe what happens on every request.
A cache hit means the data was in the cache. A cache miss means it was not there. The system then reads it from the original source, and usually puts a copy in the cache.
The share of requests that are hits is called the hit rate. A cache with a low hit rate is not helping. It is adding a step to every request and giving nothing back.
Why a Cache Is Fast
Reading a value from a cache in memory takes well under a millisecond. Running the same query on a database usually takes several milliseconds, and it uses a database connection that another request could have used.
So a cache does two things at once. It answers faster, and it removes work from the database. The second one is often the more valuable, because the database is usually the hardest part of the system to scale.
Where Caches Live
There is not one cache in a system. There are several, at different distances from the user.
The browser keeps copies of images, CSS, and API responses on the user's device. This is the fastest cache, because there is no network request at all.
The CDN keeps copies in data centers around the world, close to users. It is used for images, video, and other files that do not change often.
Local memory in each server is a cache inside the application process. It is very fast. Its problem is that every server has its own copy. The servers can disagree with each other, and a value you delete on one server still exists on the others.
A shared cache such as Redis or Memcached is one cache that all the servers use. There is a single copy of each value, so the servers agree. The cost is one network hop.
The database has its own cache of recently used data and index pages, called the buffer pool. You do not manage this one, but it explains why the same query is often faster the second time. It stores pages rather than finished answers, so the query still runs on every call.
Reading Through a Cache
There are two common ways for the application to read.
Cache-aside, also called lazy loading. The application asks the cache. On a miss, the application reads the database itself, puts the value in the cache, and returns it. The application controls everything. If the cache goes down, the application still works, because it can always go to the database.
Read-through. The application only talks to the cache. On a miss, the cache reads the database and stores the value. The application code is simpler, and the cache library has to support it.
Cache-aside is the common choice, and it is a safe default answer.
Writing Through a Cache
When data changes, you must decide when the change reaches the database.
Write-through. The application writes to the cache, and the cache writes the same data to the database before reporting success. The client waits for both. The cache is never behind the database. The cost is a slower write.
Write-back, also called write-behind. The application writes to the cache, the cache says success immediately, and the database is updated later. Writes are fast. If the cache machine dies before the database is updated, that data is gone.
Write-around. The write goes straight to the database, and nothing is put in the cache. This is good for data that is written often and read rarely. The next read is a miss, unless an old copy of that key is still in the cache. So when the key may be cached, delete it as part of the write.
These strategies and their failure cases are covered in more detail in Cache-Aside vs Read-Through, Write-Through vs Write-Back.
Keeping the Cache Correct
The data in the cache is a copy. When the original changes, the copy becomes wrong. Wrong data in a cache is called stale data, and removing or replacing it is called cache invalidation.
There are two methods you will use most of the time.
Time to live (TTL). Every item is stored with an expiry time. When the time passes, the item is dropped and the next request goes to the source. A short TTL means fresher data and more misses. A long TTL means the opposite. Choosing the number is the whole decision, and it should come from how stale that particular data is allowed to be.
Delete on write. When your code updates a row, it also deletes that key from the cache. The next read puts the fresh value back. This is more accurate than TTL, and it only works for changes your own code knows about.
A few more methods appear in CDN and browser caches:
- Purge removes one item immediately.
- Ban removes every item that matches a pattern, for example every URL under
/products/. - Refresh fetches a new copy from the source and replaces the stored one.
- Stale-while-revalidate returns the old copy right away and fetches a new one in the background. The user never waits, and the data can be slightly old.
When the Cache Is Full
A cache has a fixed size. When it is full and a new item arrives, something must be removed. The rule for choosing the victim is the eviction policy.
- LRU (least recently used) removes the item that has not been read for the longest time. This is the usual choice, and it is a good default answer.
- LFU (least frequently used) removes the item with the fewest reads. It protects items that are popular over a long period.
- FIFO (first in, first out) removes the oldest item, no matter how often it is used.
- Random removes any item. It sounds bad, and it works surprisingly well, because it needs almost no bookkeeping.
Two Problems Worth Knowing
The hot key. One item is far more popular than the others. All requests for it reach the same cache node, and that node runs out of network capacity while the rest of the cache is idle. The fixes are to keep that item in local memory on every server, or to store it under several keys and pick one at random.
The stampede, also called the thundering herd. A very popular key expires. In the moment after it expires, every request for it misses, and all of them go to the database at the same time. The database receives thousands of copies of the same query.
There are two common fixes. Let only one request refresh the key, and make the others wait for it or use the old value. Or refresh the item shortly before it expires, so it is never actually missing.
Key Takeaways
- A cache keeps a copy of data you already fetched, so the slow work is not repeated. It works because a small number of items are requested again and again.
- The number that matters is the hit rate. A cache with a low hit rate only adds a step.
- Caches live in the browser, in a CDN, in each server's memory, in a shared cache such as Redis, and inside the database.
- Cache-aside is the common read strategy, and it keeps working when the cache goes down.
- On writes, write-through is safe and slower, write-back is fast and can lose data, and write-around skips the cache for data that is rarely read.
- Data in a cache goes stale. TTL and deleting the key on write are the two methods you will use most.
- When the cache is full, LRU is the usual eviction policy.
- Watch for the hot key and the stampede. Both come from one item being much more popular than the rest.
In an interview, adding a cache is never the interesting part. What you say next is: which data goes in it, how long it stays, and what the user sees when it is out of date.
Willian Garbo Godoy Batista (Willggb)
· 6 months ago
I think that write strategies should be separeted from topic "Cache Invalidation". The relations between the contents seems a little disconnected.
Idhant Haldankar
· a year ago
I wanted to confirm my understanding.
So in this type of cache update - Write-around cache - dont we also delete/purge the the record in cache layer? I wonder how will the client expect "cache miss" by simply updating the DB records.
Sam Levin
· 2 years ago
This explanation seems a little bizarre to me.
"You should use cache-aside when you need caching but also need to ensure that a failure of the cache won’t take down your whole system"
What's an example of a situation where I'm ok with a cache failure taking down my whole system?
I also feel like you're glossing over how much complexity is involved in implementing a read-through cache. Hard to imagine how this layer wouldn't need to be aware of a lot of application logic.
rahul.raja412
· 3 years ago
Use read aside caching when optimizing read performance is the primary concern and use read-through caching when ensuring data consistency between the cache and backend storage is critical.
Choose write-through caching when data consistency is critical, write-back caching when write performance is paramount and some data loss or inconsistency can be tolerated, and write-around caching when write operations are infrequent or when certain data should not be cached.
F
· 4 years ago
If the system we are building is not large enough to have its own CDN, we can ease a future transition by serving the static media off a separate subdomain (e.g., static.yourservice.com) using a lightweight HTTP server like Nginx, and cut-over the DNS from your servers to a CDN later.
So how does this help exactly? Isn't this just sending requests to a back-end server? Is that idea that having all of your static media on a dedicated back-end somehow faster than having both your static stuff and other stuff on the same back-end?
Nikita Karpukhin
· 4 years ago
Write-around cache: This technique is similar to write-through cache, but data is written directly to permanent storage, bypassing the cache
So how does this solve cache invalidation problem?
Chris Drane
· 4 years ago
Under this scheme, data is written into the cache and the corresponding database simultaneously.
How is this done in practice? I know that DDID references XA being one approach. Are there others?
Reading Progress
0%
On This Page
Why a Cache Is Fast
Where Caches Live
Reading Through a Cache
Writing Through a Cache
Keeping the Cache Correct
When the Cache Is Full
Two Problems Worth Knowing
Key Takeaways