亚马逊DynamoDB大规模分布式事务原理


DynamoDB 的一个杀手级功能是任何规模的可预测性。请阅读Marc Brooker 的文章以充分理解此功能。
这篇论文出现在 7 月的 USENIX ATC 2023 上。

与这种可预测性原则相一致，在向 DynamoDB 添加事务时：

  1. 第一个主要约束是保持任何规模的单键读/写的可预测高性能。
  2. 第二个大限制是使用就地更新操作来实现事务，而无需多版本并发控制。这样做的原因是他们不想用不支持多版本控制的存储层进行模拟。

满足上述两个约束似乎是一件愚蠢的事情，因为事务因不具备可扩展性以及在没有 MVCC 的情况下降低正常操作的性能而臭名昭著，但团队在这些约束周围发挥了创造力，并设法找到了一个可取之处。

在研究了客户需求和案例研究之后，他们发现可以使用一次性事务来满足这些需求，因为他们可以通过仅使用一次性事务来表达大多数用例。

一次性事务意味着事务作为单个请求提交，而不是这样 ：

  1. 从BEGIN_TXN 开始
  2. 一段来回交互操作来提交。
  3. 用COMMIT_TXN 提交（或中止）。

Sinfonia 论文介绍了该系统单次事务的附带好处。DynamoDB 论文采用了不同的方法，以避免产生 Sinfonia 使用的两阶段锁定2pc方法的缺点。  

锁定会限制并发性并可能导致死锁。此外，当应用程序在事务中获取锁后出现故障时，它需要一种恢复机制来释放锁。这些将违反不干扰单个读/写可预测性的原则。

DynamoDB 使用乐观并发控制方案，而不是基于锁定的方法。而且还是一个经典！该协议可以追溯到 VLDB 1980：还记得时间戳顺序（TSO）算法吗？

在 TSO 算法中，每个事务在开始时都会分配一个时间戳，用于定义其在串行顺序中的位置。每个对象 x 都标有成功读/写它的最后一个事务的时间戳。只要事务看起来在指定的时间执行，就可以实现串行化。为了实现这一点，如果/当事务尝试从其未来访问（读/写）对象时，它将被中止。

但是，事务的正确性并不依赖于时间戳，时钟同步只会有助于提高性能，因为更准确的时钟会导致更成功的事务和符合实时的序列化顺序。

使用一次性事务，并采用 OCC TSO 算法检查所有步骤，并提供真正符合 DynamoDB 可预测响应时间精神的事务协议。

架构：
一个事务协调器执行一次性 OCC TSO 协议的两阶段协调。

一次性事务
该团队发现，大多数形式为启动/交互/提交的业务事务都可以建模为：

  1. 读取事务，
  2. 然后是带有检查条件的写入事务。

一次性事务将具有良好的表达性，并且仍然提供可串行性（感谢最后对写入事务的检查）。

例如：

  1. 检查条目是否存在：checkItem
  2. 检查产品中条目状态：updateItem
  3. 插入主表：putItem

一次性事务将上面三个函数作为一次请求发出，（banq注：类似事件溯源eventsourcing中作为一个命令事件发出）。

TransactWriteItemsRequest req = new TransactWriteItemsRequest (checkItem, updateItem,putItem);
DynamoDBclient.transactWriteItems(req );


写入事务细节
在协议的准备阶段，事务协调器向主存储节点发送正在写入的项目的消息。在以下情况下，主存储接受事务：

  • 满足该项目的所有先决条件
  • 事务的时间戳大于项目的时间戳（指示上次写入的时间）
  • 尝试写入相同项目的先前接受的事务集为空

如果事务被所有参与的存储节点接受，则事务协调器将使用第二阶段消息提交事务。每个参与者存储节点对其本地项目执行所需的写入，并将事务的时间戳记录为项目的上次写入时间戳。检查前提条件但未写入的项目的时间戳也会更新。

对于恢复，我们不需要关心存储节点组主故障，这要归功于 Paxos。事务协调器故障令人担忧，通过利用分类账和使用恢复管理器可以轻松解决此问题。

协调器在账本（以事务标识符为键的 DynamoDB 表）中维护每个事务及其结果的持久记录。恢复管理器定期扫描分类账，查找尚未完成的旧交易。这种停滞的事务被分配给一个新的事务协调器，该协调器恢复执行事务协议。多个协调器同时完成同一事务是可以的，因为写入项目的重复尝试会被其存储节点忽略。

协调器队列中的时钟源自AWS 时间同步服务，使它们在几微秒内保持紧密同步。

只读事务执行
只读事务煞费苦心地避免了在每个项目上维护读取时间戳，因为这会将每次读取变成对持久复制数据的成本更高的写入操作（以更新读取时间戳）。为了避免这种延迟和成本，他们为只读事务设计了一种两阶段无写协议。

这是通过使用乐观并发控制的经典思想再次完成的。

  1. 在协议的第一阶段，事务协调器读取事务读取集中的所有项目。如果这些项目中的任何一个当前正在被另一个事务写入，则读取事务将被拒绝；否则，读取事务进入第二阶段。在对事务协调器的响应中，存储节点不仅返回项目的值，还返回其当前提交的日志序列号（LSN）。该项目当前提交的 LSN 是存储节点执行并向客户端确认的最后一次写入的序列号。LSN 单调增加。
  2. 在第二阶段，再次读取项目。如果两个阶段之间的项目没有更改，即 LSN 没有更改，则读取事务会成功返回，并包含已获取的所有项目值。如果在两轮协议之间更新了某个项目，则读取事务将被拒绝。

结论
DynamoDB 一如既往地在任何规模上保持可预测和高性能。最近的黄金日统计数据显示，DynamoDB 每秒处理峰值 1.26 亿个请求，具有个位数毫秒的延迟和高可用性。