Loading...
Let's assume we want to scale up to 1TB of data stored in cache.
Let's assume a modern server can have up to 64GB of free memory.
It would require 1024 / 64 = 16 servers to store the entire data set.
We will design this so that these parameters can change. But let's use these numbers as our guideline.
put(key, value, ttl=never)
This sets value of the object specified by the key. If ttl is set, the cache object will expire in ttl milliseconds. If ttl is not set, it won't expire. (But it may be evicted.)
get(key)
This returns the value of the cache object specified by the key.
These calls are made via a communication protocol optimized for performance and efficiency. ProtoBuf should be a good choice.
As the hard requirement for Web Cache is being fast in response, the main storage mechanism should be the memory (RAM) in the cache servers.
For fault tolerance, we would like to make sure the data survive even when the cache servers crash.
TODO: file of database for persistence?
Cache Service does not receive messages from API Gateway directly. Cache Service's clients are other Web Services in the same data center.
Web Services send get(), put() requests to Cache Service on ProtoBuf.
[You may notice the architecture diagram is relatively simple, with fewer boxes compared to other problems. This is fine. Simplicity is one of the hallmark of a senior engineer. You do not need to add unnecessary boxes.]
Some Web Service receives requests from API Gateway.
Web Service wants to use cache to improve performance. It fetches the information which determines which Cache Server contains a certain cache key range. Web Service uses this information to determine which Cache Server to talk to.
Web Service makes get() or put() request over ProtoBuf, and Cache Service responds.
[Senior-level deep dive topic - This is one of the important points of this question.]
Cache Service has to implement data structures and algorithms to make both API (get() and put()) fast.
For get(), a hash map would be a good data structure. It provides a look up with the constant computation order O(1).
The hash map also provides O(1) access for put() , if all it has to do is to write (add or update) a cache object.
However, by its definition, cache will not be large enough to store the whole data set. Its essential tradeoff is to be fast by trading off size (compared to slower and larger SSDs and hard disks.).
Therefore, if put() needs to create a new cache object while the cache is full, we need to remove (evict) some objects from the cache. There are several eviction policies - Least Recently Used, Least Frequently Used, First In First Out, etc. Every policy has its own use case, but in this solution we focus on LRU, as it is a very popular one.
LRU can be implemented by introducing the second data structure, doubly linked list. The most recently used object is pushed into the top of the list. The least recently used object ends up in the end of the list, where it can be removed when cache is full.
However, in a high throughput cache system like we are building, the cost of maintaining the list would become a bottleneck; it takes, for example, a handful of write operations to remove a node from the end, and another handful to put a new at the head.
Therefore, a more practical approach is a pseudo-LRU algorithm. This does not have a doubly linked list. Instead, the system would randomly select some (e.g. 5) objects, and evict the least recently used object from the sampled objects.
This would be faster than the strict LRU. Link maintenance overhead is eliminated from get() and put(). put() requires random sampling when eviction happens, but we can reduce this possibility by carefully planning required cache size.
[Senior-level deep dive topic]
Since the entire data set we want to cache would not fit in one Cache Server's main memory, we would have to partition data and store them in multiple Cache Servers.
Cache key (which we use in put() and get() to specify the cache object) is a good choice of the partitioning key. As our data access pattern is simple (look up an object with the key), Client can decide which Cache Server to talk by using this key.
But a naive partitioning approach (e.g. take a hash of the key, divide it by 16, and assign the server using the reminder) would have problems:
Consistent Hashing is a good approach to solve this.
Then the next question is, how do we implement Consistent Hashing? It requires a shared configuration all the Clients can look up quickly to determine which hash range belongs to which Cache Server.
One approach is a centralized configuration manager, e.g., ZooKeeper. It provides fault tolerant and scalable configuration in a distributed environment.
Another approach is each client implementing a gossip protocol.
The gossip protocol would be even more scalable than the centralized config management approach. However, the gossip protocol would be more complex to implement, and it would take some time for the clients to reach consensus.
As we expect a modest number of cache servers (order of 100s), we believe the centralized config management approach would suffice.
[Junior-level deep dive topic.]
Cache Servers store the data in main memory for high performance. But the challenge is that, if the server crashes, all the data it stores will be lost. This is unacceptable, as server crash is common in a distributed system.
Read replicas of Cache Servers provide the first line of defense. Read replicas maintain a copy of the data the primary Cache Server has. Write requests go to the primary. Read requests can be handled by both primary and secondary. When the primary crashes, one of the secondary replicas can take over quickly because it already has the same data.
Read replicas also improve the scalability and performance of the system by serving get() requests.
[Mid-level deep dive topic]
Even with read replicas, data might still be lost, for example, the data center, which hosts both primary and read replicas, lose power by an accident.
We could implement persistence feature. Entire cache content (snapshot) can be written to a disk in a periodic fashion. Or cache server can record each write operation to an append only log file. The tradeoff of these approach are:
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?