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.


faster

 

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.

faster

 

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.

Banner


Remembering Grace Hopper On Her 114th Anniversary
09/12/2024

Today sees the start of Computer Science Education Week and  the 2024 Hour of Code. These educational event are timed to coincide with Grace Hopper's birthday on January 9th, 1906 due to her conc [ ... ]



Wasmer 5 Adds iOS Support
12/11/2024

The Wasmer team has released Wasmer 5.0. The WebAssembly runtime adds experimental support for more back ends including V8, Wasmi and WAMR. It also now has iOS support, and upgraded compilers includin [ ... ]


More News

espbook

 

Comments




or email your comment to: comments@i-programmer.info