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

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

分布式强一致性数据库的灵魂: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就可以移植到新的机器上。 

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

相关推荐

推荐文章

  • 让数据库不再成为业务发展瓶颈——分布式数据库架构设计

  • 阿里数据仓库实践分享

  • TiDB 原理与实战|架构师实践日

近期活动

  • 2018全球技术周正式开放报名 | 20+专题论坛,为技术创新者全面赋能!

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

分布式强一致性数据库的灵魂:Raft 算法 点击 【阅读原文】 回顾嘉宾演讲视频及PPT

原文 

http://mp.weixin.qq.com/s/i6ULr-aW7MOxQotCQpqBCQ

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 分布式强一致性数据库的灵魂:Raft 算法

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址