{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:05Z","timestamp":1750221005936,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2017R1D1A1B03031494","NRF-2018R1A5A1060031","NRF-2017R1E1A1A01077410"],"award-info":[{"award-number":["NRF-2017R1D1A1B03031494","NRF-2018R1A5A1060031","NRF-2017R1E1A1A01077410"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,3,26]]},"abstract":"<jats:p>In this paper, we examine the design tradeoffs of existing in-memory data structures of a state-of-the-art key-value store. We observe that no data structures provide both fast point-accesses and consistent ranged- retrievals, and naive amalgamations of existing structures fail to get the best of both worlds. Furthermore, our experiments reveal a performance anomaly when increasing the memory size: as more key-value pairs are maintained in memory, the shortcomings of the data structures exacerbate. To address the above problems, we present TeksDB, a fast and consistent key-value store with a novel in-memory data structure, which effciently handles both point- and ranged- accesses at a modest increase in memory footprint. Our evaluation demonstrates that TeksDB outperforms RocksDB by 3.6\u00d7, 9\u00d7, and 4.5\u00d7 for get, scan, and range_query, respectively. The effectiveness of TeksDB extends to real-world workloads, achieving up to 3.3\u00d7 speedup for YCSB.<\/jats:p>","DOI":"10.1145\/3322205.3311079","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T13:12:37Z","timestamp":1585228357000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["TeksDB"],"prefix":"10.1145","volume":"3","author":[{"given":"Youil","family":"Han","sequence":"first","affiliation":[{"name":"Chungbuk National University, Cheongju, South Korea"}]},{"given":"Bryan S.","family":"Kim","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, South Korea"}]},{"given":"Jeseong","family":"Yeon","sequence":"additional","affiliation":[{"name":"Chungbuk National University, Cheongju, South Korea"}]},{"given":"Sungjin","family":"Lee","sequence":"additional","affiliation":[{"name":"DGIST, Daegu, South Korea"}]},{"given":"Eunji","family":"Lee","sequence":"additional","affiliation":[{"name":"Soongsil University, Seoul, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ardb. 2013. Ardb. https:\/\/github.com\/yinqiwen\/ardb .  Ardb. 2013. Ardb. https:\/\/github.com\/yinqiwen\/ardb ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"volume-title":"Disk and Log in Log Structured Key-Value Stores. In 2017 USENIX Annual Technical Conference, USENIX ATC 2017","year":"2017","author":"Balmau Oana","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064193"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223785"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/356842.356846"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742783"},{"key":"e_1_2_1_8_1","unstructured":"cameron314. 2014. Concurrent Queue. https:\/\/github.com\/cameron314\/concurrentqueue.git.  cameron314. 2014. Concurrent Queue. https:\/\/github.com\/cameron314\/concurrentqueue.git."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_13_1","unstructured":"Facebook. 2012. RocksDB. https:\/\/github.com\/facebook\/rocksdb .  Facebook. 2012. RocksDB. https:\/\/github.com\/facebook\/rocksdb ."},{"key":"e_1_2_1_14_1","unstructured":"Facebook. 2018. MyRocks. https:\/\/myrocks.io .  Facebook. 2018. MyRocks. https:\/\/myrocks.io ."},{"key":"e_1_2_1_15_1","unstructured":"The Apache Software Foundation. 2008. Cassandra. https:\/\/github.com\/apache\/cassandra.  The Apache Software Foundation. 2008. Cassandra. https:\/\/github.com\/apache\/cassandra."},{"key":"e_1_2_1_16_1","unstructured":"FoundationDB. 2013. FoundationDB. https:\/\/www.foundationdb.org\/.  FoundationDB. 2013. FoundationDB. https:\/\/www.foundationdb.org\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_1_18_1","unstructured":"Google. 2011. LevelDB. https:\/\/github.com\/google\/leveldb .  Google. 2011. LevelDB. https:\/\/github.com\/google\/leveldb ."},{"volume-title":"Proceedings of the 12th USENIX conference on File and Storage Technologies, FAST 2014","year":"2014","author":"Harter Tyler","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","unstructured":"HyperDex. 2011. HyperLevelDB. https:\/\/github.com\/rescrv\/HyperLevelDB .  HyperDex. 2011. HyperLevelDB. https:\/\/github.com\/rescrv\/HyperLevelDB ."},{"volume-title":"Redesigning LSMs for Nonvolatile Memory with NoveLSM. In 2018 USENIX Annual Technical Conference, USENIX ATC 2018","year":"2018","author":"Kannan Sudarsun","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 2017 International Conference on Massive Storage Systems and Technology","year":"2017","author":"Lee Dong-Yun","key":"e_1_2_1_22_1"},{"volume-title":"10th USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2018","year":"2018","author":"Lee Eunji","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","unstructured":"LMDB. 2011. LMDB. https:\/\/symas.com\/lmdb\/.  LMDB. 2011. LMDB. https:\/\/symas.com\/lmdb\/."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2751519"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_2_1_27_1","unstructured":"Memcached. 2003. Memcached. https:\/\/memcached.org .  Memcached. 2003. Memcached. https:\/\/memcached.org ."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164142"},{"key":"e_1_2_1_29_1","unstructured":"Inc. MongoDB. 2018. MongoDB. https:\/\/www.mongodb.com.  Inc. MongoDB. 2018. MongoDB. https:\/\/www.mongodb.com."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"volume-title":"9th USENIX Symposium on Operating Systems Design and Implementation, OSDI","year":"2010","author":"Peng Daniel","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137659"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_2_1_35_1","unstructured":"Redis. 2009. Redis. https:\/\/redis.io .  Redis. 2009. Redis. https:\/\/redis.io ."},{"key":"e_1_2_1_36_1","unstructured":"Margo Seltzer and Keith Bostic. 1994. Berkeley DB. http:\/\/https:\/\/www.oracle.com\/database\/berkeley-db\/index.html .  Margo Seltzer and Keith Bostic. 1994. Berkeley DB. http:\/\/https:\/\/www.oracle.com\/database\/berkeley-db\/index.html ."},{"key":"e_1_2_1_37_1","unstructured":"TokyoCabinet. 2009. TokyoCabinet. http:\/\/fallabs.com\/tokyocabinet\/.  TokyoCabinet. 2009. TokyoCabinet. http:\/\/fallabs.com\/tokyocabinet\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231762"},{"volume-title":"High-Performance Distributed File System. In 7th Symposium on Operating Systems Design and Implementation (OSDI '06)","year":"2006","author":"Weil Sage A.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","unstructured":"WiredTiger. 2016. WiredTiger. http:\/\/www.wiredtiger.com\/.  WiredTiger. 2016. WiredTiger. http:\/\/www.wiredtiger.com\/."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311079","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:54Z","timestamp":1750206354000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311079"}},"subtitle":["Weaving Data Structures for a High-Performance Key-Value Store"],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,26]]}},"alternative-id":["10.1145\/3322205.3311079"],"URL":"https:\/\/doi.org\/10.1145\/3322205.3311079","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}