526互联

分布式协议与算法 概要

发布时间 2023-09-15 12:32:32作者: TomiokapEace

最近系统性的学习了分布式协议与算法，在此做个小小笔记。

理论

拜占庭将军问题

拜占庭将军问题（Byzantine Generals Problem）是一个著名的分布式系统中的问题，用于探讨在存在故障节点或恶意行为的情况下如何进行可靠的信息传递和共识达成。

问题描述如下：假设有一组拜占庭将军围绕一座城市展开进攻，并需要通过互相发送消息来协调行动。然而，其中一部分将军可能是叛徒，他们可能故意发送错误、误导性或矛盾的信息。问题是，如何使得忠诚的将军能够就行动达成一致，即使有叛徒存在？

这个问题的关键是确保忠诚将军之间的一致性，以便他们能够采取相同的行动。然而，由于叛徒的存在，他们可以发送不一致的指令，破坏共识的达成。

解决拜占庭将军问题的目标是设计一个算法，使得忠诚的将军能够就行动达成一致，并且不会受到叛徒的影响。一种经典的解决方案是使用拜占庭容错算法，如PBFT（Practical Byzantine Fault Tolerance），来达成共识。

拜占庭将军问题

[拜占庭将军问题](什么是拜占庭将军问题？ - 知乎 (zhihu.com))

CAP理论

理论

对分布式系统的特性做了高度抽象，比如抽象成一致性（Consistency），可用性（Availability）和分区容错性（Partition Tolerance）。这三个指标，C强调数据正确，A强调数据可读，P强调系统正常可用。CAP理论源自高可用高拓展的大型互联网系统的拓展，强调在数据一致性（ACID）和服务可用性（BASE）之间权衡。

CAP不可能三者兼得。

分布式系统与单机系统不同，涉及多节点的通信和交互，节点间的分区故障是必然发生的，所以在分布式系统中分区容错性是必须要考虑的，舍弃P就意味着舍弃分布式系统。只要有网络交互就会有延迟和数据丢失，只能接受这个现实还必须保证系统不会挂掉，故而必须有P，P是前提。

（但是分布式系统并非只能在CA中选择一个，不存在网络分区的时候，CA能同时保证）

CP模型，AP模型

CP舍弃了可用性，一定会读到最新数据，一旦因为消息丢失、延迟过高发生了网络分区，就会影响一致性，所以无法响应时报错。

AP舍弃了一致性，实现了服务的高可用，用户访问时能得到响应数据，不会出现响应错误，但会读到旧数据。

根据场景特点，进行CAP权衡，设计合适的分布式系统。

CP模型的KV存储和AP模型的KV存储分别适合怎么样的业务场景？

CP模型的KV存储适合强一致性要求较高的业务场景。在CP模型中，当写入数据后，系统必须保证所有副本都达到一致状态才返回成功，这样可以确保读取最新的数据。因此，CP模型适用于需要精确数据一致性的应用，如金融交易系统、订单处理系统等。

AP模型的KV存储适合对一致性要求相对较低但可用性要求很高的业务场景。在AP模型中，系统允许在写操作完成之后立即返回成功，即使不同副本之间的数据可能存在较小的延迟或不一致。这样可以提高系统的可用性，同时可能会降低数据的一致性。AP模型适用于分布式系统中需要高可用性和容错性的场景，如社交网络、实时通信应用等。

ACID理论 追求一致性

ACID理论是对事务特性的抽象和总结，方便我们实现事务，实现了操作的ACID特性，就实现了事务。

保证节点间的ACID特性，分布式事务协议。

二阶段提交协议

节点中的其中一个收到消息，作为协调者，协调者收到消息之后发起二阶段提交，进入提交请求阶段（投票阶段），向剩余节点（参与者）发送消息，各节点对自身进行评估之后回复协调者，协调者收到所有回复后进入提交执行阶段（完成阶段），执行消息或返回无法执行，保证节点动作一致。

在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己的那一部分，即使它出现故障或中途被替换掉。

缺点：在提交请求阶段需要预留资源，资源预留期间其他人不能操作。数据库是独立的系统（XA协议，现在常用）。故而无法根据业务特点弹性地调整锁的粒度，这些都会影响数据库的并发性能（解决：TCC）。

二阶段提交协议不仅是一种协议，也是一种非常经典的思想。

TCC（try confirm cancel)

三个阶段：预留（try），确认（confirm），撤销（cancel）。关系图：

预留 → 确认
↑  ↓
撤销

对比二阶段提交协议，预留类似提交请求，确认类似提交执行，撤销类似回滚。本质上是补偿事务，核心思想是为每个操作都注册一个与其对应的确认操作和补偿操作（也就是撤销操作）。

缺点：引入询问阶段和超时机制类减少资源被长时间锁定，但会导致集群各节点正常运行的情况下，使用更多的消息进行协商，增加了系统负载和响应延迟。

所以如果不是必须，不要实现ACID，考虑实现最终一致性。

事务性分布式系统有哪些优点和缺点？

优点：

  1. 可扩展性：分布式系统可以通过增加节点的方式进行水平扩展，以满足不断增长的负载需求。
  2. 高可用性：分布式系统中的多个节点可以提供冗余和容错机制，即使某些节点出现故障，系统仍然可以继续正常运行。
  3. 弹性和容错性：分布式系统在遇到故障或网络中断等问题时，能够自动适应并恢复正常操作，确保系统的可靠性和稳定性。
  4. 数据局部性：分布式系统可以将数据存储在就近的节点上，降低数据访问的延迟，提高系统的性能。

缺点：

  1. 复杂性：分布式系统设计和开发需要考虑到分布式一致性、并发控制、网络通信等复杂问题，增加了系统的开发和维护成本。
  2. 一致性和同步：在分布式环境中实现一致性是一个挑战，需要采用合适的协议和算法来确保数据的一致性，并处理好节点之间的同步问题。
  3. 性能损耗：由于跨网络通信和数据复制的需求，分布式系统可能会引入一定的性能损耗，例如网络延迟和数据同步开销。
  4. 难以调试和排错：分布式系统中的错误和故障排查可能更加复杂，因为涉及多个节点和组件之间的相互影响。
BASE理论 追求可用性

