参考文献

共识简介

  • 所谓共识，简单理解就是指大家都达成一致的意思.

拜占庭容错算法

工作量证明(PoW,Proof of Work)

  • 简单理解就是一份用来确认你做过一定量的工作的证明。监测工作的整个过程通常是极为低效的，而通过对工作的结果进行认证来证明完成了相应的工作量，则是一种非常高效的方式。比如现实生活中的毕业证、驾驶证等等，也是通过检验结果的方式(通过相关的考试)所取得的证明。
  • 工作量证明系统(或者说协议、函数)，是一种应对拒绝服务攻击和其他服务滥用的经济对策。它要求发起者进行一定量的运算，也就意味着需要消耗计算机一定的时间。

实用拜占庭容错算法(PBFT：Practical Byzantine Fault Tolerance)

非拜占庭容错算法/故障容错算法（Crash Fault Tolerance，CFT）

  • CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。 也就是说，这个场景可能会丢失消息，或者有消息重复，但不存在错误消息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议.

Paxos

  • Paxos 是由Leslie Lamport(就是大名鼎鼎的LaTeX中的“La”)提出的一种基于消息传递的协商共识算法
算法流程
  • 提案节点：称为Proposer，提出对某个值进行设置操作的节点，设置值这个行为就被称之为提案(Proposal)，值一旦设置成功，就是不会丢失也不可变的。请注意，Paxos是典型的基于操作转移模型而非状态转移模型来设计的算法，这里的“设置值”不要类比成程序中变量赋值操作，应该类比成日志记录操作.
  • 决策节点：称为Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，即称该提案被批准(Accept)，提案被批准即意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受该它.
  • 记录节点：被称为Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案，譬如少数派节点从网络分区中恢复时，将会进入这种状态
  • 使用 Paxos 算法的分布式系统里的，所有的节点都是平等的，它们都可以承担以上某一种或者多种的角色，不过为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，且在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息

PAFT

  • RAFT是一种共识算法，它被分解成了相对独立的子问题。共识是指多台服务器或进程在一些值上达成一致的过程.RAFT确保了一致性，使得同一序列的命令产生相同序列的结果，并在所部署的各个成员中达到相同序列的状态.
  • 副本集成员相互间每隔两秒发送一次心跳(heartbeat，也就是 ping)。如果某个成员在 10秒内没有反馈心跳，则其他成员会将该不良成员标记为无法访问。选举算法将尽“最大努力”尝试让具有最高优先权的从节点发起选举。成员优先权会影响选举的时机和结果。优先级高的从节点要比优先级低的从节点更快地发起选举，而且也更有可能成为主节点。然而，低优先级的从节点也可能短暂地被选为主节点，即使还存在一个可用的高优先级从节点。副本集成员会继续发起选举直到可用的最高优先级成员被选为主节点。
  • 就所有能连接到的成员，被选为主节点的成员必须拥有最新的复制数据。严格地说，所有的操作都必须比任何一个成员的操作都要高，因此所有的操作都必须比任何一个成员的操作都要晚。

算法选择

如何在实际场景选择合适的算法类型呢？

  • 答案是：如果能确定该环境中各节点是可信赖的，不存在篡改消息或者伪造消息等恶意行为（例如 DevOps 环境中的分布式路由寻址系统），推荐使用非拜占庭容错算法；反之，推荐使用拜占庭容错算法，例如在区块链中使用 PoW 算法。