Paper

1. 摘要

新兴的基于NUMA/CXL的分层内存系统具有异构内存设备（如DRAM和NVMM），可同时提供超快速度、大容量和数据持久性，为高性能内存键值存储提供了巨大的希望。为了充分释放此类内存系统的性能潜力，本文介绍了BonsaiKV，这是一种键值存储，可以充分利用分层内存系统中的不同组件。BonsaiKV的核心是一个三层分层存储架构，它将数据索引，持久性和可扩展性相互分离，并在专门的软件-硬件层中实现它们。我们设计BonsaiKV与一组新的技术，包括协作分层索引，NVMM拥塞控制机制，细粒度的数据条带化，和NUMA感知的数据管理，利用硬件的优势和解决设备的缺陷。我们使用各种YCSB工作负载将BonsaiKV与最先进的NVMM优化的键值存储和持久化索引结构进行比较。评估结果表明，BonsaiKV在读、写和扫描密集型场景中的性能分别高达7.69×、19.59×和12.86×。

2. 面临挑战

1. DRAM快，但容量小，价格贵
2. NVM带宽小，多线程下容易饱和，导致流量拥塞
3. 分层DRAM-NVM存储器系统包含由通道隔离存储器模块组成的多个存储器节点，如何通过利用硬件提供的并行性和减轻远程存储器访问开销来扩展键值存储

3. 本文贡献

1. 开发了一个分析模型来理解NVMM拥塞，然后提出了两种拥塞控制机制来减少流量干扰和缓解带宽争用
2. 设计了一个可扩展的细粒度数据放置方案，充分利用内存通道级并行
3. 提出了一种自适应KV数据复制机制和一种写最优数据一致性协议，以减轻远程内存访问开销

4. 背景

1. NVM可以插在内存插槽中
2. CPU之间的连接构成了numa
3. 在CXL内存扩展中，设备被视为没有CPU内核的常规NUMA节点

5. 和现有系统的比较

6. Overview

• 对于所有请求(get/put/del/scan)，它们首先被发送到索引层(1)。
• 它首先在DRAM层(2)中找到相关联的索引条目。
• 然后，在NVMM层(3)中执行剩余的键值数据索引。它搜索存储在log或dnode中的目标数据。
• 对于put/del，他们在(4)中的日志层中创建新日志。删除请求在日志中有一个标记。
• 日志检查点线程将日志刷新到(5)中的数据层。
• 在键值数据从日志移动到dnode之后，修改DRAM层里的索引层(6)。
• 最后，存储在dnode中的键值的放置方案提供了上级访问并行性，支持快速扫描(7)。

1. 结合DRAM的高速和NVMM的大容量，以实现快速和内存高效的索引
2. 调整数据持久化粒度以解决NVMM拥塞
3. 充分利用通道级并行读数据
4. 通过本地化数据访问扩展到NUMA结构

7. 索引层设计

• inode都存放在DRAM中
• Shim层(在内存中)中存放了最下面一层的inode，这层的inode结构与上层的不同
• Shim inode中，bitmap用于标识哪些log是有效的，log IDs可以存放16个logId，lfence和rfence表示节点的左右边界
• 当16个日志写满时，该Shim inode会分裂，但仍然指向同一个dnode
• 在checkpoint时日志会应用到dnode中。当Shim inode的日志空了，除了对应dnode左边界的inode，其他的inode都可以删除
• 点查时先从日志里找，找不到再从dnode里找。
• Shim inode中的fingerprints里存放了各条日志的key的hash(1B)，点查时只有fingerprint匹配了才需要去日志读取键值对

8. NVMM拥塞分析模型

• 理论分析：
  • $G$是持久化粒度
  • CPU只允许最多$k$个待处理的内存请求在行填充缓冲区中
  • $C$是cacheline大小
  • 没有持久化粒度的情况下数据传输速率是$v$
  • 那么带有持久化粒度的情况下，传输速率为$\frac{min(G, C\cdot k)}{C\cdot k}\cdot v$
  • 在线程数为$N$的情况下，传输速率为$\frac{min(G, C\cdot k)}{C\cdot k}\cdot v \cdot N$，在该速率超过NVM处理速度，就会引发拥塞和颠簸
• 持久粒度越大，传输速率越快。像LFB、WPQ和NVMM缓冲器这样的硬件单元很可能填充有其数据。它的内存请求首先被服务，并且线程表现出更高的优先级。
• 下图实验中，一个线程固定持久化粒度为256B，另一个改变持久化粒度

