云原生分布式存储基石:etcd深入解析(txt+pdf+epub+mobi电子书下载)


发布时间:2020-05-25 21:19:59

点击下载

作者:华为云容器服务团队 等

出版社:机械工业出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

云原生分布式存储基石:etcd深入解析

云原生分布式存储基石:etcd深入解析试读:

版权信息书名:云原生分布式存储基石:etcd深入解析作者:华为云容器服务团队 等排版:HMM出版社:机械工业出版社出版时间:2018-11-01ISBN:9787111611929本书由北京华章图文信息有限公司授权北京当当科文电子商务有限公司制作与发行。— · 版权所有 侵权必究 · —前言为什么要写这本书

近年来,容器和云原生生态蓬勃发展,我们正身处于一波云原生的浪潮中。随着我们习惯于在云端产生和收集的数据,云端积累了海量的数据并继续以惊人的速度增长。如何实现数据分布式、一致性存储,确保云原生环境的可扩展性和高可用性,是各组织亟须解决的现实问题。

云计算时代,etcd必将成为云原生和分布式系统的基石!而奠定etcd基石地位的三个关键因素是Raft协议、Go语言和生态。

etcd从一开始就摒弃了以复杂和难以理解著称的Paxos,而是另辟蹊径地通过Raft化繁为简,实现了一套健壮的分布式一致性协议的SDK,这套SDK被很多其他分布式数据库/系统采用,甚至包括etcd兄弟项目rkt的竞争对手Docker。

至于被誉为云时代C语言的Go语言,具备天然的高并发能力、易安装和可读性好等优点,成就了etcd的高性能和项目的易维护性,极大地激发了来自全世界的开源工程师参与etcd的热情。云原生领域用Go语言编写的重量级项目不胜枚举,例如Docker、Kubernetes和Istio等。

etcd相对于Zookeeper是一个年轻且更加轻量的项目,它拥有更加健康和有活力的社区。截至这本书出版前夕,etcd在Github上的star数是20000+,fork数是4000+,拥有超过400名活跃的代码贡献者。不能忽视的一点是,etcd已经被Kubernetes和Cloud Foundry等顶级云原生项目采用,并借势经过了Google、华为云、Red Hat、IBM、阿里等IT巨头大规模生产环境的考验。随着etcd进入CNCF社区孵化,成为由CNCF治理的顶级项目,厂商中立的运作模式将进一步繁荣etcd的开源生态。

顺势而为,再加上合理的架构设计,恰如其分的实现,完全让人有理由相信etcd的成功。

在我最开始接触Kubernetes的时候,就和etcd打过交道了。etcd在华为PaaS平台作为关键组件应用在分布式数据协同与更新观察等架构中。犹记得那时etcd刚发布,我们希望它提升华为PaaS平台的扩展性、性能和稳定性。因此,我们团队还专门成立etcd特别攻关小组,吃透了etcd的内部运作机制和核心技术。我很荣幸成为这个小组的成员。从那时起,我便对etcd着了迷,一口气翻看了etcd的源码,同时也向etcd社区提交了若干个patch。

对于我们团队来说,我们很荣幸见证了etcd在技术和社区的持续进步并成长为Kubernetes项目的一部分。etcd v3的正式发布延续了这个势头,我们期待将来有更多的功能和特性被引入华为云容器平台的产品中。我们也很高兴过去能够与etcd团队和技术社区一起工作,并将持续与etcd技术社区协作,将这项技术推到一个更高的层面。

至于为什么要在工作之余抽空写这本书,我们在容器和Kubernetes技术布道的过程中发现,国内从事该领域的工程师普遍对etcd了解不多,出了问题鲜有定位手段,而etcd官网又没有中文资料,因特网上也缺少深入解析etcd原理的文章。本着回馈社区和普及云原生技术的原则,我们华为云容器服务团队决定编写这本书,做第一个“吃螃蟹”的人。

毕竟“源码面前,了无秘密”。读者对象

这里我们可以根据软件需求划分出本书的受众:

·分布式系统工作者

·Raft算法研究者

·etcd各个程度的学习者

·Kubernetes用户与开发者如何阅读本书

本书分为三部分,其中第二部分以接近实战的实例来讲解etcd的使用,相较于其他两部分更独立。如果你是一名分布式系统的初学者,请一定从第1章的基础理论知识开始学习。

第一部分为基础篇,包括第1章,我们将简单地介绍分布式系统的基本理论,并且详解Raft算法的工作原理,帮助读者了解一些掌握etcd的基础背景知识。

第二部分为实战篇,包括第2~7章,我们将着重讲解etcd的常见功能和使用场景,包括etcd的架构分析、命令行使用、API调用、运维部署等。

第三部分为高级篇,包括第8~11章,我们将直接打开etcd的源码,为喜欢刨根问底的读者深度剖析etcd的实现原理。勘误和支持

由于作者的水平有限,编写的时间也很仓促,书中不妥之处在所难免,恳请读者批评指正。如果你发现了书中的错误或者有更多的宝贵意见,欢迎发送邮件至我的邮箱m1093782566@163.com,我很期待能够获得你们的真挚反馈。致谢

我首先要感谢etcd的工程师团队,他们编写并开源了这么一款足以成为云原生基石的分布式存储系统——etcd。

感谢华为云容器服务团队的高级架构师、Kubernetes社区核心维护者Kevin老师,他为这本书的出版提供了良好的技术氛围和宝贵的实战经验支持。

感谢CMU在读硕士研究生梁明强同学,在写作过程中为我提供了犀利而宝贵的意见和文字。

感谢机械工业出版社华章公司的编辑杨绣国老师,感谢你的魄力和远见,在这一年多的时间中始终支持我的写作,你的鼓励和帮助引导我能顺利完成全部书稿。

我要感谢我的爸爸、妈妈、外公、外婆,感谢你们将我培养成人,并时时刻刻为我灌输着信心和力量!

我要感谢我的爱人,你的陪伴和鼓励使得这本书得以顺利完成。

谨以此书,献给我最亲爱的家人,以及众多热爱云原生与分布式技术的朋友们。杜军 中国,华为杭州研究所,2018年9月第一部分基础篇

