目录

分布式一致性详解

什么是一致性

在分布式系统中,计算、存储分布在各个节点上,节点可能分布在各个区域甚至是国家。

一致性就是数据保持一致,在分布式系统中,可以理解为多个节点中数据的值是一致的。

CAP theorem

https://gitee.com/lienhui68/picStore/raw/master/null/20-20200927102650250.png

站内引用: {%post_link 工作/410_分布式/分布式一致性/CAP原理和BASE思想 CAP %}

分区容忍性

举个简单的例子,一个服务共有5个节点分别部署在中国和美国,其中中国2个节点,美国3个节点。现在中美海底电缆断了,这两个分区无法互相访问,但是可以独立提供服务给外部。

此时保证一致性可以将某一个分区关闭服务,也可以保证可用性但此时数据可能会不一致,用户本来访问中国节点,出现分区之后只能访问美国节点,此时数据有可能不一致。

一致性模型

弱一致性

最终一致性

典型应用场景

  • DNS(Domain Name System)

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927103133231.png

  • Gossip(Cassandra的通信协议)

强一致性

  • 同步

  • Paxos

  • Raft

  • ZAB

强一致性算法

首先,要明确问题

数据要保证是安全的容错的,就不能存在单点上。

分布式系统对fault tolorence的一般解决方案是state machine replication。

state machine 可以简单里理解为一个函数或者方程,本身有初始状态,比如0,有input或者log将这个值增加5,这个值最终状态就是5。分布式系统希望通过log的形式往节点上写操作日志,分布式系统的设计是把这一些log复制到其他各个节点上,保证这些log不存在单点上。类似mysql的undo/redo log。

其实本篇要讨论的准确的说,应该是state machine replication的共识(consensus)算法。

paxos其实是一个共识算法。系统的最终一致性,不仅需要达成共识,还会取决于client的行为。

主从同步

主从同步复制

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927104539063.png

  1. master接受写请求
  2. master复制日志到slave
  3. master等待,直到所有从库返回

问题:

一个节点失败,master阻塞,导致整个集群不可用,保证了一致性,可用性却大大降低。

多数派

基本想法:

多数派!

每次写都保证写入大于 N/2 个节点,每次读保证从大于 N/2 个节点中读。

问题:

在并发环境下,无法保证系统正确性,顺序非常重要

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927105102253.png

Paxos

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法,使其获得2013年图灵奖。

Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开,最初的描述使用希腊的一个小岛Paxos作为比喻,描述了Paxos小岛中通过决议的流程,并以此命名这个算法,但是这个描述理解起来比较有挑战性。后来在2001年,Lamport觉得同行不能理解他的幽默感,于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

为描述Paxos算法,Lamport虚拟了一个叫做Paxos的希腊城邦,这个岛按照议会民主制的政治模式制定法律,但是没有人愿意将自己的全部时间和精力放在这种事。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。

自Paxos问世以来就持续垄断了分布式一致性算法,Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题,如Chubby、Megastore以及Spanner等。开源的ZooKeeper,以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。

然而,Paxos的最大特点就是难,不仅难以理解,更难以实现。

分类:

  • Basic Paxos
  • Multi Paxos
  • Fast Paxos

Basic Paxos

角色介绍

  • Client 客户端 产生议题者(群众)

    系统外部角色,请求发起者,像民众。

  • Proposer 提案者

    接受Client请求,向集群提出提议(propose)。并在冲突发生时,起到冲突调节的作用。像议员,替民众提出议案。

    acceptor只是起到投票的作用,返回通过或者不通过,由proposer决定是否符合多数派,要不要进行到下一个阶段

    谁改变了数据谁就是proposer,proposer可以理解成业务机器,acceptor是数据集群中的节点,代表分布式存储的独立存储节点

    多数派用在两个场景,第一次是决定proposer,第二次是将日志写入learner后决定是否commit

  • Acceptor(Voter) 决策者

    提议投票和接受者,只有在形成法定人数(Quorum,一般即为majority 多数派)时,提议才会最终被接受。像国会。

  • Learner 最终决策学习者(群众),和Client类似,不参与一致性的解决,只负责记录。

    提议接受者,backup备份,对集群一致性没什么影响。像记录员。

在多副本状态机中,每个副本同时具有Proposer、Acceptor、Learner三种角色。

client 客户端

proposer 业务处理节点

acceptor 数据节点,参与投票,是达成共识最重要的数据节点

learner 也是数据备份节点,不参与投票,类似slave,提供读服务提高并发

各角色均是节点,每个节点也可能同时扮演多个角色