BASE理论是对CAP中一致性和可用性权衡的结果，它来源于对大规模互联网分布式系统实践的总结，是基于CAP定理逐步演化而来的。它的核心思想是，如果非必需，不推荐实现事务或强一致性，鼓励优先考虑可用性和性能，根据业务的场景特点来实现非常弹性的基本可用，以及实现数据的最终一致性。在NoSQL中应用广泛，是NoSQL系统设计事实上的理论支撑。

集群的可用性是各个节点可用性的乘积，根据实际场景，尽量采用可用性优先的AP模型。

实现基本可用的四板斧

流量削峰（错开访问请求，削弱峰值），延迟响应（队列处理），体验降级（简化方案代替原始方案），过载保护（超时拒绝请求）。

除了上述四个方法，还有哪些方法可以用来实现基本可用？

  1. 限流：通过设置请求限制来控制系统的吞吐量，防止系统被过多请求压垮。可以使用算法如漏桶算法或令牌桶算法来实现请求限流。
  2. 资源优化：对系统中的资源进行优化，包括数据库查询优化、缓存优化、网络带宽优化等，以提高系统的性能和响应速度。
  3. 异步处理：将耗时的操作转换为异步任务，在后台进行处理，以避免同步操作导致的延迟。例如，可以使用消息队列或异步调用来处理一些非实时的业务逻辑。
  4. 故障隔离：使用容错机制和故障隔离策略，将系统划分为不同的模块或服务，并使用容器化或虚拟化技术来隔离故障，确保故障不会影响整个系统的正常运行。
  5. 自动化监控和报警：建立有效的监控系统，实时监测系统的状态和性能指标，并设置合理的报警机制，及时发现和解决潜在的问题，减少系统不可用的时间。
最终一致性

系统中所有的数据副本在经过一个短暂的延迟之后最终达到一种一致的状态。但对于敏感元数据，需要考虑采用强一致性。实际工程实践有两个标准：以最新写入为准；以第一次写入为准。具体方式：读时修复，写时修复（读写时检测数据的不一致并修复），异步修复（定时检测修复）。

协议与算法

Paxos算法（共识算法）

Paxos是一种用于实现分布式一致性的算法，它解决了在一个存在故障的异步系统中，多个节点如何达成一致的问题。

Basic-Paxos

如何达成共识（在整个过程中，提案号用于解决冲突，多数接受者的支持用于保证一致性）：

  1. 提议（Prepare）阶段：一个节点（称为提议者）向其他节点（称为接受者）发出提议请求。提议者选择一个提案号（编号），并发送一个prepare请求给所有接受者。
  2. 响应（Promise）阶段：接受者收到prepare请求后，检查提案号。如果收到的提案号比之前收到的更大，则接受者承诺不再接受小于该提案号的提议，并返回之前已经接受过的最大提案号和对应的提案值给提议者。
  3. 接受（Accept）阶段：如果提议者收到来自多数接受者的响应，且没有收到更高提案号的响应，则提议者认为它拥有了多数接受者的支持。此时，提议者可以向这些接受者发送accept请求，包含提案号和提案值。
  4. 存储（Learn）阶段：接受者收到accept请求后，检查提案号并接受提案。一旦接受了提案，接受者将提案号和提案值存储下来。

接受者对于已经响应过的提案编号：小于，不响应，不通过；等于，不响应（响应过了），通过；保证优先级更高的提案信息。

Basic-Paxos就单个值达成了共识，容错能力源自“大多数”的约定，当少于一半的节点出现故障时（容错），共识协商仍然可以正常工作。

Multi-Paxos

Multi-Paxos不是一个算法，而是统称，指基于Basic-Paxos思想，通过多个Basic-Paxos示例实现一系列值的共识算法。实现Multi-Paxos的最大挑战的如何证明它是正确的。

如果直接通过多个Basic-Paxos示例实现一系列值的共识，会出现什么问题？

1.多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，导致协商失败，需要重新协商。

2.分布式系统的运行是建立在RPC通信的基础之上的，两轮RPC通信（准备阶段和接受阶段）往返消息多、耗性能、延迟大。

兰伯特的优化：
1.领导者（投票产生等）

2.领导者可以独立指定提案中的值。（领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段：解决提案冲突；减少往返消息数，提升性能，降低延迟）

Chubby实现的Multi-Paxos算法

1.引入主节点，主节点故障了就投票选出其他主节点（主节点一直存在且唯一，能容纳(n-1)/2个节点故障）

2.领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段（兰伯特）

3.实现成员变更，保证节点变更时集群的平稳运行

4.为了实现强一致性，读操作也只在主节点上执行（缺点：限制了集群处理读写请求的并发能力，此时其并发能力约等于单机的并发能力）

Raft算法

Raft算法属于Multi-Paxos算法，是一种用于分布式系统的一致性协议，在兰伯特的Multi-Paxos思想的基础上做了简化和限制（如要求日志连续；只支持领导者、跟随者、候选人三种模式，强领导者模型）。

Raft算法是现在分布式系统开发首选的共识算法。本质上说，Raft算法是通过一切以领导者为准的方式实现一系列值的共识和各节点日志的一致。

一系列值的共识
选举过程

Raft算法能够实现一个全局唯一的领导者，并在领导者失效或网络分区恢复时重新选举新的领导者，确保系统的可用性和一致性：

  1. 初始状态：当系统启动时，所有节点都处于初始状态，没有任何节点被选为领导者。
  2. 选举超时（Election Timeout）：每个节点都会定期随机选择一个选举超时时间，如果在该时间内没有收到来自当前领导者的心跳消息，则认为当前领导者失效，开始新一轮选举。
  3. 提出候选人（Candidate）：节点检测到选举超时后，会将自己转换为候选人，并向其他节点发送选举请求（RequestVote）。
  4. 收集投票：候选人发送选举请求后，其他节点会对该候选人进行投票。如果节点还没有投票给其他候选人，并且认可该候选人的合法性，则会投票给该候选人，并重置选举超时计时器。
  5. 当选领导者：如果候选人接收到了多数节点的投票，它就成为新的领导者。一旦成为领导者，它会发送心跳消息（AppendEntries）给其他节点，以维持自己的地位。
  6. 撤销选举：如果在选举过程中，候选人接收到了来自其他节点的心跳消息，表明有更高级别的领导者存在，则该候选人会放弃竞选并转为追随者状态。
节点间通信

在raft中，服务器节点间通信方式是RPC，在领导者选举中用到这两类：

