PolarDB-SCC：阿里低延迟强一致性读取的云数据库分析


阿里巴巴组的这篇论文讨论了如何在PolarDB数据库部署中从从节点执行低延迟强一致性读取。发表在VLDB'23 上。

PolarDB采用关系型数据库规范的主从架构。主节点是读写 (RW) 节点，辅助节点是只读 (RO) 节点。让 RO 节点有助于执行查询，并在查询性能方面进行扩展。

这本质上就是AWS Aurora 架构。持久性是通过共享存储来满足的，因此我们可以忽略这一点并正交地专注于提高 RO 节点性能的优化。

提高 RO 节点性能的方法是将重做日志（本质上是 WAL）传送到这些 RO 节点，以便它们可以保持缓冲区准备就绪，并快速从缓冲区读取数据，而不必访问共享存储。

PolarDB架构遵循同样的思路。最重要的是，他们对能够从 RO 节点提供强一致性读取服务感兴趣。论文称，这在阿里巴巴的电商应用中尤其需要，而且对于使用数据库支持微服务之间交互的场景也是如此。  

强一致性读取
强一致性也称为线性化。
如果我们简化事情，并将操作限制为仅写入和读取，则线性化可归结为：
“读取应返回最后写入的值”。

但最后写入的值是多少？
即使在操作请求和操作响应之间存在差距，也需要考虑一些有趣的行为。

事实上，可以利用客户端发送的读取请求和客户端观察到的读取响应之间存在的间隙。

  • 实现线性化读取的一种方法是通过延迟数据库端的读取操作较长时间的读取，并延迟返回响应。
  • 这样，如果在读取请求之前有一个更新已完成/确认，我们就可以很好地保证在我们正在进行读取的任何节点上，更新已被看到/传播并包含在内。
  • 其他后续更新也可以包含在延迟读取中，但就线性化定义而言，这是可以的。

当然，滥用这种延迟读取执行方法是不好的，并且会适得其反。客户想要快速响应，而不是慢读。

如何平衡：我们最快什么时候可以序列化/提供读取服务，同时保证读取的强一致性？

如何从从节点执行线性化读取？
将 Paxos 中的学习者角色（第一阶段仲裁读取操作）卸载给想要获得强一致性读取的客户端。为此，客户端联系辅助节点的第一阶段仲裁，并保留正忙于提供更新/突变的主节点。

分两个步骤执行线性化读取：屏障和冲洗。

  • 我们将屏障点确定为可能已被写入确认（并暴露于外部）的最后一个值。
  • 然后，我们延迟提供读取服务，直到在该辅助节点中达到障碍点，以保证我们不会提供过时的读取服务。

好消息是我们不需要经常清洗，特别是在读取键值类型数据时。对于我们感兴趣的读取键，通常没有待处理的更新，因此不需要等待来服务器读取。

这种方法仍然不是那么高效，因为我们正在联系第一阶段的辅助节点法定人数。我们可以从一个节点进行可序列化的读取吗？

可以通过与单个节点交谈来找出屏障点？
是的，我们可以。

一种选择是依靠客户端提供屏障点，并延迟辅助节点上的读取，直到辅助节点赶上该屏障点。

但这在许多系统中可能不是一个好的做法，因为这对客户端要求太多。客户端需要跟踪这个因果关系标记，并将其传递给读取而不需要搞乱。此外，从技术上讲，如果有多个客户端，这不会是强一致性读取。一个客户端不会获得有关其他客户端收到的 ack 的信息，因此这不是强一致性读取，而是更多的会话一致性读取。

