Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory

abstract

buffer manager设计的关键假设就是数据必须从non-volatile storage迁移到DRAM, 才能对数据进行操作，而且storage速度比DRAM慢几个数量级。但是新的非易失性存储器(NVM)技术的到来,使这些先前的假设无效。

Hymem是最近提出的buffer manager，用于由DRAM、NVM和SSD组成的三层存储层次。Hymem支持cache-line-grained loading和NVM-aware数据迁移策略。虽然这些优化提高了它的吞吐量，Hymem却受到了两个限制。首先，它是一个单线程的缓冲区管理器。其次，在NVM仿真平台上进行的仿真。

本文提出了spilfile, multi-threaded three-tier buffer manager，在Optane PMMs上测试。我们介绍一个在多层存储层次结构中进行数据迁移的策略。数据迁移策略必须根据设备和工作负载的特征进行调整。鉴于此，我们提出了一种机器学习技术，用于为任意工作负载和存储层次自动调整策略。

introduction and background

Hymem

1. 新分配的16 KB页面驻留在SSD上。当一个事务请求该页面时，Hymem急切地将整个页面移动到DRAM。
2. DRAM需要回收空间时,使用clock算法选择victim page evict.
3. 选择好victim page后需要考虑是否将page放到nvm(如果page不在nvm的话).当page被考虑进入NVM，Hymem检查该页面是否在admission queue。如果是，则将其从队列中删除并放到nvm。否则，它将被添加到队列中，并直接移动到SSD，从而绕过NVM。
4. NVM需要回收空间时,同样使用clock算法选择page evict.

Hymem使用cache line grained从一个冷的16 KB页面中提取热数据。通过只加载那些需要的cache line，Hymem降低了它的带宽消耗。

当一个事务请求一个页面时，Hymem检查该页面是否在DRAM缓冲区中。如果它不在DRAM缓冲区中，它会检查该页面是否在NVM缓冲区中。如果在NVM中,它直接移动驻留在NVM上的页面到DRAM。如果不在NVM中，它将驻留在SSD上的整个页面放入DRAM缓冲区,此时不利用从SSD到NVM的路径.

Hymem维护了两个bitmasks(标记为resident和dirty)来跟踪loaded和dirty的cacheline, cacheline大小为64B,一个nvm page大小为16KB,所以一个page包含256个cacheline.

mini page 的大小为16个 cache line,如果超过16个cache line 会加载整个nvm page到DRAM.

spitfire

由于CPU能够直接操作在NVM中的数据，所以spitfire不会积极的将数据从NVM移动到DRAM,lazy数据迁移策略保证只有热数据会被移动到DRAM.

考虑到必须根据设备的特性和负载来调整迁移策略,本文采用ML的方法来为任意负载和存储层次自动调整策略。这种自适应数据迁移方案无需手动调优策略。

conribution

• data migration in a multi-tier storage hierarchy
• an adaptation mechanism that converges to a near-optimal policy for an arbitrary workload and storage hierarchy without requiring any manual tuning
• multi-threaded, three-tier buffer manager
• evaluate Spitfire on Optane DC PMMs
• a set of guidelines for choosing the storage hierarchy and migration policy based on workload
• an NVM-SSD hierarchy works well on write-intensive workloads

optane dc pmms

这里不太懂为啥没用pmdk.

