Raft和它的三个子问题

这篇文章来源于一个经常有人困惑的问题：Quorum与Paxos，Raft等一致性协议有什么区别，这个问题的答案本身很简单： 一致性协议大多使用了Quorum机制，但仅仅有Quorum(R+W>N)机制是保证不了一致性的 。本文计划延伸这个问题，以Raft为例回答一个完善的一致性协议拥有包括Quorum在内的那些机制，试着说明这些机制的完备以及其中每一项的不可或缺。

要回答这个问题首先需要说明Raft是做什么的，Paxos、Raft被称为一致性协议，顾名思义它们要解决的是多节点的一致性问题，需要注意的是这里所说的一致性并不是要求所有节点在任何时刻状态完全一致。而是要保证：

即使发生网络分区或机器节点异常，整个集群依然能够像单机一样提供一致的服务，即在每次 *** 作时都可以看到其之前的所有成功 *** 作按顺序完成。

这里有两点需要说明：

将每一个对Raft集群的 *** 作称为一个提案，希望Raft集群对外屏蔽内部的网络或节点异常，依次对每一个提案作出相应，提交成功的提案可以在后续 *** 作中持续可见。这里的提案需要是幂等的，即重复执行不会导致集群状态不同。

接下来我们就看Raft是如何实现这种一致性保证的。Raft将一致性问题拆分为三个子问题，各个击破，从而使得其实现简单易懂。本文将首先简单介绍其三个子问题的内容以及达成方式；之后证明三个子问题是实现一致性的充分条件；最后尝试说明这三个子问题的保证缺一不可。

组成一个Raft集群至少需要三台机器，而Raft限制每一时刻最多只能有一个节点可以发起提案，这个限制极大的简化了一致性的实现，这个可以发起提案的节点称为Leader。因此所要解决的第一个 问题 便是：

如上图所示：

从上面对Raft状态转换的讨论中可以看到，任何非Leader的节点都有可能在未来成为Leader，为了能保证后续Leader节点变化后依然能够使得整个集群对外保持一致，需要通过Log Replication机制来解决如下两个问题：

上图描述了一个Raft提案的执行过程：

Follower在接受AppendEntry时会检查其前一条的Log是否与Leader相同，利用数学归纳法可以很简单的证明Leader和Follower上的Log一致。另外，由于只需要过半数的节点成功即可返回，也就在保证一致性的前提下竟可能的提高了集群的可用性。

这里需要注意， Leader Commit过的提案会向用户返回成功，因此Raft集群需要保证这些提案永远存在 。

通过上述的两个子问题已经解决了大部分的难题，除了下面两个细节：

通过上述的三个子问题的解决，我们得到了一个完善的一致性算法，论文中给出了详细严谨的证明，其首先假设Commit过的提案会在后续丢失，之后推导出矛盾进而反证成功，这里不再赘述。该证明的关键点在于：Leader Election中要求新Leader获得超过半数的节点投票，Log Replication中每个Commit都有超过半数的节点同意，因此这两个大多数中至少存在一个公共节点，这个节点既同意了某个提案的Commit又投票给了新的Leader。

上面讨论了三个子问题对一致性的充分性，接下来要讨论的是在Raft的框架下，任何一个子问题的缺失都会导致严重的不一致后果：

通过上面的讨论，可以看出一个完整的一致性协议做了包括Quorum在内的诸多努力。Raft划分了三个子问题来使得整个一致性算法的实现简单易懂，我们也基于Raft实现了自己的一致性库 Floyd 来满足诸如 Zeppelin 元信息集群及 Pika 跨机房功能中对一致性的需求。

In Search of an Understandable Consensus Algorithm

Qihoo360 Floyd

--listen-peer-urls

--listen-client-urls

--initial-advertise-peer-urls

--initial-cluster

--initial-cluster-state

--advertise-client-urls

1code

headless svc, 像DNS RR ClusterIP:None

kubectl -n stg1 get endpoints

client 怎么访问：

2配置文件

3apply

官方的code有两个问题

本地访问

扩容

利用反亲和性 分布etcd pod到不同节点

~ ❯❯❯ etcdctl get / --prefix

从 etcd 的架构图中我们可以看到，etcd 主要分为四个部分。

etcd 目前支持 V2 和 V3 两个大版本，这两个版本在实现上有比较大的不同，一方面是对外提供接口的方式，另一方面就是底层的存储引擎，V2 版本的实例是一个纯内存的实现，所有的数据都没有存储在磁盘上，而 V3 版本的实例就支持了数据的持久化。

v3默认boltdb

consortium etcd2+mysql

数据默认会存放在 /var/lib/etcd/default/ 目录。我们会发现数据所在的目录，会被分为两个文件夹中，分别是 snap 和 wal目录。

