乐趣区

关于美团:Replication上常见复制模型分布式系统挑战

分布式系统设计是一项十分复杂且具备挑战性的事件。其中,数据复制与一致性更是其中非常重要的一环。数据复制畛域概念庞杂、理论性强,如果对应的算法没有实践验证大概率会出错。如果在设计过程中,不理解对应实践所解决的问题以及不同实践之间的分割,势必无奈设计出一个正当的分布式系统。

本系列文章分高低两篇,以《数据密集型利用零碎设计(DDIA)》(下文简称《DDIA》)为主线,文中的外围实践解说与图片来自于此书。在此基础上,退出了日常工作中对这些概念的了解与个性化的思考,并将它们映射到 Kafka 中,跟大家分享一下如何将具体的实践利用于理论生产环境中。

1. 简介

1.1 简介——应用复制的目标

在分布式系统中,数据通常须要被扩散在多台机器上,次要为了达到以下目标:

  1. 扩展性,数据量因读写负载微小,一台机器无奈承载,数据扩散在多台机器上能够无效地进行负载平衡,达到灵便的横向扩大。
  2. 容错、高可用,在分布式系统中,单机故障是常态,在单机故障下依然心愿零碎可能失常工作,这时候就须要数据在多台机器上做冗余,在遇到单机故障时其余机器就能够及时接管。
  3. 对立的用户体验,如果零碎客户端散布在多个地区,通常思考在多个地区部署服务,以不便用户可能就近拜访到他们所须要的数据,取得对立的用户体验。

数据的多机散布的形式次要有两种,一种是将数据分片保留,每个机器保留数据的局部分片(Kafka 中称为 Partition,其余局部零碎称为 Shard),另一种则是齐全的冗余,其中每一份数据叫做一个正本(Kafka 中称为 Replica),通过数据复制技术实现。在分布式系统中,两种形式通常会独特应用,最初的数据分布往往是下图的样子,一台机器上会保留不同数据分片的若干个正本。本系列博文次要介绍的是数据如何做复制,分区则是另一个主题,不在本文的探讨领域。

复制的指标须要保障若干个正本上的数据是统一的,这里的“统一”是一个非常不确定的词,既能够是不同正本上的数据在任何时刻都放弃完全一致,也能够是不同客户端不同时刻拜访到的数据保持一致。一致性的强弱也会不同,有可能须要任何时候不同客端都能拜访到雷同的新的数据,也有可能是不同客户端某一时刻拜访的数据不雷同,但在一段时间后能够拜访到雷同的数据。因而,“一致性”是一个值得独自抽出来细说的词。在下一篇文章中,咱们将重点介绍这个词在不同上下文之间的含意。

此时,大家可能会有疑难,间接让所有正本在任意时刻都保持一致不就行了,为啥还要有各种不同的一致性呢?咱们认为有两个考量点,第一是性能,第二则是复杂性。

性能 比拟好了解,因为冗余的目标不齐全是为了高可用,还有提早和负载平衡这类晋升性能的目标,如果只一味地为了地强调数据统一,可能得失相当。复杂性 是因为分布式系统中,有着比单机零碎更加简单的不确定性,节点之间因为采纳不大牢靠的网络进行传输,并且不能共享对立的一套零碎工夫和内存地址(后文会具体进行阐明),这使得本来在一些单机零碎上很简略的事件,在转到分布式系统上当前就变得异样简单。这种复杂性和不确定性甚至会让咱们狐疑,这些正本上的数据真的能达成统一吗?下一篇文章会专门详细分析如何设计算法来应答这种简单和不确定性。

1.2 文章系列概述

本系列博文将分为高低两篇,第一篇将次要介绍几种常见的数据复制模型,而后介绍分布式系统的挑战,让大家对分布式系统一些稀奇古怪的故障有一些理性的意识。

第二篇文章将针对本篇中提到的问题,别离介绍事务、分布式共识算法和一致性,以及三者的内在联系,再分享如何在分布式系统中保证数据的一致性,进而让大家对数据复制技术有一个较为全面的意识。此外,本系列还将介绍业界验证分布式算法正确性的一些工具和框架。接下来,让咱们一起开始数据复制之旅吧!

2. 数据复制模式

总体而言,最常见的复制模式有三种,别离为主从模式、多主节点模式、无主节点模式,上面别离进行介绍。

2.1 最简略的复制模式——主从模式

简介

对复制而言,最直观的办法就是将正本赋予不同的角色,其中有一个主正本,主正本将数据存储在本地后,将数据更改作为日志,或者以更改流的形式发到各个从正本(后文也会称节点)中。在这种模式下,所有写申请就全副会写入到主节点上,读申请既能够由主正本承当也能够由从正本承当,这样对于读申请而言就具备了扩展性,并进行了负载平衡。但这外面存在一个衡量点,就是客户端视角看到的一致性问题。这个衡量点存在的外围在于,数据传输是通过网络传递的,数据在网络中传输的工夫是不能疏忽的。

