[系统运维]拜占庭将军问题

拜占庭将军问题

什么是拜占庭将军问题？

• 故事影射的问题

  1. 拜占庭将军问题是一个协议问题，只有所有将军达成共识，一同攻击某个敌军，才能成功。（目的是达成共识，且结果代表大多数人的意见）
  2. 分散的军队，军队内可能有叛徒和敌军间谍，左右将军们的决策。在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。（在缺少可信任的中央节点和可信任的通道的情况下，分布在网络中的各个节点应如何达成共识）
  3. 拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。（点对点通信，在存在消息丢失的不可靠信道上试图通过消息传递方式达到一致性是不可能的）
  

• 问题剖析

  1. 身份追溯
  2. 信息私密
  3. 防伪签名
  4. 传递规则
  

• 解决方法：区块链

  1. 随机成本（哈希算法工作量）
  区块链轻而易举地解决了这一问题，它为信息发送加入了成本，降低了信息传递的速率，而且加入了一个随机元素使得在一定时间内只有一个将军可以广播信息。这里所说的成本就是区块链系统中基于随机哈希算法的“工作量证明”。哈希算法所做的事情就是计算获得的输入，得到一串64位的随机数字和字母的字符串。
  
  2. 控制节奏(10分钟的运算量)
  算的输入数据是指节点发送的当前时间点的整个总账。当前计算机的算力使其可以实时计算出单个哈希值，但是区块链系统只接受前13个字符是0的哈希值结果作为“工作量证明”。而前13个字符是0的哈希值是非常罕见的，需要整个网络花费10分钟的时间才在数以亿计的数据中找到一个。在一个有效的哈希值被计算出来之前，网络中已经生产了无数个无效值，这就是降低信息传递速率并使得整个系统成功运行的“工作量证明”。
  

• 每个比特币交易账号可以看作一个将军

  哈希算法对信息传递速率的限制加上加密工具使得区块链构成了一个无须信任的数据交互系统。在区块链上，一系列的交易、时间约定、域名记录、政治投票系统或者任何其他需要建立分布式协议的地方，参与者都可以达成一致。
  

• 区块链思想：

  1. 去中心化，避免依赖第三方中心平台的信任担保。
  2. 只可记录，不可修改（约束）。
  3. 记账有回报，记账有成本（算力）。
  4. 最长账单链为有效链条（公共约束力，增加作恶算力成本）。
  

拜占庭将军问题与PAXOS算法中的希腊民主选举问题有什么区别？

1. 拜占庭将军问题：在不可靠信道上试图通过消息传递的方式达到一致性是不可能的（Leslie Lamport证明，当叛徒不到1/3时，存在有效的算法，不论叛徒如何折腾，忠诚的将军们总能达成共识。当叛徒达到三分之一时，则无法保证一定能达成一致性）。
2. Paxos算法的前提是：不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传递的消息是不会被篡改的。

ZAB与PAXOS什么关系？

1. Zookeeper Atomic Broadcast，zk原子性广播协议。
2. ZAB是Paxos的工业实现，目的是构建一个高可用的分布式数据主从系统，follower是leader的从机，leader挂了可以马上从follower选一个leader。ZAB为了解决活锁问题，只允许一个进程提交提案，属于3PC提交。而leader挂了时候选举算法是2PC，所有的follower都可以提交，就是我选我。

如何理解2PC与3PC的区别？

PAXOS算法分为贿选阶段（prepare->promise）+提议阶段（propose->accept）。
在具体的实现过程中，需要对整个选举过程进行模拟，PAXOS算法模型中，所有节点都是对等的（选举与贿选都可以），具体实现的过程中，为了解决“活锁”的问题，引入了“总统/领导”的概念（主从模式）。
方法一： 2PC，即二阶段模拟方式，存在问题：
	1. 二阶段的 prepare 和 commit 中，prepare 到 commit 的过程，需要锁定资源，同步阻塞导致性能下降。
	2. 主节点宕机挂掉，在选举出新的主节点之前，所有从节点阻塞。
	3. commit 阶段，网络延迟、丢包导致从节点事务状态分歧（仅部分成功提交），导致整个分布式系统出现数据不一致现象。

	由于二阶段提交存在着诸如同步阻塞、协调者宕机后阻塞、脑裂等缺陷等问题，所以研究者们在二阶段提交的基础上做了改进，提出了三阶段提交。

方法二： 3PC，即三阶段模拟方式。
	与二阶段相比，三阶段：
		1. 引入超时机制：同时在协调者和参与者中都引入超时机制。
		2. 在第一阶段和第二阶段中插入一个准备阶段：保证了在最后提交阶段之前各参与节点的状态是一致的，即三阶段提交就有 CanCommit（无锁状态）、PreCommit（无锁状态）、DoCommit 三个阶段。
	存在问题：
		1. 三阶段的超级机制，解决了阻塞问题。
		2. CanCommit的预先铺垫 过渡到 PreCommit 的预备阶段，相当于让我们有理由相信 DoCommit 成功提交的几率很大，但是由于网络原因导致的数据不一致问题依然存在。

Reference

• https://www.jianshu.com/p/8bcef0ca676c（拜占庭将军问题快速理解）
• https://baike.baidu.com/item/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98/265656?fr=aladdin（拜占庭将军问题）
• https://baike.baidu.com/item/%E4%B8%AD%E6%9C%AC%E8%81%AA/5740822?fr=aladdin（中本聪）
• https://www.jianshu.com/p/8bcef0ca676c（拜占庭将军问题快速理解）
• https://juejin.cn/post/6844904114443436039（面试官：能聊聊Paxos算法和ZAB协议吗）
• https://www.jianshu.com/p/30a18e4ef16e（2pc和3pc的详解与对比）
• https://blog.csdn.net/qq_41946557/article/details/102770531（分布式系统之Paxos选举协议）