{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:11:35Z","timestamp":1775596295379,"version":"3.50.1"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Cloud databases revolutionize data processing and storage by providing on-demand and scalable services housed on the cloud infrastructure. Multi-tenancy and serverless are two key tenets transforming the cloud database architecture, offering significant cost savings and simplified user management. However, we found that cloud databases using LSM-tree-based key-value stores as the storage engine face a crucial conundrum when adopting this promising multi-tenant serverless architecture. Specifically, LSM-tree-based key-value store encounters a critical dilemma between maintaining performance service-level agreements (SLAs) for tenants and over-subscribing storage bandwidth for high cost-efficiency. In this paper, we present FlexEngine, a novel LSM-tree-based key-value store, which for the first time enables the practical and efficient adoption of LSM tree in multi-tenant serverless cloud databases. FlexEngine introduces a series of designs to navigate the above dilemma, including a two-level (i.e., partition- and node-level) I\/O admission control framework and a two-stage compaction deferral mechanism. We implement FlexEngine on a commercially-deployed RocksDB and perform comprehensive experiments on both production traces and micro-level workloads. The experimental results demonstrate that FlexEngine can significantly improve the capability to over-subscribe storage bandwidth, which leads to high cost-efficiency, while still promising consistent performance SLAs for users.<\/jats:p>","DOI":"10.1145\/3786667","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Making LSM-Tree-based Key-Value Store Practical and Efficient for Multi-Tenant Serverless Cloud Databases"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2890-7984","authenticated-orcid":false,"given":"Yingjia","family":"Wang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4295-0220","authenticated-orcid":false,"given":"Caixin","family":"Gong","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8779-3631","authenticated-orcid":false,"given":"Guoyun","family":"Zhu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1582-3316","authenticated-orcid":false,"given":"Sheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0694-184X","authenticated-orcid":false,"given":"Zhengheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1934-8715","authenticated-orcid":false,"given":"Huan","family":"Liu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5884-9923","authenticated-orcid":false,"given":"Junzhi","family":"Shi","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4164-5778","authenticated-orcid":false,"given":"Wu","family":"Qin","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1417-7995","authenticated-orcid":false,"given":"Wei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0770-5775","authenticated-orcid":false,"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4029-757X","authenticated-orcid":false,"given":"Ming-Chang","family":"Yang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. Auto-tuned Rate Limiter in RocksDB. https:\/\/rocksdb.org\/blog\/2017\/12\/18\/17-auto-tuned-rate-limiter.html."},{"key":"e_1_2_1_2_1","unstructured":"2017. Wikipedia of Token Bucket Algorithm. https:\/\/en.wikipedia.org\/wiki\/Token_bucket."},{"key":"e_1_2_1_3_1","unstructured":"2017. Wikipedia of Weighted Fair Queueing. https:\/\/en.wikipedia.org\/wiki\/Weighted_fair_queueing."},{"key":"e_1_2_1_4_1","unstructured":"2021. Write Stalls in RocksDB. https:\/\/github.com\/facebook\/rocksdb\/wiki\/Write-Stalls."},{"key":"e_1_2_1_5_1","unstructured":"2022. Rate Limiter in RocksDB. https:\/\/github.com\/facebook\/rocksdb\/wiki\/rate-limiter."},{"key":"e_1_2_1_6_1","unstructured":"2023. RocksDB Tuning Guide. https:\/\/github.com\/facebook\/rocksdb\/wiki\/RocksDB-Tuning-Guide."},{"key":"e_1_2_1_7_1","unstructured":"2025. Alibaba Cloud ESSD. https:\/\/www.alibabacloud.com\/help\/en\/ecs\/user-guide\/essds."},{"key":"e_1_2_1_8_1","unstructured":"2025. Alibaba Tair Serverless KV. https:\/\/www.alibabacloud.com\/help\/en\/redis\/product-overview\/tair-serverless-kv\/."},{"key":"e_1_2_1_9_1","unstructured":"2025. Amazon AWS ESSD. https:\/\/docs.aws.amazon.com\/ebs\/latest\/userguide\/ebs-volumes.html."},{"key":"e_1_2_1_10_1","unstructured":"2025. Apache Cassandra. https:\/\/cassandra.apache.org\/_\/index.html."},{"key":"e_1_2_1_11_1","unstructured":"2025. Apache HBase. https:\/\/hbase.apache.org\/."},{"key":"e_1_2_1_12_1","unstructured":"2025. Google LevelDB. https:\/\/github.com\/google\/leveldb."},{"key":"e_1_2_1_13_1","unstructured":"2025. Meta RocksDB. http:\/\/rocksdb.org\/."},{"key":"e_1_2_1_14_1","unstructured":"2025. PingCAP TiKV. https:\/\/tikv.org\/."},{"key":"e_1_2_1_15_1","unstructured":"2025. Postgres' Vaccum. https:\/\/www.postgresql.org\/docs\/current\/sql-vacuum.html."},{"key":"e_1_2_1_16_1","unstructured":"2025. Rate Limiting Algorithms - System Design. https:\/\/www.geeksforgeeks.org\/system-design\/rate-limitingalgorithms-system-design\/."},{"key":"e_1_2_1_17_1","volume-title":"An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version). arXiv preprint arXiv:1910.08185","author":"Alkowaileet Wail Y","year":"2019","unstructured":"Wail Y Alkowaileet, Sattam Alsubaiee, and Michael J Carey. 2019. An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version). arXiv preprint arXiv:1910.08185 (2019)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314047"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3625054.3625058"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018465"},{"key":"e_1_2_1_21_1","first-page":"753","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Balmau Oana","year":"2019","unstructured":"Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. 2019. {SILK}: Preventing latency spikes in {Log-Structured} merge {Key-Value} stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). 753-766."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3685800.3685825"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457560"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3663408.3663417"},{"key":"e_1_2_1_25_1","volume-title":"ScalaTap: Scalable Outbound Rate Limiting in Public Cloud. In IEEE INFOCOM 2025-IEEE Conference on Computer Communications. IEEE, 1-10","author":"Chen Zhongjie","year":"2025","unstructured":"Zhongjie Chen, Yingchen Fan, Kun Qian, Qingkai Meng, Ran Shu, Xiaoyu Li, Yiran Zhang, Bo Wang, Wei Li, and Fengyuan Rent. 2025. ScalaTap: Scalable Outbound Rate Limiting in Public Cloud. In IEEE INFOCOM 2025-IEEE Conference on Computer Communications. IEEE, 1-10."},{"key":"e_1_2_1_26_1","first-page":"155","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Dai Yifan","year":"2020","unstructured":"Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2020. From {WiscKey} to bourbon: A learned index for {Log-Structured} merge trees. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 155-171."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276980"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319903"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457273"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551853"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483840"},{"key":"e_1_2_1_33_1","first-page":"1037","volume-title":"2022 USENIX Annual Technical Conference (USENIX ATC 22)","author":"Elhemali Mostafa","year":"2022","unstructured":"Mostafa Elhemali, Niall Gallagher, Bin Tang, Nick Gordon, Hao Huang, Haibo Chen, Joseph Idziorek, Mengtian Wang, Richard Krog, Zongpeng Zhu, et al. 2022. Amazon {DynamoDB}: A scalable, predictably performant, and fully managed {NoSQL} database service. In 2022 USENIX Annual Technical Conference (USENIX ATC 22). 1037-1048."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM42981.2021.9488773"},{"key":"e_1_2_1_35_1","unstructured":"Xiang Hu Tianyu Xu Lilong Chen Xiaochong Jiang Ye Yang Liming Ye XuWang Yilong Lv Chenhao Jia Yongwang Wu et al. 2025. Distributed Rate Limiting under Decentralized Cloud Networks. IEEE Transactions on Mobile Computing (2025)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457297"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3383133"},{"key":"e_1_2_1_38_1","unstructured":"Stratos Idreos Niv Dayan Wilson Qin Mali Akmanalp Sophie Hilgard Andrew Ross James Lennon Varun Jain Harshita Gupta David Li et al. 2019. Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn.. In CIDR."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787479"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00259"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551814"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554893"},{"key":"e_1_2_1_43_1","first-page":"739","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Li Yongkun","year":"2019","unstructured":"Yongkun Li, Chengjin Tian, Fan Guo, Cheng Li, and Yinlong Xu. 2019. {ElasticBF}: Elastic bloom filter with hotness awareness for boosting read performance in large {Key-Value} stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). 739-752."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00094"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3715331"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_2_1_47_1","volume-title":"On performance stability in LSM-based storage systems (extended version). arXiv preprint arXiv:1906.09667","author":"Luo Chen","year":"2019","unstructured":"Chen Luo and Michael J Carey. 2019. On performance stability in LSM-based storage systems (extended version). arXiv preprint arXiv:1906.09667 (2019)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430916"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3522566"},{"key":"e_1_2_1_51_1","volume-title":"The log-structured merge-tree (LSM-tree). Acta informatica 33, 4","author":"O'Neil Patrick","year":"1996","unstructured":"Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. The log-structured merge-tree (LSM-tree). Acta informatica 33, 4 (1996), 351-385."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342396"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514073"},{"key":"e_1_2_1_54_1","first-page":"475","volume-title":"11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14)","author":"Radhakrishnan Sivasankar","year":"2014","unstructured":"Sivasankar Radhakrishnan, Yilong Geng, Vimalkumar Jeyakumar, Abdul Kabbani, George Porter, and Amin Vahdat. 2014. {SENIC}: Scalable {NIC} for {End-Host} rate limiting. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14). 475-488."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1282427.1282419"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098852"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3522563"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3520169"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00273"},{"key":"e_1_2_1_61_1","volume-title":"Constructing and analyzing the LSM compaction design space (updated version). arXiv preprint arXiv:2202.04522","author":"Sarkar Subhadeep","year":"2022","unstructured":"Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. 2022. Constructing and analyzing the LSM compaction design space (updated version). arXiv preprint arXiv:2202.04522 (2022)."},{"key":"e_1_2_1_62_1","volume-title":"8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11)","author":"Shieh Alan","year":"2011","unstructured":"Alan Shieh, Srikanth Kandula, Albert Greenberg, Changhoon Kim, and Bikas Saha. 2011. Sharing the data center network. In 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11)."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2009.5199141"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056101"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3676536.3676653"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA61900.2025.00053"},{"key":"e_1_2_1_67_1","volume-title":"The Unwritten Contract of Cloud-based Elastic Solid-State Drives. In 2025 62nd ACM\/IEEE Design Automation Conference (DAC). IEEE, 1-7.","author":"Wang Yingjia","year":"2025","unstructured":"Yingjia Wang and Ming-Chang Yang. 2025. The Unwritten Contract of Cloud-based Elastic Solid-State Drives. In 2025 62nd ACM\/IEEE Design Automation Conference (DAC). IEEE, 1-7."},{"key":"e_1_2_1_68_1","first-page":"71","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Wu Xingbo","year":"2015","unstructured":"Xingbo Wu, Yuehai Xu, Zili Shao, and Song Jiang. 2015. {LSM-trie}: An {LSM-tree-based} {Ultra-Large} {Key-Value} store for small data items. In 2015 USENIX Annual Technical Conference (USENIX ATC 15). 71-82."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139922"},{"key":"e_1_2_1_70_1","first-page":"65","volume-title":"21st USENIX Conference on File and Storage Technologies (FAST 23)","author":"Yu Jinghuan","year":"2023","unstructured":"Jinghuan Yu, Sam H Noh, Young-ri Choi, and Chun Jason Xue. 2023. {ADOC}: Automatically Harmonizing Dataflow Between Components in {Log-Structured} {Key-Value} Stores for Improved Performance. In 21st USENIX Conference on File and Storage Technologies (FAST 23). 65-80."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00384"},{"key":"e_1_2_1_73_1","first-page":"451","volume-title":"2023 USENIX Annual Technical Conference (USENIX ATC 23)","author":"Zhou Yuanhui","year":"2023","unstructured":"Yuanhui Zhou, Jian Zhou, Shuning Chen, Peng Xu, Peng Wu, Yanguang Wang, Xian Liu, Ling Zhan, and Jiguang Wan. 2023. Calcspar: A {Contract-Aware} {LSM} Store for Cloud Storage with Low Latency Spikes. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). 451-465."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:03:39Z","timestamp":1775592219000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":73,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786667"],"URL":"https:\/\/doi.org\/10.1145\/3786667","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}