Space and Time Bounded Multiversion Garbage Collection
Space and Time Bounded Multiversion Garbage Collection
复制标题
DOI：
10.4230/lipics.disc.2021.12
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
N. Ben-David;G. Blelloch;P. Fatourou;E. Ruppert;Yihan Sun;Yuanhao Wei
中科院分区：
文献类型：
--
作者：
N. Ben-David;G. Blelloch;P. Fatourou;E. Ruppert;Yihan Sun;Yuanhao Wei
我们提出了一种通用技术，用于垃圾收集旧版本，以同时实现良好的时间和空间复杂性，以进行多元化并发控制。我们的技术平均仅需$ o（1）$时间来收回每个版本，并且仅维持比所需的恒定要素（加上添加期）。它是为最常见的版本列表而设计的。我们的方法使用两个具有独立感兴趣的组件。首先，我们定义了一种新颖的范围跟踪数据结构，该数据结构存储了一组旧版本，并有效地找到了不再需要的范围。我们提供了无候补的实现，所有操作都需要摊销的恒定时间。其次，我们使用一个新的无锁双关联列表算法表示版本列表，该算法支持有效的（摊销恒定时间）删除，并给出了指向列表中任何节点的指针。这两个组件自然拟合在一起以解决多元垃圾收集问题 - 范围跟踪器标识了要删除的版本，我们的列表算法可以使用它们从其版本列表中删除。我们将垃圾收集技术应用于Wei等人的多离子系统的端到端时间和空间界限。 （PPOPP 2021）。
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only $O(1)$ time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion 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 our list algorithm can then be used to remove them from their version lists. 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).