论文标题
EEMARQ：有效的无锁范围查询，并带有内存填海
EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation
论文作者
论文摘要
多次并发控制（MVCC）是在数据库系统和并发数据结构中实现可线化范围查询的常见机制。核心想法是将节点的先前版本保留以提供范围查询，同时仍提供原子读取和更新。现有的并发数据结构实现，支持可线化的范围查询，要么缓慢，要么使用锁，要么依靠阻止开垦方案。我们提出EEMARQ，这是第一个使用带有无锁存储回收的MVCC来获得完全无锁的数据结构，支持可线化的插入，删除，包含和范围查询。评估表明，EEMARQ在大多数工作负载中胜过现有的解决方案，其空间较低，并且提供了完全的锁定自由度。
Multi-Version Concurrency Control (MVCC) is a common mechanism for achieving linearizable range queries in database systems and concurrent data-structures. The core idea is to keep previous versions of nodes to serve range queries, while still providing atomic reads and updates. Existing concurrent data-structure implementations, that support linearizable range queries, are either slow, use locks, or rely on blocking reclamation schemes. We present EEMARQ, the first scheme that uses MVCC with lock-free memory reclamation to obtain a fully lock-free data-structure supporting linearizable inserts, deletes, contains, and range queries. Evaluation shows that EEMARQ outperforms existing solutions across most workloads, with lower space overhead and while providing full lock freedom.
