Foundational learning
https://www.youtube.com/watch?v=U3RkDLtS7uY
Writing policies
The order in which data is written to the cache and the persistent data store will affect the performance of the cache.
What happens if data is written into the cache first?
Writing the data in the cache first, means you can then choose to either:
- write synchronously to the persistent datastore and then respond to the client
- write to cache and respond to the client but allow writing to the persistent storage asynchronously
The first approach is called Write-through cache. The implications of this approach is that writes will take longer as both the cache and the database are written to and ensured it is successful before a response is sent to the client.
The second approach is called write-back cache. The implication of this one is there is a chance that data read by the client could be stale and inconsistent.
Writing data into database first
Data is written to the DB first and then reads are done from the cache, on a cache-miss it is fetched from the db and cached. This is alright for writes but for reads, there would be more cache-misses than the other approach.
Eviction policies
These are necessary to keep the caches small. Caches are fast because there isn’t as much data as there could be in a database to scan and fetch from. And it is important to remove data that is not accessed from the cache from the cache to keep it small.
Some popular eviction mechanisms are:
- least frequently used
- most recently used
- least recently used
- most frequently used
Data temperature
- Hot - most frequently accessed data ready to be served from the fastest storage possible
- warm - frequently accessed data ready to be served from the next fastest storage
- cold - not as frequently used hence stored in ordinary storage to be pulled as necessary.
Cache invalidation
It is necessary to ensure that cached data is not stale depending on how often it changes in the business. Identifying stale entries is one side of the equation.
- using time to live value to deal with outdated cache items is one way
let’s say you store TTL values alongside the cached value. Then there are different ways in which you can invalidate the cache.
- Active invalidation is when there is a process that invalidates cache records based on the TTL values continuously
- Passive invalidation is when a cache value is invalidated as it is read. The client reads the value from the cache, realizes that it is stale and then invalidates and fetches fresh values from the persistent datastore.
Storage Mechanism
Distributed data storage is not trivial. Also determining what to store in the cache is an important exercise.
- what data to store in cache
- what data structure to use to store the data
Hash function
Consistent hashing is a great way to determine which server to store what data on. This ensures fairly uniform and random distribution of load. We also need to locate cache entries inside each cache server. Typical hash functions could be used to do this.
Data-structure to store cache
Linked lists - doubly linked lists specifically. But why? And wouldn’t hashmaps be best? could a combination be used?
- Adding and removing data from doubly linked list will be constant time operation
Sharding in cache clusters
We don’t want SPOF. So we shard data among multiple servers and then (do we replicate where necessary).
Dedicated cache servers
Application servers are separate to cache servers. You can scale caches independently without having to scale the application. You are creating a Caching platform/service here that can be used by any of your applications.
Colocated caching
Each service host has a cache. This is not something I would use as an application crash could take down the cache too.
Cache client
So far we have discussed where the hash functions would put the data. The entity that performs these hash calculations is: the hash client.
Put and get operations. Must be aware of all the cache servers.