远程持久性和写合并的混合部署R树

吴 瑶,张 瑞,吴 杰

(复旦大学 计算机科学技术学院,上海 200433)

1 引 言

近年来,随着信息技术的不断发展和智慧城市进程的推进,数据量急剧增长.其中,存在着大量的空间数据.从最初的地图导航到外卖应用的骑手定位,空间数据已经渗透到生活的各个方面.这些大数据在为人民生活提供便利的同时,随之而来的是其在技术层面上带来的存储、处理及分析难题.通常情况下,为了解决数据的快速响应问题,过去大量的研究提出了基于DRAM内存存储和计算(例如,Redis、spark)来解决处理速率问题[1].

然而由于DRAM容量的限制(单根最大容量128GB)、昂贵的价格、高功耗,以及虽然将数据从磁盘移动到DRAM,由DRAM作为缓存其访问时延缩短约原本的10,000分之一,但是当通过网络访问远端内存时,其速度优势会被大大减弱[2].因此,随着当前对更大内存的需求的不断扩大,持久性内存(Persistent Memory,PM),即非易失性内存(Non-Volatile Memory,NVM),其具有存储密度高、按字节粒度寻址、DRAM级别的访问时延和低功耗的特点.它弥补了DRAM与SSD/Disk之间的容量和性能差距.

由于第一款实际可商用的英特尔傲腾持久性内存正式发布于2019年4月[3].之前大量的研究工作[4-6]基于有关持久性内存的假设和DRAM模拟实验进行设计.然而,尽管傲腾持久性内存的特性符合以前研究中对持久性内存的许多假设(例如,非对称读写),但其同时被观察到一些其他的特性,这要求设计者重新考虑之前基于持久化的设计.例如256字节的内部访问粒度和读时延约为DRAM的3.7倍等.

为了支持高效的空间数据查询,几十年来,空间数据库一直依赖于高效迅速的索引.然而,随着当前基于位置的服务的普及,以谷歌Maps[7]为例,其需要管理数以亿计的具有各种分布的空间对象,并在2017年达到了处理10亿用户请求的规模.因此,空间索引(如四叉树[8]、KD树[9]、R树[10]、网格索引[11]等)对空间对象的快速检索和大规模处理至关重要.其中,R树是最流行的空间索引.由于它能够快速排除与被访问的地理位置不相关的对象或集合,避免访问没有所需数据的数据块.因此,极大地提高了空间索引的效率,在商业数据库系统中得到了广泛的研究,如Oracle Spatial等.然而,原始的传统R树在面对不断增长的数据规模时,必须进行频繁和有效的快速更新,难以满足低时延需求,且很容易受到DRAM容量的限制.与此同时,远程直接内存访问(Remote Direct Memory Access,RDMA)技术允许通过远端内核绕过和零拷贝,从而实现高带宽和低时延的远程内存访问.目前,RDMA已经被广泛应用于数据中心来加速分布式通信消息传输[12,13].因此,如图1所示,大容量、低时延的持久性内存和RDMA技术有望成为解决数据中心中空间数据存储、处理和网络传输的重要手段.

图1 傲腾持久性内存结构图Fig.1 Structure of optane DC persistent memory

为了解决上述提到的持久性内存相比DRAM慢3～4倍的访问速度,256B的内部访问粒度导致的写放大和额外引入的昂贵的持久化开销,导致显著的性能下降和有限的可扩展性问题以及RDMA在同持久性内存结合使用时需要注意配置否则也会导致性能下降等问题,本文提出了RRtree,一个在数据中心中专门为大规模空间数据处理设计的基于混合PM-DRAM架构的远程持久性R树以提高空间数据索引的效率.本文的工作主要为以下几个方面.

1)分别分析了在DRAM内存和持久性内存上的构建的索引性能,随之提出了具有混合PM-DRAM架构的RRtree从而实现更高的效率和具有更大的持久性容量.

2)基于对PM特性的观察和分析,本文采用了选择性的元数据持久化和写合并机制,其目的是缓解写放大现象和尽可能地减少持久化的开销.

