论文标题
实际和理论上有效的垃圾收集
Practically and Theoretically Efficient Garbage Collection for Multiversioning
论文作者
论文摘要
多相关广泛用于数据库，交易存储器和并发数据结构。它可用于支持在存在并发更新操作的情况下出现原子质的仅读取事务。任何维护每个对象的多个版本的系统都需要一种有效回收它们的方法。我们通过将它们应用于多元化树和多元散布表中的各种现有填海技术来比较它们。 使用这些实验的见解，我们开发了两种新的多元垃圾收集（MVGC）技术。这些技术使用两个新型并发版本列表数据结构。我们的实验评估表明，我们最快的技术具有现有的MVGC技术最快的竞争，同时在某些工作负载上使用了明显较小的空间。我们的新技术提供了强大的理论界限，尤其是在空间使用方面。这些界限确保了这些方案具有一致的性能，从而避免了其他技术的最高最差空间使用情况。
Multiversioning is widely used in databases, transactional memory, and concurrent data structures. It can be used to support read-only transactions that appear atomic in the presence of concurrent update operations. Any system that maintains multiple versions of each object needs a way of efficiently reclaiming them. We experimentally compare various existing reclamation techniques by applying them to a multiversion tree and a multiversion hash table. Using insights from these experiments, we develop two new multiversion garbage collection (MVGC) techniques. These techniques use two novel concurrent version list data structures. Our experimental evaluation shows that our fastest technique is competitive with the fastest existing MVGC techniques, while using significantly less space on some workloads. Our new techniques provide strong theoretical bounds, especially on space usage. These bounds ensure that the schemes have consistent performance, avoiding the very high worst-case space usage of other techniques.
