spring mvc工作原理_paxos 算法_哈希

（Messagespassing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、垮、重启，消息可能会延迟、丢失、重复，在基础Paxos 场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。

为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会制的模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantinefailure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。

对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。

算法 算法的提出与证明 首先将议员的角色分为 proposers，acceptors，和learners（允许身）。proposers 提出提案，提案信息包括提案编号和提议的 value；acceptor收到提案后可以接受（accept）提案，若提案获得多数 acceptors 的接受，则称该提案被批准（chosen）；learners只能“学习”被批准的提案。划分角色后，就可以更精确的定义问题：

决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）； 在一次Paxos 算法的执行实例中，只批准（chosen）一个 value； learners 只能获得被批准（chosen）的value。 另外还需要保证 progress。这一点以后再讨论。

作者通过不断加强上述3个约束（主要是第二个）获得了 Paxos 算法。

批准 value 的过程中，首先 proposers 将 value 发送给 acceptors，之后 acceptors 对value 进行接受(accept)。为了满足只批准一个 value 的约束，要求经“多数派（majority）”接受的 value成为正式的决议（称为“批准”决议）。这是因为无论是按照人数还是按照权重划分，两组“多数派”至少有一个公共的 acceptor，如果每个acceptor 只能接受一个 value，约束2就能保证。

于是产生了一个显而易见的新约束：

P1：一个 acceptor 必须接受(accept)第一次收到的提案。 注意 P1 是不完备的。如果恰好一半 acceptor接受的提案具有 value A，另一半接受的提案具有 value B，那么就无法形成多数派，无法批准任何一个 value。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-28610-1.html