VLDB2020DPTree:DifferentialIndexingforPersistentMemory

一、前言

由于新硬件的出现，传统的应用迁移到新架构上需要做一些相应的设计调整，才能发挥新硬件的性能。持久性内存（PM）作为内存型介质，其高密度、可字节寻址以及低延迟等优良特性，有望取代DRAM，是近年来研究的热点，包括OSDI，SOSP,ISCA，SIGMOD,VLDB等顶会上，有相当比例的文章与它相关。随着Intel AEP的量产，针对其的优化的文章也越来越多。本文是来自浙江大学和阿里巴巴的工作，今天找论文时看到，简单记录下。

二、目前存在的问题：

• PM具有较高的写延迟。

• 掉电非易失以及原子写粒度的问题，导致数据部分写。而且CPU乱序写会导致cacheline刷新顺序不同，因此不能识别出数据属于那个cacheline。

• mfence和cflush能保证cacheline的刷新顺序，但是这种同步方式带来的极大的写开销，而写问题是PM的瓶颈所在。

• 传统的索引机制主要是针对磁盘和DRAM的架构设计的，没有考虑到PM的特性。

相关工作：

目前存在大量的解决方案，比如CDDS-Tree， wB+-Tree ， NVTree , FPTree 和 FASTFAIR 等，然而这些索引机制都引起大量mfence和cflush维护数据一致性，带来了很大的性问题。

解决方案：

为了减少昂贵的写开销，本文提出了一种针对PM的索引结构，DPTree，如图1所示。DPTree是一个两层的索引结构：第一层是buffer tree，保存在DRAM中(写优化）；第二层是Base Tree，保存在PM中，它是只读的(读优化）。（类似于LSM架构）

写流程：

1. 写请求首先写到DRAM中的buffer Tree中，减轻对PM的写压力。

2. 当buffer Tree中的数据量超过给定阈值时（阈值是buffer cache/base tree），将buffer Tree中数据merge到Base Tree中，然后持久化到PM中。由于进行了merge操作（批量更新），因此只需要少量的mfence操作。

DPTree的详细设计

1. Buffer Tree

本文采用了链表的结构存储日志，如图2所示，每个page被分割成8byte大小，其中63bit存储数据，1bit是有效位标志符。

日志链表的头部是PLog，PLog由fist，curp和poff三个指针组成，其中first表示指向第一个page,curp表示指向目前活动的page，poff指向目前活动的page的offset。Cacheling Log Page Allocator是分配器，包含两个freelist，其中一个有效位是0，另外一个freelist的有效位是1.当buffer tree初始化时，会根据bool值选择freelist。并且当freelist的大小超过请求大小时，对其进行内存分配，等使用完后不会直接释放，转换成其他的freelist，供之后的请求使用，类似内存池。另外， Csize（alloctor的可用容量）能够动态的调整。

2. Base Tree

在DPTree中，base tree中的数据是只读的，并且通过merge操作更新（类似与LSM Tree中的sstable）。在base tree中，inner node保存在DRAM中，leaf node保存在PM中，并采用了部分写日志的机制。

如图2所示，meta由bitmap。next，maxkey等组成，其中bitmap表示对应的key/value slot是否有效，这里面用2位来表示（由于这里delete操作时追加tomstone的机制，所以entry有三种状态），next指向下一个叶子节点，max_key表示该节点中的最大值，order存储按序排列的key/value的offset，fingerprint存储key的hash值（这部分设计基本是借鉴了NV-Tree，wB-Tree，FP-Tree的设计方案）。另外，DPTree采用了部分持久化的机制，不同于NV-Tree等，这里count, order和 fingerprints不需要持久化。作者认为系统crash是稀有发生的事情，即使crash了，也可以通过数据重建恢复。

最后

只是粗略的看了下总体设计，本文还有很多设计上的实现细节，等有空再看下。

[1] Xinjing Zhou et al. DPTree: Differential Indexing for Persistent Memory.VLDB