多线程持久性B+树数据结构设计与实现方法

摘要

本发明公开了一种多线程持久性B+树数据结构设计与实现方法，方法包括：在预设的B+树中引入一层基于链式结构的影子叶节点；通过基于混合主存的数据布局策略将基于链表的叶节点存储在NVM中，以生成基于数组结构的树层，并且将索引数据结构的其他部分存储在DRAM中，以生成基于链表结构的链层，使得通过分层的易失性树结构和持久性链表结构的设计避免平衡和排序的持久化开销；设计嵌入式的细粒度锁机制和乐观写机制，以分别用于读写操作之间和写写操作之间的并发控制。该方法使用非易失性内存和易失性内存的混合主存数据结构，增加数据检索的并发性和实现数据持久存储，解决放大的锁开销问题，并加速数据结构的系统恢复过程。

说明书

技术领域

本发明涉及非易失性主存存储技术领域，特别涉及一种多线程持久性B+树数据结构设计与实现方法。

背景技术

非易失性主存(Non-Volatile Memory，NVM)是一种新型的内存存储介质，具有可字节寻址、掉电后信息非易失、存储密度高、不需要动态刷新和静态功耗低等优点。但是，也存在一些不足之处，如读写性能不对称，有限的写次数和写功耗较高等缺点。它的出现对存储领域带来了新的巨大机遇和挑战，引发了产业界和学术界对异构混合内存体系架构及其相关系统软件的研究热潮。非易失性内存对计算机系统结构、系统软件、软件库以及应用程序都有很多新的启示。非易失性内存设备可以与动态随机存取存储器(Dynamic RandomAccess Memory，DRAM)设备共同构成混合主存，其中，应用程序中临时性的数据存储在DRAM上，把需要持久保存的数据存储在NVM上。非易失主存的出现促使研究人员着手设计基于主存的存储系统，包括文件系统和数据库系统。索引结构是构建存储系统的关键模块，它在很大程度上决定了存储系统的性能。在基于非易失主存的存储系统中，索引结构需要同时保证高效的一致性和多线程扩展性，这对索引结构的设计者提出了新的挑战。

传统的索引数据结构如B+树，排序和平衡操作在整个树操作开销中占据了很大的比例，更加严重的是，持久化延迟会进一步增加树操作持有锁的时间，相关技术中的持久性B+树在多线程场景下面临严重的性能问题。在多线程场景下,随着非易失主存持久化延迟的增加，树操作持有锁的时间几乎线性地增长，B+树的性能下降十分严重。

发明内容

本发明旨在至少在一定程度上解决相关技术中的技术问题之一。

为此，本发明的一个目的在于提出一种多线程持久性B+树数据结构设计与实现方法，该方法使用非易失性内存和易失性内存的混合主存数据结构，增加数据检索的并发性和实现数据持久存储，解决了放大的锁开销问题，并加速数据结构的系统恢复过程。

为达到上述目的，本发明实施例提出了一种多线程持久性B+树数据结构设计与实现方法，包括以下步骤：在预设的B+树中引入一层基于链式结构的影子叶节点；通过基于混合主存的数据布局策略将基于链表的叶节点存储在NVM中，以生成基于数组结构的树层，并且将索引数据结构的其他部分存储在DRAM中，以生成基于链表结构的链层，使得通过分层的易失性树结构和持久性链表结构的设计避免平衡和排序的持久化开销；设计嵌入式的细粒度锁机制和乐观写机制，以分别用于读写操作之间和写写操作之间的并发控制。

本发明实施例的多线程持久性B+树数据结构设计与实现方法，通过使用非易失性内存和易失性内存的混合主存数据结构，使得具有良好空间局部性和平衡性的搜索操作，有效地减少了昂贵的持久化操作，并且还设计嵌入式的细粒度锁和乐观写机制，解决放大的锁开销问题，同时采用多线程的恢复机制和持久性垃圾回收器，用于支持非易失主存的一致性管理，并加速数据结构的系统恢复过程。

另外，根据本发明上述实施例的多线程持久性B+树数据结构设计与实现方法还可以具有以下附加的技术特征：

进一步地，在本发明的一个实施例中，所述嵌入式的细粒度锁机制为每个链表节点设计一个更新标记位和删除标记位，以将不满足预设条件的持久化延迟从读操作的版本验证路径上移除，并且所述乐观写机制将树节点和链表节点的并发控制机制进行分离，以将所述持久化延迟从树节点粒度的加锁路径上移除。

进一步地，在本发明的一个实施例中，位于所述DRAM中的基于数组结构的树层，其每一个节点能容纳预设数量的键值对，其中，树节点的每个键值对指向下一层的树节点或者链表节点，以在任意个树节点的键值对数量超过或者低于预设阙值，树节点会执行分裂或者合并操作，在上一层的树节点中插入或者删除一个键值对。