3)在实际傲腾持久化内存上用真实世界的数据集对RRtree进行了测试和评估.结果表明,RRtree明显优于当前已有的工作FBR-tree[14].

2 背景介绍

2.1 持久性内存和远程直接内存访问

持久性内存(PM)是对内存/存储层次结构的补充,它既有硬盘等外置存储的大容量以及持久特性,又有DRAM级的低时延与高带宽的高性能特性.英特尔傲腾持久性内存模块提供3种容量选项:128GB、256GB、512GB,并可直接接入在内存总线上.它支持两种操作模式.Memory模式:仍然作为易失性内存使用,DRAM被当作CPU和PM之间的缓存.App Direct模式:被识别为一个持久性设备,可以通过CPU的加载和存储指令直接访问.

为了支持数据持久化,英特尔提出如图1所示的异步刷新(Asynchronous DRAM Refresh,ADR).一旦写请求到达写等待队列(Write Pending Queue,WPQ),数据的持久性就得到了保证.但由于CPU cache仍然是易失的,可能导致数据在掉电或系统崩溃时无法及时写回PM或部分写回,从而破坏PM中的数据完整性,导致数据不一致.因此,为了确保故障原子性,Intel提供了缓存行刷新指令(CLFLUSH、CLFLUSHOPT和CLWB)来显式地将缓存行刷新到PM中.然而,由于这些刷新指令是非阻塞的,因此需要内存屏障指令(SFENCE、LFENCE、MFENCE)来约束写操作的顺序.但是,这些指令产生的持久化开销致使系统性能下降.因此,需要尽可能地减少不必要的持久化操作(缓存行刷新和内存屏障指令).

RDMA是一种面向高性能网络I/O,允许跨网络直接访问远端机器内存中数据的网络协议.RDMA协议消除了TCP/IP网络中内核缓冲区之间的内存拷贝开销.它可通过两类原语(单边和双边)进行数据的传输.单边原语(one-sided verbs):read、write、原子操作以及带立即数的写(write-imm),能够在没有远端主机CPU的中断处理下直接访问远端主机内存.双边原语(two-sided verbs):send和recv,需要接收双方CPU参与,与套接字编程中的原语类似.

然而,尽管PM和RDMA网络的出现为构建新型的存储系统提供了新的可能,若只是简单地将空间数据索引系统中网络传输模块替换为RDMA并将数据存储在PM上,而不进行其它优化改进,并不能保证数据的持久化以及充分发挥PM及RDMA网络的硬件优势[15].此外,在大型集群情景下,RDMA硬件可拓展性受到的其深层次技术限制[16].

当前,已有诸多国内外学者针对哈希表,B+树,ART树等数据结构提出了持久性优化方案[6,17,18].Level-hashing[6]提出了一种写优化的持久性哈希索引方案,其具有一致性保证和低开销的resize操作,可以在最坏的情况下实现恒定的时间复杂性,同时只引起少量额外的PM写入.Utree[17]是一个B+树的变体,优化PM中的长尾效应问题,并证明了该问题主要是由SMO引起的.ROART[18]基于ART索引结构提出了3个方面的设计目标,并支持可变长键和范围查询,以尽可能地减少持久化字的开销.然而,对于多维空间数据结构R树,除了FBR-tree,没有更多的研究,这对于高性能的大规模空间存储系统是至关重要的.

2.2 设计远程持久性R树主要问题和挑战

与B树不同,R树是一种存储空间对象的高度平衡树,由一组最小边界矩形(Minimum Bounding Rectangle,MBRs)组成.其每个节点(根除外)的大小∈[m,M],m=M/2,M为节点中的最大条目数.R树使用原始数据的覆盖矩形MBR作为索引的键.因为MBR的构造简单明了,易于查询和存储,对于一个二维空间数据对象,一个MBR只需要两个点(如左下角,右上角)来定义.R树遍历其最小边界矩形与给定范围相交的所有内部节点,直到找到包含重叠矩形的叶节点或返回失败.在傲腾持久性内存上设计远程持久化R树时,本文观察并总结了以下4个重要的挑战:

