{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T06:26:58Z","timestamp":1778048818870,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p>\n            <jats:italic>Log-structured merge (LSM)<\/jats:italic>\n            stores have emerged as the technology of choice for building scalable write-intensive key-value storage systems. An LSM store replaces random I\/O with sequential I\/O by accumulating large batches of writes in a\n            <jats:italic>memory store<\/jats:italic>\n            prior to flushing them to log-structured disk storage; the latter is continuously re-organized in the background through a\n            <jats:italic>compaction<\/jats:italic>\n            process for efficiency of reads. Though inherent to the LSM design, frequent compactions are a major pain point because they slow down data store operations, primarily writes, and also increase disk wear. Another performance bottleneck in today's state-of-the-art LSM stores, in particular ones that use managed languages like Java, is the fragmented memory layout of their dynamic memory store.\n          <\/jats:p>\n          <jats:p>In this paper we show that these pain points may be mitigated via better organization of the memory store. We present Accordion - an algorithm that addresses these problems by re-applying the LSM design principles to memory management. Accordion is implemented in the production code of Apache HBase, where it was extensively evaluated. We demonstrate Accordion's double-digit performance gains versus the baseline HBase implementation and discuss some unexpected lessons learned in the process.<\/jats:p>","DOI":"10.14778\/3229863.3229873","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1863-1875","source":"Crossref","is-referenced-by-count":33,"title":["Accordion"],"prefix":"10.14778","volume":"11","author":[{"given":"Edward","family":"Bortnikov","sequence":"first","affiliation":[{"name":"Yahoo Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasia","family":"Braginsky","sequence":"additional","affiliation":[{"name":"Yahoo Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eshcar","family":"Hillel","sequence":"additional","affiliation":[{"name":"Yahoo Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Idit","family":"Keidar","sequence":"additional","affiliation":[{"name":"Technion and Yahoo Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gali","family":"Sheffi","sequence":"additional","affiliation":[{"name":"Yahoo Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache HBase. http:\/\/hbase.apache.org.  Apache HBase. http:\/\/hbase.apache.org."},{"key":"e_1_2_1_2_1","unstructured":"Apache hbase at airbnb. https:\/\/www.slideshare.net\/HBaseCon\/apache-hbase-at-airbnb.  Apache hbase at airbnb. https:\/\/www.slideshare.net\/HBaseCon\/apache-hbase-at-airbnb."},{"key":"e_1_2_1_3_1","unstructured":"Avoiding full gcs with memstore-local allocation buffers. http:\/\/blog.cloudera.com\/blog\/2011\/02\/.  Avoiding full gcs with memstore-local allocation buffers. http:\/\/blog.cloudera.com\/blog\/2011\/02\/."},{"key":"e_1_2_1_4_1","unstructured":"Cassandra. http:\/\/cassandra.apache.org.  Cassandra. http:\/\/cassandra.apache.org."},{"key":"e_1_2_1_5_1","unstructured":"Dragon: A distributed graph query engine. https:\/\/code.facebook.com\/posts\/1737605303120405.  Dragon: A distributed graph query engine. https:\/\/code.facebook.com\/posts\/1737605303120405."},{"key":"e_1_2_1_6_1","unstructured":"Hbase compaction tuning tips. https:\/\/community.hortonworks.com\/articles\/52616\/hbase-compaction-tuning-tips.html.  Hbase compaction tuning tips. https:\/\/community.hortonworks.com\/articles\/52616\/hbase-compaction-tuning-tips.html."},{"key":"e_1_2_1_7_1","unstructured":"Hbase operations in a flurry. http:\/\/bit.ly\/2yaTfoP.  Hbase operations in a flurry. http:\/\/bit.ly\/2yaTfoP."},{"key":"e_1_2_1_8_1","unstructured":"Java concurrent skiplist map. https:\/\/docs.oracle.com\/javase\/7\/docs\/api\/java\/util\/concurrent\/ConcurrentSkipListSet.html.  Java concurrent skiplist map. https:\/\/docs.oracle.com\/javase\/7\/docs\/api\/java\/util\/concurrent\/ConcurrentSkipListSet.html."},{"key":"e_1_2_1_9_1","unstructured":"LevelDB. https:\/\/github.com\/google\/leveldb.  LevelDB. https:\/\/github.com\/google\/leveldb."},{"key":"e_1_2_1_10_1","unstructured":"Mongodb. https:\/\/mongorocks.org.  Mongodb. https:\/\/mongorocks.org."},{"key":"e_1_2_1_11_1","unstructured":"Mysql. http:\/\/myrocks.io.  Mysql. http:\/\/myrocks.io."},{"key":"e_1_2_1_12_1","unstructured":"Off-heap memtables in cassandra 2.1. https:\/\/www.datastax.com\/dev\/blog\/off-heap-memtables-in-cassandra-2-1.  Off-heap memtables in cassandra 2.1. https:\/\/www.datastax.com\/dev\/blog\/off-heap-memtables-in-cassandra-2-1."},{"key":"e_1_2_1_13_1","unstructured":"Offheap read-path in production the alibaba story. https:\/\/blog.cloudera.com\/blog\/2017\/03\/.  Offheap read-path in production the alibaba story. https:\/\/blog.cloudera.com\/blog\/2017\/03\/."},{"key":"e_1_2_1_14_1","unstructured":"RocksDB. http:\/\/rocksdb.org\/.  RocksDB. http:\/\/rocksdb.org\/."},{"key":"e_1_2_1_15_1","unstructured":"Rocksdb tuning guide.  Rocksdb tuning guide."},{"key":"e_1_2_1_16_1","unstructured":"Scylladb. https:\/\/github.com\/scylladb\/scylla.  Scylladb. https:\/\/github.com\/scylladb\/scylla."},{"key":"e_1_2_1_17_1","unstructured":"Sstable compaction and compaction strategies. http:\/\/bit.ly\/2wXc7ah.  Sstable compaction and compaction strategies. http:\/\/bit.ly\/2wXc7ah."},{"key":"e_1_2_1_18_1","unstructured":"Universal compaction.  Universal compaction."},{"key":"e_1_2_1_19_1","unstructured":"Zen: Pinterest's graph storage service. http:\/\/bit.ly\/2ft4YDx.  Zen: Pinterest's graph storage service. http:\/\/bit.ly\/2ft4YDx."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064193"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808797.2808880"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191886"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1534530.1534544"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671026"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/615232.615237"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_33_1","unstructured":"A. S. Tanenbaum and H. Bos. Modern Operating Systems. Prentice Hall Press Upper Saddle River NJ USA 4th edition 2014.   A. S. Tanenbaum and H. Bos. Modern Operating Systems . Prentice Hall Press Upper Saddle River NJ USA 4th edition 2014."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093139.2093140"},{"key":"e_1_2_1_35_1","first-page":"71","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Wu X.","year":"2015"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3229863.3229873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:15:27Z","timestamp":1672222527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3229863.3229873"}},"subtitle":["better memory organization for LSM key-value stores"],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":35,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.14778\/3229863.3229873"],"URL":"https:\/\/doi.org\/10.14778\/3229863.3229873","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}