本部分简单介绍分布式系统的基本理论,详细讲解Raft算法的工作原理,帮助读者了解etcd的基础知识,主要包括以下章节:

·第1章 分布式系统与一致性协议第1章分布式系统与一致性协议

现如今,摩尔定律的影响已经严重衰减甚至近于失效,但我们却实实在在地看到了计算能力的大幅度提升。在围棋人机大战里,人工智能AlphaGo打败李世石、柯洁的事实仍历历在目。计算能力的提升在很多时候都是源于系统(大数据、人工智能、云计算、区块链等)采用了分布式架构。《分布式系统概念与设计》一书中对分布式系统概念的定义如下:

分布式系统是一个硬件或软件组件分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统。

简单来说,分布式系统就是一组计算机节点和软件共同对外提供服务的系统。但对于用户来说,操作分布式系统就好像是在请求一个服务器。因为在分布式系统中,各个节点之间的协作是通过网络进行的,所以分布式系统中的节点在空间分布上几乎没有任何限制,可以分布于不同的机柜、机房,甚至是不同的国家和地区。

分布式系统的设计目标一般包括如下几个方面。

·可用性:可用性是分布式系统的核心需求,其用于衡量一个分布式系统持续对外提供服务的能力。

·可扩展性:增加机器后不会改变或极少改变系统行为,并且能获得近似线性的性能提升。

·容错性:系统发生错误时,具有对错误进行规避以及从错误中恢复的能力。

·性能:对外服务的响应延时和吞吐率要能满足用户的需求。

虽然分布式架构可以组建一个强大的集群,但实际工作中遇到的挑战要比传统单体架构大得多,具体表现如下所示。

1)节点之间的网络通信是不可靠的,存在网络延时和丢包等情况。

2)存在节点处理错误的情况,节点自身随时也有宕机的可能。

3)同步调用使系统变得不具备可扩展性。1.1 CAP原理

提到分布式系统,就不得不提CAP原理。CAP原理在计算机科学领域广为人知,如果说系统架构师将CAP原理视作分布式系统的设计准则一点也不为过。

下面让我们先来回顾一下CAP的完整定义。

·C:Consistency(一致性)。这里的一致性特指强一致,通俗地说,就是所有节点上的数据时刻保持同步。一致性严谨的表述是原子读写,即所有读写都应该看起来是“原子”的,或串行的。所有的读写请求都好像是经全局排序过的一样,写后面的读一定能读到前面所写的内容。

·A:Availability(可用性)。任何非故障节点都应该在有限的时间内给出请求的响应,不论请求是否成功。

·P:Tolerance to the partition of network(分区容忍性)。当发生网络分区时(即节点之间无法通信),在丢失任意多消息的情况下,系统仍然能够正常工作。

相信大家都非常清楚CAP原理的指导意义:在任何分布式系统中,可用性、一致性和分区容忍性这三个方面都是相互矛盾的,三者不可兼得,最多只能取其二。本章不会对CAP原理进行严格的证明,[1]感兴趣的读者可以自行查阅Gilbert和Lynch的论文,下面将给出直观的说明。

1)AP满足但C不满足:如果既要求系统高可用又要求分区容错,那么就要放弃一致性了。因为一旦发生网络分区(P),节点之间将无法通信,为了满足高可用(A),每个节点只能用本地数据提供服务,这样就会导致数据的不一致(!C)。一些信奉BASE(Basic Availability,Soft state,Eventually Consistency)原则的NoSQL数据库(例如,Cassandra、CouchDB等)往往会放宽对一致性的要求(满足最终一致性即可),以此来换取基本的可用性。

2)CP满足但A不满足:如果要求数据在各个服务器上是强一致的(C),然而网络分区(P)会导致同步时间无限延长,那么如此一来可用性就得不到保障了(!A)。坚持事务ACID(原子性、一致性、隔离性和持久性)的传统数据库以及对结果一致性非常敏感的应用(例如,金融业务)通常会做出这样的选择。

3)CA满足但P不满足:指的是如果不存在网络分区,那么强一致性和可用性是可以同时满足的。

CAP原理最初的提出者Eric Brewer在CAP猜想提出12年之际[2](2012年)对该原理重新进行了阐述,明确了CAP原理只适用于原子读写的场景,而不支持数据库事务之类的场景。同时指出,只有极少数网络分区在非常罕见的场景下,三者才有可能做到有机的结合。无独有偶,Lynch也重写了论文“Perspectives on the CAP Theorem”[3],引入了活性(liveness)和安全属性(safety),并认为CAP是活性与安全性之间权衡的一个特例。CAP中的C(一致性)属于活性,A(可用性)属于安全性。

正如热力学第二定律揭示了任何尝试发明永动机的努力都是徒劳的一样,CAP原理明确指出了完美满足CAP三种属性的分布式系统是不存在的。了解CAP原理的目的在于,其能够帮助我们更好地理解实际分布式协议实现过程中的取舍,比如在后面的章节中将会提到的lease机制、quorum机制等。1.2 一致性

在阐述一致性模型和一致性协议之前,我们先来了解下什么是一致性。分布式存储系统通常会通过维护多个副本来进行容错,以提高系统的可用性。这就引出了分布式存储系统的核心问题——如何保证多个副本的一致性?“一致性”这个中文术语在计算机的不同领域具有不同的含义,不同的含义所对应的英文术语也是不一样的,例如,Coherence、Consensus和Consistency等。就这三个术语而言,简单来说,它们之间存在的区别具体如下:

·Coherence这个单词只在Cache Coherence场景下出现过,其所关注的是多核共享内存的CPU架构下,各个核的Cache上的数据应如何保持一致。

·Consensus是共识,它强调的是多个提议者就某件事情达成共识,其所关注的是达成共识的过程,例如Paxos协议、Raft选举等。Consensus属于replication protocol的范畴。

·Consistency表达的含义相对复杂一些,广义上说,它描述了系统本身的不变量的维护程度对上层业务客户端的影响,以及该系统的并发状态会向客户端暴露什么样的异常行为。CAP、ACID中的C都有这层意思。

