泛读笔记：《DEX: Scalable Range Indexing on Disaggregated Memory》

文章发布时间:

最后更新时间:

文章总字数:
2.4k

预计阅读时间:
8 分钟

页面浏览: 加载中...

Paper

1. 摘要

内存分离有可能让内存优化的范围索引（如B+树）在超出单一机器的范围内扩展，同时实现高硬件利用率和低成本。然而，在内存分离架构上设计可扩展的索引是具有挑战性的，主要是因为基础缓存、不规范的卸载以及服务器之间的一致性过度问题。

本文提出了DEX，一种新的用于内存分离的可扩展B+树。DEX包括一组减少远程访问的技术：逻辑分区、轻量级缓存和成本感知卸载。我们的评估显示，DEX可以比现有技术提高到1.7到56.3倍的性能，并且在不同的设置下，如缓存大小和数据倾斜，依然存在优势。

2. 背景

  • 单机内存数据库：
    • 内存容量有限
    • 只有负载接近满载时高成本才能得到回报
  • 内存分离架构：
    • 将内存和计算分开到各自的服务器池中，并通过快速网络将二者互联
    • 灵活地独立扩展计算线程和内存大小，实现高利用率和低成本
  • 缓存和计算下推：
    • 远程内存访问延迟较高，简单实现从根节点到叶子节点每层都需要一次RDMA操作
    • 计算服务器有少量本地内存 => 计算服务器缓存
    • 内存服务器有少量计算资源 => 简单计算可以下推(卸载)到内存服务器

3. 面临挑战

  1. 缓存问题
    1. 软件开销更加明显：
      • 传统的许多研究集中在如何提高缓存命中率上，本地和远程内存的访问延迟差距(10倍)比存储器之间的差距小(SSD1000倍)，因此与缓存维护和同步相关的软件开销变得更加明显
    2. 计算服务器不应假设一定数量的本地内存：
      • 如果本地内存严重受限，非树形索引的通用缓存机制可能表现不佳
  2. 卸载策略
    1. 卸载利用了内存服务器上有限的计算资源，以减少RDMA通信
    2. 应当避免在内存服务器上占用有限的计算资源，决策（什么、何时以及多少进行卸载）对于避免过载并保证可扩展的性能至关重要
  3. 一致性问题
    1. 内存分离带来了处理不同来源的数据不一致的挑战，但现有的基于RDMA的分布式同步锁定成本高昂
    2. 如果在计算服务器上实现缓存，则必须确保所有计算端缓存之间的一致性，这种复杂性随着计算服务器数量的增加而增长
    3. 如果考虑到计算端缓存和内存端卸载，一致性问题将更加严重
alt text

4. 本文方法

  1. 计算端采用逻辑分区
    1. 每个计算服务器逻辑上“拥有”一组键范围，而内存服务器仍然提供全局可寻址的共享空间
    2. 减少了计算服务器之间的缓存一致性成本以及RDMA远程内存访问同步开销
    3. 易于负载均衡和增删计算服务器：逻辑分区只需调整路由，而不需要物理重新划分数据
  2. 轻量级路径感知缓存
    1. 提出了一种基于随机采样的轻量级缓存替换策略，减少了竞争并实现了高可扩展性
    2. 为了减少缓存未命中的情况，利用应用层信息进行路径感知缓存，将频繁访问的索引路径保留在缓存中。
    3. 子B+树节点只能在其父节点被缓存后才能被加入计算端缓存中，父节点在其所有子节点被逐出之前不会被逐出。这不仅提高了缓存效率（因为靠近根节点的节点更热），还使得计算和内存服务器之间的卸载更加有效，降低了一致性开销。
  3. 成本感知卸载
    1. 在运行时跟踪内存服务器的资源可用性
    2. 仅在卸载成本更低时才进行卸载

5. 计算服务器的逻辑分区

  • 每个计算服务器都拥有一个逻辑分区
  • 可以使用各种范围分区方案
    • 例如等宽或工作负载感知
  • 要求每个叶节点仅由一个分区（即一个计算服务器）拥有
    • 分区的边界使用最底层内部节点中的键
    • 跨服务器同步和缓存一致性的需求限制在仅内部节点上（内部节点更新频率低）
  • 重新分区非常快

