FASTER: A Concurrent Key-Value Store with In-Place Updates

Over the last decade, there has been a tremendous growth in data-intensive applications and services in the cloud. Data is created on a variety of edge sources, e.g., devices, browsers, and servers, and processed by cloud applications to gain insights or take decisions. Applications and services either work on collected data, or monitor and process data in real time. These applications are typically update intensive and involve a large amount of state beyond what can fit in main memory. However, they display significant temporal locality in their access pattern. This paper presents FASTER, a new key-value store for point operations. FASTER combines a highly cache-optimized concurrent hash index with a “hybrid log”: a concurrent log-structured record store that spans main memory and storage, while supporting fast in-place updates of the hot set in memory. FASTER extends the standard key-value store interface to handle read-modify-writes, blind updates, and CRDT-based updates. Experiments show that FASTER achieves orders-of-magnitude better throughput – up to 160M operations per second on a single machine – than alternative systems deployed widely today, and exceeds the performance of pure in-memory data structures when the workload fits in memory.