请求投票RPC：由候选人在选举期间发起，通知各节点进行投票

日志复制RPC：由领导者发起，用来复制日志和提供心跳信息

任期

1.跟随者在领导者心跳信息超时并推举自己为候选人时会增加自己的任期编号

2.一个服务器节点发现自己的任期编号比其他节点小时会更新自己的编号到较大值

任期编号大小的影响：当一个候选人发现自己的任期编号比其他节点小，会立刻恢复成追随者状态；一个节点接收到一个包含较小的任期编号值的请求，会直接拒绝这个请求。

选举规则

1.领导者周期性地向所有跟随者发送心跳消息（不含日志项的日志复制RPC消息），阻止跟随者发起新的选举

2.指定时间内，跟随者没接收到领导者的心跳消息，认为当前没有领导者，同时推举自己为候选人，发起领导者选举

3.一次选举中获得大多数选票的候选人晋升为领导者

4.一个任期内，领导者一直都是领导者（强领导者），直到它出问题

5.先来先服务

6.日志完整性高的跟随者拒绝投票给日志完整性低的候选人（推优）

一个任期内，领导者定时发心跳消息给其他节点直到自己出问题，跟随者一旦没收到心跳消息就推选自己，当还没推选自己（还没超时）时就收到投票消息时，先推选这个请求投票的节点，日志完整性高的不给低的投票。

Raft算法中日志必须是连续的，日志不仅是数据的载体，日志的完整性还影响领导者选举的结果。

随机超时时间

处理选举无效问题，大多数情况下只有一个服务器先发起选举。两个含义：跟随者等待领导者心跳消息的超时时间随机；如果一个候选人在一个随机时间间隔内没有赢得超过半数票，选举无效，即等待选举超时的时间是随机的。

实现节点日志的一致
理想状态下的日志复制过程

日志项是一种数据格式（指令、索引值、任期编号）。

1.收到客户端请求后，领导者根据请求中的指令创建一个新日志项，附加到本地日志中

2.领导者通过日志复制RPC消息将新的日志项复制到其他服务器。

3.当领导者将日志项成功复制到大多数的服务器上时，领导者会将这条日志项应用到它的状态机中。

4.领导者将执行的结果返回给客户端。

5.当跟随者接收到心跳信息或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就会将这条日志项应用到本地的状态机中。

实现日志一致性

领导者通过日志复制RPC消息的一致性检查，找到跟随者节点上与自己相同的日志项的最大索引值。领导者和跟随者的日志在这个索引值之前是一致的，之后是不一致的。领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。

1.领导者发送当前最新日志项到跟随者

2.跟随者在日志项中找不到某些日志项，也就是说它的日志项和领导者不一致，跟随者会拒绝接受新的日志项并返回失败给领导者

3.如果是2的情况，领导者递减要复制的日志项的索引值并发送新的日志项到跟随者

4.直到跟随者找到该日志项，日志复制RPC消息返回成功

5.领导者通过日志复制RPC消息复制并更新该索引值之后的日志项，最终实现集群各节点日志的一致

跟随者中的不一致的日志项会被领导者的日志项覆盖，而领导者从来不会覆盖或删除自己的日志。

成员变更 单节点变更

成员变更的主要问题在于成员变更时，可能存在新旧配置里的两个“大多数”导致集群中同时出现两个领导者，破坏了Raft算法的领导者的唯一性原则，影响了集群的稳定运行。

单节点变更就是通过一次变更一个节点实现成员变更，如果需要变更多个节点，则需要执行多次单节点变更。

  1. 提议变更：当需要进行节点变更时，领导者会将变更请求作为一条特殊的日志条目附加到自己的日志中，并将此条目发送给其他节点。
  2. 日志复制和一致性：其他节点接收到领导者的日志条目后，会按照Raft算法的日志复制流程进行处理。它们会确认接收并持久化该条目，并将其复制到自己的日志中。
  3. 变更确认：一旦领导者发现新的日志条目已经被多数节点接收并持久化，它就会将变更标记为已提交，并将确认消息广播给其他节点。
  4. 节点状态更新：所有节点在接收到变更确认消息后，会根据具体的变更类型执行相应的节点状态更新操作。例如，如果是添加节点，节点会将新节点加入集群；如果是移除节点，节点会将对应节点从集群中删除。

需要注意的是，Raft算法的单节点变更会使得集群的任期号增加，触发新一轮的领导者选举。这是因为每个节点都会更新自己的任期号，并在变更操作中包含当前任期号。

不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。

在分区错误，节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，使集群出现两个领导者。

与Multi-Paxos的不同之处

1.raft不是所有节点都能当领导者，只有日志较完整的节点才能当领导者，Multi-Paxos所有节点都有可能

2.raft日志必须连续，Multi-Paxos没有这个要求

一致哈希算法

强领导者模型的缺点：集群的接入性能约等于单机，随着业务发展容易造成系统过载和服务不可用。

解决？分集群，哈希。哈希算法有个明显的缺点，当需要变更集群数量的时候大部分数据都需要迁移重新映射，大量的数据迁移成本过高。

一致哈希 实现KV存储的分集群

一致哈希算法是对2^32进行取模，将整个哈希空间组织成一个虚拟的圆环（哈希环）。

一致哈希算法（Consistent Hashing）是一种用于分布式系统中数据分片和负载均衡的算法。它通过将数据和节点映射到一个固定大小的哈希环上，使得数据能够均匀地分布在不同的节点上，并保持在节点增减时最小程度的数据迁移。

基本原理：

  1. 构建哈希环：将所有的节点和数据映射到一个相同的哈希环上。通常使用节点的唯一标识或者节点的哈希值作为哈希环上的位置。
  2. 数据路由：当有新的数据需要存储或查询时，将数据的哈希值映射到哈希环上。然后从该哈希值所在的位置开始顺时针查找，找到的第一个节点就是应该存储或查询该数据的节点。
  3. 节点增减：当有节点加入或离开集群时，只会对与新节点或离开节点相关的一小部分数据进行重新分配。具体而言，对于新增的节点，它会接管哈希环上两个相邻节点之间的数据；对于离开的节点，它的数据会被均匀分散到其他节点上。
  4. 均衡性：一致哈希算法通过让节点和数据在哈希环上均匀分布来实现负载均衡。节点的数量越多，数据分布得越均匀。