本书将要重点讨论的分布式系统中的一致性问题,属于上文中提到的Consensus和Consistency范畴。分布式系统的一致性是一个具备容错能力的分布式系统需要解决的基本问题。通俗地讲,一致性就是不同的副本服务器认可同一份数据。一旦这些服务器对某份数据达成了一致,那么该决定便是最终的决定,且未来也无法推翻。

一致性与结果的正确性没有关系,而是系统对外呈现的状态是否一致(统一)。例如,所有节点都达成一个错误的共识也是一致性的一种表现。注意 一致性协议就是用来解决一致性问题的,它能使得一组机器像一个整体一样工作,即使其中的一些机器发生了错误也能正常工作。正因为如此,一致性协议在大规模分布式系统中扮演着关键角色。

同时,一致性协议也是分布式计算领域的一个重要的研究课题,对它的研究可以追溯到20世纪80年代,一致性协议衍生出了很多算法。衡量一致性算法的标准具体如下。

·可终止性:非失败进程在有限的时间内能够做出决定,等价于liveness。

·一致性:所有的进程必须对最终的决定达成一致,等价于safety。

·合法性:算法做出的决定值必须在其他进程(客户端)的期望值范围之内。即客户端请求回答“是”或“否”时,不能返回“不确定”。

一致性协议是在复制状态机(Replicated State Machines,RSM)的背景下提出来的,通常也应用于具有复制状态机语义的场景。在了解复制状态机之前,让我们先简单了解下一致性模型。1.2.1 一致性模型

一致性问题一直以来都是分布式系统的痛点,因为很多场景都要求一致性,但并不是所有的系统都要求是强一致的。强一致需要极高的成本,我们需要根据系统的容忍度适当放宽一致性的要求。

在很多人看来,银行间的转账应该是强一致的,但是如果仔细分析一下就会发现,小王向小张转账1000元,小王的账户扣除了1000元,此时小张并不一定会同步收到1000元,可能会存在一个不一致的时间窗口。也就是小王的账户中扣除了1000元,小张还没收到1000元。另外一个常见的例子,12306网站上买票的功能也未必是强一致的,如果你在12306上发现某车次的票还剩余10张,发起请求订了一张票,系统返回的信息可能是“正在排队,剩余10张票,现在有15人在购买”,而不是购买成功或失败的结果,很可能你在收到上述信息之后,不得不去查询未完成订单,以进一步确认订票情况。如果有人退了一张票,通常这张票也不会立即返回到票池中。很明显这里也存在不一致的时间窗口。

本节将要重点讨论分布式系统的一致性模型。我们知道,分布式系统中网络分区在任何时刻、任何地点都有可能正在或即将发生。交换机、网卡、主机硬件、操作系统、磁盘、虚拟化层和语言运行时间(更不用说程序语义本身)都会延误、丢弃、复制或重新排序我们的消息。在一个不确定的世界里,我们肯定都是希望自己的软件能够按照确定的规则运行。

那么,很显然我们需要直观的正确性。做正确的事情!那么究竟什么是正确的呢?我们又该如何描述它呢?正确性

我们有很多种方式来表达一个算法的抽象行为,比如前文中介绍的状态机模型——“一个系统是由状态以及改变这些状态的操作组成的”,随着系统的运行,它会通过一些操作历史从一个状态转移到另一个状态。

如果我们的状态是一个变量,状态上的操作可能是写入和读取该变量,那么,如下这个简单的Ruby程序将会多次写入和读取一个变量,并将其打印到屏幕上,以说明读取的内容。示例代码如下:*****

x = "a"; puts x; puts xx = "b"; puts xx = "c"x = "d"; puts x*****

在上述示例代码里,我们已经有了这个程序正确性的直观模型:它应该打印“aabd”。为什么?因为每个陈述都是按顺序发生的。首先写入一个值a,然后是读取两次值a,再写入值b,然后读取值b等。上述寄存器系统读写输出具体如图1-1所示。图1-1 寄存器系统读写输出示例

我们将这种一个变量携带一个值的系统称为寄存器。一旦我们将一个变量(寄存器)设置为某个值,该值就会立刻生效,直到我们再次更改该值,即读取变量应该返回最近写入的值。

从开始编写程序的第一天起,这种模式就已经深深地印刻在了我们的头脑之中,然而这并非变量唯一的工作方式。事实上,一个变量可以返回任何一个读取的值:a、d或the moon。如果发生这种情况,则认为系统是不正确的,因为这些操作与我们的变量应该如何工作的模型不一致。这也暗示了系统正确性的定义:在给定了与操作和状态相关的一些规则的情况下,系统中的操作历史应该总是遵循这些规则。我们称这些规则为一致性模型。

更正式的说法是,一致性模型是所有允许的操作历史的集合。如果运行一个程序,它经历了“允许操作集”中的一系列操作,那么任意一次执行都是一致的。如果程序偶尔发生故障并且出现了不是一致性模型中的历史操作,那么我们就说历史记录是不一致的。如果每个可能的执行都落入允许的集合中,则系统满足该一致性模型。我们希望真正的系统能够满足“直观正确”的一致性模型,以便编写可预测的程序。1.2.2 一致性模型分述

在讨论了一致性模型的正确性之后,下面就来分类概述各种类型的一致性模型。对于一致性,可以分别从客户端和服务端两个不同的视角来理解。从客户端来看,一致性主要是指多并发访问时如何获取更新过的数据的问题。从服务端来看,则是更新如何复制分布到整个系统,以保证数据最终的一致性。因此,可以从两个角度来查看一致性模型:以数据为中心的一致性模型和以用户为中心的一致性模型。

最后,一致性是基于并发读写才有的问题,因此在理解一致性的问题时,一定要注意结合考虑并发读写的场景。1.以数据为中心的一致性模型

实现以下这几种一致性模型的难度会依次递减,对一致性强度的要求也依次递减。(1)严格一致性(Strong Consistency)

严格一致性也称强一致性,原子一致性或者是可线性化(Linearizability),是要求最高的一致性模型。严格一致性的要求具体如下。

