https://raft.github.io/raft.pdf raft论文
http://thesecretlivesofdata.com/raft/ raft算法动画演示
etcd是CoreOS团队于2013年6月发起的开源项目,它的目标是构建一个高可用的分布式键值(key-value)数据库。etcd内部采用raft协议作为一致性算法,etcd基于Go语言实现。
etcd作为服务发现系统,有以下的特点:
分布式共识是分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。
分布式共识的引用(Application of Consensus)
raft是一个共识算法(consensus algorithm),所谓共识,就是多个节点对某个事情达成一致的看法,即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币(比特币、区块链)就需要共识算法,而在分布式系统中,共识算法更多用于提高系统的容错性,比如分布式存储中的复制集(replication),在带着问题学习分布式系统之中心化复制集一文中介绍了中心化复制集的相关知识。raft协议就是一种leader-based的共识算法,与之相应的是leaderless的共识算法。
共识算法就是保证一个集群的多台机器协同工作,在遇到请求时,数据能够保持一致。即使遇到机器宕机,整个系统仍然能够对外保持服务的可用性。
Raft将共识问题分解三个子问题:
所以,Raft算法核心流程可以归纳为:
leader election, log replication,safety,membership changes
raft会先选举出leader,leader完全负责replicated log的管理。leader负责接受所有客户端更新请求,然后复制到follower节点,并在“安全”的时候执行这些请求。如果leader故障,followes会重新选举出新的leader。
leader:
系统中最多只有一个leader,选举-投票选出leader
收到majority的造成票(含自己的一票)则切换到leader状态
follower:所有节点启动时都是follower状态
candidate:follower一段时间内没有收到来自leader的心跳,从follower切换到candidate
哪个节点做leader是大家投票选举出来的,每个leader工作一段时间,然后选出新的leader继续负责。这根民主社会的选举很像,每一届新的履职期称之为一届任期,在raft协议中,也是这样的,对应的术语叫term。
term(任期)以选举(election)开始,然后就是一段或长或短的稳定工作期(normal Operation)。从上图可以看到,任期是递增的,这就充当了逻辑时钟的作用;另外,term 3展示了一种情况,就是说没有选举出leader就结束了,然后会发起新的选举,后面会解释这种split vote的情况。
如果follower在election timeout内没有收到来自leader的心跳,(也许此时还没有选出leader,大家都在等;也许leader挂了;也许只是leader与该follower之间网络故障),则会主动发起选举。步骤如下:
在这个过程中,根据来自其他节点的消息,可能出现三种结果
第一种情况,赢得了选举之后,新的leader会立刻给所有节点发消息,广而告之,避免其余节点触发新的选举。在这里,先回到投票者的视角,投票者如何决定是否给一个选举请求投票呢,有以下约束:
总共有四个节点,Node C、Node D同时成为了candidate,进入了term 4,但Node A投了NodeD一票,NodeB投了Node C一票,这就出现了平票 split vote的情况。这个时候大家都在等啊等,直到超时后重新发起选举。如果出现平票的情况,那么就延长了系统不可用的时间(没有leader是不能处理客户端写请求的),因此raft引入了randomized election timeouts来尽量避免平票情况。同时,leader-based 共识算法中,节点的数目都是奇数个,尽量保证majority的出现。
简单来说:相同的初识状态 + 相同的输入 = 相同的结束状态。引文中有一个很重要的词deterministic
,就是说不同节点要以相同且确定性的函数来处理输入,而不要引入一下不确定的值,比如本地时间等。如何保证所有节点 get the same inputs in the same order
,使用replicated log是一个很不错的注意,log具有持久化、保序的特点,是大多数分布式系统的基石。
因此,可以这么说,在raft中,leader将客户端请求(command)封装到一个个log entry,将这些log entries复制(replicate)到所有follower节点,然后大家按相同顺序应用(apply)log entry中的command,则状态肯定是一致的。
当系统(leader)收到一个来自客户端的写请求,到返回给客户端,整个过程从leader的视角来看会经历以下步骤:
https://www.instructables.com/Understanding-how-ECDSA-protects-your-data/
ECDSA 代表“椭圆曲线数字签名算法”,它用于创建数据(例如文件)的数字签名,以便您在不影响其安全性的情况下验证其真实性。把它想象成一个真正的签名,你可以识别某人的签名,但你不能在别人不知道的情况下伪造它。然而,ECDSA 签名和真实签名之间的区别在于根本不可能伪造 ECDSA 签名。