进一步地，在本发明的一个实施例中，位于所述NVM中的基于数组结构的链层，将链层存储在非易失主存中，其中，所述链层为一个有序的链表，每个链表节点仅存储一个键值对，且用右指针相连，利用CPU原子操作保证其原子性和一致性的插入/删除/更新操作

进一步地，在本发明的一个实施例中，每个树操作均从根结点开始搜索，直到找到对应的叶节点，其中，在访问任意一个树节点之前，执行预取指令，将整个树节点读取到CPU缓存中，以掩盖所述整个树节点的访存延迟，并且分别将键数组和值数组存放在不同的主存空间中，以只预取键数组，降低每次预取操作的数据总量。

可选地，选取预设阈值的键数组大小，可以使用线性查找操作取代二分查找操作，将所述线性查找操作放在主存空间上进行，并利用SIMD指令加速，其中，每个键值对配备1B的指纹，且每个指纹都是对应键值的哈希值，并将指纹数组存储在叶节点的头部。

进一步地，在本发明的一个实施例中，如果读写操作间的冲突，则采用基于版本号的并发控制机制，其中，在每个树节点上采用一个版本号计数器，版本号在每次树节点状态被改变的时候递增，对于插入、删除或者更新操作，在修改树节点之前申请锁，并将对应版本号置为脏，并在完成操作后且版本号加1后，释放掉对应树节点的锁，且如果版本号被修改或者被加锁，则读操作就会重复执行上述过程，直到版本号验证通过；如果写写操作间的冲突，则采用树节点粒度的锁机制，其中，采用树节点粒度的锁确保修改不同树节点的写操作同时执行，叶节点之间通过右指针相连，并且预设所述叶节点的分裂方向只能从左往右，并自底向上申请所述树节点的锁，且在所述树节点发生分裂或者删除时，申请上一层树节点的锁，链表节点和叶节点的键值对有一一对应的关系，使得所述写操作只有在获取树层对应叶节点的锁之后，才会修改所述链表节点。

进一步地，在本发明的一个实施例中，在每次分配和释放一个链表节点之前，每次从系统主存分配器中分配一块非易失主存空间，并且将所述非易失主存空间的地址和长度持久化到一个持久性链表中，并将分配到的所述主存空间分割成预设大小的主存块，并通过一个易失性的空闲主存块链表维护，以用于链层的主存分配和释放操作，且在系统恢复时，恢复线程扫描持久性链表上的元数据信息和链层的节点，判断出正在使用的和没有被使用的主存块，从而重建易失性的空闲主存块链表。

进一步地，在本发明的一个实施例中，还可以包括：通过维护一个全局的epoch计数器和三个垃圾回收链表来正确回收被释放的树节点和链表节点，其中，在执行相关操作前，工作线程首先注册现有的epoch号，对于每个删除的树/链表节点，线程根据当前的全局epoch号将其放置到对应的垃圾回收链表中。

进一步地，在本发明的一个实施例中，还包括：当系统正常关机时，将所有易失性的内部树节点和垃圾回收器持久化到非易失主存的预设位置，且当系统重启后，恢复线程将所述所有易失性的内部树节点和所述垃圾回收器从非易失主存拷贝到所述DRAM中。

本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：

图1为根据本发明一个实施例的多线程持久性B+树数据结构设计与实现方法流程图；

图2为根据本发明一个实施例的基于链式结构的多线程持久性B+树结构示意图；

图3是根据本发明一个实施例的读写冲突和写写冲突的优化策略图；

图4是根据本发明一个实施例的持久性B+树受限的多线程扩展性分析图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

下面参照附图描述根据本发明实施例提出的多线程持久性B+树数据结构设计与实现方法。

图1是本发明一个实施例的多线程持久性B+树数据结构设计与实现方法流程图。

如图1所示，该多线程持久性B+树数据结构设计与实现方法包括以下步骤：

在步骤S101中，在预设的B+树中引入一层基于链式结构的影子叶节点。

进一步地，在本发明的一个实施例中，每个树操作均从根结点开始搜索，直到找到对应的叶节点，其中，在访问任意一个树节点之前，执行预取指令，将整个树节点读取到CPU缓存中，以掩盖整个树节点的访存延迟，并且分别将键数组和值数组存放在不同的主存空间中，以只预取键数组，降低每次预取操作的数据总量。

在步骤S102中，通过基于混合主存的数据布局策略将基于链表的叶节点存储在NVM中，以生成基于数组结构的树层，并且将索引数据结构的其他部分存储在DRAM中，以生成基于链表结构的链层，使得通过分层的易失性树结构和持久性链表结构的设计避免平衡和排序的持久化开销。

进一步地，在本发明的一个实施例中，位于DRAM中的基于数组结构的树层，其每一个节点能容纳预设数量的键值对，其中，树节点的每个键值对指向下一层的树节点或者链表节点，以在任意个树节点的键值对数量超过或者低于预设阙值，树节点会执行分裂或者合并操作，在上一层的树节点中插入或者删除一个键值对。