1)任何一次读都能读到某个数据的最近一次写的数据。

2)系统中的所有进程,看到的操作顺序,都与全局时钟下的顺序一致。

从示意图1-2可以看到,在时间轴上,一旦数据x被重新写入了,其他进程读到的要求就必须是最新的值。图1-2 严格一致性示意图

对于严格一致性的存储器,要求写操作在任一时刻对所有的进程都是可见的,同时还要维护一个绝对全局时间顺序。一旦存储器中的值发生改变,那么不管读写之间的事件间隔有多小,不管是哪个进程执行了读操作,也不管进程在何处,以后读出的都是新更改的值。同样,如果执行了读操作,那么不管后面的写操作有多迅速,该读操作仍应读出原来的值。

传统意义上,单处理机遵守严格一致性。但是在分布式计算机系统中为每个操作都分配一个准确的全局时间戳是不可能实现的。因此,严格一致性,只是存在于理论中的一致性模型。

幸运的是,通常的编程方式是语句执行的确切时间(实际上是存储器访问的时间)并不重要,而当事件(读或写)的顺序至关重要时,可以使用信号量等方法实现同步操作。接受这种意见意味着采用较弱的一致性模式来编程。

按照定义来看,强一致模型是可组合的,也就是说如果一个操作由两个满足强一致的子操作组成,那么父操作也是强一致的。强一致提供了一系列很好的特性,也非常易于理解,但问题在于它基本很难得到高效的实现。因此,研究人员放松了要求,从而得到了在单机多线程环境下实际上普遍存在的顺序一致性模型。(2)顺序一致性(Sequential Consistency)

顺序一致性,也称为可序列化,比严格一致性要求弱一点,但也是能够实现的最高级别的一致性模型。

因为全局时钟导致严格一致性很难实现,因此顺序一致性放弃了全局时钟的约束,改为分布式逻辑时钟实现。顺序一致性是指所有的进程都以相同的顺序看到所有的修改。读操作未必能够及时得到此前其他进程对同一数据的写更新,但是每个进程读到的该数据不同值的顺序却是一致的。

可见,顺序一致性在顺序要求上并没有那么严格,它只要求系统中的所有进程达成自己认为的一致就可以了,即“错的话一起错,对的话一起对”,且不违反程序的顺序即可,并不需要整个全局顺序保持一致。

如图1-3所示的是严格一致性和顺序一致性的对比。图1-3 严格一致性和顺序一致性对比图

在图1-3中,图1-3a满足顺序一致性,但是不满足强一致性。原因在于,从全局时钟的观点来看,P2进程对变量X的读操作在P1进程对变量X的写操作之后,然而读出来的却是旧的数据。但是这个图却是满足顺序一致性的,因为两个进程P1、P2的一致性并没有冲突。从这两个进程的角度来看,顺序应该是这样的:Write(y,2)→Read(x,0)→Write(x,4)→Read(y,2),每个进程内部的读写顺序都是合理的,但是显然这个顺序与全局时钟下看到的顺序并不一样。

图1-3b满足强一致性,因为每个读操作都读到了该变量最新写的结果,同时两个进程看到的操作顺序与全局时钟的顺序一样,都是Write(y,2)→Read(x,4)→Write(x,4)→Read(y,2)。

图1-3c不满足顺序一致性,当然也就不满足强一致性了。因为从进程P1的角度来看,它对变量Y的读操作返回了结果0。也就是说,P1进程的对变量Y的读操作在P2进程对变量Y的写操作之前,这意味着它认为的顺序是这样的:Write(x,4)→Read(y,0)→Write(y,2)→Read(x,0),显然这个顺序是不能满足的,因为最后一个对变量x的读操作读出来的也是旧的数据。因此这个顺序是有冲突的,不满足顺序一致性。

通常,满足顺序一致性的存储系统需要一个额外的逻辑时钟服务。(3)因果一致性(Causal Consistency)

这里提到的因果关系专指Lamport在“Time,Clocks,and the Ordering of Events in a Distributed System”论文中描述的happen-before关系及其传递闭包,简单地说,因果关系可以描述成如下情况。

·本地顺序:本进程中,事件执行的顺序即为本地因果顺序。

·异地顺序:如果读操作返回的是写操作的值,那么该写操作在顺序上一定在读操作之前。

·闭包传递:与时钟向量里面定义的一样,如果a→b且b→c,那么肯定也有a→c。

否则,操作之间的关系为并发(Concurrent)关系。对于具有潜在因果关系的写操作,所有进程看到的执行顺序应相同。并发写操作(没有因果关系)在不同主机上被看到的顺序可以不同。不严格地说,因果一致性弱于顺序一致性。如图1-4所示的是因果一致性与顺序一致性的对比。图1-4 因果一致性和顺序一致性的对比

在InfoQ分享的腾讯朋友圈的设计中,腾讯在设计数据一致性的时候,使用了因果一致性这个模型,用于保证对同一条朋友圈的回复的一致性,比如下面这样的情况。

A发了朋友圈,内容为梅里雪山的图片。

B针对A的内容回复了评论:“这是哪里?”

C针对B的评论进行了回复:“这是梅里雪山”。

那么,这条朋友圈的显示中,显然C针对B的评论,应该在B的评论之后,这是一个因果关系,而其他没有因果关系的数据,可以允许不一致。(4)可串行化一致性(Serializable Consistency)

如果说操作的历史等同于以某种单一原子顺序发生的历史,但对调用和完成时间没有说明,那么就可以获得称为可序列化的一致性模型。这个模型很有意思,一致性要么比你想象的强得多,要么弱得多。

可串行化一致性很弱,由于它没有按时间或顺序排列界限,因此这就好像消息可以任意发送到过去或未来。例如,在一个可序列化的系统中,有如下所示的这样一个程序:*****

x = 1x = x + 1puts x*****

在这里,我们假设每行代表一个操作,并且所有的操作都成功。因为这些操作可以以任何顺序进行,所以可能打印出nil、1或2。因此,一致性显得很弱。

但在另一方面,串行化的一致性又很强,因为它需要一个线性顺序。例如,下面的这个程序:*****

