EUVIMEDEUVIMED entdecken
Crossref

B link -hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases

Hokeun Cha, Xiangpeng Hao, Tianzheng Wang, Huanchen Zhang, Aditya Akella, Xiangyao Yu

Proceedings of the VLDB Endowment · 2023-02 · 16 (6) · 1235-1248

DOI: 10.14778/3583140.3583143 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 20.04.2023. Verfasst von Hokeun Cha und 5 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 56 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

High-speed data ingestion is critical in time-series workloads that are driven by the growth of Internet of Things (IoT) applications. We observe that traditional tree-based indexes encounter severe scalability bottlenecks for time-series workloads that insert monotonically increasing timestamp keys into an index; all insertions go to a small memory region that sees extremely high contention. In this work, we present a new index design, B link -hash, that enhances a tree-based index with hash leaf nodes to mitigate the contention of monotonic insertions --- insertions go to random locations within a hash node (which is much larger than a B+-tree node) to reduce conflicts. We develop further optimizations (median approximation and lazy split) to accelerate hash node splits. We also develop structure adaptation optimizations to dynamically convert a hash node to B+-tree nodes for good scan performance. Our evaluation shows that B link -hash achieves up to 91.3× higher throughput than conventional indexes in a time-series workload that monotonically inserts timestamps into an index, while showing comparable scan performance to a well-optimized B+-tree.

Zitieren

APA

Cha, H., Hao, X., Wang, T., Zhang, H., Akella, A., & Yu, X. (2023). B link -hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases. Proceedings of the VLDB Endowment, 16(6), 1235-1248. https://doi.org/10.14778/3583140.3583143

Vancouver

Cha H, Hao X, Wang T, Zhang H, Akella A, Yu X. B link -hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases. Proceedings of the VLDB Endowment. 2023;16(6):1235-1248. doi:10.14778/3583140.3583143

BibTeX
@article{Cha2023,
  author = {Cha, Hokeun and Hao, Xiangpeng and Wang, Tianzheng and Zhang, Huanchen and Akella, Aditya and Yu, Xiangyao},
  title = {B link -hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {6},
  pages = {1235--1248},
  doi = {10.14778/3583140.3583143}
}
Kostenlos starten →