使用一致哈希算法在扩容或者缩容的时候，都只需要重定位环空间中的一小部分数据。一致哈希算法具有叫号的容错性和可拓展性。当节点变化时，只需要重新分配少部分数据，大部分数据仍然保持在原来的节点上，减小了系统的开销和影响。这使得一致哈希算法适用于构建高性能、可伸缩的分布式存储系统和缓存服务等场景。

通过用虚拟节点解决访问冷热不均的问题，即用多个map重定位。

通过增加节点数来降低节点宕机对集群的影响。

一致哈希算法本质上是一种路由寻址算法，适合简单的路由寻址场景，不需要维护路由信息。

ZAB协议

ZAB协议是ZooKeeper使用的一种原子广播协议，用于保持分布式系统的一致性和可靠性。

Multi-Paxos虽然能保证达成共识后的值不再改变，但是不关心达成共识后的值是什么，也无法保证操作的顺序性：

假设有三个节点A、B和C，并且A是领导者。现在有两个客户端操作请求，分别是"写操作1"和"写操作2"。

  1. A作为领导者接收到"写操作1"请求，并将该操作追加到自己的日志中。然后A向其他节点B和C发送附加日志请求以复制该操作。
  2. 在上述过程进行的同时，客户端又发送了"写操作2"请求，并被A接收，追加到日志中，并发送附加日志请求给B和C。由于网络和节点的延迟，B和C可能较晚才接收到"写操作2"的附加日志请求。
  3. 为了使Multi-Paxos协议达成一致，领导者A必须等待大多数节点响应并确认"写操作1"和"写操作2"的附加日志请求。如果此时B和C还未接收到"写操作2"的请求，它们无法确认该操作。
  4. 当B和C最终接收到"写操作2"的请求时，它们会将其追加到自己的日志中，并向A发送确认消息。只有当大多数节点（包括A、B和C）都确认了该操作，A才能将其标记为已提交。

由于延迟和网络问题，"写操作2"可能会在先于"写操作1"之前达到节点B和C。然而，Multi-Paxos无法保证操作的顺序性，因为它仅关注多数节点的一致性。尽管操作的结果最终是一致的，但操作的顺序可能并不符合客户端的预期。

Zab协议的核心设计目标是实现操作的顺序性，它是能保证操作顺序性的、基于主备模式的原子广播协议。

实现操作的顺序性

1.写操作必须在主节点进行，如果是备份节点收到请求，则转发给主节点

2.主节点收到写请求后，基于请求中的指令来创建提案，并使用唯一的ID来标识这个提案

3.主节点基于TCP协议并按照事务标识符大小顺序将提案广播到其他节点，保证先发送的消息先被接受到，进而保证消息的顺序性

4.最后主节点返回执行成功的响应给备份节点，备份节点再转发给客户端

（为了提供读并发能力，zk提供的是最终一致性，读操作可以在任意节点进行，可能读到旧数据）

领导者选举

主节点崩溃时，领导者选举选举出新的领导者，领导者选举关乎着节点故障容错能力和集群可用性，是Zab协议非常核心的设计之一。

Zab协议的成员身份有三种：领导者（同一时间集群只有一个领导者，所有的写请求必须在领导者节点上执行）、跟随者（作为备份节点，集群可以有多个追随者，响应领导者的心跳信息并参与领导者选举和提案提交的投票，跟随者可以直接处理响应客户端的读请求，但对于写请求要转发给领导者）、观察者（作为备份节点与跟随者类似，但没有投票权）。

四种成员状态：LOOKING（选举状态，该状态下的节点认为当前集群中没有领导者，会发起领导者选举）、FOLLOWING（跟随者）、LEADING（领导者）、OBSERVING（观察者）

本质是通过“见贤思齐，相互推荐”的方式选举领导者：

1.跟随者检测到连接领导者的读操作等待超时时，跟随者将自己的状态改为LOOKING然后发起领导者选举

2.每个节点会创建一张选票，这张选票投给自己（节点会先收到投给自己的选票）

3.节点读取接收到的投票信息，.为了选举出数据最完整的节点，节点对于每一张接收到的选票，都需要进行领导者PK，找出更适合作为领导者的节点（优先检查任期编号，选择任期编号大的节点；其次比较事务标识符的最大值，选择更大的事务标识符的最大值；再次比较集群ID，选择更大的集群ID）

4.提议的领导者赢得大多数选票时，变更节点状态，退出选举，否则重新读取投票信息

成员发现和数据同步不仅让新领导者正式成为领导者，确立了它的领导关系，还解决了各副本数据冲突的问题，实现了数据副本的一致性，使集群能够正常处理写请求。确立领导关系是指在成员发现(DISCOVERY)阶段，领导者和大多数跟随者建立连接，并再次确认各节点对自己当选领导者没有异议，从而确立自己的领导关系；处理冲突数据是指在数据同步(SYNCHRONIZATION)阶段，领导者以自己的数据为准，解决各节点数据副本不一致的问题。

ZAB集群的故障恢复

ZAB协议定义了4种状态来标识节点的运行状态：选举（ELECTION）、成员发现（DISCOVERY）、数据同步（SYNCHRONIZATION）、广播（BROADCAST）。

只有当集群大多数节点处于广播状态的时候，集群才能提交提案，ZAB集群中确立领导关系的步骤：

  1. 选举初始化：当一个新的ZAB服务节点加入集群时，它将发起一次选举初始化。节点会向其他节点发送选举请求，以获取它们的同意。
  2. 选举开始：当一个节点发起选举请求后，其他节点可以接受或拒绝该请求。节点会检查请求中的ZXID（ZooKeeper事务ID），如果请求中的ZXID比自己的最大ZXID还要小，则拒绝请求。否则，节点会投票给请求节点。
  3. 投票计数：每个节点都会记录收到的选举请求，并为每个请求节点进行投票计数。节点只会投一次票，且只能投给一个节点。
  4. 选举结果：当有节点获得半数以上的选票时，该节点成为新的领导者。选举结果会通过广播方式通知集群中的其他节点。
  5. 新领导者的角色：一旦选举结果确定，新领导者将开始处理客户端的请求，并广播事务日志给其他节点。其他节点将在收到领导者的广播后进行数据同步。

