分布式

1.为什么分布式火

随着摩尔定律碰到瓶颈，越来越多的系统要依靠分布式集群架构来实现海量数据处理和可扩展计算能力。

2.分布式的核心问题

参考资料：https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/problem.html

2.1一致性问题

多个节点在协议（往往通过某种共识算法）保障下，试图使得它们对处理结果达成某种程度的一致。
要求;1.Termination，有限时间完成 2.Consensus 不同节点结果一致 3.Validity 合法性，决策的记过必须是其他进程提出的提案

带约束的一致性
首先明确：一致性约束和性能只能平衡，不能同时精确。就跟物理的测不准性质一样
强一致性：
顺序一致性（[Sequential Consistency]：保证局部的一致性，类比于java 的并发，某个线程的a before b
线性一致性（[Linearizability Consistency]：这个相当于保证了全局一致性，需要用全局的时钟或锁实现
弱一致性：weak consisitency，放款一致性要求，实现效率Eventual Consistency

2.2 共识算法

问题挑战：
把故障（不响应）的情况称为“非拜占庭错误”，恶意响应的情况称为“拜占庭错误”（对应节点为拜占庭节点）。

tip: 1： FLP 不可能性原理

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

不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法。

e.g.三个人在不同房间，进行投票（投票结果是 0 或者 1）。三个人彼此可以通过电话进行沟通，但经常会有人时不时地睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。如果可以重新投票，则类似情形每次在取得结果前发生：
FLP 原理实际上说明对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。

物理和数学研究确定了问题的极端情况，即边界的情形，但工程通过多次重复等方式，达到可以接受的的效果，就像物理的不确定性原理，粒子的位置和速度不能同时确定，但仍然能进行量子研究应用

tip 2：CAP原理

分布式计算系统不可能同时确保一致性（Consistency）、可用性（Availablity）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证
这里的分区容忍性（Partition）指：网络可能发生分区，即节点之间的通信不可保障。

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

好在大部分时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（大部分时候都是如此），要么牺牲掉可用性。
实际应用场景
既然 CAP 不可同时满足，则设计系统时候必然要弱化对某个特性的支持。

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

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

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

tip 3：Paxos和Raft

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。
Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统
参考资料：https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/paxos.html
重要概念，proposer：提出提案，acceptor：负责投票，learner：被告知提案结果

需要保证 safety：决议是proposer提出的，且无歧义和liveness：有限时间

当获取的acceptor支持超过一半时，即发送结果给所有人进行确认，因此当超过1/2的正常节点存在时，系统可以达成共识，如果在proposer提案时故障，则可通过超时机制，加重新新一轮提案加以解决。

需要两阶段提交

Why

在于只有一个阶段的话，在多提案+多接收者情况下，无法确认是否获得通过的提案是最终结果，可能还有后续的提案继续提交通过。
索引引入新的一个阶段，在proposer前一阶段拿到反馈后，判断这个提案是否被大多数接受，需要对其进行最终确认

how

准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。

prepare阶段：
proposer：发送提案和编号到acceptor试探是否获取多数接受者的支持
acceptor：保留接受到的提案的最大编号和接受的最大提案，时刻更新当前的最大提案号，不接受下雨最大提案号的提案（一般来说，算法当中，越是后提交的，即新的提案，编号越大，使用时间戳等方式）

commit：
proposer：如果收到大多数的回复，则可准备发送带有提案号的接收消息。如果收到的回复不带有新的提案，则说明锁定成功，使用自己的提案；如果收到的回复带有新的内容，则替换为编号更大的提案；如果没有收到足够多的请求，则再次发出请求
acceptor：接受消息后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新最大提案号

一旦多数接受了共同的提案值，则形成决议，成为最终确认的提案

Raft

是Paxos的简化实现。
包括三种角色：leader、candidate 和 follower，其基本过程为：

Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选为 leader；
同步 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记录；
注：此处 log 并非是指日志消息，而是各种事件的发生记录。

tip 2：拜占庭问题和算法

拜占庭将军（Byzantine Generals Problem）问题，是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。

对于拜占庭问题来说，假如节点总数为 N，叛变将军数为 F，则当N≥3F+1时，问题才有解，即 Byzantine Fault Tolerant (BFT) 算法。
最简单的
例如，N=3,F=1 时。
提案人不是叛变者，提案人发送一个提案出来，叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。

提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。
更一般的推到了解即可

新的解决思路

拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且要完成最终的一致性确认过程十分困难，容易受干扰。但是一旦确认，即为最终确认。

比特币的区块链网络在设计时提出了创新的 PoW（Proof of Work） 算法思路。一个是限制一段时间内整个网络中出现提案的个数（增加提案成本），另外一个是放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出很大的经济代价（付出超过系统一半的算力）。

后来的各种 PoX 系列算法，也都是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者