一种面向事务型数据库的无锁并发B+tree索引结构

A wait-free concurrent B + tree index scheme for transaction databases

为了克服现有多版本并发控制(MVCC)进行数据的并发访问控制中短暂阻塞的缺点,达到读写完全并发,提出了一种基于写时复制的多版本并发B+tree(BCMVBT)索引结构。BCMVBT通过复制分离读写的操作空间以使读写事务在任意时刻完全并发执行,规避比较与交换(CAS)操作带来的高CPU消耗,达到一写多读场景下的完全并发。同时针对现有多版本开发B+tree(MVBT)范围查询的复杂操作,提出了无锁的BCMVBT的范围查询算法和回收机制,从而实现了索引的插入、查询、更新与回收的无锁并发操作。通过与事务型MVBT(transaction MVBT)的对比,在读写并发环境下BCMVBT的时间消耗降低了50%,实验进一步表明BCMVBT在大事务的场景下具有更高的优势。

In order to overcome multi-version concurrent control （MVCC） ＇ s disadvantage of short obstruction in its con- current control of data access to achieve the full read-write concurrency, a new index scheme based on copy on write （BC） with multi-version concurrency B ＋ tree, called the BCMVBT, was presented. The BCMVBT uses the copy of the operation space for read-write separation to make the read-write transaction be concurrently conducted. Moreover, it avoids the CPU consumption caused by compare and swap （CAS） operations to achieve the full con- currency under write-once-read-many scenarios. Additionally, the current MVBT range query algorithm was im- proved and a recovery mechanism with wait-free manner was proposed in order to achieve full concurrency of insert/ delete/recycle operations. Compared to TMVBT, BCMVBT reduces time cost by 50%. Further experiments show that BCMVBT is more efficient in large transaction environment.