{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T07:16:19Z","timestamp":1779002179350,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T00:00:00Z","timestamp":1712188800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2023YFB4502701 and 2022YFB4501100"],"award-info":[{"award-number":["2023YFB4502701 and 2022YFB4501100"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072196, 62302465, U22A2071, 62372197, U2001203, and 62102155"],"award-info":[{"award-number":["62072196, 62302465, U22A2071, 62372197, U2001203, and 62102155"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Creative Research Group Project of NSFC","award":["61821003"],"award-info":[{"award-number":["61821003"]}]},{"DOI":"10.13039\/501100015956","name":"Key Research and Development Program of Guangdong Province","doi-asserted-by":"crossref","award":["2021B0101400003"],"award-info":[{"award-number":["2021B0101400003"]}],"id":[{"id":"10.13039\/501100015956","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2024,5,31]]},"abstract":"<jats:p>\n            Cloud storage is gaining popularity because features such as pay-as-you-go significantly reduce storage costs. However, the community has not sufficiently explored its contract model and latency characteristics. As LSM-Tree-based key-value stores (LSM stores) become the building block for numerous cloud applications, how cloud storage would impact the performance of key-value accesses is vital. This study reveals the significant latency variances of Amazon Elastic Block Store (EBS) under various I\/O pressures, which challenges LSM store read performance on cloud storage. To reduce the corresponding tail latency, we propose Calcspar, a contract-aware LSM store for cloud storage, which efficiently addresses the challenges by regulating the rate of I\/O requests to cloud storage and absorbing surplus I\/O requests with the data cache. We specifically developed a fluctuation-aware cache to lower the high latency brought on by workload fluctuations. Additionally, we build a congestion-aware IOPS allocator to reduce the impact of LSM store internal operations on read latency. We evaluated Calcspar on EBS with different real-world workloads and compared it to the cutting-edge LSM stores. The results show that Calcspar can significantly reduce tail latency while maintaining regular read and write performance, keeping the 99\n            <jats:sup>th<\/jats:sup>\n            percentile latency under 550\u03bcs and reducing average latency by 66%. In addition, Calcspar has lower write prices and average latency compared to Cloud NoSQL services offered by cloud vendors.\n          <\/jats:p>","DOI":"10.1145\/3643851","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T12:30:12Z","timestamp":1708432212000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Contract-aware and Cost-effective LSM Store for Cloud Storage with Low Latency Spikes"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3685-7033","authenticated-orcid":false,"given":"Yuanhui","family":"Zhou","sequence":"first","affiliation":[{"name":"WNLO, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5295-4680","authenticated-orcid":false,"given":"Jian","family":"Zhou","sequence":"additional","affiliation":[{"name":"WNLO, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7757-4083","authenticated-orcid":false,"given":"Kai","family":"Lu","sequence":"additional","affiliation":[{"name":"WNLO, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9086-2944","authenticated-orcid":false,"given":"Ling","family":"Zhan","sequence":"additional","affiliation":[{"name":"Division of Information Science and Technology, Wenhua University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8547-5344","authenticated-orcid":false,"given":"Peng","family":"Xu","sequence":"additional","affiliation":[{"name":"Research Center for Graph Computing, Research Institute of Intelligent Computing, Zhejiang Laboratory, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6177-0553","authenticated-orcid":false,"given":"Peng","family":"Wu","sequence":"additional","affiliation":[{"name":"WNLO, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3568-7271","authenticated-orcid":false,"given":"Shuning","family":"Chen","sequence":"additional","affiliation":[{"name":"PingCAP, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8902-3416","authenticated-orcid":false,"given":"Xian","family":"Liu","sequence":"additional","affiliation":[{"name":"PingCAP, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4160-9475","authenticated-orcid":false,"given":"Jiguang","family":"Wan","sequence":"additional","affiliation":[{"name":"WNLO, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,4]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2022. Amazon EBS Volume Modify Limitations. https:\/\/docs.aws.amazon.com\/AWSEC2\/latest\/UserGuide\/modify-volume-requirements.html"},{"key":"e_1_3_2_3_2","unstructured":"2022. Amazon EBS Volume Pricing. https:\/\/aws.amazon.com\/cn\/ebs\/pricing"},{"key":"e_1_3_2_4_2","unstructured":"2022. Amazon EBS Volume Types. https:\/\/docs.aws.amazon.com\/AWSEC2\/latest\/UserGuide\/ebs-volume-types.html"},{"key":"e_1_3_2_5_2","unstructured":"2022. RocksDB. https:\/\/github.com\/facebook\/rocksdb"},{"key":"e_1_3_2_6_2","unstructured":"2023. AWS DynamoDB Pricing for On-Demand Capacity. https:\/\/aws.amazon.com\/dynamodb\/pricing\/on-demand"},{"key":"e_1_3_2_7_2","unstructured":"2023. AWS DynamoDB Pricing for Provisioned Capacity. https:\/\/aws.amazon.com\/dynamodb\/pricing\/provisioned"},{"key":"e_1_3_2_8_2","unstructured":"2023. Managing throughput Capacity Automatically with DynamoDB Auto Scaling. https:\/\/docs.aws.amazon.com\/amazondynamodb\/latest\/developerguide\/AutoScaling.html"},{"key":"e_1_3_2_9_2","unstructured":"2023. RocksDB Autotuned Rate Limiter. https:\/\/rocksdb.org\/blog\/2017\/12\/18\/17-auto-tuned-rate-limiter"},{"key":"e_1_3_2_10_2","unstructured":"2024. Amazon DynamoDB Accelerator (DAX). https:\/\/aws.amazon.com\/cn\/dynamodb\/dax\/"},{"key":"e_1_3_2_11_2","unstructured":"2024. LevelDB. https:\/\/github.com\/google\/leveldb"},{"key":"e_1_3_2_12_2","unstructured":"2024-01-16. Benchmarking Tools | RocksDB. https:\/\/github.com\/facebook\/rocksdb\/wiki\/Benchmarking-tools"},{"key":"e_1_3_2_13_2","unstructured":"Alibaba Cloud.2023. 2023. Aliyun. https:\/\/www.alibabacloud.com\/product\/disk\/"},{"key":"e_1_3_2_14_2","unstructured":"Alibaba Aliyun. 2023. https:\/\/www.aliyun.com\/product\/ots"},{"key":"e_1_3_2_15_2","unstructured":"Amazon. 2023. https:\/\/aws.amazon.com\/cn\/dynamodb\/pricing\/"},{"key":"e_1_3_2_16_2","unstructured":"Amazon.2022. 2022. Cloud Storage. https:\/\/aws.amazon.com\/what-is-cloud-storage\/"},{"key":"e_1_3_2_17_2","first-page":"363","volume-title":"2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Balmau Oana","year":"2017","unstructured":"Oana Balmau, Diego Didona, Rachid Guerraoui, Willy Zwaenepoel, Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka. 2017. TRIAD: Creating synergies between memory, disk and log in log structured key-value stores. In 2017 USENIX Annual Technical Conference (USENIX ATC\u201917). 363\u2013375."},{"key":"e_1_3_2_18_2","first-page":"753","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC\u201919)","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\u201919). 753\u2013766."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2485732.2485740"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386712"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3019264"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_3_2_26_2","first-page":"1037","volume-title":"2022 USENIX Annual Technical Conference (USENIX ATC\u201922)","author":"Elhemali Mostafa","year":"2022","unstructured":"Mostafa Elhemali, Niall Gallagher, Nick Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somasundaram Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, and Akshat Vig. 2022. Amazon DynamoDB: A scalable, predictably performant, and fully managed NoSQL database service. In 2022 USENIX Annual Technical Conference (USENIX ATC\u201922). USENIX Association, Carlsbad, CA, 1037\u20131048. https:\/\/www.usenix.org\/conference\/atc22\/presentation\/elhemali"},{"key":"e_1_3_2_27_2","unstructured":"Google.2023. 2023. Google Cloud. https:\/\/cloud.google.com\/"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_3_2_29_2","first-page":"113","volume-title":"15th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201921)","author":"Hwang Jaehyun","year":"2021","unstructured":"Jaehyun Hwang, Midhul Vuppalapati, Simon Peter, and Rachit Agarwal. 2021. Rearchitecting Linux storage stack for \u00b5s latency and high throughput. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201921). USENIX Association, 113\u2013128. https:\/\/www.usenix.org\/conference\/osdi21\/presentation\/hwang"},{"key":"e_1_3_2_30_2","unstructured":"IDC The digitization of the world from edge to core. 2022. https:\/\/www.seagate.com\/files\/www-content\/our-story\/trends\/files\/idc-seagate-dataage-whitepaper.pdf"},{"key":"e_1_3_2_31_2","unstructured":"Jens Axboe. 2022. Flexible I\/O Tester. https:\/\/github.com\/axboe\/fio"},{"key":"e_1_3_2_32_2","first-page":"3367","volume-title":"2023 IEEE 39th International Conference on Data Engineering (ICDE\u201923)","author":"Kesavan Ram","year":"2023","unstructured":"Ram Kesavan, David Gay, Daniel Thevessen, Jimit Shah, and C. Mohan. 2023. Firestore: The NoSQL serverless database for the application developer. In 2023 IEEE 39th International Conference on Data Engineering (ICDE\u201923). 3367\u20133379."},{"key":"e_1_3_2_33_2","first-page":"755","volume-title":"2022 USENIX Annual Technical Conference (USENIX ATC\u201922)","author":"Kwon Miryeong","year":"2022","unstructured":"Miryeong Kwon, Seungjun Lee, Hyunkyu Choi, Jooyoung Hwang, and Myoungsoo Jung. 2022. Vigil-KV: Hardware-software co-design to integrate strong latency determinism into log-structured merge key-value stores. In 2022 USENIX Annual Technical Conference (USENIX ATC\u201922). USENIX Association, Carlsbad, CA, 755\u2013772. https:\/\/www.usenix.org\/conference\/atc22\/presentation\/kwon"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384356"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1109\/ICDE51399.2021.00094","volume-title":"2021 IEEE 37th International Conference on Data Engineering (ICDE\u201921)","author":"Liang Junkai","year":"2021","unstructured":"Junkai Liang and Yunpeng Chai. 2021. CruiseDB: An LSM-tree key-value store with both better tail throughput and tail latency. In 2021 IEEE 37th International Conference on Data Engineering (ICDE\u201921). IEEE, 1032\u20131043."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524059.3532378"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3118599"},{"key":"e_1_3_2_38_2","first-page":"413","volume-title":"20th USENIX Conference on File and Storage Technologies (FAST\u201922)","author":"Macedo Ricardo","year":"2022","unstructured":"Ricardo Macedo, Yusuke Tanimura, Jason Haga, Vijay Chidambaram, Jos\u00e9 Pereira, and Jo\u00e3o Paulo. 2022. PAIO: General, portable I\/O optimizations with minor application modifications. In 20th USENIX Conference on File and Storage Technologies (FAST\u201922). USENIX Association, Santa Clara, CA, 413\u2013428. https:\/\/www.usenix.org\/conference\/fast22\/presentation\/macedo"},{"key":"e_1_3_2_39_2","unstructured":"Microsoft.2023. 2023. Azure. https:\/\/azure.microsoft.com\/en-us\/products\/storage\/disks\/"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139226424","volume-title":"Performance Modeling and Design of Computer Systems","author":"Mor Harchol-Balter","year":"2013","unstructured":"Harchol-Balter Mor. 2013. Performance Modeling and Design of Computer Systems. Vol. 576. Cambridge University Press."},{"issue":"10","key":"e_1_3_2_41_2","first-page":"268","article-title":"The research study on DynamoDB\u2013NoSQL database service","volume":"3","author":"Niranjanamurthy M.","year":"2014","unstructured":"M. Niranjanamurthy, U. L. Archana, K. T. Niveditha, S. Abdul Jafar, and N. S. Shravan. 2014. The research study on DynamoDB\u2013NoSQL database service. Int. J. Comput. Sci. Mob. Comput. 3, 10 (2014), 268\u2013279.","journal-title":"Int. J. Comput. Sci. Mob. Comput."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-017-1704-4"},{"key":"e_1_3_2_43_2","first-page":"arXiv\u20132008","article-title":"PrismDB: Read-aware log-structured merge trees for heterogeneous storage","author":"Raina Ashwini","year":"2020","unstructured":"Ashwini Raina, Asaf Cidon, Kyle Jamieson, and Michael J. Freedman. 2020. PrismDB: Read-aware log-structured merge trees for heterogeneous storage. arXiv e-prints (2020), arXiv\u20132008.","journal-title":"arXiv e-prints"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_3_2_45_2","unstructured":"Research and Markets. 2022. Cloud Storage Market. https:\/\/www.researchandmarkets.com\/reports\/4306260\/cloud-storagemarket-forecasts-from-2017-to-2022"},{"key":"e_1_3_2_46_2","volume-title":"CuttleTree: Adaptive Tuning for Optimized Log-structured Merge Trees","author":"Ruta Nicholas Joseph","year":"2017","unstructured":"Nicholas Joseph Ruta. 2017. CuttleTree: Adaptive Tuning for Optimized Log-structured Merge Trees. Ph. D. Dissertation."},{"key":"e_1_3_2_47_2","first-page":"68","volume-title":"2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS\u201917)","author":"Teng Dejun","year":"2017","unstructured":"Dejun Teng, Lei Guo, Rubao Lee, Feng Chen, Siyuan Ma, Yanfeng Zhang, and Xiaodong Zhang. 2017. LSbM-tree: Re-enabling buffer caching in data management for mixed reads and writes. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS\u201917). IEEE, 68\u201379."},{"key":"e_1_3_2_48_2","first-page":"253","volume-title":"18th USENIX Conference on File and Storage Technologies (FAST\u201920)","author":"Wang Shucheng","year":"2020","unstructured":"Shucheng Wang, Ziyi Lu, Qiang Cao, Hong Jiang, Jie Yao, Yuanyuan Dong, and Puyuan Yang. 2020. BCW: Buffer-controlled writes to HDDs for SSD-HDD hybrid storage server. In 18th USENIX Conference on File and Storage Technologies (FAST\u201920). USENIX Association, Santa Clara, CA, 253\u2013266. https:\/\/www.usenix.org\/conference\/fast20\/presentation\/wang-shucheng"},{"key":"e_1_3_2_49_2","first-page":"603","volume-title":"2020 USENIX Annual Technical Conference (USENIX ATC\u201920)","author":"Wu Fenggang","year":"2020","unstructured":"Fenggang Wu, Ming-Hong Yang, Baoquan Zhang, and David H. C. Du. 2020. AC-Key: Adaptive caching for LSM-based key-value stores. In 2020 USENIX Annual Technical Conference (USENIX ATC\u201920). USENIX Association, 603\u2013615. https:\/\/www.usenix.org\/conference\/atc20\/presentation\/wu-fenggang"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3527452"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407803"},{"key":"e_1_3_2_52_2","first-page":"1","volume-title":"Proc. 33rd Int. Conf. Massive Storage Syst. Technol. (MSST)","author":"Yao Ting","year":"2017","unstructured":"Ting Yao, Jiguang Wan, Ping Huang, Xubin He, Qingxin Gui, Fei Wu, and Changsheng Xie. 2017. A light-weight compaction tree to reduce I\/O amplification toward efficient key-value stores. In Proc. 33rd Int. Conf. Massive Storage Syst. Technol. (MSST). 1\u201313."},{"key":"e_1_3_2_53_2","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/3267809.3267846","volume-title":"Proceedings of the ACM Symposium on Cloud Computing (SoCC\u201918)","author":"Yoon Hobin","year":"2018","unstructured":"Hobin Yoon, Juncheng Yang, Sveinn Fannar Kristjansson, Steinn E. Sigurdarson, Ymir Vigfusson, and Ada Gavrilovska. 2018. Mutant: Balancing storage cost and latency in LSM-tree data stores. In Proceedings of the ACM Symposium on Cloud Computing (SoCC\u201918). 162\u2013173."},{"key":"e_1_3_2_54_2","first-page":"222","volume-title":"International Conference on Algorithms and Architectures for Parallel Processing","author":"Zhang Shuo","year":"2021","unstructured":"Shuo Zhang, Guangping Xu, YuLei Jia, Yanbing Xue, and Wenguang Zheng. 2021. Parallel cache prefetching for LSM-tree based store: From algorithm to evaluation. In International Conference on Algorithms and Architectures for Parallel Processing. Springer, 222\u2013236."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547320"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643851","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3643851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:57:34Z","timestamp":1750291054000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,4]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,31]]}},"alternative-id":["10.1145\/3643851"],"URL":"https:\/\/doi.org\/10.1145\/3643851","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,4]]},"assertion":[{"value":"2023-09-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}