print x if x = 3x = 1 if x = nilx = 2 if x = 1x = 3 if x = 2*****

它可能不会严格地以我们编写的顺序发生,但它能够可靠地将x从nil→1→2,更改为3,最后打印出3。

因此,可序列化允许对操作重新进行任意排序,只要顺序看起来是原子的即可。2.以用户为中心的一致性模型

在实际业务需求中,很多时候并不会要求系统内所有的数据都保持一致,例如在线的日记本,业务只要求基于这个用户满足一致性即可,而不需要关心整体。这就是所谓的以用户为中心的一致性。

最终一致性(Eventual Consistency)

在读多写少的场景中,例如CDN,读写之比非常悬殊,如果网站的运营人员修改了一张图片,最终用户延迟了一段时间才看到这个更新实际上问题并不是很大。我们把这种一致性归结为最终一致性。最终一致性是指如果更新的间隔时间比较长,那么所有的副本都能够最终达到一致性。

最终一致性是弱一致性的一种特例,在弱一致性情况下,用户读到某一操作对系统特定数据的更新需要一段时间,我们将这段时间称为“不一致性窗口”。

在最终一致性的情况下,系统能够保证用户最终将读取到某操作对系统特定数据的更新(读取操作之前没有该数据的其他更新操作)。此种情况下,如果没有发生失败,那么“不一致性窗口”的大小将依赖于交互延迟、系统的负载,以及复制技术中副本的个数(可以理解为master/slave模式中slave的个数)。DNS系统在最终一致性方面可以说是最出名的系统,当更新一个域名的IP以后,根据配置策略以及缓存控制策略的不同,最终所有的客户都会看到最新的值。

最终一致性模型根据其提供的不同保证可以划分为更多的模型,比如上文提到的因果一致性(Causal Consistency)就是其中的一个分支。1.2.3 复制状态机

当同一份数据存在多个副本的时候,怎么管理它们就成了问题。在Map-Reduce的场景下,数据都是只读的,即一次写入永不更改,所以不存在一致性问题。复制状态机用于支持那些允许数据修改的场景,比如分布式系统中的元数据。典型的例子是一个目录下的那些文件,虽然文件本身可以做到一次写入永不修改,但是目录的内容总是随文件的不断写入而发生动态变化的。

复制状态机由图灵奖得主Leslie Lamport(Lamport就是LaTeX中的“La”,微软研究院科学家,荣获2013年图灵奖)在他那篇著名的“Time,Clocks,and the Ordering of Events in a Distributed System”(1978)论文中首次提出,而比较系统的阐述则是在Fred Schneider的论文“Implementing fault-tolerant services using the state machine approach”(1990)中。它的基本思想是一个分布式的复制状态机系统由多个复制单元组成,每个复制单元均是一个状态机,它的状态保存在一组状态变量中。状态机的状态能够并且只能通过外部命令来改变。

上文提到的“一组状态变量”通常是基于操作日志来实现的。每一个复制单元存储一个包含一系列指令的日志,并且严格按照顺序逐条执行日志上的指令。因为每个状态机都是确定的,所以每个外部命令都将产生相同的操作序列(日志)。又因为每一个日志都是按照相同的顺序包含相同的指令,所以每一个服务器都将执行相同的指令序列,并且最终到达相同的状态。

综上所述,在复制状态机模型下,一致性算法的主要工作就变成了如何保证操作日志的一致性。

复制状态机的运行过程如图1-5所示。图1-5 复制状态机

图1-5中,服务器上的一致性模块负责接收外部命令,然后追加到自己的操作日志中。它与其他服务器上的一致性模块进行通信以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制,那么每一个服务器的状态机都将按照操作日志的顺序来处理它们,然后将输出结果返回给客户端。

复制状态机之所以能够工作是基于下面这样的假设:如果一些状态机具有相同的初始状态,并且它们接收到的命令也相同,处理这些命令的顺序也相同,那么它们处理完这些命令后的状态也应该相同。因为所有的复制节点都具有相同的状态,它们都能独立地从自己的本地日志中读取信息作为输入命令,所以即使其中一些服务器发生故障,也不会影响整个集群的可用性。不论服务器集群包含多少个节点,从外部看起来都只像是单个高可用的状态机一样。

复制状态机在分布式系统中常被用于解决各种容错相关的问题,例如,GFS、HDFS、Chubby、ZooKeeper和etcd等分布式系统都是基于复制状态机模型实现的。

需要注意的是,指令在状态机上的执行顺序并不一定等同于指令的发出顺序或接收顺序。复制状态机只是保证所有的状态机都以相同的顺序执行这些命令。基于复制状态机模型实现的主-备系统中,如果主机发生了故障,那么理论上备机有权以任意顺序执行未提交到操作日志的指令。但实际实现中一般不会这么做。以ZooKeeper为例,它采用的是原子化的广播协议及增量式的状态更新。状态更新的消息由主机发给备机,一旦主机发生故障,那么备机必须依然执行主机的“遗嘱”。下文将详细描述Raft协议的做法。1.2.4 拜占庭将军问题

拜占庭将军问题(The Byzantine Generals Problem或Byzantine Failure)是一个共识问题。Byzantine Failure这个概念最早是由Leslie Lamport于1980年发表的“Reaching agreement in the presence of faults”论文中提出的。

拜占庭位于如今土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国幅员辽阔,出于防御的原因,每个军队都相隔甚远,将军与将军之间只能靠信差来传递消息。发生战争时,拜占庭军队内所有将军必需达成共识,决定是否攻击敌人。但是军队内可能存在叛徒和敌军的间谍扰乱将军们的决定,因此在进行共识交流时,结果可能并不能真正代表大多数人的意见。这时,在已知有成员不可靠的情况下,其余忠诚的将军如何排除叛徒或间谍的影响来达成一致[4]的决定,就是著名的拜占庭将军问题。