好吧，在不将其转嫁给客户端的情况下，我们如何找出屏障点，即最近的“潜在”确认的更新操作？

  • 实现这一想法的一种方法是，如果您可以拥有一个前端服务来维护此信息（每个键的最后一个更新点），例如使用哈希表。然后，辅助节点可以查询此前端服务以了解要屏障的内容，并仅在辅助节点当前达到该屏障点时提供只读服务。这几乎就是POLARDB的想法。除此之外，他们将哈希表（他们称之为修改跟踪表 (MTT)）保留在主设备上，并让辅助设备通过单向 RDMA 读取该表以绕过主 CPU，以免给主设备带来负担。
  • 实现这个想法的另一种方法是使用同步物理时钟。考虑使用 TrueTime 的 Spanner。要执行线性化读取，客户端可以使用 TrueTime(now) 提交读取操作。

POLARDB架构
在PolarDB中，分层修改跟踪表 (MTT)维护在主节点以跟踪系统中的所有修改。辅助节点检查 MTT（它通过单向 RDMA 到达主节点），以查看相对于读取密钥的屏障点。这成为读取的序列化点。如果辅助节点已经赶上这一点，它将提供读取服务，否则将等待，直到它获得足够的电流来提供读取服务。

MTT 的分层只是一种优化。MTT从三个级别跟踪主节点最新修改点：全局数据库最新修改点、表最新修改点、页级最新修改点。

辅助节点将首先检查（通过单向 RDMA）全局级别的水印，然后检查请求的表和页面的水印。一旦满足了一级，就会直接处理请求，不会检查下一级。只需要在最后一级（页面级别）不满足的情况下等待日志申请即可。
一旦请求在全局级别得到满足，则无需在该事务的后续数据访问期间检查时间戳，因为整个数据库对于当前请求来说是最新的。
如果仅在一个请求的表/页面上满足请求，则在访问不同的表/页面时必须检查时间戳。

日志推送
MTT和单向RDMA读取是最大的贡献。该论文还讨论了基于 RDMA 的日志传送。但评估表明，这并没有产生太大的影响。

PolarDB-SCC采用单侧RDMA进行日志传送，以减少网络开销并节省CPU周期。每个辅助节点都有一个用于重做日志的日志缓冲区（正如我们在简介中提到的）。主节点远程填充这些内容。辅助节点的日志缓冲区大小与主节点的日志缓冲区大小相同。使用这种循环缓冲区机制，主节点的日志数据将始终远程写入辅助节点日志缓冲区中的相同偏移量。

评估
该论文包括一个很好的评估部分。他们比较不同的读方式

  • 默认值：主要处理除更新之外的所有查询，
  • 陈旧读取：辅助设备立即运行查询以提供可能陈旧的值，
  • 读取等待：辅助设备检查主设备的全局时间戳并延迟读取，直到赶上该时间点
  • SCC：二次使用MTT表和论文中提到的整个shebang

巨大的成功！SCC 方案几乎与延时读取方案一样快、一样高吞吐量，但提供线性化读取。

另外一篇：
评测：PolarDB-SCC：低延迟强一致性读取的云原生数据库
在《PolarDB-SCC：低延迟强一致性读的云原生数据库》一文中，阿里巴巴工程师介绍了加速复制、保证RO一致性读的算法。（SCC 代表“强一致性集群”。）现在所有应用程序都可以安全地从 RO 读取数据，阿里巴巴可以有效地自动缩放 RO 数量，并在一个无服务器端点后面的所有节点之间实现负载平衡查询。

RO 使用单侧 RDMA 从 RW 读取 WAL。WAL 是 RW 内存中的环形缓冲区。节点进行协调以确保 RW 可以安全地读取它，并且 RW 在复制条目之前不会覆盖条目。论文详细描述了该协议；它看起来像我以前见过的无锁环形缓冲区，但我不是专家。

使用 RDMA 传输日志可以节省 RW 的 CPU，作者声称它还可以最大限度地减少网络开销。

当客户端查询 RO 时，RO 检查 RW 的全局上次写入时间戳。如果 RO 已重播 WAL 直至该时间戳，则 RO 的本地数据足够新鲜以运行客户端的查询。否则，它会等到重播到该时间戳后再运行查询。RO 使用单侧 RDMA 从 RW 获取时间戳，以节省 RW 的 CPU 并可能最大限度地减少延迟。

