Name
Abstract | ||
|---|---|---|
We present a general technique for garbage collecting old versions for multi-version concurrency control that simultaneously achieves good time and space complexity. Our technique takes only $O(1)$ time on average for each new version and maintains only a constant factor more than then number of needed versions. Our technique is designed for multi-version schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem--the range-tracker identifies which versions to remove and the list algorithm splices them out. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.DISC.2021.12 | DISC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Naama Ben-David | 1 | 15 | 6.02 |
| Guy E. Blelloch | 2 | 2927 | 207.30 |
| Panagiota Fatourou | 3 | 281 | 28.16 |
| Eric Ruppert | 4 | 41 | 4.21 |
| Yihan Sun | 5 | 73 | 11.19 |
| Yuanhao Wei | 6 | 1 | 2.06 |