拜占庭将军问题是对现实世界的模型化。由于硬件错误、网络拥塞、连接断开或遭到恶意攻击等原因,计算机和网络可能会出现不可预料的行为。拜占庭错误(Byzantine Failure)在计算机科学领域特指分布式系统中的某些恶意节点扰乱系统的正常运行,包括选择性不传递消息,选择性伪造消息等。很显然,拜占庭错误是一个overly pessimistic模型(最悲观、最强的错误模型),因为这种错误在实际环境里很罕见。那么为什么还要研究这个模型呢?因为如果某个一致性协议能够保证系统在出现N个拜占庭错误时,依旧可以做出一致性决定,那么这个协议也就能够处理系统出现N个其他任意类型的错误。

反之,进程失败错误(fail-stop Failure,如同宕机)则是一个overly optimistic模型(最乐观、最弱的错误模型)。这个模型假设当某个节点出错时,这个节点会停止运行,并且其他所有节点都知道这个节点发生了错误。提出这个错误模型的意义在于,如果某个一致性协议在系统出现N个进程失败错误时都无法保证做出一致性决定,那么这个协议也就无法处理系统出现N个其他任意类型的错误。

Fred Schneider在前面提到的那篇论文中指出了这样一个基本假设:一个RSM系统要容忍N个拜占庭错误,至少需要2N+1个复制节点。如果只是把错误的类型缩小到进程失败,则至少需要N+1个复制节点才能容错。

综上所述,对于一个通用的、具有复制状态机语义的分布式系统,如果要做到N个节点的容错,理论上最少需要2N+1个复制节点。这也是典型的一致性协议都要求半数以上(N/2+1)的服务器可用才能做出一致性决定的原因。例如,在一个5节点的服务器集群中要求至少其中3个可用;如果小于3个可用,则会无法保证返回一致的结果。

但是不是只要满足上文提到的2N+1个要求就能保证万无一失了呢?很不幸,答案是否定的。1.2.5 FLP不可能性

FLP不可能性(FLP Impossibility,F、L、P三个字母分别代表三个作者Fischer、Lynch和Patterson名字的首字母)是分布式领域中一个非常著名的定理(能够在计算机科学领域被称为“定理”,可见其举足轻重的地位),该定理给出了一个令人吃惊的结论:

No completely asynchronous consensus protocol can tolerate even a single unannounced process death.

在异步通信场景下,任何一致性协议都不能保证,即使只有一个进程失败,其他非失败进程也不能达成一致。这里的“unannounced process death”指的是一个进程发生了故障,但其他节点并不知道,继续认为这个进程还没有处理完成或发生消息延迟了,要强于上文提到的“fail-stop Failure”。感兴趣的读者可以翻阅论文“Impossibility [5]of Distributed Consensus with One Faulty Process”。下面用一个小例子来帮助大家直观地理解FLP定理。

甲、乙、丙三个人各自分开进行投票(投票结果是0或1)。他们彼此可以通过电话进行沟通,但有人会睡着。例如:甲投票0,乙投票1,这时候甲和乙打平,丙的选票就很关键。然而丙睡着了,在他醒来之前甲和乙都将无法达成最终的结果。即使重新投票,也有可能陷入无尽的循环之中。

FLP定理实际上说明了在允许节点失效的场景下,基于异步通信方式的分布式协议,无法确保在有限的时间内达成一致性。换句话说,结合CAP理论和上文提到的一致式算法正确性衡量标准,一个正确的一致性算法,能够在异步通信模型下(P)同时保证一致性(C)和可终止性(A)——这显然是做不到的!

请注意,这个结论的前提是异步通信。在分布式系统中,“异步通信”与“同步通信”的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序等。

可能会有读者提到TCP。在分布式系统的协议设计中,不能简单地认为基于TCP的所有通信都是可靠的。一方面,尽管TCP保证了两个TCP栈之间的可靠通信,但无法保证两个上层应用之间的可靠通信。另一方面,TCP只能保证同一个TCP连接内网络报文不乱序,而无法保证不同TCP连接之间的网络报文顺序。在分布式系统中,节点之间进行通信,可能先后会使用多个TCP连接,也有可能并发建立多个TCP连接。

根据FLP定理,实际的一致性协议(Paxos、Raft等)在理论上都是有缺陷的,最大的问题是理论上存在不可终止性!至于Paxos和Raft协议在工程的实现上都做了哪些调整(例如,Paxos和Raft都通过随机的方式显著降低了发生算法无法终止的概率),从而规避了理论上存在的哪些问题,下文将会有详细的解释。1.2.6 小结

最后,本节在此总结一下一致性协议的两大关键因素,具体如下。

1)让服务器集群作为一个整体对外服务。

2)即使一小部分服务器发生了故障,也能对外服务。

实际生产环境也对一致性协议提出了以下要求。

·安全性。在非拜占庭错误模型的条件下,永远不会返回一个错误的结果。即要具备处理网络延迟、网络分区(通信断开)、丢包、冗余和乱序等错误的能力。

·高可用。只要集群中的大部分机器都能运行,可以互相通信并且可以与客户端通信,那么这个集群就可用。例如,一个拥有5台服务器的集群可以容忍其中的2台出现故障。

·不依赖时序。时钟错误和极端情况下的消息延迟只有在最坏情况下才会引起可用性问题。

一小部分节点不会成为系统性能的瓶颈。通常情况下,一条外部命令要求能够快速地在大部分节点上完成并响应,一小部分性能较差的节点不会影响系统的整体性能。

除了错误模型,不同的系统条件也会影响一致性的达成,例如,同步/异步通信,一致性达成的规定时间等。由于FLP定理决定了在异步通信+响应时间无上限的情况下,不存在能够解决一个节点崩溃(节点异常但其他节点不知情,强于fail-stop错误)的一致性协议。因此解决拜占庭将军问题的算法(Paxos及其变种,Raft等)都会用到同步假设(或保证safety,或保证liveness)。1.3 Paxos协议

Leslie Lamport对类似拜占庭将军这样的问题进行了深入研究,并发表了几篇论文。总结起来就是回答如下的三个问题。

1)类似拜占庭将军这样的分布式一致性问题是否有解?

2)如果有解的话需要满足什么样的条件?

3)基于特定的前提条件,提出一种解法。

