Storage management with multi-version partitioned BTrees
- Database management systems and K/V-Stores operate on updatable datasets – massively exceeding the size of available main memory. Tree-based K/V storage management structures became particularly popular in storage engines. B+ -Trees [1, 4] allow constant search performance, however write-heavy workloads yield in inefficient write patterns to secondary storage devices and poor performance characteristics. LSM-Trees [16, 23] overcome this issue by horizontal partitioning fractions of data – small enough to fully reside in main memory, but require frequent maintenance to sustain search performance. Firstly, we propose Multi-Version Partitioned BTrees (MV-PBT) as sole storage and index management structure in key-sorted storage engines like K/V-Stores. Secondly, we compare MV-PBT against LSM-Trees. The logical horizontal partitioning in MV-PBT allows leveraging recent advances in modern B+ -Tree techniques in a small transparent and memory resident portion of the structure. Structural properties sustain steady read performance, yielding efficient write patterns and reducing write amplification. We integrated MV-PBT in the WiredTiger [15] KV storage engine. MV-PBT offers an up to 2× increased steady throughput in comparison to LSM-Trees and several orders of magnitude in comparison to B+ -Trees in a YCSB [5] workload.
Author of HS Reutlingen | Riegger, Christian; Petrov, Ilia |
---|---|
DOI: | https://doi.org/10.1007/978-3-031-15740-0_19 |
ISBN: | 978-3-031-15740-0 |
Erschienen in: | Advances in databases and information systems : 26th European Conference, ADBIS 2022, Turin, Italy, September 5-8, 2022, proceedings. - (Lecture notes in computer science ; 13389) |
Publisher: | Springer |
Place of publication: | Cham |
Editor: | Silvia Chiusano, Tania Cerquitelli, Robert Wrembel |
Document Type: | Conference proceeding |
Language: | English |
Publication year: | 2022 |
Tag: | append storage; storage engine; storage management |
Page Number: | 15 |
First Page: | 255 |
Last Page: | 269 |
DDC classes: | 004 Informatik |
Open access?: | Nein |
Licence (German): | In Copyright - Urheberrechtlich geschützt |