分布式强一致性数据库的灵魂 - 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 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

大型服务端开发的反模式技巧

1. 用线程池执行异步任务 ? 为了减少阻塞时间,加快响应速度,把无需返回结果的操作变成异步任务,用线程池来执行,这是提高性能的一种手段。 你可能要惊讶了,这么...

3345
来自专栏数据和云

DBLINK分布式事务失败又遭遇RAC热点块争用

编辑手记:在DBLINK中由于远端数据库无法正常执行分布式事务,又遭遇RAC热块争用,两者共同作用导致数据库严重故障。接下来我们从AWR报告分析入手,一步步分析...

2775
来自专栏lulianqi

为什么需要多线程

对于这个问题可能很多朋友会说是为了高性能,个人觉得这是误解,多线程不等于高性能,从cpu(单核)的角度上看单线程才能带来最高性能。

572
来自专栏Pythonista

python多线程与线程

考虑一个场景:浏览器,网易云音乐以及notepad++ 三个软件只能顺序执行是怎样一种场景呢?另外,假如有两个程序A和B,程序A在执行到一半的过程中,需要读取大...

1052
来自专栏芋道源码1024

【追光者系列】HikariCP 连接池配多大合适(第一弹)?

首先声明一下观点:How big should HikariCP be? Not how big but rather how small!连接池的大小不是设置...

780
来自专栏前端杂货铺

node服务的监控预警系统架构

需求背景 目前node端的服务逐渐成熟,在不少公司内部也开始承担业务处理或者视图渲染工作。不同于个人开发的简单服务器,企业级的node服务要求更为苛刻: 高稳定...

2907
来自专栏架构师之路

单点系统架构的可用性与性能优化

一、需求缘起 明明架构要求高可用,为何系统中还会存在单点? 回答:单点master的设计,会大大简化系统设计,何况有时候避免不了单点 在哪些场景中会存在单点?先...

3328
来自专栏码神联盟

缓存 | redis和memecache的异同以及应用场景

缓存就是数据交换的缓冲区Cache。当某一硬件要读取数据时,会首先从缓存中查找需要的数据,如果找到了则直接执行,找不到的话则从内存中找。由于缓存的运行速度比内存...

3399
来自专栏大宽宽的碎碎念

你对Redis的使用靠谱吗?Redis的性能高,吗?Redis可以保证原子性,吗?用Redis可以实现事务,吗?用Redis可以当队列,吗?Redis适合用来做什么?

37710
来自专栏码神联盟

JAVA架构 | Redis分布式缓存原理分析

1引言 Redis是Remote Dictionary Server(Redis) 的缩写,或许光听名字你就能猜出它大概是做什么的。不错,它是一个由Salvat...

3755

扫码关注云+社区