Bundled References: An Abstraction for Highly-Concurrent Linearizable Range Queries (Artifact)
| Main Authors: | Jacob, Ahmed, Roberto |
|---|---|
| Format: | info software Journal |
| Terbitan: |
, 2020
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/4290932 |
Daftar Isi:
- In this paper we address the challenge of providing linearizable range query operations for linked data structures by introducing a new building block; we call bundled references. Using bundled references provides range queries with a path through the data structure consistent with their linearization point. Our design guarantees that range queries only traverse nodes belonging to their snapshot and that they never block writers. With multi-version concurrency control (MVCC) in mind, we implement our technique in three data structures. The experimental evaluation of our bundled linked list, skip list, and binary search tree, including their integration as indexes in the DBx1000 in-memory database, shows up to 20% improvement over state-of-the-art techniques to provide linearizable range queries, as well as a more consistent performance profile across a variety of workloads