Loading...
A user could store key-value pair in cache to increase write/read efficiency
The system should have high consistency and availability
Estimate the scale of the system you are going to design...
put(key, value)
get(key)
key: string
value: string
In memory cache
hashmap
key is string
value is linked list
The LB balances traffic through consistent hashing. The servers are the key component to process key, value pairs. It will also hold Cache.
Cache will be in RAM as they provide high speed access. Note, in our design, the cache will be storing data. Another service will be handling persist data into database.
The client sends a key to the server, it will first go to LB, which separate the traffic using consistent hashing. Each server will handle a subset of all possible keys.
Each server has a dedicated cache and another service which consistently persist data in cache to database.
When getting the key, it first goes to the cache to find whether the key exists in the cache. If cache miss, it will go to the database for finding the key.
Also add a TTL.
The Cache should also have snapshot and write ahead log WAL. This could ensure data consistency. If any failure happens, one can recover from the logs and snapshots.
For the cache, normally it is in memory cache. We can use a hash table. The hashtable will first hash the key to find the right bucket by taking modulation. Each bucket will be a double linked list to store the memory address.
The eviction of the data will be using LFU. We will evict least used data when memory reaches certain limit. To do so, we will have a hashtable and a double linked list. When an item is put into the cache, it will append the data to the back of the linked list. If it exists already (by searching through hashtable), we can easily find the memory chunk. We just move that memory chunk to the back of the table with latest data if needed.
When eviction happens, we always evict the front of the linked list.
Explain any trade offs you have made and why you made certain tech choices...
A single server could fail
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
We can have a mirror server for each server. In case of a server failure, we can immediately replace the failed server.