Part 9 Caching | Cache Patterns | Cache Invalidation & Eviction | System Design Tutorials | Part 9 | 2020
This is one of the topics that (like Yogita says at the start of her video) - I really looked forward to findong out more about. This lecture table of contents includes:
- What is a cache?
- Use Cases
- Invalidation & Eviction
- Cache Patterns
What is a Cache?
A cache is a way to temporarily store some computed values, such as for example "what is 75 times 75" (5625). The official definition is "a hardware of software component which helps in serving the data that is either frequently requested or expensive to compute, hence the cache saves the response and saves on expensive operations."
Techopedia has the following definition: "Cache memory is a small-sized type of volatile computer memory that provides high-speed data access to a processor and stores frequently used computer programs, applications and data."
Example:
Client requests images from a server. In the first scenario, the request goes from the client to the server to the database and the response goes in the other direction.
If the same response came in from the same or a different client, it would be a waste of computing resources to request it from the database again. Instead, if the image is stored in an in-memory cache, the response time is significantly improved and the load on the database is reduced.
Either the caching can be setup at the server side, such as for example in a reverse proxy.
Or the caching can be done at the client side, such as for example via browser cache or forward proxy.
Frequently requested data is kept in a cache. Another use case for caching is when a client requests information from a server, it sends a request for data from the database, some computation is done and the result is sent in the response. If this same information is requested again - repeating the DB fetch and computation is redundant.
Instead the request and response can be kept in a cache as a key value pair - with the request as a the key and the response as the value.If the request is in the cache, it is referred to as a "cache hit", and if the request is not in the cache, it is called a "cache miss". The cache miss would then result in the database being queried and the cache being updated with the new information.
Invalidation & Eviction
After a period of time, the data in the cache is no longer up to date or relevant. In this instance the cache data needs to be invalidated and replaced or deleted. In an application that shows the daily active users e.g. 5000. After 10 mins the information request can be returned from the cache. However, after 1-2 hours the cache needs to be refreshed - also called "warming up the cache".
Time to Live
Items have a timer: TTL (Time to live) after which the data needs to be replaced. After the TTL expires the item is deleted from the cache. The next data request results in a "cache miss" and new data is retrieved and/or computed, after which the cache is updated again.
If the TTL is too low, the cache is refreshed very frequently and reduces the effectiveness of having a cache in the first place. If the TTL is too high, then the client will be served stale data.
Deciding when to invalidate a cache is a non-deterministic problem and is therefore hard to solve. It depends on each use case to find out what the best cache invalidation strategy and timing to use. The TTL can vary from seconds or minutes to hours or days. Is it more important to have up to date information and hence have more DB hits? Or is it OK to server stale data for a longer time period.
Updating the Cache
Either the old value from the cache is deleted. It will be repopulated after a cache miss and read from DB. An alternative to deleting the data is that as part of the response, the cache value is automatically updated. in some instances, both strategies are used in combination.
Cache Eviction
Due to the limited number of cache keys - if the key limit is exceeded then an existing key needs to be freed up. This is called cache eviction. Below are some examples of cache eviction strategies:
- First in, first out
- Least recently used
Cache Strategies
Cache Aside Strategy / Pattern
The cache only ever interacts with the application. Never with the server or database. If the database is updated, then either the cache is updated due to entry having it's TTL (time to live) expire - which results in the application getting a cache miss and then updating the cache with the new value. Or there is code in the application that receives notification of a new value in the database (DB) and it then updates the cache.
 |
CodeAhoy: Caching Strategies - Cache Aside |
Advantages of this pattern are that if the cache fails - that the application can keep serving the data. The application may slow down due to load on DB, but the system will still remain functioning.
Read Through Strategy / Pattern
In this pattern the cache sits between the application and the database. In this strategy the application always communicates with the cache and never with the database. The first database request will result in a cache miss - that will then trigger the cache to retrieve information from the DB and send it as the response. If there are database changes, the cache is notified and updated without any involvements from the application.
 |
CodeAhoy: Caching Strategies - Read Through |
|
Advantage of this pattern is that is supports read heavy workload such as for example news feeds. Disadvantage is that it always results in a cache miss on the first request. This can be mitigated by "pre-heating the cache", which means populating the cache in advance by sending in a pre-generated list of expected queries.
A key difference between Cache Aside and Read Through is that the latter is often implemented via third party software or library. In addition the modelling of data between the cache and database in Read Through is often similar, whilst for Cache Aside the data modelling can be different.
Write Through Strategy / Pattern
Very similar to read-through pattern and often used in conjunction with the read-through pattern. Application reads and writes to the cache, which is then in turn responsible for updating the database. The disadvantage of this approach is that there is additional time needed for writing to the database - compared to cache aside in which the application writes to the database directly.
Write Around Strategy / Pattern
This pattern tries to use the best of both worlds. The application writes directly to the database, and reads via the cache from the database. So it has the speed of reading from the cache, as well as the speed of writing directly to the database. This strategy is often used when the system has heavy load of write traffic and less read heavy traffic.
Write Back Strategy / Pattern
This is very similar to write through pattern... except that the writes are sent as a batch. So the cache will send an acknowledgement to each write request to the cache, store the write request, and only send it to the database after specific time internal or other condition (such as number of pending writes).
One key advantage of this approach is that it can handle database failure, as the data will be stored for some time in the cache. The main disadvantage of this pattern is that if the cache fails, the database is not updated.
Pros and Cons of each Caching Strategy / Pattern
Cache Aside Pattern
+ Supports heavy reads
+ Works even if cache goes down
- TTL application code have to be used to keep cache and DB consistent
Read/Write Through Pattern
+ Great alternative for read heavy workloads, e.g. news-feed
? Data modelling of cache and DB have to be similar
- Cache failure results in system failure
? Caching layer adds extra layer of latency while writing to the DB (can be solved by 'write around pattern')
Write Back Pattern
+ Useful for write heavy workloads
+ Database failure can be sustained for time cache keeps data in bulk
+ Used by various DB internal applications
- Cache failure results in system failure
Useful links:
Where do I keep the Cache
Caching can be done at client (browser), proxy level, application level, outside of application level, etc. Cache can be used in any of these parts of the system or all of the parts of the system - it really depends on your use cases to which caching locations works best.