进一步地，在本发明的一个实施例中，位于NVM中的基于数组结构的链层，将链层存储在非易失主存中，其中，链层为一个有序的链表，每个链表节点仅存储一个键值对，且用右指针相连，利用CPU原子操作保证其原子性和一致性的插入/删除/更新操作。

可选地，选取预设阈值的键数组大小，可以使用线性查找操作取代二分查找操作，将线性查找操作放在主存空间上进行，并利用SIMD指令加速，其中，每个键值对配备1B的指纹，且每个指纹都是对应键值的哈希值，并将指纹数组存储在叶节点的头部。

在步骤S103中，设计嵌入式的细粒度锁机制和乐观写机制，以分别用于读写操作之间和写写操作之间的并发控制。

进一步地，在本发明的一个实施例中，嵌入式的细粒度锁机制为每个链表节点设计一个更新标记位和删除标记位，以将不满足预设条件的持久化延迟从读操作的版本验证路径上移除，并且乐观写机制将树节点和链表节点的并发控制机制进行分离，以将持久化延迟从树节点粒度的加锁路径上移除。

进一步地，在本发明的一个实施例中，如果读写操作间的冲突，则采用基于版本号的并发控制机制，其中，在每个树节点上采用一个版本号计数器，版本号在每次树节点状态被改变的时候递增，对于插入、删除或者更新操作，在修改树节点之前申请锁，并将对应版本号置为脏，并在完成操作后且版本号加1后，释放掉对应树节点的锁，且如果版本号被修改或者被加锁，则读操作就会重复执行上述过程，直到版本号验证通过；如果写写操作间的冲突，则采用树节点粒度的锁机制，其中，采用树节点粒度的锁确保修改不同树节点的写操作同时执行，叶节点之间通过右指针相连，并且预设叶节点的分裂方向只能从左往右，并自底向上申请树节点的锁，且在树节点发生分裂或者删除时，申请上一层树节点的锁，链表节点和叶节点的键值对有一一对应的关系，使得写操作只有在获取树层对应叶节点的锁之后，才会修改链表节点。

进一步地，在本发明的一个实施例中，在每次分配和释放一个链表节点之前，每次从系统主存分配器中分配一块非易失主存空间，并且将非易失主存空间的地址和长度持久化到一个持久性链表中，并将分配到的主存空间分割成预设大小的主存块，并通过一个易失性的空闲主存块链表维护，以用于链层的主存分配和释放操作，且在系统恢复时，恢复线程扫描持久性链表上的元数据信息和链层的节点，判断出正在使用的和没有被使用的主存块，从而重建易失性的空闲主存块链表。

进一步地，在本发明的一个实施例中，还可以包括：通过维护一个全局的epoch计数器和三个垃圾回收链表来正确回收被释放的树节点和链表节点，其中，在执行相关操作前，工作线程首先注册现有的epoch号，对于每个删除的树/链表节点，线程根据当前的全局epoch号将其放置到对应的垃圾回收链表中。

进一步地，在本发明的一个实施例中，还包括：当系统正常关机时，将所有易失性的内部树节点和垃圾回收器持久化到非易失主存的预设位置，且当系统重启后，恢复线程将所有易失性的内部树节点和垃圾回收器从非易失主存拷贝到DRAM中。

本发明实施例提出一种使用非易失性内存和易失性内存的混合主存数据结构，在易失性内存中采用传统的树型数据结构，在非易失性内存中采用链式的数据结构，树型的数据结构增加数据检索的并发性，链式数据结构实现在非易失性介质上的数据持久存储，树型结构具有良好空间局部性和平衡性的搜索操作，链式结构有效地减少了昂贵的持久化操作，并且该数据结构还设计了嵌入式的细粒度锁和乐观写机制，解决了放大的锁开销问题，同时采用多线程的恢复机制和持久性垃圾回收器，用于支持非易失主存的一致性管理，并加速了数据结构的系统恢复过程。

具体地，本发明的实施例提出一种基于非易失性内存NVM和易失性内存DRAM混合主存存储系统进行优化的数据结构。其中，该优化后的数据结构主要包括以下特征：该数据结构包含两个层次，第一个层次是基于数组结构的树层(Tree Layer)，存放在DRAM中，第二个层次是基于链表结构的链层(List Layer)，存放在NVM中。其中，链层有效地减少了数据结构的持久化操作，树层提供具有良好空间局部性和平衡性的搜索操作。

其中，优化后的数据结构具体包括以下特征：