解决三个问题：节点选举、日志复制以及安全性 。

每一个 Raft 集群中都包含多个服务器，在任意时刻，每一台服务器只可能处于 Leader 、 Follower 以及 Candidate 三种状态；在处于正常的状态时，集群中只会存在一个 Leader 状态，其余的服务器都是 Follower 状态。

所有的 Follower 节点都是被动的，它们不会主动发出任何的请求 ，只会响应 Leader 和 Candidate 发出的请求。对于每一个用户的可变 *** 作，都会被路由给 Leader 节点进行处理，除了 Leader 和 Follower 节点之外，Candidate 节点其实只是集群运行过程中的一个临时状态。

每一个服务器都会存储当前集群的最新任期，它就像是一个单调递增的逻辑时钟，能够同步各个节点之间的状态，当前节点持有的任期会随着每一个请求被传递到其他的节点上。Raft 协议在每一个任期的开始时都会从一个集群中选出一个节点作为集群的 Leader 节点，这个节点会负责集群中的日志的复制以及管理工作。

客户端通过 监听指定的key可以迅速感知key的变化并作出相应处理 ，watch机制的实现依赖于 资源版本号revision的设计 ，每一次key的更新都会使得revision原子递增，因此根据不同的版本号revision的对比就可以感知新事件的发生。etcd watch机制有着广泛的应用，比如利用etcd实现分布式锁； k8s中监听各种资源的变化 ，从而实现各种controller逻辑等。

watch机制的实现主要可分为三个部分

client使用 watchClient 的watch接口发起watch请求，与server端建立一个 gRPCStream 连接。

server端会为每个client生成唯一一个watch id，并记录每个client也就是watcher监听的key或者key range，通过recvLoop接收client请求，通过sendLoop发送请求，server端只负责收发请求和响应。

主要的实现都放在了watchalbStore层，watchalbStore会监听key的变化，然后通过syncWatchersLoop和syncVictimsLoop两个处理流程将key的更新变化包装成event，通过channel发送给gRPC server。

MVCC（Multiversion Concurrency Control）多版本并发控制机制

场景1:

这就是悲观锁

悲观锁：悲观得认为并发事务会冲突，所以要先拿锁，拿到锁的作修改 *** 作

场景2

数据库：写回磁盘，A写好了。哎，B和C都是version 13，我咋写？算了，报错吧。。

就是乐观锁，默认不加锁，你尽管写，冲突我认怂！乐观锁其实不是锁，只是相对悲观锁来定义，适合读多写少。

乐观锁：乐观得认为数据不会冲突，但发生冲突时要能检测到。

场景3

这就是MVCC，在 MVCC 数据库中，你更新一个 key-value 数据的时候，它并不会直接覆盖原数据，而是 新增一个版本来存储新的数据，每个数据都有一个版本号 ，版本号是一个逻辑时钟，不会因为服务器时间的差异而受影响。

MVCC不等于乐观锁！

--rev 查的是main

在底层boltdb里，实际分布是这样的：

底层的key是revision，/奥特曼是用户key，“他很帅”就是用户value

删除

之前有delete动作，但是依然有版本记录。为什么？

删除这个动作，其实etcd是在blotdb里写了一条，“删除用户/奥特曼”

此时有个问题：用户说我的确删除了啊，真的不要了！请把空间还给我啊！

回收 compact（压缩）

etcdctl compact {version}

compact 需要一个版本号。这个版本号就是写事务递增的那个版本号，compact 12345，就是说把版本12345以前的 标记删除了的数据 释放掉，用户没删除的数据肯定不能回收。

如何压缩：

注意修改gomod

Watch

服务发现要解决的也是分布式系统中最常见的问题之一，即在同一个分布式集群中的进程或服务，要如何才能找到对方并建立连接。本质上来说，服务发现就是想要了解集群中是否有进程在监听 udp 或 tcp 端口，并且通过名字就可以查找和连接。

需要实现的功能；

discovergo

eBay payment

ebay kubernetes 控制面架构

问题

本文将以阿里云在GIAC的分享《云原生InfluxDB高可用架构设计》为例，剖析阿里云的自研InfluxDB集群方案的当前实现，在分析中会尽量聚焦的相对确定的技术、架构等，考虑到非一线信息，在个别细节上难免存在理解偏差，欢迎私聊讨论:

0x0 初步结论

目前是一个过渡性质的公测方案，具备数据一致性，但接入性能有限，缺乏水平扩展能力。缺乏自定义副本数和水平扩展等能力，通过Raft或Anti-entroy提升了数据的可靠性，但受限于节点和副本的强映射，集群接入性能有限，约等同于单机接入性能，另外，基于时序分片和分布式迭代器等核心功能未提及，可能仍在预研中。

0x1 集群方案剖析