1)基于PM的R树索引性能下降.当将R树直接完全存储在PM上时,其性能不如内存中的R树高效.首先,表1对比了PM和DRAM随机读写时延,PM的随机读取时延比DRAM高约4倍,其写入性能在写入粒度接近256B时与DRAM相当.由于傲腾持久性内存内部数据访问的粒度是256B,所以在该访问粒度下可以达到更好的读/写性能.而CPU以缓存行的粒度刷入数据,从而导致持久性内存读/写放大.其次,其读取带宽为39 GB/s(4KB顺序访问6个傲腾模块的)明显高于写入带宽(13.2 GB/s).

表1 持久性内存/DRAM随机读写对比Table 1 Random Read/Write performance comparison

2)巨大的持久化开销.为了保证故障的原子性和空间数据的一致性,持久化R树必须引入持久化操作(FLUSH和FENCE).由于当前CPU可能会对内存写入重新排序,以进一步优化程序性能,从而造成部分更新问题.然而,在系统故障的情况下,部分更新可能会导致PM上的数据不一致.内存写入的原子性只能支持不超过内存总线宽度(一般64位CPU为8B).因此,更新大于8B的数据(空间数据通常大于8B)需要一定的机制来确保数据的一致性.同时,R树的非叶节点需要经常进行结构修改操作(Structure Mo-dification Operations,SMO)以确保运行效率,这将在PM上产生更多的持久化开销.

3)PM和RDMA结合使用时,需注意系统配置和优化[15].这是因为傲腾持久性内存具有一些额外特殊的硬件特性.首先,在基于RDMA的持久化系统中,发送端A在发起单向RDMA写入时是非阻塞的,即写入网卡后立即返回,而无法确保写入数据是否被真正持久化从而引发一致性问题.这是因为缺少远端持久化原语从而需要通过发起额外的读操作以保证数据持久性.该过程在引发了多个RTT导致其系统性能下降的同时增加了软件的复杂性.这将导致实际情况下更低的吞吐和更高的时延,减少了由于CPU绕过节省的开销.其次,数据直接I/O模式(Data Direct I/O,DDIO)对持久性内存是不友好的,会造成系统性能下降.由于DDIO使得原来的顺序写变成了随机写,造成了2倍左右写放大,50%左右的带宽下降.

因此,基于以上问题,本文设计了一种基于混合PM-DRAM部署架构,专门为大规模空间数据处理设计的快速、写优化的远程持久性RRtree.

3 RRtree设计

本节主要介绍了远程持久化RRtree的总体结构和叶子结点设计,以及具体的基本操作的执行流程.

3.1 RRtree总体结构

如图2所示,远程持久化RRtree由服务端和客户端两部分组成:客户端负责响应外部请求并将请求发送至服务端获取结果并返回外部;服务端上存储空间数据索引并负责响应来自客户端的请求(如查询、插入等)进行实际相关操作.客户端和服务端通过高速RDMA网络进行通信和数据传输.由于RDMA单边写操作在远程持久化内存中的表现不佳且RDMA单边写操作目前没有持久性语义,因此,本文采用基于RDMA双边原语的RPC进行消息传输.由于当采用RDMA双边原语时需要服务端CPU参与写入持久性内存,在对单个持久性DIMM写入时,会导致CPU扩展性下降.因此,RRtree在使用时对写入DIMM进行优化,减少对同一个DIMM的并发访问.此外,为了加速消息传输,RRtree允许“Doorbell batching”操作以减少CPU发起的PCIe总线事务从而来进一步减少CPU周期,节约开销.

图2 RRtree结构图Fig.2 Architecture of RRtree

服务器端存储的空间数据索引由内部节点和叶子节点两部分组成.由于R树是一棵平衡树,当一个新条目被插入时,可能会触发树的重新平衡(SMO)操作,会产生大量对PM不友好的随机小写.小于256B的读写会导致读写放大.且PM的性能相比DRAM慢3～4倍.因此为了实现更高效率的持久化R树,RRtree采取DRAM和PM混合部署的架构.一方面,实现了数据的持久化,另一方面实现了快速的索引操作.内部节点存储在DRAM上,负责存储索引信息,系统崩溃或掉电后可以恢复重建;叶子节点存储在PM上,负责存储指向实际的数据信息,即使在系统崩溃或掉电的情况下仍然被存储而不易失,可以作为依据对内部节点进行恢复.