(1)位于DRAM中的基于数组结构的树层，其中，其每一个节点能容纳固定数量的键值对，将有序的键值对存储在连续的主存空间中，从而保证良好的空间局部性，支持时间复杂度为O(log n)的树操作。树节点的每个键值对指向下一层的树节点或者链表节点。如果某个树节点的键值对数量超过或者低于某个特定的阙值，树节点会执行分裂或者合并操作，在上一层的树节点中插入或者删除一个键值对，并不会产生任何持久化开销。由于树层只用于加速链层的查找性能，当系统发生错误时，通过持久性的链层恢复易失性的树层，并且通过此方法使得平衡和排序操作只发生在DRAM中，因此，该方法不会引入过高的持久化写开销，可以有效地提升索引结构的性能。

(2)位于NVM中的基于数组结构的链层，具体地，只将链层存储在非易失主存中。链层是一个有序的链表，每个链表节点仅存储一个键值对，用右指针相连，利用CPU原子操作(x86平台支持对齐的64比特原子操作)，保证其原子性和一致性的插入/删除/更新操作。具体地，以插入操作为例，在找到正确的插入位置后，只需要执行以下两个持久化操作就可以保证链层的有序性，第一个持久化操作是将新生成的链表节点(已指向后置节点)持久化，第二个持久化操作是将前置链表节点的指针(已指向新生成的链表节点)持久化。其中，如果在两个操作之间发生了系统错误，因为新生成的链表节点还没有插入到链层中，所以链层的一致性并不会受到影响。并且对于没有插入成功的新节点，持久性垃圾回收器会避免这块主存的丢失，因为链层能容纳无限数量的链表节点，天然地消除了平衡操作。

(3)每个树操作都需要从根结点开始搜索，直到找到对应的叶节点，还需要读取搜索路径上的所有树节点，其中，树节点的访存延迟就成为树层性能的主要影响因素。本发明的实施例在访问一个树节点之前，会执行一个预取指令，将整个树节点读取到CPU缓存中，掩盖了整个树节点的访存延迟，还分别将键数组和值数组存放在不同的主存空间中，从而实现只预取键数组，降低每次预取操作的数据总量的目的。

(4)对于位于DRAM中的树型数据结构，可以选取一定阈值的键数组大小，使用线性查找操作取代二分查找操作。进一步地，将线性查找操作放在主存空间上进行，并利用SIMD指令加速。其中，对于查找操作，使用SIMD指令同时将目标键值和多个不同键值进行比较，在排序和平衡中也使用类似的策略，从而同时移动多个数据，提升索引性能。

(5)对于该数据结构的叶节点上，为每个叶节点的每个键值对配备了1B的指纹，其中，每个指纹都是对应键值的哈希值，并将指纹数组存储在叶节点的头部。对于一个查找操作，只有目标键值的哈希值与某个指纹的哈希值相同的时候，才可以去比较这个指纹对应的键值。其中，每个指纹的大小远远小于每个键值的大小，因此，基于指纹数组的对比操作可以更近一步地增加额外并发的能力。

进一步地，本发明的实施例描述的是数据结构的基于版本号的并发控制机制，该并发控制机制主要内容如下：对于读写操作间的冲突，采用基于版本号的并发控制机制，对于写写操作间的冲突，采用树节点粒度的锁机制。

其中，一方面，对于读写操作间的冲突，可以在每个树节点上采用一个版本号计数器，作为并发执行的读写操作之间的沟通媒介，避免每次写操作都需要申请锁的开销。其中，版本号在每次树节点状态被改变的时候递增，对于插入、删除或者更新操作，在修改树节点之前申请锁，并将版本号置为脏，在完成操作后将版本号加1，然后释放掉这个树节点的锁，如果版本号被修改或者被加锁，读操作就会重复执行上述过程，直到版本号验证通过。

另一方面，对于写写操作间的冲突，可以采用树节点粒度的锁确保修改不同树节点的写操作同时执行，因为写操作只需要持有将要修改的树节点的锁，每个写操作通过版本号验证的方式到达目标叶节点，叶节点之间通过右指针相连，并且规定叶节点的分裂方向只能从左往右，避免分裂操作导致的无法找到目标键值对的情况。下一步自底向上申请树节点的锁，并且只有在树节点发生分裂或者删除时，才会申请上一层树节点的锁。因为链表节点和叶节点的键值对有一一对应的关系，所以写操作只有在获取树层对应叶节点的锁之后，才会去修改链表节点。因此，树节点的并发控制机制同时解决了链表层次的并发冲突问题。

