{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:08:19Z","timestamp":1779131299129,"version":"3.51.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DBI-2327954"],"award-info":[{"award-number":["DBI-2327954"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2106621"],"award-info":[{"award-number":["CCF-2106621"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    Cloud databases often use\n                    <jats:italic toggle=\"yes\">consistent hashing<\/jats:italic>\n                    to schedule queries because of its data locality guarantee -- scheduling the queries accessing the same data segment to the same node. This makes optimizations such as\n                    <jats:italic toggle=\"yes\">caching<\/jats:italic>\n                    effective in reducing data I\/O costs. However, consistent hashing causes load imbalance when handling skewed workloads and can lead to large query latencies. In this paper, to address this limitation, we propose HotHash, a technique that offers strong data locality and load balancing guarantees, while still preserving the key properties of consistent hashing, e.g., robustness to node changes. HotHash  achieves these objectives with two key ideas: (1) range hashing that takes data hotness into consideration and (2) virtual hash ring that introduces randomness into query scheduling. More specifically, rather than mapping one data segment to one single node,\n                    <jats:italic toggle=\"yes\">range hashing<\/jats:italic>\n                    maps it to a range of the hash ring where its length is proportional to the hotness of this data item; and it achieves so with\n                    <jats:italic toggle=\"yes\">one single hash.<\/jats:italic>\n                    Furthermore, HotHash  uses a\n                    <jats:italic toggle=\"yes\">virtual hash ring<\/jats:italic>\n                    where the locations of nodes in the hash ring are randomized for each data segment, which randomizes nodes caching each data segment while preserving data locality for a given item. We show that HotHash  is robust to node changes in that it still uses the same principles of consistent hashing to map data to the nodes. Our experimental evaluation on various workloads shows that HotHash  is 1.4\u00d7 to 150\u00d7 faster than the state-of-the-art in average execution time and tail latency.\n                  <\/jats:p>","DOI":"10.1145\/3802073","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["HotHash: Hotness-Aware Consistent Hashing for Cloud Databases"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5862-6127","authenticated-orcid":false,"given":"Junyong","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Arizona, Tucson, Arizona, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2953-6307","authenticated-orcid":false,"given":"Jia","family":"Yuan","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, Arizona, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6939-3189","authenticated-orcid":false,"given":"Zui","family":"Chen","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7470-3265","authenticated-orcid":false,"given":"Samuel","family":"Madden","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9909-8607","authenticated-orcid":false,"given":"Lei","family":"Cao","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, Arizona, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. NumPy. https:\/\/numpy.org\/doc\/stable."},{"key":"e_1_2_1_2_1","unstructured":"2026. Google Capacitor. https:\/\/cloud.google.com\/blog\/products\/bigquery\/inside-capacitor-bigquerys-next-generationcolumnar- storage-format."},{"key":"e_1_2_1_3_1","first-page":"185","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)","author":"Ananthanarayanan Ganesh","year":"2013","unstructured":"Ganesh Ananthanarayanan, Ali Ghodsi, Scott Shenker, and Ion Stoica. 2013. Effective straggler mitigation: Attack of the clones. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 185-198."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148163"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i5.16517"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741967"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Sixth ACM Symposium on Cloud Computing. 139-152","author":"Coppa Emilio","year":"2015","unstructured":"Emilio Coppa and Irene Finocchi. 2015. On data skewness, stragglers, and MapReduce progress indicators. In Proceedings of the Sixth ACM Symposium on Cloud Computing. 139-152."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903741"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1012889.1012894"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-020-03241-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191886"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742795"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2525970"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670518.2673882"},{"key":"e_1_2_1_20_1","volume-title":"2017 IEEE 2nd International Conference on Big Data Analysis (ICBDA). IEEE, 89-93","author":"Kalid Sultana","year":"2017","unstructured":"Sultana Kalid, Ali Syed, Azeem Mohammad, and Malka N Halgamuge. 2017. Big-data NoSQL databases: A comparison and analysis of ''Big-Table'', ''DynamoDB'', and ''Cassandra''. In 2017 IEEE 2nd International Conference on Big Data Analysis (ICBDA). IEEE, 89-93."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258660"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00055-9"},{"key":"e_1_2_1_23_1","volume-title":"44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 482-491","author":"Kempe David","year":"2003","unstructured":"David Kempe, Alin Dobra, and Johannes Gehrke. 2003. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 482-491."},{"key":"e_1_2_1_24_1","unstructured":"Jay Kreps. 2012. Project Voldemort."},{"key":"e_1_2_1_25_1","volume-title":"Cassandra: a decentralized structured storage system. ACM SIGOPS operating systems review 44, 2","author":"Lakshman Avinash","year":"2010","unstructured":"Avinash Lakshman and Prashant Malik. 2010. Cassandra: a decentralized structured storage system. ACM SIGOPS operating systems review 44, 2 (2010), 35-40."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2805789.2805800"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175309"},{"key":"e_1_2_1_28_1","first-page":"385","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)","author":"Nishtala Rajesh","year":"2013","unstructured":"Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, et al. 2013. Scaling memcache at facebook. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 385-398."},{"key":"e_1_2_1_29_1","unstructured":"Diego Ongaro and John Ousterhout. 2014. In search of an understandable consensus algorithm. In 2014 USENIX annual technical conference (USENIX ATC 14). 305-319."},{"key":"e_1_2_1_30_1","first-page":"401","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Rashmi KV","year":"2016","unstructured":"KV Rashmi, Mosharaf Chowdhury, Jack Kosaian, Ion Stoica, and Kannan Ramchandran. 2016. {EC-Cache}:{Load- Balanced},{Low-Latency} Cluster Caching with Online Erasure Coding. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). 401-417."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 379-392","author":"Ren Xiaoqi","year":"2015","unstructured":"Xiaoqi Ren, Ganesh Ananthanarayanan, Adam Wierman, and Minlan Yu. 2015. Hopper: Decentralized speculation aware cluster scheduling at scale. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 379-392."},{"key":"e_1_2_1_33_1","first-page":"329","volume-title":"Germany","author":"Rowstron Antony","year":"2001","unstructured":"Antony Rowstron and Peter Druschel. 2001. Pastry: Scalable, decentralized object location, and routing for large scale peer-to-peer systems. In Middleware 2001: IFIP\/ACM International Conference on Distributed Systems Platforms Heidelberg, Germany, November 12-16, 2001 Proceedings 2. Springer, 329-350."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229871"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00196"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuroimage.2016.02.074"},{"key":"e_1_2_1_37_1","volume-title":"Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM computer communication review 31, 4","author":"Stoica Ion","year":"2001","unstructured":"Ion Stoica, Robert Morris, David Karger, MFrans Kaashoek, and Hari Balakrishnan. 2001. Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM computer communication review 31, 4 (2001), 149-160."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2019.2909854"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"2170","DOI":"10.14778\/3352063.3352133","article-title":"Choosing a cloud DBMS: architectures and tradeo!s","volume":"12","author":"Tan Junjay","year":"2019","unstructured":"Junjay Tan, Thanaa Ghanem, Matthew Perron, Xiangyao Yu, Michael Stonebraker, David DeWitt, Marco Serani, Ashraf Aboulnaga, and Tim Kraska. 2019. Choosing a cloud DBMS: architectures and tradeo!s. Proceedings of the VLDB Endowment 12, 12 (2019), 2170-2182.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"3694","DOI":"10.14778\/3681954.3682031","article-title":"Why TPC is not enough: An analysis of the Amazon Redshift fleet","volume":"17","author":"Renen Alexander Van","year":"2024","unstructured":"Alexander Van Renen, Dominik Horn, Pascal Pfeil, Kapil Vaidya, Wenjian Dong, Murali Narayanaswamy, Zhengchun Liu, Gaurav Saxena, Andreas Kipf, and Tim Kraska. 2024. Why TPC is not enough: An analysis of the Amazon Redshift fleet. Proceedings of the VLDB Endowment 17, 11 (2024), 3694-3706.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056101"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 2018 International Conference on Management of Data. 789-796","author":"Verbitski Alexandre","year":"2018","unstructured":"Alexandre Verbitski, Anurag Gupta, Debanjan Saha, James Corey, Kamal Gupta, Murali Brahmadesam, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvilli, et al. 2018. Amazon aurora: On avoiding distributed consensus for i\/os, commits, and membership changes. In Proceedings of the 2018 International Conference on Management of Data. 789-796."},{"key":"e_1_2_1_44_1","first-page":"449","volume-title":"17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Vuppalapati Midhul","year":"2020","unstructured":"Midhul Vuppalapati, Justin Miron, Rachit Agarwal, Dan Truong, Ashish Motivala, and Thierry Cruanes. 2020. Building an elastic query engine on disaggregated storage. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 449-462."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476265"},{"key":"e_1_2_1_46_1","first-page":"7","article-title":"Improving MapReduce performance in heterogeneous environments","volume":"8","author":"Zaharia Matei","year":"2008","unstructured":"Matei Zaharia, Andy Konwinski, Anthony D Joseph, Randy H Katz, and Ion Stoica. 2008. Improving MapReduce performance in heterogeneous environments.. In Osdi, Vol. 8. 7.","journal-title":"Osdi"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225109"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802073","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:37:38Z","timestamp":1779129458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802073"],"URL":"https:\/\/doi.org\/10.1145\/3802073","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}