ZAB协议在成员发现阶段确立了领导者的领导关系，这样领导者就可以行使职能了。当进入数据同步状态之后，领导者会根据跟随者的事务标识符的最大值，判断以哪种方式处理不一致数据。

在ZK代码实现中，处于提交状态的提案是可能会改变的：

在ZooKeeper中，一个提案进入提交状态的方式有两种:被复制到大多数节点上和被领导者提交或接收到来自领导者的提交消息(leader.COMMIT)而被提交。在这种状态下，提交的提案是不会改变的。
另外，在ZooKeeper的设计中，节点在退出跟随者状态时(在follower. shutdown()函数中)会将所有本地未提交的提案都提交。需要注意的是，此时提交的提案可能并未被复制到大多数节点上，而且这种设计会导致ZooKeeper中出现处于“提交”状态的提案可能会被删除(也就是接收到领导者的TRUNC消息而删除的提案)的情况。
更准确地说，在ZooKeeper中，被复制到大多数节点上的提案最终会被提交，并不会再改变；而只在少数节点存在的提案可能会被提交和不再改变，也可能会被删除。

如果写请求对应的提案"SET X=1"已经复制到大多数节点上，那么它最终会被提交，之后也不会再改变。也就是说，在没有新的X赋值操作的前提下，不管节点怎么崩溃、领导者如何变更，你查询到的X的值都为1。
如果写请求对应的提案“SET X=1”未被复制到大多数节点上，比如在领导者广播消息过程中，领导者崩溃了，那么，提案“SET X=1”可能会被复制到大多数节点上提交并不再改变，也可能会被删除。这个行为是未确定的，具体取决于新的领导者是否包含该提案。

另外在ZAB协议选举出了新的领导者后，该领导者不能立即处理写请求，还需要通过成员发现、数据同步两个阶段进行故障恢复。这是由ZAB协议的设计决定的，不是所有的共识箕法都必须这样，比如通过Raft算法选举出新的领导者后，领导者是可以立即处理写请求的。

ZAB集群的故障恢复的两种方法

成员发现

领导者选举结束，节点进入跟随者状态或领导者状态后，会分别设置ZAB状态为成员发现状态→追随者发送FOLLOWINFO给领导者→领导者响应LEADINFO给追随者→追随者相应ACKEPOCH消息给领导者→跟随者设置ZAB状态为数据同步状态→领导者等待和接受大多数节点的ACKEPOCH消息→领导者设置ZAB状态为数据同步状态

数据同步

数据同步目标是确保追随者节点上的数据与领导者节点上的数据一致。

领导者根据追随者的事务标识符最大值选择数据同步方式，并将相关数据缓存在发送队列中→领导者创建NEWLEADER消息并缓存在发送队列中→领导者将缓存的数据发送给跟随者→跟随者修复不一致数据→跟随者返回NEWLEADER消息的响应给领导者→领导者等待来自大多数节点的NEWLEADER消息的响应→领导者设置ZAB状态为广播状态并发送UPTODATE消息给所有跟随者→跟随者设置ZAB状态为广播状态

领导者向跟随者同步数据的三种方式

领导者是以自己的数据为准，实现各节点数据副本的一致的。

三个关键变量：peerLastZxid（跟随者节点上提案的事物标识符的最大值），maxCommittedLog，minCommittedLog（领导者节点内存队列中已提交提案的事务标识符的最大值和最小值）

TRUNC:当peerLastZxid大于maxCommittedLog时，领导者会通知跟随者丢弃超出的那部分提案。比如，如果跟随者的peerLastZxid为11，领导者的maxCommittedLog为10，那么领导者将通知跟随者丢弃事务标识符值为11 的提案。

DIFF:当peerLastZxid 小于maxCommittedLog但大于minCommittedLog 时，领导者会向跟随者同步缺失的已提交的提案，比如，如果跟随者的peerLastZxid为9，领导者的maxCommittedLog为10， minCommittedLog为9，那么领导者将同步事务标识符值为10的提案给跟随者。

SNAP:当peerLastZxid 小于minCommittedLog 时，也就是说，跟随者缺失的提案比较多，那么，领导者会同步快照数据给跟随者，并直接覆盖跟随者本地的数据。

处理读写请求

对ZooKeeper而言，如何处理写请求关乎着操作的顺序性，会影响节点的创建；而如何处理读请求关乎着一致性，也影响着客户是否会读到旧数据。在zk中，写请求必须在领导者上处理，如果是跟随者接收到请求则要转发给领导者，当写请求对应的提案被复制到大多数节点上时，领导者会提交提案，并通知追随者提交提案。而读请求可以在所有的节点上处理，所以读性能是水平拓展的。所以，可以通过分集群的方式突破写性能的限制，并通过增加更多的节点来拓展集群的读性能。

写操作

（跟随者接收到写请求→跟随者将写请求转发给领导者→）领导者接受写请求，创建提案并持久化存储→领导者将提案广播给集群的所有节点又跟随者接收到提案，持久化存储，并返回确认响应给领导者→当领导者接收到大多数节点的确认响应后，广播COMMIT消息给跟随者→当跟随者接收到COMMIT消息后，提交提案（如果是自己接收到写请求，返回成功给客户端）

读操作

节点查询本地数据，响应数据给客户端即可。

ZAB协议与Raft算法

领导者选举:ZAB协议采用的是“见贤思齐、相互推荐”的快速领导者选举(Fast Leader Election)算法，Raft算法采用的是“一张选票、先到先得”的自定义算法。在我看来，Raft算法的领导者选举需要通信的消息数更少，选举也更快。

日志复制:Raft算法和ZAB协议都是以领导者的日志为准来实现日志一致，而且日志必须是连续的，也必须按照顺序提交。

读操作和一致性:ZAB协议的设计目标是操作的顺序性，在ZooKeeper中默认实现的是最终一致性，读操作可以在任何节点上执行；而Raft算法的设计目标是强一致性(也就是线性一致性)，所以Raft算法更灵活，它既可以提供强一致性，也可以提供最终一致性。

写操作:Raft算法和ZAB协议的写操作都必须在领导者节点上处理。

成员变更:Raft算法和ZAB协议都支持成员变更(其中ZAB协议是以动态配置的方式实现的)，所以在节点变更时，你不需要重启机器，因为集群是一直运行的，服务也不会中断。