作者描述了一种他们称之为线性 Lamport 时间戳的优化方法，以避免每次 RO 查询都对 RW 进行时间戳获取。如果一个 RO 查询 r2 在时间 T 开始获取 RW 时间戳，而另一个 RO 查询 r1 恰好在时间 T 之前开始，但尚未开始获取时间戳，那么 r1 就可以等待获取完成，并重复使用该时间戳。

这听起来像是一个重要的优化，但我想知道这种情况发生的频率有多高。作者没有告诉我们查询和获取的比例。重复使用获取似乎需要在 RO 上重新安排任务顺序：r1 在 r2 之前开始，但 r2 首先开始获取时间戳。这可能是线程调度不稳定造成的，也可能是因为某些查询比其他查询需要更多的预处理？也许 Nagle 算法可以让更多查询重复使用每次获取？

分层修改跟踪器
即使 RO 没有赶上 RW 的全局时间戳，几乎所有缓存的数据都是新鲜的，因此它可以在该新鲜子集上运行查询。修改跟踪表 (MTT) 让 RO 可以廉价地确定新子集中有哪些数据。

RW 在三个级别维护最后写入的时间戳：全局、表、页。（一页是一块内存，一张表中有很多页。）RW的MTT有两个哈希表：一个将表映射到时间戳，另一个将页映射到时间戳。当 RW 提交事务时，它会更新全局时间戳以及 MTT 中每个受影响的页和表的时间戳。

当 RO 启动查询时，它会首先获取 RW 的全局时间戳，并检查它是否应用了截至该时间戳的 WAL；如果是，RO 就有足够的时间运行查询。如果没有，RO 会获取相关表的时间戳并进行检查。如果检查失败，则获取相关页面时间戳。如果检查失败，它就没有选择了，只能等待。通过在这三个层面上检查时间戳（在可能的情况下使用线性 Lamport 时间戳优化），RO 有机会在其数据的新子集上运行查询，而无需等待全局跟上。

RW MTT 中的表/页哈希表是几百兆字节的固定大小内存区域；RO 在首次连接 RW 时会了解这些区域的地址，因此可以通过 RDMA 读取它们。哈希碰撞很常见。如果多个表（或页）具有相同的哈希键，RW 就会使用最新的时间戳作为该哈希键的值。这是一种悲观的做法：它记录的是任何冲突表（页）可能被修改的最新时间。因此，当 RO 检查它是否赶上了所有相关的时间戳时，可能会出现不必要的等待，但不会违反一致性。

当 RO 获取表/页时间戳时，它会更新 MTT 的本地副本。这意味着 RW 和 RO 的 MTT 并不趋同；RO 的副本有它所查询数据的最新时间戳，但不会更新其他表和页的时间戳。此外，RO 获取的时间戳可能是错误的：由于 RW 上的哈希碰撞，时间戳太新了。研究访问模式和哈希表设计之间的相互作用如何影响 MTT 在 RO 上的准确性，以及如何导致不必要的等待，将是一件有趣的事情。

评价
线性化Linear Lamport 时间戳和 MTT 看起来很聪明，我猜它们确实有效——PolarDB-SCC 正在生产中。

这两个功能可以由任何数据库实现，但 RDMA 协议需要特殊的硬件，因此我希望作者比较每个功能的非 RDMA 实现。

  • 如果PolarDB-SCC不使用RDMA来获取全局时间戳或MTT，情况会更糟吗？
  • 如果没有 RDMA，日志传送会慢多少？

尽管进行了所有实验，作者并没有隔离 RDMA 对每个功能的优势，而我们这些无法访问 RDMA 的人想知道。

我的 MongoDB 同事 Amirsaman Memaripour 与人合着了两篇论文，实验使用 RDMA 进行 MongoDB 复制[1,2 ] ，看起来很敏捷。

这是我唯一的抱怨。本文描述了一种令人兴奋的方法，可以为所有云数据库节省大量电力和碳，我希望自己尝试一下。