fd = open(("/mnt/pmem0/file", O_RDWR, 0);
res = ftruncate(fd, SIZE);
ptr = mmap(nullptr, SIZE, PROT_WRITE, MAP_SHARED, fd, 0);

spiltfile data migration

bypass dram during reads

$D_r$ 是从NVM到DRAM移动数据的可能性.当$D_r=0.01$意味着100次的read才会有一次将data 移动到DRAM,这种惰性策略保证温数据保存在NVM中不会移动到DRAM.

bypass dram during writes

$D_w$是写数据时使用DRAM的可能性.在DRAM-SSD的层次结构下,$D_w=1$.当$D_w$较小时,避免了频繁的从DRAM向下移动数据,而直接将数据在nvm中持久化.这样也可以避免DRAM中的热数据移出DRAM.

bypass nvm during reads

当请求的page不在DRAM和NVM中，将SSD上的数据直接复制到DRAM，从而在读操作期间绕过NVM。如果读入DRAM缓冲区的数据随后没有被修改，并且被选择替换，那么只是简单地丢弃page。如果页面被修改，然后选择从DRAM中删除，那么spitfire会考虑将其移动到NVM.

$N_r$表示读操作时，将数据从SSD复制到NVM的可能性。 当一个页面从SSD中取出，然后在DRAM中修改并移出时，一个eager策略需要对NVM进行两次写操作:一次是在取出时，一次是在从DRAM中移出时。使用惰性策略时(例如，$N_r = 0.01$)，spitfire会在修改后的页面被从DRAM中移出时才在NVM上保存这个page。这就消除了spitfire从SSD获取页面时对NVM的第一次写入操作的代价。

为了减少从SSD到NVM再到DRAM的数据迁移策略.可以采用从NVM到DRAM的惰性策略$(D_r=0.01)$,积极的从SSD到NVM的数据迁移策略$(N_r=0.2)$.

bypass nvm during writes

通过在写操作过程中绕过NVM，spitfire可以确保只有经常从DRAM交换出来的页面才会存储在NVM上。这种优化类似于Hymem中DRAM到NVM的队列机制。与Hymem不同，spitfire并不显式地维护这样一个队列，而是采用概率方法。除了减少对NVM的写入次数外，这种优化还确保只有温数据存储在NVM缓冲区中。

$N_w$表示写操作时将数据从DRAM拷贝到NVM的概率。使用默认的写路径$N_w = 1$。较小的$N_w$减小了数据向NVM的向下迁移。当DRAM的容量与NVM相当时，这种惰性策略是有益的，因为它确保从DRAM上移出的冷数据不会驱逐NVM上的温数据。

data migration policy

可以用元组表示数据移动策略:$<D_r,D_w,N_r,N_w>$,针对不同的负载,肯定会有不同的数据移动策略的参数设置.

假设page P产生了N次读,那么P被移动到DRAM的概率为$1-((1-D_r)^N)$.

adaptive data migration

通过 模拟退火 simulated annealing (SA)来寻找最优的data migration policy.

system architecture

buffer management

mapping table记录page buffer在哪里(NVM DRAM).

当请求一个页面时，Spitfire执行一个table lookup，返回一个包含位置的page descriptor(如果有的话).如果该页面在DRAM上找到，那么它将返回一个对DRAM frame的引用。否则，如果在NVM上找到了该页面，并且迁移策略允许Spitfire绕过DRAM，那么它将返回对NVM frame的引用。如果在NVM和DRAM中都没有找到，spitfire从SSD中检索页面，并根据多层数据迁移策略将其放置在DRAM或NVM中。

page descriptor包含了latches,使用page的计数,a bit 确定是不是脏页.指针指向page.

与Hymem类似，spitfire采用了clock缓存替换策略，回收DRAM和NVM中的空间。

concurrency control

为了支持并发操作，使用了以下数据结构或协议:

• 一个并发哈希表，用于管理从逻辑页标识符到共享页描述符的映射
• 用于缓存替换策略的并发bitmap
• multi-versioned timestamp-ordering (MVTO)并发控制协议
• 乐观锁的并发B+树
• 用于线程安全页面迁移的轻量级锁

spitfire为一个page descriptor维护了三个latch,当数据从NVM移动到SSD时,只需要锁NVM和SSD latch,这样还可以访问DRAM上的page.

当一个page在NVM和DRAM上都存在,访问时绕过DRAM,则DRAM中的page不包含NVM中的修改信息.为了防止这种问题,需要获取DRAM和NVM的latches,在将NVM上的page移动到DRAM之前释放掉其他对象对NVM上page的引用,最终释放获得的锁存。

recovery

NVM-aware write-ahead logging protocol

日志记录包括:(1)事务标识符和页面标识符，(2)记录类型，(3)该事务前一个日志记录的日志序号，(4)日志记录前后的数据镜像。

一旦事务的提交日志记录被持久化到NVM日志缓冲区中，事务就被认为已提交。当NVM日志缓冲区大小达到阈值时，它的内容将异步追加到磁盘上的日志文件。在后台，spitfire会定期刷脏页面。但是，由于NVM是持久的，NVM缓冲区中的修改页面不会被刷新到SSD。因此，NVM缓冲区中的页比SSD对应页新。

在恢复过程中，spitfire首先重构NVM缓冲区来识别页的最新版本。这是通过扫描NVM缓冲区来收集页id并构造映射表来完成的。其次，NVM日志缓冲区需要追加到日志文件中，(将NVM中的日志append到日志文件应该是为了使用传统的方案恢复数据库)因为该缓冲区是持久的。一旦恢复了映射表并完成了日志文件，喷火式战斗机将继续使用传统的恢复方案恢复数据库。