RAFT共识算法

https://raft.github.io/raft.pdf raft论文

http://thesecretlivesofdata.com/raft/ raft算法动画演示

1.分布式系统

etcd简介

etcd是CoreOS团队于2013年6月发起的开源项目，它的目标是构建一个高可用的分布式键值(key-value)数据库。etcd内部采用raft协议作为一致性算法，etcd基于Go语言实现。

etcd作为服务发现系统，有以下的特点：

• 简单：安装配置简单，而且提供了HTTP API进行交互，使用也很简单
• 安全：支持SSL证书验证
• 快速：根据官方提供的benchmark数据，单实例支持每秒2k+读操作
• 可靠：采用raft算法，实现分布式系统数据的可用性和一致性

分布式系统的挑战

• 时序性Timing运行在不同网络下的机器中的进程如何判断一些事件发生的顺序
• 并发性Concurreny运行在不同网络下的机器中的进程如何共享资源而互不干扰。比如访问共同的数据库。
• 健壮性Roubustness 应对网络的不稳定性以及硬件的不稳定性。
• 一致性Consistency如何保障无论访问哪个服务节点，都能获得相同的结果。

分布式共识

分布式共识是分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。

分布式共识的引用（Application of Consensus）

• 逻辑时间的共识，来决定事件发生的顺序
• 互斥性的共识，用于决定谁正拥有访问的资源
• 协调者的共识，谁是当下的leader

2.raft基本原理

raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication），在带着问题学习分布式系统之中心化复制集一文中介绍了中心化复制集的相关知识。raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。

共识算法就是保证一个集群的多台机器协同工作，在遇到请求时，数据能够保持一致。即使遇到机器宕机，整个系统仍然能够对外保持服务的可用性。

Raft将共识问题分解三个子问题：

• Leader election 领导选举：有且仅有一个leader节点，如果leader宕机，通过选举机制选出新的leader；
• Log replication 日志复制：leader从客户端接收数据更新/删除请求，然后日志复制到follower节点，从而保证集群数据的一致性；
• Safety 安全性：通过安全性原则来处理一些特殊case，保证Raft算法的完备性。

所以，Raft算法核心流程可以归纳为：

• 首先选出leader，leader节点负责接收外部的数据更新/删除请求；
• 然后日志复制到其他follower节点，同时通过安全性的准则来保证整个日志复制的一致性；
• 如果遇到leader故障，followers会重新发起选举出新的leader。

3.重要过程

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

Term

哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。这根民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫***term***。

term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。从上图可以看到，任期是递增的，这就充当了逻辑时钟的作用；另外，term 3展示了一种情况，就是说没有选举出leader就结束了，然后会发起新的选举，后面会解释这种split vote的情况。

如果follower在election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举。步骤如下：

• 增加节点本地的 current term ，切换到candidate状态
• 投自己一票
• 并行给其他节点发送 RequestVote RPCs
• 等待其他节点的回复

在这个过程中，根据来自其他节点的消息，可能出现三种结果

1. 收到majority的投票（含自己的一票），则赢得选举，成为leader
2. 被告知别人已当选，那么自行切换到follower
3. 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举

第一种情况，赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。在这里，先回到投票者的视角，投票者如何决定是否给一个选举请求投票呢，有以下约束：

• 在任一任期内，单个节点最多只能投一票
• 候选人知道的信息不能比自己的少（这一部分，后面介绍log replication和safety的时候会详细介绍）
• first-come-first-served 先来先得

总共有四个节点，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的视角来看会经历以下步骤：

• leader append log entry
• leader issue AppendEntries RPC in parallel
• leader wait for majority response
• leader apply entry to state machine
• leader reply to client
• leader notify follower apply log

4.ECDSA算法

https://www.instructables.com/Understanding-how-ECDSA-protects-your-data/

ECDSA 代表“椭圆曲线数字签名算法”，它用于创建数据（例如文件）的数字签名，以便您在不影响其安全性的情况下验证其真实性。把它想象成一个真正的签名，你可以识别某人的签名，但你不能在别人不知道的情况下伪造它。然而，ECDSA 签名和真实签名之间的区别在于根本不可能伪造 ECDSA 签名。