# Cache Craftiness for Fast Multicore Key-Value Storage

 Title: Cache Craftiness for Fast Multicore Key-Value Storage Author: Kohler, Edward W; Morris, Robert; Mao, Yandong Note: Order does not necessarily reflect citation order of authors. Citation: Mao, Yandong, Edward W. Kohler, and Robert Morris. 2012. Cache craftiness for fast multicore key-value storage. In EuroSys'12: Proceedings of the 7th ACM European Conference on Computer Systems: April 10-13, 2012, Bern, Switzerland, ed. P. Felber, F. Bellosa, and H. Bos, 183-196. New York: Association for Computing Machinery. Full Text & Related Files: 80452906.pdf (266.7Kb; PDF) Abstract: 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. Published Version: doi:10.1145/2168836.2168855 Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:10728827 Downloads of this work: