分布式协议与算法实战
2022-11-06 20:58:22 0 举报AI智能生成
分布式协议与算法实战
作者其他创作
大纲/内容
分布式协议和算法是决定分布式系统如何运行的核心规则和关键步骤
如果想正在搞懂分布式技术，开发出一个分布式系统，最先需要掌握的就是这部分知识
分布式算法是分布式技术中的核心
分布式系统里，最重要的事情，就是如何选择或者设计适合的算法，解决一致性和可用性相关的问题
InfluxDB企业版的护城河就是以分布式算法为核心的分布式集群能力
现阶段，掌握分布式算法也是面试架构师、技术专家等高端岗位的敲门砖
除了算法本身抽象，不容易理解之外，即使是非常经典的论文，也存在在一些关键细节上没有讲清楚的情况。
信息时代资料丰富，但质量参差不齐，甚至有错误。
很多资料是为了讲解理论而讲解理论，无法站在“用”的角度，将理论和实战结合。
分布式算法难学的原因
不仅要理解常用算法的原理、特点和局限，还要能根据场景特点选择适合的分布式算法
理论篇，搞懂分布式架构设计核心且具有“实践指导性”的基础理论，会涉及典型的分布式问题，以及如何认识分布式系统中相互矛盾的特性，在实战中根据场景特点选择适合的分布式算法。
协议和算法篇，掌握它们的原理、特点、适用场景和常见误区等。
实战篇，将所学知识落地，掌握分布式基础理论和分布式算法在工程实践中的应用。
如何学习分布式协议和算法
分布式协议与算法的重要性想成为分布式高手？那就先把协议和算法烂熟于心吧
00丨开篇词
如何统一大家的作战计划？
有叛将的情况下，如何达成共识，制定统一的作战计划呢？
这个案例是拜占庭问题的一个简化版，苏秦面临的就是典型的共识难题，就是在可能有误导信息的情况下，采用合适的通讯机制，让多个将军达成共识，制定一致性的作战计划。
案例解析-苏秦的困境
假设 苏秦带领齐楚燕联军攻打秦国，按照少数服从多数的原则决定是进攻还是撤退
按照少数服从多数原则，齐也会进攻
情况一：齐根据侦查情况决定撤退，会给楚和燕发送撤退的消息楚和燕根据侦查信息，决定进攻
比如齐向楚、燕分别发送了“撤退”的消息，燕向齐和楚发送了“进攻”的消息。撤退：进攻 =1:1，无论楚投进攻还是撤退，都会成为 2:1，这个时候还是会形成一个一致性的作战方案。
但是，如果楚是叛徒在暗中配合秦国，让信使向齐发送了“撤退”，向燕发送了“进攻”，那么：燕看到的是，撤退：进攻 =1:2齐看到的是，撤退：进攻 =2:1按照少数服从多数的原则，就会出现燕就会单独进攻的场景
情况二：如果有人暗通秦国，就会出现作战计划不一致的问题。
二忠一叛的难题
三位将军分别拨出一部分军队由苏秦率领，苏秦参与作战计划讨论及执行，这样就增加了忠诚将军的数量
设定默认策略，如果没有收到命令，就执行约定的默认命令，撤退或者进攻，同事约定好流程，比如需要进行两次作战信息协商
1.先发送作战命令的将军作为指挥官，其余将军作为副官2.指挥官将作战命令发送给每位副官3.每位副官，将从指挥官处收到的命令作为其作战指令，如果没有收到，则执行默认指令，如撤退
第一轮协商：
1.除了第一轮的指挥官，其余将军分别作为指挥官，向另外两位将军（不包含第一轮的指挥官）发送作战信息2.这三位将军按照少数服从多数原则，执行收到的命令
第二轮协商：
第一轮协商：齐楚燕收到的指令都是进攻
第二轮协商：齐楚燕分别作为指挥官向另外两位发送指令。齐燕发送的是进攻，楚作为叛将，发送的是撤退指令
结论：按照少数服从多数原则，齐燕收到了一次撤退，收到了两次进攻指令，一起执行进攻
假设忠诚将军苏秦发起作战指令-进攻
案例推演一：忠诚将军先发起作战指令
第一轮协商：楚向苏秦发送进攻指令，向齐燕发送撤退指令
第二轮协商：苏秦和齐楚分别向对方发送作战命令，齐楚发出撤退的指令，苏秦发出进攻指令
结论：苏秦、齐、燕收到的是 撤退&撤退&进攻，按照原则会执行撤退
案例推演二：叛将先发起作战指令
总结：如果叛将人数为m，将军人数不能少于3m+1，那么拜占庭将军问题就能解决了。也就是说，如果有n位将军，最多能容忍 (n-1)/3 位叛将
外框
解决办法一：口信消息型拜占庭问题之解
苏秦还可以通过签名的方式，在不增加将军人数的情况下，解决二忠一叛的难题
通过印章、虎符等信物实现特性：忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现；任何人都能验证将军签名的真伪。
如果忠诚的将军，比如齐先发起作战信息协商，一旦叛将楚修改或伪造收到的作战信息，那么燕在接收到楚的作战信息的时候，会发现齐的作战信息被修改，楚已叛变
如果叛变将军楚先发送误导的作战信息，那么齐和燕将发现楚发送的作战信息是不一致的，知道楚已经叛变。这个时候，他们可以先处理叛将，然后再重新协商作战计划。
总结：通过签名机制约束叛将的叛变行为，任何叛变行为都会被发现，也就会实现无论有多少忠诚的将军和多少叛将，忠诚的将军们总能达成一致的作战计划。
解决办法二：签名消息型拜占庭问题之解
二忠一叛问题的解法
01丨拜占庭将军问题：有叛徒的情况下，如何才能达成共识？
作者负责自研 InfluxDB 系统的项目，遇到的第一个问题就是，如何为单机开源版的 InfluxDB 设计分区容错一致性模型。 因为 InfluxDB 有 META 和 DATA 两个节点，它们的功能和数据特点不同，所以需要考虑这两个逻辑单元的特点，分别设计分区容错一致性模型。
解法：CAP 理论
背景问题
CAP 理论是一个很好的思考框架，它对分布式系统的特性做了高度抽象。抽象为一致性、可用性和分区容错性，并对特性间的冲突（也就是 CAP 不可能三角）做了总结。
一致性是指，客户端的每次读操作，不管访问哪个节点，要么读取到的都是同一份最新数据，要么读取失败
一致性可以看做是分布式系统对访问本系统的客户端的一种承诺：不管你访问哪个节点，要么都读取失败，要么给你返回的都是绝对一致的问题
可以看出，一致性强调的是数据正确性，各个节点之间的数据一致性，而不是完整性。（完整性强调的是所有数据的状态都是正确的）
一致性（Consistency）
可用性是指，不管客户端访问哪个节点，都能得到响应数据，但不保证是同一份最新数据
可用性可以看做是分布式系统对访问本系统客户端的另一种承诺：我一定会给你返回数据，不会不相应你的请求，但是不保证每个节点的数据都是最新的
可以看出，可用性强调的是服务可用，但不保证数据一致性
可用性（Availability）
分区容错性是指，当任意数量的消息丢失或延迟到达时，系统仍会继续提供服务，不会挂掉。
分区容错性可以看做分布式系统对访问本系统客户端的一种承诺：不管我内部出现什么问题，我会一直运行，提供服务
可以看出，分区容错性强调的是对分区故障的容错能力，系统不挂掉
分区容错性（Partition Tolerance）
CAP不可能三角说的是对于一个分布式系统而言，一致性（Consistency）、可用性（Availability）、分区容错性（PartitionTolerance）3个指标不可兼得，只能在3个指标中选择2个。
CAP不可能三角
CAP理论
只要有网络交互就一定会有延迟和数据丢失，我们不仅要接受这种状况，还必须保证系统不能挂掉，也就是说，节点间的分区故障是必然会发生的。因此，分区容错性（P）是我们一定要保证的。现在我们只剩下一致性（C）和可用性（A）可以进行选择了：要么选择一致性，保证数据的绝对一致，要么选择可用性，保证服务可用。
选择一致性（C）:CP应用，如果因为消息丢失、网络超时等原因发生了网络分区，部分节点无法保证特定的数据是最新的，此时，集群收到客户端的写请求后，因为无法保证集群所有节点数据都是最新的，系统将会返回写入失败，也就是集群会拒绝写入新数据，集群可用性受损。
选择可用性（A）：AP应用，集群会一直接受客户端的查询和写入请求，但是此时不能保证一致性，查询特定信息时，一些节点可能无法返回最新信息，只能返回自己的相对最新信息，一致性受损。
说明：因为网络分区一定存在，所以我们才需要再CA之间进行选择，如果网络分区不存在，或者不需要保证分区一致性时，CA就能够同时进行保证
如何使用CAP理论
首先作为分布式系统，分区容错性是一定要保证的，不能因为节点之间出现了分区故障，导致整个系统不可用的情况
META节点存储的是系统运行的关键元信息，因此必须保证一致性，这样才能避免由于各节点元信息不一致，导致数据不一致或者影响系统运行，因此 META节点选择CP架构
DATE节点保存的是具体的时序数据信息，不属于系统运行的关键信息，同时服务访问频繁，水平拓展、性能、可用性是关键指标，因此选择AP架构
Raft算法是一个强领导者模型，所有请求都是在领导者节点上处理，整个集群的性能等于领导者的单节点性能，这样就会造成集群性能低下，无法支撑海量的时序数据
Raft算法受限于强领导者模型，只能拓展读性能，写性能无法提升
Raft算法一切以领导者为准的日志负责特性，可能会导致DATA节点丢失数据
该案例如果直接采用Raft等算法，基于CAP理论来分析Raft算法
背景问题解决方案
采用CP架构的分布式系统，一旦出现网络分区等问题时，就会影响用户的体验和业务可用性，因为为了防止出现数据不一致的情况，集群将拒绝写入，典型的如Zookeeper、Etcd、HBase
采用AP架构的分布式系统，实现了服务的高可用，但是在出现分区故障后，写入的数据不能实现一致性，导致读操作时，可能会读取不到最新数据。典型的如Cassandra、DynamoDB
总结
02丨CAP理论：分布式系统的PH试纸，用它来测酸碱度
ACID（原子性、一致性、隔离性、持久性）是对事物特性的抽象与总结，如果系统实现了操作的ACID特性，那么就实现了事务。那么如何在分布式系统上实现ACID特性呢？
背景故事：苏秦想要协调赵魏韩一起发起对秦的军事行动，苏秦面临的问题是，如何高效协同赵、魏、韩一起行动，并且保证当有一方不方便行动时，取消整个计划。
苏秦面对的这个问题，就是典型的分布式事务恩替，赵魏韩一起攻打秦国，这三个操作一起组成一个分布式事务，要么全部执行，要么全部不执行
综述
二阶段提交，就是通过二阶段的协商来完成一个分布式事务的提交操作
结合案例来分析，首先，苏秦（可理解为客户端）发消息给赵，赵收到消息后作为协调者身份，由赵联系魏韩
第一步，赵分别向魏、韩发送消息：“明天攻打秦国，方便吗？”
第二步，赵、魏、韩，分别评估明天能否去攻打秦国，如果能，就预留时间并锁定，不再安排其他军事活动。
第三步，赵得到全部的回复结果（包括他自己的评估结果），都是 YES。
赵发起二阶段提交后，先进入第一阶段：提交请求阶段
赵收到所有回复之后，进入第二阶段：提交执行阶段
注意：在第一个阶段，每个参与者投票表决事务是放弃还是提交。一旦参与者投票要求提交事务，那么就不允许放弃事务。也就是说，在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己那一部分，即使参与者出现故障或者中途被替换掉。这个特性，是我们需要在代码实现时保障的
二阶段是反可伸缩性的，因为在第一阶段，需要预留资源，也就是会锁定资源，其他人不能操作，因此在大规模场景下，并不是最优解。
由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。
二阶段的问题：
因此2PC算法可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者反馈的情况决定各参与者是否要提交操作还是中止操作。两个阶段是指：第一阶段：准备阶段（投票阶段）和第二阶段：提交阶段（执行阶段）
准备阶段事务协调者（事务管理器）给每个参与者（资源管理器）发送Prepare消息，每个参与者要么直接返回失败（如权限验证失败），要么在本地执行事务，写本地redo和undo日志，但是不提交事务，达到一种“万事俱备，只欠东风”的状态。可以将准备阶段进一步分为以下三个步骤：- 协调者节点向所有参与者节点询问是否可以执行提交操作，并开始等待各参与者的响应- 参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。（注意：若成功这里其实每个参与者已经执行了事务操作）- 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个”同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个”中止”消息。
提交阶段如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚（Rollback）消息，否则发送提交（Commit）消息；参与者根据协调者的指令执行提交或者回滚操作，释放事物处理过程中的锁资源。分两种情况来讨论提交阶段：- 所有参与节点都返回成功 1. 协调者向所有参与者节点发出“正式提交”请求 2. 参与者节点正式完成提交操作，并释放整个事物操作期间的锁资源 3. 参与者节点向协调者节点发送“完成”消息 4. 协调者节点收到所有参与者节点反馈的“完成”消息后，事物完成- 存在参与节点返回中止超时 1. 协调者节点向所有参与者节点发出”回滚操作(rollback)”的请求 2. 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源 3. 参与者节点向协调者节点发送”回滚完成”消息 4. 协调者节点受到所有参与者节点反馈的”回滚完成”消息后，取消事务
补充-系统的描述：
二阶段提交协议
TCC的理论基础是BASE理论，用于解决二阶段的性能问题
TCC 是 Try（预留）、Confirm（确认）、Cancel（撤销） 3 个操作的简称，它包含了预留、确认或撤销这 2 个阶段。
第一步，苏秦分别发送消息通知赵、魏、韩，让他们预留明天的时间和相关资源。然后苏秦实现确认操作（明天攻打秦国），和撤销操作（取消明天攻打秦国）。
第二步，苏秦收到赵、魏、韩的预留答复，都是OK。
预留阶段
第一步，苏秦执行确认操作，通知赵、魏、韩明天攻打秦国。
第二步，收到确认操作的响应，完成分布式事务。
如果预留阶段执行出错，那么就进入撤销阶段
确认阶段
第一步，苏秦执行撤销操作，通知赵、魏、韩取消明天攻打秦国的计划。
第二步，收到撤销操作的响应。
撤销阶段
TCC本质上是补偿事务，它的核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作（也就是撤销操作）
TCC是一个业务层面的协议，会和业务代码耦合在一起，需要在业务代码中编码实现，为了实现一致性，确认操作和撤销操作必须是幂等的（这两个操作可能会失败重试）
TCC不依赖数据库的事务能力，在业务中实现分布式事务能力，减轻了DB压力，但是对代码侵入性更强，实现复杂度也更高
TCC（Try-Confirm-Cancel）事务
二阶段提交协议，不仅仅是协议，也是一种非常经典的思想。二阶段提交在达成提交操作共识的算法中应用广泛，比如XA协议、TCC、Paxos、Raft等。
Paxos、Raft等强一致性算法，也采用了二阶段提交操作，在“提交请求阶段”，只要大多数节点确认就可以，而具有ACID特性的事务，则要求全部节点确认可以。所以可以将具有ACID特性的操作，理解为最强的一致性。
03丨ACID理论：CAP的酸，追求一致性
如果在分布式系统中要实现强一致性，就必然会影响可用性
集群的可用性是每个节点的可用性乘积，假设一个三节点集群，每个节点可用性为99.9%，那么整个集群可用性为99.7%，也就是一个月有129.6分钟不可用。这将是非常严重的问题，解决此类问题的关键在于，根据实际情况，尽可能采用AP模型
BASE理论是CAP理论中的AP的延伸，是对互联网大规模分布式系统的实践总结，强调可用性
基本可用是指分布式系统出现不可预知的故障时，允许损失部分功能的可用性，保障核心功能的可用性。是对分布式系统完全可用和完全不可用的一种折中
比如12306在不同的时间出售不同地区的票，将访问请求错开
如果可能预估流量，可以将多余的流量存储与队列中，让系统根据实际消费能力从队列中消费数据
流量削峰填谷
对用户的请求不是不处理，而是先缓存起来，慢慢处理，异步的给到用户处理结果，对用户来说，相应延迟了，对系统来说，能处理的请求更多了
延迟响应
在超出系统负载的大流量过来后，我们可以牺牲系统非核心能力，保障核心能力可用。比如使用小图片替代原始图片，降低日志级别，非核心接口功能降级
服务降级
如果使用了以上一些手段还是无法应对大流量，那么可以采用过载保护，根据一定的规则或者随机丢弃一些请求，直接返回上游错误。或者是将多余的请求存储与队列中，队列满了就清空。
过载保护
注意：基本可用在本质上是一种妥协，也就是在出现节点故障或系统过载的时候，通过牺牲非核心功能的可用性，保障核心功能的稳定运行
Basically Available(基本可用)
软状态是指允许系统存在中间状态，中间状态不会影响系统的整体可用性。
分布式存储中一般一份数据会有多个副本，允许不同节点间副本同步的延时就是软状态的体现。
Soft state（软状态）
最终一致性是说，分布式系统中所有的数据副本在经过一段时间同步后，最终能够达到一个一致的状态
互联网中绝大多数的系统都采用最终一致性，只有少数无法使用最终一致性或者一些关键的元数据信息，需要采用强一致性
分布式系统中的强一致性是一种不存在延迟的一致性
以最新写入的数据为准，比如AP模型的KV存储就采用这种方式
以第一次写入数据为准，就是说如果不希望存储的数据被更改，就以第一次为准
实现最终一致性以什么数据为准
在写入数据时，如果某个节点写入失败，就缓存起来通过自动重试等方式进行重新写入，这种方式能够更快的达到最终一致性。
比如Cassandra的Hinted Handoff实现。具体来说，Cassandra集群的节点之间远程写数据的时候，如果写失败就将数据缓存下来，然后定时重传，修复数据的不一致性。
写时修复
在写入数据时，不关心是否成功，在读取数据时，检测数据是否一致，如果不一致则进行修复
比如读取的时候，读取多个节点的数据进行比对，依照一定的规则，比如以超过半数的数据值为准的办法，来决定返回的值。
比如 Cassandra 的 Read Repair 模式下，读时候发现数据不一致的时候会自动修复。
读时修复
同步异步的任务比对所有节点的数据一致性，如果不一致则进行修复
异步修复
实践总结：推荐写时修复+异步修复，确保实现最终一致性。读时修复，需要读取多个节点值并进行比较，性能较差，不推荐
实现最终一致性的方式
Eventually consistent（最终一致性）
以自研InfluxDB系统中DATA节点的集群实现为例，来看如何使用BASE理论
DATA节点的核心功能是读和写，所以基本可用是指读和写的基本可用。可以通过分片和多副本，实现读和写的基本可用。也就是说，将同一业务的数据先分片，然后再以多份副本的形式分布在不同的节点上。
通过写时修复和异步修复实现最终一致性
还实现自定义写一致性级别，支持All、Quorum、One、Any 4种写一致性级别，用户在写数据的时候，可以根据业务数据的特点，设置不同的写一致性级别
BASE理论的工程实践
04丨BASE理论：CAP的碱，追求可用性
01丨理论篇
提议者（Proposer）、接受者（Acceptor）、学习者（Learner）
提议一个值，用于投票表决
在集群中，收到客户端请求的节点才是提议者
提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商
提议者（Proposer）
对提议者的提议值进行投票，并存储接受的值
在集群中， 所有的节点都在扮演接受者的角色，参与共识协商，并接受和存储数据
接受者代表投票协商和存储数据，对提议值进行投票，并接受达成的共识，存储保存
接受者（Acceptor）
接受投票结果通知、接受达成共识的值并保存，不参与投票过程
在集群中，学习者一般是数据备份节点，被动接收数据
学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存
学习者（Learner）
Base Paxos 三种角色
整个共识协商分成两个阶段，假设，客户端1提案编号为1，客户端2提案编号为5，节点 A、B先收到客户端1的准备请求，节点C先收到客户端2的准备请求
如何达成共识
首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求注意：在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了
由于之前没有通过任何提案，所以节点A、B将返回一个“尚无提案”的响应。也就是说节点A和B在告诉提议者，我之前没有通过任何提案，并承诺以后不再响应提案编号小于等于1的准备请求，不会通过编号小于1的提案。
节点C也是如此，它将返回一个“尚无提案”的响应，并承诺以后不再响应提案编号小于等于5的准备请求，不会通过编号小于5的提案。
当节点A、B收到提案编号为5的准备请求，和节点C收到提案编号为1的准备请求的时候
当节点A、B收到提案编号为5的准备请求的时候，因为提案编号5大于它们之前响应的准备请求的提案编号1，而且两个节点都没有通过任何提案，所以它将返回一个“尚无提案”的响应，并承诺以后不再响应提案编号小于等于5的准备请求，不会通过编号小于5的提案。
当节点C收到提案编号为1的准备请求的时候，由于提案编号1小于它之前响应的准备请求的提案编号5，所以丢弃该准备请求，不做响应。
准备（Prepare）阶段
首先客户端1、2在收到大多数节点的准备响应之后，会分别发送接受请求
三个节点收到 2 个客户端的接受请求时
核心：本质上而言，提案编号的大小代表着优先级，你可以这么理解，根据提案编号的大小，接受者保证三个承诺，具体来说：如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。
接受（Accept）阶段
Base Paxos
Multi-Paxos是一种思想，而不是算法，是指基于Multi-Paxos算法思想，通过多个Base-Paxos实例实现一系列值的共识算法（比如Raft）
如果多个提议者同时提交提案，可能会出现提案冲突，导致需要多次协商
两轮RPC通信（准备阶段和提交阶段）往返消息内容多、性能较差、耗时高
如果我们仅仅通过多次执行Base-Paxos算法操作，来实现一系列值的共识，会存在两个问题
原始Paxos算法中并没有说明如何选举领导者，这需要实现Paxos算法的自行实现领导者选举
优化Base-Paxos算法执行：如果领导者是稳定的，那么说明领导中的指令序列是完整且最新的，那么可以省略准备阶段，直接进入提交阶段
领导者（Leader）
首先通过主节点，实现了领导者（Leader）节点的特性，主节点作为唯一的提议者，这样就不会存在多个提议者，解决了提议冲突的问题
然后，主节点通过执行Base-Paxos算法来进行投票选举产生，并且只运行过程中，主节点会通过不断续租的方式来延长租期
其次，Chubby实现了 当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段
最后，Chubby实现了成员变更，保证节点变更时，集群的平稳运行
补充：Chubby为了实现强一致性，度操作也在主节点进行
Chubby的Multi-Paxos实现
Multi-Paxos
Paxos算法
Raft算法数据Multi-Paxos算法，在Multi-Paxos算法的思想基础上，做了一些简化和限制
Raft算法现在是分布式系统开发首选的共识算法
Raft算法的本质：Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致
蛮不讲理的霸道总裁，一切以我为准。
职责1：处理写请求
职责2：日志复制管理
职责3：发送心跳消息，维护领导者地位
Raft算法是强领导者模型，一切以领导者为准，集群中只能有一个领导者
就是普通群众，默默接收和处理来自领导者的消息，当等待领导者心跳消息超时的时候，就主动站出来，推举自己作为候选人
跟随者（Follower）
候选人将向其他牙节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果获得大多数选票，就晋升为领导者
候选人（Candidate）
Raft算法成员
在初始状态下，集群中所有的节点都是跟随者的状态，Raft算法实现了随机超时的时间特性，也就是说，每个节点等待领导者心跳信息的超时时间间隔具有随机性。
当某个超时时间最短的节点（节点A）到达超时时间后，A节点会增加自己的任期编号，推举自己为候选人，自己先给自己投一票，然后向其他节点发送请求投票的RPC请求，要求其他节点发起投票推举自己喂领导者
其他节点收到候选人A节点的请求投票RPC消息，在编号为1的任期内，还没有进行过投票，那么他就会把选票投给A节点，并增加自己的任期编号注意：每个节点在每个任期呢，只会投一票
如果候选人A节点在选举超时时间内赢得了大多数选票，那么就会成为本届任期内的领导者
当节点A成为领导者后，A将会周期性的发送心跳消息，通知其他服务器领导者存在，防止其他很随着发起新的选举
Raft算法领导者选举过程
在Raft算法中，服务器节点之间通过RPC进行通信
请求投票（RequestVote）RPC由候选人在选举期间发起，通知各节点进行投票
日志复制（AppendEntries）RPC由领导者发起，用来复制日志和提供心跳消息
节点间如何通信
Raft算法中，领导者是有任期的，每个任期由单调递增的数字标识。任期编号会随着选举的不断进行而递增
在跟随者等待领导者心跳消息超时后，推举自己喂候选人，会增加自己的任期编号
如果一个节点，发现自己的人气编号比其他节点小，那么他会自动更新自己的任期编号到较大值
如果一个候选人或者领导者发现自己的编号比别的节点小，会把自己恢复为跟随者，并更新任期编号
如果一个节点接收到一个包含较小任期编号值的请求，那么他会直接拒绝这个请求
什么是任期
领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制RPC消息），通知大家我是领导者，阻止跟随者发起新的选举。
如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。
在一次选举中，赢得大多数选票的候选人，将晋升为领导者。
在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。
在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。
当任期编号相同时，日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。
领导者选举有哪些规则
Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况。
随机超时时间：跟随者等待领导者心跳信息超时的时间间隔，是随机的当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是说，等待选举超时的时间间隔，是随机的。
如何理解随机超时时间
Raft算法领导者选举过程的细节
领导者选举
Raft中日志是由多条日志项（Log entry）组成的
Raft 算法的数据副本是以日志的形式存在的，领导者接收到来自客户端的写请求后，处理写请求的过程就是一个复制和提交日志项的过程
日志项是一种数据格式，主要包含用户指定的数据（也就是指令Command），以及一些附加信息，比如索引值（Log index）、任期编号（Term）
指令：一条由客户端请求指定的、状态机需要执行的指令。也就是客户端指定的数据。
索引值：日志项对应的整数索引值，用来标识日志项的，是一个连续的、单调递增的整数序列
任期编号：创建这条日志项的领导者的任期编号
什么是日志
可以把日志复制理解成一个优化后的二阶段提交，减少一半的往返消息，也就是降低了一半的消息延迟
首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC消息，将日志项复制到集群其他节点上
紧接着，如果领导者收到大多数的“复制成功”响应后，领导者将日志项提交到自己的状态机，并返回成功给客户端。如果领导者没有收到大多数的复制成功响应，那么将返回错误给客户端
注意：第2步骤中，领导者将日志提交到自己的状态机后，并没有通知跟随者提交日志。这是Raft算法的一个优化，领导者不直接发送消息通知其他节点提交日志项。因为领导者的日志复制RPC消息或者心跳消息中，包含了当前最大的，将会被提交的日志项索引值。所以通过消息复制RPC消息或者心跳消息，跟随者就能知道领导者日志提交的位置信息
因此，当其他节点接受领导者心跳消息或者新的日志复制RPC消息后，会将这条日志项提交到他的状态机。这个优化，减少了一次RPC请求，降低了客户端处理的时延，将二阶段优化为一阶段提交，降低一半的消息延迟。
接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。
领导者将执行的结果返回给客户端。
当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中。
如何复制日志
在Raft算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft是通过以领导者的日志为准，来实现各节点日志的一致的。具体有2个步骤：
首先，领导者通过日志复制RPC的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。
然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。
过程演示：
领导者通过日志复制RPC消息，发送当前最新日志项到跟随者（为了演示方便，假设当前需要复制的日志项是最新的），这个消息的PrevLogEntry值为7，PrevLogTerm值为4。
如果跟随者在它的日志中，找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，也就是说它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项，并返回失败信息给领导者。
这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，这个消息的PrevLogEntry值为6，PrevLogTerm值为3。
如果跟随者在它的日志中，找到了PrevLogEntry值为6、PrevLogTerm值为3的日志项，那么日志复制RPC返回成功，这样一来，领导者就知道在PrevLogEntry值为6、PrevLogTerm值为3的位置，跟随者的日志项与自己相同。
领导者通过日志复制RPC，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。
如何实现日志一致
日志复制
Raft采用单节点变更方式，来确保集群节点变更时不出现脑裂等问题
在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。
在启动集群时，配置是固定的，不存在成员变更，在这种情况下，Raft 的领导者选举能保证只有一个领导者。
成员变更的问题
单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群
第一步，领导者（节点 A）向新节点（节点 D）同步数据；
第一步，领导者（节点 A）向新节点（节点 E）同步数据；
在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。 也就是说，不会同时存在旧配置和新配置 2个“大多数”
不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节点，新旧配置的“大多数”都会存在重叠
过程推演
通过单节点变更解决成员变更的问题
成员变更
Raft算法
如果我们通过 Raft 算法实现了 KV 存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接入性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系统过载和服务不可用。系统瓶颈在领导者
Hash算法局限性：如果我们采用多集群，通过Proxy层代理，将不同的key通过Hash算法路由到不同的集群。缺点在于，如果集群数量发生变化，大量的key需要重新映射，需要搬迁的数据量太大，成本太高
通过哈希算法，每个 key 都可以寻址到对应的服务器，比如，查询 key 是 key-01，计算公式为 hash(key-01) % 3 ，经过计算寻址到了编号为 1 的服务器节点 A
如果服务器数量发生变化，基于新的服务器数量来执行hash算法的时候，就会出现寻址失败的情况，Proxy就会无法找到之前的服务器节点。
假如 3 个节点不能满足业务需要了，这时我们增加了一个节点，节点的数量从3 变化为 4，那么之前的 hash(key-01) % 3 = 1，就变成了 hash(key-01) % 4 = X，因为取模运算发生了变化，所以这个 X 大概率不是 1（可能 X 为 2），这时你再查询，就会找不到数据了，因为 key-01 对应的数据，存储在节点 A 上，而不是节点 B
同样的道理，如果我们需要下线 1 个服务器节点（也就是缩容），也会存在类似的可能查询不到数据的问题。
而解决这个问题的办法，在于我们要迁移数据，基于新的计算公式 hash(key-01) % 4 ，来重新对数据和节点做映射。需要你注意的是，数据的迁移成本是非常高的。例如，对于 1000 万 key 的 3 节点 KV 存储，如果我们增加 1 个节点，变为 4 节点集群，则需要迁移 75% 的数据。
使用哈希算法的问题
一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算。即一致哈希算法，将整个哈希值空间组织成一个虚拟的圆环，也就是哈希环：
哈希环的空间是按顺时针方向组织的，圆环的正上方的点代表 0，0点右侧的第一个点代表 1，以此类推，2、3、4、5、6……直到 2^32-1，也就是说 0 点左侧的第一个点代表 2^32-1。
在一致哈希中，可以通过执行哈希算法，将节点映射到哈希环上，每个节点就能确定其在哈希环上的位置了：
当需要对指定 key 的值进行读写的时候，可以通过下面 2 步进行寻址
首先，将 key 作为参数执行 c-hash() 计算哈希值，并确定此 key 在环上的位置；
然后，从这个位置沿着哈希环顺时针“行走”，遇到的第一节点就是 key 对应的节点。
案例：假设 key-01、key-02、key-03 三个 key，经过哈希算法 c-hash() 计算后，在哈希环上的位置如图所示。那么根据一致哈希算法，key-01 将寻址到节点 A，key-02 将寻址到节点 B，key-03 将寻址到节点 C
假设，现在有一个节点故障了（比如节点 C），从图中可以看到，key-01 和 key-02 不会受到影响，只有 key-03 的寻址被重定位到A。一般来说，在一致哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是，会寻址到此节点和前一节点之间的数据。比如当节点 C 宕机了，受影响的数据是会寻址到节点 B和节点 C 之间的数据（例如 key-03），寻址到其他哈希环空间的数据（例如 key-01），不会受到影响。
如果需要扩容一个节点（也就是增加一个节点，比如D），从图中可以看到，key-01、key-02 不受影响，只有 key-03 的寻址被重定位到新节点 D。一般而言，在一致哈希算法中，如果增加一个节点，受影响的数据仅仅是，会寻址到新节点和前一节点之间的数据，其它数据也不会受到影响。
使用一致哈希的话，对于 1000 万 key 的 3 节点 KV 存储，如果我们增加 1 个节点，变为 4 节点集群，只需要迁移 24.3% 的数据
也就是说，一致哈希算法具有较好的容错性和可扩展性
一致性Hash算法如何避免Hash算法的问题：
在哈希寻址中常出现这样的问题：客户端访问请求集中在少数的节点上，出现了有些机器高负载，有些机器低负载的情况，那么在一致哈希中，可以通过虚拟节点解决该问题
在一致哈希中，如果节点太少，容易因为节点分布不均匀造成数据访问的冷热不均，也就是说大多数访问请求都会集中少量几个节点上
解决方案：就是对每一个服务器节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。比如，可以在主机名的后面增加编号，分别计算“Node-A-01”“Node-A-02”“Node-B-01”“Node-B-02”“Node-C-01”“Node-C-02”的哈希值，于是形成 6 个虚拟节点从图中看到，增加了节点后，节点在哈希环上的分布就相对均匀了。这时，如果有访问请求寻址到“Node-A-01”这个虚拟节点，将被重定位到节点 A。
总结：当节点数越多的时候，使用哈希算法时，需要迁移的数据就越多，使用一致哈希时，需要迁移的数据就越少
当我们向 10 个节点集群中增加节点时，如果使用了哈希算法，需要迁移高达 90.91% 的数据，使用一致哈希的话，只需要迁移 6.48% 的数据。
一致性Hash算法的问题
如何使用一致哈希算法实现哈希寻址
一致哈希算法：突破集群的“领导者”数量限制
如果我们需要再数据写入之后，就能查到最新的数据，也就是要实现强一致性
强一致性能保证写操作完成后，任何后续访问都能读到更新后的值
最终一致性只能保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。也就是说，写操作完成后，后续访问可能会读到旧数据。
通过Quorum NWR，可以自定义一致性级别，通过临时调整写入或者查询的方式，当 W + R > N时，就可以实现强一致性
在 AP 型分布式系统中，Quorum NWR 是通常都会实现的一个功能
N 表示副本数，又叫做复制因子（Replication Factor）。也就是说，N 表示集群中同一份数据有多少个副本，比如图中，在这个三节点的集群中，DATA-1 有 2 个副本，DATA-2 有 3 个副本，DATA-3 有 1 个副本。也就是说，副本数可以不等于节点数，不同的数据可以有不同的副本数。在实现 Quorum NWR 的时候，你需要实现自定义副本的功能。也就是说，用户可以自定义指定数据的副本数，比如，用户可以指定 DATA-1 具有 2 个副本，DATA-2 具有 3 个副本
W，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新，才完成写操作从图中你可以看到，DATA-2 的写副本数为 2，也就说，对 DATA-2 执行写操作时，完成了 2 个副本的更新（比如节点 A、C），才完成写操作。
R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R个副本。你可以这么理解，读取指定数据时，要读 R 副本，然后返回 R 个副本中最新的那份数据。从图中可以看到，DATA-2 的读副本数为 2。也就是说，客户端读取 DATA-2 的数据时，需要读取 2 个副本中的数据，然后返回最新的那份数据。
总结：无论客户端如何执行读操作，哪怕它访问的是写操作未强制更新副本数据的节点（比如节点 B），但因为 W(2) + R(2) > N(3)，也就是说，访问节点 B，执行读操作时，因为要读 2 份数据副本，所以除了节点 B 上的 DATA-2，还会读取节点 A 或节点 C 上的 DATA-2，就像上图的样子（比如节点 C 上的 DATA-2），而节点 A 和节点 C的 DATA-2 数据副本是强制更新成功的。这个时候，返回给客户端肯定是最新的那份数据。
当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据
当 W + R < N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。
N、W、R 值的不同组合，会产生不同的一致性效果：
Quorum NWR 的三要素
any：任何一个节点写入成功后，或者接收节点已将数据写入 Hinted-handoff 缓存（也就是写其他节点失败后，本地节点上缓存写失败数据的队列）后，就会返回成功给客户端。
one：任何一个节点写入成功后，立即返回成功给客户端，不包括成功写入到 Hinted-handoff 缓存。
quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2时才有意义，否则等效于 all。
all：仅在所有节点都写入成功后，返回成功。
InfluxDB 企业版，支持“any、one、quorum、all”4 种写一致性级别
如何实现 Quorum NWR
QuorumNWR算法：灵活地自定义一致性
在 ZooKeeper 中，数据是以节点的形式存储的
Multi Paxos不能保证操作的顺序性，顺序性也是ZAB协议的关键
本质上 Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序
Zookeeper
ZAB 不是共识算法，不基于状态机，而是基于主备模式的原子广播协议，最终实现了操作的顺序性
这里的主备，就是 Master-Slave 模型，一个主节点和多个备份节点，所有副本的数据都以主节点为准，主节点采用二阶段提交，向备份节点同步数据，如果主节点发生故障，数据最完备的节点将当选主节点。而原子广播协议，你可以理解成广播一组消息，消息的顺序是固定的。
ZAB 在这里做了个优化，为了实现分区容错能力，将数据复制到大多数节点后（也就是如果大多数节点准备好了），领导者就会进入提交执行阶段，通知备份节点执行提交操作。
ZAB 是如何保证操作的顺序性
首先，ZAB 实现了主备模式，也就是所有的数据都以主节点为准
其次，ZAB 实现了 FIFO 队列，保证消息处理的顺序性。
最后，ZAB 还实现了当主节点崩溃后，只有日志最完备的节点才能当选主节点，因为日志最完备的节点包含了所有已经提交的日志，所以这样就能保证提交的日志不会再改变。
如何实现操作的顺序性
ZAB 是通过“一切以领导者为准”的强领导者模型和严格按照顺序提交日志，来实现操作的顺序性的
ZAB协议
如果业务在可用性上比较敏感，比如监控主机和业务运行的告警系统。如何让自己的系统能在极端情况下（比如集群中只有一个节点在运行）也能运行。可以通过 Gossip 协议实现这个目标
Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致
Gossip 的三板斧分别是：直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣言传播（Rumor mongering）
直接邮寄：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。从图中可以看到，节点 A 直接将更新数据发送给了节点 B、D。直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。也就是说，只采用直接邮寄是无法实现最终一致性
可以通过反熵来实现最终一致性，本质上，反熵是一种通过异步修复实现最终一致性的方法反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性从图中可以看到，节点 A 通过反熵的方式，修复了节点 D 中缺失的数据。
推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵
拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵
推拉方式就是同时修复自己副本和对方副本中的熵
在实现反熵的时候，主要有推、拉和推拉三种方式
反熵中的熵是指混乱程度，反熵就是指消除不同节点中数据的差异，提升节点间数据的相似度，降低熵值。反熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高
谣言传播，广泛地散播谣言，它指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据从图中可以看到，节点 A 向节点 B、D 发送新数据，节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。其实，谣言传播非常具有传染性，它适合动态变化的分布式系统
Gossip 的三板斧
在自研 InfluxDB 中，一份数据副本是由多个分片组成的，也就是实现了数据分片，三节点三副本的集群，如图所示
反熵的目标是确保每个 DATA 节点拥有元信息指定的分片，而且不同节点上，同一分片组中的分片都没有差异。比如说，节点 A 要拥有分片 Shard1 和 Shard2，而且，节点 A 的Shard1 和 Shard2，与节点 B、C 中的 Shard1 和 Shard2，是一样的
修复：只需要将分片数据，通过 RPC 通讯，从其他节点上拷贝过来就可以了
缺失分片：也就是说，在某个节点上整个分片都丢失了。
修复：按照一定顺序来修复节点的数据差异，先随机选择一个节点，然后循环修复，每个节点生成自己节点有、下一个节点没有的差异数据，发送给下一个节点，进行修复
从图中可以看到，数据修复的起始节点为节点 A，数据修复是按照顺时针顺序，循环修复的。需要你注意的是，最后节点 A 又对节点 B 的数据执行了一次数据修复操作，因为只有这样，节点 C 有、节点 B 缺失的差异数据，才会同步到节点 B 上。
节点之间的分片不一致：也就是说，节点上分片都存在，但里面的数据不一样，有数据丢失的情况发生。
数据缺失情况
注意事项：由于反熵需要做一致性对比，很消耗系统性能，所以建议你将是否启用反熵功能、执行一致性检测的时间间隔等，做成可配置的，能在不同场景中按需使用。
使用 Anti-entropy 实现最终一致
Gossip协议：流言蜚语，原来也可以实现一致性
PBFT 算法是一种能在实际场景中落地的拜占庭容错算法，它在区块链中应用广泛（比如 Hyperledger Sawtooth、Zilliqa）
这个算法有个非常致命的缺陷。如果将军数为 n、叛将数为 f，那么算法需要递归协商 f+1 轮，消息复杂度为 O(n ^ (f + 1))，消息数量指数级暴增。你可以想象一下，如果叛将数为 64，消息数已经远远超过 int64 所能表示的了
另外，尽管对于签名消息，不管叛将数（比如 f）是多少，经过 f + 1 轮的协商，忠将们都能达成一致的作战指令，但是这个算法同样存在“理论化”和“消息数指数级暴增”的痛点。
口信消息型拜占庭问题之解的局限
所有的消息都是签名消息，也就是说，消息发送者的身份和消息内容都是无法伪造和篡改的（比如，楚无法伪造一个假装来自赵的消息）
赵将进入预准备（Pre-prepare）阶段，构造包含作战指令的预准备消息，并广播给其他将军（魏、韩、楚）
接收到预准备消息之后，魏、韩、楚将进入准备（Prepare）阶段，并分别广播包含作战指令的准备消息给其他将军。比如，魏广播准备消息给赵、韩、楚（如图所示）
当赵接收到苏秦的请求之后，会执行三阶段协议（Three-phase protocol）
首先，苏秦联系赵，向赵发送包含作战指令“进攻”的请求，如图所示
进入提交阶段后，各将军分别广播提交消息给其他将军，也就是告诉其他将军，我已经准备好了，可以执行指令了
最后，当某个将军收到 2f + 1 个验证通过的提交消息后（包括自己，其中 f 为叛徒数，演示中为 1），也就是说，大部分的将军们已经达成共识，这时可以执行作战指令了，那么该将军将执行苏秦的作战指令，执行完毕后发送执行成功的消息给苏秦。
然后，当某个将军收到 2f 个一致的包含作战指令的准备消息后，会进入提交（Commit）阶段（这里的 2f 包括自己，其中 f 为叛徒数，在我的演示中是 1）
最后，当苏秦收到 f+1 个相同的响应（Reply）消息时，说明各位将军们已经就作战指令达成了共识，并执行了作战指令（其中 f 为叛徒数，演示中为 1）
总结：PBFT 算法是通过签名（或消息认证码 MAC）约束恶意节点的行为，也就是说，每个节点都可以通过验证消息签名确认消息的发送来源，一个节点无法伪造另外一个节点的消息。最终，基于大多数原则（2f + 1）实现共识的。
PBFT 是如何达成共识的
PBFT算法：有人作恶，如何达成共识？
工作量证明 (Proof Of Work，简称 PoW)，就是一份证明，用来确认你做过一定量的工作。比如，你的大学毕业证书就是一份工作量证明，证明你通过 4年的努力完成了相关课程的学习。
具体来说就是，客户端需要做一定难度的工作才能得出一个结果，验证方却很容易通过结果来检查出客户端是不是做了相应的工作
请求方做了一些运算，解决了某个问题，然后把运算结果发送给验证方，进行核验，验证方根据运算结果，就能判断请求方是否做了相关的工作。
这个算法具有不对称性，也就是说，工作对于请求方是有难度的，对于验证方则是比较简单的，易于验证的
具体的工作量证明过程，如图所示
如何理解工作量证明
区块链是通过 SHA256 来执行哈希运算的，通过计算出符合指定条件的哈希值，来证明工作量。在区块链中，PoW 算法是基于区块链中的区块信息，进行哈希运算的
区块头（Block Head）：区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数（nonce）等组成的
区块体（Block Body）：区块包含的交易数据，其中的第一笔交易是 Coinbase 交易，这是一笔激励矿工的特殊交易
区块链的区块，是由区块头、区块体 2 部分组成的
在区块链中是通过对区块头执行 SHA256 哈希运算，得到小于目标值的哈希值，来证明自己的工作量的
计算出符合条件的哈希值后，矿工就会把这个信息广播给集群中所有其他节点，其他节点验证通过后，会将这个区块加入到自己的区块链中，最终形成一串区块链，如图所示
最后，如果算力越强，系统大概率会越先计算出这个哈希值。这也就意味着，如果坏人们掌握了 51% 的算力，就可以发起 51% 攻击，比如，实现双花（DoubleSpending），也就是说，同一份钱花 2 次。
具体说的话，就是攻击者掌握了较多的算力，能挖掘一条比原链更长的攻击链，并将攻击链向全网广播，这时呢，按照约定，节点将接受更长的链，也就是攻击链，丢弃原链。如图所示
需要注意，即使攻击者只有 30% 的算力，他也有可能连续计算出多个区块的哈希值，挖掘出更长的攻击链，发动攻击； 另外，即使攻击者拥有 51% 的算力，他也有可能半天无法计算出一个区块的哈希值，也就是攻击失败。也就是说，能否计算出符合条件的哈希值，有一定的概率性，但长久来看，攻击者攻击成功的概率等同于攻击者算力的权重。
区块链如何实现 PoW 算法的
PoW算法：有办法黑比特币吗？
02丨协议和算法篇
分布式协议与算法实战
0 条评论
回复 删除
下一页