进一步地，本发明的实施例提出并发控制机制，通过版本计数器，该数据结构可以支持乐观读。在乐观读机制中，一个读操作将获取现有版本的快照而不需要对当前版本进行锁定，接着读取数据并检查版本，其中，如果版本没有改变或者没有被标记为脏，则表明读操作成功，并且通过不需要锁定位的设计，读并发机制就可以得到改善。对于写写冲突，该数据结构对每一个先树节点锁使用版本和锁定，首先，一个写操作定位好需要写的节点，定位节点通过自顶向下的读操作来确定，当需要写的节点被定位后，写操作对节点写入锁定位，并开始写操作和持久化过程。对于任何需要平衡的写操作，都需要从该数据底层到上层的锁，通过上述方法，该数据结构支持前树节点的锁，而不是整个树的锁。对于一个插入操作，首先，在进行写操作和持久化之前，对锁定操作位进行锁定并增加版本计数器，在上述情况下，版本计数器增加。其次，对叶子节点进行写操作和持久化操作，最后增加版本节点号并释放锁。对于一个读操作，执行查找和读操作，并把快照的版本与最新的版本进行比较，如果版本是脏的和被修改的，则读操作失败，重新启动验证直到成功为止。

具体地，对于读写冲突，因为写操作过程中在叶子节点层将版本设置为脏，并在写操作结束后将版本增加，所以较长的写执行时间将会导致较高的读中止的概率。因此，对于读操作，即使是读取其他键的操作，也将在版本号被清除和不变之前一直不停地尝试，此操作将会导致较高的读中止率。其中，持久化延迟可以从版本验证关键路径上移除，具体过程为，在链表层基于元素的组织方式允许进行元素粒度的控制，首先，该数据结构使用一个嵌入式微型指针，该指针包括更新位置和删除位置，其次，叶子节点综合的数组和链表层可以同时支持乐观读和元素粒度的写锁定，对于每一个链表节点都使用版本计数器，链表层可以对每一个正在被修改的元素提供锁定。基于上述说明，链表节点可以使用嵌入式的微型锁来执行持久化操作，而不会产生任何对其他键的读操作。在持久化操作后，链表节点更新在数组节点中的版本号，持久化延迟就会从版本验证的关键路径中移除。在本发明实施例中，对于更新和删除操作，该数据结构需要设置嵌入式位以表明链表节点正在被修改。其中，在插入和持久化链表节点后，使用版本机制对数组层进行更新。最后，该数据结构解锁嵌入式位和数组节点，嵌入式位仅为了调度，因此不需要进行持久化。对于删除操作，只设置了删除位而回收内存空间防止读操作访问到空悬指针。

对于写写冲突，与读写冲突类似，写操作中的持久化开销同样会延迟写操作的锁定。其中，对于位于叶子节点层的链表层，该数据结构允许对同一个叶子节点的不同键进行并发写。为达到此并发写，第一部分是针对那些正在生成的插入节点，节点还没有被连接到链表中，这部分节点可以随机地被写入和持久化。第二部分是正在被修改的节点，包括插入、删除、更新的节点。一个原子性的CAS操作可以改变链表节点的状态，可以通过解耦链表层和数组层并发控制来实现。具体地，允许对不可访问的节点采用随机访问。一个插入操作将伴随两个持久化操作，一个是节点持久化，将持久化新生成的链表节点以及指向下一个节点的指针，该操作将使得链表中的节点可以访问。基于上述说明，该数据结构的一个插入操作可以在链表节点被生成和持久化的时候不需要产生锁，而锁只需要在该节点被指向以及前一个节点的指针被更新和持久化的时候产生。

首先，每一个插入操作通过版本验证获得前一个和后一个链表节点的插入位置，接着需要一个新的链表连接兄弟指针到下一个节点中去，并持久化整个节点。其次，获取数组锁，并决定前一个或后一个节点是否被修改，如果没有，直接连接前一个节点的指针到后一个节点，持久化节点并使用版本机制更新数组层，否则，将采用传统的基于锁的方式来执行插入操作。最后，对锁进行释，链表节点的持久化代价将会从锁定路径上移除。对于数组层和链表层的并发控制进行解耦合，链表层通过一系列CAS的指令可以原子性地在DRAM中实现无锁的并发机制。但是，CAS操作指令并不能保证NVM中的持久性原子性写。具体地，可以通过一个持久性的CAS操作保证以下几方面。首先，对一个共享变量的原子性更新。其次，持久化包含共享变量的缓存行来保证更新的持久性。易失性的CAS将在持久性内存中导致不正确的行为，当一个并发读操作读取到一个共享变量的值，并基于读操作做出一个持久性写操作，当系统异常出现在写操作的过程中时，将会导致系统不一致。为保障并发并发操作的一致性，该数据结构需要持久化的CAS操作等待持久化来操作链表节点，当修改还没有对叶子层可见，可见性通过嵌入式的微型锁实现，持久化的CAS操作通过解耦链表层的原子性和数组层的持久化可见性实现。对于每一个插入操作，首先，确定目标的前一个节点和后一个节点，接着将新的链表节点指向下一个节点并将其持久化。其次，使用CAS原子性地修改前一个节点的兄弟节点并对其进行持久化，新插入的元素仅仅在其插入到上一个层次的时候才可见，如果CAS指令执行失败的话，将从第一步重新开始执行，否则将使用基于锁的机制插入上一层节点并对全局可见。

