Cache craftiness for fast multicore key-value storage

By Yandong Mao, Eddie Kohler, Robert Morris. European Conference on Computer Systems, 2012

528 citations recorded by the source corpus.

We present Masstree, a fast key-value database designed for SMP machines. Masstree keeps all data in memory. Its main data structure is a trie-like concatenation of B+-trees, each of which handles a fixed-length slice of a variable-length key. This structure effectively handles arbitrary-length possiblybinary keys, including keys with long shared prefixes. +-tree fanout was chosen to minimize total DRAM delay when descending the tree and prefetching each tree node. Lookups use optimistic concurrency control, a read-copy-update-like technique, and do not write shared data structures; updates lock only affected nodes. Logging and checkpointing provide consistency and durability. Though some of these ideas appear elsewhere, Masstree is the first to combine them. We discuss design variants and their consequences. On a 16-core machine, with logging enabled and queries arriving over a network, Masstree executes more than six million simple queries per second. This performance is comparable to that of memcached, a non-persistent hash table server, and higher (often much higher) than that of VoltDB, MongoDB, and Redis.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/02238222335347bf16048b9bdd306aab48c98002

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Using One-Sided RDMA Reads to Build a Fast, CPU-Efficient Key-Value Store (2013, methodology): “Logging: By default, Pilaf server asynchronously logs all put and delete operations to the local disk, similar to the logging facility in other key-value stores including Redis [24], Masstree [19] and LevelDB [8].”
Performance Isolation and Fairness for Multi-Tenant Cloud Storage (2012, unknown): “It is designed primarily to serve keys out of an in-memory cache for high throughput, and only asynchronously writes data to disk (much like Masstree [19] and the MyISAM storage engine in MySQL).”
Speedy transactions in multicore in-memory databases (2013, background): “A number of recent systems have proposed storage abstractions for main-memory and multicore systems.”
IncBricks: Toward In-Network Computation with an In-Network Cache (2017, methodology): “To reduce these components, we could apply kernel by-pass techniques[1] or use a higher-performance key-value store instead (e.g., MICA[33] or Masstree[35]).”
Flat combining and the synchronization-parallelism tradeoff (2010, methodology): “Masstree enables a very high fanout (2 64 ) by using a B+ tree at each trie node [26].”
In-Memory Big Data Management and Processing: A Survey (2015, background): “There are key-value stores such as Redis [66], RAMCloud [2], MemepiC [60], [138], Masstree [249], MICA [64], Mercury [250], Citrusleaf/Aerospike [34], Kyoto/Tokyo Cabinet [251], Pilaf [252], document stores such as MongoDB [65], Couchbase [253], graph databases such as Trinity [46], Bitsy [254], RDF”
Datacenter RPCs can be General and Fast (2018, methodology): “In this section, we evaluate whether eRPC can be used in real applications with unmodi ed existing storage software: We build a state machine replication system using an opensource implementation of Raft [48], and a networked ordered key-value store using Masstree [43].”
ALEX: An Updatable Adaptive Learned Index (2019, background): “Masstree [26] andAdaptive Radix Tree [22] combine the ideas of B+Tree and trie to reduce cache misses.”
WiscKey (2016, background): “Many proposed techniques seek to overcome the scalability bottlenecks of in-memory key-value stores, such as Masstree [Mao et al. 2012], MemC3 [Fan et al. 2013], Mem-cache [Nishtala et al. 2013], MICA [Lim et al. 2014], and cLSM [Golan-Gueta et al. 2015].”