什么是共识算法

背景

分布式系统集群设计中面临着一个不可回避的问题，一致性问题

对于系统中的多个服务节点，给定一系列操作，如何试图使全局对局部处理结果达成某种程度的一致？

这个一致性问题大致有如下的场景：

节点之间通讯不可靠的，延迟和阻塞

节点的处理可能是错误的，甚至节点自身随时可能宕机

节点作恶

举例说明，就比如有两家电影院同时售卖总量一定的电影票，在这样的场景下，要如何设计方式来保证两家电影院协调同步不出现超卖或者错卖的问题呢？

共识算法，就是解决对某一提案（目标，投票等各种协作工作），大家达成一致意见的过程

比如上述的买票问题，就可以有如下的设计：

1.每次卖票打电话给其他电影院，确认当前票数

2.协商售卖时间，比如一三五A卖，二四六B卖

3.成立个第三方存票机构，它统一发票

通过以上的设计，可以看出一个很重要的解决一致性算法的解决思路，即：

将可能引发不一致的并行操作进行串行化，就是现在计算机系统里处理分布式一致性问题基础思路和唯一秘诀

著名的共识设计理论

FLP 不可能性原理  共识算法的理论下限

提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表，该论文后来获得了 Dijkstra（就是发明最短路径算法的那位）奖。

FLP 原理认为对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。

三人三房间投票例子

三个人在不同房间，进行投票（投票结果是 0 或者 1）。三个人彼此可以通过电话进行沟通，但经常会有人时不时地睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。如果可以重新投票，则类似情形每次在取得结果前发生

带入到计算机领域就是说，即便在网络通信可靠情况下，一个可扩展的分布式系统的共识问题的下限是无解。即可靠性的下限是0%

CAP  分布式系统领域的重要原理

CAP 原理最早由 Eric Brewer 在 2000 年，ACM 组织的一个研讨会上提出猜想，后来 Lynch 等人进行了证明

• C（一致性）：所有的节点上的数据时刻保持同步，即数据一致

• A（可用性）：每个请求都能在一定时间内接受到一个响应，即低延迟

• P（分区容错）：当系统发生分区时仍然可以运行的

定理：任何分布式系统只可同时满足二点，没法三者兼顾。即数据一致，响应及时，可分区执行不可能同时满足。

举个例子：

一个分布式网路上，某一个节点有一组依赖数据A，当网络无延迟，无阻塞时，依赖于X的操作可正常进行。但网络无延迟阻塞在现实世界中是没法100%保证的，那么当网络异常时，必然会产生分布式系统的分区和孤岛，那当一个执行操作在A分区之外时，如果要保证P,即当系统发生分区时仍可运行，就需要在分布式系统中多个节点有X的备份数据，以应对分区情况。则这时候就需要在C,A之间做出选择。

假如选择C，即要保证数据在分布式网络中的一致性，那么就需要在X每次改动时，需要将全网节点的X数据同步刷新成最新的状态，那么在等待数据刷新完成之前，分布式系统是不可响应X的依赖操作的，即A的功能缺失

假如选择A，即要突出低延迟的实时响应。那么在响应的时候，可能全节点的X数据并没有同步到最新的状态，则会导致C的缺失。

上面看上去有些绕，那么你只要记住这句话，

CAP原理在分布式网络系统的应用讨论，其实就是讨论在允许网络发生故障的系统中，该选择一致性还是可靠性？

如果系统重视一致性，那么可以基于ACID原则做系统设计

即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）。

ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。

• Atomicity：每次操作是原子的，要么成功，要么不执行；

• Consistency：数据库的状态是一致的，无中间状态；

• Isolation：各种操作彼此互相不影响；

• Durability：状态的改变是持久的，不会失效

相应的有一个BASE原则，（Basic Availiability，Soft state，Eventually Consistency）则强调了可用性。

经典的共识算法设计

业内，针对节点异常的情况，会有两种分类

1.故障的，不响应的节点，成为非拜占庭错误

2.恶意响应的节点，称为非拜占庭错误

Paxos 最早的共识算法  非拜占庭算法的代表

Paxos有三种角色：

• proposer：提出一个提案，等待大家批准为结案。客户端担任该角色；

• acceptor：负责对提案进行投票。往往是服务端担任该角色；

• learner：被告知结案结果，并与之统一，不参与投票过程。即普通节点

系统运行由proposer驱动，当合法提案在一定时间内收到1/2以上投票后达成共识。