Leslie Lamport在论文“拜占庭将军问题”中已经给出了前两个问题的回答,而第三个问题在他的论文“The Part-Time Parliament”中提出了一种基于消息传递的一致性算法。有意思的是,Lamport在论文中使用了古希腊的一个城邦Paxos作为例子,描述了Paxos通过决议的流程,并以此命名算法,也就是后来人们耳熟能详的Paxos算法。

Paxos算法从提出到为大众所熟知,中间还有一段小插曲。1990年,Lamport向ACM Transactions on Computer Systems提交了他那篇关于Paxos算法的论文。主编回信建议他用数学而不是神话描述他的算法,否则他们不会考虑接受这篇论文。Lamport觉得那些人太迂腐,拒绝做任何修改,转而将论文贴在了自己的个人博客上。

起初Paxos算法由于难以理解并没有引起多少人的重视,直到2006年Google的三大论文初现“云”端,其中Chubby Lock服务使用了Paxos作为Chubby Cell的一致性算法,这件事使得Paxos算法的人气从此一路飙升,几乎垄断了一致性算法领域。在Raft算法诞生之前,Paxos几乎成了一致性协议的代名词。Chubby作者关于Paxos协议有一句经典的评价:“There is only one consensus protocol,and that’s Paxos-all other approaches are just broken versions of Paxos.”(所有的一致性协议都是Paxos协议的变种。)

由此可见,Paxos协议在一致性协议领域具有重要地位。

尽管Lamport本人觉得Paxos很简单,但事实上对于大多数人来说,Paxos还是太难理解了。引用NSDI社区上的一句话就是:“The dirty little secret of the NSDI community is that at most five people really,truly understand every part of Paxos.”(全世界真正理解Paxos算法的人只有5个!)

Paxos不仅难,而且难以实现,引用Chubby工程师的一段话就是:

There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system.In order to build a real-world system,an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions.The cumulative effort will be substantial and the final system will be based on an unproven protocol.

上面这段话的核心含义是Paxos算法与现实世界之间有条鸿沟,而且Paxos论文本身并未提供工程实现方法,算法实现者不得不对Paxos协议做一些拓展,因此最终的系统实现实际上是建立在一个Paxos的衍生算法上的,而这个衍生算法的正确性却未被证明!

正因为Paxos协议存在这些问题,而一致性协议对大规模分布式系统又非常重要,因此,斯坦福大学的Diego Ongaro和John Ousterhout决定设计一种比Paxos更容易理解的一致性算法。Raft就是这样的一个算法,从论文题目“In Search of an Understandable Consensus Algorithm”就可以看出Raft算法把可理解性作为算法设计的主要目标之一。1.4 Raft协议:为可理解性而生

上文中提到过,Raft算法的提出是为了改变Paxos算法垄断分布式一致性协议的局面。可以说,可理解性是系统工程师从Paxos算法切换到Raft算法的主要原因。Raft的作者在他的论文中也特别提到Raft算法在教学方面比Paxos算法的效果更好。

为了比较Paxos和Raft算法的可理解性能,Raft算法的作者特地在斯坦福大学和加州大学伯克利分校的课堂上,对总共43名学生进行了一次教学实验。他们分别为每个学生讲授Raft和Paxos算法,并针对每个算法准备了相应的随堂测验,通过计算每个学生的测验得分来衡量学生对哪种算法理解得更好。

测验总分为60,Raft算法测验的平均得分是25.7,Paxos算法的平均得分是20.8,Raft比Paxos平均高出4.9分。图1-6展示了43个学生在Paxos和Raft测验中的成绩,对角线之上的点表示在Raft算法测验中获得更高分数的学生。图1-6 Paxos与Raft测验对比

同时在测验之后采访参与学生,询问他们认为哪个算法更容易解释和实现。压倒性的结果表明Raft算法更加容易解释和实现。图1-7展示了这个采访结果。图1-7 Paxos与Raft算法实现难易程度调查

在图1-7中,左侧柱形图表示的是哪个算法在工程上更容易实现的统计结果,右边表示的是哪个算法更容易解释的统计结果。

Raft算法主要使用两种方法来提高可理解性。(1)问题分解

尽可能地将问题分解成为若干个可解决的、更容易理解的小问题——这是众所周知的简化问题的方法论。例如,Raft算法把问题分解成了领袖选举(leader election)、日志复制(log replication)、安全性(safety)和成员关系变化(membership changes)这几个子问题。

·领袖选举:在一个领袖节点发生故障之后必须重新给出一个新的领袖节点。

·日志复制:领袖节点从客户端接收操作请求,然后将操作日志复制到集群中的其他服务器上,并且强制要求其他服务器的日志必须和自己的保持一致。

·安全性:Raft关键的安全特性是下文提到的状态机安全原则(State Machine Safety)——如果一个服务器已经将给定索引位置的日志条目应用到状态机中,则所有其他服务器不会在该索引位置应用不同的条目。下文将会证明Raft是如何保证这条原则的。

·成员关系变化:配置发生变化的时候,集群能够继续工作。(2)减少状态空间

Raft算法通过减少需要考虑的状态数量来简化状态空间。这将使得整个系统更加一致并且能够尽可能地消除不确定性。需要特别说明的是,日志条目之间不允许出现空洞,并且还要限制日志出现不一致的可能性。尽管在大多数情况下,Raft都在试图消除不确定性以减少状态空间。但在一种场景下(选举),Raft会用随机方法来简化选举过程中的状态空间。

Raft算法与现有的一些Paxos协议的变种(主要是Oki和Liskov的[6]Viewsta-mped Replication)存在一些相似的地方,但是Raft还有几点重要的创新。

·强领导人。Raft使用一种比其他算法更强的领导形式。例如,日志条目只从领导人发向其他服务器。这样就简化了对日志复制的管理,提高了Raft的可理解性。

·领袖选举。Raft使用随机定时器来选举领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化,就使得冲突解决更加简单和快速。

·成员变化。Raft在调整集群成员关系时使用了新的一致性(joint consensus,联合一致性)方法。使用这种方法,使得集群配置在发生改变时,集群依旧能够正常工作。

