一种基于远程直接非易失内存访问的B+树管理方法

摘要

本发明涉及一种基于远程直接非易失内存访问的B+树管理方法。该方法将完整的B+树的内部节点存放在DRAM上，DRAM上的易失叶子节点只包含关键字，其对应的数据存放在非易失内存上的叶子节点中，每个易失叶子节点关联一个非易失叶子节点；客户端通过RDMA原子操作获取远程锁，然后发送B+树的操作命令至服务端；服务端在对应的非易失叶子节点中预留远程操作的空间，再由客户端使用RDMA的远程写技术采用日志的方式将数据直接持久化到服务端的非易失叶子节点中。本发明使用客户端协作服务端对基于非易失内存的B+树的操作，在并发访问的情况下，减少了服务端的处理负担；此外，采用日志的方式操作非易失叶子节点，缓解了NVM的写磨损。

说明书

技术领域

本发明涉及一种B+树的管理机制，特别是一种基于远程直接非易失内存访问的B+树管理方法。

背景技术

索引作为存储系统功的重要组成部分，能够加速数据的查找。作为使用广泛的B树类的索引结构，最初是针对磁盘的访问特征设计的一种平衡多路查找树。对于一个m阶的B树其主要的特性有：每个节点最多有m棵子树；除了根节点外，其他的节点至少有m/2(取整)棵子树；根节点至少有两棵子树，除了B树只包含一个节点；所有的叶子节点都在同一层上；所有节点上的数据按照关键字有序排列。B树的节点的大小通常和磁盘的块大小一致，这样每次查找一个元素读取其所属的一个节点预取至内存，既能够充分利用磁盘的带宽，也能提升其他节点的查找性能。而作为B树的一种变形索引结构-B+树，其比B树更具有实际应用价值，如数据库；因为B+树的内部节点不包含具体的具体数据信息,其内部节点占用的空间更小，也就是说，相同大小的内部节点B+树能容纳的关键字数量更多；因此，一次加载到内存中关键字就更多；此外，B+树的查找效率更加稳定，因为其内部节点不包含任何的实际的数据，只存放用于索引的关键字，所有的实际数据(或指向实际数据的指针)都存放在叶子节点上，这样，每个元素的查找都有相同的路径长：从根节点遍历到叶子节点。但是，随着计算机技术的发展，内存和磁盘的性能差距的越来越大，磁盘的性能已不能满足海量数据的分析的需求；数据的存储架构已逐渐以内存为中心；而新型存储器件，如PCM(相变随机存储器)、3D Xpoint, 拥有外存的非易失性、高集成度和内存级的访问速度等特性，能弥补现有的DRAM(动态随机存取存储器)的易失特性、高能耗以及容量有限的不足，基于这些器件构成的非易失内存(NVM, Non-Volatile Memory)成为计算机设计和研究者改善存储系统性能的热门。诚然，针对非易失内存的索引结构的设计也面临新的挑战，比如非易失内存将原先的数据持久化层次外存提升到了内存以及其本身存在的写磨损等问题；一般来讲，内存级的数据持久化是通过显式地将CPU cache中的数据刷新到内存上，对于B+树而言，由于叶子节点上的元素的有序性，元素的插入操作会导致数据的移动，从而产生很多的CPU cache刷新的开销，致使B+树的性能降低；并且在多核的系统中，单线程的B+树操作性能的降低会使其占据锁的时间过长，这样会导致多线程的并发竞争更加激烈，进一步降低了B+树的性能和系统资源的利用率；现有的单机已经不能够满足大数据存储需求，不过在分布式环境下，由于B+树的处理是以服务端为中心的，所以基于非易失内存的B+树设计面临着相同的挑战，如数据持久化与并发性能的权衡以及NVM的写磨损等。

本发明通过RDMA(Remote Direct Memory Access，远程直接访问内存技术)远程访问非易失内存，与客户端共同协作实现B+树的叶子节点的以日志方式进行数据持久化，一方面简化服务端B+树的处理流程，提升B+的整体性能，另一方面延长了NVM的写寿命。

发明内容