如上图所示,在这个工夫窗口中,任何状况都有可能产生。在这种状况下,客户端何时算写入实现,会决定其余客户端读到数据的可能性。这里咱们假如这份数据有一个主正本和一个从正本,如果主正本保留后即向客户端返回胜利,这样叫做异步复制(1)。而如果等到数据传送到从正本 1,并失去确认之后再返回客户端胜利,称为同步复制(2)。这里咱们先假如零碎失常运行,在异步同步下,如果从正本承当读申请,假如 reader1 和 reader2 同时在客户端收到写入胜利后收回读申请,两个 reader 就可能读到不一样的值。

为了防止这种状况,实际上有两种角度的做法,第一种角度是让客户端只从主正本读取数据,这样,在失常状况下,所有客户端读到的数据肯定是统一的(Kafka 以后的做法);另一种角度则是采纳同步复制,假如应用纯的同步复制,当有多个正本时,任何一个正本所在的节点产生故障,都会使写申请阻塞,同时每次写申请都须要期待所有节点确认,如果正本过多会极大影响吞吐量。而如果仅采纳异步复制并由主正本承当读申请,当主节点故障产生切换时,一样会产生数据不统一的问题。

很多零碎会把这个决策权交给用户,这里咱们以 Kafka 为例,首先提供了同步与异步复制的语义(通过客户端的 acks 参数确定),另外提供了 ISR 机制,而只须要 ISR 中的正本确认即可,零碎能够容忍局部节点因为各种故障而脱离 ISR,那样客户端将不必期待其确认,减少了零碎的容错性。以后 Kafka 未提供让从节点承当读申请的设计,但在高版本中曾经有了这个 Feature。这种形式使零碎有了更大的灵活性,用户能够依据场景自在衡量一致性和可用性。

主从模式下须要的一些能力

减少新的从正本(节点)

  1. 在 Kafka 中,咱们所采取的的形式是通过新建正本调配的形式,以追赶的形式从主正本中同步数据。
  2. 数据库所采纳的的形式是通过快照 + 增量的形式实现。

    a. 在某一个工夫点产生一个一致性的快照。
    b. 将快照拷贝到从节点。
    c. 从节点连贯到主节点申请所有快照点后产生的扭转日志。
    d. 获取到日志后,利用日志到本人的正本中,称之为追赶。
    e. 可能反复多轮 a -d。

解决节点生效

从节点生效——追赶式复原

针对从节点生效,复原伎俩较为简单,个别采纳追赶式复原。而对于数据库而言,从节点能够晓得在解体前所执行的最初一个事务,而后连贯主节点,从该节点将拉取所有的事件变更,将这些变更利用到本地记录即可实现追赶。

对于 Kafka 而言,复原也是相似的,Kafka 在运行过程中,会定期项磁盘文件中写入 checkpoint,共蕴含两个文件,一个是 recovery-point-offset-checkpoint,记录曾经写到磁盘的 offset,另一个则是 replication-offset-checkpoint,用来记录高水位(下文简称 HW),由 ReplicaManager 写入,下一次复原时,Broker 将读取两个文件的内容,可能有些被记录到本地磁盘上的日志没有提交,这时就会先截断(Truncate)到 HW 对应的 offset 上,而后从这个 offset 开始从 Leader 正本拉取数据,直到认追上 Leader,被退出到 ISR 汇合中

主节点生效 – 节点切换

主节点生效则会稍稍简单一些,须要经验三个步骤来实现节点的切换。

  1. 确认主节点生效,因为生效的起因有多种多样,大多数零碎会采纳超时来断定节点生效。个别都是采纳节点间互发心跳的形式,如果发现某个节点在较长时间内无响应,则会认定为节点生效。具体到 Kafka 中,它是通过和 Zookeeper(下文简称 ZK)间的会话来放弃心跳的,在启动时 Kafka 会在 ZK 上注册长期节点,尔后会和 ZK 间维持会话,假如 Kafka 节点呈现故障(这里指被动的掉线,不蕴含被动执行停服的操作),当会话心跳超时时,ZK 上的长期节点会掉线,这时会有专门的组件(Controller)监听到这一信息,并认定节点生效。
  2. 选举新的主节点。这里能够通过通过选举的形式(民主协商投票,通常应用共识算法),或由某个特定的组件指定某个节点作为新的节点(Kafka 的 Controller)。在选举或指定时,须要尽可能地让新主与原主的差距最小,这样会最小化数据失落的危险(让所有节点都认可新的主节点是典型的共识问题)——这里所谓共识,就是让一个小组的节点就某一个议题达成统一,下一篇文章会重点进行介绍。
  3. 重新配置零碎是新的主节点失效,这一阶段根本能够了解为对集群的元数据进行批改,让所有外界晓得新主节点的存在(Kafka 中 Controller 通过元数据播送实现),后续及时旧的节点启动,也须要确保它不能再认为本人是主节点,从而承当写申请。

问题