1 背景补充：InfluxDB是DB-Engines上排名第一的TSDB，针对时序数据多写、少读、成本敏感等特点而设计的TSDB，并做了多轮架构迭代和优化，是一款实时、高性能、水平扩展（InfluxDB Enterprise）、具有成本优势的TSDB。但在2016年，Paul Dix基于商业化和持久运营的考虑，尚未成熟的集群能力在v0111版后，选择闭源，推出了收费版的InfluxDB Enterprise和InfluxDB Cloud。

2 通过Raft协议实现Meta节点的数据一致性，考虑到Meta节点存放的是Database/Rention Policy/Shard Group/Shard Info等元信息，这些信息敏感，是系统稳定运行的的关键，CP的分布式架构，合适。

3 通过Raft协议实现Data节点的数据一致性，考虑到Data节点存储的是具体的时序数据，性能和水平扩展性是挑战，对一致性性要求不高（PPT中亦提到这一点），采用CP的分布式架构，节点和副本强映射，不仅对实时性有影响，集群接入性能亦有限，约等同于单机接入性能，不能很好的支持海量数据的实时接入的时序需求。

4 2节点集群方案，通过Anti-entroy实现Data节点的数据一致性，应该还实现了Hinted-handoff能力，AP的分布式架构，但节点和副本还是强映射，未见提及基于时序分配、自定义副本数、分布式迭代器等能力，暂无法水平扩展。

5 云盘能保障数据的可靠性，但无法保障接入的可用性，可用性敏感的业务或实时要求高的业务，还是推荐多节点的集群模式。

6 开源版InfluxDB（单机）性能不错，InfluxDB Enterprise性能不错，但如何保障补齐集群能力的卓越性能，取决于集群架构、并发架构等，是由集群功能的开发者决定的，这次未见提及性能数据，期待后续的公布。

0x2 附录

如果你搭建过大型的分布式系统，那么一般你会用到zookeeper这个服务。该服务实现了ZAB算法。其通常会用在fail over选主，微服务上下游server配置中心等场景。但是ZAB和paxos有个缺点，就是理解性比较差。其论文内容十分复杂，导致真正理解的开发人员非常少。 知乎：raft算法与paxos算法相比有什么优势，使用场景有什么差异

raft homepage

raft paper

live demo

raft和zookeeper类似，一般需要3或者5个node。这样有利于判断选举的多数情况

node分为3个状态：follower，candidate，leader

状态的转换

raft有2个timeout设置

1）从follow而转换到candidate的timeout： election timeout，设置为：150ms到300ms中的随机数。一个node到达这个timeout之后会发起一个新的选举term（递增的，大的表示新的），向其他节点发起投票请求，包括投给自己的那票，如果获得了大多数选票，那么自己就转换为leader状态

2）node成为leader之后会向其他node发送Append Entries，这个时间为heartbeat timeout

如果lead在实际使用中down掉，剩下的节点会重新开启1）和2）描述的选举流程，保证了高可用性

特殊情况

如果集群中剩下偶数个node，并且在选举的过程中有2个node获得相等的选票数，那么会开启新的一轮term选举。知道有一个node获得多数选票（随机的election timeout保证可行）

client给leader发送数据修改请求

leader通过Append Entries在心跳的过程中将修改内容下发到follower nodes

在多数follower 接收了修改内容返回后，leader向client确认

leader向follower发送心跳，具体执行修改 *** 作，此后数据在集群中保持一致

特殊情况

节点之前的网络状况十分不好，此时会有多个leader，其term也是不同的。

由于commit的修改需要多数通过，那么只有具有最多node的一个集群会commit修改成功。

当网络状况恢复，整个集群的节点会向多数节点的集群同步。这样整个集群中的数据会继续保持一致

live demo中没有提及，但是paper中说明的内容。

在实际使用中可有可能会遇到现有机器被新机器替换，或者为了提升稳定性扩容raft集群的情况。作者给出了joint consensus的解决方案。其能保证切换过程是无缝的。

Paxos问题指分布式系统中存在故障fault，但不存在恶意corrupt节点场景（消息可能丢失但不会造假）下的共识达成（Consensus）问题。

Paxos是第一个被证明的共识算法，原理基于两阶段提交并进行扩展。算法中将节点分为三种类型：

每个节点在协议中可以担任多个角色。

Paxos的特点：

假设5个节点构成分布式系统，A和E节点分别有X和Y提案，其他节点没有提案。

然后A节点广播它的提案，强假设网络延迟的原因，只有A，B，C节点收到提案，这里的提案哪怕A，E节点的提案同时到某个节点，也必然会有先后顺序的，是不可能真正意义上的同时。

A，B，C接收到A的提案后，由于是第一个接收到的提案，acceptedProposal和acceptedValue都为空，诚实返回。

