极客时间：分布式算法和协议
- 分布式系统里，最重要的事情，就是如何选择或设计适合的算法，解决一致性和可用性相关的取舍问题
- InfluxDB 集群的护城河就是以分布式算法为核心的分布式集群能力
- 问题
- 实现集群能力的时候，怎么支持基于时序进行分片？怎么支持水平扩展？
- 甚至还有些人在接入性能敏感的场景，该使用反熵（Anti-Entropy）算法的时候，却用了 Raft 算法，使得集群性能约等同于单机。
- 课程划分了三个模块，分别是
- 理论篇
- 协议和算法篇
- Raft 比较适合性能要求不高的强一致性场景
- Paxos 和 Raft 的区别在哪里？
- 实战篇
- 掌握分布式基础理论和分布式算法在工程实践中的应用
- 剖析 InfluxDB 企业版的 CP 架构和 AP 架构的设计和背后的思考
- Raft、Quorum NWR、Anti-Entropy 等分布式算法的具体实现
- 剖析 Hashicorp Raft 的实现
- 以一个分布式 KV 系统的开发实战为例，来聊聊如何使用 Raft 算法实际开发一个分布式系统
- 收获
- 4 大分布式基础理论
- 拜占庭将军问题：有叛徒情况下如何达成共识
- The Byzantine Generals Problem
- 抽象模型：分布式共识问题
- 目的：统一作战计划
- 消息类型
- 错误消息（恶意消息或中间人篡改）
- 口信消息型拜占庭问题：如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了。
- 指挥官收到消息数：1+(3m+1-2)=3m
- 原始错误消息数：m（使单人进攻被歼灭）
- 叛将数 m 决定递归循环的次数：即 m+1 轮
- 签名消息型拜占庭问题：对消息签名
- 忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现
- 任何人都能验证将军签名的真伪
- 修改或发送不一致消息都能让进攻取消
- 口信消息型拜占庭问题：如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了。
- 消息丢失（节点挂掉或通信中断）
- 消息重复
- 错误消息（恶意消息或中间人篡改）
- 其他拜占庭容错算法（Byzantine Fault Tolerance，BFT）
- PBFT算法
- PoW算法
- 在计算机分布式系统中，最常用的是非拜占庭容错算法：故障容错算法（Crash Fault Tolerance，CFT）
- CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。
- CAP理论
- 一致性 Consistency （退化成最终一致性，等同于原子性）
- 可用性 Availability （需要）
- 分区容错性 Partition Tolerance （分布式必定需要）
- 埃里克·布鲁尔（Eric Brewer）基于自己的工程实践，提出的一个猜想，后被赛斯·吉尔伯特（Seth Gilbert）和南希·林奇（Nancy Lynch）证明
- P是必需的，所以成了 CP 和 AP 二选一
- **注意，在不存在网络分区的情况下，也就是分布式系统正常运行时（这也是系统在绝大部分时候所处的状态），就是说在不需要 P 时，C 和 A 能够同时保证。只有当发生分区故障的时候，也就是说需要 P 时，才会在 C 和 A 之间做出选择。**而且如果各节点数据不一致，影响到了系统运行或业务运行（也就是说会有负面的影响），推荐选择 C，否则选 A。
- ACID理论：CAP的酸，追求一致性
- 在单机上实现 ACID 也不难，比如可以通过锁、时间序列等机制保障操作的顺序执行，让系统实现 ACID 特性
- 掌握分布式事务协议
- 二阶段提交协议
- 提交请求阶段（又称投票阶段）
- 提交执行阶段（又称完成阶段）
- 执行要求：在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己那一部分，即使参与者出现故障或者中途被替换掉。
- 存在弊端
- 提交请求阶段，需要预留资源，此期间其他人不能操作
- 数据库是独立的系统
- 解决：TCC，最终变成了请求、确认、执行/取消
- 存在弊端
- 不过现在最常用的协议是 XA 协议
- 这个协议是 X/Open 国际联盟基于二阶段提交协议提出的，也叫作 X/Open Distributed Transaction Processing（DTP）模型
- 比如 MySQL 就是通过 MySQL XA 实现了分布式事务。
- TCC（Try-Confirm-Cancel）
- Try 预留
- Confirm 确认
- Cancel 取消
- TCC 本质上是补偿事务，它的核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作（也就是撤销操作）
- 为了实现一致性，确认操作和补偿操作必须是等幂的，因为这 2 个操作可能会失败重试。
- 二阶段提交协议
- BASE理论：CAP的碱，追求可用性
- BASE 理论是 CAP 理论中的 AP 的延伸，是对互联网大规模分布式系统的实践总结，强调可用性。
- 它的核心就是基本可用（Basically Available）和最终一致性（Eventually consistent）。也有人会提到软状态（Soft state），软状态描述的是实现服务可用性的时候系统数据的一种过渡状态，也就是说不同节点间，数据副本存在短暂的不一致。
- 基本可用4板斧
- 流量削峰
- 延迟响应
- 体验降级：降低图片清晰度
- 过载保护：定容队列
- 最终一致性
- 最终数据以延迟可用性阶段什么数据为准
- 以最新写入的数据为准，比如 AP 模型的 KV 存储采用的就是这种方式
- 以第一次写入的数据为准，如果你不希望存储的数据被更改，可以以它为准
- 如何实现
- 读时修复：比如 Cassandra 的 Read Repair 实现
- 写时修复：比如 Cassandra 的 Hinted Handoff 实现
- 异步定时修复：最常用的方式
- 在实现最终一致性的时候，推荐同时实现自定义写一致性级别（All、Quorum、One、Any）， 让用户可以自主选择相应的一致性级别，比如可以通过设置一致性级别为 All，来实现强一致性。
- 最终数据以延迟可用性阶段什么数据为准
- 基本可用4板斧
- BASE 理论在 NoSQL 中应用广泛，是 NoSQL 系统设计的事实上的理论支撑
- 拜占庭将军问题：有叛徒情况下如何达成共识
- 8 个最常用的分布式协议和算法
- BFT （Byzantine Fault Tolerance，拜占庭容错）
- PBFT算法
- 不过事实上，拜占庭将军问题之解很难在实际项目落地，因为口信消息型拜占庭问题之解是一个非常理论化的算法，没有和实际场景结合，也没有考虑如何在实际场景中落地和实现。
- 比如，它实现的是在拜占庭错误场景下，忠将们如何在叛徒干扰时，就一致行动达成共识。但是它并不关心结果是什么，这会出现一种情况：现在适合进攻，但将军们达成的最终共识却是撤退。很显然，这不是我们想要的结果。因为在实际场景中，我们需要就提议的一系列值（而不是单值），即使在拜占庭错误发生的时候也能被达成共识。
- 这个算法有个非常致命的缺陷。如果将军数为 n、叛将数为 f，那么算法需要递归协商 f+1 轮，消息复杂度为 O(n ^ (f + 1))，消息数量指数级暴增。你可以想象一下，如果叛将数为 64，消息数已经远远超过 int64 所能表示的了。
- PBFT 算法是通过签名（或消息认证码 MAC）约束恶意节点的行为，也就是说，每个节点都可以通过验证消息签名确认消息的发送来源，一个节点无法伪造另外一个节点的消息。最终，基于大多数原则（2f + 1）实现共识的。
- PBFT 算法通过视图变更（View Change）的方式，来处理主节点作恶，当发现主节点在作恶时，会以“轮流上岗”方式，推举新的主节点。
- 尽管 PBFT 算法相比口信消息型拜占庭之解已经有了很大的优化，将消息复杂度从 O(n ^ (f + 1)) 降低为 O(n ^ 2)，能在实际场景中落地，并解决实际的共识问题。但 PBFT 还是需要比较多的消息。
- 相比 Raft 算法完全不适应有人作恶的场景，PBFT 算法能容忍 (n - 1)/3 个恶意节点 (也可以是故障节点)。另外，相比 PoW 算法，PBFT 的优点是不消耗算力，所以在日常实践中，PBFT 比较适用于相对“可信”的场景中，比如联盟链。
- PoW算法
- 区块链通过工作量证明（Proof of Work）增加了坏人作恶的成本，以此防止坏人作恶。比如，如果坏人要发起 51% 攻击，需要控制现网 51% 的算力，成本是非常高昂的。
- 这个算法具有不对称性，也就是说，工作对于请求方是有难度的，对于验证方则是比较简单的，易于验证的。
- 区块链也是通过 SHA256 来执行哈希运算的，通过计算出符合指定条件的哈希值，来证明工作量的。
- 区块链的区块，是由区块头、区块体 2 部分组成的，就像下图中的样子。
- 区块头（Block Head）：区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数（nonce）等组成的。
- 区块体（Block Body）：区块包含的交易数据，其中的第一笔交易是 Coinbase 交易，这是一笔激励矿工的特殊交易。
- 需要你注意的是，即使攻击者只有 30% 的算力，他也有可能连续计算出多个区块的哈希值，挖掘出更长的攻击链，发动攻击； 另外，即使攻击者拥有 51% 的算力，他也有可能半天无法计算出一个区块的哈希值，也就是攻击失败。也就是说，能否计算出符合条件的哈希值，有一定的概率性，但长久来看，攻击者攻击成功的概率等同于攻击者算力的权重。
- PBFT算法
- CFT（Crash Fault Tolerance，故障容错）
- Paxos 算法
- 在过去几十年里，它基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如，Fast Paxos 算法、Cheap Paxos 算法、Raft 算法、ZAB 协议等等。
- 分类
- 一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识
- 一些概念：提案、准备（Prepare）请求、接受（Accept）请求、角色等等
- 三种角色
- 提议者（Proposer）
- 提议一个值，用于投票表决。在绝大多数场景中，集群中收到客户端请求的节点，才是提议者。
- 使用[n, v]表示一个提案，其中 n 为提案编号，v 为提议值。
- 接受者（Acceptor）
- 对每个提议的值进行投票，并存储接受的值。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。
- 学习者（Learner）
- 被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份。
- 提议者（Proposer）
- 共识的两个个阶段，包含了三个承诺
- 准备阶段
- 注意：发送包含提案编号的准备请求。在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了。
- 承诺1：小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求
- 接受阶段
- 承诺2：如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案
- 承诺3：如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。
- 准备阶段
- 另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识
- 多次执行 Basic Paxos 存在几个问题
- 如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。
- 2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。分布式系统的运行是建立在 RPC 通讯的基础之上的，因此，延迟一直是分布式系统的痛点，是需要我们在开发分布式系统时认真考虑和优化的。
- 通过引入领导者节点，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了
- 在论文中，兰伯特没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby 中，主节点（也就是领导者节点）是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）
- 另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。
- 在 Chubby 中，为了实现了强一致性，读操作也只能在主节点上执行。
- 多次执行 Basic Paxos 存在几个问题
- 一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识
- Basic Paxos 的容错能力，源自“大多数”的约定，你可以这么理解：当少于一半的节点出现故障的时候，共识协商仍然在正常工作。
- Raft 算法
- 受限于 Raft 的强领导者模型。所有请求都在领导者节点上处理，整个集群的性能等于单机性能。这样会造成集群接入性能低下，无法支撑海量或大数据量的时序数据。
- Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，只有日志最完整的节点，才能当选领导者。
- Raft 算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导，也极大地减少了选举失败的情况
- Raft 算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统（比如 Cubby、Spanner）都是在 Raft 算法发布前开发的，当时没得选；而全新的系统大多选择了 Raft 算法（比如 Etcd、Consul、CockroachDB）
- 成员身份，又叫做服务器节点状态，Raft 算法支持领导者（Leader）、跟随者（Follower）和候选人（Candidate） 3 种状态。
- 跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
- 候选人：候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
- 领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”
- 节点间是如何通讯的呢？
- 服务器节点间的沟通联络采用的是远程过程调用（RPC）
- 包括投票请求（RequestVote）RPC，日志复制（AppendEntries）RPC
- 日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键之一
- 什么是任期呢？
- 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号
- 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值
- 任期编号的大小，会影响领导者选举和请求的处理
- 在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态
- 如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求
- 选举有哪些规则？
- 领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息），通知大家我是领导者，阻止跟随者发起新的选举
- 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举
- 在一次选举中，赢得大多数选票的候选人，将晋升为领导者
- 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举
- 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票
- 随机超时时间又是什么？如何处理选举无效的问题？
- Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况
- 随机超时时间是有 2 种含义的，这里是很多同学容易理解出错的地方
- 跟随者等待领导者心跳信息超时的时间间隔，是随机的
- 当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是说，等待选举超时的时间间隔，是随机的
- 如何复制日志？
- 副本数据是以日志的形式存在的，日志是由日志项组成。做个类比，一个木筏（Raft）是由多根整齐一致的原木（Log）组成的，而原木又是由木质材料组成，所以你可以认为日志是由多条日志项（Log entry）组成的，如果把日志比喻成原木，那么日志项就是木质材料。
- 日志项究竟是什么样子呢？
- 日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）
- 一届领导者任期，往往有多条日志项。而且日志项的索引值是连续的。
- 可以把 Raft 的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟。
- 领导者不直接发送消息通知其他节点应用指定日志项。因为领导者的日志复制 RPC 消息或心跳消息，包含了当前最大的，将会被提交（Commit）的日志项索引值。所以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。这是Raft中的一个优化。
- 如何实现日志的一致？
- 在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。
- 兰伯特的 Multi-Paxos 不要求日志是连续的，但在 Raft 中日志必须是连续的。而且在 Raft 中，日志不仅是数据的载体，日志的完整性还影响领导者选举的结果。也就是说，日志完整性最高的节点才能当选领导者。
- 跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。
- 如何解决成员变更的问题
- Raft 是共识算法，对集群成员进行变更时（比如增加 2 台服务器），会不会因为集群分裂，出现 2 个领导者呢？
- 在我看来，的确会出现这个问题，因为 Raft 的领导者选举，建立在“大多数”的基础之上，那么当成员变更时，集群成员发生了变化，就可能同时存在新旧配置的 2 个“大多数”，出现 2 个领导者，破坏了 Raft 集群的领导者唯一性，影响了集群的运行。
- 而关于成员变更，不仅是 Raft 算法中比较难理解的一部分，非常重要，也是 Raft 算法中唯一被优化和改进的部分。比如，最初实现成员变更的是联合共识（Joint Consensus），但这个方法实现起来难，后来 Raft 的作者就提出了一种改进后的方法，单节点变更（single-server changes）。
- 配置是成员变更中一个非常重要的概念：它就是在说集群是哪些节点组成的，是集群各节点地址信息的集合。比如节点 A、B、C 组成的集群，那么集群的配置就是[A, B, C]集合。
- 因为我们在启动集群时，配置是固定的，不存在成员变更，在这种情况下，Raft 的领导者选举能保证只有一个领导者。
- 单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群。
- 不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节点，新旧配置的“大多数”都会存在重叠。
- 节点数 -> 多数节点数 -> 剩余节点数
- 2n -> n + 1 -> n -1
- 2n + 1 -> n + 1 -> n (上一状态的多数节点数 n + 1 比 剩余节点数多1)
- 2n + 2 -> n + 2 -> n (上一状态的多数节点数 n + 1 比 剩余节点数多1)
- …
- 也就是说在要求多数一致和存在分区的情况下，不可能出现两个领导者节点
- 需要你注意的是，在分区错误、节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者的情况。如果你遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项应用后，再执行成员变更请求。
- 因为联合共识实现起来复杂，不好实现，所以绝大多数 Raft 算法的实现，采用的都是单节点变更的方法（比如 Etcd、Hashicorp Raft）。其中，Hashicorp Raft 单节点变更的实现，是由 Raft 算法的作者迭戈·安加罗（Diego Ongaro）设计的，很有参考价值。
- 不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节点，新旧配置的“大多数”都会存在重叠。
- 有很多同学把 Raft 当成一致性算法，其实 Raft 不是一致性算法而是共识算法，是一个 Multi-Paxos 算法，实现的是如何就一系列值达成共识。并且，Raft 能容忍少数节点的故障。虽然 Raft 算法能实现强一致性，也就是线性一致性（Linearizability），但需要客户端协议的配合。在实际场景中，我们一般需要根据场景特点，在一致性强度和实现复杂度之间进行权衡。
- 一般而言，在实际工程中，Consul 的 consistent 就够用了，可以不用线性一致性，只要能保证写操作完成后，每次读都能读到最新值就可以了。比如为了实现冥等操作，我们使用一个编号 (ID) 来唯一标记一个操作，并使用一个状态字段（nil/done）来标记操作是否已经执行，那么只要我们能保证设置了 ID 对应状态值为 done 后，能立即和一直读到最新状态值就可以了，也就通过防止操作的重复执行，实现了冥等性。
- 比如我负责过多个 QQ 后台的海量服务分布式系统，其中配置中心、名字服务以及时序数据库的 META 节点，采用了 Raft 算法。在设计时序数据库的 DATA 节点一致性时，基于水平扩展、性能和数据完整性等考虑，就没采用 Raft 算法，而是采用了 Quorum NWR、失败重传、反熵等机制。这样安排不仅满足了业务的需求，还通过尽可能采用最终一致性方案的方式，实现系统的高性能，降低了成本。
- 一致性算法与共识算法的区别？
- 一致性哈希算法
- 如果我们通过 Raft 算法实现了 KV 存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接入性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系统过载和服务不可用，这时该怎么办呢？
- 通过分集群，突破单集群的性能限制
- 一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算。你可以想象下，一致哈希算法，将整个哈希值空间组织成一个虚拟的圆环，也就是哈希环。
- 在一致哈希中，你可以通过执行哈希算法（为了演示方便，假设哈希算法函数为“c-hash()”），将节点映射到哈希环上，比如选择节点的主机名作为参数执行 c-hash()，那么每个节点就能确定其在哈希环上的位置了
- 当需要对指定 key 的值进行读写的时候，你可以通过下面 2 步进行寻址：
- 首先，将 key 作为参数执行 c-hash() 计算哈希值，并确定此 key 在环上的位置
- 然后，从这个位置沿着哈希环顺时针“行走”，遇到的第一节点就是 key 对应的节点。
- 在一致哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是，会寻址到此节点和前一节点之间的数据。
- 客户端访问请求集中在少数的节点上，出现了有些机器高负载，有些机器低负载的情况，那么在一致哈希中，有什么办法能让数据访问分布的比较均匀呢？
- 答案就是虚拟节点。（本质是避免哈希输入值的这个随机抽样过程在样本数太少的时候带来不均匀的分布）
- 其实，就是对每一个服务器节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。
- 如果我们通过 Raft 算法实现了 KV 存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接入性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系统过载和服务不可用，这时该怎么办呢？
- Gossip 算法
- Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。对你来说，掌握这个协议不仅能很好地理解这种最常用的，实现最终一致性的算法，也能在后续工作中得心应手地实现数据的最终一致性。
- Gossip 三板斧
- 直接邮寄（Direct Mail）
- 反熵（Anti-entropy）
- 反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性
- 实现反熵的时候，主要有推、拉和推拉三种方式
- 修复情况有两种
- 数据缺失：复制
- 数据不一致：循环修复
- 谣言传播（Rumor mongering）
- 虽然反熵很实用，但是执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境（比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态），这时反熵就不适用了。
- Quorum NWR 算法
- 你开发实现了一套 AP 型的分布式系统，实现了最终一致性。业务也接入了，运行正常，一起看起来都那么美好。可是，突然有同事说，我们要拉这几个业务的数据做实时分析，希望数据写入成功后，就能立即读取到新数据，也就是要实现强一致性。
- 通过次算法，可以自定义一致性级别，通过临时调整写入或者查询的方式，当 W + R > N 时，就可以实现强一致性了。
- N 表示副本数，又叫做复制因子（Replication Factor）。也就是说，N 表示集群中同一份数据有多少个副本。
- W，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新，才完成写操作。
- R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R 个副本。
- N、W、R 值的不同组合，会产生不同的一致性效果，具体来说，有这么两种效果：当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。当 W + R <= N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。
- InfluxDB 企业版，支持“any、one、quorum、all”4 种写一致性级别，具体的含义是这样的：
- any：任何一个节点写入成功后，或者接收节点已将数据写入 Hinted-handoff 缓存（也就是写其他节点失败后，本地节点上缓存写失败数据的队列）后，就会返回成功给客户端。
- one：任何一个节点写入成功后，立即返回成功给客户端，不包括成功写入到 Hinted-handoff 缓存。
- quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2 时才有意义，否则等效于 all。
- all：仅在所有节点都写入成功后，返回成功。
- ZAB 算法
- 而在 Multi-Paxos 中，领导者作为唯一提议者，是不存在同时多个提议者的情况。也就是说，Paxos（更确切的说是 Multi-Paxos）无法保证操作的顺序性的问题是存在的，但原因不是 ZAB 论文中演示的原因，本质上是因为 Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序。
- ZooKeeper 怎么实现操作的顺序性的呢? 答案是它实现了 ZAB 协议。
- Raft 可以实现操作的顺序性啊，为什么 ZooKeeper 不用 Raft 呢？因为 Raft 出来的比较晚，直到 2013 年才正式提出，在 2007 年开发 ZooKeeper 的时候，还没有 Raft 呢。
- 过程
- 接着，当主节点接收到写请求后，它会基于写请求中的指令（也就是 X，Y），来创建一个提案（Proposal），并使用一个唯一的 ID 来标识这个提案。这里我说的唯一的 ID 就是指事务标识符（Transaction ID，也就是 zxid）。事务标识符是 64 位的 long 型变量，有任期编号 epoch 和计数器 counter 两部分组成（为了形象和方便理解，我把 epoch 翻译成任期编号），格式为 ，高 32 位为任期编号，低 32 位为计数器。
- 任期编号，就是创建提案时领导者的任期编号，当新领导者当选时，任期编号递增，计数器被设置为零。
- 在创建完提案之后，主节点会基于 TCP 协议，并按照顺序将提案广播到其他节点。这样就能保证先发送的消息，会先被收到，保证了消息接收的顺序性。
- 然后，当主节点接收到指定提案的“大多数”的确认响应后，该提案将处于提交状态（Committed），主节点会通知备份节点提交该提案。
- 主节点根据事务标识符大小，按照顺序提交提案，如果前一个提案未提交，此时主节点是不会提交后一个提案的。
- 为了提升读并发能力，Zookeeper 提供的是最终一致性，也就是读操作可以在任何节点上执行，客户端会读到旧数据。Zookeeper 提供了 sync 命令，使得读到最新的数据。
- 为什么 ZAB 作者宣称ZAB 不是 Paxos 算法，但又有很多资料提到 ZAB 是 Multi-Paxos 算法呢？
- 因为技术是发展的，概念的内涵也在变化。Raft 算法（主备、强领导者模型）与 ZAB 协议非常类似，它是作为共识算法和 Multi-Paxos 算法提出的。当它被广泛接受和认可后，共识算法的内涵也就丰富和发展了，不仅能实现一系列值的共识，还能保证值的顺序性。同样，Multi-Paxos 算法不仅指代多次执行 Basic Paxos 的算法，还指代主备、强领导者模型的共识算法。
- Paxos 算法
- BFT （Byzantine Fault Tolerance，拜占庭容错）
- 3 大实战案例
- InfluxDB
- 什么是时序数据库
- 最大特点是数据量很大
- 时序数据主要来自监控
- 由META节点和DATA节点2种逻辑单元组成；DATA节点只需要实现最终一致性，选用了CAP中的AP模型
- 如何实现DATA节点一致性
- 自定义副本数：不同于Raft算法的算法节点和副本必须一一对应
- Hinted-handoff
- 写失败请求缓存到本地硬盘上
- 周期性尝试重传
- 有可配置的缓存空间大小、缓存周期、尝试间隔
- 反熵
- 时序数据像日志数据一样，创建后就不会再修改了，一直存放在那里，直到被删除。所以，数据副本之间的数据不一致，是因为数据写失败导致数据丢失了，也就是说，存在的都是合理的，缺失的就是需要修复的。这时我们可以采用两两对比、添加缺失数据的方式，来修复各数据副本的不一致了。
- Quorum NWR
- 在一个AP型的分布式系统中，实现强一致性
- 技术是用来解决场景的需求的，只有当你吃透技术，深刻理解场景的需求，才能开发出适合这个场景的分布式系统
- 竞品比较
- 相比 OpenTSDB，InfluxDB 的写性能是它的 9.96 倍，存储效率是它的 8.69 倍，查询效率是它的 7.38 倍。
- 相比 Graphite，InfluxDB 的写性能是它的 12 倍，存储效率是 6.3 倍，查询效率是 9 倍。
- 什么是时序数据库
- Hashicorp Raft
- 领导者选举：本质上是节点状态变迁，跟随者、候选人、领导者对应的功能函数分别为 runFollower()、runCandidate()、runLeader()
- 复制日志：Raft 是基于强领导者模型和日志复制，最终实现强一致性的
- raft.go 是 Hashicorp Raft 的核心代码文件，大部分的核心功能都是在这个文件中实现的，平时可以多研究这个文件中的代码，直到彻底吃透，掌握。
- 高效阅读源码的关键在于抓住重点，要有“底线”，不要芝麻和西瓜一把抓，什么都想要，最终陷入到枝节琐碎的细节中出不来。什么是重点呢？我认为重点是数据结构和关键的代码执行流程。
- 文档里虽然提到了 API 的功能，但并没有提如何在实际场景中使用这些 API，每个 API 都是孤立的点，缺乏一些场景化的线将它们串联起来。所以，为了帮你更好地理解 Hashicorp Raft 的 API 接口，在实践中将它们用起来，我以“集群节点”为核心，通过创建、增加、移除集群节点，查看集群节点状态这 4 个典型的场景，具体聊一聊在 Hashicorp Raft 中，通过哪些 API 接口能创建、增加、移除集群节点，查看集群节点状态。这样一来，我们会一步一步，循序渐进地彻底吃透 Hashicorp Raft 的 API 接口用法。
NewRaft()创建Raft节点的参数：- 可使用默认配置
raftboltdb.NewBoltStore()实现底层存储- 通信传输层
raft.NewTCPTransport()
- 启动集群
raftNode.BootstrapCluster(configuration) - 加入到集群
raftNode.AddVoter() AddNonvoter()，将一个节点加入到集群中，但不赋予它投票权，让它只接收日志记录- 移除集群节点
raftNode.RemoveServer()
- 其他实现
- 基于Raft的分布式KV系统开发实战
- InfluxDB
- 4 大分布式基础理论
另外一个提纲
一、分布式锁
数据库的唯一索引
Redis 的 SETNX 指令
Redis 的 RedLock 算法
Zookeeper 的有序节点
二、分布式事务
2PC
本地消息表
三、CAP
一致性
可用性
分区容忍性
权衡
四、BASE
基本可用
软状态
最终一致性
五、Paxos
执行过程
约束条件
六、Raft
单个 Candidate 的竞选
多个 Candidate 竞选
数据同步