3.2 RRtree节点设计

如图2中下半部分所展示的,RRtree的叶子节点由存储元数据(Lock、Count、Generation、Bitmap和Nextpos)的头部和实际条目组成.其中部分字段存储在PM上,需要被持久化.对于其余存储在DRAM上的字段,不需要进行额外的持久化操作从而移除部分持久化操作,缓解持久化开销.至于其内部节点的结构除了头部元数据中没有Nextpos字段以外,其余字段结构与叶子节点均相同,但是其全部存储在DRAM而非PM上.占据1bit的Lock和4B的Generation是为并发控制机制设计的.Count占据4B记录了节点上的条目总数.Bitmap用于验证相应位置上的条目是否有效,其大小根据实际节点上能存储的条目数决定.Bitmap和Generation的总大小不超过8B,所以它可以原子写入并持久化.Nextpos是一个48位的地址指针,用于指向当前节点的下一个相邻叶子节点.每个条目是一个键值对,包含一个MBR和指向该MBR范围的指针(每个指针占据48bit).若当前是2维MBR则一个条目的大小为22B.

若此时无法满足节点数目大小为256B,则采取缓存行对齐策略,通过使节点大小与256B对齐来避免对相同缓存行进行重复刷写.这是由傲腾持久性内存硬件本身的特性决定的.在进行持久化操作时,其会因为缓存行未对齐而被延迟执行从而影响系统性能.

3.3 恢复

由于部分节点未被持久化,因此在服务端系统崩溃或掉电后需要对RRtree进行恢复和重建.在恢复过程中,RRtree从PM的叶子节点信息中重建内部节点.该过程与完全重新开始从磁盘或硬盘中读取数据重建过程相比所消耗的时间更短.另外,RRtree使用一个持久化的状态位来指示最后一次关机是否正常.如果是正常关机,该位会在RRtree被持久化后被设置.否则,它将保持初始状态,以指示其因遭受系统故障.在重新启动时,通过扫描存储在静态地址上的最左边的叶子节点开始重建RRtree.并重新计算节点上的条目数,将结点上的Lock进行初始化,然后根据Nextpos字段找到下一个叶子节点,依次进行恢复.根据本文的实验,恢复12000万条空间数据键值对只需要1分钟.通过在PM中放置更多的非叶子节点,可以进一步减少重建时间,这需要对索引性能和重建时间进行进一步的权衡.

4 RRtree的基本操作

4.1 插入和删除

4.1.1 插入

RRtree的插入过程由客户端发起,通过RDMA操作码“IBV_WR_SEND”发送控制消息并注册本地缓冲区buffer;ibv_post_recv 接收控制消息,建立RDMA连接后,通过RDMAsend原语将待插入的数据发送到服务端,如图3所示.服务端在接收到请求后,服务端的插入流程如下:

图3 RDMA通信流程Fig.3 Workflow of RDMA

步骤1.执行遍历操作.从根节点开始遍历,依次检索子节点对应的包含所给定要插入的条目范围的子树,直到对应的叶子节点.

步骤2.检查Lock,获取父节点的锁.然后判断叶子节点是否已满.如果count

步骤3.获取叶子节点的锁.

步骤4.读取Bitmap并插入新条目,执行持久化操作.

步骤5.更新元数据并释放锁.翻转Bitmap对应的bit位并增加G(Generation)的值,对Bitmap和G执行持久化操作.

步骤6.释放父节点和叶子结点的锁.

步骤7.通过RDMA通信向客户端返回插入成功消息.

在上述插入过程中,RRtree共执行两个持久化操作.如果系统在第5步执行之前崩溃,数据结构的正确性将不会受到影响,因为Bitmap没有被修改,插入的条目仍然不可用.

算法1.插入算法

输入:根节点root,插入条目对象E

输出:成功/失败

1. 从根节点遍历,返回 Lnode &Pnode

2.ifisLock(Pnode)then//判断父节点Pnode是否被锁

