Loading...
The user is able to create, get, delete and update a key with minimal latency.
The system should handle concurrent updates.
The system should be partition tolerant
The system should have low latency.
The system should have high availability.
Suppose there are 10M users, reading 100 keys per day and 10 writes per day.
Read QPS: 11.5k
Write QPS: 1.5k
Also needs to estimate space required per day.
set(key, value)
get(key)
delete(key)
compare_and_set(key, expected_value, value)
Database is just key-value store.
LB is to balance customer traffic. It will forward the traffic to the right server. We can use key as the hashing key to balance the traffic.
The server is the application server which talks to the in memory cache. This is for fast access and write the record.
The database stores the file. We can leverage a distributed file system as database. Each file contains content and a skip list.
Persistence Service has 2 functions: persist data in cache to memory and regularly merges the datafiles in the database.
When a user tries to put the data, it first goes to the right server according to consistent hashing. Next, it directly append the data into the end of the list. The cache is a list of data.
When delete data, we simply append a key-value pair of (key, null) to the end of the list.
When we try to get, we first search the list reversely to find if the value is in cache. If the value is in cache, return the latest one. If it is not, we reversely go to the files in database and search if the key exists in the database file through a binary search.
Compare and set runs through get first and set next.
When a new key is put into the memory, it appends to the current list in the cache. The list is not sorted. Once a certain limit of the in-memory cache has been reached, Persistence Service will sort it and into the file and store in the Database. On a regular basis, the PS will merge the files in the Database.
In the file, it is very important to store the indexing. Normally a skip list is used because disk read is very slow.
We can also use bloom filter to quickly check if a file exists in the database.
Ensure compare_and_set is automic. We can add a lock on the key. This will slow the service down. May also fall into cases of dead lock. We can also use versioned control. When we read the data, we check the version. When we write, we do another check if the latest version is the same as the one when we read.
We have the following challenges:
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?