由于A节点已经收到超半数的节点相应，且返回的acceptedValue都为空，也就是说可以用X作为提议的值来发生Accept请求，A，B，C节点接收到请求后，将acceptedValue更新为X。

A，B，C节点会发生minProposal给A，A检查发现没有大于1的minProposal出现，此时X已经被选中。此时，由于D，E节点的acceptedValue并不是X，系统还没有达成一致共识，Paxos过程还是没有结束。

E节点选择Proposal ID为2发送Prepare请求，结果和上面是一样的，因为C节点已经选择接受了A节点的提议，它是很诚实的，就直接告诉E节点他的选择，E节点知道C节点既然选择了A的提案，那自己也选A的提案。于是，E发起Accept请求，使用X作为提议值，至此，整个分布式系统达成了一致，大家都选择了X。

两个阶段分别是准备（prepare）和提交（commit）。准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。

简单来说，提案者发出提案后，收到一些反馈，有两种结果，一种结果是自己的提案被大多数节点接受了，另外一种是没被接受，没被接受就过会再试试。

提案者收到来自大多数的接受反馈，也不能认为这就是最终确认。因为这些接收者并不知道自己刚反馈的提案就是全局的绝对大多数。

所以，引入新的一轮再确认阶段是必须的，提案者在判断这个提案可能被大多数接受的情况下，发起一轮新的确认提案。这就进入了提交阶段。

提交阶段的提案发送出去，其他阶段进行提案值比较，返回最大的，所以提案者收到返回消息不带新的提案，说明锁定成功，如果有新的提案内容，进行提案值最大比较，然后替换更大的值。如果没有收到足够多的回复，则需要再次发出请求。

一旦多数接受了共同的提案值，则形成决议，称为最终确认的提案。

Raft算法是Paxos算法的一种简化实现。

包括三种角色：leader，candidate和follower。

其有两个基本过程：

Raft一致性算法是通过选出一个leader来简化日志副本的管理，例如，，日志项（log entry）只允许从leader流向follower。

下面是动画演示Raft，清晰理解Raft共识如何达成。

>

1、是什么

2、etcd架构及工作原理

(1) 数据流程

一个用户的请求发送过来，会经过>

分布式系统中，同一份数据通常会有多个副本，这样即使少数副本发生故障，系统仍可正常运行。这就需要一定的技术手段来保证多个副本之间的一致性。

Raft 就是一种用于保证多副本一致性的协议。

由于 Storage 服务需要支持集群分布式架构，所以基于 Raft 协议实现了 Multi Group Raft，即每个分片的所有副本共同组成一个 Raft group，其中一个副本是 leader，其他副本是 follower，从而实现强一致性和高可用性。Raft 的部分实现如下。

由于 Raft 日志不允许空洞，Nebula Graph 使用 Multi Group Raft 缓解此问题，分片数量较多时，可以有效提高 Nebula Graph 的性能。但是分片数量太多会增加开销，例如 Raft group 内部存储的状态信息、WAL 文件，或者负载过低时的批量 *** 作。

实现 Multi Group Raft 有 2 个关键点：

Nebula Graph 中，每个分片都是串行写日志，为了提高吞吐，写日志时需要做批量 *** 作，但是由于 Nebula Graph 利用 WAL 实现一些特殊功能，需要对批量 *** 作进行分组，这是 Nebula Graph 的特色。

例如无锁 CAS *** 作需要之前的 WAL 全部提交后才能执行，如果一个批量写入的 WAL 里包含了 CAS 类型的 WAL，就需要拆分成粒度更小的几个组，还要保证这几组 WAL 串行提交。

eader 切换对于负载均衡至关重要，当把某个分片从一台机器迁移到另一台机器时，首先会检查分片是不是 leader，如果是的话，需要先切换 leader，数据迁移完毕之后，通常还要重新均衡 leader 分布。

对于 leader 来说，提交 leader 切换命令时，就会放弃自己的 leader 身份，当 follower 收到 leader 切换命令时，就会发起选举。

为了避免脑裂，当一个 Raft group 的成员发生变化时，需要有一个中间状态，该状态下新旧 group 的多数派需要有重叠的部分，这样就防止了新的 group 或旧的 group 单方面做出决定。为了更加简化，Diego Ongaro 在自己的博士论文中提出每次只增减一个 peer 的方式，以保证新旧 group 的多数派总是有重叠。Nebula Graph 也采用了这个方式，只不过增加成员和移除成员的实现有所区别。具体实现方式请参见 Raft Part class 里 addPeer/removePeer 的实现。

以上就是关于Raft和它的三个子问题全部的内容，包括:Raft和它的三个子问题、kubernetes控制平面组件：etcd、阿里云的自研InfluxDB集群方案剖析等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！