[OSDI'23] Chardonnay

分布式系统 · 数据库领域的论文

Paper: Chardonnay: Fast and General Datacenter Transactions for On-Disk Databases

传统的分布式磁盘数据库系统通常需要使用昂贵的提交协议，如两阶段提交（2PC），以保证原子性，从而导致分布式事务的速度较慢。或者不使用 2PC，从而牺牲了语义、限制了编程模型或缩小了系统的可扩展性，导致系统的通用性降低。作者认为，在现代数据中心内，这种折衷不再是必要的。利用低延迟的存储和快速的远程过程调用（RPC）以及精心设计的协议，可以实现低延迟的2PC（例如在 Azure 上约 150us 的 2PC over Paxos）。随着快速 2PC 的实现，数据争用瓶颈从2PC转移到了在持有事务锁期间从相对较慢的存储读取数据的过程。

2PC (Two phase commit)

2PC 是一种分布式算法，用于协调参与分布式原子事务的所有进程，确定是否提交或中止（回滚）事务。

二阶段提交协议（Two-phase Commit，即2PC）是常用的分布式事务解决方案，它可以保证在分布式事务中，要么所有参与进程都提交事务，要么都取消事务，即实现 ACID 的原子性（A）。在数据一致性中，它的含义是：要么所有副本（备份数据）同时修改某个数值，要么都不更改，以此来保证数据的强一致性。

2PC 要解决的问题可以简单总结为：在分布式系统中，每个节点虽然可以知道自己的操作是成功还是失败，却是无法知道其他节点的操作状态。当一个事务需要跨越多个节点时，为了保持事务的 ACID 特性，需要引入一个作为协调者的组件来统一掌控所有节点（参与者）的操作结果并最终指示这些节点是否要把操作结果进行真正的提交（比如将更新后的数据写入磁盘等等）。因此，二阶段提交的算法思路可以概括为： 参与者将操作结果通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

顾名思义，2PC 分为两个过程：

1. 表决阶段：此时 Coordinator （协调者）向所有的参与者发送一个 vote request，参与者在收到这请求后，如果准备好了就会向 Coordinator 发送一个 VOTE_COMMIT 消息作为回应，告知 Coordinator 自己已经做好了准备，否则会返回一个 VOTE_ABORT 消息；
2. 提交阶段：Coordinator 收到所有参与者的表决信息，如果所有参与者一致认为可以提交事务，那么 Coordinator 就会发送 GLOBAL_COMMIT 消息，否则发送 GLOBAL_ABORT 消息；对于参与者而言，如果收到 GLOBAL_COMMIT 消息，就会提交本地事务，否则就会取消本地事务。

2PC 的一个众所周知的问题是阻塞，即协调者在不合时宜的时刻发生故障，从而阻止参与者取得进展。这可以通过复制协调者状态来实现可用性。

CAP 理论

在分布式系统领域，有一个理论，对于分布式系统的设计影响非常大，那就是 CAP 理论，即对于一个分布式系统而言，它是无法同时满足 Consistency（强一致性）、Availability（可用性）和 Partition tolerance（分区容忍性）这三个条件的，最多只能满足其中两个。但在实际中，由于网络环境是不可信的，所以分区容忍性几乎是必不可选的，设计者基本就是在一致性和可用性之间做选择，当然大部分情况下，大家都会选择牺牲一部分的一致性来保证可用性（可用性较差的系统非常影响用户体验的，但是对另一些场景，比如支付场景，强一致性是必须要满足）。但是分布式系统又无法彻底放弃一致性（Consistency），如果真的放弃一致性，那么就说明这个系统中的数据根本不可信，数据也就没有意义，那么这个系统也就没有任何价值可言。

CAP 理论三个特性的详细含义如下：

1. 一致性（Consistency）：每次读取要么是最新的数据，要么是一个错误；
2. 可用性（Availability）：client 在任何时刻的读写操作都能在限定的延迟内完成的，即每次请求都能获得一个响应（非错误），但不保证是最新的数据；
3. 分区容忍性（Partition tolerance）：在大规模分布式系统中，网络分区现象，即分区间的机器无法进行网络通信的情况是必然会发生的，系统应该能保证在这种情况下可以正常工作。

分区容忍性 | Partition tolerance

很多人可能对分区容忍性不太理解，知乎有一个回答对这个解释的比较清楚（CAP理论中的P到底是个什么意思？），这里引用一下：

• 一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。
• 当你一个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。
• 提高分区容忍性的办法就是一个数据项复制到多个节点上，那么出现分区之后，这一数据项就可能分布到各个区里，容忍性就提高了。
• 然而，要把数据复制到多个节点，就会带来一致性的问题，就是多个节点上面的数据可能是不一致的。
• 要保证一致，每次写操作就都要等待全部节点写成功，而这等待又会带来可用性的问题。
• 总的来说就是，数据存在的节点越多，分区容忍性越高，但要复制更新的数据就越多，一致性就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性就会降低。

CAP 理论原理

CAP 定理表明，在存在网络分区的情况下，一致性和可用性必须二选一。而在没有发生网络故障时，即分布式系统正常运行时，一致性和可用性是可以同时被满足的。但是，对于大多数互联网应用来说，因为规模比较大，部署节点分散，网络故障是常态，可用性是必须要保证的，所以只有舍弃一致性来保证服务的 AP。但是对于一些金融相关行业，它有很多场景需要确保一致性，这种情况通常会权衡 CA 和 CP 模型，CA 模型网络故障时完全不可用，CP 模型具备部分可用性。

在一个分布式系统中，对于这三个特性，我们只能三选二，无法同时满足这三个特性，三选二的组合以及这样系统的特点总结如下（来自左耳朵耗子推荐：分布式系统架构经典资料）：

• CA (Consistency + Availability)：关注一致性和可用性，它需要非常严格的全体一致的协议，比如“两阶段提交”（2PC）。CA 系统不能容忍网络错误或节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不知道对面的那个结点是否挂掉了，还是只是网络问题。唯一安全的做法就是把自己变成只读的。
• CP (consistency + partition tolerance)：关注一致性和分区容忍性。它关注的是系统里大多数人的一致性协议，比如：Paxos 算法 (Quorum 类的算法)。这样的系统只需要保证大多数结点数据一致，而少数的结点会在没有同步到最新版本的数据时变成不可用的状态。这样能够提供一部分的可用性。
• AP (availability + partition tolerance)：这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。Dynamo 就是这样的系统。

对于分布式系统分区容忍性是天然具备的要求，否则一旦出现网络分区，系统就拒绝所有写入只允许可读，这对大部分的场景是不可接收的。因此，在设计分布式系统时，更多的情况下是选举 CP 还是 AP，要么选择强一致性弱可用性，要么选择高可用性容忍弱一致性。

分布式一致性协议

为了解决分布式系统的一致性问题，在长期的研究探索过程中，业内涌现出了一大批经典的一致性协议和算法，其中比较著名的有二阶段提交协议（2PC），三阶段提交协议（3PC）和 Paxos 算法。

Google 2009年 在 Transaction Across DataCenter 的分享中，对一致性协议在业内的实践做了一简单的总结，如下图所示，这是 CAP 理论在工业界应用的实践经验。

CAP 理论在工业界的实践

其中，第一行表头代表了分布式系统中通用的一致性方案，包括冷备、Master/Slave、Master/Master、两阶段提交以及基于 Paxos 算法的解决方案，第一列表头代表了分布式系统大家所关心的各项指标，包括一致性、事务支持程度、数据延迟、系统吞吐量、数据丢失可能性、故障自动恢复方式。

Paxos 算法

Paxos：半数以上同意

2PC：全部同意

基于消息传递且具有高度容错性的一致性算法。Paxos 算法要解决的问题就是如何在可能发生几起宕机或网络异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

拜占庭问题：消息不完整或者被篡改。Paxos 在维持领导者选举或者变量修改一致性上，采取一种类似议会投票的过半同意机制，比如设定一个领导者，需要将此看做一个议案，征求过半同意，每个节点通过一个议案会有编号记录，再次收到此领导者的不同人选，发现已经有编号记录便驳回，最后以多数通过的结果为准。

Paxos 有点类似分布式二阶段提交方式，但是又不同，2PC 不能是多数节点同意，必须是全部同意。为了遵守过半节点同意的约束，Paxos 算法往往要求节点总数为奇数。

第一阶段：Prepare 阶段

A 把申请修改的请求 Prepare Request 发给所有的结点 A，B，C。注意，Paxos 算法会有一个 Sequence Number（你可以认为是一个提案号，这个数不断递增，而且是唯一的，也就是说 A 和 B 不可能有相同的提案号），这个提案号会和修改请求一同发出，任何结点在“Prepare 阶段”时都会拒绝其值小于当前提案号的请求。所以，结点 A 在向所有结点申请修改请求的时候，需要带一个提案号，越新的提案，这个提案号就越是是最大的。

如果接收结点收到的提案号 n 大于其它结点发过来的提案号，这个结点会回应 Yes（本结点上最新的被批准提案号），并保证不接收其它 <n 的提案。这样一来，结点上在 Prepare 阶段里总是会对最新的提案做承诺。

优化：在上述 prepare 过程中，如果任何一个结点发现存在一个更高编号的提案，则需要通知提案人，提醒其中断这次提案。

第二阶段：Accept 阶段

如果提案者 A 收到了超过半数的结点返回的 Yes，然后他就会向所有的结点发布 Accept Request（同样，需要带上提案号 n），如果没有超过半数的话，那就返回失败。

当结点们收到了 Accept Request 后，如果对于接收的结点来说，n 是最大的了，那么，它就会通过 request（修改这个值），如果发现自己有一个更大的提案号，那么，结点就会拒绝 request（拒绝修改）。

我们可以看以，这似乎就是一个“两段提交”的优化。其实，2PC/3PC 都是分布式一致性算法的残次版本，Google Chubby 的作者 Mike Burrows 说过这个世界上只有一种一致性算法，那就是 Paxos，其它的算法都是残次品。

我们还可以看到：对于同一个值的在不同结点的修改提案就算是在接收方被乱序收到也是没有问题的。

Raft 算法（解决 Paxos 实现难度）

Paxos 相比 Raft 比较复杂和难以理解。角色扮演和流程比 Raft 都要啰嗦。比如 Agreement 这个流程，在 Paxos 里边：Client 发起请求举荐 Proposer 成为 Leader，Proposer 然后向全局 Acceptors 寻求确认，Acceptors 全部同意 Proposer 后，Proposer 的 Leader 地位得已承认，Acceptors 还得再向 Learners 进行全局广播来同步。而在 Raft 里边，只有 Follower/Candidate/Leader 三种角色，角色本身代表状态，角色之间进行状态转移是一件非常自由民主的事情。

Raft 虽然有角色之分但是是全民参与进行选举的模式；但是在 Paxos 里边，感觉更像议员参政模式。

三个角色

follower、candidate、leader。

最开始大家都是 follower，当 follower 监听不到 leader，就可以自己成为 candidate，发起投票

leader 选举：timeout 限制

选举的 timeout

follower 成为 candidate 的超时时间，每个 follower 都在 150ms and 300ms 之间随机，之后看谁先 timeout，谁就先成为 candidate，然后它会先投自己一票，再向其他节点发起投票邀请。
如果其他节点在这轮选举还没有投过票，那么就给 candidate 投票，然后重置自己的选举 timeout。
如果得到大多数的投票就成为 leader，之后定期开始向 follower 发送心跳。

如果两个 follower 同时成为 candidate 的话，如果最后得到的票数相同，则等待其他 follower 的选择 timeout 之后成为 candidate，继续开始新一轮的选举。

log 复制

leader 把变动的 log 借助心跳同步给 follower，过半回复之后才成功提交，之后再下一次心跳之后，follower 也 commit 变动，在自己的 node 上生效。

分裂之后，另一个分区的 follower 接受不到 leader 的 timeout，然后会有一个先 timeout，成为 candidate，最后成为 leader。
于是两个分区就有了两个 leader。

当客户端有变动时，其中的 leader 由于无法收到过半的提交，则保持未提交状态。有的 leader 的修改，可以得到过半的提交，则可以修改生效。

当分裂恢复之后，leader 开始对比选举的 term，发现有更高的 term 存在时，他们会撤销未提交的修改，然后以最新的为准。

Chardonnay Design

强一致性快照读取协议

Chardonnay 利用快速的 RPC 来支持严格可序列化的无锁快照读取。其核心机制如下：

• Epoch 服务：维护一个单调递增的计数器，称为 epoch。Epoch 服务通过 Multi-Paxos 协议进行复制，确保每次读取的 epoch 值都保持全局一致。
• 快照读取协议：在每个事务提交时，读取最新的 epoch 值作为全局序列化点。系统通过该协议确定查询的读写集，从而在执行事务和获取锁之前预取所需的数据。

自动预取机制

为了减少在持有锁期间从慢速存储读取数据的时间，Chardonnay 设计了自动预取机制：

• 干运行模式（Dry Run）：事务在执行正式的读写操作之前，先在干运行模式下运行一次查询，以加载并固定事务需要的所有键值。
• 预取缓存：每个范围领导者维护一个预取缓存，用于存储事务读取集中的记录。预取缓存作为写通一致性缓存（write-through consistent cache），确保所有事务都能从缓存中读取已预取的键值，而无需访问底层数据库。

轻量级死锁避免

为了避免死锁，Chardonnay 提前计算事务的读写集，并按照确定的顺序获取锁：

• 锁顺序获取：通过干运行模式计算事务的读写集，并按照键值的升序顺序获取锁，避免死锁的发生。
• RPC 链式调用：客户端发送一个 RPC 请求到第一个需要键值的范围。该范围获取所有本地锁，执行必要的本地读取操作，然后将请求转发到下一个范围。最后一个范围完成本地操作后，将所有读取结果返回给客户端，从而减少获取锁的开销。

架构

Chardonnay 的系统架构主要包括以下四个组件：

1. Epoch 服务：负责维护和更新单调递增的计数器 epoch，为所有提交的事务提供全局序列化点。
2. KV 服务：核心服务，存储用户的键值数据，使用共享无结构的范围分片架构，并通过 Paxos 实现 WAL。
3. 事务状态存储：以容错、复制的方式存储活动事务的状态，防止 2PC 阻塞。
4. 客户端库：为用户提供访问数据库的接口，并在 Chardonnay 中充当 2PC 协调器。

Chardonnay 通过利用快速 RPC和无锁快照读取协议，实现了高效的分布式事务处理，并在高争用工作负载下保持了出色的性能。通过自动预取和轻量级死锁避免机制，Chardonnay 在保持严格可序列化语义的同时，显著减少了事务锁的争用，从而实现了高吞吐量和低延迟的分布式数据库系统。

License

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

Share