Elasticell-聊聊Raft的优化

服务器

浏览数:60

2020-5-31

之前两篇文章介绍了做Elasticell的缘由和Multi-Raft的实现细节:

这篇主要介绍Elasticell在Raft上做的一些优化工作。

 

一次简单的Raft就一个值达成一致的过程

  1. Leader收到一个请求

  2. Leader存储这个Raft Log,并且给Follower发送AppendEntries消息

  3. Follower收到并且存储这个Raft Log,给Leader回复AppendEntries消息

  4. Leader收到大多数的Follower的回复,给Follower发送AppendEntries消息,确认这个Log已经被Commit了

  5. Leader自己Apply这个Log

  6. Leader Apply完成后,回复客户端

  7. Follower收到Commit的AppendEntries消息后,也开始Apply这个Log

如果都顺序处理这些,性能就可想而知了,下面我们来看一下在Elasticell中针对Raft所做的一些优化工作。

 

Append Log并行化

2这个步骤,Leader可以AppendEntries消息和Raft Log的存储并行。为什么?

  1. 如果Leader没有Crash,那么和顺序的处理结果一致。

  2. 如果Leader Crash了,那么如果大于n/2+1的follower收到了这个消息并Append成功,那么这个Raft Log就一定会被Commit,新选举出来的Leader会响应客户端;否则这个Raft Log就不会被Commit,客户端就会超时/错误/或重试后的结果(看实现方式)。

 

异步Apply

一旦一个Log被Committed,那么什么时候被Apply都不会影响正确性,所以可以异步的Apply这个Log。

 

物理连接多路复用

当系统中的Raft-Group越来越多的时候,每个Raft-Group中的所有副本都会两两建链,从物理上看,最后会看到2台物理机器(可以是物理机,虚机,容器等等)之间会存在大量的TCP链接,造成链接爆炸。Elasticell的做法:

  1. 使用链路复用技术,让单个Store进程上所有的Raft-Group都复用一个物理链接

  2. 包装Raft消息,增加Header(Header中存在Raft-Group的元信息),这样在Store收到Raft消息的时候,就能够知道这些消息是属于哪一个Raft-Group的,从而驱动Raft。

 

Batching & Pipelining

很多同学会认为实现强一致存储会影响性能,其实并非如此,在合理的优化实现下,强一致存储对于系统的吞吐量并不会有多大的影响,这主要来自于一致性协议的两个重要的细节Batching和Pipelining,理念可以参见论文[1],事实上,在阿里近期反复提到的X-DB跨机房优化中也实现了类似的功能X-Paxos,因此下面看看Raft的Batching和Pipelining如何在Elasticell中达到类似的效果。

 

在Elasticell中Batching在各个阶段都有涉及,Batching可以提高系统的吞吐量(和Latency矛盾)。Elasticell中的单个Raft-Group使用一个Goroutine来处理Raft事件,比如Step,Request,Raft Ready,Tick,Apply Result等等。

  • Proposal阶段,收集在上一次和本次处理Raft事件之间的所有请求,并把相同类型的请求做合并,并做一个Proposal,减少Raft的网络请求

  • Raft Ready阶段, 收集在上一次和本次处理Raft事件之间的所有的Ready信息,Leader节点Batch写入Raft Log

  • Apply阶段,由于Apply是异步处理,可以把相同类型的操作合并Apply(例如把多个Redis的Set操作合并为一个MSet操作),减少CGO调用

Raft的Leader给Follower发送AppendEntries的时候,如果等待上一次的AppendEntries返回,再发下一个AppendEntries,那么必然性能很差。所以需要做Pipelining来加速,不等上一次的AppendEntries返回,持续的发送AppendEntries。

 

如果要保证性能和正确性,需要做到以下两点:

  1. Leader到某一个Follower之间的发送管道必须是有序的,保证Follower有序的处理AppendEntries。

  2. 能够处理丢失AppendEntries的状况,比如连续发送了Index是2,3,4的三个Append消息,其中3这个消息丢包了,Follower收到了2和4,那么Leader必须重新发送3,4两个Append消息(因为4这个消息会被Follower丢弃)。

对于第二点,Etcd的库已经做了处理,在Follower收到Append消息的时候,会检查是不是匹配已经接收到的最后一个Raft Log,如果不匹配,就返回Reject消息,那么按照Raft协议,Leader收到这个Reject消息,就会从3(4-1)重试。

 

Elasticell的实现方式:

  1. 保证用于发送Raft消息的链接在每两个节点直接只有一个

  2. 把当前节点待发送的Raft消息按照对端节点的ID做简单的hash,放到不同的线程中去,由这些线程负责发送(线程的数量就相当于Pipelining的管道数)

这样就能保证每个Follower收到的Raft消息是有序的,并且每个Raft都只有一个Goroutine来处理Raft事件,这些消息能够保证被顺序的处理。

Batching和Pipelining的trade off

Batching能够提高系统的吞吐量(会带来系统Latency增大),Pipelining能够降低系统的Latency(也能在一定程度上提高吞吐量),这个2个优化在决策的时候是有冲突的(在Pipelining中发送下一个请求的时候,需要等多少的Batch Size,也许多等一会就回收集更多的请求),目前Elasticell采用的方式是在不影响Pipelining的前提下,尽可能多的收集2次Pipelining之间的请求Batching处理策略,显然这并不是一个最优的解决方案。

还没有做的优化

以上是Elasticell目前已经做的一些优化,还有一些是未来需要做的:

  1. 不使用RocksDB存储Raft Log,由于Raft Log和RocksDB的WAL存在功能重复的地方,这样就多了一次文件IO

  2. Raft的heartbeat合并,当一个节点上的Raft-Group的很多的时候,heartbeat消息过多

  3. Batching Apply的时候,当前节点上所有正在Apply的Raft-Group一起做Batching而不是在一个Raft-Group上做Batching

  4. 更高效的Batching和Pipelining模式,参考论文[1]

了解更多

https://github.com/deepfabric/elasticell

参考

[1] Tuning Paxos for high-throughput with batching and pipelining

作者:fagongzi