摘要：只要系统满足下面的时间要求广播时间选举超时时间平均故障间隔时间就可以选举并维持一个稳定的。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。
Raft是当前分布式领域最重要的一致性算法之一，今天我们就来好好研究研究这个算法的论文, 还有对应网站, 动画, 不想看英文的也有中文的翻译，所以我这边就不翻译了，主要还是记录一下论文重点和自己的心得。
Raft算法作者的初衷是对标Paxos算法（过去十年分布式一致性的事实标准），但是要比它更易理解，主要手段有：
分解，把整个一致性问题拆分为Leader选举、日志复制和安全机制这三大方面还有角色改变这个小方面。所以模块化是一个软件系统可维护、理解和扩展的不二手段。
减少状态空间的状态，相比于Paxos，Raft减少了非确定性和服务器之间可以处于不一致的方式。所以在复杂的问题上做减法，可以减少很多不必要的繁琐的步骤。
Raft使用了更强的Leader，感觉这和我之前看的OceanBase是相似的，就是增强Leader（UpdateServer）或者说单点的作用，加重中心化（这也是社会的运作方式，没有Leader就是大家一盘散沙，文明是达不到今天这个程度的），要做决策就先选择一个Leader，然后让他去协调所有的决议，会更加简单快速，而Paxos就是P2P或者说弱Leader的方式。事实上，我们之所以使用分布式系统也是迫不得已，如果单台机器能搞定还要这么多系统干嘛？所以我们也要看到单点系统的好处，那就是一致性很容易保证，所以在分布式系统中使用一个增强（能力和责任）的单点既利于一致性的保证也能获得分布式的优势。
Leader全权负责管理日志复制，从而实现一致性，所以有了Leader这一机制，一致性问题就可以被分解为上述三大方面了，下面分别说明。
Raft 的 Leader 是有 Term 时间限制的，类似于租约机制，这个机制能完善单纯的心跳(因为节点可能太忙发不出或没法响应心跳)。
随机的选举超时时间可以使得 Leader 选举很少有选票平分的时候，按 Term number 最大和先来先服务原则可以使得每一个 Term 内最多有一个 Leader（如果没有 Leader 就会超时进入下一个 Term 进行新的选举）。Leader 保持身份并阻止其他节点成为 Leader 的方法是不停地向其他节点发送心跳消息（也可以包含需要复制的日志）。
Leader 为客户端服务，处理所有客户端请求亦即所有的系统变更，并把日志复制分发给其他节点（包含失败重试），leader 处理日志不一致的手段是强制follower 复制自己的日志，所以 follower 中与 leader 冲突的日志会被覆盖（比如未过半数亦即未提交的日志），leader 不删除自己的日志（只附加原则）。
leader选举和日志复制都需要一些安全机制来保证每个状态机都按照相同的顺序来执行相同的指令：
①. 选举限制，除了1中的条件，还要求 candidate 具有已经提交的所有日志条目，所以 voter 会主动拒绝日志没有自己新（通过Term Number 和 日志长度 两个指标进行比较）的候选人的投票请求。
②. 提交之前Term内的日志条目时，Leader 会使用这个条目的原始Term Number，而不是使用当前的Term Number，这样更容易辨别日志，而且要提交之前Term（如 2 ）的日志时必须同时提交当前Term（如 4）的日志，保证得到复制日志的 follower A 下次更有可能成为Leader而不是那些只有较旧日志但是新于A得到的旧日志（如 3 新于 2 ）的follower。换句话来说：old term 中的 log entry 需要被间接提交，即使其满足复制数过半也必须要等到当前 term 中有 entry 被提交时才能跟着一起提交
如果 follower 或者 candidate 崩溃了，那么后续发送给他们的请求都会失败。Raft 中处理这种失败就是简单的通过无限的重试，因为Raft的这种请求都是幂等的，所以这样重试不会造成任何问题。比如，一个follower如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求。
Leader 选举是 Raft 中对时间要求最为关键的方面。只要系统满足下面的时间要求：
广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）
Raft 就可以选举并维持一个稳定的Leader。当Leader崩溃后，整个系统会大约相当于选举超时的时间里不可用，广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的， Raft的请求 要接收方将信息持久到存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。
对于客户端来说，只要得到leader的ok回复就可以认为操作成功了，未得到ok（失败或超时）就需要重试。那么Raft是怎么保证这个语义的呢？
Leader未把日志未复制过半就挂了那么此次请求客户端肯定会知道是失败的，没影响；Leader把日志复制过半但是未回复ok就挂了的话，这些日志之后可能被提交也可能被覆盖，这就需要客户端带上唯一请求id重试，新的leader发现该id已经在日志中出现并且可被提交就直接回复ok，否则就重新执行一次这个请求；leader回复ok但是未提交就挂了的话，依赖于old entry的提交机制，这个请求还是能被落盘的。
通过这三个阶段不同的应对机制保证了ok的语义。
Raft也是能够应对脑裂问题的，比如ABCDE5个节点，A是leader，一开始保证正确的同步，某时刻，假设A没发出心跳给B(比如太忙)或者B没收到心跳（比如分区）使得B超时：
如果此时A有新的写入，那么此时CDE至少有两个日志比B新（多数），这是B发起选举后是不可能得到大多数投票的
如果此时A没有没有新的写入，那么B是可以选举成功的（term自增且拥有全部已提交日志），然后B成为leader处理新的请求，如果此时AB通了，A会发现自己term落后而自动成为follower，其作为leader期间的提案都会得不到提交而回滚
所以要么是避免脑裂选主，要么是脑裂后老leader自动降级为follower。脑裂问题就可以这样被解决了。当然最好的办法还是在节点之前加一个专线，降低分区的概率。
集群状态切换通过一个共同一致（新老配置的结合）的中间状态转换实现，这样基于两阶段的做法可以使得集群平滑地进行状态迁移。这一块没仔细看，不过 etcd 等 raft 实现都是采用了更加简洁和安全的一次只能变更一个节点的 single Cluser MemberShip Change 算法。
阅读原文：Mageekchiu
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/71545.html
摘要：前言本文旨在讲述如何使用语言实现基于算法的，分布式的，结构的存储项目。甚至像，可以利用实现分布式存储。核心组件包括一致性模块，通信，日志模块，状态机。状态机，可以是任何实现，其实质就是将日志中的内容进行处理。选举者优先选举自己将自 前言 本文旨在讲述如何使用 Java 语言实现基于 Raft 算法的，分布式的，KV 结构的存储项目。该项目的背景是为了深入理解 Raft 算法，从而深刻理...
摘要：但是一致性协议的贡献在于，定义了可易于实现的一致性协议的事实标准。本文不打算对一致性协议的具体内容进行说明，而是介绍记录一些关键点，因为绝大部分内容原文已经介绍的很详实，有意者还可把作者多页的博士论文刷一遍链接在文末，可自取。 此文已由作者孙建良授权网易云社区发布。 欢迎访问网易云社区，了解更多网易技术产品运营经验。 Raft 协议的发布，对分布式行业是一大福音，虽然在核心协议上基本都...
摘要：但是分布式数据库方面，好的开源项目并不多。由于分布式数据库自身的复杂性，很多人并不能很好的理解整个项目，所以我希望能写一些文章，自顶向上，由浅入深，讲述的一些技术原理，包括用户可见的技术以及大量隐藏在界面后用户不可见的技术点。 引言： 数据库、操作系统和编译器并称为三大系统，可以说是整个计算机软件的基石。其中数据库更靠近应用层，是很多业务的支撑。这一领域经过了几十年的发展，不断的有新的...
摘要：源码解析系列如何使用本系列文章主要面向社区开发者，重点介绍的系统架构，源码结构，流程解析。另外，本系列文章并不会涉及到中心控制服务的详细介绍，但是会说明一些重要流程是如何与交互的。，和分别是得到当前的，以及最小和最后的。 TiKV 源码解析系列——如何使用 Raft 本系列文章主要面向 TiKV 社区开发者，重点介绍 TiKV 的系统架构，源码结构，流程解析。目的是使得开发者阅读之后，...
摘要：本系列文章主要面向社区开发者，重点介绍的系统架构，源码结构，流程解析。本文是本系列文章的第五章节。等待自己的状态机执行，直到超过了，这样就能够安全的提供了。执行请求，将结果返回给。 本系列文章主要面向 TiKV 社区开发者，重点介绍 TiKV 的系统架构，源码结构，流程解析。目的是使得开发者阅读之后，能对 TiKV 项目有一个初步了解，更好的参与进入 TiKV 的开发中。本文是本系列...
阅读 747·2021-09-22 15:26
阅读 2078·2021-09-14 17:57
阅读 2335·2021-09-09 11:52
阅读 1596·2021-09-02 09:52
阅读 2074·2021-08-12 13:28
阅读 1053·2019-08-30 15:53
阅读 359·2019-08-29 13:47
阅读 3251·2019-08-29 11:00