进一步地，对于每一个删除操作，定位需要删除的节点，逻辑性、原子性地使用CAS指令删除具有删除标志的节点。其次，物理性地删除通过修改和持久化前一个节点的指针并自动地指向下一个节点。该数据结构同样可以使用CAS指令检查目标节点是否正在被修改或删除和前一个节点是否被修改。对于每一个修改现存键的更新操作其并发控制机制与删除操作类似，不同的是，链表节点通过更新更新位来通知链表节点正在执行的是更新操作。

具体地，本发明实施例的数据结构的一致性主存管理机制，在每次分配和释放一个链表节点之前，每次从系统主存分配器中分配较大一块非易失主存空间，并且将这块空间的地址和长度持久化到一个持久性链表中，然后将分配到的主存空间分割成特定大小的主存块，并通过一个易失性的空闲主存块链表维护，用于链层的主存分配和释放操作。在系统恢复时，恢复线程扫描持久性链表上的元数据信息和链层的节点，判断出正在使用的和没有被使用的主存块，从而重建易失性的空闲主存块链表，只有在小的主存块都被使用后，才会再次从系统主存分配器中分配新的主存。

具体地，本发明实施例的数据结构的一致性主存管理机制，通过维护一个全局的epoch计数器和三个垃圾回收链表来正确回收被释放的树节点和链表节点。在执行相关操作前，首先，工作线程注册现有的epoch号，对于每个删除的树/链表节点，线程根据当前的全局epoch号将其放置到对应的垃圾回收链表中。其中，如果目前的epoch号为T，删除的节点会被放置到第[T mod 3]垃圾回收到链表中，当垃圾收集器想要将垃圾回收链表上的主存块移动到空闲主存块链表上时，首先，检查所有的工作线程是否都已经处于目前的epoch号中，如果检查成功，递增全局epoch号。通过上述的方法，确保所有的线程都处于epoch号T和T+1的范围内，从而将epoch号T-1对应的垃圾回收链表上的主存块安全回收。

具体地，本发明实施例的数据结构的多线程恢复机制，当系统正常关机时，将所有易失性的内部树节点和垃圾回收器持久化到非易失主存的某个特定位置，当系统重启后，恢复线程将所有易失性的内部树节点和垃圾回收器从非易失主存拷贝到DRAM中，在很短的时间内就可以完成系统重启的过程。当系统发生异常后进行恢复时，回收线程在离线的状态扫描所有的链表节点，重建所有的内部树节点和垃圾回收器。具体地，在系统正常执行过程中，使用一组持久性跟踪器记录一些链表节点的位置，在每执行一万个插入操作时，跟踪器会随机记录新的链表节点的主存地址，并持久化到非易失主存的一个预留区域，当跟踪的链表节点被删除时，对应的跟踪器也要被重置。在系统的恢复过程主要包含两个阶段：首先，在第一个阶段，根据跟踪器记录的链表节点的键值，对跟踪器进行排序，然后分发给恢复线程，每个线程独立地扫描不相交的链层的链表节点，重建数据结构。其次，在第二个阶段，在重建不相交的部分后，使用一个线程将这些部分构建成一个完整的数据结构。

本发明的实施例以非易失性内存场景下存储系统的索引数据结构为优化对象，针对当前基于主存的存储系统，提出一种在传统的B+树中引入一层基于链式结构的影子叶节点，并采用基于混合主存的数据布局策略，将基于链表的叶节点存储在NVM中，其它部分存储在DRAM中，消除了排序和平衡操作带来的持久化开销，设计了嵌入式的细粒度锁和乐观写机制，分别用于读写操作之间和写写操作之间的并发控制，其中，嵌入式的细粒度锁机制，为每个链表节点设计一个更新标记位和删除标记位，这种细粒度的并发控制机制，将不必要的持久化延迟从读操作的版本验证路径上移除，而乐观写机制将树节点和链表节点的并发控制机制进行分离，进一步将持久化延迟从树节点粒度的加锁路径上移除，减少写操作与写操作之间的并发冲突。可选地，本发明的实施例还设计持久性垃圾回收器，用于支持非易失主存的一致性管理，最后通过多线程恢复技术加速了系统崩溃时该数据结构的恢复过程。

接下来根据具体实施例来对本发明的多线程持久性B+树数据结构设计与实现方法进行详细说明。

如图2所示，本发明的实施例支持多线程持久性并发访问的B+树使用DRAM和NVM混合主存架构，在DRAM中是一个与传统B+树类似的树型结构，用于运行时的索引，在NVM中是一个基于链表的数据结构，用于存储所有的用户数据及其关系，系统在非运行状态时，只保存位于NVM上的链表结构，当系统重新启动或异常恢复时，使用位于NVM上的链表结构重构位于DRAM中的树型数据结构，并在运行时使用树型数据结构加速并发索引过程。

