System Design Course
Caching is a concept where data is stored in fast memory for quick access. The cache is generally a temporary storage like RAM since it is faster than reading the data from HDD or a database.
There is a famous 80-20 rule which states that 20% of data is accessed almost 80% of the time. So generally we try to keep that 20% data in cache.
Pros
- Improve read performance(aka Latency)
- Reduce the load(aka Throughput)
Cons
- Increases complexity
- Consumes resources
Application server cache
Placing a cache directly on a request layer node enables the local storage of response data. Each time a request is made to the service, the node will quickly return local cached data if it exists. If it is not in the cache, the requesting node will query the data from disk. The cache on one request layer node could also be located both in memory (which is very fast) and on the node's local disk (faster than going to network storage).
What happens when you expand this to many nodes? If the request layer is expanded to multiple nodes, it's still quite possible to have each node host its own cache. However, if your load balancer randomly distributes requests across the nodes, the same request will go to different nodes, thus increasing cache misses. Two choices for overcoming this hurdle are global caches and distributed caches.
Content Distribution Network (CDN)
CDNs are a kind of cache that comes into play for sites serving large amounts of static media. In a typical CDN setup, a request will first ask the CDN for a piece of static media; the CDN will serve that content if it has it locally available. If it isn't available, the CDN will query the back-end servers for the file, cache it locally, and serve it to the requesting user.
If the system we are building isn't yet 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.
Cache invalidation
Caching is great but what about the data which is constantly being updated in the database? If the data is modified in DB, it should be invalidated to avoid inconsistent application behavior. So how would you keep data in your cache coherent with the data from your source of the truth in the database? For that, we need to use some cache invalidation approach.
There are three different cache invalidation schemes
- Write Through Cache
Data is written in cache and database at the same time. This way you can keep the consistency of your data between your database and your cache. Every read done on the Cache follows the most recent write.
The advantage of this approach is that you minimize the risk of data loss because it's written in both the cache and the database. But the downside of this approach is the higher latency for the write operation because you need to write the data at two places for a single update request. If you don't have a large amount of data then it is fine but if you have heavy write operation then this approach is not suitable in those cases.
We can use this approach for the applications which have frequent re-read data once it's persisted in the database. In those applications write latency can be compensated by lower read latency and consistency.
- Write Around Cache
Data is written in database only. Cache is marked as invalid. It is written later in cache.
This approach reduces the flooded write operation compared to the write-through cache. The downside of this approach is that a read request for recently written data results in a cache miss and must be read from a slower backend. So this approach is suitable for applications which don't frequently re-read the most recent data.
- Write Back Cache
Data is written in cache only. It is written later in db.
We have discussed that the write-through cache is not suitable for the write-heavy system due to the higher latency. For these kinds of systems, we can use the write-back cache approach. Firstly flush the data from the cache, and then write the data to the cache alone. Once the data is updated in the cache, mark the data as modified, which means the data needs to be updated in DB later. Later an async job will be performed and at regular intervals, the modified data from the cache will be read to update the database with the corresponding values.
The problem with this approach is that until you schedule your database to be updated, the system is at risk of data loss. Let's say you updated the data in the cache but there is a disk failure and the modified data hasn't been updated into the DB. Since the database is the source of truth, if you read the data from the database you won't get the accurate result.
Cache Eviction
When do we need to make/load an entry into the cache and which data we need to remove from the cache?
The cache in your system can be full at any point in time. So, we need to use some algorithm or strategy to remove the data from the cache, and we need to load other data that has more probability to be accessed in the future. To make this decision we can use some cache eviction policy.
- Least Recently Used(LRU): This is the most popular policy. When the cache becomes full, it removes the least recently used data and the latest entry is added into the cache.
- Most Recently Used(MRU): Discards, in contrast to LRU, the most recently used items first.
- First in First Out(FIFO): The cache evicts the first block accessed first without any regard to how often or how many times it was accessed before.
- Last in First Out(LIFO): The cache evicts the block accessed most recently first without any regard to how often or how many times it was accessed before.
- Least Frequently Used(LFU): Counts how often an item is needed. Those that are used least often are discarded first.
- Random Replacement(RR): Randomly selects a candidate item and discards it to make space when necessary.
Distributed Caching
A distributed cache is a cache which has its data spread across several nodes in a (a) cluster, (b) across several clusters or (c) across several data centres located around the world.
A Distributed cache under the covers is a Distributed Hash Table which has a responsibility of mapping Object Values to Keys spread across multiple nodes.
A hash table manages the addition, deletion, failure of nodes continually as long as the cache service is online. Distributed hash tables were originally used in the peer to peer systems.
For example, Redis or GemFire or Memcache.