提案通过,proposer会将日志写入acceptor数据节点,acceptor再将日志写入learner数据备份节点,注意此时数据内容还没有被commit,只有当acceptor确认多数learner已经写入日志才会commit

基本流程

步骤、阶段(phases):

  1. Phase 1a: Prepare

    proposer提出一个提案,编号为N,此N大于这个proposer之前提出的提案编号。请求acceptors的quorum接受。

  2. Phase 1b: Promise

    如果N大于此acceptor之前接受的任何提案编号则接受,否则拒绝。

  3. Phase 2a: Accept

    如果达到了多数派,proposer会发出accept请求,此请求包含提案编号N,以及提案内容。

  4. Phase 2b: Accepted

    如果此acceptor在此期间没有收到任何编号大于N的提案,则接受此提案内容,否则忽略。

两个阶段分别对应两次rpc调用,第一次是提案,第二次是提案内容

看来来理解

  • 正常流程

    https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927111018849.png

跟现实中区别是,acceptor只关系提案是否冲突而不关心提案的内容。

  • 部分节点失败,但达到了Quorum

    https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927112303777.png

  • Proposer失败

    https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927113151879.png

    比如redis里的哨兵leader死了一个需要重新换一个

Basic潜在问题,活锁(liveness)或dueling

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927113449326.png

站内引用:{%post_link 工作/200_编程语言/java/并发编程/活锁 活锁 %}

Multi Paxos

Basic Paxos的问题:

  • 难实现 角色很多
  • 效率低 2轮RPC
  • 活锁

Multi Paxos

新概念 Leader:唯一的proposer,所有请求都需经过此Leader,有点像主从架构,中心节点,zk里的master节点

第一轮RPC干的事就是决定使用哪个proposer的提案,现在不需要了(竞选总统阶段除外),而且避免了活锁

基本流程

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927131015913.png

只有这一个proposer也就是leader,不会有人跟他抢着去提案

Accept!(N, I, Vm) N任总统,提案编号I, 提案内容Vm

竞选完总统后接下来的请求就不用再竞选了,原来的两轮rpc现在只需要一轮rpc就可以完成了,关键点在于只有唯一一个proposer。

现在更像现实中的分布式系统了,主从节点,下面是一个Leader和两个Slavor

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200927132207343.png

Raft

Raft是一个实现分布式一致性的协议

Paxos很难理解也很难实现,Raft应运而生。

raft可以简单理解成简化版本的Multi Paxos,也是为了解决多副本状态机复制的问题。它把状态机复制日志这个问题划分成了3个子问题,只要解决这3个子问题就能达成共识。

划分成三个子问题

  • Leader Election 选主
  • Log Replication 日志复制 log同步到其他节点上,两个阶段 写入日志 commit
  • Safety 怎么保证所有的操作在集群中一直是一致的,leader失败了是怎样的,发生分区了是怎样的。

重定义角色

  • Leader
  • Follower
  • Candidate 临时的橘色,只有在Leader宕机了,Follower要竞选Leader时才会起作用,这时某个Follower想要竞选,可以临时充当Candidate角色,期待成为下一个Leader

原理动画解释

Raft动画演示

split vote 选举时,两个follower的timeout同时到期,会再举行一轮选举,这两个节点采用随机的timeout

场景测试

raft场景测试

注意:一致性并不一定代表完全正确性

三个可能结果:成功,失败,unknown

Raft 5 nodes example:

Client写请求,Leader向followers同步日志,此时集群中有3个节点失败,2个节点存活,结果是?

unkown,开始是两个节点的log处于未提交状态,当3个节点复活后,log会继续提交。

Client写请求,Leader向followers同步日志,此时集群中有2个节点失败,3个节点存活,结果是?

unkown,开始是两个节点的log处于未提交状态,3个节点提交,另两个节点复活后悔将未提交的抛弃,使用其他3个节点已同步的数据复制。

所以需要client决定如何处理。

ZAB

基本与raft相同,是zk的共识算法

在一些名词的叫法上有些区别:如ZAB将某一个leader的周期称为epoch,而raft则称之为term。

实现上也有些许不同:如raft保证日志连续性,心跳方向为leader至follower。ZAB则相反。

项目实践

在性能测试上etcd已经超过了ZK,最主要的应该是一致性算法的优势,zk基于从paxos改进而来的zab,而etcd基于raft,k8s现在都用etcd管理各种状态

Zookeeper集群搭建和命令行操作

Etcd集群搭建和restful api

参考

Paxos、Raft分布式一致性算法应用场景

Paxos算法详解

一文搞懂Raft算法

一致性算法