在学习 Raft 算法之前，我们有必要知道何为分布式系统、分布式系统存在的问题、CAP、Base 定理等。
1 何为分布式系统
随着互联网用户规模和业务复杂度的急速增长，单台服务器早已无法满足现代应用在性能、可用性和扩展性上的需求。无论是电商平台的秒杀活动、社交网络的海量动态，还是视频网站的高并发点播，数据量和访问量都呈指数级上升。
因此，如何提高大规模数据的读写性能就成为了一个难以避过的话题。
一方面，我们可以通过升级硬件，比如使用更快的 CPU、更大的内存、更高的存储容量来解决，但事实上，无论多强的硬件始终都会受到物理极限的约束，还不免带来了单点故障的问题，同时硬件不断升级的成本也在不断上升，这带来的 ROI 是越来越小的，就像考试时，从 95 分提升到 98 分的难度可能远远超过从 60 分提升到 90 分。
所以，我们更多的还是将目光放在了横向扩展这个层面，也就是所谓的分布式系统。
所谓分布式系统，就是一个系统中的多个节点（通常是多台服务器）通过网络协作完成一个任务，单个节点只负责部分功能或数据（按业务功能拆分服务、按数据分片存储、任务拆分计算等），对外看起来是一个整体系统。
而在我的理解中，分布式系统是有别于集群的，虽然集群和分布式一样，都是整体对外提供服务的，但是集群中多个节点提供的是相同/相似的服务，并且通常会有一个统一入口（负载均衡器），节点之间可以是对等的，也可以是主从的。
分布式侧重于拆分任务，协同完成，比如用户在淘宝下单时的每个步骤的处理可以被拆分到不同的服务器或微服务上。例如，支付、库存管理、订单管理、物流系统可能分别部署在不同的服务器上，它们通过网络进行通信和协同工作，保证每个任务顺利完成。
而集群侧重于多个节点提供相同/相似的服务，比如 MySQL 的主从集群，无论是主库还是从库，都是提供数据库服务，多个从库之间可以进行读请求的负载均衡。
在我第一次学习 Raft 算法的时候，我不是很理解为什么会将其称为“分布式”共识算法，因为 Raft 算法看上去是在一堆节点组成的主从集群里讨论的。
事实上，到现在我也没想明白，我对自己的解释是，在分布式系统里面会有集群，而在集群内部需要共识算法保证内部状态一致，所以共识算法被称为分布式共识算法。
这篇文章主要是 Raft 算法的前篇，所以我们将目光聚焦在分布式系统内部的集群节点，而非进行“实际”的分布式系统，下文所描述的分布式系统可以理解为集群。
2 网络的不确定性
虽然引入分布式系统带来了很大的收益，通过将任务分散到多台机器上，系统可以横向扩展，根据需求动态增加计算和存储资源。而且，通过分布式架构中的数据冗余（避免单点故障/数据丢失）、容错机制和负载均衡，系统能够高效应对大规模并发请求，减少单点故障的风险，从而提升系统的可用性、容错性和灵活性。
但是伴随着收益而来的一个最大的问题在于网络的不确定性 —— 丢失、超时、乱序，这些情况的发生导致了分布式系统整体复杂度的上升。事实上，分布式系统中还有一个问题是“节点故障”，但是该问题最终可以归结到网络超时这里，所以我认为分布式系统中最大的问题在于“网络的不确定性”。
3 CAP 定理
CAP 理论中阐明：在一个分布式系统中，最多只能同时满足一致性、可用性、分区容错性的两者。
（1）一致性：在任何时候，分布式系统中的所有节点都必须保持数据一致性，客户端始终读取到最新的数据。
（2）可用性：分布式系统保证每个客户端请求都能在有限的时间内得到响应，但是这不保证数据是最新的。
（3）分区容错性：分布式系统能够容忍网络分区（部分节点之间出现网络故障而无法通信），也就是系统能够处理不同节点之间的通信失败，不会因为部分节点无法访问导致整个系统崩溃。
由于分布式系统中的网络问题，所以网络分区是必然的，而我们是必须要保证分区容错性的，否则谈何分布式系统呢，一旦出现网络分区，系统就会崩溃，那还不如单机系统。
那为什么 CAP 定理是这样的呢，或者说如何证明 CAP 定理。
（1）当前集群有一主两从三个节点，初始 x 值为 0
（2）此时客户端发出写请求，写入 x = 1
（3）紧接着，客户端又发起读请求，在从节点查询 x 的值
那么客户端在（3）读取到的 x 是多少呢？因为网络是不确定的，所以我们没办法保证客户端读取的时间一定在 master 将数据同步完成之后。
如果系统优先保证可用性，那么 master 节点在完成写操作后，无需等待数据同步到 slave 节点，而是立即返回写入成功的响应给客户端。这样可以确保系统快速响应客户端请求，但由于 slave 节点可能尚未同步数据，客户端在读取时可能会访问到过时的数据 x = 0，导致一致性被破坏。
相反，如果系统优先保证一致性，则 master 节点必须等待所有 slave 节点完成数据同步后，才能返回写入成功的响应。这虽然保证了数据一致性，但是可用性也遭到了破坏，因为在网络分区必然存在的情况下，如果 slave 节点宕机，那么 master 将永远不能返回给客户端写入成功的响应。
所以在 P 的情况，如何选择 A 和 C，就又成为一个不可避免的问题了。
到这里，你有没有发现，CAP 理论的阐述貌似有点问题，或许正确的应该是：在一个分布式系统中，一致性和可用性只能满足其中一个。分区容错性在提到分布式系统时已经隐含了。
4 Base 理论
CAP 定理揭示了一致性和可用性在网络分区下的根本矛盾。而 BASE 理论正是针对 AP 系统而提出的一套设计哲学和实践准则。它承认在大型分布式系统中，尤其是在互联网应用场景下：
（1）强一致性代价太高（性能、延迟、可用性）。
（2）业务上往往可以接受一定程度、一定时间的数据不一致。
（3）高可用性是用户体验和系统鲁棒性的关键。
因此，BASE 理论的核心思想是：在无法保证强一致性的现实下，通过放宽对一致性的要求，最大限度地保证系统的可用性和可扩展性。
BASE 不是一套具体的协议，而是一种务实的设计理念，指导开发者在可用性、一致性和性能之间做出符合业务需求的权衡。
BASE 是三个特性的首字母缩写，即“基本可用、软状态、最终一致性”。下面我们逐一解释一下。
4.1 B - Basically Available
分布式系统在出现不可预知的故障（如机器宕机、网络抖动，包括但不限于网络分区）时，允许损失部分功能或降低部分性能，但核心功能仍然保持可用。
比如，在高峰时段或系统压力大时，可以关闭非核心功能（如商品评论、个性化推荐），保证核心交易链路（下单、支付）可用。或者将用户请求引导到备用资源/页面。
分区时的可用性：在网络分区发生时，分区两侧只要还有节点存活，就能继续提供服务（即使数据可能不一致）。
4.2 S - Soft State
允许分布式系统中的数据存在中间状态，并且这个状态不需要在系统内所有副本间实时同步保持一致。软状态是相对于强一致性要求的“硬状态”（所有副本在任何时刻都必须一致）而言的。
比如在异步复制时，数据写入一个节点成功后即可返回，数据同步到其他副本的操作在后台异步进行。这期间不同副本的数据就是软状态（可能不一致）。
4.3 E - Eventually Consistent
这是 BASE 理论的最终目标。如果在一段时间内没有新的数据更新操作发生，那么最终（经过一个不确定的时间窗口：收敛时间），所有对数据的读取操作都将返回最后一次更新的值。简单说，不一致是暂时的，系统最终会达成一致。
这其实就是“一致性”中的最终一致性，会在下个章节详细描述。
5 深入理解一致性
CAP 定理表示，在一个分布式系统中，一致性和可用性只能满足其中一个。但事实上，可用性和一致性并非是站在绝对意义的对立面的，是存在可以调和取舍的空间的，就像黑与白之间的灰色地带。
而一致性模型就是在 C 和 A 之间进行权衡取舍的具体体现。
分布式一致性模型定义了在分布式系统中，当数据被复制到多个节点时，客户端对这份数据副本进行读写操作时所应该遵循的规则。
其中的核心问题在于：在分布式系统（网络延迟、节点故障）的不可靠环境下，如何让分散在各地的副本保持“一致”？以及这个“一致”到底意味着什么？不同的模型对“一致”有不同的定义和要求。
一些常见的一致性模型包括：线性一致性、顺序一致性、因果一致性和最终一致性等。
5.1 线性一致性
线性一致性是分布式一致性模型中最严格、最直观，但也是最难实现、性能开销最大的一种强一致性模型，CAP 中的 C 一般指的就是线性一致性，也被称为严格一致性、原子一致性。
我们想象在一个单机数据库服务器上，当多个客户端向它发起读写请求时，它是符合下面三个特征的。
（1）操作是顺序发生的，所有操作（读和写）一个接一个的执行，形成一条清晰的历史记录线，或者说是一个全局唯一的、所有操作（读和写）组成的总顺序。
（2）读操作看到新鲜写，任何一个读操作，都必须返回在（1）中所描述的“全局顺序”中的，它（指当前的这个读操作）之前最后一个完成的写操作的结果。
（3）符合真实全局时间顺序，如果一个写操作 w1 在实际时间上发生在另一个写操作 w2 之前，并且 w2 覆盖了 w1 写入的值，那么任何后续的读操作都不会再看到 w1 的值（除非新的写操作覆盖了 w2）。
那么，线性一致性的核心思想就在于：让分布式系统“看起来”像单机系统一样，即使数据被复制在多个节点上。
所以，线性一致性的要求也就是上面所描述的三点。
而所谓的“线性”也就是指所有操作可以排列在一条全局时间线上（全局唯一顺序），这条线符合真实时间的先后关系，并且读操作的结果完全由这条线上它之前最后发生的写操作决定。就像一条直线一样清晰、没有歧义。
那如何判断线性一致性呢？假设有下面这样的一个执行历史，横轴表示时钟。
每一个长方形表示一个读或写操作，中间的持续时间表示执行对应的操作，并在其中的某个时刻完成了该操作，这样注意，并不是在长方形右边界的时刻完成操作，可以理解为客户端收到对应操作的响应，真正操作执行成功的时刻是不确定的。
- 不同操作如果在逻辑时钟上没有重叠的部分，就说按操作顺序排列存在顺序关系，比如 write(x,4) 和 read(y,2)。
- 不同操作如果在逻辑时钟上存在重叠的部分，就说按操作顺序排列存在并发关系，比如 write(x,4) 和 write(y,2)。
判断线性一致性的方式就是：根据给定的执行历史，按照顺序关系和并发关系扩展出所有的顺序历史，只要找到一个合法的顺序历史，那么该执行历史就是符合线性一致性的。
比如上面的执行历史，可以扩展出的顺序历史如下：
可以看到，由于 read(x,0) 的错误，这个执行历史并不是线性一致性的。
5.2 顺序一致性
顺序一致性相较于线性一致性稍弱一些，但是仍然属于强一致性模型的范畴内。
它的核心思想是让分布式系统“看起来”像在单机上按“某种顺序”串行执行了所有进程的操作，并且每个进程自身的操作顺序在这个串行序列中得到保持。
和“线性一致性”类似，顺序一致性也存在一个全局顺序：即线性一致性描述中的（1），也要求读操作看到新鲜写：即线性一致性描述中的（2）。
不同的地方在于，顺序一致性**不要求“全局顺序”符合真实的全局物理时间顺序，但是必须要保证进程内部的“程序顺序”。**所谓“程序顺序”指的是：如果某个进程先执行操作 A，再执行操作 B，那么在全局顺序中操作 A 必须出现在操作 B 之前。
还是上面的例子，如果脱离全局时钟的存在，那么这个执行历史是可以满足顺序一致性的。
这个顺序对于两个进程内部的读写顺序都是合理的，并且逻辑也是正确的。
所以，从逻辑上来说，判断一个执行历史是否是顺序一致性的，只需要在保证每个进程上执行的操作的顺序的前提下，如果能找出一个逻辑正确的顺序历史，那么它（指执行历史）就是顺序一致性的。
5.3 因果一致性
因果一致性，属于弱一致性的范畴内，它旨在解决弱一致性中可能出现的、违反直觉且通常不可接受的“因果颠倒”问题，同时比强一致性提供更好的性能和可用性。
因果一致性的核心思想在于：能够捕获并且保持“因果”依赖关系。
也就是说，所有因果相关的操作，必须在所有进程上以相同的顺序被观察到，而没有因果关系的操作可以在不同进程上以不同的顺序被观察到。
因果一致性比顺序/线性一致性更弱，因为它不要求一个全局唯一的操作序列，只要求因果相关的操作序列一致，不同进程看到的非因果序列可以不同。但它又比最终一致性更强，它在最终一致性的基础上，额外保证了因果关系的顺序，避免了“因果颠倒”这种在最终一致性中可能出现的、令人困惑甚至错误的情况。
看一个没有满足因果一致性的经典例子。
- 在南京市的 A 在朋友圈发表状态“我戒指丢了”。
- 接着 A 在同一条状态下评论“我找到了”。
- 在新加坡的 B 在同一条评论下评论“太棒了”。
若没有因果一致性，则会发生则会发生如下的事情：
- 在美国的键盘侠 C 看到的是“我戒指丢了”“太棒了”，开始喷 B。
- 然而过了一会，更新完后，C 又看到了“我戒指丢了”“我找到了”“太棒了”，意识到自己喷错人了。
由于物理距离（南京/新加坡 -> 美国）导致网络传输延迟，以及服务于不同区域的数据中心同步存在时间差，远在美国的 C 可能先看到 A 的丢失状态和 B 的祝贺评论，却缺失了中间“找到戒指”这个关键原因。
这种分布式系统中事件写入和传播顺序的短暂不一致（即不满足因果一致性），让 C 误以为 B 在幸灾乐祸，从而冲动开喷，直到稍后数据完全同步才尴尬地发现是自己看错了信息顺序。
5.4 最终一致性
最终一致性是分布式系统中最常用、最核心的弱一致性模型。它代表了在可用性、分区容忍性和性能与强一致性之间所做的最根本的权衡。
它的核心思想在于牺牲即时一致性，换取高可用和低延迟，并保证数据最终会一致。
如果对某个数据项不再有新的写操作，那么经过一段时间（“收敛时间”）后，所有对该数据项的读取操作最终都将返回最后写入的那个值。
“最终”表示不一致的状态是暂时的，不是永久的，系统最终会消除不一致的情况。
下面再来看一看在最终一致性下的读写问题。
（1）读取到旧值，也就是臭名昭著的 Stale Read（过期读），比如在社交媒体上，用户更新了自己的头像，然后立刻刷新页面，可能看到的还是旧头像。原因在于，写操作可能只更新了主副本或部分副本，而读请求可能被路由到了一个尚未收到更新的副本。
（2）违反单调读一致性（后面会解释），在收敛期内，同一客户端的连续读取可能读到不同的值，因为不能确定客户端读取时路由到了哪个副本。
（3）不同客户端可能读到不同的值，这其实和第（2）点是同一个道理。
对于上面的三个问题，其实并不是什么大问题，只要我们正确的实现最终一致性，并且从业务角度来说，可以容忍一些不一致的时间，那么在等待足够的“收敛时间”后，数据总会保持一致的。
但对于并发写入的场景来说，就可能会导致一些无法容忍的问题，这可以说是“最终一致性”最大的挑战。
考虑上面的场景，当两个客户端进行并发写入时，由于网络的不确定性，那么第 2 步进行数据同步时，不同的 slave 节点可能以不同的顺序应用这些写入，所以就出现了上图中 master 和 salve2 节点 x 值为 2，但是 slave1 节点 x 值为 1 的情况。
最终结果可能不确定，所以系统需要一种冲突解决机制来决定哪个写入“胜出”。
最常见的解决并发写入冲突的策略就是 Last Write Wins，即最后写入获胜，该策略会为每个写入附加全局时间戳（物理或者逻辑时钟），不同的副本节点保留时间戳最大的写入。
5.5 最终一致性的变体模型
为了在最终一致性的框架下提供更好的用户体验或特定保证，还发展出了一些增强模型。
（1）读写一致性：保证用户总能看到自己提交的更新。自己写的东西，自己刷新后一定能看到。
（2）单调读一致性：一个用户不会看到数据“时光倒流”。如果用户读到了某个值 V（版本 N），那么后续的任何读取操作返回的值，其版本号都大于或等于 N（即至少和 V 一样新，或者更新）。
（3）单调写一致性：一个用户的多个写操作会按照其发出的顺序被所有副本执行。不会发生乱序覆盖。
（4）会话一致性：在一个用户会话（Session）期间，结合提供读写一致性+单调读一致性（通常也隐含单调写一致性）。这是对用户体验最重要的增强。
6 分布式共识算法
分布式共识算法是指在分布式系统中，确保多个节点就某个值或状态达成一致的机制。可以说，共识算法是实现 CP 系统的关键工具。
常见的“非拜占庭”分布式共识算法包括 Paxos、Raft、ZAB 等。
所谓“非拜占庭”是指我们假设分布式节点只会 Crash 或者出现网络延迟，而不会故意作恶。
其中 Paxos 算法是首个在 1990 年被证明正确的共识算法，但是其描述抽象，工程实现及其困难。
而 Raft 算法通过模块化设计（Leader 选举/日志复制/安全）大大简化了算法理解难度和工程实现难度，广泛用于 etcd、TiDB 等系统。