为了解决上述的技术问题，本发明的目的是提供了一种基于远程直接非易失内存访问的B+树管理方法。该方法将完整的B+树的内部节点存放在DRAM上，DRAM上的易失叶子节点只包含关键字，其对应的数据存放在非易失内存上的叶子节点中，每个易失叶子节点关联一个非易失叶子节点；客户端通过RDMA原子操作获取远程锁，然后发送B+树的操作命令至服务端；服务端通过解析客户端的命令消息，对于插入操作命令，在对应的非易失叶子节点中预留远程操作的空间，再由客户端使用RDMA的远程写技术采用日志的方式将数据直接持久化到服务端的非易失叶子节点中。本发明使用客户端协作服务端对基于非易失内存的B+树的操作，在并发访问的情况下，减少了服务端的处理负担；此外，采用日志的方式操作非易失叶子节点，缓解了NVM的写磨损。

本发明解决其技术问题所采用的技术方案是：

一种基于远程直接非易失内存访问的B+树管理方法，包括：

第一步，客户端通过RDMA的原子操作竞争B+树的操作锁，在成功获取操作锁之后，将关键字和数据长度以及操作命令的消息，发送至服务端注册至网卡的DRAM内存中；

第二步，服务端解析已接收消息中的信息字段，根据相应的命令操作存放在DRAM中完整的B+树；

第三步，服务端为存放在DRAM中的B+树的每个易失叶子节点关联一个非易失叶子节点，这些非易失叶子节点已注册至网卡上；

第四步，如果客户端的B+树命令是插入操作，服务端直接返回非易失叶子节点的当前操作的地址；如果命令是删除操作，则服务端在非易失叶子节点的当前操作位置写入删除标识，然后返回删除标识的首地址至客户端，更新下次非易失叶子节点的下次操作的地址；如果命令是读操作，则服务端直接返回数据至客户端；

第五步，对于插入操作，客户端通过RDMA远程写操作将数据直接写入到返回的非易失叶子节点地址，并通过RDMA原子操作释放B+树的操作锁；对于其他操作，则直接释放B+树的操作锁；

第六步，服务端定期地判断非易失叶子节点的可用空间，并选择一定数量的叶子节点，回收其中无效的垃圾数据。

使用本发明能达到以下有益效果：首先，B+树的内存节点全部存放在DRAM中，包含数据的叶子节点存放在NVM中，一是保证了B+树的遍历的性能，二是能够使得B+树从系统崩溃中恢复；其次，由客户端获取/释放锁同步处理客户端的请求，有利于利用RDMA的性能；再者，B+树的只包含关键字的有序的易失叶子节点和包含无序数据的非易失叶子节点，减少了对NVM的磨损的同时，保证了范围查找的性能；最后，通过客户端利用RDMA远程写非易失叶子节点，减少了服务端的数据持久化开销。

附图说明

图1是基于远程直接非易失内存访问的B+树管理流程图；

图2是DRAM中的B+树叶子节点的元素格式图；

图3是B+树的分裂和覆盖写时拷贝机制示意图。

具体实施方式

参照图1，本发明提供了一种基于远程直接非易失内存访问的B+树管理方法，包括:

第一步，客户端通过RDMA的原子操作竞争B+树的操作锁，在成功获取操作锁之后，将关键字、数据长度(可选)以及操作命令的消息，发送至服务端注册至网卡的DRAM中；

第二步，服务端解析已接收消息中的信息字段，根据相应的命令操作存放在DRAM中完整的B+树；

第三步，服务端为存放在DRAM中的B+树的每个叶子节点关联一个存放在非易失内存上的叶子节点；

第四步，如果客户端的命令是插入操作，服务端直接返回非易失叶子节点的当前操作的内存地址；

第五步，如果命令是删除操作，则服务端在非易失的叶子节点的当前操作位置写入删除标识，然后返回删除标识的首地址至客户端；

第六步，服务端更新下次非易失叶子节点的下次操作的内存地址；

第七步，对于插入操作，客户端通过RDMA远程写操作将数据直接写入到返回的非易失内存地址，并通过RDMA原子操作释放B+树的操作锁；对于其他操作，则直接释放B+树的操作锁；

第八步，服务端定期地判断非易失内存上的叶子节点的可用空间，并选择一定数量的叶子节点，回收其中无效的垃圾数据。

进一步作为优选的实施方式，所述的步骤一，还包括：

对于较小的数据，例如大小小于64字节，将数据和命令一起发送至服务端，由服务端将数据持久化至非易失内存的叶子节点中。

进一步作为优选的实施方式，所述的步骤二，其具体为：

