分布式共识

4.1 分布式共识简介

分布式共识（Distributed Consensus）是指在分布式系统中，多个节点（或进程）协同完成某个任务或达成某个决策的过程。在这个过程中，每个节点需要就该任务或决策达成一致，并且能够互相通信、协调、协作。

分布式共识的一个重要应用是在区块链技术中，用于解决双花问题（Double-spending problem）和确定哪些交易会被写入区块链。比特币等加密货币就是通过共识算法来实现去中心化的交易记录。

常见的分布式共识算法包括拜占庭将军问题（Byzantine fault tolerance, BFT）、Raft、Paxos、Proof of Work（PoW）、Proof of Stake（PoS）等。这些算法都有各自的优缺点，适用于不同的场景。例如，PoW 算法被应用在比特币等加密货币中，而 PoS 算法则被用在以太坊等区块链平台中。

4.1.1 什么是分布式共识

分布式共识是指在一个分布式系统中，多个节点之间需要就某些决策达成一致意见的过程。在这个过程中，各个节点通过相互通信和协作来达成共识，以保证系统能够正常运作并避免出现错误或冲突。

在分布式系统中，由于节点之间的网络延迟、节点故障等原因，不同节点的状态可能存在不一致的情况。因此，需要通过分布式共识算法来解决这些问题。常用的分布式共识算法包括 Paxos、Raft、Byzantine Fault Tolerance 等。

分布式共识算法的基本思路是，通过节点之间的通信和协作，选出一个“领导者”节点来负责提出某个决策，其他节点通过投票和确认的方式来达成共识，以保证系统在多个节点之间的一致性和可靠性。这种算法在分布式数据库、区块链等系统中都得到了广泛应用。

4.1.2 为什么要达成共识

在分布式系统中，节点之间的状态可能存在不一致的情况，如果不对这些状态进行协调，就可能导致系统出现错误或冲突。为了避免这种情况的发生，需要在分布式系统中实现共识机制，保证各个节点之间的状态达成一致，从而保证系统的正确性和可靠性。

具体来说，如果在一个分布式系统中，某些节点的状态发生了变化，但其他节点还没有收到这个变化的通知，那么这些节点就会基于过期的状态进行操作，从而导致数据不一致或操作冲突。通过分布式共识算法，可以确保所有节点在进行操作前都已经达成了共识，从而保证了数据的一致性和操作的正确性。

另外，分布式共识还能够防止拜占庭错误的发生。拜占庭错误是指分布式系统中存在恶意节点或网络攻击，导致节点之间的通信受到干扰或伪造。通过分布式共识算法，可以检测和排除这些恶意行为，确保系统的安全性和可靠性。

4.2 异步系统中的共识

4.2.1 FLP不可能定理

FLP不可能定理是指，在一个异步的分布式系统中，不存在一个算法能够保证在存在至少一个节点故障的情况下，仍然能够保证所有节点能够在有限时间内达成共识。

该定理由Fischer、Lynch和Paterson在1985年提出，是分布式共识领域的一个重要理论。其基本思想是，由于节点之间的通信存在延迟和不可靠性，因此在存在故障节点的情况下，无法确定某个节点是否已经停止工作或者只是延迟。这种不确定性会导致共识过程无法完成。

FLP不可能定理的证明使用了卡慕尔异步通信模型，即假设节点之间的消息传输可以无限制地延迟，但必须保证每个节点最终能够收到所有消息。基于这种通信模型，可以证明在存在至少一个节点故障的情况下，无法保证所有节点能够在有限时间内达成共识。

虽然FLP不可能定理指出了分布式共识问题的困难性，但是在实际应用中，往往会使用一些近似算法来解决共识问题。例如，Paxos算法、Raft算法等就是通过一些特殊的约束条件来实现了共识，从而在实际应用中得到了广泛的应用。

安全性: 在一个任期内只会确定一个值（something wrong not happen）
活性：分布式系统最终会认同某一个值(something right must happen)
容错性

分布式系统中的 safety 和 liveness — 源代码 (lrita.github.io)

和CAP一样，三选二

证明：

FLP不可能定理的证明是基于卡慕尔异步通信模型的，该模型假设节点之间的消息传输可以无限制地延迟，但必须保证每个节点最终能够收到所有消息。在这种通信模型下，证明FLP不可能定理的基本思路是，通过构造一个反例来说明在异步通信模型下，不存在一个算法能够保证在存在至少一个节点故障的情况下，仍然能够保证所有节点能够在有限时间内达成共识。

