事务提交上的共识

有点难啃的一篇paper，读这篇paper需要对Paxos共识算法有一定的熟悉程度。

为什么需要对事务的提交要达成共识

这里的共识指的是对于一个决议选定的值达成多数派的同意。

为什么需要这个共识？因为在传统的事务两阶段提交里，协调者的身份是作为事务的发起者和提交者，事务能否提交或者事务已经提交完全取决于协调者自身收到的信息和记录的信息。

相当于，协调者是一个中心节点，如果协调者出现故障，那么后续的事务不能开启，正在执行的事务状态不明。

或许你会说，我多搞几个协调者节点就行了，这个也只能解决一部分问题，即后续的事务可以开启了。但是前一个节点那些未决的事务实际上还在那里卡着。

问题出现在了，决定事务提交和回滚的这几条决议，是由一个节点来负责的，也就是协调者。而不是由一组节点共同达成共识来决定的。这就间接导致了单个做决议，跪了就全跪了，多个节点一起做决议，跪了一个还能有其它的节点顶上来。这样只要做过的决议，还能读取出来，继续向前处理。其实思路就是这个，多少个节点一起做决议呢？2F+1个，不过实际操作的时候，只给F+1个发送消息要求其做决议。如果这F+1个有几个连不通，再在剩下的里面选几个发。

简单的对比：
paxos commit相当于把原来的1个协调者做决议，扩充到了2F+1个协调者做决议。

经过计算，Paxos Commit和经典的两阶段提交，具有相同的持久化延迟和消息发送延迟（前提是在无错的情况）。但Paxos Commit的消息数量会更多。传统的两阶段提交算法是Paxos Commit算法的一个特例，即F=0的时候的特例。

介绍

通常情况下，一个算法需要对两种正确性的特性满足：

1. 安全性（Safety）：描述什么是允许发生的，什么是绝对不能发生的。
2. 活性（Liveness）：描述什么是必须要发生的。

事务提交

在分布式系统中，事务是被一组叫做的Resource Manageers（RMs）的进程执行的，每个执行都发生在不同的节点上。

事务的提交意味着每个参与事务的RM必须愿意提交它，要不然事务必须被终止。

最基础的要求是：所有的RMs必须最终在事务提交和终止上达成一致。

我们抽象出事务提交协议如下，每个进程开始从一个working状态。所有的RMs必须最终达到committed状态或者aborted状态。

两个安全性需要如下：

• Stability：一旦一个RM已经进入到committed 或者 aborted状态，它将永远保持在这个状态。
• Consistency：不可能存在一个RM已经是在committed状态，但是其它RMs却在abort状态。

每个RM还有一个prepared状态，即：

一个RM可以进入committed状态只有在所有的RMs已经处于prepared状态的时候。

所有的RMs到达committed的状态只能按照如下事件发生：

1. 所有的RMs进入到prepared状态，以任何的顺序
2. 所有的RMs进入到committed状态，以任何顺序

协议允许如下的事件来终止这个事务提交：

任意一个RM从working状态可以进入到终止状态。但不允许出现已经有一个RM进入到committed状态，该RM还继续终止事务。

2pc state

我们对于事务提交的协议有两个关于Liveness的要求：

• Non-Triviality（非平凡条件，有实际效果的，在一定条件下做出有效决策）: 如果在贯穿整个事务执行的过程中网络是没有错误的。则
  1. 如果所有的RMs到达prepared 状态，之后所有的RMs最终到达committed状态。
  2. 如果一些RM到达了aborted 状态，那么所有的RMs最终到达aborted状态。
• Non-Blocking: 如果，在任意时间，足够多的节点所在的网络能够维持足够长的时间没有错误，那么每个在这些节点上执行的RM将最终达到committed 或者aborted状态。

可以更精确的描述事务提交协议，通过描述其一系列的合理行为，这些行为是在一系列的状态下来执行的。假设所有的RMs是在working state。为了定义下一个状态的关联，我们定义两个状态的预测：

• canCommit: 为True当且仅当所有的RMs处于prepared或者committed状态。
• notCommitted: 为True当且仅当没有RM处于committed状态。

每个单独的RM根据状态的预测，每个状态下可以由如下的两个行为组成：

• Prepare: RM可以转换working状态到prepared状态。
• Decide: 如果RM处于prepared状态，而且canCommit是true，则其可以转换自己的状态到committed状态；如果RM是在working或者prepared状态，并且notCommit是true，则其可以转换自己的状态为aborted状态。

两阶段提交在无错误情况下的流程简略图示：

2pc

两阶段提交的代价

• 一个RM进入Prepared状态，并且发送 一个Prepared消息给TM。（1 条消息）
• TM发送Prepare消息给其它所有RMs。（N-1条消息）
• 其它所有RM发送Prepared消息给TM。（N-1条消息）
• TM发送Commit消息给所有的RM。（N条消息）

所以，总共的消息数量 3N - 1。一般情况下，TM和RM会在同一个节点上，这种情况下，两条消息（TM->RMd的Prepared和RM->TM的Response）可以省略，最终3N - 3条消息发送。并且有3次消息的延迟。

对于持久化的代价如下：

1. 第一个RM写入Prepared状态到磁盘上。
2. 剩下的RM进入Prepared，写Prepared状态到磁盘上。
3. TM在收到所有的RMs的Prepared之后，做出Commit决定，记录磁盘。

所以共有3次写入磁盘等待。

两阶段提交的问题

TM失败会引起协议阻塞，直到TM恢复了。尤其是如果TM刚好在每个RM都发送Prepared回复之后挂了，那么所有其它的的RMs没办法知道TM是Committed还是aborted这个事务。

一个非阻塞的提交协议即单个的进程的失败不会阻止其它进程去决定事务提交或者中断。这类协议通常成为 三阶段提交协议。（不过Lamport在这里说没有谁给出一个完整的证明，来解释一个进程在收到两个不同的TM进程发来的消息的时候该怎么做）。

Paxos Commit

Paxos Commit使用一个单独的Paxos共识算法实例来在让RM去达到prepare或者abort上达成共识。共识选定的值即为：Prepared和Aborted。所以，每个RM均会有一个paxos共识实例。
事务提交了当且仅当每个RM的实例均选择了Prepared。要不然事务就是Aborted。
Paxos Commit使用2F+1个acceptors和一个当前的Leader来执行每个paxos实例。所以这里角色有：

• N RMs
• 2F+1 Acceptors
• 1 current leader。
  我们假设RMs事先是知道所有的Acceptors的。在Paxos中，一个ballot 0的phase 2a是可以携带任何value的。

Paxos Commit的大致执行过程如下：

1. 一些RM决定要prepare，于是发送BeginCommit给Leader。
2. Leader发送一个Prepare消息给其它所有参与的RMs。
3. 如果RM也决定要prepare，它会开启一次paxos instance，使用ballot 0的phase 2a消息，并携带value为Prepared。要不然（不准备prepare）就携带Aborted。
4. Acceptors收到2a消息后，将要回复的2b消息回复给Leader（每个RM的instance，Leader均需要收够2F+1个才能知道Acceptors对提案已经形成多数派决议了），Leader就知道了是否所有的RMs均已经对事务形成Prepared决议。
5. Leader知道了所有Acceptors的结果之后，给每个RM发送下一步Commit或者Abort，事务可以被提交当且仅当每个RM的instance的决议均为Prepared，要不然事务就是要被终止的。
   （这里Leader接收结果可换成直接让RMs接收2b的结果，省去了一次消息延迟）

如果Leader等待某个RM的2b没有等到（通过超时机制），则表示一个或多个RM的prepare决议可能没有达成共识。Leader会在这个instance上使用一个更大的ballot num区检测是否真的没有达成决议。如果在2a时，Leader收到的决议可以是任意值时（意味着确实没有达成共识），此时Leader会促使其达成abort共识，将其成为决议，通过在2b中携带value Aborted。

这里存在一个优化，就是如果Leader在收取所在RMs的instance的2b时，一旦收到其中一个instance的决议是Aborted，则可以快速让整个事务失败。通过短路机制，即可以用什么广播协议通知所有参与事务的进程，事务已经被Aborted了，一旦一个进程知道事务被Aborted，它可以忽略其它协议的消息）。

我们看看Paxos提交算法是否满足了之前非阻塞算法应该满足的四个特性，即：

• Stability: 一旦RM收到来自Leader的决议，它就不会修改决议。稳定性有保障。
• Consistency: 一致性是由Paxos算法来保证的，即一个instance中只能 选定一个值。
• Non-Triviality: 如果Leader在使用新的bllot num（应该是大于0的ballot num）执行phase 1a前等待足够长的时间，所以，如果没有出现失败的情况，每个Paxos实例应该在用ballot 0执行phase 2a时就执行完了。（表示Leader会主动做动作的，或者Acceptors没有失败就不需要Leader主动处理）
• Non-Blocking: 通过Paxos的progress特性来满足的，即如果存在一个足够大的于Acceptors节点间的网络，是没有错误的，则每个Paxos实例将最终选定要么Prepared或者Aborted。

在没有错误的情况下，Paxos Commit的提交过程。

paxos 2pc

Paxos Commit的代价

消息数量

假设有N个RMs，假设系统能容忍F个失败，所以需要有2F+1个Acceptors。我们在这里优化一下，Leader只给F+1个Acceptor发送消息，当有发不过去或者回不来的Acceptor存在时，再换一个发。则Paxos 提交算法会有潜在的节点间通信数量如下：

1. 第一个RM要prepare，发送一个BeginCommit消息给到Leader。（1条消息）
2. Leader发送一个Prepare消息给所有其它的RMs（N-1条消息）
3. 每个RM发送一个bollot 0 phase 2a 带Prepared value的instance消息给F+1个Acceptors（N（F+1）条消息）
4. 对于每个RM的Paxos instance来说，Acceptor回复2a的2b消息给Leader，但是可以让每个Acceptor都等到收到所有RMs的instanc的2a之后再一并回复给Leader，即将其绑定到一条消息里面。（F+1 条消息）
5. Leader给所有的RMs发送Commit消息并携带了每个instance的phase 3 Prepared的消息。（N 条消息）

持久化磁盘数量

Paxos Commit和传统的两阶段提交有着相同的写延迟。

1. 当RM要进入到prepared状态时，RM记录消息到持久化设备上。 N条记录
2. Acceptors在回复2b决议的时候，要先记录到自己的持久化设备上。F+1条记录

一些优化：

1. initial leader和其中一个Acceptor是在同一个节点上的，则一个2b Prepared消息可以被优化。更进一步第一个RM的BeginCommit可以和2a 一起发，又省一条。
2. 如果 N >= F，并且每个Acceptor均和RM在同一节点部署，并且第一个RM和Leader在同一个节点上。则第一个RM到Leader的消息可以省了，并且F个2a的消息变成了节点内部的。
3. 我们可以让phase 3 消息不用Leader发，而是让Acceptors直接发送给每个RMs。这就要求RM能够归并Acceptors的结果，并从中学习到结果。这样会减少一次消息传送的延迟。但造成了更多的消息发送，即N(2F+3)，不过加上2中的优化，可以让消息总量在(N-1)(2F+3)条。消息延迟成了3个。
4. 如果能够让RMs都自发地发起Prepare，而不用Leader间接去通知，则消息延迟降低成2个。

cost

这里的co-locatin表示混合部署。

详细的推导过程不赘述了，参见原论文。

传统的两阶段提交相当于是 F=0 时的Paxos Commit的特例退化。

简单总结一下

实际上Paxos Commit是消除了（弱化了）TM一个进程的决策。因为传统的2PC中TM可以单方面决定是否提交或Abort。也就是通过弱化TM，去中心化来使得决议本身成为可靠的结果。即：

1. 代替单个TM的持久化存储为多个Acceptors的持久化存储。
2. 代替单个TM为一组可能的Leaders集合。

Paxos Commit更进一步地从本质上消除了TM的决策的角色。

Paxos Commit在具体实现上

事务的创建、注册、加入、提交、获取结果

（这里与上面最大的不同点就是多了一次共识，即registrar要将参与者RMs的列表先达到共识，相当于持久化下来，之后才是给其它RM发送Prepare，让RMs自己开始自己的paxos instance）

以下是ChatGPT3.5的一些相关问答：
这里直接使用ChatGPT 3.5的结果

在Consensus on Transaction Commit论文中，一个Paxos Commit事务最终的执行流程是怎样的？每个参与的进程及其作用分别是什么？
ChatGPT 说：
ChatGPT
在 Consensus on Transaction Commit 论文中，Paxos Commit 提出了基于 Paxos 共识协议的事务提交机制，旨在解决传统 Two-Phase Commit (2PC) 的单点故障问题。以下是 Paxos Commit 中事务最终执行流程的简要概述，以及每个参与进程的角色及其作用。

Paxos Commit 执行流程
Paxos Commit 的执行流程基于 Paxos 协议，用于保证分布式系统中的一致性决策。以下是事务执行的主要步骤：

事务初始化阶段：

