在Rust中实施Raft的领导人选举

2021-01-24 04:47:33

共识算法是一个始终引起我注意的主题:它复杂且困难,需要精确而安全的解决方案。换句话说:我们有几台机器组成一个集群,它们在相同数据的相同副本上运行,即使在某些服务器宕机的情况下也可以继续运行。此方法用于解决分布式系统中的许多问题。

为了稍微介绍一下我们目前的立场,我们必须谈论Paxos。在过去的十年或更长时间里,Paxos几乎是共识的同义词,因为它是大多数计算机科学课程中讲授的协议,共识的大多数实现都使用它。唯一的问题是Paxos确实很难理解,因此很难正确实施。因此,Diego Ongaro和John Ousterhout设计了Raft,其最重要的目标是使其易于理解。

鉴于Raft非常关注可理解性,因此将共识分解为三个相对独立的子问题(引用Raft论文):

日志复制:领导者必须接受来自客户端的日志条目,并在整个集群中复制它们,从而迫使其他日志同意自己的日志条目

安全性:如果任何服务器已将给定日志条目应用于其状态机,则其他服务器均不得对同一日志索引应用不同的命令。

在此博客文章中,我将仅讨论领袖选举。我将在以后的其他博客文章中介绍另外两个主题!

一个Raft群集由几台服务器组成,五台是典型的服务器,因此使系统出现两个故障。此群集中的服务器处于以下三种可能状态之一:

筏将时间划分为任意长度,并用连续的整数编号。这些条款中的每一项都以选举开始,在该选举中,一个或多个候选人试图成为集群的领导者。当一个候选人赢得选举,它充当了的余下任期的领导者。为了更好地说明此过程,我们可以说明这些过渡。

Raft使用心跳机制触发选举。当服务器加入集群时,它们以跟随者的身份开始,只要他们从当前领导者那里收到有效的心跳,它们就保持这种状态。领导者定期向所有追随者发送心跳,以通知他们存在并维持其权威。当跟随者在一段时间内未收到心跳信号(以Raft“选举超时”命名)时,它将继续进行新的选举。

如果服务器获得多数票,则它将扮演领导者的角色

这是对领导人选举过程的非常简单和简短的解释,有关更多细节,请随时阅读本文!读起来很愉快。

Rust是一种为性能,安全性和安全并发而设计的编程语言。它是强类型的,已编译的,没有垃圾收集器的,并且没有运行时(也就是非常小的运行时)。

到2020年底,我通过阅读一些博客文章对Rust产生了兴趣。有了这个触发条件,我决定阅读The Rust Programming Language一书,并开始编写非常小的项目。只有很小的项目并不能告诉您有关现实世界中的语言的太多信息。因此,我决定实施与我的日常工作更相关的东西:处理分布式系统。

注意:如果您不熟悉该语言,则可以快速查看Rust的Gentle简介。

我决定使用该语言的最简单和最基本的结构。这意味着没有大的运行时,可以完成大部分工作的库等。因此,我最终仅将线程用于并发,将TCP用于RPC。

我最初的方法是找出最重要的类型,然后在代码中复制它们。

//类型示例。枚举状态{FOLLOWER,LEADER,CANDIDATE,}枚举LogEntry {心跳{term:u64,peer_id:String},} struct Server {id:字符串,地址:SocketAddrV4,state:State,term:u64,log_entries:Vec< LogEntry> ,voted_for:选项<对等,next_timeout:选项<即时> ,config:ServerConfig,current_leader:选项<领导者> ,number_of_peers:usize,} //访问文件" types.rs"在仓库中查看所有类型定义。

定义好类型后,我便开始逐步实现状态转换。

为了重现此行为,我在Server内部实现了一个新方法,以确保所有服务器均以此状态启动。

impl Server {pub fn new(config:ServerConfig,number_of_peers:usize,address:SocketAddrV4,id:String,)->自我{服务器{id:id,状态:State :: FOLLOWER,term:0,log_entries:Vec :: new(),voted_for:None,next_timeout:None,config:config,current_leader:None,number_of_peers:number_of_peers,地址:地址 , } } }

现在,我们有一个以跟随者身份启动的服务器!我们去实现其余的状态转换。

如前所述,当Raft中的服务器在预定的时间内未收到来自领导者的心跳时,就会超时。每个服务器都有一个随机的超时设置,以确保服务器在不同的时间超时。