9. 日志层设计

• 减少NVMM流量干扰：
  • 有两个持久化数据流：
    1. 由put/del引起的前台日志持久化
    2. 后台日志刷新到数据层
  • 为每个工作线程设计了一个私有的2KB的易失性日志组合缓冲区，日志会被打包一起持久化
  • 后台线程会以较小的粒度持久化，这样能降低优先级，减少对前台的干扰
• 缓解NVMM带宽争用（值较大的情况）：
  • 较大的值如果要持久化可能导致严重的带宽争用，需要适当降低数据传输速度
  • 一种方法是将值分成小的定长的阶段，分阶段持久化(使用sfence保证一次只持久化一阶段)，即通过减小持久化粒度来降低数据传输速率
  • 另一种方法是减小并行度，由于不可忽略的通信开销，这种方法对于键值存储来说是沉重的。

一条日志包含：

• 4B日志大小
• 8B值或者6B值offset和2B值大小，值会额外储存
• 8B时间戳
• 1B日志类型
• 变长的键

10. 数据层设计

• 将一个dnode划分为多个固定大小的块（文中是256 B），包括一个Meta块和几个数据块
• 块的总数与每个CPU的内存通道数（本文中为6个，即一个numa节点有6条pmem）一致，存放在各个内存结点上，顺序不一样
• Meta块包含一个40元素的指纹数组、一个位图和其他元数据
• 数据块中有8个条目，一个条目包含：
  • 一个24B的键，或一个内联的16B键和一个指向剩余键数据的8B指针
  • 一个8B的值，或一个6B的逻辑值偏移量和一个2B的值大小
  • 一个在数据一致性协议中使用的易失性2B epoch
• order数组记录dnode条目顺序
• 每个NVMM设备都有一个内存池，该内存池被划分为多个256字节的块，以存储Meta或数据块
• 一个dnode的多个块在每个设备的内存池中以相同的偏移量驻留
• 对于较大的值，也会被分割成多个小块，以roundrobin方式分布在N个NVMM上

• dnode 的 id (32位) 中有3位存放numa节点号，剩下29位存放在节点中的索引
• 首先，根据最高三位找到dnode在哪个numa节点
• 然后，之后29位的hash值确定dnode中各个块的排列方式(排列方式数量不多，总共就$6!=720$种，预先算好)
• 找到Meta块之后将其复制到内存中
• 对于点查
  • 先对fingerprints做过滤，如果有多个fingerprint匹配上了，可以并行读取再过滤
• 对于扫描，使用prefetch优化
  • 第一阶段，每次将各个数据块第k个64B数据prefetch进缓存
  • 第二阶段，根据order array中的顺序读取数据
• 数据层会检测热数据，将热数据所在的dnode缓存到内存中

数据一致性：

• 有一个全局时钟$t$，副本创建时获取创建时间戳$t_r$，如果读取时$t − t_r > \Delta t$则表明副本失效，需要重新获取，$\Delta t$是有效时间段阈值
• 当写入新日志时，由于会优先在日志中查找，旧版本的副本即使未到失效时间也是不可见的
• 检查点清空日志可能导致检查点前创建的旧版本副本仍然可见，使检查点和清空日志的间隔增大到大于$\Delta t$可以解决

11. 实验环境

• 2颗Xeon Gold 5220R(24核,2.20GHZ,关闭超线程)
• 1.5T(12*128GB)NVM
• 192GB(12×16GB)DDR4 DRAM

• 100% get, 每个线程插入1.5亿个16字节的记录。
• BonsaiKV+DRAM-only: 全放内存
• BonsaiKV+data offload: 把数据层和部分索引层放到NVM中
• BonsaiKV+data offload+meta upload: 将查找相关的元数据上传到DRAM上

• 图a：
  • 当打包大小变大时，吞吐量增加并逐渐接近没有检查点时的吞吐量。较大的打包大小减少了日志检查点的干扰，并提高了日志持久化优先级
  • 当打包大小变大时(持久化粒度增大)，吞吐量也增大
• 图b: 值大小为16KB
  • 对于大值，使用较小的粒度分段持久化能够有效地降低了传输速率，并防止了设备缓冲区竞争
  • OdinFS使用机会委托(OD)来限制并行线程数量，该技术遭受严重的通信开销的环形缓冲区缓存颠簸，适合文件系统而非键值储存

扩展性实验(使用YCSB-E)，能够有效利用带宽

key长度变化实验: key长度没有太多影响

内存和NVM占用