3. 重试

4.else

5. GetLock(Pnode) //获取父节点的锁

6.if叶子结点已满then

7. 跳转执行分裂操作Split

8.else

9. GetLock(Lnode) //获取叶子节点Lnode的锁

10. 读取Lnode.Bitmap并在适当位置插入对象

11. Persist(E) //持久化对象E

12. Flip(Lnode.Bitmap) //翻转对应的bit

13. Update(Lnode.metadata) //更新有关元数据

14. Persist(E) //持久化有关元数据

15. Release(Lnode) &Release(Pnode)

16.Return成功

17.endif

18.endif

4.1.2 删除

插入的过程类似,首先,由客户端发起删除请求,并通过RDMAsend将待删除的数据发送到服务端.服务端接收到消息后执行删除操作,具体的删除过程如下:

步骤1.执行遍历操作.通过遍历树找到要删除的条目所在的叶子节点,然后获取锁.

步骤2.更新元数据.清除Bitmap的对应bit位,并增加G,并更新Count(减1)并释放锁.然后对Bitmap和G执行持久化操作.

步骤3.获取父节点的锁,向上更新父节点对应的覆盖矩形MBR.由于父节点的对应的MBR在删除后范围可能变化,因此更新MBR,避免范围冗余.这一步是否执行并不影响的结果正确性,但会加快后续搜索速度.由于此时内部节点存储在DRAM中,消除了持久化开销并不会引起较大的额外开销.

步骤4.通过RDMA通信向客户端返回删除成功消息.

4.2 分裂和汇聚

4.2.1 分裂

当客户端向服务端发起插入操作时,若要插入的条目所在的叶子结点已满,此时会引发RRtree的算法2分裂操作.分裂操作引发持久性内存分配、移动原始数据等操作,不可避免地引入额外的持久化操作.因此应当尽可能地减少或合并持久化操作.RRtree的分裂过程如下:

步骤1.获取要进行分裂的叶子节点的Lock.

步骤2.在PM上分配和创建一个新的持久化节点,并初始化节点元数据.(在内部节点分裂的情况下,节点从DRAM分配.随后的操作与叶子节点类似,只是省去了持久化操作).

步骤3.将原始叶子节点中一半的条目复制到新的节点中并执行写合并持久化操作.由于持久化操作缓存行刷新的粒度是一个缓存行(64B).同时,持久化写入性能不会受到同一缓存行中条目数量多少的影响[19].因此,在RRtree中通过执行写合并操作进行优化,即把所有的数据放在一个缓存行中,执行一次持久化操作,从而减少操作的次数且该持久化的开销由处于统一缓存行上的多个条目共同分摊.

步骤4.更新新节点上的元数据信息.在新节点上翻转与这些条目对应的Bitmap.设置当前节点的指针指向元叶子节点所指向的节点并增加G,然后进行持久化操作;同时,Count更新且不需要持久化.

步骤5.获取父节点的Lock,更新其父节点上的覆盖矩形MBR,并在父节点上插入新节点的覆盖矩形MBR;

步骤6.更新原叶子节点上的元数据.清除Bitmap中被删除的条目对应的bit位,更新当前节点的指针指向新叶子结点及G,并执行持久化操作.最后,更新count,释放节点原叶子结点的锁.

步骤7.释放父节点的Lock.

至此,分裂操作结束.如果系统在步骤3之后步骤6之前发生崩溃,此时数据结构的正确性不会受到影响.由于原叶子节点的Bitmap未被修改且其相邻叶子结点的指针也未被修改,已发生的操作是不可见的.但是,已分配PM的新叶子节点中插入的数据仍然被保存并未丢失.因此,在重启时,这些已分配的新叶子节点,但实际未被插入到RRtree中,可能会带来更多的搜索开销.这时系统会检查所有的叶子条目,如果叶子结点的G等于初始值或者其值加1,说明叶子节点正在进行分裂.因此,启动一个后台线程,搜索当前节点上的条目是否存在于其它节点上,如果存在则删除该条目.否则当前节点为空,这意味着它是一个刚被分配且尚未插入的节点,那么该节点将被回收,以防止持续的内存泄漏.

