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.



More Information

PDF Of Conference Paper

Related Articles

RocksDB on Steroids

RocksDB - Facebook's Database Now Open Source

Microsoft Expands Redis Support

Apple Open Sources FoundationDB



To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.


Apache Software Foundation Is Worth $20 Billion

Yes, Apache is worth $20 billion by its own valuation of the software it offers for free. But what price can you realistically put on open source code?

Visual Basic Problems From Windows Update

There's a problem for applications based on Visual Basic for all Windows machines that have installed the cumulative updates for August. The issue, raised by Microsoft, says that apps may stop respond [ ... ]

More News





or email your comment to: