{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:35:56Z","timestamp":1780346156511,"version":"3.54.1"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,12,8]],"date-time":"2018-12-08T00:00:00Z","timestamp":1544227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>In this article, we show that key-value stores backed by a log-structured merge-tree (LSM-tree) exhibit an intrinsic tradeoff between lookup cost, update cost, and main memory footprint, yet all existing designs expose a suboptimal and difficult to tune tradeoff among these metrics. We pinpoint the problem to the fact that modern key-value stores suboptimally co-tune the merge policy, the buffer size, and the Bloom filters\u2019 false-positive rates across the LSM-tree\u2019s different levels.<\/jats:p>\n          <jats:p>We present Monkey, an LSM-tree based key-value store that strikes the optimal balance between the costs of updates and lookups with any given main memory budget. The core insight is that worst-case lookup cost is proportional to the sum of the false-positive rates of the Bloom filters across all levels of the LSM-tree. Contrary to state-of-the-art key-value stores that assign a fixed number of bits-per-element to all Bloom filters, Monkey allocates memory to filters across different levels so as to minimize the sum of their false-positive rates. We show analytically that Monkey reduces the asymptotic complexity of the worst-case lookup I\/O cost, and we verify empirically using an implementation on top of RocksDB that Monkey reduces lookup latency by an increasing margin as the data volume grows (50--80% for the data sizes we experimented with). Furthermore, we map the design space onto a closed-form model that enables adapting the merging frequency and memory allocation to strike the best tradeoff among lookup cost, update cost and main memory, depending on the workload (proportion of lookups and updates), the dataset (number and size of entries), and the underlying hardware (main memory available, disk vs. flash). We show how to use this model to answer what-if design questions about how changes in environmental parameters impact performance and how to adapt the design of the key-value store for optimal performance.<\/jats:p>","DOI":"10.1145\/3276980","type":"journal-article","created":{"date-parts":[[2018,12,10]],"date-time":"2018-12-10T13:09:16Z","timestamp":1544447356000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":58,"title":["Optimal Bloom Filters and Adaptive Merging for LSM-Trees"],"prefix":"10.1145","volume":"43","author":[{"given":"Niv","family":"Dayan","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1837-0010","authenticated-orcid":false,"given":"Manos","family":"Athanassoulis","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stratos","family":"Idreos","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757810"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733096"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201910)","author":"Anand A."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629577"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR\u201913)","author":"Anderson M. R."},{"key":"e_1_2_1_6_1","unstructured":"Apache. Accumulo. Retrieved from https:\/\/accumulo.apache.org\/.  Apache. Accumulo. Retrieved from https:\/\/accumulo.apache.org\/."},{"key":"e_1_2_1_7_1","unstructured":"Apache. Cassandra. Retrieved from http:\/\/cassandra.apache.org.  Apache. Cassandra. Retrieved from http:\/\/cassandra.apache.org."},{"key":"e_1_2_1_8_1","unstructured":"Apache. HBase. Retrieved from http:\/\/hbase.apache.org\/.  Apache. HBase. Retrieved from http:\/\/hbase.apache.org\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465296"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989414"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699484"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2912569"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT\u201916)","author":"Athanassoulis M."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201909)","author":"Badam A."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201917)","author":"Balmau O."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229873"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Brodal G. S."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201913)","author":"Bronson N. G."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735477"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Buchsbaum A. L."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201918)","author":"Chan H. H. W."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Chang F."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213947"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915219"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921015"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989327"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the ICSOC\/ServiceWave 2009 WorkshopsService-Oriented Computing. 197--207","author":"Dejun J.","year":"2009"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR\u201917)","author":"Dong S."},{"key":"e_1_2_1_39_1","unstructured":"Facebook. MyRocks. Retrieved from http:\/\/myrocks.io\/.  Facebook. MyRocks. Retrieved from http:\/\/myrocks.io\/."},{"key":"e_1_2_1_40_1","unstructured":"Facebook. RocksDB. Retrieved from https:\/\/github.com\/facebook\/rocksdb.  Facebook. RocksDB. Retrieved from https:\/\/github.com\/facebook\/rocksdb."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_42_1","volume-title":"Memcached: A distributed memory object caching system. White Paper.","author":"Fitzpatrick B.","year":"2011"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_1_44_1","unstructured":"Google. LevelDB. Retrieved from https:\/\/github.com\/google\/leveldb\/.  Google. LevelDB. Retrieved from https:\/\/github.com\/google\/leveldb\/."},{"key":"e_1_2_1_45_1","first-page":"64","article-title":"The periodic table of data structures","volume":"41","author":"Idreos S.","year":"2018","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3199671"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201997)","author":"Jagadish H. V."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201999)","author":"Jermaine C."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0171-7"},{"key":"e_1_2_1_50_1","unstructured":"B. C. Kuszmaul. 2014. A comparison of fractal trees to log-structured merge (LSM) trees. Tokutek White Paper.  B. C. Kuszmaul. 2014. A comparison of fractal trees to log-structured merge (LSM) trees. Tokutek White Paper."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920990"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Lim H."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043558"},{"key":"e_1_2_1_55_1","unstructured":"LinkedIn. 2016. Online reference. Retrieved from http:\/\/www.project-voldemort.com.  LinkedIn. 2016. Online reference. Retrieved from http:\/\/www.project-voldemort.com."},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Lu L."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201916)","author":"Papagiannis A."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137659"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_2_1_61_1","unstructured":"Redis. Online reference. Retrieved from http:\/\/redis.io\/.  Redis. Online reference. Retrieved from http:\/\/redis.io\/."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_64_1","volume-title":"Bitcask: A log-structured hash table for fast key\/value data. Basho White Paper.","author":"Sheehy J.","year":"2010"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201913)","author":"Shetty P."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_1_67_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE\u201917)","author":"Thonangi R."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807194"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_2_1_70_1","unstructured":"WiredTiger. Source Code. Retrieved from https:\/\/github.com\/wiredtiger\/wiredtiger.  WiredTiger. Source Code. Retrieved from https:\/\/github.com\/wiredtiger\/wiredtiger."},{"key":"e_1_2_1_71_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201915)","author":"Wu X."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276980","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276980","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:41Z","timestamp":1750208261000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276980"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,8]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3276980"],"URL":"https:\/\/doi.org\/10.1145\/3276980","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,8]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}