Initial Leader (通常为 TM 或 RM)：负责发起 Paxos 提案来决定事务的提交或回滚。初始 Leader 会先向其他参与者提议一个事务决策过程，类似于传统 2PC 的 prepare 阶段。（笔者注：初始Leader是在事务注册之后，记录的当时的Leader。）
Resource Managers (RMs)：代表资源的持有者，例如数据库节点。RMs 接收 Initial Leader 发起的提案请求，进行处理，并回应是否接受该提案。
Registrar：登记事务相关的元数据，主要是用来跟踪事务的参与者（RMs）。Registrar 并不参与事务决策过程，而是作为一个元数据服务，为查询事务状态或恢复操作提供支持。
Prepare 阶段：

Initial Leader：Initial Leader 向所有的 RMs 发送 Prepare 消息，询问它们是否愿意提交事务。此时，Leader 开始发起提案。
RMs：RMs 收到 Prepare 消息后，检查其本地状态，决定是否准备提交。如果愿意提交，它们会向 Leader 发送 "Prepared" 的响应，表示它们已准备好提交。
Paxos 执行阶段（Propose 阶段）：

Initial Leader：收集足够多的“Prepared”响应后，Initial Leader 发起一个正式的 Paxos 提案，决定事务是提交还是回滚。这时，Leader 开始推进共识决策。
Paxos Acceptors：所有参与的进程（可能包括 RMs）作为 Paxos 协议的 Acceptor，接收并表决是否接受该提案。如果大多数（quorum）的 Acceptor 接受该提案，则提案被认为达成一致。
决策执行阶段：

Initial Leader：在收到足够多的 Acceptor 同意提案的回应后，Leader 宣布最终决定（commit 或 abort）。该决定会被广播给所有的 RMs。
RMs：RMs 根据最终的决策执行提交或回滚操作，并记录该事务的最终状态。
事务完成阶段：

Initial Leader 和 RMs：一旦所有 RMs 执行了决策，事务完成。RMs 可能会记录最终状态以应对潜在的故障恢复情况。
参与进程及其作用
Initial Leader (通常为 TM 或 RM)：

发起并领导整个事务提交流程。
负责提案生成和推进 Paxos 共识协议。
在事务过程中，充当协调者角色，但与传统 2PC 的 TM 不同，Paxos Commit 中 Leader 可容错，并可在故障时切换。
Resource Managers (RMs)：

资源持有者，负责检查其本地资源状态，决定是否参与事务提交。
作为 Paxos 的 Acceptor，参与提案的表决并执行最终的事务决策。
在事务执行中，负责实际的资源提交或回滚操作。
Paxos Acceptors：

参与 Paxos 协议的节点，负责表决提案并达成一致。
一些 RMs 也可以充当 Acceptor 角色，但并不是所有参与者都必须是 Acceptor。
Registrar：

登记事务的参与者和元数据。
并不直接参与决策过程，但在故障恢复时，Registrar 的记录可用于查找事务的参与者和状态。
总结
Paxos Commit 的事务执行流程基于 Paxos 协议，通过选举 Leader 发起事务提案，并通过 Paxos 多数派决策机制达成一致，从而避免了传统 2PC 中协调者单点故障的问题。每个进程都有明确的角色，负责不同的任务，确保在部分进程故障的情况下，系统仍然能够继续进行决策并完成事务。

您说：
在上文中initial leader和leader的区别是什么？
ChatGPT 说：
ChatGPT
在 Paxos Commit 的上下文中，Initial Leader 和 Leader 实际上是相关但不同的概念，它们的区别主要体现在以下几个方面：

1.  Initial Leader:
    角色定义: Initial Leader 是指在 Paxos Commit 流程启动时，首先被选中的那个发起者或协调者。这个角色通常会由一个 Resource Manager (RM) 或事务管理器（TM）扮演，负责开始事务提交的提案流程。
    任务: Initial Leader 负责向其他参与者发送初始的提案消息（Prepare 阶段）并收集响应。如果 Initial Leader 成功引导整个过程，那么它将继续担任 Leader 角色，直到事务完成。
    容错性: 如果 Initial Leader 失败或挂掉，其他参与者可以通过 Paxos 协议重新选举一个新的 Leader。Initial Leader 仅仅是初始发起者，但并不保证始终是后续流程中的 Leader。
