2024年7月3日 (三) 06:18的最新版本

Paxos解决的是什么问题

state machine replication

如上所示的系统中，如果客户端要执行某个命令，那么将遵循如下的步骤：

发送命令到其中某一个server
server首先将命令记录到log中，然后将命令发送到其他的服务中；其他server同样将其记录到log中
当命令完整的记录到各个server之后，就可以传到state machine去执行了，并将结果返回给客户端

其中，consensus module用来保证log的复制是正确的，也就是paxos要解决的问题。

那么，对于这样一个系统有哪些要求呢？

所有的服务器将以同样的顺序执行相同的命令
只要集群中大多数服务器可用，系统就是可用状态

Paxos算法

The Paxos algorithm, when presented in plain English, is very simple.

共识问题

上述问题可以简化为，有多个服务可以propose value，而共识算法将保证有且仅有一个value会被选中（chosen）。这里面隐含的条件是：

如果没有任何value被propose，那么也不应该有任何值被选中
值一旦被选中，各个服务应该可以知晓（learn）选中的值

从而可以得出共识算法实现的安全性约束：

Safety requirements

Validity (or non-triviality): Only a value that has been proposed may be chosen, A process never learns that a value has been chosen unless it actually has been.
Agreement (or consistency, or safety): Only a single value is chosen, and
Termination (or liveness): if a value has been chosen, then a process can eventually learn the value.

assumptions

另外，paxos中是不考虑拜占庭问题的，有如下假设成立：

Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be re- membered by an agent that has failed and restarted.
Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted. 也即是 fail-stop/crash (non-Byzantine) and message delay/loss

Choosing a Value

Quorum

Paxos made simple中，从最简单（但不正确）的方式开始，逐步加强约束，最终得到正确的算法。

首先最简单的情况下，只有一个acceptor，然后choose第一个收到的提案。这种办法显然不行，因为一旦这个acceptor出问题了整个系统就没法用了，所以需要有多个acceptor，当系统中有大多数acceptor接受了提案则认为值被choosen。

为了在集群中形成多数派，其数目必须为基数，设集群中server总数为$$2F + 1$$，则至少可以由$$F+1$$个server构成多数派。

P1

如果仅有一个proposer提出了一个提案，那么这个提案显然是需要被接受的。也就是说，acceptor必须要接受它收到的第一个提案，否则如果只有一个proposal的时候就无法选出任何提案了。因此可推导出约束P1：

P1. An acceptor must accept the first proposal that it receives.

但是这样是有问题的，因为如果不同的proposal提出多个提议，分别被不同的acceptors接受，则无法形成多数派：

即使只有两个提案，如上图，如果其中一个acceptor失败则也无法知晓到底哪个值被choose了。

因此说，只允许acceptor接受一个提议是不行的。acceptor必须要能够允许接受多个提议。对于不同的proposal，以编号的形式来表示，则每个提议可表示为$$p_{i}(v)$$，即第$$i$$个提议值为$$v$$。

P2

为了解决P1的问题，可以允许acceptor接受多个提议，但是保证这些提议的值是一样的。也即：

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

@@ 第1行： / 第1行： @@
-=介绍=
+=Paxos解决的是什么问题=
-分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。
+==state machine replication==
-为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。
+[[File:Log-Replication.png|600px]]
-对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。
+如上所示的系统中，如果客户端要执行某个命令，那么将遵循如下的步骤：
-=Paxos made simple=
+#发送命令到其中某一个server
+#server首先将命令记录到log中，然后将命令发送到其他的服务中；其他server同样将其记录到log中
+#当命令完整的记录到各个server之后，就可以传到state machine去执行了，并将结果返回给客户端
+其中，consensus module用来保证log的复制是正确的，也就是paxos要解决的问题。
+那么，对于这样一个系统有哪些要求呢？
+* 所有的服务器将以同样的顺序执行相同的命令
+* 只要集群中大多数服务器可用，系统就是可用状态
+=Paxos算法=
 <q>
 The Paxos algorithm, when presented in plain English, is very simple.
 </q>
-==推导过程==
+==共识问题==
+上述问题可以简化为，有多个服务可以propose value，而共识算法将保证有且仅有一个value会被选中（chosen）。这里面隐含的条件是：
+* 如果没有任何value被propose，那么也不应该有任何值被选中
+* 值一旦被选中，各个服务应该可以知晓（learn）选中的值
+从而可以得出共识算法实现的安全性约束：
 ===Safety requirements===
-* Only a value that has been proposed may be chosen,
-* Only a single value is chosen, and
-* A process never learns that a value has been chosen unless it actually has been.
-[[Category:Distributed]]
+;Validity (or non-triviality):Only a value that has been proposed may be chosen, A process never learns that a value has been chosen unless it actually has been.
+;Agreement (or consistency, or safety):Only a single value is chosen, and
+;Termination (or liveness): if a value has been chosen, then a process can eventually learn the value.
+===assumptions===
+另外，paxos中是不考虑拜占庭问题的，有如下假设成立：
+* Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be <span class="article-label">re- membered</span> by an agent that has failed and restarted.
+* Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are <span class="article-label">not corrupted</span>. 也即是 <span class="article-label">fail-stop/crash</span> (non-Byzantine) and <span class="article-label">message delay/loss</span>
+==Choosing a Value==
+===Quorum===
+Paxos made simple中，从最简单（但不正确）的方式开始，逐步加强约束，最终得到正确的算法。
+首先最简单的情况下，只有一个acceptor，然后choose第一个收到的提案。这种办法显然不行，因为一旦这个acceptor出问题了整个系统就没法用了，所以需要有多个acceptor，当系统中有大多数acceptor接受了提案则认为值被choosen。
+为了在集群中形成多数派，其数目必须为基数，设集群中server总数为$$2F + 1$$，则至少可以由$$F+1$$个server构成多数派。
+===P1===
+如果仅有一个proposer提出了一个提案，那么这个提案显然是需要被接受的。也就是说，acceptor必须要接受它收到的第一个提案，否则如果只有一个proposal的时候就无法选出任何提案了。因此可推导出约束P1：
+<q>
+P1. An acceptor must accept the first proposal that it receives.
+</q>
+但是这样是有问题的，因为如果不同的proposal提出多个提议，分别被不同的acceptors接受，则无法形成多数派：
+[[File:Paxos-p1-issue.png|600px]]
+即使只有两个提案，如上图，如果其中一个acceptor失败则也无法知晓到底哪个值被choose了。
+因此说，只允许acceptor接受一个提议是不行的。acceptor必须要能够允许接受多个提议。对于不同的proposal，以编号的形式来表示，则每个提议可表示为$$p_{i}(v)$$，即第$$i$$个提议值为$$v$$。
+===P2===
+为了解决P1的问题，可以允许acceptor接受多个提议，但是保证这些提议的值是一样的。也即：
+<q>
+P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.
+</q>
+[[Category:Algorithm]]