分布式一致性协议Raft

参考文档: https://blog.csdn.net/qq_18515155/article/details/120854235

什么是Raft

Paxos 是论证了一致性协议的可行性，但是论证的过程据说晦涩难懂，缺少必要的实现细节，而且工程实现难度比较高, 广为人知实现只有 zk 的实现 zab 协议。

Paxos协议的出现为分布式强一致性提供了很好的理论基础，但是Paxos协议理解起来较为困难，实现比较复杂。

然后斯坦福大学RamCloud项目中提出了易实现，易理解的分布式一致性复制协议 Raft。Java， C++，Go 等都有其对应的实现之后出现的Raft相对要简洁很多。引入主节点，通过竞选确定主节点。节点类型：Follower、Candidate 和 Leader。

说明:

Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间（我想称它为“静默时间”），一般为 150ms~300ms；
如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate（静默期已到，哥们我要出山了），进入竞选阶段；
通过竞选阶段的投票多的人成为Leader（当老大了）。

Raft相关概念

节点状态

Leader（主节点）：接受 Client 更新请求，写入本地后，然后同步到其他副本中。
Follower（从节点）：从 Leader 中接受更新请求，然后写入本地日志文件。对客户端提供读请求。
Candidate（候选节点）：如果 Follower 在一段时间内未收到 leader 心跳。则判断 leader 可能故障，发起选主提议。节点状态从 Follower 变为 Candidate 状态，直到选主结束。

Election Timeout：

选举超时时间（可以被重置）。是节点状态从Follower变为Candidate的时间，是一个150ms～300ms的随机值。

Heartbeat Timeout：

心跳超时时间。Leader节点会以固定的时间间隔定时给Follower节点发送心跳。

Election Term：

选举轮次。初始值为0，当某个节点从Follower 变为 Candidate时该节点的Term会加1。Term值越大表示当前leader越新。

Request Vote：

请求投票，Candidate 在选举过程中发起，收到多数派响应后，成为 Leader。

原理解析

Raft提供两个核心过程：日志复制和Leader选举。

日志复制

来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。

Leader 会把修改复制到所有 Follower。

Leader 会等待大多数的 Follower 也进行了修改，然后才将修改提交。
此时 Leader 会通知的所有 Follower 让它们也提交修改，此时所有节点的值达成一致。

Leader选举

初始阶段，只有 Follower，没有 Leader。Follower A 优先等待一个随机的Election Timeout（竞选超时时间）之后，没收到 Leader 发来的心跳包，因此进入竞选阶段。
A 发送投票请求给其它所有节点。

其它节点如果在当前Term没有投过票则会对请求进行回复，如果超过一半的节点回复了，那么该 Candidate 就会变成 Leader。

之后 Leader 会根据Heartbeat Timeout周期性地发送心跳包给 Follower，Follower 接收到心跳包，会重置Election Timeout。

Leader节点宕机

当之前选举的Leader A宕机，节点B和节点C在选举超时时间内没有收到Leader的心跳续约包，其中节点B优先结束选举超时时间即变为Candidate。

后续的流程和之前一样，只不过宕机的节点A不会做出任何响应。

多个Candidate竞争选举

如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票。
当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此下一次再次出现多个Candidate 并获得同样票数的概率很低。

网络分区处理

当出现网络分区后，如果某个分区没有Leader则会进行Leader选举。

当网络分区恢复后，多个分区里面的Leader取Term最大的一个作为分区恢复以后整个集群的Leader，然后向其他节点同步自己的数据。

总结

Raft是在Paxos协议基础上的一个便于理解，便于实现的分布式一致性协议。也经常被用在分布式系统和软件当中，其中就包括了大名鼎鼎的Redis，两者都是保证了CAP理论中的“AP”。

通过了解也发现Raft的Leader选举和日志复制过程巧妙又有趣，对于入门分布式，以及了解分布式系统面临的问题有很大的帮助。

Raft的实现

GO: https://github.com/hashicorp/raft

C++: https://github.com/eBay/NuRaft

Java: https://github.com/atomix/copycat

CAP 原则

参考文档: https://baike.baidu.com/item/CAP%E5%8E%9F%E5%88%99/5712863

简介

CAP原则又称CAP定理，指的是在一个分布式系统中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼。

一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）
可用性（A）：保证每个请求不管成功或者失败都有响应。
分区容忍性（P）：系统中任意信息的丢失或失败不会影响系统的继续运作。

CAP原则的精髓就是要么AP，要么CP，要么AC，但是不存在CAP。如果在某个分布式系统中数据无副本，那么系统必然满足强一致性条件，因为只有独一数据，不会出现数据不一致的情况，此时C和P两要素具备，但是如果系统发生了网络分区状况或者宕机，必然导致某些数据不可以访问，此时可用性条件就不能被满足，即在此情况下获得了CP系统，但是CAP不可同时满足。