具体来说，假设有一个分布式系统，其中包含n个节点，节点之间通过消息传递来达成共识。为了方便起见，假设系统中只有两种状态：0和1。初始状态下，每个节点的状态都是不确定的。节点之间的通信是异步的，消息传输可以无限制地延迟，且无法保证消息的可靠性。

接下来，假设有一个算法A，可以在存在至少一个节点故障的情况下，仍然能够保证所有节点能够在有限时间内达成共识。为了证明FLP不可能定理，需要构造一个反例来说明这个算法是不可行的。

具体来说，假设存在两个节点p和q，它们的状态初始时均为不确定状态。为了达成共识，节点p发送一个消息m给节点q，告诉节点q它当前的状态是0。但由于通信是异步的，消息m可能会被延迟或者丢失，导致节点q无法知道节点p的状态。因此，节点q可以选择继续等待消息m，或者猜测节点p的状态是1。如果节点q猜测节点p的状态是1，那么节点q会发送一个消息n给节点p，告诉节点p它当前的状态是1。由于节点p也无法确定节点q的状态，节点p也有可能会猜测节点q的状态是0，从而发送一个消息k给节点q，告诉节点q它当前的状态是0。这样，就形成了一个死锁状态，导致节点p和q无法达成共识。

从上述分析可以看出，由于异步通信模型的存在，无法保证消息的可靠性和节点状态的一致性，从而导致FLP不可能定理的存在。虽然该定理证明了在异步通信模型下，不存在一个算法能够保证在存在至少一个节点故障的情况下，仍然能够保证所有节点能够在有限时间内达成共识，但在实际应用中，可以采用一些近似算法来解决共识问题。

故障屏蔽
使用故障检测器
使用随机性算法

这三种方法可以绕开FLP不可能定理

4.2.2 故障屏蔽

故障屏蔽（Fault tolerance）和故障检测器（Fault detection）是分布式系统中常用的技术，用于提高系统的可靠性和鲁棒性。使用随机性算法是实现这些技术的一种常用方法。

故障屏蔽是一种技术，可以在系统中发生故障时保证系统的正常运行。一种常见的故障屏蔽技术是冗余备份（Redundancy），即在系统中增加多个备份，当一个节点发生故障时，备份节点可以接管其任务，保证系统的正常运行。在实现冗余备份时，常常使用随机性算法，如随机化选举（Randomized election）和随机化复制（Randomized replication）等技术，来提高系统的可靠性和鲁棒性。

4.2.3 使用故障检测器

故障检测器是一种技术，用于检测分布式系统中的故障节点。一种常见的故障检测器是心跳检测（Heartbeat detection），即每个节点定期向其他节点发送心跳消息，检测是否有节点故障。在实现心跳检测时，常常使用随机性算法，如随机化时间间隔（Randomized interval）和随机化路线（Randomized routing）等技术，来避免故障检测过程中的死锁和瓶颈等问题，提高检测的准确性和效率。

虽然完美的故障检测器具备以下条件：

完全性：每一个故障的进程都会被每一个正确的进程怀疑
精确性：每一个正确的进程都不会被其他进程怀疑

但实际上，实现困难。而论文证明，即使使用”不完美”的故障检测器，只要通信可靠，失效进程不超过一半，依然可以用来解决共识问题。因此实现最终弱故障检测器：

最终弱完全性：每一个故障的进程最终都会被一些正确的进程检测到。
最终弱精确性：经过一段时间后，一个正确的进程不会被其他正确的进程怀疑。

4.2.4 使用随机性算法

随机性算法是指在算法设计和实现中引入随机性的一种技术，可以用于解决一些分布式系统中的复杂问题，如分布式计算、分布式存储、分布式共识等问题。随机性算法具有一些优点，如简单、快速、容易实现和分布式化等特点，可以提高分布式系统的性能和效率。

区块链：

Proof of Work（PoW）和Proof of Stake（PoS）是两种常见的区块链共识机制，用于保证区块链的安全性和去中心化特性。它们的主要区别在于如何选举出下一个区块的记账节点。

PoW机制是通过计算一定难度的工作量来选举出下一个区块的记账节点。矿工需要通过计算一个随机数，使得计算结果符合一定的规则，以此获得记账权。这种机制需要大量的计算能力和电力消耗，因此存在能源浪费和环境污染等问题。

PoS机制则是通过拥有一定数量的代币来选举出下一个区块的记账节点。持有更多代币的用户会有更大的概率被选中作为记账节点。这种机制可以避免计算资源和能源的浪费，但需要考虑如何避免寡头垄断和激励机制的问题。

