|Microsoft Showcases Key Value Store|
|Written by Kay Ewbank|
|Tuesday, 12 June 2018|
Researchers from Microsoft have presented a new embedded key-value store called FASTER at SIGMOD 2018.
The key value store is innovative in that it supports the use of in-place updates, meaning it can support fast and frequent lookups and updates of large amounts of state information. The developers say that they see this as being particularly useful in scenarios such as Internet-of-Things where billions of devices report and update state such as per-device performance counters.
At the moment, if an application needs to maintain such state, it will typically scale out on multiple machines for memory, under utilizing other resources such as storage and networking on the machine. Such applications tend to have temporal locality - data or resources are reused within a small time frame. Faster makes use of this to control the in-memory footprint of the system and cache the frequently accessed values without maintaining any fine-grained statistics per record.
It does this with a combination of an in-memory allocator that handles data access and in-place updates to records, alongside an append-only log-structured allocator that can handle data larger than main-memory, but without in-place updates.
Faster has two technical innovations. Firstly, its hash index is cache-friendly and concurrent latch-free, and is designed to grow and shrink dynamically while maintaining logical pointers to records in a log. The second change is a concurrent hybrid log record allocator that returns logical or physical memory pointers, and works alongside the index so spans fast storage (such as cloud storage and SSD) and main memory.
The head of the hybrid log is located in storage, and uses a read-copy-update strategy for updating records. The tail of the hybrid log is located in main memory and uses in-place updates. In between these two regions lies a read-only region in memory that provides hot records a “second chance” to be quickly copied back to the tail.
This mix of locations and techniques utilizes the temporal locality of updates, allows records to spill to sequential storage efficiently and enables a natural clustering of hot records in memory for fast in-place updates.
The researchers say that Faster can outperform even pure in-memory data structures such as the Intel TBB hash map when the working set fits in memory. They say it also outperforms today’s key-value stores and caching systems such as RocksDB and Redis by several orders-of-magnitude.
or email your comment to: firstname.lastname@example.org