Cache Me If You Can

Caching is an important process that can improve your website or application’s performance. At a high level, a cache is a data storage layer that acts like short-term memory by storing data that has been recently requested, taking advantage of the locality of reference principle in which recently requested data will likely be requested again. A cache’s main purpose is to increase data retrieval performance by reducing the number of times the main database/storage layer will need to be queried.

In this post, I wanted to look into the basics of a cache such as the different approaches to caching, how its data remains consistent with data in a database, and the different eviction policies that determine how things in a cache are removed to free up space.

Cache Approaches

Application caching and database caching are the two main approaches to caching, though most systems will rely greatly on both. Application caching will require direct integration in the application’s code. It typically works by checking if the data requested is in the cache. If not, it will retrieve the data from the database and then write the value into the cache.

Via http://lethain.com

The opposite aspect is database caching, where the cache is placed between the application and the database.

Via http://lethain.com

Cache Invalidation

There will need to be maintenance to ensure the data located in the cache is consistent with the database, as the database is the single source of truth. If your data is modified in the database, it should be invalidated in the cache. Below are the main schemes used for cache invalidation:

1. Write-through cache: data is written into the cache and the corresponding database at the same time
   • pros: fast retrieval in the cache and complete data consistency
   • cons: higher latency for write operations, as the work is done twice
2. Write-around cache: data is only written to the database, bypassing the cache
   • pros: reduces the cache from being flooded with write operations that won’t be read
   • cons: may create a “cache miss” for a read request that will have to be read from the slower backend storage and face higher latency
3. Write-back cache: data is only written to the cache initially and then written to permanent storage after specified intervals or under specific conditions
   • pros: low latency and high throughput for a write-intensive application
   • cons: risk of data loss and inconsistency in the event of a crash
4. Read-through cache: the cache sits between the application and database, and the application only requests data from the cache
   • pros: good for read-heavy workloads
   • cons: higher latency and results in a “cache miss” the first time
5. Cache Aside: the cache is sitting aside the database and the cache will be checked first to see if the data exists. If not, the application will request data from the database and then update to the cache
   • pros: simple implementation, good for read-heavy workloads
   • cons: possible data inconsistency and results in a “cache miss” the first time

Cache Eviction Policies

A cache is limited in its size and memory in order to remain performant. In order to maintain what is stored in local memory, there will need to be a way for the cache to regulate what goes in (cached) and what goes out (evicted).

The most common cache eviction polices are:

1. First In First Out (FIFO): cache acts like a queue and removes the first block accessed without considering how often or how many times it was accessed before
2. Last In First Out (LIFO): cache acts like a stack and evicts the block accessed most recently without considering how often or how many times it was accessed before
3. Least Recently Used (LRU): cache will discard the least recently used item
4. Most Recently Used (MRU): cache will discard the most recently used item
5. Least Frequently Used (LFU): cache will count how often an item is needed and the items that are least used are discarded first
6. Random Replacement (RR): cache will randomly select an item and discard it to make space when necessary

There is a lot more about caching I couldn't cover so please utilize the resources below for further reading. Next week, I’ll look at implementing an LRU cache. Stay tuned!

Resources
Cache Eviction Policies - Grokking the System Design Interview (paid resource)
Introduction to Architecting Systems
Cache(computing)
Things You Should Know About Database Caching

Comments

[Tom Hewlett-Taylor]

Great job - a nice overview of what can be a very complex topic.