以下是PoW和PoS机制的一些优缺点：

Proof of Work（PoW）:

优点：安全性高，攻击成本高，可预测性好。
缺点：能源浪费，环境污染，效率低，中心化问题。

Proof of Stake（PoS）:

优点：节省能源，环保，效率高，可扩展性好，分散化程度高。
缺点：可能导致寡头垄断，激励机制难以设计，安全性有待验证。

[(459条消息) [区块链]共识算法（POW,POS,DPOS,PBFT）介绍和心得_dpos共识机制_乐扣老师lekkoliu的博客-CSDN博客](https://blog.csdn.net/lsttoy/article/details/61624287?ops_request_misc=%7B%22request%5Fid%22%3A%22168594614916800186538613%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168594614916800186538613&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-2-61624287-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=pow pos&spm=1018.2226.3001.4187)

[(459条消息) 区块链必知基础知识、POS、POW、DPOS、公有链、私有链、联盟链_区块链pos_yida&yueda的博客-CSDN博客](https://blog.csdn.net/qq_40585384/article/details/124678390?ops_request_misc=&request_id=&biz_id=102&utm_term=pow pos&utm_medium=distribute.pc_search_result.none-task-blog-2~~all~~sobaiduweb~default-0-124678390.142^v88^control_2,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)

4.3 同步系统中的共识

Dolev-Strong算法是一种用于解决密码学中的安全多方计算（Secure Multiparty Computation，SMC）问题的算法。该算法由Danny Dolev和Hadas Shachnai-Strong于1991年提出。

安全多方计算是一种加密技术，允许多个参与者在不泄露私有信息的情况下共同计算出一个结果。在安全多方计算中，每个参与者需要负责保护自己的私有信息，同时协调计算过程以达到预期的结果。Dolev-Strong算法就是一种用于实现安全多方计算的算法之一。

Dolev-Strong算法基于一种名为交互式验证协议（Interactive Verification Protocol，IVP）的技术，通过多轮的通信和验证来确保计算的正确性和安全性。该算法可以在不需要信任第三方的情况下完成安全计算，因此具有很好的去中心化特性。

Dolev-Strong算法的主要思想是，将计算任务分解成多个子任务，每个参与者只负责计算其中的一部分，并将计算结果加密后传递给下一个参与者。在每个子任务之间，参与者需要进行验证，以确保计算的正确性和安全性。通过多轮的交互和验证，参与者最终可以得到正确的计算结果，同时保护自己的私有信息不被泄露。

总的来说，Dolev-Strong算法是一种基于交互式验证协议的安全多方计算算法，可以在不需要信任第三方的情况下实现安全计算，具有很好的去中心化特性，被广泛应用于密码学、区块链和分布式系统等领域。

4.4 Paxos

(443条消息) 分布式共识算法——Paxos算法（图解）_杨戬的博客-CSDN博客

Paxos算法是一种用于解决分布式系统中达成一致性的算法，由Leslie Lamport于1998年提出。Paxos算法的目的是保证分布式系统中各个节点之间的状态一致性，即在不可靠的网络环境下，保证不同节点对共享资源的操作具有相同的效果。

Paxos算法的核心思想是通过一个协调者（coordinator）和多个参与者（acceptor）之间的协作来达成共识。在Paxos算法中，协调者的主要任务是向参与者发起提案（proposal），而参与者的主要任务是接受并决策是否通过提案，进而达成一致性。

具体来说，Paxos算法分为三个阶段：

准备阶段（prepare phase）：协调者向参与者发起提案，并请求参与者发送自己曾经接受的最大提案编号（proposal number），以便协调者了解当前的提案状态。
接受阶段（accept phase）：如果协调者获得了大多数参与者的反馈，并且没有其他提案正在进行，那么协调者就可以向参与者发起新的提案，并请求参与者接受该提案。
学习阶段（learn phase）：一旦协调者成功地向大多数参与者发送了新的提案，并得到了反馈，那么协调者就可以通知所有参与者接受该提案，从而完成一致性达成的过程。

总的来说，Paxos算法是一种用于解决分布式系统中达成一致性的算法，通过协调者和参与者之间的协作来实现共识。该算法被广泛应用于分布式存储、分布式计算、分布式数据库和区块链等领域。

Paxos算法是一种非常复杂的算法，实现和理解上有一些细节需要注意：

提案编号（proposal number）的生成方式需要确保唯一性和可比较性，一般使用时间戳和节点编号等信息组合而成。
在准备阶段，参与者需要检查当前提案的编号是否比自己之前接受的所有提案编号都要大。如果有更大的提案编号，参与者就需要返回该提案的编号和对应的值，以便协调者做出决策。
在接受阶段，协调者需要确保至少有半数的参与者接受了新的提案，并将其值写入日志。如果无法达成一致，协调者需要回退并重新发起提案。
在学习阶段，协调者需要通知所有参与者已经达成共识，并将提案值写入共享存储中。
Paxos算法还需要考虑一些异常情况，例如节点宕机、网络延迟和网络分区等，需要通过复杂的协议来保证系统的可用性和一致性。

需要注意的是，Paxos算法是一种非常复杂的算法，对于初学者来说理解起来比较困难。因此，建议在实践中结合阅读相关文献和代码实现，逐步理解其细节和原理。

为什么要提案编号？

分布式系统使用时间戳之类的物理时间可能并不准确
轮次+服务器id

4.5 Go实现Paxos

4.6 Multi-Paxos

Multi-Paxos是Paxos算法的一个变种，用于优化Paxos算法在多次提案的情况下的性能。在Paxos算法中，每次提案都需要执行一次完整的Paxos流程，包括准备、接受和学习三个阶段，这会导致Paxos算法的性能比较低。

Multi-Paxos通过引入领导者（leader）的概念来优化Paxos算法的性能。在Multi-Paxos中，领导者负责向参与者发起提案，而参与者则只需要根据领导者的指示来决策是否接受提案。因此，领导者可以在一段时间内发起多个提案，从而避免了每次提案都需要执行完整的Paxos流程的问题。

具体来说，Multi-Paxos的流程如下：

领导者向参与者发起一个提案，包括提案编号和提案值。
参与者根据提案编号进行决策：如果当前的提案编号比之前接受的所有提案编号都要大，那么参与者就接受该提案，并向领导者发送接受消息；否则，参与者就拒绝该提案，并向领导者发送拒绝消息。
如果领导者收到了大多数参与者的接受消息，那么该提案就被确定，并向所有参与者发送确定消息，完成该提案的学习阶段。
如果领导者收到了大多数参与者的拒绝消息，那么领导者就需要重新选择一个提案编号，并重新发起提案。

需要注意的是，Multi-Paxos仍然需要保证Paxos算法的正确性和一致性，但通过引入领导者来优化性能，使得Multi-Paxos在实际应用中更加高效。

4.8 Raft算法

要持久化存储的信息：

currentTerm：当前任期，用于恢复
votefor:向谁投票，只投个第一个发送RequestVote RPC的人而拒绝其他发送RequestVote RPC的人
日志：包含索引位置，任期号，命令本身，如果日志在半数节点上被存储，则该记录可提交。注意，领导者先将日志持久化存储到本地，再并行用AppendEntries RPC发送到其他节点上。这时，如果收到超过半数的响应，则领导者将命令应用于自己的状态机，提交该日志，然后向客户端返回响应。后续的日志复制RPC中还包含LeaderCommit表明领导者已经提交的日志的最大索引，跟随者收到此RPC时也会提交所有小于该索引的日志

两个RPC：

RequestVote RPC ：用于领导者选举，包含term,id,lastLogIndex,lastLogTerm，同样在用于领导者选举中，最后两个属性若term>跟随者的term或者term相等但index大于跟随者最后一条日志的index，则跟随者才会投票，同理也需要一半投票才行，这确保了领导者在超过半数给他投票的节点中拥有最完整的日志。
AppendEntries RPC ：用于复制日志/发送心跳信息，后续的日志复制RPC中还包含LeaderCommit表明领导者已经提交的日志的最大索引，跟随者收到此RPC时也会提交所有小于该索引的日志

节点转换流程：

只有发生以下三种情况之一才更新自己的状态
- RequestVote RPC收到超过半数的选票，变为领导者
- 收到来自其他领导者的AppendEntries，退化为跟随者
- 没发生上述两种情况，任期++，投自己一票

保证两个特性：

安全性：一个任期内最多只有一个领导者被选出来
活性：系统最终能选出一个领导者

解决活锁问题（没人可以获得超过一半选票）：

节点随机选择超时时间（T-2T期间，T越大于网络传播时间效果越加，但同时不能太大，否则性能会受到影响）

两个特性：

如果任期和索引相同，则日志条目完全相同，日志内容相同，且之前的日志也完全相同（数学归纳法？）
RAFT不允许出现日志空洞，必须连续提交日志
为了维护这两个特性，在AppendEntries中还有之前一个日志的prevLogIndex和任期prevLogTerm，跟随者收到后，会检查自己最后一条日志的index和term是否匹配，若匹配，则接受，否则拒绝。（一致性检查）

延迟提交：

为什么需要延迟提交？
- 若出现网络分区，导致B分区中的一个服务器拥有更新任期的日志（比如3），而A分区中的领导者（此时在任期4，而最新的日志任期为2），若提交后宕机（而A分区中其他服务器的日志任期也为2，但未提交），而B分区中的服务器此时恰好又成为新的领导者（任期5），此时则会覆盖掉A分区中未提交任期为日志2的服务器的日志，而实际上，A分区之前的领导者实际上已经提交了该日志，这不符合已提交日志不能被修改的需求
怎么延迟提交
- 日志必须存储在超过半数节点上
- 领导者必须看到超过半数节点上还存储着至少一条自己任期内的记录
- 领导者只能提交自己任期的日志，从而间接提交之前任期的日志
- no-op日志：只有索引和日期，保持领导者的权威
  - 在领导者刚选举成功时，就本地追加no-op日志（只包含任期），同时appendEntries到其他的节点，显然，no-op日志的任期就是领导者当前的任期，当然能提交，从而间接提交之前的任期的日志

清理不一样的日志：

两种不一样的日志，缺失/多出来的
- 前者直接AppendEntries来补齐（也要用到nextIndex）
- 后者，领导者为每个跟随者保存nextIndex[]变量，存储领导者最后一条日志的索引+1
流程
- 针对缺失的：领导者检查自己的日志，最新index为10，然后比如对于跟随者1，nextIndex[1]=11,带上前一个日志条目的唯一标识（10，任期6），跟随者1索引为10处没有日志，递减nextIndex[1],直到nextIndex[1]=5,索引4且任期4的日志匹配，补齐索引5-10
- 针对多出来的，跟上面一样，直到找到匹配的index，而之后的全部删除即可

处理旧领导者：

RPC请求有自己的任期，如果发生网络分区，老的领导者还以为自己是领导者，他的RPC在被其他Follower接收到的时候，但凡Follower已知的任期比他新，都会返回拒绝消息，但凡接收到拒绝消息，老的领导者就跟咽了气的皮球似的变为跟随者。

配置变更：

使用 Joint Consensus（联合共识）完成两阶段协议
- 第一阶段,Cold+new，多数派，提交
- 第二阶段,Cnew，多数派，提交，提交后后续配置都基于Cnew（不在Cnew的领导者下台）
  - 不在Cnew的领导者下台会导致一个问题就是，不在Cnew的跟随者将不再收到心跳，因此其会参与领导者选举（尽管会因为日志不够新而导致竞选失败，但是还是会影响竞选过程导致可用性变差）
    - 解决：Pre-Vote阶段，就还是发送Pre-Vote请求询问整个系统“我到底有没有资格参与竞选”（这个资格还是根据任期以及日志Index来判断的）。但这样会有个问题就是，如果在Cnew集群中的领导者还没有把Cnew的日志发到其跟随者上，也就是说，跟随者的日志还不够新，那么就算有Pre-Vote，可能还是会影响选举，导致不在Cnew的服务节点竞选成功
    - 增强Pre-Vote判断条件：
      - 任期更大，或者任期相同索引更大
      - 至少一次选举时间内没有收到领导者心跳
    - 注意到在Pre-Vote阶段不会增加自己的任期，所以Pre-Vote不仅可以解决配置更改干扰领导者的问题，还能解决网络分区脑裂和任期爆炸增长的问题
    - 示例：etcd，将候选者细分为预候选者和候选者，前者发送Pre-Vote，不增加日期，后者发送RequestVote，会增加任期

日志压缩：

关注最终状态
压缩后得到快照，持久化存储
每个服务器独立地压缩其已提交的日志
保存最后一条被丢弃的日志的索引和任期，用AppendEntries进行日志一致性的检查
一旦丢弃了前面部分的日志，领导者要承担两个责任：
- 如果服务器重启了，则需要将最新的快照加载到状态机后再接收日志
- 向较慢的跟随着发送一致的状态快照(InstrallSnapshot RPC)
LastIncludeIndex和LastIncludeTerm，记录状态，之前的日志全部丢弃
在正常运行期间通过写时复制技术（COW）生成快照（开源LogCabin）