Microsoft Research Blog

Microsoft Research Blog

The Microsoft Research blog provides in-depth views and perspectives from our researchers, scientists and engineers, plus information about noteworthy events and conferences, scholarships, and fellowships designed for academic and scientific communities.

Microsoft Unveils FASTER – a key-value store for large state management

June 8, 2018 | By Microsoft blog editor

At SIGMOD 2018, a team from Microsoft Research will be presenting a new embedded key-value store called FASTER, described in their paper “FASTER: A Concurrent Key-Value Store with In-Place Updates”. As its name suggests, FASTER makes a major leap forward in terms of supporting fast and frequent lookups and updates of large amounts of state information – a particularly challenging problem for applications in the cloud today. For example, in scenarios such as Internet-of-Things, billions of devices report and update state such as per-device performance counters. In advertising platforms, user activity such as ad and search result clicks drive the creation and frequent update of per-user behavior models and per-ad statistics.

Applications that maintain such state typically scale out on multiple machines for memory, severely underutilizing other resources such as storage and networking on the machine. FASTER takes a different approach; it leverages the temporal locality inherent in all these applications to control the in-memory footprint of the system and cache the frequently accessed values without maintaining any fine-grained statistics per record. FASTER is a single-node shared memory key-value store library that makes two important technical innovations:

  • It proposes a cache-friendly and concurrent latch-free hash index designed to grow and shrink dynamically while maintaining logical pointers to records in a log.
  • It proposes a new concurrent hybrid log record allocator abstraction backing the index that spans fast storage (such as cloud storage and SSD) and main memory.
    The FASTER hash index is an array of cache-line-sized hash buckets, each with 8-byte entries that hold hash tags and logical pointers to records that are stored separately in the hybrid log. All operations on the hash table are latch-free, using atomic compare-and-swap instructions for very high performance. Keys are not stored as part of the index structure in order to keep its memory footprint small.

While traditional key-value stores have used log-structured record organizations, the hybrid log of FASTER seamlessly combines log-structuring with read-copy-updates (that are good for external storage) and in-place updates (that are good for in-memory performance). Specifically, the head of the hybrid log on storage uses a read-copy-update strategy for updating records, whereas the tail of the hybrid log in main memory 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 record organization captures 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. Maintaining this elegant design in a concurrent latch-free setting required solving new technical challenges and proposing an extended epoch-protection-based concurrent system design framework that is detailed in the paper.

The result? FASTER can outperform even pure in-memory data structures such as the Intel TBB hash map when the working set fits in memory. Further, it outperforms today’s key-value stores and caching systems such as RocksDB and Redis by several orders-of-magnitude.

To support failure recovery, FASTER incorporates a recovery strategy that can bring the system back to a recent consistent state at low cost, without blocking or having to create a separate “write ahead log”, a recovery mechanism used in traditional database systems. Researchers are currently working on writing a follow up paper that describes this innovation in more detail. They are also working on using the key-value store in systems at Microsoft, including within their previous research project, Trill (site | blog post), a highly successful and widely deployed incremental stream analytics library.

Up Next

Data platforms and analytics

Research Collection: Tools and Data to Advance the State of the Art

Editor’s Note: In the diverse and multifaceted world of research, individual contributions can add up to significant results over time. In this new series of posts, we’re connecting the dots to provide an overview of how researchers at Microsoft and their collaborators are working towards significant customer and societal outcomes that are broader than any […]

Microsoft blog editor

Data platforms and analytics, Programming languages and software engineering, Systems and networking

Project Orleans and the distributed database future with Dr. Philip Bernstein

Episode 114 | April 8, 2020 - Forty years ago, database research was an “exotic” field and, because of its business data processing reputation, was not considered intellectually interesting in academic circles. But that didn’t deter Dr. Philip Bernstein, now a Distinguished Scientist in MSR’s Data Management, Exploration and Mining group, and a pioneer in the field. Today, Dr. Bernstein talks about his pioneering work in databases over the years and tells us all about Project Orleans, a distributed systems programming framework that makes life easier for programmers who aren’t distributed systems experts. He also talks about the future of database systems in a cloud scale world, and reveals where he finds his research sweet spot along the academic industrial spectrum.

Microsoft blog editor

Data platforms and analytics, Programming languages and software engineering, Security, privacy, and cryptography, Systems and networking

Democratizing data, thinking backwards and setting North Star goals with Dr. Donald Kossmann

Episode 107 | February 19, 2020 - Dr. Donald Kossmann is a Distinguished Scientist who thinks big, and as the Director of Microsoft Research’s flagship lab in Redmond, it’s his job to inspire others to think big, too. But don’t be fooled. For him, thinking big involves what he calls thinking backwards, a framework of imagining the future, defining progress in reverse order and executing against landmarks along an uncertain path. On the podcast, Dr. Kossmann reflects on his life as a database researcher and tells us how Socrates, an innovative database-as-a-service architecture, is re-envisioning traditional database design. He also reveals the five superpowers of Microsoft Research and how we can improve science… with marketing.

Microsoft blog editor