//最终的实现并不完全像这样,//但想法是相同的。 thread :: spawn(|| {循环{如果server .has_timed_out(){new_election(& server);}}});

因此,我们有一个运行无限循环的线程,始终检查服务器的超时。无论何时发生,都会触发新的选举。

// 1.将状态从关注者更改为候选服务器.state = State :: CANDIDATE; // 2.将当前项增加一台服务器.term = server .term + 1;服务器.refresh_timeout(); // // 3.为服务器本身投票.voted_for = Some(对等{id:server .id .to_string(),address:server .address,}); // 4.准备投票请求,并进行RPC请求let request_vote_rpc = Some(VoteRequest {term:new_term,候选人ID:id,})let rpc_response = rpc_client .request_vote(request_vote_rpc); // 5.如果服务器获得多数票,并且如果has_won_the_election(& server,rpc_response){// 6.将心跳发送给所有关注者,则将成为领导者let log_entry = LogEntry :: Heartbeat {term:server .term,peer_id:服务器.id .to_string(),}; rpc_client .broadcast_log_entry(log_entry); }

如果发生超时或服务器得不到多数票,它将再次开始选举,再次增加选任期。在Raft中,没有领导者可以有条件。

在选举过程中可能会发生另一种有趣的情况:选举集群中的另一台服务器,并开始发送心跳。发生这种情况时,我们的服务器会将状态从CANDIDATE更改为FOLLOWER,并将条款设置为当前领导者的条款。

//服务器接收心跳时的行为示例//如果接收到的心跳具有比自身更高的条件,它将成为跟随者。如果条款>服务器.term {信息! ("服务器{}成为关注者。新的领导者是:{}",server .id和peer_id);服务器.term =术语;服务器.state = State :: FOLLOWER;服务器.voted_for = None;服务器.current_leader =某些(领导{id:peer_id .to_string(),term:term,})}

这样,我们涵盖了Raft领导者选举算法中状态转换的所有步骤!

领导者选举的核心逻辑是在raft :: core包中实现的,其中放置了用于处理日志条目(心跳),选举和超时的函数。请访问完整的实现,以更详细地了解该代码。

RPC通过TCP连接完成。每个服务器以TPC侦听器启动,并创建与群集中所有其他服务器的客户端连接。

该实现未使用持久性存储,因此所有操作都在内存中完成。因此,通过使用Rust的Arc和Mutex组合,可以在许多功能之间共享Server实例。我花了一些时间来理解这些概念,但是一旦掌握了基础知识,事实证明非常简单!

有一个演示,运行并演示了在新集群中选拔领导者的过程。通过运行它,我们得到以下输出:

22:46:10 [INFO]在以下位置启动服务器:127.0.0.1:3300...22:46:10 [INFO]在以下位置启动服务器:127.0.0.1:3301...22:46:10 [INFO]启动服务器在:127.0.0.1:3302...22:46:11 [INFO]服务器server_1的超时为3秒。22:46:11 [INFO]服务器server_3的超时为6秒。22: 46:11 [INFO]服务器server_2的超时时间为5秒。22:46:14 [INFO]服务器server_1超时。22:46:14 [INFO]服务器server_1的期限为1,开始了选举过程0.22:46:14 [INFO]服务器服务器1已经赢得了选举!新术语是:122:46:14 [INFO]术语为0的服务器server_3,从服务器_1接收了术语122:46:14的心跳[INFO]服务器server_3成为跟随者。新的领导者是:server_122:46:14 [INFO]术语为0的服务器server_2,从服务器_1接收了术语为122:46:14的心跳[INFO]服务器server_2成为跟随者。新的领导者是:server_122:46:14 [INFO]术语为1的服务器server_3,从术语为122:46:14的server_1收到心跳[INFO]术语为1的服务器server_2,从术语为122:46:16的server_1接收到心跳[INFO]带有术语1的服务器server_3接收到带有术语122的server_1的心跳[INFO]带有术语1的服务器server_3从带有术语1的server_1接收到的心跳

用Rust编写代码非常愉快。语法非常好,它对emacs有很好的支持,Cargo非常简单易用,并且编译器确实可以帮助您发现错误。

不利的一面是学习曲线,至少对于习惯使用GC语言的我而言。 理解借阅检查器需要花费时间,并且在途中会出错-尽管它是语言的重要组成部分。 总而言之,在实施Raft领导人选举的两个星期中,我学到了很多东西,我强烈建议您也做类似的事情! 这很有趣,您最终会学到很多东西。