01 | 拜占庭将军问题：有叛徒的情况下，如何才能达成共识？

• Q:二忠一叛难题
  • 假设3个国家齐、楚、燕要攻打秦国，以只有半数以上的将军参与进攻，才能击败敌人，在这个期间，将军们彼此之间需要通过信使传递消息，然后协商一致之后，并让信使传递信息，按照“少数服从多数”的原则投票表决，然后在同一时间点发动进攻
  • 但若有人暗通秦国出现作战计划不一致的情况。比如齐向楚、 燕分别发送了“撤退”的消息，燕向齐和楚发送了“进攻”的消息。撤退：进攻 =1:1，无 论楚投进攻还是撤退，都会成为 2:1，这个时候还是会形成一个一致性的作战方案
  • 但是，楚这个叛徒在暗中配合秦国，让信使向齐发送了“撤退”，向燕发送了“进攻”，那么：
  • 燕看到的是，撤退：进攻 =1:2
  • 齐看到的是，撤退：进攻 =2:1。
  • 按照“少数服从多数”的原则，就会出现燕单独进攻秦军，当然，最后肯定是因为寡不敌众，被秦军给灭了
  • 
• Q:口信消息型拜占庭问题之解
  • 增加讨论中忠诚将军的数量，由3位将军变为4位将军。并约定如果没有收到命令，就执行预设的默认命令如“撤退”。以及进行两轮作战信息协商
  • 第一轮
    • 先发送作战信息的将军作为指挥官，其他的将军作为副官
    • 指挥官将他的作战信息发送给每位副官
    • 每位副官，将从指挥官处收到的作战信息，作为他的作战指令；如果没有收到作战信 息，将把默认的“撤退”作为作战指令
  • 第二轮
    • 除了第一轮的指挥官外，剩余的 3 位将军将分别作为指挥官，向另外 2 位将军发送作战信息；
    • 然后，这 3 位将军按照“少数服从多数”，执行收到的作战指令
  • 这个解决办法实现了作战计划的一致性
  • 如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了
  • 这个算法的前提是，叛将人数m是已知的，这个算法中，叛将数m决定递归循环的次数，即m+1轮
• Q:签名消息型拜占庭问题之解
  • 通过签名的方式，可在不增加将军人数的情况下，解决二忠一叛的难题
  • 签名的特性：
    • 忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现
    • 任何人都能验证将军签名的真伪
  • 
  • 
• Q:拜占庭容错算法和非拜占庭容错算法
  • 拜占庭将军问题描述的是最困难的，也是最复杂的一种分布式故障场景，除了存在故障行为，还存在恶意行为的一个场景。必须使用拜占庭容错算法（Byzantine Fault Tolerance，BFT）。还有：PBFT 算法，PoW 算法
  • 在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错算法（Crash Fault Tolerance，CFT）。CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。这个场景可能会丢失消息，或者有消息重复，但不存在错误消息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议

02 | CAP理论：分布式系统的PH试纸，用它来测酸碱度

• Q:CAP的三个指标
  • 一致性Consistency：客户端的每次读操作，不管访问哪个节点，要么读到的都是同一份最新的数据，要么读取失败，强调的是各节点间的数据一致
  • 可用性Availability：任何来自客户端的请求，不管访问哪个节点，都能得到相应数据，但不保证是同一份最新数据，强调的是服务可用，但不保证数据的一致
  • 分区容错性Partition Tolerance：当节点间出现任意数量的消息丢失或高延迟时，系统仍然可以继续提供服务，强调的是集群对分区故障的容错能力
• Q:CAP不可能三角
  • 是对于一个分布式系统而言，一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance）3 个指标不可兼得，只能在 3 个指标中选择 2 个
  • 
  • 在不存在网络分区的情况下，即分布式系统正常运行时（这也是系统在绝大部分时候所处的状态），就是说在不需要 P 时，C 和 A 能够同时保证。只有当发生分区故障的时候，也就是说需要 P 时，才会在 C 和 A 之间做出选择。而且如果各节点数据不一致，影响到了系统运行或业务运行（也就是说会有负面的影响），推荐选择 C，否则选 A
• Q:CAP的三个模型
  • CA 模型，在分布式系统中不存在。因为舍弃 P，意味着舍弃分布式系统，就比如单机版关系型数据库 MySQL，如果 MySQL 要考虑主备或集群部署时，它必须考虑 P
  • CP 模型，采用 CP 模型的分布式系统，一旦因为消息丢失、延迟过高发生了网络分区，就影响用户的体验和业务的可用性。因为为了防止数据不一致，集群将拒绝新数据的写入，典型的应用是 ZooKeeper，Etcd 和 HBase
  • AP 模型，采用 AP 模型的分布式系统，实现了服务的高可用。用户访问系统的时候，都能得到响应数据，不会出现响应错误，但当出现分区故障时，相同的读操作，访问不同的节点，得到响应数据可能不一样。典型应用就比如 Cassandra 和 DynamoDB