尽管上述三个步骤较为清晰,但在理论产生时,还会存在一些问题:

  1. 假如采纳异步复制,在生效前,新的主节点与原主节点的数据存在 Gap,选举实现后,原主节点很快从新上线退出到集群,这时新的主节点可能会收到抵触的写申请,此时还未齐全执行上述步骤的第三步,也就是原主节点没有意识到本人的角色发生变化,还会尝试向新主节点同步数据。这时,个别的做法是,将原主节点上未实现复制的写申请丢掉,但这又可能会产生数据失落或不统一,假如咱们每条数据采纳 MySQL 的自增 ID 作为主键,并且应用 Redis 作为缓存,假如产生了 MySQL 的主从切换,从节点的计数器落后于主节点,那样可能呈现利用获取到旧的自增 ID,这样就会与 Redis 上对应 ID 取到的数据不统一,呈现数据泄露或失落。
  2. 假如下面的问题,原主节点因为一些故障永远不晓得本人角色曾经变更,则可能产生“脑裂”,两个节点同时操作数据,又没有相应解决抵触(没有设计这一模块),就有可能对数据造成毁坏。
  3. 此外,对于超时工夫的设定也是个十分复杂的问题,过长会导致服务不可用,设置过短则会导致节点频繁切换,假如自身零碎处于高负载状态,频繁角色切换会让负载进一步减轻(团队外部对 Kafka 僵尸节点的解决逻辑)。

异步复制面临的次要问题 – 复制滞后

如前文所述,如果咱们应用纯的同步复制,任何一台机器产生故障都会导致服务不可写入,并且在数较多的状况下,吞吐和可用性都会受到比拟大的影响。很多零碎都会采纳半步复制或异步复制来在可用性和一致性之间做衡量。

在异步复制中,因为写申请写到主正本就返回胜利,在数据复制到其余正本的过程中,如果客户端进行读取,在不同正本读取到的数据可能会不统一,《DDIA》将这个种景象称为复制滞后(Replication Lag),存在这种问题的复制行为所造成的数据一致性统称为最终一致性。将来还会重点介绍一下一致性和共识,但在本文不做过多的介绍,感兴趣的同学能够提前浏览《Problems with Replication Lag》这一章节。

2.2 多主节点复制

前文介绍的主从复制模型中存在一个比较严重的弊病,就是所有写申请都须要通过主节点,因为只存在一个主节点,就很容易呈现性能问题。尽管有从节点作为冗余应答容错,但对于写入申请实际上这种复制形式是不具备扩展性的。

此外,如果客户端来源于多个地区,不同客户端所感知到的服务相应工夫差距会十分大。因而,有些零碎顺着传统主从复制进行延长,采纳多个主节点同时承当写申请,主节点接到写入申请之后将数据同步到从节点,不同的是,这个主节点可能还是其余节点的从节点。复制模式如下图所示,能够看到两个主节点在接到写申请后,将数据同步到同一个数据中心的从节点。此外,该主节点还将一直同步在另一数据中心节点上的数据,因为每个主节点同时解决其余主节点的数据和客户端写入的数据,因而须要模型中减少一个抵触解决模块,最初写到主节点的数据须要解决抵触。

应用场景

a. 多数据中心部署

个别采纳多主节点复制,都是为了做多数据中心容灾或让客户端就近拜访(用一个高大上的名词叫做异地多活),在同一个地区应用多主节点意义不大,在多个地区或者数据中心部署相比主从复制模型有如下的劣势:

  • 性能晋升:性能晋升次要体现在两个外围指标上,首先从吞吐方面,传统的主从模型所有写申请都会通过主节点,主节点如果无奈采纳数据分区的形式进行负载平衡,可能存在性能瓶颈,采纳多主节点复制模式下,同一份数据就能够进行负载平衡,能够无效地晋升吞吐。另外,因为多个主节点散布在多个地区,处于不同地区的客户端能够就近将申请发送到对应数据中心的主节点,能够最大水平地保障不同地区的客户端可能以类似的提早读写数据,晋升用户的应用体验。
  • 容忍数据中心生效:对于主从模式,假如主节点所在的数据中心产生网络故障,须要产生一次节点切换才可将流量全副切换到另一个数据中心,而采纳多主节点模式,则可无缝切换到新的数据中心,晋升整体服务的可用性。

b. 离线客户端操作

除了解决多个地区容错和就近拜访的问题,还有一些乏味的场景,其中一个场景则是在网络离线的状况下还能持续工作,例如咱们笔记本电脑上的笔记或备忘录,咱们不能因为网络离线就禁止应用该程序,咱们仍然能够在本地欢快的编辑内容(图中标记为 Offline 状态),当咱们连上网之后,这些内容又会同步到近程的节点上,这外面咱们把本地的 App 也当做其中的一个正本,那么就能够承当用户在本地的变更申请。联网之后,再同步到近程的主节点上。

c. 协同编辑

这里咱们对离线客户端操作进行扩大,假如咱们所有人同时编辑一个文档,每个人通过 Web 客户端编辑的文档都能够看做一个主节点。这里咱们拿美团外部的学城(外部的 Wiki 零碎)举例,当咱们正在编辑一份文档的时候,基本上都会发现右上角会呈现“xxx 也在协同编辑文档”的字样,当咱们保留的时候,零碎就会主动将数据保留到本地并复制到其余主节点上,各自解决各自端上的抵触。

另外,当文档呈现了更新时,学城会告诉咱们有更新,须要咱们手动点击更新,来更新咱们本地主节点的数据。书中阐明,尽管不能将协同编辑齐全等同于数据库复制,但却是有很多相似之处,也须要解决抵触问题。

