Paper

1. 摘要

在过去十年中，内存数据库系统在学术界和工业界变得十分流行。然而，大型数据集通常需要分布存储在集群中多个节点的内存中，因为它们通常无法装入单台机器的内存中。最近提出的一种用于为快速 RDMA 网络构建分布式内存数据库的数据库架构是网络附加内存 (NAM) 架构。NAM 架构在逻辑上将计算和内存服务器分开，从而为这两种资源提供独立的可扩展性。NAM 架构中的一个重要挑战是为计算节点提供有效的远程访问方法，以访问驻留在内存节点中的数据。

因此，在本文中，我们讨论了 NAM 架构中分布式树型索引结构的设计方案。本文主要关注两个方面：（1）索引本身应如何分布在多个内存服务器上；（2）计算服务器应使用哪些 RDMA 原语以最有效的方式访问分布式索引结构。我们的实验评估显示了使用各种工作负载的不同分布式索引设计方案的权衡。虽然本文的重点是 NAM 架构，但我们相信研究结果也有助于理解如何为其他基于 RDMA 的分布式数据库架构构建分布式树型索引的设计空间。

2. NAM的特点

• 优势
  1. 适合不同的工作负载
     • CPU和内存解耦
     • 对数据库不易分区的工作负载支持较好
  2. 扩展性较好
     • 可以线性扩展至50个节点
     • 传统无共享架构只能扩展到几个
• 面临的挑战：
  1. 如何充分利用RDMA
     • 尤其是对于较小的数据传输
  2. 维持系统的可扩展性
     • 以往的研究都假设二级索引是非分布式的，限制了扩展性
  3. 如何选择RDMA的访问模式
     • 单边操作更具可扩展性，开销少，但使用更复杂

3. 本文贡献

1. 讨论了可通过 RDMA 高效访问的 NAM 架构的分布式树形索引结构的设计选项
2. 提出了三种不同的可能的索引实现，它们在数据分布方案以及用于访问和更新索引的底层 RDMA 原语方面有所不同
3. 使用各种工作负载分析了所提出的索引设计的性能，这些工作负载包括具有各种访问模式和选择性的只读工作负载，以及具有不同写入强度的混合工作负载

4. 基于RDMA的索引的设计选项

分配方案

1. 索引分布
   1. 粗粒度分布（CG）：
      1. 对索引分区
      2. 每个机器上储存一部分键
      3. 当网络带宽是主要限制因素时，粗粒度方案是分发索引（和数据）的主要解决方案
      4. 使用RPC协议，使用可靠双边RDMA
   2. 细粒度分布（FG）：
      1. 不对索引进行分区
      2. 每个树节点的第$i$个儿子储存在第$i\%N$个机器上
      3. 对于RDMA网络而言，细粒度方案可以实现更好的负载均衡，特别是本地和远程内存带宽受限时
      4. 倾斜负载下扩展性理论上更优（如下图）
      5. 使用单边RDMA原语
   3. 混合方案：对上层CG，叶节点使用FG

alt text

5. 实验

YCSB