DynaHash: Efficient Data Rebalancing in Apache AsterixDB
Abstract
Parallel shared-nothing data management systems have been widely used to exploit a cluster of machines for efficient and scalable data processing. When a cluster needs to be dynamically scaled in or out, data must be efficiently rebalanced. Ideally, data rebalancing should have a low data movement cost, incur a small overhead on data ingestion and query processing, and be performed online without blocking reads or writes. However, existing parallel data management systems often exhibit certain limitations and drawbacks in terms of efficient data rebalancing.
In this paper, we introduce DynaHash, an efficient data rebalancing approach that combines dynamic bucketing with extendible hashing for shared-nothing OLAP-style parallel data management systems. DynaHash dynamically partitions the records into a number of buckets using extendible hashing to achieve good a load balance with small rebalancing costs. We further describe an end-to-end implementation of the proposed approach inside an open-source Big Data Management System (BDMS), Apache AsterixDB. Our implementation exploits the out-of-place update design of LSM-trees to efficiently rebalance data without blocking concurrent reads and writes. Finally, we have conducted performance experiments using the TPC-H benchmark and we present the results here.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems cites Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores
- Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems cites On Performance Stability in LSM-based Storage Systems
Cited by top-tier papers1
Builds on5
- Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value StoresSiqiang Luo, Subarna Chatterjee, Rafael Ketsetsidis, Niv Dayan et al.SIGMOD 2020 · 91 citations
- Lethe: A Tunable Delete-Aware LSM EngineSubhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Manos AthanassoulisSIGMOD 2020 · 68 citations
- An LSM-based Tuple Compaction Framework for Apache AsterixDBWail Y. Alkowaileet, Sattam Alsubaiee, Michael J. CareyVLDB 2020 · 23 citations
- Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage SystemsChen Luo, Michael J. CareyVLDB 2021 · 20 citations
- On Performance Stability in LSM-based Storage SystemsChen Luo, Michael J. CareyVLDB 2020 · 1 citation
Related papers
- Dash: Scalable Hashing on Persistent MemoryBaotong Lu, Xiangpeng Hao, Tianzheng Wang, Eric LoVLDB 2020 · 8 citations
- EEPH: An Efficient Extendible Perfect Hashing for Hybrid PMem-DRAMQi Chen, Hao Hu, Cai Deng, Dingbang Liu et al.ICDE 2023 · 8 citations
- DyTIS: A Dynamic Dataset Targeted Index Structure Simultaneously Efficient for Search, Insert, and ScanJin Yang, Heejin Yoon, Gyeongchan Yun, Sam H. Noh et al.EuroSys 2023 · 5 citations
- EIGA: elastic and scalable dynamic graph analysisKasimir Gabert, Kaan Sancak, M. Yusuf Özkaya, Ali Pinar et al.SC 2021 · 5 citations
- Global Hash Tables Strike Back! An Analysis of Parallel GROUP BY AggregationDaniel Xue, Ryan MarcusVLDB 2026