其他:相比ZAB协议，Raft算法的设计更为简洁，比如Raft算法没有引入类似ZAB协议的成员发现和数据同步阶段，而是当节点发起选举时递增任期编号，在选举结束后广播心跳，直接建立领导者关系，然后向各节点同步日志，来实现数据副本的一致性。在我看ZAB协议的成员发现可以和领导者选举合到一起类似Raft算法在领导者选举结束后直接建立领导者关系，而不是再引入一个新的阶段；数据同步阶段是一个冗余的设计，可以去除，因为ZAB协议无须先实现数据副本的一致性，才可以处理写请求，而且这个设计是没有额外的意义和值的。ZAB协议与ZooKeeper强耦合，无法在实际系统中独立使用；而Raft算法的实现(比如Hashicorp Raft算法)是可以独立使用的，编程友好。

在ZAB协议中，主节点是/基于TCP协议关广播消息的，且保证了消息接收的顺序性。如果ZAB采用的是UDP协议，能保证消息接收的顺序性吗？为什么呢？

无法保证消息接收的顺序性。这是因为UDP是一种无连接、不可靠的传输协议，它不会对数据包进行确认和重传，也不会保持数据包的顺序。

在UDP中，发送方将数据分割成小的数据包，并尽可能快地发送出去，而接收方则根据数据包的到达顺序进行处理。但由于网络环境的不稳定性，数据包可能会丢失、重复或乱序到达。UDP不提供任何机制来纠正这些问题。

因此，如果ZAB使用UDP协议进行广播消息，就无法保证消息的接收顺序性。这样可能会导致数据的冲突、不一致或错误，破坏了ZAB协议的一致性保证。

相比之下，TCP是一种面向连接、可靠的传输协议。TCP通过序列号、确认机制和重传等功能，确保数据按照发送的顺序到达接收方，并提供了保证数据完整性的机制。这使得ZAB协议能够依赖TCP协议来实现消息的有序传输和一致性保证。

ZAB协议是通过快速领导者选举来选举出新的领导者的。那么选举中会出现选票被瓜分、选举失败的问题吗？为什么呢？

在ZAB协议中，快速领导者选举确实存在选票被瓜分和选举失败的问题。这是因为当多个节点同时发起选举，并且彼此没有达成共识时，选票可能会被分散到不同的候选人上，从而导致选举无法达成共识。

以下是可能导致选票被瓜分和选举失败的情况：

  1. 同时发起选举：如果多个节点同时检测到当前集群没有有效的领导者，并发起选举请求，那么选票可能会被瓜分到不同的候选人上。
  2. 网络延迟或分区：当网络延迟或分区发生时，节点之间的通信可能受到影响。这可能导致选举请求在部分节点之间无法及时进行广播，进一步导致选票被瓜分。
  3. 节点故障或重启：如果正在执行选举的节点在选举过程中发生故障或重启，其他节点可能会继续进行选举，导致选票分散。

由于以上原因，选举中存在选票被瓜分和选举失败的风险。为了应对这些问题，ZAB协议采用了一些机制来尽量避免选票的分散和选举的失败：

  1. 递增的ZXID：每个节点的选举请求中都包含一个递增的ZXID（ZooKeeper事务ID）。其他节点会比较收到的选举请求的ZXID，只有当请求中的ZXID更大时，才会投票给该节点。这样可以避免较小ZXID的节点成为领导者。
  2. 选票计数：每个节点会记录收到的选举请求，并对每个请求进行计数。只有在获得多数节点的投票时，候选人才能成为新的领导者。这样能够确保选举结果的一致性。
  3. 选举超时时间：选举过程中使用了超时机制，如果某个节点在规定时间内没有获得多数投票，它将放弃竞选并重新发起选举。这有助于防止选举陷入死锁状态。

尽管ZAB协议采取了上述机制来尽量避免选票被瓜分和选举失败，但仍然存在极端情况下选票瓜分的可能性。在这种情况下，系统运维人员需要检查网络连接、节点配置等因素，以解决选举问题并确保集群正常运行。

ZooKeeper提供的是最终一致性，读操作可以在任何节点上执行。如果读操作访问的是备份节点，为什么无法保证每次都能读到最新的数据呢？

因为备份节点可能存在数据复制的延迟。

以下是造成备份节点无法保证每次都读取到最新数据的原因：

  1. 数据复制延迟：当领导者节点接收到写操作后，它会将该操作广播给其他节点进行数据复制。然而，由于网络延迟或其他因素，备份节点可能无法立即接收并复制最新的数据。这会导致备份节点的数据与领导者节点的数据存在一定的时间差。
  2. 客户端路由策略：ZooKeeper的客户端通常采用一种路由策略，将读请求发送到就近的节点。这可能导致读请求被发送到备份节点而不是领导者节点。如果备份节点还没有复制最新的数据，那么读请求就无法获取到最新的数据。

尽管备份节点无法保证每次都读取到最新的数据，但是在ZooKeeper中，客户端可以通过设置相应的读操作模式来选择读请求的一致性级别。例如，可以使用"READ_UNCOMMITTED"模式来实现更低的一致性要求，允许读取到稍旧的数据。

为了确保读取到最新的数据，建议客户端在读操作时优先选择领导者节点进行读取。这样可以提高读取到最新数据的几率。如果对于应用程序来说对于读取的实时性要求很高，可以考虑使用更高级别的一致性模式（如"READ_COMMITTED"或"SERIALIZABLE"）来确保更强的一致性保证。

Gossip协议

顾名思义，类似流言，指利用一种随机、带有传染性的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。

如何实现最终一致性？

Gossip协议的三板斧
直接邮寄

指直接发送新数据，当发送失败时，直接发送更新数据，将数据缓存下来然后重传。但有可能因为缓存队列满了而丢失数据。

直接邮寄是一定要实现的，因为不需要做一致性对比，性能损耗低。

反熵

集群中的节点每隔一段时间就随机选择一个其他节点通过互相交换自己的所有数据来消除两者之间的差异，最终实现数据一致性。

方式：拉（获得对方副本节点数据）、推（将本身副本数据发给对方）、推拉（双方互相发送副本数据）

虽然反熵实用，但执行反熵操作时，相关节点都是已知的而且节点数量不能太多，如果是一个动态变化或者是节点数多的分布式环境就不适用了。此时要用到谣言传播。

反熵需要做一致性对比，非常消耗系统资源，建议做成可配置的，方便按需使用。

谣言传播