在本发明实施例中，可以采用预取机制减少访存延迟，对于树的搜索从根节点开始，直到找到对应的叶节点为止，由于此过程需要读取搜索路径上的所有叶子节点，这些树节点的访存延迟将会严重影响整个树的查找性能。为解决此问题，本发明实施例中在访问每一个树节点之前，执行一个预取指令，将整个树节点预取到CPU缓存中，从而掩盖了整个树节点的访存延迟，并且分别将键数组和值数组缓存在不同主存空间中，只预取键数组，降低每次预取操作的数据总量。

在本发明实施例中，采用SIMD机制加速处理过程。其中，线性查找操作是在连续的主存空间上执行的，所以可以利用Single Instruction Multiple Data(SIMD)指令进行加速。多数的现代处理器都支持SIMD指令，支持同时对多个数据执行相同的算术或者比较操作。对于查找操作，使用SIMD比较指令同时将目标键值与多个不同键值进行比较。在排序和平衡操作中也使用了相似的优化策略，从而可以同时移动多个数据，本发明实施例使用24核英特尔处理器支持256比特的SIMD操作，因此，该数据结构可以同时比较32个指纹，加速了叶节点的查找过程。

在本发明的实施例中，采用基于版本号的并发控制机制和树节点粒度的锁，确保修改不同树节点的写操作可以同时执行，图2给出了版本号的结构，版本号使用一个32位的字节序列结构。其中，第一位为是否被锁定的标识符，第二位是是否为根节点标识符，第三位是是否为叶子节点标识符，后29位是递增的版本号，该版本号在每次树节点状态被改变时递增。

在修改树节点之前申请这个树节点的锁，然后将版本号置为脏，并在完成操作后将版本号加1，然后释放掉该树节点的锁。对于查询操作，在读取树节点之前记录下这个节点的版本号，在完成读操作后将这个树节点最新的版本号与之前记录下的版本号进行对比，判断这个树节点是否在读取过程中被其它操作所修改，如果版本号被修改或者被加锁，读操作就会重新执行上述过程，直到版本号验证通过。

在本发明实施例中，过高的持久化延迟会堵塞相同叶节点不同键值对的其它写操作。基于数组结构的树节点上每个键值对都与相邻的键值对有很强的关联关系，任何一个写操作都可能触发昂贵的平衡操作(修改同一个树节点的大部分键值对)，因此，难以设计键值对粒度的锁，用于协调访问相同叶节点不同键值对的并发写操作，并通过乐观写机制将持久化延迟从树节点的加锁路径上移除。

在本发明实施例中，索引结构使用互斥锁将那些修改临界区数据的写操作顺序化，避免写操作之间的并发冲突。因此，对非临界区数据进行修改的持久化操作可以从互斥锁路径上移除。

如图3和图4所示，是该数据结构对读写冲突和写写冲突的处理步骤。对于读写冲突，每个插入操作首先定位到插入的位置，获取到前置和后置链表节点。对于更新操作，第一步，申请一个新的链表节点，将右指针指向后置节点，并持久化整个链表节点。第二步，获取树层叶节点的锁，判断前置和后置节点是否已经被修改。第三步，如果没有被修改，将前置节点的指针指向新节点并持久化。第四步，更新叶节点的键值对和版本号。第五步，如果被修改则将按照传统基于锁的方式执行插入操作，并释放锁。通过上述的优化策略，将不修改链层的持久化操作从加锁路径上移除。值得注意的是，在第一步和第三步之间发生的系统崩溃不会导致非易失主存的泄漏。

在本发明实施例中，对于读操作，通过以上描述的第一，二，三步，通过版本号验证的方式得到对应的链表节点指针，通过以上描述的第四步，读取到链表节点的数据，然后检查这个节点的嵌入标记位。其中，如果标记位被设置为脏，说明读取的链表节点正在处于更新或者删除的状态，如果更新标记位为脏，读操作会一直等待，直到更新操作完成并被持久化。如果删除标记位为脏，读操作会从根节点重做。具体地，基础的读写并发控制机制和基于嵌入式的细粒度锁的读写并发控制机制的区别：后者将针对相同叶节点不同键值对的写操作的持久化开销从读操作的版本号检查路径上移除。

在本发明实施例中，链层只需要通过一系列的CAS操作就可以执行保证原子性的更新操作，并且嵌入式的细粒度锁支持修改的键值对只有在持久化操作完成后才会可见。通过上述两项技术，将树层和链层的并发控制机制进行分离，在持久性链层采用键值对粒度的并发控制机制，在易失性树层采用树节点粒度的加锁并发机制，从而将链层的持久化开销从树节点的加锁路径上移除。对于每个插入操作，通过版本号验证的方式定位到插入的位置，获取到前置和后置节点。其中，第一步，分配新的链表节点，并将其指向后置节点，然后执行持久化操作。第二步，通过CAS指令将前置节点的右指针指向新的链表节点。由于前置节点的状态存储在右指针中，CAS操作也被用来避免将新节点插入到被删除的链表节点之后，传统的原子操作无法保证数据的持久性。