算法2.分裂算法

输入:分裂节点Cnode的父节点Pnode,插入条目对象E

输出:成功/失败

1.ifisLock(Pnode)then//判断父节点Pnode是否被锁

2. 重试

3.else

4. GetLock(Pnode) //获取父节点的锁

5.ifisLeaf(Cnode)then//分裂节点是否是叶节点

6. NewNode = PM_allocate() //从PM分配内存

7. IsLeafFlag = true

8.else

9. NewNode = DRAM_allocate() //从DRAM分配

10.endif

11.ifGetLock(Lnode)then//获取Cnode的锁

12. 从Cnode中复制一半条目到NewNode

13.ifIsLeafFlag== truethen

14. Persist_Coalescing(移动条目) //写合并持久化

15.endif

16. Update(NewNode.metadata) //更新有关元数据

17.ifIsLeafFlag== truethen

18. NewNode.Nextpos = Cnode.Nextpos

19. Persist (NewNode.metadata) //写合并持久化

20. Cnode.Nextpos = NewNode

21.endif

22. Release(Lnode) &Release(Pnode)

23.endif

24.Return成功

25.endif

4.2.2 汇聚

汇聚操作一般由删除操作触发.当服务端执行删除操作后,叶子节点的条目数少于m,此时执行RRtree汇聚操作.以使RRtree每个节点的条目数不低于下限m,保证树节点的平衡和利用率.然而,随着当前大量的写密集型工作负载进入数据中心,压缩的空间可能很快就会面临重新分配的操作,从而产生较高的开销.而基于PM与DRAM相比性能较慢,本文因此考虑忽略汇聚操作.由于被删除的位置很快就会被新插入的条目覆盖,因此RRtree不立即执行汇聚,以减少SMO造成的开销.然而,在重启过程中,RRtree会扫描所有的叶子节点,如果节点中的条目数量少于预设的阈值m,此时执行汇聚操作,以达到更好的搜索效率,提高内存利用率.

5 实验设计与分析

5.1 实验环境与数据

本文基于FBR-tree实现了RRtree,并在2台服务器上进行实验验证.每台服务器配备了两个Intel(R) Xeon(R) Gold 6242 CPU @2.80GHz CPU(共64个核心)、6个傲腾持久性内存(每个DIMM 128GB,共768GB),以及128GB DRAM,操作系统为Ubuntu18.04.6.Optane DIMMs被配置为App Direct模式,由ext4-DAX文件系统管理.服务器中的RNIC为ConnectX-5 MCX516A-CDAT 100 Gbps RoCE NIC,并通过 PCIe 3.0x16 连接到 Mellanox SN2100 交换机进行通信.由于现有的拥塞控制算法[20,21]能够较好的解决多主机间的网络通信高扇入incast问题,该问题超出本文的研究范围,且其不会对本文中提出的RRtree的优化策略产生的性能提升造成影响,因此在本文中使用两台服务器进行实验.

在本文中,本文将RRtree与当前唯一基于持久性内存的空间数据结构FBR-tree进行比较.但由于FBR-tree本身不具备网络传输模块,因此对其进行了RDMA网络配置改进.同时,为了公平起见,由于FBR-tree完全存储在持久性内存中,在实验中将其转化为基于PM-DRAM混合架构的HFBR-tree以验证RRtree基于持久性内存的性能优化效果.

本文使用真实数据集和合成数据集进行实验测试.其中,真实数据使用的是空间数据库中一直用作标准基准数据的TigerLine数据集[22],其中包含美国1700多万个矩形的地理特征,并使用其线段的边界框作为输入矩形.合成数据集由服从均匀分布、正态分布以及偏度不同(2,4,6,8)的倾斜的数据集组成.其中倾斜数据集由服从均匀分布的二维数据转换而来,通过将y坐标转换为yα,即每个点(x,y)被替换为(x,yα),α为倾斜度[23].为了保证实验结果的有效性,在每次测试前都用1千万个条目进行预热操作.

5.2 实验结果对比分析

5.2.1 单线程性能对比

