共识算法（分布式下的一致性算法)

概述

1. 解决的问题：分布式环境下的存储，如何保持各个节点上存储的数据一致。

2. 经典的问题：拜占庭将军问题
   拜占庭帝国想要进攻一个强大的敌人，为此派出了11支军队去包围这个敌人。
   这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。
   这11支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。
   他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。
   困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？

业务场景：

• 有故障节点，可能传输问题，导致意图未能准确的传达或者传达到了但是未能及时反馈回来
• 有叛军节点，可能发布错误的信号

3. 常见的共识算法：

• 局域网有限节点（私链）（考虑故障节点，不考虑叛军节点）：Paxos算法系列（Raft协议、Zab协议、PBFB协议），比如zk集群的业务场景，不需要考虑叛军节点

• 互联网无限可能节点（公链）(考虑叛军节点+故障节点)：Pow算法（比特币共识算法)、Pos算法（以太坊2.0计划引入的算法)、DPos算法（比如比特币的业务场景，有人想篡改交易，或者给自己造币）

Zab协议

达到的效果：可以保证在过半节点正常的情况下，所有的写入操作不会丢失。

Zab协议并不保证强一致性，也不是弱一致性，而是在一定限度内的强一致性。

1. 强一致性：要求在任意时间节点，所有的Node的数据都保持一致。
   优点：可以保证任意时间节点上，全部节点的数据保持一致。读取性能高，可以从任意节点获取最新的数据。

缺点：

• 容错性差：但凡有一个节点故障，为了保证所有节点的数据完全一致，则整个集群不可用
• 写的性能差：完成任意的写操作，需要全部的节点全部写入成功，那么这个写操作才算成功，如果有某个节点性能差，会导致整个集群的性能差，短板效应。
• 实现起来复杂：类似于分布式事务问题，既要保证所有节点写入成功后再反馈写入成功，还要保证某个节点故障之后，其它的所有节点都回撤之前的写操作。

2. 弱一致性：Eureka
   优点：读和写的性能都很高
   缺点：

• 可能丢失写入的数据（很多业务场景下，这个是不能容忍的)
• 在同一时间不同节点读取到的数据不一致(ABC三节点的集群中，A写入了数据，还未同步到BC节点，那么此时同时读取 AB节点，返回的数据不一致)

3. Zab的一致性：
   在过半节点正常的情况下

• 写的性能高，只要过半节点写入成功，则可以直接反馈客户端，写操作成功，不会因为个别慢节点，拉低集群的写的性能
• 保证写入过的数据，绝对不会丢失（因为在选举时，新leader的数据肯定包含全部写入成功的数据，否则它不会当选为leader)
• 任意时间节点，不同节点读取到的数据都是一样的，因为所有的读取命令都会转交到leader节点来返回数据（强一致性读模式下是这样的)

缺点：

• 读的性能不及强一致性算法，因为所有的读取命令都会转交到leader节点来返回数据
• 写的性能不如弱一致性算法，因为要等待过半节点都写入成功才反馈客户端写入成功
• 算法复杂
• 选举阶段不对外提供服务，直到新的leader产生为止

Zookeeper一致性的其它一些细节

1. zk的存储结构：内存树（状态机）+ 文件日志。

• 状态机就是存储变量的最终的值，提升每个节点读的性能。
• 文件日志记录了所有变量的过程值，一旦节点宕机，可以根据文件日志重构状态机，保证数据不会丢失。

2. zk通过zxid来保证写的顺序性，也就是用户发起 a1（比如 x=1）、a2（比如 x=2）、a3（比如x=3) 3个连续的操作，在做持久化的时候，可能是a3先持久化（提高并发写入的性能)，但是在运用到内存树时，必须保证zxid严格有序
   这种机制既保证并发写的速度，又保证了操作的严格有序性

3. zk的一致性依赖于客户端的实现，比如一个写入的请求如果没有过半节点完成写入操作，此时leader宕机，新leader不包含这条写入的消息，依赖客户端等待超时发起重试，来保证事务不会丢失。

4. zk的读取不保证所有节点的一致性，每个node都直接反馈读的请求，此时可能同一时间节点，不同Node读取到的数据不一致，但是读取的性能高，适用于大部分对一致性要求没有那么高的业务场景。

5. zk为了提升自己的短板，支持observer模式。提升读取的性能的同时，不降低写的性能，因为observer节点只参与读，不参与写和投票。适用于默认模式。

6. zk也支持通过配置支持弱一致性模式，配置：readonlymode.enable属性，默认是false，如果开启的话，节点处于异常状态，集群仍然可用，但是只能执行读的请求，不能写。

区块链概述