2.  Leader:
    角色定义: Leader 是在 Paxos 协议执行过程中实际领导提案的那个节点。它负责推动提案，并与其他参与者（Acceptor）进行通信，直至达成共识。在整个事务决策过程中，可能会出现多个不同的 Leader，因为 Paxos 允许在故障或竞争的情况下进行重新选举。
    任务: Leader 的任务是发起和推进 Paxos 协议中的提案。Leader 发出的提案需要得到多数派参与者的接受（quorum）才能达成共识。
    动态变化: Leader 可以动态变化。如果当前 Leader 失败或没有得到足够的响应，其他节点可以通过 Paxos 机制成为新的 Leader，并继续推进提案。Leader 的职责在整个协议执行期间可能会转移。
    两者的关系:
    Initial Leader 是整个 Paxos Commit 流程的第一个提案发起者，通常由某个进程预先担任。这个角色是静态分配的，并且负责启动事务的准备阶段。
    Leader 是在 Paxos 协议执行过程中的实际决策领导者。虽然 Initial Leader 在流程启动时通常会担任 Leader 角色，但在协议执行过程中，Leader 可以发生变化。例如，如果 Initial Leader 失效或遇到问题，Paxos 机制将允许其他进程成为新的 Leader。
    总结
    Initial Leader 是启动事务的第一个协调者，负责开始提案流程。
    Leader 是在 Paxos 协议执行过程中，实际推动共识达成的节点。Initial Leader 通常最先担任 Leader，但在故障或其他情况下，Leader 角色可以动态变化。
    两者的关键区别在于角色的时间点和持续性：Initial Leader 是启动阶段的角色，而 Leader 是在整个协议过程中领导提案的角色，并且可能会随时间发生变化。

4/4

您说：
在Consensus on Transaction Commit 论文中，the names of the transaction's coordinator processes 具体指的是什么？这些进程的功能是什么？
ChatGPT 说：
ChatGPT
在 Consensus on Transaction Commit 论文中，提到的“the names of the transaction's coordinator processes” 指的是在 Paxos Commit 协议中与事务协调相关的进程名称或角色。为了更好地理解这些进程的功能，我们需要知道它们在事务提交过程中的作用。

事务协调进程的名称和功能
在 Paxos Commit 协议中，主要涉及以下几类进程：

Initial Leader (或 Initial Coordinator)：

功能: 负责启动事务的提交流程。Initial Leader 发起事务提交提案，向所有参与者（通常是 Resource Managers, RMs）发送 Prepare 消息。它在事务开始时起着关键的领导作用。
角色: 在事务开始时，Initial Leader 是事务协调的发起者，负责开始提案过程。
Paxos Leader：

功能: 在事务提交过程的执行阶段，Paxos Leader 负责提出提案并推动共识过程。Leader 通过 Paxos 协议与其他参与者沟通，以达成关于事务提交或回滚的最终决定。
角色: Paxos Leader 可能是 Initial Leader 也可能是后续通过 Paxos 选举出来的 Leader。它负责发起和推进提案，确保事务最终达成一致。
Paxos Acceptors：

功能: 参与 Paxos 协议的进程，负责接收和表决事务提交的提案。Acceptors 对提案进行投票，决定是否接受事务提交。
角色: Acceptors 是参与决策的节点，通过接受提案来帮助达成共识。Paxos 协议要求多数（quorum）的 Acceptors 接受提案才能完成决策。
Resource Managers (RMs)：

功能: 代表实际资源的持有者，例如数据库节点。它们接收事务的提交请求，执行实际的事务操作（如提交或回滚），并在 Paxos 协议中充当 Acceptors 的角色。
角色: RMs 执行事务的实际操作，并且在 Paxos 协议中参与投票，最终决定事务的提交或回滚。
Registrar：

功能: 记录事务的相关元数据，跟踪事务的参与者和状态。虽然 Registrar 不直接参与事务的决策，但它负责维护事务的登记信息。
角色: Registrar 提供事务状态的查询服务，并在事务恢复或故障处理过程中提供支持。
总结
在 Consensus on Transaction Commit 论文中，"the names of the transaction's coordinator processes" 涵盖了这些关键的进程角色：

Initial Leader：事务提案的发起者，启动事务提交流程。
Paxos Leader：负责推动 Paxos 协议和达成最终的事务决策。
Paxos Acceptors：参与投票和达成共识。
Resource Managers (RMs)：执行实际的事务操作并参与决策。
Registrar：记录和维护事务的元数据，辅助事务状态的查询。
这些进程的功能分工确保了 Paxos Commit 协议在分布式环境中实现一致性和容错，克服了传统 2PC 的局限性。

End;