抵触解决

通过下面的剖析,咱们理解到多主复制模型最大挑战就是解决抵触,上面咱们简略看下《DDIA》中给出的通用解法,在介绍之前,咱们先来看一个典型的抵触。

a. 抵触实例

在图中,因为多主节点采纳异步复制,用户将数据写入到本人的网页就返回胜利了,但当尝试把数据复制到另一个主节点时就会出问题,这里咱们如果假如主节点更新时采纳相似 CAS 的更新形式时更新时,都会因为预期值不合乎从而回绝更新。针对这样的抵触,书中给出了几种常见的解决思路。

b. 解决思路

1. 防止抵触

所谓解决问题最基本的形式则是尽可能不让它产生,如果可能在应用层保障对特定数据的申请只产生在一个节点上,这样就没有所谓的“写抵触”了。持续拿下面的协同编辑文档举例,如果咱们把每个人的都在填有本人姓名表格的一行外面进行编辑,这样就能够最大水平地保障每个人的批改范畴不会有重叠,抵触也就迎刃而解了。

2. 收敛于统一状态

然而,对更新题目这种状况而言,抵触是没法防止的,但还是须要有办法解决。对于单主节点模式而言,如果同一个字段有屡次写入,那么最初写入的肯定是最新的。ZK、KafkaController、KafkaReplica 都有相似 Epoch 的形式去屏蔽过期的写操作,因为所有的写申请都通过同一个节点,程序是相对的,但对于多主节点而言,因为没有相对程序的保障,就只能试图用一些形式来决策绝对程序,使抵触最终收敛,这里提到了几种办法:

给每个写申请调配 Uniq-ID,例如一个工夫戳,一个随机数,一个 UUID 或 Hash 值,最终取最高的 ID 作为最新的写入。如果基于工夫戳,则称作最初写入者获胜(LWW),这种形式看上去十分间接且简略,并且十分风行。但很遗憾,文章一开始也提到了,分布式系统没有方法在机器间共享一套对立的零碎工夫,所以这个计划很有可能因为这个问题导致数据失落(时钟漂移)。

每个正本调配一个惟一的 ID,ID 高的更新优先级高于地区低的,这显然也会失落数据。

当然,咱们能够用某种形式做拼接,或利用事后定义的格局保留抵触相干信息,而后由用户自行解决。

3. 用户自行处理

其实,把这个操作间接交给用户,让用户本人在读取或写入前进行抵触解决,这种例子也是不足为奇,Github 采纳就是这种形式。

这里只是简略举了一些抵触的例子,其实抵触的定义是一个很奥妙的概念。《DDIA》第七章介绍了更多对于抵触的概念,感兴趣同学能够先自行浏览,在下一篇文章中也会提到这个问题。

c. 解决细节介绍

此外,在书中将要完结《复制》这一章时,也具体介绍了如何进行抵触的解决,这里也简略进行介绍。

这里咱们能够思考一个问题,为什么会发生冲突?通过浏览具体的解决伎俩后,咱们能够尝试这样了解,正是因为咱们对事件产生的先后顺序不确定,但这些事件的解决主体都有重叠(比方都有设置某个数据的值)。通过咱们对抵触的了解,加上咱们的常识揣测,会有这样几种形式能够帮咱们来判断事件的先后顺序。

1. 间接指定事件程序

对于事件产生的先后顺序,咱们一个最直观的想法就是,两个申请谁新要谁的,那这里定义“最新”是个问题,一个很简略的形式是应用工夫戳,这种算法叫做最初写入者获胜 LWW。

但分布式系统中没有对立的零碎时钟,不同机器上的工夫戳无奈保障准确同步,那就可能存在数据失落的危险,并且因为数据是笼罩写,可能不会保留两头值,那么最终可能也不是统一的状态,或呈现数据失落。如果是一些缓存零碎,笼罩写看上去也是能够的,这种简略粗犷的算法是十分好的收敛抵触的形式,但如果咱们对数据一致性要求较高,则这种形式就会引入危险,除非数据写入一次后就不会产生扭转。

2. 从事件自身推断因果关系和并发

下面间接简略粗犷的制订很显著过于果断,那么有没有可能工夫外面就存在一些因果关系呢,如果有咱们很显然能够通过因果关系晓得到底须要怎么的程序,如果不行再通过指定的形式呢?

例如:

这里是书中一个多主节点复制的例子,这里 ClientA 首先向 Leader1 减少一条数据 x =1,然 Leader1 采纳异步复制的形式,将变更日志发送到其余的 Leader 上。在复制过程中,ClientB 向 Leader3 发送了更新申请,内容则是更新 Key 为 x 的 Value,使 Value=Value+1。

原图中想表白的是,update 的日志发送到 Leader2 的工夫早于 insert 日志发送到 Leader2 的工夫,会导致更新的 Key 不存在。然而,这种所谓的事件关系自身就不是齐全不相干的,书中称这种关系为依赖或者 Happens-before。

