TiKV笔记-Raft复制状态机--未完

[toc]

理解Raft复制状态机才能更好的理解TiKV引擎,后续分成三篇文章由浅入深来逐步讲解Raft相关的内容:

  • Raft复制状态机

  • TiKV中的Multi Raft

  • TiKV中关于Raft的优化

本文重点介绍Raft的入门基础,也就是Raft的复制状态机。

1. Raft背景以及基础概念

1.1 Raft提出背景

分布式存储系统通常通过维护多个副本来进行容错,提高系统的可用性。要实现此目标,就必须要解决分布式存储系统的最核心问题:维护多个副本的一致性。

首先需要解释一下什么是一致性(consensus),它是构建具有容错性(fault-tolerant)的分布式系统的基础。 在一个具有一致性的性质的集群里面,同一时刻所有的结点对存储在其中的某个值都有相同的结果,即对其共享的存储保持一致。集群具有自动恢复的性质,当少数结点失效的时候不影响集群的正常工作,当大多数集群中的结点失效的时候,集群则会停止服务(不会返回一个错误的结果)。一致性协议就是用来干这事的,用来保证即使在部分(确切地说是小部分)副本宕机的情况下,系统仍然能正常对外提供服务。

1.2 TiKV为什么选择Raft?

  • Raft 提供了线性一致性的保证,适合数据库等一致性要求高的系统。

  • Raft过半节点失败不可用,延迟稳定,适合事务处理;对比全部节点失败才不可用,

  • 工程实现成熟,实现简单。

  • 选举算法、成员变更算法实现细节完备。

1.3 Raft基础概念

1.3.1 Raft复制状态机

一致性协议通常基于复制状态机,即所有结点都从同一个状态出发,都经过同样的一些指令,最后到达同一个状态。复制状态机用于解决分布式系统中的各种容错问题,例如具有单个Leader的大规模系统,GFS、HDFS等等通常使用单独的复制状态机来进行Leader的选举和存储Leader崩溃后重新选举需要的配置信息。Chubby、Zookeeper等都是复制状态机。复制状态机要能容忍很多错误场景。复制状态机的典型实现是基于复制日志,如下图所示:

raft-001

复制状态机包含了三个组件:

状态机: 当我们说一致性的时候,实际就是在说要保证这个状态机的一致性。状态机会从日志里面取出所有的命令,然后顺序执行一遍,得到的结果就是我们对外提供的保证了一致性的数据。

Log: 保存了所有修改指令的日志。

一致性模块: 一致性模块算法就是用来保证写入的日志的一致性,这也是Raft算法核心内容。

状态机可以理解为一个确定的应用程序,所谓确定是指只要是相同的输入,那么任何状态机都会计算出相同的输出。至于如何实现日志完全一致的复制,则是Raft一致性模块(Consensus Module)需要做的事。

每个节点上存储了一个包含一系列指令的日志,复制状态机按序执行这些指令。每一个日志在相同的位置存放相同的指令,所以每一个状态机都执行了相同序列的指令。

1.3.2 Raft节点状态

Raft的节点被称为peer,节点的状态是Raft算法的关键属性,在任何时候,Raft节点可能处于以下三种状态:

  • Leader:Leader负责处理客户端的请求,同时还需要协调日志的复制。在任意时刻,最多允许存在1个Leader,其他节点都是Follower。注意,集群在选举期间可能短暂处于存在0个Leader的场景。

  • Follower:Follower是被动的,它们不主动提出请求,只是响应Leader和Candidate的请求。注意,节点之间的通信是通过RPC进行的。

  • Candidate:Candidate是节点从Follower转变为Leader的过渡状态。因为Follower是一个完全被动的状态,所以当需要重新选举时,Follower需要将自己提升为Candidate,然后发起选举。

下图展示了这些状态以及它们之间的转化:

raft-002

从状态转换图可以看到,所有的节点都是从Follower开始,如果Follower经过一段时间后收不到来自Leader的心跳,那么Follower就认为需要Leader已经崩溃了,需要进行新一轮的选举,因此 Follower的状态变更为Candidate。Candidate有可能被选举为Leader,也有可能回退为 Follower。如果Leader发现自己已经过时了,它会主动变更为Follower。Leader如何发现自己过时了?下文会引入Term继续分析。

1.3.3 Term

Raft的一个关键属性是任期(Term),在分布式系统中,由于节点的物理时间戳都不统一,因此需要一个逻辑时间戳来表明事件发生的先后顺序,Term正是起到了逻辑时间戳的作用。Raft的运行过程被划分为一系列任意长度的Terms,一次Leader选举会开启一个新的Term,如下图所示:

raft-003

Terms有连续单调递增的编号,每个Term开始于选举,这一阶段每个Candidate都试图成为Leader。如果一个Candidate选举成功,它就在该Term剩余周期内履行leader职责。一次Term 也可能选不出Leader,这是因为可能多个Candidate都获得了相同数量的选票,此时下一次会进行下一次选举。

每个节点都会维护自己当前的Term(Current Term),并且持久化存储 Current Term。当Leader宕机后再恢复,Leader仍然会认为自己是Leader,除非发现自己已经过时了。节点利用Current Term判断过时的信息。节点的Term在节点之间通信时改变:如果某个节点的当前Term小于其它节点,那么这个节点必须更新它的Term,与集群其他节点保持一致;如果一个Candidate或者Leader发现自己的Term过期,它就必须要放下身段变成Follower;如果某个节点收到一个过时的请求(拥有过时的Term),它会拒绝该请求。

目前我们需要知道的是Term在Raft中是一个非常关键的属性,Term始终保持单调递增,而Raft认为一个节点的Term越大,那么它所拥有的日志就越准确。

前面对Raft算法进行了简要的介绍,这里开始对它进行深入分析。Raft实现一致性的机制是这样的:日志是由Leader到Follower的单向传递。也就是说Leader相当于一个总控节点,由它负责接受Client的请求,并且把日志发送各个Follower,进行复制。也是只有Leader能决定何时提交一个日志。通过Leader机制,Raft将一致性难题分解为三个相对独立的子问题:

  • Leader选举:一开始每个节点都是Follower,那么需要决定由谁来做Leader,这里延伸出Leader选举的问题,而且当Leader宕机的时候也需要重新进行选举。

  • 日志复制:当Leader选举出来之后,需要把日志复制到每个Follower。这里复制需要保证所有日志都有序且正确的复制到Follower上。也就是说Follower上的日志不管是顺序还是内容都要和Leader上的一样

  • 安全性:一但Leader把一项日志复制到绝大多数的Follower时,需要执行这个日志。这里的安全性是指所有的服务器都要在这同一个位置执行同一个Log,通俗的说,就是集群中所有节点都需要按照相同的顺序执行相同的日志

6赞

:+1::+1::+1:

意犹未尽,托腮等更新

坐等更新。。。

月底更新,年底OKR

请问大佬,更新完了吗