算法：

  • 如果某节点缓存未命中
    • 要么将剩余索引操作卸载到内存服务器
    • 要么将节点从内存服务器读取到计算服务器（共享节点使用乐观锁）
  • 内部节点过时使其搜索到错误的子节点时，才从远程内存中引入内部节点的新副本
    • 如果在过时的内部节点能找到正确的叶子节点，就没有必要从远程内存引入

6. 计算端缓存

  • 使用一张hash表(mapping table)和多个FIFO队列，节点根据指针hash值放入不同FIFO队列中
  • 热节点的父亲指向该节点使用本地指针，冷节点父亲指向该节点使用全局指针，通过最高位区分
  • 当有FIFO队列满的时候，随机挑选队列中一组（本文实现是两个）节点，将其脏数据刷回内存池，将其变为冷节点，它会成为被驱逐的候选者，如果冷节点被再次访问到，就把它变成热节点
  • 路径感知：如果中间节点需要变冷，且它有孩子是热节点，那么冷却命令会传递给它的一个热孩子，它本身还是热节点
  • “I/O” flag(乐观锁)：对于正在remote read的节点，会先在mapping table插入一个“I/O” flag来避免重复的RDMA读取，其他线程遇到该标志会从头重新开始
  • 延迟接纳（可选特性）：节点在远程读之后有一定概率留在cache中，文中设置内部节点概率为1，叶子节点留存概率为0.1
  • 实验对比：FIFO在并行度高时争用大，扩展性不佳，Cooling Map扩展性好

7. 成本感知卸载

  • 因为路径感知的缓存策略，当一个节点未命中时，其子节点也可能会未命中，所以卸载是有利的
  • 如果1)节点不专属于该分区 或者 2)节点高度L>M，则不会卸载
    • 确保卸载仅限于一个计算服务器和一个内存服务器
  • 当卸载报告会在内存服务器上触发结构修改操作（SMO）时，将退回到正常处理路径
    • 因为SMO（例如叶子节点分裂）可以向上传播到第𝑀 + 1层或更高层的节点
  • 根据最近的样本估算代价
  • 正确卸载需满足两个条件（卸载的一致性问题）：
    • 问题简化：
      • 卸载仅发生在一对计算服务器和内存服务器之间
      • 如果推送线程操作某子树，那么子树所有节点要么已经被驱逐，要么处于冷却状态
    • 在卸载进行时，没有其他计算线程正在操作子树在缓存中的节点或使用RDMA检索子树中缺失的任何节点
      • 在卸载操作开始之前，会将子树根的父节点固定在热状态，以防止其被驱逐
      • 在卸载操作开始之前，会将映射表中子树根节点值设置“I/O”flag，以防止其被其他节点检索或操作
    • 在卸载过程中对节点的任何更新都必须传递回计算节点，以使相应的缓存副本失效
      • 内存侧的卸载线程在成功时返回更新节点的全局地址（或在遇到任何SMO时返回失败状态）
      • 卸载请求返回后，计算侧工作线程会检查映射表，确定是否有更新节点的缓存副本，如果有，则通过从映射表中删除其引用来使其失效
      • 最后取消子树根的父节点固定，并从映射表移除子树根节点

8. 索引操作：插入

  • 插入操作可能会导致节点分裂
  • 对于独属于该分区的节点，使用一种积极的分裂策略，即在自顶向下遍历过程中遇到的任何满的节点都会立即分裂
  • 当一个节点𝑁在当前分区中已满，而它的父节点𝑃是共享的：
    1. 获取𝑃的全局锁，并从内存池中检索其最新版本
    2. 如果满足两个条件：1）缓存的𝑃是最新的，且2）𝑃不是满的，则进行当前节点的分裂并完成
    3. 如果不满足条件：
    4. 放弃正在进行的节点分裂，并从远程根节点触发缓存刷新
    5. 对于路径中的共享节点，如果它们是满的，则立即进行节点分裂
    6. 最后重试插入操作
≡