咱们可能在 JVM 的内存模型(JMM)中听到过这个词,在 JMM 中,表白的也是多个线程操作的先后顺序关系。这里,如果咱们把线程或者申请了解为对数据的操作(区别在于一个是对本地内存数据,另一个是对近程的某处内存进行批改),线程或客户端都是一种执行者(区别在于是否须要应用网络),那这两种 Happens-before 也就能够在实质上进行对立了,都是为了形容事件的先后顺序而生。

书中给出了检测这类事件的一种算法,并举了一个购物车的例子,如图所示(以餐厅扫码点餐的场景为例):

图中两个客户端同时向购物车里放货色,事例中的数据库假如只有一个正本。

  1. 首先 Client1 向购物车中增加牛奶,此时购物车为空,返回版本 1,Value 为[牛奶]。
  2. 此时 Client2 向其中增加鸡蛋,其并不知道 Client1 增加了牛奶,但服务器能够晓得,因而调配版本号为 2,并且将鸡蛋和牛奶存成两个独自的值,最初将两个值和版本号 2 返回给客户端。此时服务端存储了[鸡蛋] 2 [牛奶]1。
  3. 同理,Client1 增加面粉,这时候 Client1 只认为增加了 [牛奶],因而将面粉与牛奶合并发送给服务端[牛奶,面粉],同时还附带了之前收到的版本号 1,此时服务端晓得,新值[牛奶,面粉] 能够替换同一个版本号中的旧值 [牛奶],但[鸡蛋] 是并发事件,调配版本号 3,返回值[牛奶,面粉] 3 [鸡蛋]2。
  4. 同理,Client2 向购物车增加 [火腿],但在之前的申请中,返回了鸡蛋,因而和火腿合并发送给服务端[鸡蛋,牛奶,火腿],同时附带了版本号 2,服务端间接将新值笼罩之前版本 2 的值[鸡蛋],但[牛奶,面粉] 是并发事件,因而存储值为[牛奶,面粉] 3 [鸡蛋,牛奶,火腿] 4 并调配版本号 4。
  5. 最初一次 Client 增加培根,通过之前返回的值里,晓得有 [牛奶,面粉,鸡蛋],Client 将值合并[牛奶,面粉,鸡蛋,培根] 联通之前的版本号一起发送给服务端,服务端判断 [牛奶,面粉,鸡蛋,培根] 能够笼罩之前的 [牛奶,面粉] 但[鸡蛋,牛奶,火腿]是并发值,加以保留。

通过下面的例子,咱们看到了一个依据事件自身进行因果关系的确定。书中给出了进一步的形象流程:

  • 服务端为每个主键保护一个版本号,每当主键新值写入时递增版本号,并将新版本号和写入值一起保留。
  • 客户端写主键,写申请比蕴含之前读到的版本号,发送的值为之前申请读到的值和新值的组合,写申请的相应也会返回对以后所有的值,这样就能够一步步进行拼接。
  • 当服务器收到有特定版本号的写入时,笼罩该版本号或更低版本号的所有值,保留高于申请中版本号的新值(与以后写操作属于并发)。

有了这套算法,咱们就能够检测出事件中有因果关系的事件与并发的事件,而对于并发的事件,依然像上文提到的那样,须要根据肯定的准则进行合并,如果应用 LWW,仍然可能存在数据失落的状况。因而,须要在服务端程序的合并逻辑中须要额定做些事件。

在购物车这个例子中,比拟正当的是合并新值和旧值,即最初的值是[牛奶,鸡蛋,面粉,火腿,培根],但这样也会导致一个问题,假如其中的一个用户删除了一项商品,然而 union 完还是会呈现在最终的后果中,这显然不合乎预期。因而能够用一个相似的标记位,标记记录的删除,这样在合并时能够将这个商品踢出,这个标记在书中被称为墓碑(Tombstone)。

2.3 无主节点复制

之前介绍的复制模式都是存在明确的主节点,从节点的角色划分的,主节点须要将数据复制到从节点,所有写入的程序由主节点管制。但有些零碎罗唆放弃了这个思路,去掉了主节点,任何正本都能间接承受来自客户端的写申请,或者再有一些零碎中,会给到一个协调者代表客户端进行写入(以 Group Commit 为例,由一个线程积攒所有客户端的申请对立发送),与多主模式不同,协调者不负责管制写入程序,这个限度的不同会间接影响零碎的应用形式。

解决节点生效

假如一个数据系统领有三个正本,当其中一个正本不可用时,在主从模式中,如果恰好是主节点,则须要进行节点切换能力持续对外提供服务,但在无主模式下,并不存在这一步骤,如下图所示:

这里的 Replica3 在某一时刻无奈提供服务,此时用户能够收到两个 Replica 的写入胜利的确认,即可认为写入胜利,而齐全能够疏忽那个无奈提供服务的正本。当生效的节点复原时,会从新提供读写服务,此时如果客户端向这个正本读取数据,就会申请到过期值。

