分布式强一致性数据库的灵魂 - Raft 算法

内容来源:2017 年 11 月 18 日,PingCAP首席架构师唐刘在“数据技术嘉年华——分会场五:云架构、数据架构”进行《分布式强一致性数据库的灵魂 - Raft 算法的理论和实践》演讲分享。IT 大咖说(微信id:itdakashuo)作为独家视频合作方,经主办方和讲者审阅授权发布。

阅读字数:3258 | 10分钟阅读

摘要

Raft 分布式一致性算法在 2013 年发布,以容易理解、实现方式明确的特点,迅速在业界流行起来。本次分享将介绍 TiDB 如何使用 Raft 算法构建分布式可扩展的后端存储系统,以及 TiDB 在可靠性、可用性、性能等方面对 Raft 做的工程优化。

嘉宾演讲视频及PPT回顾:http://t.cn/RmTm6GF

Why Ralf

假设我们有某一个业务要实现数据存储方面的功能,最简单方法就是实现一个节点,所有的数据读写都是通过这一个节点。但是这样会存在各种各样的问题,比如数据量增大后无法承受压力,单节点如何向多节点分布,数据的一致性怎么保证,最严重的就是数据节点挂掉,数据全部丢失了。

Replication

为了解决节点损坏的问题,业界通用的方案是采用Replication,在Master写数据的时候挂多个Slave,写完后保证将log同步到Slave,这样的流程下来才能认为写入是成功的。

通常情况下为了保证性能,我们都会使用异步复制(Async Replication),不过会产生一些问题。当Master挂掉了之后很有可能有些数据并没有同步到Slave,这时候如果把这个Slave提升到新的Master就会面临数据丢失的问题。

强同步(Sync Replication)解决了异步复制(Async Replication)可能潜在的问题。Master写入数据后必须保证Slave接收到log写入才算成功,当然这样会损耗一些性能,不过最严重在于Master挂掉后,Slave提升为Master,单节点的问题就又出现了。

为了保证系统中N台节点挂掉后,仍然能够对外提供服务,至少需要2N+1台机器,也就是传统的Quorum,这样最少就需要三台机器,但是数量的增大也会带来更多的问题。

首先Master挂掉后要需要判断该提升哪个Slave为新的Master。另外在多态集群下还容易遇到一个问题,就是在网络情况下以前的Master出现网络隔离,还在继续对外提供服务,而这时新的集群和Master已经形成了,新的数据被写入到新的Master,可是读取的却是旧的数据,这就是在分布式一致性领域所面临的线性一致性问题。

Consensus Algorithm

一致性算法(Consensus Alogrithm)就是为了解决分布式集群所面临的诸多问题而准备的。它保证了系统在多个状态上的Agreement,另外在集群的大部分节点挂掉后能够保证数据一致性。

Raft

Replicated State Machine

大多数的一致性算法其实都是采用了Replicated State Machine的模型。对于这个模型你可以认为数据是被放在状态机上,用户操作集群时 首先需要写入log,然后通过一致性算法将log复制到其他机器,一旦确定其他机器都接收到log后就会认为该log被提交了,最后其他节点会依次将log存放到状态机。

State

Raft有着三个状态,第一个状态就是Leader,即使Raft Group存在多个节点,Leader也只会存在一个,也只有Leader能负责所有数据的读写,这样就不会出现线性一致性的问题。

当一个集群选出了Leader后其他集群的节点都会变成Follow,这个Follow只负责一件事就是接收Leader的Replication logs。当一个Follow没有接收到数据或者发现集群中没有Leader的时候,就会进入Candidate状态,这个状态表示可以开始选举了。

Term

Raft是不依赖系统的时间,它是将时间分成一个个Term,每个Term可以是任意长度,每次Term开始的时候都是由一次新的选举产生的,然后在这个Term内选出一个Leader,该Leader会一直服务到所在Leader结束。

结合Raft Term就可以进行Raft的选举。首先当系统启动后所有的节点都会进入Follow状态,Follow没有接收到任何请求的话,过一段时间就会进入Candidate状态,然后询问其他节点是否投票,如果其他节点反馈已经有新的Leader,这个Candidate就会变成Follow,而当Candidate接收到大多数的投票后就会变成Leader,之后会立即将一个log发送给其他节点开始续租Leader的时间租约。

Log Replication

一个新的Leader被选出来之后就会开始工作了,它会不停的去接收客户端发送过来的请求,这些请求都会通过log落地,而这些log一定要是单调递增,以保证数据的一致性。

之后log会被复制到其他的节点,绝大多数节点都接收到这个log后, Leader就认为该log是committed的。

Membership Change

对于分布式集群来说添加节点其实是分成困难的操作,最常见的做法是先更改配置中心,然后将新的配置同步到旧的节点。不过这样在同步配置的时候,就需要停止外部服务。而Raft采用了一种动态的成员节点变更,它会将新的节点到当作Raft log通过Leader传递给其他节点,这样其他节点就知道了这个新的节点的信息。不过这个过程中有可能会在某一阶段出现2个Leader的情况,为了避免这种情况就要每次只变更一个节点,而不进行多节点变更。

Raft也提供了一种多节点变更的算法,它是一种两阶段提交,Leader在第一阶段会同时将新旧集群的配置同时当成一个Raft log发送给其他旧集群节点,当这些节点接收到数据后就会和新的集群节点进入join状态,所有的操作都要进过新旧集群的大多数节点同意才会执行,然后在新的join状态内重新提交新的配置信息,在配置被committed后新的节点会上线,旧的节点会下线。

Optimization

Pre-Vote

在Follow处于网络抖动无法接受到Leader的消息的时候,它就会变成Candidate并且Term加一,但是其他集群其实还是在正常工作的,这样整个集群的就混乱了。

Pre-Vote机制会在Follow没有接收到Leader的消息并且开始投票之前进入Pre-Candidate状态,在想其他节点发送投票请求,并获得同意后才会进入Candidate状态。

Pipeline

正常的Raft流程中,客户端事先给Leader写入数据,Leader处理后会追加到log中,追加成功后Replication到其他节点中,­当Leader发现log被整个集群大多数节点接收后就会进行Apply。

这样的一个过程其实是非常低效的,所以就需要引入Pipeline,它可以将多个请求进行并发处理,有效提高效率。

Batch

通常情况下接收到的客户端请求都是依次过来的,而当有一批请求过来的时候,就可以通过Batch将这些请求打包成一个Raft log发送出去。

Multi-Raft

当目前的Raft Group无法支撑所有的数据的时候,就需要引入Multi-Raft处理数据,第一种做法是将数据切分成多个Raft Group分担到不同的机器上。

为了应对更复杂的情况就需要使用动态分裂的方法,假设最开始的只有3台机器以及一个Region,这个Region就布置在一台机器上,所有的数据都写入这台机器,当数据量达到某个预值后Region就产生分裂,得到的新的Region就可以移植到新的机器上。

今天的分享就到这里,喜欢请点赞~谢谢大家!有问题可以在评论区讨论。

原文发布于微信公众号 - IT大咖说(itdakashuo)

原文发表时间:2018-04-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6708
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2625
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3095
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5346
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏java 成神之路

使用 NIO 实现 echo 服务器

4537
来自专栏Golang语言社区

【Golang语言社区】GO1.9 map并发安全测试

var m sync.Map //全局 func maintest() { // 第一个 YongHuomap := make(map[st...

4698
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2000
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4818
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2662

扫码关注云+社区