下文将对Raft算法展开详细的讨论。1.4.1 Raft一致性算法

Raft算法是基于复制状态机模型推导的,所以在开始Raft算法的探秘之前,建议大家回顾一下1.2.3节有关复制状态机的内容。下文将从Raft算法的4个子问题:领袖选举、日志复制、安全性和成员关系变化出发,采取各个击破的策略,直击Raft算法的本质。不过,在此之前,先让我们简单了解下Raft算法的几个基本概念。

当Paxos协议的读者还在抱怨Lamport没有给出一个形式化的、可实现的工程方法时,Diego在论文中就已经明确告诉他的读者只要实现2个远端过程调用,就能构建一个基于Raft协议的分布式系统。

Raft集群中的节点通过远端过程调用(RPC)来进行通信,Raft算法的基本操作只需2种RPC即可完成。RequestVote RPC是在选举过程中通过旧的Leader触发的,AppendEntries RPC是领导人触发的,目的是向其他节点复制日志条目和发送心跳(heartbeat)。下文还会介绍Raft算法的第3种RPC,用于领导人向其他节点传输快照(snapshot)。如果节点没有及时收到RPC的响应,就会重试。而且,RPC可以并行地发出,以获得最好的性能。1.Raft算法的基本概念

一般情况下,分布式系统中存在如下两种节点关系模型。

·对称。所有节点都是平等的,不存在主节点。客户端可以与任意节点进行交互。

·非对称。基于选主模型,只有主节点拥有决策权。任意时刻有且仅有一个主节点,客户端只与主节点进行交互。

基于简化操作和效率等因素考虑,Raft算法采用的是非对称节点关系模型。

在一个由Raft协议组织的集群中,一共包含如下3类角色。

·Leader(领袖)

·Candidate(候选人)

·Follower(群众)

联系实际的民主社会,领袖由群众投票选举得出。刚开始时没有领袖,民主社会的所有参与者都是群众。首先开启一轮大选,大选期间所有的群众都能参与竞选,即所有群众都可以成为候选人。一旦某位候选人得到了半数以上群众的选票,就出任那一届的领袖,开始一个新的任期。领袖产生后,将由领袖昭告天下,结束选举。于是,除领袖之外的所有候选人又都回到了群众的身份并接受领袖的领导。

上文提到一个概念——“任期”,其在Raft算法中对应一个专门的术语——“Term”。

如图1-8所示,Raft算法将时间划分成为任意个不同长度的任期,任期是单调递增的,用连续的数字(1,2,3……)表示。在Raft的世界里,每一个任期的开始都是一次领导人的选举。正如上文所描述的那样,一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举,那么它就会在该任期的剩余时间内担任领导人。在某些情况下,选票会被瓜分,导致没有哪位候选人能够得到超过半数的选票,这样本次任期将以没有选出领导人而结束。那么,系统就会自动进入下一个任期,开始一次新的选举。Raft算法保证在给定的一个任期内最多只有一个领导人。某些Term会由于选举失败,存在没有领导人的情况。图1-8 Raft算法任期示意图

众所周知,分布式环境下的“时间同步”是一个大难题,但是有时为了识别“过期信息”,时间信息又是必不可少的。于是,任期在Raft中起着逻辑时钟的作用,同时也可用于在Raft节点中检测过期信息——比如过期的领导人。每个Raft节点各自都在本地维护一个当前任期值,触发这个数字变化(增加)主要有两个场景:开始选举和与其他节点交换信息。当节点之间进行通信时,会相互交换当前的任期号。如果一个节点(包括领导人)的当前任期号比其他节点的任期号小,则将自己本地的任期号自觉地更新为较大的任期号。如果一个候选人或者领导人意识到它的任期号过时了(比别人的小),那么它会立刻切换回群众状态;如果一个节点收到的请求所携带的任期号是过时的,那么该节点就会拒绝响应本次请求。

需要注意的是,由于分布式系统中节点之间无法做到在任意时刻完全同步,因此不同的Raft节点可能会在不同的时刻感知到任期的切换。甚至在出现网络分区或节点异常的情况下,某个节点可能会感知不到一次选举或者一个完整的任期。这也是Raft强制使用较新的Term更新旧的Term的原因。

好了,Raft协议的核心概念和术语就这么多——领袖、候选人、群众和任期,而且这些术语与现实民主制度也非常匹配,因此也很好理解。下面就开始讨论Raft算法的领导人选举流程。2.领导人选举

Raft通过选举一个权力至高无上的领导人,并采取赋予他管理复制日志重任的方式来维护节点间复制日志的一致性。领导人从客户端接收日志条目,再把日志条目复制到其他服务器上,并且在保证安全性的前提下,告诉其他服务器将日志条目应用到它们的状态机中。强领导人的存在大大简化了复制日志的管理。例如,领导人可以决定新的日志条目需要放在日志文件的什么位置,而不需要和其他服务器商议,并且数据都是单向地从领导人流向其他服务器。当然,在这种方式下,领导人自身的日志正确性显得尤为重要,下文的“4.安全性Q&A”一节会着重说明Raft使用怎样的策略来保证日志的正确性。

Raft集群三类角色的有限状态机图如图1-9所示,后面的具体选举过程可以结合图1-9来进行理解。图1-9 Raft集群三类角色切换示意图

观察图1-9可以很容易地看出,有一个“times out”(超时)条件,这是触发图1-9有限状态自动机发生状态迁移的一个重要条件。在Raft的选举中,有两个概念非常重要:心跳和选举定时器。每个Raft节点都有一个选举定时器,所有的Raft节点最开始以Follower角色运行时,都会启动这个选举定时器。不过,每个节点的选举定时器时长均不相等。

Leader在任期内必须定期向集群内的其他节点广播心跳包,昭告自己的存在。Follower每次收到心跳包后就会主动将自己的选举定时器清零重置(reset)。因此如果Follower选举定时器超时,则意味着在Raft规定的一个选举超时时间周期内,Leader的心跳包并没有发给

试读结束[说明:试读内容隐藏了图片]

下载完整电子书


相关推荐

最新文章


© 2020 txtepub下载