在本发明实施例中，新插入的链表节点只有在被更新到上层的树节点之后才会可见，从而避免被其它操作看到未被持久化的新节点。该数据结构在持久化新链表节点和前置节点的指针后，采用传统的基于锁的方式将新键值对插入到上层的叶节点中使其可见。对于每个删除操作，删除一个现有的键值对。首先，定位到目标链表节点，使用CAS操作设置删除标记位，完成逻辑删除操作，避免其它线程将任何新生成的链表节点插入到这个将要删除的节点后面，否则可能导致新节点的丢失。其次，原子性地修改前置节点的右指针，将其指向后置节点并持久化，完成物理删除操作，使用CAS操作检查目标节点是否正在被删除或者更新，和前置节点是否正在被删除。该数据结构在完成上述操作之后，将该键值对从上层树节点中删除。对于每个更新操作，修改一个现有的键值对的值。除了目标更新节点，更新操作并不影响链层的其它节点，所以并发控制机制十分简单。通过更新标记位，通知其它线程这个链表节点正处于被更新的过程。图3(c)显示两个插入操作的并发执行过程，本发明实施例中所描述的数据结构将链表层次的持久化延迟从树节点粒度的加锁路径上移除。

在本发明实施例中，为保证链层的一致性和持久性，在系统崩溃时，未完成的操作(例如插入和删除操作)可能导致新分配的链表节点的丢失，导致主存空间的泄露，并且读操作可能看到一个正在被其它线程删除的链表/树节点。为解决上述问题，该数据结构设计轻量级的一致性主存管理和一个持久性垃圾回收器。

本发明实施例中，每次从系统主存中分配较大一块非易失主存空间，并且将这块空间的地址和长度持久化到一个持久性链表中，将分配到的主存空间分割成特定大小的主存块，并通过一个易失性的空闲主存块链表维护，用于链层的主存分配和释放操作。在系统恢复时，恢复线程扫描持久性链表上的元数据信息和链层的节点，判断出正在使用的和没有被使用的主存块，从而重建易失性的空闲主存块链表，只有在这些小的主存块都被使用后，才会再次从系统主存分配器中分配新的主存。

本发明实施例中，避免读操作看到正在被其他线程删除的链表节点和树节点，通过维护一个全局epoch计数器和三个垃圾回收链表来正确回收被释放的树节点和链表节点。其中，在执行该数据结构的操作前，首先，工作线程注册现有的epoch号。对于每个删除的树/链表节点，线程根据当前的全局epoch号将其放置到对应的垃圾回收链表中，如果目前的epoch号为T，删除的节点会被放置到第[T mod 3]垃圾回收链表中，当垃圾收集器想要将垃圾回收链表上的主存块移动到空闲主存块链表上时，首先检查所有的工作线程是否都已经处于目前的epoch号中，如果检查成功，就递增全局epoch号。通过上述的方法，确保所有的线程都处于epoch号T和T+1的范围内，从而将epoch号T-1对应的垃圾回收链表上的主存块安全回收。

本发明实施例中，采用多线程恢复机制加速系统恢复进程，将所有易失性的内部树节点和垃圾回收器持久化到非易失主存的某个特定位置。当系统正常关机后重启时，恢复线程将所有的易失性的内部树节点和垃圾回收器从非易失主存拷贝到DRAM中，在很短的时间内完成系统重启。当系统异常恢复时，回收线程在离线的状态扫描所有的链表节点，重建所有的内部树节点和垃圾回收器。具体地，在系统正常执行过程中，使用一组持久性跟踪器记录一些链表节点的位置，在每执行一万个插入操作时，跟踪器会随机记录新的链表节点的主存地址，并持久化到非易失性主存的一个预留区域，当跟踪的链表节点被删除时，对应的跟踪器也要被重置。

当系统恢复时，恢复过程主要包括两个阶段：第一个阶段，首先根据跟踪器记录的链表节点的键值，对跟踪器进行排序，然后分发给恢复线程，每个阶段独立地扫描不相交的链层的链表节点，重构该数据结构；第二个阶段，在重建不相交部分的数据结构后，使用一个线程将这些部分重构成一个完整的数据结构，该机制可以有效地减少线程之间的冲突。

本发明实施例的多线程持久性B+树数据结构设计与实现方法，通过使用非易失性内存和易失性内存的混合主存数据结构，使得具有良好空间局部性和平衡性的搜索操作，有效地减少了昂贵的持久化操作，并且还设计嵌入式的细粒度锁和乐观写机制，解决放大的锁开销问题，同时采用多线程的恢复机制和持久性垃圾回收器，用于支持非易失主存的一致性管理，并加速数据结构的系统恢复过程。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。