服务端对于B+树存放在DRAM中的操作和原先的B+树的操作一样，存放在DRAM中的叶子节点的元素保持有序，这个叶子节点中的元素不包含实际的数据信息，而实际的数据信息存放在对应的非易失叶子节点中，DRAM叶子节点中的元素包含关键字、对应数据存放在非易失叶子节点中的偏移量，偏移量以64字节为单位，存放在指针变量中，占用指针变量的14个比特位，非易失内存指针变量的格式参考附图2。

进一步作为优选的实施方式，所述的步骤三，其具体为：

作为B+树的非易失叶子节点，客户端可以通过RDMA远程直接访问；在服务端关联DRAM中的易失叶子节点和非易失叶子节点之前，需要将所有的非易失叶子节点注册到网卡上，考虑到内存的注册开销，所以服务端一开始预注册一定量的非易失叶子节点，当非易失叶子节点的数量低于一定阀值时(例如50%)，则动态增加非易失叶子节点的数量；由于非易失叶子节点需要存放实际的数据，所以这个非易失叶子节点的大小是易失叶子节点的数倍(默认值是4)；

进一步作为优选的实施方式，在所述的步骤四，其具体为：

B+树的插入操作，最简单的流程是返回非易失叶子节点的内存地址至客户端，用于客户端远程写实际的数据；但是，B+树的插入操作为引起非易失叶子节点的分裂(分裂的条件一般是在节点中包含的元素的个数超过B+树阶数的一半时)，对于叶子节点分裂流程，首先按照B+树正常的分裂算法创建新的非易失叶子节点；其次为新的叶子节点关联非易失叶子节点，由于在被分裂的节点关联的非易失叶子节点中，存在着属于新分裂出的易失叶子节点的数据，为了减少分裂的开销，这些需要移动的数据不是在分裂时进行迁移，而是延迟在数据覆盖写时复制，参照附图3；在覆盖写时复制时，在原先的非易失叶子节点中写入写时删除标识即可，新的数据将会直接写入到新的非易失叶子节点中。

进一步作为优选的实施方式，在所述的步骤五，其具体为：

B+树的删除操作，遍历查找到其所在的非易失叶子节点，在非易失节点的当前操作的位置写入直接删除标识(与写时删除标识的类型不同)；和插入操作一样，删除操作为导致易失叶子节点的合并，类似地，首先将候选的两个易失叶子节点合并，其原先的非易失叶子节点中的数据不在合并时迁移，而是在数据覆盖写时复制；在数据完全迁移完后， 释放这个非易失叶子节点；

进一步作为优选的实施方式，在所述的步骤六，其具体为：

对于B+树的插入和删除操作都会涉及到非易失叶子节点操作，而非易失叶子节点的数据操作是类似于日志append的方式，所以在上述操作之后，需要更新当前的操作位置，对于插入操作，以数据的长度向后移动当前操作位置；对于删除操作，则根据删除标识的不同类型的长度向后一定当前操作位置；

进一步作为优选的实施方式，在所述的步骤七，其具体为：

由于B+树的插入操作没有实质性的数据写，数据的写由客户端进行；一般地，使用RDMA的普通远程写可以保证数据能够到达远端的网卡，但是不能保证数据一定在远端的内存中，这种方式的远程写，称为弱远程持久化；另一种，是通过RDMA远程立即数写，通知数据已经到达远程非易失叶子节点，这种是强远程持久化，在这种模式下，锁的释放由服务端进行。

进一步作为优选的实施方式，在所述的步骤八，其具体为：

B+树的非易失叶子节点的日志操作方式，使得叶子节点中存在很多的垃圾数据；在插入或删除操作的过程中，当非易失叶子节点的空闲空间不足时，主动触发垃圾回收的过程，而定期扫描非易失叶子节点回收垃圾数据，是为了减少在插入操作或删除过程中主动垃圾回收的开销；隐式的垃圾回收选择的非易失叶子节点，根据易失的叶子节点中记录的删除标识数量选择叶子节点，删除标识的个数越多，表明垃圾数据越多；回收垃圾数据的流程，直接遍历选定的易失叶子节点中的元素，在非易失叶子节点中定位对应的有效数据，将数据拷贝至新分配的非易失叶子节点，重复这个过程直至遍历完易失叶子节点中的所有数据，最后释放原先的非易失叶子节点。

以上是对本发明的较佳实施进行了具体说明，但本发明创造并不限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可作出种种的等同变形或替换，这些等同的变型或替换均包含在本申请权利要求所限定的范围内。