spring mvc工作原理_redis aof_paxos 算法

参考资料 #8：知行学社的分布式系统与Paxos算法视频课程，循序渐进，讲解得比较浅显易懂

什么是 consensus （一致性）问题？

在一个分布式系统中，有一组的 process，每个 process 都可以提出一个 value，consensus 算法就是用来从这些 values 里选定一个最终 value。如果没有 value 被提出来，那么就没有 value 被选中；如果有1个 value 被选中，那么所有的 process 都应该被通知到。

上面问题看上去很好解决，比如用一个 master，所有 process 都向这个 master 提交 value，这个 master 可以根据先到的原则选择最先到达的 value 为最终 value 并通知给所有 process。这里有个问题，如果这个 master 断了、当机、重启、崩溃了怎么办？所以一个好的方法就是选择一组 masters，value 由这一组 masters 共同决定，有点像 ”议会“。为了解决这个问题，大家提出了各种各样的 protocols（协议），其中最有名的就是 Lamport 的 Paxos.

Icon

Paxos is a consensus algorithm executed by a set of processes, termed replicas, to agree on a single value in the presence of failures.

Paxos算法解决的问题是在一个可能发生异常（进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，不考虑消息篡改即拜占庭错误的情况）的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

Paxos协议提出只要系统中2f+1个节点中的f+1个节点可用，那么系统整体就可用并且能保证数据的强一致性，它对于可用性的提升是极大的。

Paxos协议由Leslie Lamport最早在1990年提出，由于Paxos在云计算领域的广泛应用Leslie Lamport因此获得了2013年度图灵奖。

Leslie写的两篇论文：《The Part-Time Parliament》和《Paxos Made Simple》比较完整的阐述了Paxos的工作流程和证明过程，Paxos协议把每个数据写请求比喻成一次提案（proposal），每个提案都有一个独立的编号，提案会转发到提交者（Proposer）来提交，提案必须经过投票委员会(Quorum)接受才会生效，投票委员会中的节点叫做Acceptor。

角色分为proposers，acceptors（允许身）

proposers提出提案，提案信息包括提案编号和提议的value

acceptor收到提案后可以接受（accept）提案，若提案获得多数acceptors的接受，则称该提案被批准（chosen）

Paxos协议流程划分为两个阶段，第一阶段是Proposer学习提案最新状态的准备阶段；第二阶段是根据学习到的状态组成正确提案提交的阶段，完整的协议过程如下：

prepare 阶段：

1a) proposer选择一个提案编号n并将prepare请求发送给acceptors中的一个多数派；

accept 阶段：

2b) 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即接受这个请求。

这个过程在任何时候中断都可以保证正确性。例如如果一个proposer发现已经有其他proposers提出了编号更高的提案，则有必要中断这个过程。

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