为了解决这个问题,这里客户端就不是简略向一个节点申请数据了,而是向所有三个正本申请,这时可能会收到不同的响应,这时能够通过相似版本号来辨别数据的新旧(相似上文中并发写入的检测形式)。这里可能有一个问题,正本复原之后难道就始终让本人落后于其余正本吗?这必定不行,这会突破一致性的语义,因而须要一个机制。有两种思路:

  1. 客户端读取时对正本做修复,如果客户端通过并行读取多个正本时,读到了过期的数据,能够将数据写入到旧正本中,以便追赶上新正本。
  2. 反熵查问,一些零碎在正本启动后,后盾会一直查找正本之间的数据 diff,将 diff 写到本人的正本中,与主从复制模式不同的是,此过程不保障写入的程序,并可能引发显著的复制滞后。

读写 Quorum

上文中的实例咱们能够看出,这种复制模式下,要想保障读到的是写入的新值,每次只从一个正本读取显然是有问题的,那么须要每次写几个正本呢,又须要读取几个正本呢?这里的一个外围点就是让写入的正本和读取的正本有交加,那么咱们就可能保障读到新值了。

间接上公式:$w+r>N$。其中 N 为正本的数量,w 为每次并行写入的节点数,r 为每次同时读取的节点数,这个公式非常容易了解,就不做过多赘述。不过这里的公式尽管看着比拟直白也简略,外面却蕴含了一些零碎设计思考:

Quorum 一致性的局限性

看上去这个简略的公式就能够实现很弱小的性能,但这里有一些问题值得注意:

  • 首先,Quorum 并不是肯定要求少数,重要的是读取的正本和写入正本有重合即可,能够依照读写的可用性要求酌情思考配置。
  • 另外,对于一些没有很强一致性要求的零碎,能够配置 w +r <= N,这样能够期待更少的节点即可返回,这样尽管有可能读取到一个旧值,但这种配置能够很大晋升零碎的可用性,当网络大规模故障时更有概率让零碎持续运行而不是因为没有达到 Quorum 限度而返回谬误。
  • 假如在 w +r>N 的状况下,实际上也存在边界问题导致一些一致性问题:

    • 首先假如是 Sloppy Quorum(一个更为宽松的 Quorum 算法),写入的 w 和读取的 r 可能齐全不相交,因而不能保证数据肯定是新的。
    • 如果两个写操作同时产生,那么还是存在抵触,在合并时,如果基于 LWW,依然可能导致数据失落。
    • 如果写读同时产生,也不能保障读申请肯定就能取到新值,因为复制具备滞后性(上文的复制窗口)。
    • 如果某些正本写入胜利,其余正本写入失败(磁盘空间满)且总的胜利数少于 w,那些胜利的正本数据并不会回滚,这意味着及时写入失败,后续还是可能读到新值。

尽管,看上去 Quorum 复制模式能够保障获取到新值,但理论状况并不是咱们设想的样子,这个协定到最初可能也只能达到一个最终的一致性,并且仍然须要共识算法的加持。

2.4 本章小结

以上咱们介绍了所有常见的复制模式,咱们能够看到,每种模式都有肯定的利用场景和优缺点,然而很显著,光有复制模式远远达不到数据的一致性,因为分布式系统中领有太多的不确定性,须要前面各种事务、共识算法的帮忙能力去真正反抗那些“稀奇古怪”的问题。

到这里,可能会有同学就会问,到底都是些什么稀奇古怪的问题呢?相比单机零碎又有那些独特的问题呢?上面本文先来介绍分布式系统中的几个最典型的挑战(Trouble),让一些同学小小地“失望”一下,而后咱们会下一篇文章中再揭晓答案。

3. 分布式系统的挑战

这部分存在的意义次要想让大家了解,为什么一些看似简略的问题到了分布式系统中就会变得异样简单。顺便说一声,这一章都是一些“奇葩”景象,并没有过于简单的推理和证实,心愿大家可能较为轻松愉悦地看完这些内容。

3.1 局部生效

这是分布式系统中特有的一个名词,这里先看一个事实当中的例子。假如老板想要解决一批文件,如果让一个人做,须要十天。但老板感觉有点慢,于是他眉头一皱; 计上心来,想到能够找十个人来搞定这件事,而后本人把工作安顿好,认为这十个人一天正好干完,于是向他的下级山盟海誓地承诺一天搞定这件事。他把这十个人叫过去,把任务分配给了他们,他们彼此建了个微信群,约定每个小时在群里汇报本人手上的工作进度,并强调在早晨 5 点前须要通过邮件提交最初的后果。于是老版就去欢快的喝茶去了,然而事实却让他大跌眼镜。

首先,有个同学家里信号特地差,报告进度的时候只胜利报告了 3 个小时的,而后老板在微信里问,也收不到任何回复,最初后果也没法提交。另一个同学家的表因为长期没换电池,停在了下午四点,后果那人看了两次表都是四点,所以一点都没焦急,两头还看了个电影,慢慢悠悠做完交上去了,他还认为老板会褒扬他,提前了一小时交,后果实际上曾经是早晨八点了。还有一个同学因为前一天没睡好,效率极低,而且也没方法再去高强度的工作了。后果到了早晨 5 点,只有 7 集体实现了本人手头上的工作。