广泛性地传播谣言，当一个节点有了新数据后，这个节点就会变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有节点都存储了该数据。谣言传播非常具有传染性，适合动态变化的分布式系统。

Quorum NWR算法

适应强一致性（不是最终一致性这种有延迟的）的应用场景，可以自定义一致性级别。

Quorum NWR的三要素
N

表示副本数（集群中同一份数据有多少个副本）。副本数不等于节点数，不同的数据可以有不同的副本数。可以指定副本数。不推荐副本数超过当前的节点数（鸽巢原理），同个节点会出现相同副本，当这个节点有故障时，上面的多个副本都会受到影响。N决定了副本的冗余备份能力。

W

写一致性级别，表示成功完成W个副本更新才算完成写操作。如果设置W=N则读性能比较好。

R

读一致性级别，表示读取一个数据对象时需要读取R个副本。读取指定数据时要读取R个副本，然后返回R个副本中最新的那份数据。如果设置R=N则写性能比较好。

如果设置W=(N+1)/2、R=(N+1)/2则容错能力比较好，能容忍最多(n-1)/2的故障。

N、W、R的值的不同组合会产生不同的一致性效果：W+R>N时，对客户端来说整个系统能保证强一致性，即一定能返回更新后的那份数据；当W+R≤N时，对于客户端来说，整个系统只能保证最终一致性，即可能会返回旧数据。

MySQL XA

实现多个MySQL数据库更新的一致性。

XA规范

XA规范约定的是DTP（分布式事务处理）模型中的两个模块（事务管理器和资源管理器）的通信方式。

MySQL XA性能不高，适合在并发性能要求不高的场景中。

DTP

DTP各模块：AP（Application Program，应用程序，一般指事务的发起者，定义事务对应的操作）、RM（Resource Manager，资源管理器，管理共享资源并提供访问接口供外部程序来访问共享资源）、TM（Transaction Manager，事务管理器，一般指分布式事务的协调者）。应用程序访问、使用资源管理器的资源，并通过事务管理器的事务接口(TX
interface)定义需要执行的事务操作，然后事务管理器和资源管理器会基于XA规范，执行二阶段提交协议。

XA规范约定了事务管理器和资源管理器之间双向通信的接口规范，并实现了二阶段提交协议。

XA规范流程

1)AP(应用程序)联系TM(事务管理器)发起全局事务；
2)TM调用ax_open()建立与资源管理器的会话；
3)TM调用xa_start()标记事务分支(Transaction Branch)的开头；
4)AP访问RM(资源管理器)并定义具体事务分支的操作，比如更新一条数据记录(UPDATE executed_table SET status=true WHERE id=100)和插入一条数据记录(INSERT into operation_table SET id=100, op-'get-cdn-1og');
5)TM调用xa_end()标记事务分支的结尾；
6)TM调用xa_prepare()通知RM做好事务分支提交的准备工作，比如锁定相关资源，也就是执行二阶段提交协议的提交请求阶段；
7)TM调用xa_commit)通知RM提交事务分支(xa rol1back(通知RM回滚事务)，也就是执行二阶段提交协议的提交执行阶段；
8)TM调用xa_close()关闭与RM的会话。

可以这样理解:xa_ start()和xa_end()在准备和标记事务分支的内容，然后调用xa_prepare()和xa_commit()(或者xa_ rollback()) 执行二阶段提交协议，实现操作的原子性。注意，这些接口需要按照一定顺序执行，比如xa_start()必须在xa end()之前执行。另外，事务管理器对资源管理器调用的xa start()和xa end()这对组合，一般用于标记事务分支(就像上面的更新一条数据记录和插人一条数据记录)的开头和结尾。

对于同一个资源管理器，根据全局事务的要求，可以前后执行多个操作组合，比如，先标记一个插人操作，再标记一个更新操作；事务管理器只是标记事务，并不执行事务，最终是由应用程序通知资源管理器来执行事务操作的。
另外，XA规范还约定了如何向事务管理器注册和取消资源管理器的API接口(也就是ax reg()和ax unreg()接口)。这里需要注意的是，这两个接口是以 ax开头的，而不是像xa_start())那样以xa_开头。

能否将XA END和XA PREPARE合并到一起？

不能，因为在XA END之后，我们是可以直接执行XA COMMIT命令的，也就是一阶段提交(比如当共享资源变更只涉及一个RM时)。

如何通过MySQL XA实现分布式事务

实现全局事务的一致性

1.创建一个唯一的事物ID来唯一标识事物，并调用XA START和XA END来定义事务分支对应的操作

2.调用XA PREPARE来执行二阶段提交协议的提交请求阶段

3.调用XA COMMIT来提交事务

想要开启MySQL的XA功能就必须设置存储引擎为InnoDB（在MySQL中只有InnoDB支持XA规范）

局限

XA规范保证了全局事务的一致性，实现成本较低，而且得到了包括MySQL 在内的主流数据库的支持。但是因为XA规范是基于二阶段提交协议实现的，所以它也存在二阶段提交协议的局限：
1.单点问题，因为事务管理器在整个流程中扮演的角色很关键，如果其宕机，比如第一阶段已经完成了，在第二阶段正准备提交的时候，事务管理器宕机了，那么相关的资源会被锁定，无法访问。
2.资源锁定，在进入准备阶段后，资源管理器中的资源将处于锁定状态，直到提交完成或者回滚完成才能解锁。

在MySQLXA 不能满足并发需求时，我们应该如何重新设计底层数据系统，来避免采用分布式事务呢？为什么呢？

简答：分库分表

  1. 水平分片：将数据按照某个维度（如用户ID、地理位置等）进行水平分片，使每个分片都存储部分数据。这样可以将并发请求均匀地分散到不同的分片上，减少多个事务之间的冲突。
  2. 读写分离：将读和写操作分离到不同的数据库实例或节点上。通过复制或异步复制，将写操作传播到所有写实例，而读操作则可以从任意实例中获取。这样可以提高读取性能，并降低对分布式事务的需求。
  3. 异步处理：将一些不需要立即保证一致性的操作异步化，将其移出事务范围。例如，可以将某些独立的写操作转换为异步任务，通过消息队列或事件驱动的方式处理。这样可以减少事务的执行时间，提高并发能力。
  4. 分布式缓存：引入分布式缓存（如Redis、Memcached等），将经常访问的数据缓存在内存中，减少对数据库的访问次数。通过缓存数据，可以提高读取操作的性能和响应时间，并减轻底层数据库的负载。
  5. 业务拆分：考虑重新设计业务逻辑，将原本需要跨多个数据库事务的操作拆分成独立的事务。通过引入更细粒度的事务边界，可以降低分布式事务的需求，并提高并发性能。

