分布式系统

分布式系统一致性要求

可终止性（ Termination）：一致的结果在有限时间内能完成；

共识性（ Consensus）：不同节点最终完成决策的结果应该相同；

合法性（ Validity）：决策的结果必须是其它进程提出的提案。

典型的强一致性算法通常有，顺序一致性（ Sequential Consistency）和线性一致性（ Linearizability Consistency）等，但性能很差，实现复杂。

于此相对的，大家发现很多系统对一致性要求其实并没有那么高，只需要在一定的条件下让系统可以达到最终一致性（ Eventual Consistency）就可以了，这种情形叫做弱一致性（ Weak Consistency）。

FLP 不可能原理：在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表，该论文后来获得了 Dijkstra 奖。

FLP 不可能原理实际上告诉人们，不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法。理解这一原理的一个不严谨的例子是：

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

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

CAP理论：分布式计算系统不可能同时确保一致性（ Consistency）、可用性（ Availablity）和分区容忍性（ Partition），设计中往往需要弱化对某个特性的保证。其中：

一致性（ Consistency）：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性；

可用性（ Availablity）：在有限时间内，任何非失败节点都能应答请求；

分区容忍性（ Partition）：网络可能发生分区，即节点之间的通信不可保障。

比较直观地理解，当网络可能出现分区时候，系统是无法同时保证一致性和可用性的。要么，节点收到请求后因为没有得到其他人的确认就不应答，要么节点只能应答非一致的结果。

好在大部分时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（大部分时候都是如此），要么牺牲掉可用性。

既然 CAP 不可同时满足，则设计系统时候必然要弱化对某个特性的支持。

弱化一致性：对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才更新成功，期间不保证一致性。例如网站静态页面内容、实时性较弱的查询类数据库等，CouchDB、Cassandra 等为此设计。

弱化可用性：对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。MongoDB、Redis 等为此设计。Paxos、Raft 等算法，主要处理这种情况。

弱化分区容忍性：现实中，网络分区出现概率减小，但较难避免。某些关系型数据库、ZooKeeper 即为此设计。实践中，网络通过双通道等机制增强可靠性，达到高稳定的网络通信。

ACID即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）。ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。

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

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

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

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

一个与之相对的原则是 BASE（ Basic Availiability，Soft state，Eventually Consistency），牺牲掉对一致性的约束（最终一致性），来换取一定的可用性

容错的上限：

(1）在部分同步（partially synchronous）的网路环境中（即网路延迟有一定的上限，但我们无法事先知道上限是多少），协议可以容忍最多1/3的拜占庭故障（Byzantine fault）。

(2）在异步（asynchronous）的网路环境中，具确定性质的协议无法容忍任何错误，但这篇论文并没有提及randomized algorithms在这种情况可以容忍最多1/3的拜占庭故障。

(3）在同步（synchronous）的网路环境中（即网路延迟有上限且上限是已知的），协议可以容忍100%的拜占庭故障，但当超过1/2的节点为恶意节点时，会有一些限制条件。

要注意的是，我们考虑的是"具认证特性的拜占庭模型（authenticated Byzantine）"，而不是"一般的拜占庭模型"；具认证特性指的是将如今已经过大量研究且成本低廉的公私钥加密机制应用在我们的演算法中。

最后更新于6年前