这个例子可能看起来并不是十分失当,但根本能够形容分布式系统特有的问题了。在分布式的零碎中,咱们会遇到各种“稀奇古怪”的故障,例如家里没信号(网络故障),不管怎么叫都不理你,或者断断续续的理你。另外,因为每个人都是通过本人家的表看工夫的,所谓的 5 点须要提交后果,在肯定水平上旧失去了参考的相对价值。因而,作为下面例子中的“老板”,不能那么自信的认为一个人干工作须要 10 天,就能够释怀交给 10 集体,让他们一天搞定。

咱们须要有各种措施来应答分派任务带来的不确定性,回到分布式系统中,局部生效是分布式系统肯定会呈现的状况。作为零碎自身的设计人员,咱们所设计的零碎须要可能容忍这种问题,绝对单机零碎来说,这就带来了特有的复杂性。

3.2 分布式系统特有的故障

不牢靠的网络

对于一个纯的分布式系统而言,它的架构大多为 Share Nothing 架构,即便是存算拆散这种看似的 Share Storage,它的底层存储一样是须要解决 Share Nothing 的。所谓 Nothing,这里更偏向于叫 Nothing but Network,网络是不同节点间共享信息的惟一路径,数据的传输次要通过以太网进行传输,这是一种异步网络,也就是网络自身并不保障收回去的数据包肯定能被接到或是何时被收到。这里可能产生各种谬误,如下图所示:

  1. 申请失落
  2. 申请正在某个队列中期待
  3. 近程节点曾经生效
  4. 近程节点无奈响应
  5. 近程节点曾经解决完申请,但在 ack 的时候丢包
  6. 近程接管节点曾经解决完申请,但回复解决很慢

本文认为,造成网络不牢靠的起因不光是以太网和 IP 包自身,其实利用自身有时候异样也是造成网络不牢靠的一个诱因。因为,咱们所采纳的节点间传输协定大多是 TCP,TCP 是个端到端的协定,是须要发送端和接收端两端内核中明确保护数据结构来维持连贯的,如果应用层产生了上面的问题,那么网络包就会在内核的 Socket Buffer 中排队得不到解决,或响应得不到解决。

  1. 应用程序 GC。
  2. 解决节点在进行重的磁盘 I /O,导致 CPU 无奈从中断中复原从而无奈解决网络申请。
  3. 因为内存换页导致的平稳。

这些问题和网络自身的不稳定性相叠加,使得外界认为的网络不靠谱的水平更加重大。因而这些不靠谱,会极大地减轻上一章中的 复制滞后性,进而带来各种各样的一致性问题。

应答之道

网络异样相比其余单机上的谬误而言,可能多了一种不确定的返回状态,即提早,而且提早的工夫齐全无奈预估。这会让咱们写起程序来异样头疼,对于上一章中的问题,咱们可能无从通晓节点是否生效,因为你发的申请压根可能不会有人响应你。因而,咱们须要把下面的“不确定”变成一种确定的模式,那就是利用“超时”机制。这里引申出两个问题:

  1. 假如可能检测出生效,咱们应该如何应答?

    a. 负载平衡须要防止往生效的节点上发数据(服务发现模块中的健康检查性能)。
    b. 如果在主从复制中,如果主节点生效,须要登程选举机制(Kafka 中的长期节点掉线,Controller 监听到变更触发新的选举,Controller 自身的选举机制)。
    c. 如果服务过程解体,但操作系统运行失常,能够通过脚本告诉其余节点,以便新的节点来接替(Kafka 的僵尸节点检测,会触发强制的长期节点掉线)。
    d. 如果路由器曾经确认指标节点不可拜访,则会返回 ICMP 不可达(ping 不通走下线)。

  2. 如何设置超时工夫是正当的?

很遗憾地通知大家,这外面实际上是个衡量的问题,短的超时工夫会更快地发现故障,但同时减少了误判的危险。这里假如网络失常,那么如果端到端的 ping 工夫为 d,解决工夫为 r,那么基本上申请会在 2d+ r 的工夫实现。但在事实中,咱们无奈假如异步网络的具体提早,理论状况可能会更简单。因而这是一个非常靠教训的工作。

3.2 不牢靠的时钟

说完了“信号”的问题,上面就要说说每家的“钟表”——时钟了,它次要用来做两件事:

  1. 形容以后的相对工夫
  2. 形容某件事情的持续时间

在 DDIA 中,对于这两类用处给出了两种工夫,一类成为墙上时钟,它们会返回以后的日期和工夫,例如 clock_gettime(CLOCK_REALTIME)或者 System.currentTimeMills,但这类反馈准确工夫的 API,因为时钟同步的问题,可能会呈现回拨的状况。因而,作为持续时间的测量通常采纳枯燥时钟,例如 clock_gettime(CLOCK_MONOTONIC) 或者 System.nanoTime。高版本的 Kafka 中把申请的相应提早计算全副换成了这个 API 实现,应该也是这个起因。

这里时钟同步的具体原理,以及如何会呈现不精确的问题,这里就不再具体介绍了,感兴趣的同学能够自行浏览书籍。上面将介绍一下如何应用工夫戳来形容事件程序的案例,并展现如何因时钟问题导致事件程序判断异样的:

这里咱们发现,Node1 的时钟比 Node3 快,当两个节点在解决完本地申请筹备写 Node2 时产生了问题,本来 ClientB 的写入显著晚于 ClientA 的写入,但最终的后果,却因为 Node1 的工夫戳更大而抛弃了本该保留的 x +=1,这样,如果咱们应用 LWW,肯定会呈现数据不合乎预期的问题。

因为时钟不精确,这里就引入了统计学中的置信区间的概念,也就是这个工夫到底在一个什么样的范畴里,个别的 API 是无奈返回相似这样的信息的。不过,Google 的 TrueTime API 则恰好可能返回这种信息,其调用后果是一个区间,有了这样的 API,的确就能够用来做一些对其有依赖的事件了,例如 Google 自家的 Spanner,就是应用 TrueTime 实现快照隔离。

如何在这艰巨的环境中设计零碎

下面介绍的问题是不是挺“令人失望”的?你可能发现,当初工夫可能是错的,测量可能是不准的,你的申请可能得不到任何响应,你可能不晓得它是不是还活着 …… 这种环境真的让设计分布式系统变得异样艰巨,就像是你在 100 集体组成的大部门外面协调一些工作一样,工作量异样的微小且简单。

但好在咱们并不是什么都做不了,以协调这件事为例,咱们必定不是果断地听取一个人的意见,让咱们回到学生时代。咱们须要评比一位班长,必定咱们都经验过投票、唱票的环节,最终得票最多的那个人入选,有时可能还须要设置一个前提,须要得票超过半数。

映射到分布式系统中也是如此,咱们不能轻易地置信任何一台节点的信息,因为它有太多的不确定,因而更多的状况下,在分布式系统中如果咱们须要就某个事件达成统一,也能够采取像竞选或议会一样,大家协商、投票、仲裁决定一项提议达成统一,假相由少数人商议决定,从而达到大家的统一和对立,这也就是前面要介绍的分布式共识协定。这个协定可能容忍一些节点的局部生效,或者莫名其妙的故障带来的问题,让零碎可能失常地运行上来,确保申请到的数据是可信的。

上面给出一些理论分布式算法的实践模型,依据对于提早的假如不同,这里介绍三种零碎模型。

1. 同步模型

该模型次要假如网络提早是有界的,咱们能够分明地晓得这个提早的上下界,不论呈现任何状况,它都不会超出这个界线。

2. 半同步模型(大部分模型都是基于这个假如)

半同步模型认为大部分状况下,网络和提早都是失常的,如果呈现违反的状况,偏差可能会十分大。

3. 异步模型

对提早不作任何假如,没有任何超时机制。

而对于节点生效的解决,也存在三种模型,这里咱们疏忽歹意谎话的拜占庭模型,就剩下两种。

1. 解体 - 终止模型(Crash-Stop):该模型中假如一个节点只能以一种形式产生故障,即解体,可能它会在任意时刻进行响应,而后永远无奈复原。

2. 解体 - 复原模型:节点可能在任何时刻产生解体,可能会在一段时间后复原,并再次响应,在该模型中假如,在长久化存储中的数据将得以保留,而内存中的数据会失落。

而少数的算法都是基于半同步模型 + 解体 - 复原模型来进行设计的。

Safety and Liveness

这两个词在分布式算法设计时起着非常要害的作用,其中安全性(Safety)示意没有意外产生,假如违反了安全性准则,咱们肯定可能指出它产生的工夫点,并且安全性一旦违反,无奈撤销。而活性(Liveness)则示意“预期的事件最终肯定会产生”,可能咱们无奈明确具体的工夫点,但咱们冀望它在将来某个工夫可能满足要求。

在进行分布式算法设计时,通常须要必须满足安全性,而活性的满足需要具备肯定的前提。

7. 总结

以上就是第一篇文章的内容,简略做下回顾,本文首先介绍了复制的三种常见模型,别离是主从复制、多主复制和无主复制,而后别离介绍了这三种模型的特点、实用场景以及优缺点。接下来,咱们用了一个现实生活中的例子,向大家展现了分布式系统中常见的两个特有问题,别离是节点的局部生效以及无奈共享零碎时钟的问题,这两个问题为咱们设计分布式系统带来了比拟大的挑战。如果没有一些设计特定的措施,咱们所设计的分布式系统将无奈很好地满足设计的初衷,用户也无奈通过分布式系统来实现本人想要的工作。

以上这些问题,咱们会下篇文章《Replication(下):事务,一致性与共识》中逐个进行解决,而事务、一致性、共识这三个关键词,会为咱们在设计分布式系统时保驾护航。

8. 作者简介

仕禄,美团根底研发平台 / 数据迷信与平台部工程师。

浏览美团技术团队更多技术文章合集

前端 | 算法 | 后端 | 数据 | 平安 | 运维 | iOS | Android | 测试

| 在公众号菜单栏对话框回复【2021 年货】、【2020 年货】、【2019 年货】、【2018 年货】、【2017 年货】等关键词,可查看美团技术团队历年技术文章合集。

| 本文系美团技术团队出品,著作权归属美团。欢送出于分享和交换等非商业目标转载或应用本文内容,敬请注明“内容转载自美团技术团队”。本文未经许可,不得进行商业性转载或者应用。任何商用行为,请发送邮件至 tech@meituan.com 申请受权。

退出移动版