因此在进行分布式架构设计时，必须做出取舍。当前一般是通过分布式缓存中各节点的最终一致性来提高系统的性能，通过使用多节点之间的数据异步复制技术来实现集群化的数据一致性。通常使用类似 memcached 之类的 NOSQL 作为实现手段。虽然 memcached 也可以是分布式集群环境的，但是对于一份数据来说，它总是存储在某一台 memcached 服务器上。如果发生网络故障或是服务器死机，则存储在这台服务器上的所有数据都将不可访问。由于数据是存储在内存中的，重启服务器，将导致数据全部丢失。当然也可以自己实现一套机制，用来在分布式 memcached 之间进行数据的同步和持久化，但是实现难度是非常大的。

可用的抉择

CAP理论就是说在分布式存储系统中，最多只能实现上面的两点。而由于网络硬件肯定会出现延迟丢包等问题，所以分区容错性是我们必须需要实现的。所以我们只能在一致性和可用性之间进行权衡，没有NoSQL系统能同时保证这三点。对于web2.0网站来说，关系数据库的很多主要特性却往往无用武之地。

数据库事务一致性需求：很多web实时系统并不要求严格的数据库事务，对读一致性的要求很低，有些场合对写一致性要求并不高。允许实现最终一致性。
数据库的写实时性和读实时性需求：对关系数据库来说，插入一条数据之后立刻查询，是肯定可以读出来这条数据的，但是对于很多web应用来说，并不要求这么高的实时性，比方说发一条消息之后，过几秒乃至十几秒之后，我的订阅者才看到这条动态是完全可以接受的。
对复杂的SQL查询，特别是多表关联查询的需求：任何大数据量的web系统，都非常忌讳多个大表的关联查询，以及复杂的数据分析类型的报表查询，特别是SNS类型的网站，从需求以及产品设计角度，就避免了这种情况的产生。往往更多的只是单表的主键查询，以及单表的简单条件分页查询，SQL的功能被极大的弱化了。

与NoSQL的关系

传统的关系型数据库在功能支持上通常很宽泛，从简单的键值查询，到复杂的多表联合查询再到事务机制的支持。而与之不同的是，NoSQL系统通常注重性能和扩展性，而非事务机制（事务就是强一致性的体现）。

传统的SQL数据库的事务通常都是支持ACID的强事务机制。

A代表原子性，即在事务中执行多个操作是原子性的，要么事务中的操作全部执行，要么一个都不执行；
C代表一致性，即保证进行事务的过程中整个数据库的状态是一致的，不会出现数据花掉的情况；
I代表隔离性，即两个事务不会相互影响，覆盖彼此数据等；
D表示持久化，即事务一旦完成，那么数据应该是被写到安全的，持久化存储的设备上（比如磁盘）。

NoSQL系统仅提供对行级别的原子性保证，也就是说同时对同一个Key下的数据进行的两个操作，在实际执行的时候是会串行的执行，保证了每一个Key-Value对不会被破坏。

与BASE的关系

BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的简写。

BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于CAP定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。接下来我们着重对BASE中的三要素进行详细讲解。基本可用：指分布式系统在出现不可预知故障的时候，允许损失部分可用性。

注意，这绝不等价于系统不可用，以下两个就是“基本可用”的典型例子：

响应时间上的损失：正常情况下，一个在线搜索引擎需要0.5秒内返回给用户相应的查询结果，但由于出现异常（比如系统部分机房发生断电或断网故障），查询结果的响应时间增加到了1~2秒。

功能上的损失：正常情况下，在一个电子商务网站上进行购物，消费者几乎能够顺利地完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。

弱状态：也称为软状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

最终一致性：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

分布式系统

分布式系统（distributed system）是建立在网络之上的软件系统。正是因为软件的特性，所以分布式系统具有高度的内聚性和透明性。因此，网络和分布式系统之间的区别更多的在于高层软件（特别是操作系统），而不是硬件。在一个分布式系统中，一组独立的计算机展现给用户的是一个统一的整体，就好像是一个系统似的。系统拥有多种通用的物理和逻辑资源，可以动态的分配任务，分散的物理和逻辑资源通过计算机网络实现信息交换。系统中存在一个以全局的方式管理计算机资源的分布式操作系统。通常，对用户来说，分布式系统只有一个模型或范型。在操作系统之上有一层软件中间件（middleware）负责实现这个模型。一个著名的分布式系统的例子是万维网（World Wide Web），在万维网中，所有的一切看起来就好像是一个文档（Web页面）一样。

在计算机网络中，这种统一性、模型以及其中的软件都不存在。用户看到的是实际的机器，计算机网络并没有使这些机器看起来是统一的。如果这些机器有不同的硬件或者不同的操作系统，那么，这些差异对于用户来说都是完全可见的。如果一个用户希望在一台远程机器上运行一个程序，那么，他必须登陆到远程机器上，然后在那台机器上运行该程序。