区块链1.0时代：比特币，作用就是去中心化的货币，无国界的货币，并且可以匿名性的洗钱
区块链2.0时代：代表以太坊，引入了智能合约的概念，发挥其 去中心化和不可篡改的特性，可以实现类似于 追溯、拍卖、投票等业务场景。

区块链技术的实用价值：
无国界虚拟货币：比如比特币

• 总量确定（2100万枚比特币），所以没有通货膨胀的风险。而法定货币都会通货膨胀
• 去中心化，不受任何政府管制
• 交易的成本很低，除了记账算力的开销，没有其它的中介费（因为记账是耗费算力的，所以有手续费的概念，理论上在竞争不强的情况下，肯定比 支付宝、微信的费用要低）
• 匿名性，很好的保护隐私（支付宝、微信等转账都可以被查的)，最重要的实用价值：可以洗钱

模拟一个拍卖（盲拍）的业务场景（发布一个智能合约）：
https://solidity.readthedocs.io/en/latest/solidity-by-example.html#simple-open-auction

普通拍卖可能存在的问题：

1. 可能存在不公平竞争，有人通过特殊手段，知道或者可以预料当前的最高报价，那么只需要付出稍微多一点的资金就可以获取到竞拍品，对商家不利
2. 竞标失败商家可能不退款，或者卷款跑路
3. 匿名性得不到保证，比如某珍宝的拍卖，竞拍者的信息在竞拍过程中被暴露
4. 举办竞拍活动存在的费用（场地费用、保安费用等等）

商家A对一件商品公开自己要拍卖，智能合约在规定的时间会开始接收竞拍（参与竞拍的人需要支付保证金（以太币）），在竞拍结束之后，价格最高的人会完成支付，其它的买家的保证金会全额退回。
然后成功竞拍者可以线下去找卖家，证明自己的身份，然后获得竞拍品

优点：

1. 商家的智能合约对外是可见的，所以竞拍规则是固定的，不存在围标，或者不正当竞争的情况，即使是商家也不知道当前的最高出价是多少
2. 竞标者是无法撤回自己的投标，因为触发保证金的赎回，只有等到时间点到了，流标的资金才会退回。而且因为智能合约是公开的，所以竞标者也不用担心，万一流标，商家卷款跑路，因为程序是设定好的
3. 整个过程是线上匿名进行的，非常安全。不仅没人知道竞拍成功的得主是谁，竞拍成功者也不知道与他竞拍的人的信息。
4. 几乎没有费用（但是每笔投标都有手续费，因为记账的费用）

Pow算法（比特币共识算法)（匿名性 + 不可篡改)

工作量证明（ PoW ）通过计算一个数值（ nonce ），使得拼揍上交易数据后内容的 Hash 值满足规定的上限。在节点成功找到满足的Hash值之后，会马上对全网进行广播打包区块，网络的节点收到广播打包区块，会立刻对其进行验证

举个例子，给定的一个基本的字符串”Hello, world!”，我们给出的工作量要求是，可以在这个字符串后面添加一个叫做nonce的整数值，对变更后（添加nonce)的字符串进行SHA256哈希运算，
如果得到的哈希结果（以16进制的形式表示）是以”0000”开头的，则验证通过。为了达到这个工作量证明的目标。我们需要不停的递增nonce值，对得到的新字符串进行SHA256哈希运算。
按照这个规则，我们需要经过4251次计算才能找到恰好前4位为0的哈希散列。计算完之后，然后广播到临近的节点，临近的节点会先验算交易是否合法（金额是否异常），再验证hash值是否满足要求，都满足的话，就会把这个数据块添加到自己的账本中。

"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

优点：

• 迄今为止，被时间验证的最久最可靠的共识算法
• 计算很复杂，但是验证很容易
• 因为hash运算随机性，所以每个计算机都有机会计算到满足要求的值，通过数学难题，解决了被操作的可能性，从而去中心化

缺点：

• 太费电了
• 浪费了大量的计算机算力（CPU、内存、显卡等硬件）
• 大的矿池有能力垄断
• 高通等公司研发了适合挖矿运算的硬件，让计算的效率提升，提升了算力垄断的概率
• 每个区块的生成速度很慢，一般平均12分钟出一个区块，最快12分钟，交易才被确认，交易的速度比较慢
• 一般认为7块区块之后的交易才是非常安全的交易，效率很低

Pos算法（以太坊2.0计划引入的算法)

计算难度值会因为 股东持有的 币龄而降低，为挖矿无形之中提升了壁垒，股东更容易算出结果值（难度更低），从而避免过度的算力竞争，节省电力，提升系统的稳定性。
因为从人性的角度，股东更不愿意让不安全的现象发生（比如攻击主链)，因为会造成信用降低，从而自己的矿币贬值。让股东拥有更多的记账权，让主链更安全。

扩展

扩展可以参考我之前写过的zab专栏博客
https://www.jianshu.com/nb/32551354