Caching in depth

In the previous post we learned about what is caching and why it's useful. Now, we are going to understand some more concepts related to caching. 

Topics Covered

• Comparison with different databases
• Cache eviction policies
• Cache miss
• Cache invalidation strategies
• Challenges with caching
• Cache metrics

When working with caching database, it may seem a simple task to store the frequently accessed data in cache and retrieve on subsequent calls instead of hitting our main DB. But, it's not that simple.

What if your cache storage is full, and you want to get rid of unnecessary cache data. In this case, how will you determine which data to be discarded and which data to be kept?

What if the data requested is not in cache. Should you save this after fetching from main DB or not?

What amount of your total data should you store in cache? How do you decide the storage size? 

These are some of the problems that we face when working with caching databases. 

Why cache DB like Redis or Memcached are faster than normal DB like Mongo or MySQL?

Simple answer to this question is, cache databases are in-memory databases and do not store data on disk. On the other hand, databases like MySQL & Mongo store data on disk storage. And because RAM is faster than Disk, it is ideal to make reads & writes faster. 

But RAM is also more expensive, therefore, it requires some consideration on what data to store and what data to discard. 

In-Memory storage is not the only way, we can also choose to store cache in disk, CDN, etc.

Cache Eviction Policies

Cache eviction policy is just deciding which data to discard and which data to keep when cache reaches its limit. 

The main benefit of doing this is, it optimizes our cache performance because we are removing unnecessary data. 

There are many policies available that we can choose from:

• LRU (Least Recently Used) - remove the data is used least frequently. This policy is based on the time. Example, if a user accesses a web page and is likely to visit it again, then it's a good idea to evict least recently used data.
• MRU (Most Recently Used) - remove the most recently used data. Example, if a user watches a movie, it's less likely that he will watch it again, in this case, it's best to evict the most recently used cache.
• LFU (Least Frequently Used) - this policy is based on how frequently same data is being accessed. If a data is used less frequently by users, we evict it to make space for new data. Example, databases can cache the results of queries that are more frequently used.
• MFU (Most Frequently Used) - this policy is the opposite of LFU and may seem unnecessary. But, there are times when this can be helpful. I don't have an example for this one, so if you have one, do share in comment :)
• FIFO (First In, First Out) - remove the data that got added first, to make space for the new data. It's similar to a queue. One simple example can be browser history, in which the oldest item in the history is removed to make room for newly visited page.
• LIFO (Last In, First Out) - it may seem similar to MRU, but instead of considering the frequency, we just remove the most recent data from cache.
• Size Based Eviction - in applications where data is large in size, we may choose to discard data with the largest size and to make room for new data. This ensures that cache storage is not full just by storing a few amount of data. Example, in a CDN, we can choose to discard the data according to the size and frequency to ensure we have space in cache for future data.
• Adaptive Replacement Cache - this strategy of cache eviction is based on algorithm that dynamically decides which data to discard and which data to keep by observing the workload. It maintains a list of frequently used and recently used data. You can explore it in details as this strategy can provide great performance in various scenarios but may take some efforts to setup.

Fun Fact: Caching is also used in problem solving and building efficient algorithms especially in Dynamic Programming.

What should be the size of our cache storage?

Now that we have an idea of what options we can have to discard the data we need, next thing that we need to know is what should be the size of our cache storage.
So, usually it depends on the use case and architecture of your system, but if you don't know what to start with, you can consider 20% of Daily Traffic as the amount of data to cache. Suppose your application has a traffic of around 10gb daily, then you can have the cache storage of 2gb.

What's a cache miss??

When you check the cache storage for data and you don't find one, that is called cache miss. This is when you make call to your main database to get the data and update cache.

Cache Invalidation Strategies

Cache invalidation is deciding when and how cached data should be considered stale or invalid. This makes that data no longer usable.

Key Difference b/w eviction and invalidation
The difference between cache invalidation and cache eviction is cache eviction is deciding what data to discard when cache storage is full, while cache invalidation is marking cache data as invalid.

Benefits of Cache invalidation:

• Cache invalidation affects the consistency of data served to the user.
• Maintains up to date data in cache, consistent with our main database.

Strategies

There are many strategies for cache invalidation based on different factors that caters to different use cases:

1. Time Based: In this strategy, we set an expiration on the cached data. Once the expiry is hit, data is marked as stale and we can either discard it or replace it with fresh data. It's a fairly simple and effective strategy. Key thing to keep in mind is to decide the expiration time.
2. Write Through: we update our cache and main database together when we receive new data. One example of this can be, suppose in a ecommerce website, products count can be updated in both cache and main database. Drawback of this strategy is that it increases the latency as data needs to be saved in cache and main DB before responding to user.
3. Write Back: This strategy can be applied in real time applications, where multiple users are collaborating. So, we start by storing the updates in cache storage, which results in faster reads and writes, and when a certain threshold is reached, we update the main database using our cache.
4. Write Behind: While write-back strategy waits for certain condition to trigger the update to main database, write-behind is based on eventually updating the main DB on specified intervals. Example, in online applications, data can be first written to cache, and can be stored in main database on specified intervals.
5. Key Based: In this strategy, cache data is stored against a key, which can be a unique identifier or a group of relevant attributes. When there are changes to the actual data, such as delete or update, cached data is also marked as invalid to ensure users receive the most current information.

Challenges with caching

Always keep in mind, whenever we introduce something in our system, however small it is, it always brings a level of complexity in our system. Same is true for caching.
Caching may seem simple on surface but due to its versatile nature, it presents several challenges that we need to address to actually derive the value out of it.

Let's see what are some common challenges with caching:

• Cache Invalidation: Above, we discussed some of the strategies that are used for cache invalidation. But choosing the right one is not easy. Different architectures require different type of strategies. So, try to look at all the possible scenarios and monitor the cache and data to come up with the right strategy.

Tip: You can use tools like DataDog, perf (Linux), New Relic etc. to monitor cache performance

• Cache Eviction: Similar to cache invalidation, choosing the right cache eviction policy is crucial. Don't just go with Least Recently Used eviction policy by default. Analyze data and your system requirements and then decide the best policy.

• Cache Security: Make sure your cache database is protected from unauthorized access. Therefore, implement proper access control and authentication system to ensure data privacy and integrity.

• Cache Expiration: This can be one of the hardest thing to achieve. If you set a short expiration, your chances of cache miss will increase. And if you set a long expiration, your data will become stale and inconsistent with the DB. So, give this also some thought when setting this up. Discuss with your team and monitor your cache to eventually reach the sweet spot.

Tip: The better you understand your application's data access patterns, the easier it is to setup your caching layer.

Cache Metrics

When trying to setup monitoring for your cache, there are a few metrics that you can focus on to get a better understanding. Our goal with cache metrics is to determine how well our caching strategy is performing under different workloads.

• Hit Ratio: Also known as Cache Hit Rate, helps us evaluate how well our cache system is performing.

Cache Hit Ratio(%) = (Number of Cache Hits / Total Number of Cache Accesses) * 100

where,
Number of cache hits is the total number of cache hits where data was found in cache, and
Total Number of cache accesses is the total number of cache hits made

Higher Hit Ratio means cache is used adequately and we are getting good performance by having reduced latency, better performance and less load on our backend. Cache Hit Ratio of 90-97% is ideal for a cache system.

• Cache Miss: It is opposite of Cache Hit and indicates that higher number of requests are not utilizing cache properly. Thus, we should look into our application's data access pattern.

• Cache Size: We can also monitor how much cache size is actually used by our system. Having a larger cache size means higher Hit Rate but that also increases memory usage of our system and may incur extra cost. So, by monitoring data and adjusting cache size, we can reduce our cost and still keep our system performant.

---

In summary, it's crucial to analyze your requirements thoroughly and determine the caching strategy that best fits your needs. Applying these concepts may require time and effort, but understanding and incorporating them into your coding practices will prove invaluable in the long run. Thank you for reading, and I hope this information aids you in your coding journey.