03 | ACID理论：CAP的酸，追求一致性

• Q:二阶段提交协议
  • 提交请求阶段（又称投票阶段）
    • 协调者(Coordinator)向所有节点发起请求，各节点评估事务中需要操作的对象和对象状态，是否准备好，能否提交新操作。如果能，预留时间并锁定，不再安排其它事务
    • 这个阶段每个参与者投票表决事务是放弃还是提交。一旦参与者投票要求提交事务，那么就不允许放弃事务。在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己那一部分，即使参与者出现故障或者中途被替换掉。这个特性，是需要在代码实现时保障的
  • 提交执行阶段（又称完成阶段）
    • 事务的每个参与者执行最终统一的决定，提交事务或者放弃事务，这个是为了实现ACID中的原子性
• Q:原始的二阶段提交协议和 XA 协议存在的问题是
  • 在提交请求阶段，需要预留资源，在资源预留期间，其他人不能操作（比如，XA 在第一阶段会将相关资源锁定）
  • 数据库是独立的系统
  • 因此无法根据业务特点弹性地调整锁的粒度，这些都会影响数据库的并发性能
• Q:TCC(Try预留-Confirm确认-Cancel取消)
  • 预留阶段
    • 协调者注册确认操作和撤销操作，各个节点预留资源，并返回消息答复
  • 确认阶段
    • 协调者执行确认操作，各节点收到确认操作的响应，完成分布式事务
  • 撤销阶段
    • 如果预留阶段出错，则进入撤销阶段
    • 协调者执行撤销操作，通知各个节点取消事务执行，并返回撤销操作的响应
  • TCC 本质上是补偿事务，核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作（也就是撤销操作）
  • TCC 不依赖于数据库的事务，而是在业务中实现了分布式事务，这样能减轻数据库的压力，但对业务代码的入侵性也更强，实现的复杂度也更高
  • 荐在需要分布式事务能力时，优先考虑现成的事务型数据库（比如 MySQL XA），当现有的事务型数据库不能满足业务的需求时，再考虑基于 TCC 实现分布式事务

04 | BASE理论：CAP的碱，追求可用性

• Q:BASE理论
  • 基本可用(Basically Available)
  • 最终一致性(Eventually consistent)
  • 软状态(Soft state)：实现服务可用性的时候系统数据的一种过渡状态，即不同节点间，数据副本存在短暂的不一致
• Q:实现基本可用的 4 板斧
  • 流量削峰：将访问请求错开，削弱请求峰值
  • 延迟响应：把请求放在队列中排队等待，一段时间后，系统开始处理，并响应处理结果
  • 体验降级：通过降低图片清晰度和大小，提升系统的处理能力
  • 过载保护：把接收到的请求放在指定的队列中排队处理，如果请求等待时间超时了，直接拒绝超时请求；队列满了之后，清楚队列中一定数量的排队请求，保护系统不过载
• Q:实际工程实践中何实现最终一致性以什么为准
  • 以最新写入的数据为准，比如 AP 模型的 KV 存储采用的就是这种方式
  • 以第一次写入的数据为准，如果你不希望存储的数据被更改，可以以它为准
• Q:实现最终一致性的具体方式
  • 读时修复：在读取数据时，检测数据的不一致，进行修复。如 Cassandra 的 Read Repair 实现，即在向Cassandra系统查询数据时，如果检测到不同节点的副本数据不一致，系统就自动修复数据
  • 写时修复：在写入数据时，检测数据的不一致，进行修复。如 Cassandra 的 Hinted Handoff 实现。即Cannandra集群的节点之间远程写数据的时候，如果写失败就将数据缓存下来，然后定时重传，修复数据的不一致性
  • 异步修复：最常用的方式，通过定时对账检测副本数据的一致性，并修复
  • 写时修复不需要做数据一致性对比，性能消耗比较低，对系统运行影响也不大，推荐你在实现最终一致性时优先实现这种方式。而读时修复和异步修复因为需要做数据的一致性对比，性能消耗比较多，在开发实际系统时，要尽量优化一致性对比的算法，降低性能消耗，避免对系统运行造成影响
  • 实现最终一致性的时候，推荐同时实现自定义写一致性级别（All、Quorum、One、Any）， 让用户可以自主选择相应的一致性级别，比如可以通过设置一致性级别为 All，来实现强一致性