## FLP and CAP

分布式系统的核心问题：**一致性问题 共识问题**  
引起不一致的因素:  
- 节点间网络通信的不可靠,消息延迟,消息乱序,内容错误.
- 节点处理时间无法保证: 结果可能错误,或者节点宕机.

### FLP不可能原理

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


FLP 不可能原理告诉大家不必浪费时间去追求完美的共识方案，而要根据实际情况设计可行的工程方案。

那么，退一步讲，在付出一些代价的情况下，共识能做到多好？

回答这一问题的是另一个很出名的原理：CAP 原理。


### CAP 原理

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

- **一致性**：所有节点在同一时刻能够看到相同的数据。
- **可用性**：在有限时间内，任何非失败节点都能应答请求；
- **分区容忍性**：分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务。 


#### 一致性
  - 对于客户端来说，一致性指的是并发访问时更新过的数据如何获取的问题。
  - 从服务端来看，则是更新如何复制分布到整个系统，以保证数据最终一致。

规范来看，分布式系统达成一致的过程，应该满足：
- 可终止性（Termination）：一致的结果在有限时间内能完成；意味着可以保障提供服务（Liveness）。
- 约同性（Agreement）：不同节点最终完成决策的结果是相同的；
- 合法性（Validity）：决策的结果必须是某个节点提出的提案。

**CAP 原理认为，分布式系统最多只能保证三项特性中的两项特性。**

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

### CAP应用场景

既然 CAP 三种特性不可同时得到保障，则设计系统时候必然要弱化对某个特性的支持。

#### 弱化一致性

对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才最终更新成功，期间不保证一致性。

例如网站静态页面内容、实时性较弱的查询类数据库等，简单分布式同步协议如 Gossip，以及 CouchDB、Cassandra 数据库等，都为此设计。

#### 弱化可用性

对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。MongoDB、Redis、MapReduce 等为此设计。

Paxos、Raft 等共识算法，主要处理这种情况。在 Paxos 类算法中，可能存在着无法提供可用结果的情形，同时允许少数节点离线。


#### 弱化分区容忍性

现实中，网络分区出现概率较小，但很难完全避免。

两阶段的提交算法，某些关系型数据库以及 ZooKeeper 主要考虑了这种设计。

实践中，网络可以通过双通道等机制增强可靠性，实现高稳定的网络通信。


### 共识算法

针对如上不稳定的情况，把出现故障（Crash 或 Fail-stop，即不响应）但不会伪造信息的情况称为“非拜占庭错误（Non-Byzantine Fault）”或“故障错误（Crash Fault）”；伪造信息恶意响应的情况称为“拜占庭错误”（Byzantine Fault），对应节点为拜占庭节点。显然，后者场景中因为存在“捣乱者”更难达成共识。

共识算法:
- BFT类 针对拜占庭错误有: PBFT确定性算法、POW工作量证明的概率算法等.
- CFT类 针对非拜占庭错误有: PAXOS 算法 、Raft算法（容错较好,处理快,保证不超过一半节点故障）



#### 参考如下：
[常用共识算法总结（Paxos，Raft，PBFT，PoW，PoS，DPoS，Ripple）](https://segmentfault.com/a/1190000019947618)

[blockchain_guide](https://yeasy.gitbooks.io/blockchain_guide/04_distributed_system/acid.html)