分布式协议与算法（常⽤）
01 | 拜占庭将军问题：有叛徒的情况下，如何才能达成共识？
解决办法⼀：⼝信消息型拜占庭问题之解
如果叛将⼈数为 m，将军⼈数不能少于 3m + 1 ，需要进⾏m+1轮作战信息协商，那么占庭将军问题就能解决了。这个算法有个前提，叛徒数量是已知的。
解决办法⼆：签名消息型拜占庭问题之解
在不增加将军数量的情况下，某个将军发送的作战信息⼀旦被修改就能被发现，从⽽执⾏另⼀个将军的作战计划
强调：拜占庭将军问题描述的是最困难的，也是最复杂的⼀种分布式故障场景，除了存在故障⾏为，还存在恶意⾏为的⼀个场景。
在存在恶意节点⾏为的场景中（⽐如在数字货币的区块链技术中），必须使⽤拜占庭容错算法（Byzantine FaultTolerance，BFT）。除了故事中提到两种算法，常⽤的拜占庭容错算法还有：PBFT 算法，PoW 算法，⽽在计算机分布式系统中，最常⽤的是⾮拜占庭容错算法，即故障容错算法（Crash FaultTolerance，CFT）。
CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。
也就是说，这个场景可能会丢失消息，或者有消息重复，但不存在错误消息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议
02 | CAP理论：分布式系统的PH试纸，⽤它来测酸碱度
⼀致性（Consistency）：不管你访问哪个节点，要么我给你返回的都是绝对⼀致的数据，要么你都读取失败。
⼀致性强调的不是数据完整，⽽是各节点间的数据⼀致。
可⽤性（Availability）：我尽⼒给你返回数据，不会不响应你，但是我不保证每个节点给你的数据都是最新的。
这个指标强调的是服务可⽤，但不保证数据的⼀致。
分区容错性（Partition Tolerance）：不管我的内部出现什么样的数据同步问题，我会⼀直运⾏，提供服务。
这个指标，强调的是集群对分区故障的容错能⼒。
”CAP 不可能三⾓“怎么理解？
CAP 不可能三⾓说的是对于⼀个分布式系统⽽⾔，⼀致性（Consistency）、可⽤性（Availability）、分区容错性（Partition Tolerance）3 个指标不可兼得，只能在 3 个指标中选择 2 个。
总结：
CA 模型，在分布式系统中不存在。因为舍弃 P，意味着舍弃分布式系统，就⽐如单机版关系型数据库 MySQL，如果 MySQL 要考虑主备或集群部署时，它必须考虑 P。
CP 模型，采⽤ CP 模型的分布式系统，⼀旦因为消息丢失、延迟过⾼发⽣了⽹络分区，就影响⽤户的体验和业务的可⽤性。因为为了防⽌数据不⼀致，集群将拒绝新数据的写⼊，典型的应⽤是 ZooKeeper，Etcd 和 HBa。
AP 模型，采⽤ AP 模型的分布式系统，实现了服务的⾼可⽤。⽤户访问系统的时候，都能得到响应数据，不会出现响应错误，但当出现分区故障时，相同的读操作，访问不同的节点，得到响应数据可能不⼀样。典型应⽤就⽐如 Cassandra 和 DynamoDB。
03 | ACID理论：CAP的酸，追求⼀致性
（1）分布式事务协议：
（2）⼆阶段提交协议：最早是⽤来实现数据库的分布式事务的，不过现在最常⽤的协议是XA协议
以上两种协议存在的问题：
在提交请求阶段，需要预留资源，在资源预留期间，其他⼈不能操作（⽐如，XA 在第⼀阶段会将相关资源锁定）；
数据库是独⽴的系统。
如何解决这种问题？
TCC（Try-Confirm-Cancel）：TCC 本质上是补偿事务，它的核⼼思想是针对每个操作都要注册⼀个与其对应的确认操作和补偿操作（也就是撤销操作）。
TCC 它是⼀个业务层⾯的协议，不依赖于数据库的事务，⽽是在业务中实现了分布式事务，这样能减轻数据库的压⼒，但对业务代码的⼊侵性也更强，实现的复杂度也更⾼。
所以，我推荐在需要分布式事务能⼒时，优先考虑现成的事务型数据库（⽐如 MySQL XA），当现有的事务型数据库不能满⾜业务的需求时，再考虑基于 TCC 实现分布式事务。
04 | BASE理论：CAP的碱，追求可⽤性（基本可⽤+最终⼀致性）
实现基本可⽤的 4 板斧：
不仅掌握流量削峰、延迟响应、体验降级、过载保护这 4 板斧，更能理解这 4 板斧背后的妥协折中，从⽽灵活地处理不可预知的突发问题。
最终⼀致性是说，系统中所有的数据副本在经过⼀段时间的同步后，最终能够达到⼀个⼀致的状态。也就是说，在数据⼀致性上，存在⼀个短暂的延迟。
实现最终⼀致性的具体⽅式是什么呢？
读时修复：在读取数据时，检测数据的不⼀致，进⾏修复。
写时修复：在写⼊数据，检测数据的不⼀致时，进⾏修复。
异步修复：这个是最常⽤的⽅式，通过定时对账检测副本数据的⼀致性，并修复。
我想强调的是因为写时修复不需要做数据⼀致性对⽐，性能消耗⽐较低，对系统运⾏影响也不⼤，所以我推荐你在实现最终⼀致性时优先实现这种⽅式。⽽读时修复和异步修复因为需要做数据的⼀致性对⽐，性能消耗⽐较多，在开发实际系统时，你要尽量优化⼀致性对⽐的算法，降低性能消耗，避免对系统运⾏造成影响。
还实现⾃定义写⼀致性级别，⽀持 All、Quorum、One、Any 4 种写⼀致性级别，⽤户在写数据的时候，可以根据业务数据的特点，设置不同的写⼀致性级别。
05 | Paxos算法（⼀）：如何在多个节点间确简爱中的经典语句
定某变量的值？
Basic Paxos 的容错能⼒，源⾃“⼤多数”的约定，你可以这么理解：当少于⼀半的节点出现故障的时候，共识协商仍然在正常⼯作。
在 Basic Paxos 中，有提议者（Propor）、接受者（Acceptor）、学习者（Learner）三种⾓⾊，
提议者代表的是接⼊和协调功能，收到客户端请求后，发起⼆阶段提交，进⾏共识协商；
接受者代表投票协商和存储数据，对提议的值进⾏投票，并接受达成共识的值，存储保存；
学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。
你可以看到，Basic Paxos 是通过⼆阶段提交（准备阶段和提交阶段）的⽅式来达成共识的。
⼆阶段提交是达成共识的常⽤⽅式，如果你需要设计新的共识算法的时候，也可以考虑这个⽅式。
除了共识，Basic Paxos 还实现了容错，在少于⼀半的节点出现故障时，集群也能⼯作。它不像分布
式事务算法那样，必须要所有节点都同意后才提交操作，因为“所有节点都同意”这个原则，在出现节点故障的时候会导致整个集群不可⽤。也就是说，“⼤多数节点都同意”的原则，赋予了 Basic Paxos 容错的能⼒，让它能够容忍少于⼀半的节点的故障。
本质上⽽⾔，提案编号的⼤⼩代表着优先demands
级，你可以这么理解，根据提案编号的⼤⼩，
接受者保证三个承诺，具体来说：
如果准备请求的提案编号，⼩于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；
如果接受请求中的提案的提案编号，⼩于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；
如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最⼤编号的提案信息。
07 | Raft算法（⼀）：如何选举领导者？
从本质上说，Raft 算法是通过⼀切以领导者为准的⽅式，实现⼀系列值的共识和各节点⽇志的⼀致。
Raft 算法通过任期、领导者⼼跳消息、随机选举超时时间、先来先服务的投票原则、⼤多数选票原则等，保证了⼀个任期只有⼀位领导，也极⼤地减少了选举失败的情况。
08 | Raft算法（⼆）：如何复制⽇志？
⼀个理想状态下的⽇志复制过程：
1.接收到客户端请求后，领导者基于客户端请求中的指令，创建⼀个新⽇志项，并附加到本地⽇志中。
2.领导者通过⽇志复制 RPC，将新的⽇志项复制到其他的服务器。
3.当领导者将⽇志项，成功复制到⼤多数的服务器上的时候，领导者会将这条⽇志项提交到它的状态机中。
4.领导者将执⾏的结果返回给客户端。
5.当跟随者接收到⼼跳信息，或者新的⽇志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条⽇志项，⽽它还没提交，那么跟随者就将这条⽇志项提交到本地的状态机中。
如何实现⽇志的⼀致？
领导者通过⽇志复制 RPC ⼀致性检查，找到跟随者节点上与⾃ ⼰相同⽇志项的最⼤索引值，然后复制并更新覆盖该索引值之后的⽇志项，实现了各节点⽇ 志的⼀致。
09 | Raft算法（三）：如何解决成员变更的问题？
如何通过单节点变更解决成员变更的问题？
我们就通过⼀次变更⼀个节点的⽅式，完成了成员变更，保证了集群中始终只有 ⼀个领导者，⽽且集群也在稳定运⾏，持续提供服务。
需要你注意的是，在分区错误、节点故障榴莲雪糕
等情况下，如果我们并发执⾏单节点变更，那么就 可能出现⼀次单节点变更尚未完成，新的单节点变更⼜在执⾏，导致集群出现 2 个领导者 的情况。 如果你遇到这种情况，可以在领导者启动时，创建⼀个 NO_OP ⽇志项（也就是空⽇志项），只有当领导者将 NO_OP ⽇志项提交后，再执⾏成员变更请求。
⽐如我负责过多个 QQ 后台的海量服务分布式系统，其中配置中⼼、名字服务以及时序数 据库的 META 节点，采⽤了 Raft 算法。在设计时序数据库的 DATA 节点⼀致性时，基于⽔平扩展、性能椴树蜜的作用与功效
和数据完整性等考虑，就没采⽤ Raft 算法，⽽是采⽤了Quorum NWR、失败重传、反熵等机制。这样安排不仅满⾜了业务的需求，还通过尽可能采⽤最终⼀致性⽅案的⽅式，实现系统的⾼性能，降低了成本。
10 | ⼀致哈希算致敬劳动者
法：如何分群，突破集群的“领导者”限制？
如果我们通过 Raft 算法实现了 KV 存储， 虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接⼊性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系 统过载和服务不可⽤，这时该怎么办呢？分集群，加个 Proxy 层，由 Proxy 层处理来⾃客户端的读写请求，接收到读写请求后，通过对 Key 做哈希找到对应的集群就可以了啊。
哈希算法的确是个办法，但它有个明显的缺点：当需要变更集群数时（⽐如从 2 个 集群扩展为 3 个集
群），这时⼤部分的数据都需要迁移，重新映射，数据的迁移成本是⾮常⾼的。
那么如何解决哈希算法，数据迁移成本⾼的痛点呢？答案就是⼀致哈希（Consistent Hashing）
⼀致哈希算法具有较好的容错性和可扩展性。
与哈希算法不同的是，哈希算法是对节点的数量进⾏取模运算，⽽⼀致哈希算法是对 2^32 进⾏取模运算。你可以想象下，⼀致哈希算法，将整个 哈希值空间组织成⼀个虚拟的圆环，也就是哈希环：
在哈希寻址中常出现这样的问题：客户端访问请求集中在少数的节点上 出现了有些机器⾼负载，有些机器低负载的情况，那么在⼀致哈希中，有什么办法能让数据访问分布的⽐较均匀呢？答案就是虚拟节点。
使⽤⼀致哈希实现哈希寻址时，可以通过增加节点数降低节点宕机对整个集群的影响，以及故障恢复时需要迁移的数据量。后续在需要时，你可以通过增加节点数来提升系统的容灾能⼒和故障恢复效率。
11 | Gossip协议：流⾔蜚语，原来也可以实现⼀致性
Gossip 协议，顾名思义，就像流⾔蜚语⼀样，利⽤⼀种随机、带有传染性的⽅式，将信息传播到整个⽹络中，并在⼀定时间内，使得系统内的所有节点数据⼀致。
Gossip 的三板斧分别是：直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣⾔传播 （Rumor mon时尚图片头像
gering）。
直接邮寄：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。
只采⽤直接邮寄是⽆法实现最终⼀致性的
那如何实现最终⼀致性呢？答案就是反熵。本质上，反熵是⼀种通过异步修复实现最终⼀致 性的⽅法
反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换⾃⼰的 所有数据来消除两者之间的差异，实现数据的最终⼀致性：因为反熵需要节点两两交换和⽐对⾃⼰所有的数据，执⾏反熵时通讯成本会很⾼，所以我不建议你在实际场景中频繁执⾏反熵，并且可以通过引⼊校验和（Checksum）等机制，降低需要对⽐的数据量和通讯消息等。虽然反熵很实⽤，但是执⾏反熵时，相关的节点都是已知的，⽽且节点数量不能太多，如果 是⼀个动态变化或节点数⽐较多的分布式环境（⽐如在DevOps环境中检测节点故障拉二胡英语
，并动态维护集群节点状态），这时反熵就不适⽤了。那么当你⾯临这个情况要怎样实现最终⼀致性呢？答案就是谣⾔传播。
谣⾔传播，⼴泛地散播谣⾔，它指的是当⼀个节点有了新数据后，这个节点变成活跃状态， 并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据：其实，谣⾔传播⾮常具有传染性，它适合动态变化的分布式系统。
最后需要你注意的是，因为反熵需要做⼀致性对⽐，很消耗系统性能，所以建议你将是否启⽤反熵功能、执⾏⼀致性检测的时间间隔等，做成可配置的，能在不同场景中按需使⽤。
总结：
在实际场景中，实现数据副本的最终⼀致性时，⼀般⽽⾔，直接邮寄的⽅式是⼀定要实现的，因为不需要做⼀致性对⽐，只是通过发送更新数据或缓存重传，来修复数据的不⼀致，性能损耗低。在存储组件中，节点都是已知的，⼀般采⽤反熵修复数据副本的⼀致性。当集群节点是变化的，或者集群节点数⽐较多时，这时要采⽤谣⾔传播的⽅式，同步更新数据，实现最终⼀致。
