Raft系列稿件之一: 什么是Raft
简单的说，Raft是一种易于理解的一致性算法，其功能相当于Paxos。目前很多提供一致性服务的系统都采用Paxos, 例如Chubby, ZooKeeper, 那么为何还需要Raft？自Lamport 1998年提出Paxos以来, 该协议虽逐渐成为主流一致性协议，但也以难以理解而著名，实现起来比较困难。针对Raft难以理解的缺陷，Raft 设计的主要目的之一就是容易理解，Raft将整个算法过程分解为若干个独立的子过程，并且详细描述了每个子过程如何实现，容易理解和实现。我自己也用Java实现了Raft, 代码在 https://github.com/chicm/CmRaft , 本系列文章的最后我将介绍我的实现。
本文主要参考了In Search of an Understandable Consensus Algorithm (Extended Version)，也包含了我自己的理解。
那么什么是一致性算法？
一致性是分布式容错系统的基本功能，例如在分布式共享文件系统中，通常有多台服务器向客户提供文件服务，当客户通过其中一台服务器A向文件系统存储了一个文件，如何保证能从服务器B获取刚刚保存的文件？其核心问题在于多台机器就某个值达成一致，一旦某个值达成了一致，客户向整个集群的任何一台机器请求该值时都会得到同一个值。一般一致性算法要求系统中大多数服务器处于可用状态，才可能就某个值达成一致。例如5台机器的集群，至少需要3台机器是可用的才可能就某个值达成一致，这一点通过反证法很容易理解，假设某个值通过集群的一半或一半一下服务器能达成一致，那么另外一半服务器也可能达成另一个一致，如果两个一致不同的话，就不是一致的。分布式系统的容错一般通过多副本状态机来实现。
多副本状态机
一致性算法通常产生于多副本状态机情景中，多副本状态机即集群中每个服务器维护一个状态机，它们维护同一数据状态的相同副本，当集群中一个或多个节点当掉时，整个集群仍然能够正常运行。多副本状态机用于解决分布式系统中的容错问题，例如在使用GFS, HBase的大型系统中，集群的Leader节点管理全系统配置信息，这些信息在Master 当掉时必须能够恢复, 这些系统通常使用多副本状态机来管理Leader选举和配置信息存储。Chubby和ZooKeeper都是多副本状态机。GFS使用Chubby, 而HBase使用ZooKeeper。
多副本状态机一般采用多分布日志来实现，上图是一个多副本状态机的例子。在上图中，服务器中存储的日志是命令的执行序列，状态机依次执行这些命令，每台服务器的状态机按相同顺序执行相同命令，因此每台状态机的输出状态也是一样的。这样说有点抽象，我们按上图中的例子来说明一下，例如有一个用来存储键值对的多副本状态机， 每台服务按相同顺序存储了如下命令：
1. 设置x=3
2. 设置y=1
3. 设置y=9
在多副本状态机每个副本上，状态机的状态为：x=3, y=9
一致性算法主要目标就是用来确保日志在多个副本上的一致性，例如在上例中，如果系统中有的状态机得到的日志顺序是1，2，3，有的是1，3，2，则就是出现了不一致的情况，一致性算法当然要避免出现这样的情况。
一致性算法一般具备如下特性：
正确性：任何条件下都能保证正确性，永远不向用户提供一个错误的结果
可用性： 只要多数节点可用，并能相互通信，系统就是可用的，5个节点的集群，只要有任何3个节点工作正常，整个系统就能正常使用。
不依赖时钟：即使有的节点时间设置是错误的，也能正常工作。
少数缓慢节点不影响全系统性能：只要大多数节点能及时响应，系统不会因为少数节点响应缓慢而性能低下。
Raft特性
Raft是专门针对Paxos难以理解的缺陷而重新设计的新算法，为使算法容易理解，采用了模块化设计方法，将整个过程划分为若干子过程，包括Leader选举，日志分发，确保一致性。Raft和已有的一致性算法有很多相似之处，但也有自己独特的特性：
Strong Leader： 相对其他一致性算法，Raft的Leader作用更强，例如，所有日志都是通过Leader分发给其他服务器，只有Leader接受客户请求。这一特性简化了日志管理，也让算法容易理解。
Leader选举：Leader选举过程采用随机时间计时器，这一看起来小小的改进简单有效快速地解决了Leader选举过程中的冲突。
成员变化：当集群的成员发生变化，例如增加或减少服务器时，Raft采用新的联合一致性方法来进行处理，可以保证成员变化过程中系统正常工作。
后面的系列文章中我会详细描述Raft原理及所有这些特性。
Raft算法由于其易于理解，在实现时就更容易把系统实现得更加健壮，因此是比Paxos及其他一致性算法更为优秀的算法。目前Raft已经有很多各种语言的实现，包括博主自己的基于Java的实现。