Design and implement a Caching library

One of the common question in a design round interview is to design a caching library. In this article, I have tried to address this question.

Disclaimer: I had failed in an interview with one of the FAANG companies, where this question was asked. After coming out of interview, I gave an afterthought, and came up with this design.

C++ implementation of this code is shared in git. github link for same is here

What is cache?

As in Wikipedia, a cache is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere.

In simple terms, a cache is a key value store to access frequently required data. Instead of accessing database or computing a data every time, such data can be stored in a cache, for easy retrieval.

Types of caches

In-Process cache:
These are local caches where an application instantiates, manages and runs it’s own cache, with code residing inside the application or as a 3rd party dynamic library. As cache shares memory with the application, multiple instances of application will be maintaining it’s own cache instance, leading to data duplication. Such kind of caches are useful in end user applications like mobile apps, or web apps.

Distributed Caching:
When we are dealing with back end applications catering thousands to million requests per seconds, we would require dedicated machines to handle caching. Also, with multiple nodes trying to access database, a common cache across instances becomes a necessity. In such cases, a separate hardware with dedicated resources like flash, SSD, etc, can be used for better and faster throughput.

In this article, we are dealing with design of an in-process cache.

Cache hit, miss, eviction

Data in Cache is stored as key-value format, where data is stored as value and a unique key is associated with it to access. If requested key is present, cache hit occurs and associated value is returned. If requested key is not present, cache miss occurs. In this case, required value is calculated or fetched from database, and put back in cache.
However, Cache will be having limited memory. Hence to store the new value, some existed key-value pair should be removed. This is called eviction. There are various eviction strategies: Least Recently Used (LRU), Least Frequently Used (LFU), Most Recently Used (MRU), etc. In this article, we target LRU and LFU.

Cache library Design Overview

As an end user, what all functions are to be exposed?
1. put(key, value) to create or update a key-value pair
2. get(key) to return a value for a given key
3. delete(key) to hard delete a particular value pair
4. clear() to clear all data from cache.

Data in cache might turn stale after some time. Actual data in database would have changed. For some data, like company logo, or product images, data does not change very often. In such cases, a TTL (Time To Live) comes handy.

To implement TTL, signature of put would change, where another argument for TTL will be sent.

Implement different Eviction strategy

In current article, we try to implement 2 eviction strategies. LRU and LFU. To achieve the same, factory pattern will be used. A virtual base class of Cache will be implemented, with above mentioned functions as interface and the 2 different cache implementations will inherit from this.

// cache.h
#pragma once
#include <string>
#include <memory>
constexpr auto MAX_CACHE_SIZE = 4096;
using namespace std;
enum CacheType {
LRU_CACHE,
LFU_CACHE
};
class Cache;
typedef shared_ptr<Cache> CachePtr;
class Cache
{
public:
    Cache(int size = MAX_CACHE_SIZE);
    virtual string get(string key) = 0;
    virtual void put(string key, string value, int ttl = -1) = 0;
    virtual void deleteKey(string key) = 0;
    virtual void clear() = 0;
    static CachePtr getCache(CacheType c, int size = MAX_CACHE_SIZE);
    ~Cache();
};

LRU Cache Implementation

Data-structures
Queue (Using Doubly Linked List) — The node value containing key and value pair is stored as a queue. The queue is implemented using a Doubly Linked List (DLL), which allows easy manipulation of the queue.
Map — This has map of key to the node in DLL.

Implementation details
put: Any new entry to the cache is put to the back of the DLL. If the size of DLL exceed the max cache size, eviction of front of the node is done. This ensures that the oldest node is removed, while newest entries are at the back of the queue. When there is an update, the value of the node is changed, and the node is pushed to the back of the queue.
get: Using the map, the DLL node extracted using the key. The value to the key can be extracted using this node. Also, node is taken out of DLL and pushed to the back of the DLL, making it the most recent node.
delete: The node is removed from DLL, and corresponding entry is deleted from the map
clear: All nodes of DLL is deleted, and the map is emptied

Code for this is check pointed here

LFU Cache Implementation

Data-structures
Map— Key to Value map is used
Map — Key to count map. The count here is the frequency count of usage/access of the key.
Map — Count to Key map. As this is a one to many relation (Many keys can have same frequency count), keys are stored in doubly linked list of keys

Implementation details
put: Any new entry to the cache, a key-value pair is added to corresponding map. In count map, a new entry with count 1 is added at the back of the DLL. In count to key map, a new entry of key is added against entry of 1. If the size exceeds max size, we go to the lowest count entry in count to key map. Then the key is removed from front of the queue. This ensures that Lest recently used in the least frequently used keys is removed. Corresponding entries of other maps are removed
get: key-value map contains the return value. We then increment the frequency count in key to count map. In count to key map, we remove entry from old count DLL and add to new count DLL
delete: key value is deleted from all maps
clear: All nodes of all DLL in count-key map are deleted, and all maps are emptied

The code is check pointed here.

TTL Implementation

There are many ways of implementing TTL.
One of the most common way is a reactive way, wherein when get of the key is called ttl is checked and is and deleted is key has expired.
Another way is a proactive way where, entry is deleted as soon as expiry is hit.
In this implementation, we have taken pseudo proactive way, where whenever any call is made to the library, all expired entries are removed.

Details
A min heap is maintained to store TTL values. Top of the tree denotes which is the next key to be removed. During any call to the library, Top of the heap is examined and corresponding entries are deleted

Conclusion

We have discussed here one of the ways of designing a Cache. Neither the design is feature complete nor the code is production ready. It is just a proof of concept. The final code is shared here