重新设计底层数据系统的目标是降低对分布式事务的依赖，同时确保系统的可靠性和性能。具体的方案应根据具体业务需求和场景进行选择和实施。重点是分散并发请求、减少事务冲突、提高读取性能和引入异步处理等措施。

TCC

实现指令执行的原子性。

（引用上文）三个阶段：预留（try），确认（confirm），撤销（cancel）。关系图：

预留 → 确认
↑  ↓
撤销

对比二阶段提交协议，预留类似提交请求，确认类似提交执行，撤销类似回滚。本质上是补偿事务，核心思想是为每个操作都注册一个与其对应的确认操作和补偿操作（也就是撤销操作）。因为TCC的每一个操作对于数据库来讲，都是一个本地数据库事务，所以当操作结束时，本地数据库事务的执行就完成了，相关的数据库资源也就被释放了，这就避免了数据库层面的二阶段提交协议长时间锁定资源，导致系统性能低下的问题。

为什么TCC能解决指令执行的原子性问题？

通过将操作分解为try comfirm cancel，实现原子性，每个阶段都有对应的逻辑来确保操作的可靠执行，如果任何一个参与者出错或失败，系统都能用事务回滚恢复到初始状态。

TCC与XA对比

1.TCC是个业务层面的分布式事务协议，而XA规范是数据层面的分布式事务协议，这也是TCC和XA规范的最大区别。TCC与业务紧密耦合，在实际场景中，需要我们根据场景特点和业务逻辑来设计相应的预留、确认、撤销操作。相比MySQL XA,TCC有一定的编程开发工作量。
2.因为TCC是在业务代码中编码实现的，所以，TCC 可以跨数据库、跨业务系统实现资源管理，满足复杂业务场景下的事务需求。比如，TCC可以将对不同的数据库、不同业务系统的多个操作通过编码方式转换为一个原子操作，实现事务。

PBFT算法

PBFT（Practical Byzantine Fault Tolerance）算法是一种拜占庭容错的共识算法，用于解决分布式系统中存在节点故障和恶意行为的问题。它允许系统在存在最多f个恶意节点的情况下保持安全性和一致性。

PBFT算法是通过签名(或消息认证码MAC)来约束恶意节点的行为，同时采用三阶段协议，基于大多数原则达成共识的。与口信消息型拜占庭问题之解(以及签名消息型拜占庭问题之解)不同的是，PBFT算法实现的是一系列值的共识，而不是单值的共识。

客户端通过等待f+1个相同响应消息超时来发现主节点可能在作恶，此时客户端会发送客户端请求给所有集群节点，从而触发可能的视图变更。与Raft算法在领导者选举期间服务不可用类似，在视图变更时，PBFT集群也是无法提供服务的（只有经过视图变更后，新选举出的主节点才具备对客户端请求处理的权限。视图变更时，备份节点可以继续处理读请求并提供最近已提交的状态作为响应，保证系统的可用性和读一致性。）。

PBFT算法的优点包括高吞吐量、低延迟和容忍f个恶意节点。然而，它的缺点是需要较高的通信复杂性和一定的网络延迟，因为每个节点都需要与其他节点进行通信和交互。

PBFT算法的局限 解决办法

在一般情况下，每个节点都需要持久化保存状态数据(比如准备消息)，以便后续使用。但随着系统运行，数据会越来越多，最终肯定会出现存储空间不足的情况。

解决：检查点机制。PBFT算法实现了检查点机制，来定时清理节点缓存在本地但已经不再需要的历史数据(比如预准备消息、准备消息和提交消息)，节省了本地的存储空间，且不会影响系统的运行。

基于数字签名的加解密非常消耗性能（这也是为什么在一些对加解密要求高的场景中，大家常直接在硬件中实现加解密，比如IPSEC VPN）。如果在PBFT算法中，所有消息都是签名消息，那么肯定非常消耗性能，且会极大地制约PBFT算法的落地场景。有什么办法优化这个问题呢？

解决：将数字签名和消息验证码(MAC)混合使用。具体来说，在PBFT算法中，只有视图变更消息和新视图消息采用签名消息，其他消息则采用消息验证码，这样一来，就可以节省大量加解密的性能开销。

相比Raft算法完全不适应有人作恶的场景，PBFT算法能容忍 (n-1)/3个恶意节点(也可以是故障节点)。另外，相比 PoW算法，PBFT算法的优点是不消耗算力，所以在日常实践中，PBFT算法比较适用于相对“可信”的场景，比如联盟链。

PBFT算法实际应用情况

PBFT算法是一个能在实际场景中落地的拜占庭容错算法，它和区块链也结合紧密：相对可信、有许可限制的联盟链，比如Hyperledger Sawtooth；与其他拜占庭容错算法结合来落地公有链。建议根据场景的可信度来决定是否采用PBFT算法，是否改进和优化 PBFT算法。

PoW算法

口信消息型拜占庭问题之解、PBFT算法虽然能防止坏人作恶，但只能防止少数人，也就是(n-1)/3个坏人。

工作量证明

通过指定的结果来证明自己做过一定量的工作。

在比特币的区块链中，PoW算法通过SHA256哈希运算计算出符合指定条件的哈希值来证明工作量。

区块链如何实现PoWer算法

区块链过对区块头进行SHA256哈希运算得到小于目标值的哈希值来证明自己的工作量，计算出符合条件的哈希值之后，矿工就会把这个信息广播给集群中所有其他节点，待其他节点验证通过后，他们会将这个区块加入自己的区块链中。最终形成一条区块链。

算力越强，系统大概率会越先计算出这个值。长久来看，攻击者攻击成功的概率等同于攻击者算力的权重。51%攻击的本质是因为比特币的区块链约定了“最长链胜出，其他节点在这条链基础上拓展”，所以攻击者可以通过优势算力实现对最长链的争夺。除了通过PoW算法增加坏人作恶的成本，比特币还通过“挖矿得币”奖励好人，最终保证了整个系统的稳定运行。