图4和图5分别对单线程下RRtree的性能进行了测试分析.分别测量了在单线程下,不同索引大小下即RRtree包含条目数从200～3200百万条时的插入和搜索真实数据集的平均时延.

图4 单线程插入性能对比Fig.4 Insertion performance comparison under single thread

图5 单线程搜索性能对比Fig.5 Search performance comparison under single thread

图4展示的RRtree的平均插入一条条目对象的时延约为32μs,和FBR树相比缩短了30%,和HFBR-tree相比缩短了20%.图5中可以看出RRtree的搜索时延为48μs,相比FBR-tree性能提升了15%.RRtree和HFBR-tree相比性能提升略微不明显,是因为网络开销占比大,掩盖了在服务端上的性能提升.其中随着数据量的增加,3种方法的平均插入和搜索时延逐渐增加,但FBR-tree最为突出.这是由于树的高度会随着数据量的增加而上升,从而导致完全持久化的FBR-tree的插入和搜索时延明显增大.

RRtree的性能表现优于FBR-tree和HFBR-tree.这主要得益于以下两方面原因:1)RRtree采取持久性内存和DRAM混合部署架构,由于内部节点存放在DRAM中,因此移除了内部节点的持久化开销.此外,RRtree采取了基于持久性内存特性的优化策略,如写合并,缓存行刷新对齐,选择性持久化元数据等进一步减少了持久化次数,从而减少了持久性开销具有更低的时延;2)RRtree针对RDMA和PM共同使用情况下进行了配置上的优化.

5.2.2 多线程对比

为了测试RRtree在多线程下的性能和可拓展性,如图6所示,本文分别对比了RRtree、FBR-tree以及HFBR-tree三者在不同线程数下的插入真实数据集时的时延和吞吐.据图6(a)显示,RRtree在16线程数下的时延约为35μs,且图6(b)显示RRtree在线程数为32情况下可以实现15Mops/秒的吞吐,这分别是HFBR-tree和FBR-tree性能的1.2倍和2.5倍.

图6 多线程下插入性能对比Fig.6 Insertion performance comparison under multi-thread

图6(a)中显示三者的插入时延都随着线程的增加而增加.因为随着线程数的增加,对同一资源的访问可能不可避免地会因为争夺而被阻塞,进而导致性能下降.而完全持久化的FBR-tree性能下降最显著.因为FBR-tree插入基于粗粒度的共享内存的锁,而由于CPU的缓存一致性机制,在每次并发读写时都会修改共享内存,导致大量的缓存缺失.此外,由于FBR-tree完全存储在持久性内存上,当多个线程同时运行时,会造成内存控制器和持久性内存芯片内硬件资源的竞争.由于持久化内存的访问时延比DRAM长,从而延长了临界区的访问时延,进一步加剧了线程之间的冲突.RRtree因将锁放置在DRAM中,且通过基于版本号来控制细粒度的访问,因而具有更好的可拓展性.此外,RRtree通过控制避免对同一DIMM地址并发访问以避免持久化访问性能下降.因此基于以上,RRtree在线程逐渐增多的时候仍然表现出较低的时延和较高的吞吐.

由于真实环境中的数据总是呈现偏斜分布的,因此为了进一步验证RRtree的性能,本文对比了其在满足不同分布情况数据集的性能.从表2中可以看出,倾斜的数据相比服从均匀分布数据显示出更好的性能,且该现象在访问偏度越高的数据时,这一现象越明显.原因是访问倾斜数据受益于CPUcache的命中.但当偏度为6时,其吞吐量达到峰值,然后随着偏度的增加而基本保持稳定,和偏度为2时相比时延减少了约10%,而吞吐量增加了约20%.

表2 不同分布数据集下性能对比Table 2 Performance comparison under different distributed datasets

6 总 结

本文提出了RRtree,一种基于混合部署架构的远程持久性R树.它通过结合PM和RDMA技术为解决空间数据存储容量和处理效率问题提供了可行的方案并进行了实践,实现了更高的远程持久性R树的效率.实验结果表明,在实际可商用的英特尔傲腾持久性内存上,RRtree的性能比当前已有的方案在时延和吞吐上有显著的提升.