The Microsoft research team announced a new key-value store named FASTER at SIGMOD 2018, in June. FASTER offers support for fast and frequent lookups of data. It also helps with updating large volumes of state information which poses a problem for cloud applications today.
Let’s consider IoT as a scenario. Here billions of devices report and update state like per-device performance counters. This leads to applications underutilizing resources such as storage and networking on the machine. FASTER helps solve this problem as it makes use of the temporal locality in these applications for controlling the in-memory footprint of the system.
According to Microsoft, “FASTER is a single-node shared memory key-value store library”. A key-value store is a NoSQL database which makes use of simple key/value method for data storage. It consists of two important innovations:
- A cache-friendly, concurrent and latch-free hash index. It maintains logical pointers to records in a log. The FASTER hash index refers to an array of cache-line-sized hash buckets, each with 8-byte entries to hold hash tags. It also consists of logical pointers to records that have been stored separately.
- A new concurrent and hybrid log record allocator. This helps in backing the index which includes fast storage (such as cloud storage and SSD) and main memory.
What makes FASTER different?
The traditional key-value stores make use of log-structured record organizations. But, FASTER is different as it has a hybrid log that combines log-structuring with read-copy-updates (good for external storage) and in-place updates (good for in-memory performance). So, the hybrid log head which lies in storage uses a read-copy-update whereas the hybrid log tail part in main memory uses in-place updates. There is a read-only region in memory that lies between these two regions. It provides the core records another chance to be copied back to the tail. This captures temporary location of the updates and allows a natural clustering of hot records in memory.
As a result, FASTER is capable of outperforming even pure in-memory data structures like the Intel TBB hash map. It also performs far better than today’s popular key-value stores and caching systems like the RocksDB and Redis, says Microsoft.
Other than that, FASTER also provides support for failure recovery as it consists of a recovery strategy in place which helps bring back the system to a recent consistent state at low cost. This is different than the recovery mechanism in traditional database systems as it does not involve blocking or creating a separate “write-ahead log”.
For more information, check out the official research paper.