分布式系统原理介绍

概念

1.1 模型


分布式系统在分布式层面的基本问题模型,为了控制问题的规模,精简了分布式系统的模型。



1.1.1 节点


节点是指一个可以独立按照分布式协议完成的一组逻辑的程序个体,一个节点往往是一个操作系统上的进程。

1.1.2 通信


节点与节点之间是完全独立、相互隔离的,节点之间传递信息的唯一方式是通过不可靠的网络进行通信。即一个节点可以向其他节点通过网络发送消息,但是发送消息的节点无法确认消息是否被接受节点完整正确的收到。


1.1.3 存储


节点可以通过将数据写入与节点在同一台机器的本地存储设备保存数据。通常的存储设备有磁盘,SSD等存储、读取数据的节点称为有状态的节点,反之称为无状态节点。如果某个节点A存储数据的方式是将数据通过网络发送到另一个节点B,由节点B负责将数据存储到节点B的本地存储设备,那么不能认为节点A是有状态的节点,而只有节点B是有状态的节点。


1.1.4 异常


分布式系统的核心问题之一就是处理各种异常情况


1.1.4.1 机器宕机


当发生宕机的时候,节点无法进入正常的工作状态,称之为不可用状态。机器重启后,节点可以通过读取本地存储设备中的信息或者通过读取其他节点数据的方式恢复内存信息,从而恢复到某一宕机前的状态。 无状态的节点可以立即恢复


1.1.4.2 网络异常

节点通过不可靠的网络进行通信


1.1.4.2.1 消息丢失



消息丢失是最常见的网络异常,在发生网络拥堵、路由变动、设备异常等情况时,都可能发生发送的数据丢失。 如果某些节点的直接的网络通信正常或丢包率在合理范围内,而某些 节点之间始终无法正常通信,则称这种特殊的网络异常为“网络分化”(network partition)。网络分 化是一类常见的网络异常,尤其当分布式系统部署在多个机房之间时。图 1-1 中,用虚线分割了两 片节点,这两片节点之间彼此完全无法通信,即出现了“网络分化” 例 1.1:某分布式系统部署于两个机房,机房间使用内部独立光纤链路。由于机房间的光纤链路 交割调整,两个机房间通信中断,期间,各机房内的节点相互通信正常。更为严重的是,所有的英 特网用户都可以正常访问两个机房内对外服务节点。本文后续将讨论出现这种严重的网络分化时, 对分布式系统的设计带来的巨大挑战

1.1.4.2.2 消息乱序



消息乱序是指节点发送的网络消息有一定的概率不是按照发送时的顺序依次到达目的节点。


1.1.4.2.3 数据错误

网络上传输的数据有可能发生比特错误,从而造成数据错误


1.1.4.2.4 不可靠的TCP

TCP也会因为一些极端情况变得不可靠


1.1.4.3 分布式系统的三态

一个节点A向另一个节点B发送消息,节点B根据收到的消息内容完成某些操作,并将操作的结果通过另一个消息返回给节点A,那么这个RPC的执行结果就有三种状态:“成功”,“失败”,“超时(未知)”,称之为分布式系统的三态。


1.1.4.4 存储数据丢失

数据丢失指节点存储的数据不可被读取或读取出的数据错误。数据丢失是另一类常见的异常。 尤其是使用机械硬盘做存储介质时,硬盘损坏的概率较大。对于有状态节点来说,数据丢失意味着 状态丢失,通常只能从其他节点读取、恢复存储的状态。


1.1.4.6 异常的处理原则

被大量工程实践所检验的异常处理黄金原则是:任何在设计阶段考虑到的异常情况一定会在系统实际运行中发生,但在系统实际运行遇到的异常却很可能在设计时未能考虑,所以,除非需求指标允许,在系统设计时不能放过任何异常情况。


1.2 副本

1.2.1 副本的概念


副本是指在分布式系统中为数据或服务提供的冗余。对于数据副本指在不同的节点上持久化同一份数据,当出现某一个节点的存储数据丢失时,可以从副本上读到数据。

1.2.1 副本一致性


分布式系统通过副本协议,使得从系统外部读取系统内部各个副本的数据 在一定的约束条件下相同,称之为副本一致性


1.3 衡量分布式系统的指标

评价分布式系统有一些常用的指标,包括性能,可用性,可扩展性,一致性

1.3.1 性能


常见的性能指标有系统的吞吐能力,指系统在某段时间可以处理的数据总量,通常可以用系统美妙处理的总的数据量来衡量;系统的响应延迟,指系统完成某一功能需要使用的时间;系统的并发能力,指系统可以同时完成某一功能的能力,通常也用QPS来衡量。以上三个性能指标往往会相互制约,追求高吞吐的系统,往往很难做到低延迟;系统平均响应时间较长时,也很难提高QPS。


1.3.2 可用性


系统的可用性指系统在面对各种异常时可以正确提供服务的能力。系统的可用性可以用系统停服务的时间与正常服务时间的比例衡量,也可以用某功能的失败次数与成功次数的比例衡量。


1.3.3 可扩展性


系统的可用性指分布式系统通过扩展集群机器规模提高系统性能(吞吐、延迟、并发)、存储容量、计算能力的特性。可扩展性时分布式系统的特有性质。


1.3.4 一致性


分布式系统为了提高可用性,总是不可避免的使用副本的机制,从而引发副本一致性的问题

2.分布式系统原理


2.1 数据分布方式

所谓分布式系统顾名思义就是利用多台计算机协同解决单台计算机所不能解决的计算、存储等问题


2.1.1 哈希方式

哈希方式是最常见的数据分布方式,其方法是按照数据的某一特征计算哈希值,并将哈希值与机器中的机器建立映射关系,从而将不同哈希值的数据分布到不同的机器上。所谓数据特征可以是key -value 系统中的key,也可以是其他与应用业务逻辑相关的值。例如,一种常见的哈希方式是按 数据属于的用户 id 计算哈希值,集群中的服务器按 0 到机器数减 1 编号,哈希值除以服务器的个数, 结果的余数作为处理该数据的服务器编号。工程中,往往需要考虑服务器的副本冗余,将每数台(例 如 3)服务器组成一组,用哈希值除以总的组数,其余数为服务器组的编号。图 2-1 给出了哈希方 式分数据的一个例子,将数据按哈希值分配到 4 个节点上。




2.1.2 按数据范围分布


按数据范围分布是另一种常见的数据分布方式,将数据按特征值的值域范围划分为不同的区间,使得集群中每台服务器处理不同区间的数据。例 2.1.1:已知某系统中用户 id 的值域范围是[1,100),集群有 3 台服务器,使用按数据范围划分 数据的数据分布方式。将用户 id 的值域分为三个区间[1, 33),,[33, 90),[90, 100)分别由 3 台服务器 负责处理。图 2-3 给出这个例子的示意图。





与哈希分布数据的方式只需要记录哈希函数及分桶个数(机器数)不同,按数据范围分布数据 需要记录所有的数据分布情况。一般的,往往需要使用专门的服务器在内存中维护数据分布信息, 称这种数据的分布信息为一种元信息。甚至对于大规模的集群,由于元信息的规模非常庞大,单台 计算机无法独立维护,需要使用多台机器作为元信息服务器。
使用范围分布数据的方式的最大优点就是可以灵活的根据数据量的具体情况拆分原有数据区间, 拆分后的数据区间可以迁移到其他机器,一旦需要集群完成负载均衡时,与哈希方式相比非常灵活。 另外,当集群需要扩容时,可以随意添加机器,而不限为倍增的方式,只需将原机器上的部分数据 分区迁移到新加入的机器上就可以完成集群扩容。


2.1.3 按数据量分布

另一类常用的数据分布方式则是按照数据量分布数据。与哈希方式和按数据范围方式不同,数 据量分布数据与具体的数据特征无关,而是将数据视为一个顺序增长的文件,并将这个文件按照某 一较为固定的大小划分为若干数据块(chunk),不同的数据块分布到不同的服务器上。与按数据范 围分布数据的方式类似的是,按数据量分布数据也需要记录数据块的具体分布情况,并将该分布信 息作为元数据使用元数据服务器管理。


2.1.4 一致性哈希

一致性哈希(consistent hashing)是另一个种在工程中使用较为广泛的数据分布方式。一致性哈 希最初在 P2P 网络中作为分布式哈希表(DHT)的常用数据分布算法。一致性哈希的基本方式是使用一个哈希函数计算数据或数据特征的哈希值,令该哈希函数的输出值域为一个封闭的环,即哈希 函数输出的最大值是最小值的前序。将节点随机分布到这个环上,每个节点负责处理从自己开始顺 时针至下一个节点的全部哈希值域上的数据。

2.1.5 副本与数据分布

假设有 3 个副 本机器,某时刻其中某台机器磁盘损坏,丢失了全部数据,此时使用新的机器替代故障机器,为了 是的新机器也可以提供服务,需要从正常的两台机器上拷贝数据。此种全盘拷贝数据一般都较为消 耗资源,为了不影响服务质量,实践中往往采用两种方式:一、将一台可用的副本机器下线,专门 作为数据源拷贝数据,这样做的缺点是造成实际正常副本数只有 1 个,对数据安全性造成巨大隐患, 且如果服务由于分布式协议设计或压力的要求必须 2 个副本才能正常工作,则该做法完全不可行。 二、以较低的资源使用限速的方法从两个正常副本上拷贝数据,此方法不停服务,但可以选择服务 压力较小的时段进行。该方法的缺点是速度较慢,如果需要恢复的数据量巨大(例如数 T),限速 较小(例如 10MB/s),往往需要数天才能够完成恢复。 更合适的做法不是以机器作为副本单位,而是将数据拆为较合理的数据段,以数据段为单位作 为副本。实践中,常常使得每个数据段的大小尽量相等且控制在一定的大小以内。数据段有很多不 同的称谓,segment,fragment,chunk,partition 等等。数据段的选择与数据分布方式直接相关。对 于哈希分数据的方式,每个哈希分桶后的余数可以作为一个数据段,为了控制数据段的大小,常常 使得分桶个数大于集群规模。例如,有 3 台服务器,10G 数据,为了使得每个数据段都是 100M 左 右大小,哈希后按 100 取模,得 1000 个数据段,每台服务器可以负责 333 个数据段。对于按数据范 围分布数据的方式,可以将每个数据区间作为一个数据段,并控制数据区间中数据的大小。对于按 数据量分数据的方式,可以自然的按照每个数据块作为数据段。对于一致性哈希分布数据的方式, 通常的做法是讲一致性哈希环分为若干等长分区,分区个数一般远大于节点个数,假设哈希函数均 匀,则每个分区中的数据可以作为一个数据段。 一旦将数据分为数据段,则可以以数据段为单位管理副本,从而副本与机器不再硬相关,每台 机器都可以负责一定数据段的副本。

2.1.6 本地化计算

对于分布式系统而言,除了解决大规模存储问题更需要解决大规模的计算问题。然而计算离不开数 据,计算的规模往往与输入的数据量或者计算产生的中间结果的数据量正相关。在分布式系统中, 数据的分布方式也深深影响着计算的分布方式。 在分布式系统中计算节点和保存计算数据的存储节点可以在同一台物理机器上,也可以位于不 同的物理机器。如果计算节点和存储节点位于不同的物理机器则计算的数据需要通过网络传输,此 种方式的开销很大,甚至网络带宽会成为系统的总体瓶颈。另一种思路是,将计算尽量调度到与存 储节点在同一台物理机器上的计算节点上进行,这称之为本地化计算。本地化计算是计算调度的一 种重要优化,其体现了一种重要的分布式调度思想:“移动数据不如移动计算”。

2.2基本副本协议

副本控制协议指按特定的协议流程控制副本数据的读写行为,使得副本满足一定的可用性和一 致性要求的分布式协议。副本控制协议要具有一定的对抗异常状态的容错能力,从而使得系统具有 一定的可用性,同时副本控制协议要能提供一定一致性级别。副本协议分为“中心化副本控制协议”和“去中心化的副本控制协议”

2.2.1 中心化副本协议

中心化副本控制协议的基本思路是由一个中心节点协调副本数据的更新、维护副本之间的一致 性。中心化副本控制协议的缺点是系统的可用性依赖于中心化节点,当 中心节点异常或与中心节点通信中断时,系统将失去某些服务(通常至少失去更新服务),所以中心 化副本控制协议的缺点正是存在一定的停服务时间。

2.2.2 primary-secondary 协议

本文着重介绍一种非常常用的 primary-secondary(也称 primary-backup)的中心化副本控制协议。 在 primary-secondary 类型的协议中,副本被分为两大类,其中有且仅有一个副本作为 primary 副本, 除 primary 以外的副本都作为 secondary 副本。维护 primary 副本的节点作为中心节点,中心节点负 责维护数据的更新、并发控制、协调副本的一致性。

2.2.2.1 数据更新基本流程

流程 2.2.1: Primary-secondary 协议的数据更新流程

  1. 数据更新都由 primary 节点协调完成。
  2. 外部节点将更新操作发给 primary 节点
  3. primary 节点进行并发控制即确定并发更新操作的先后顺序
  4. primary 节点将更新操作发送给 secondary 节点
  5. primary 根据 secondary 节点的完成情况决定更新是否成功并将结果返回外部节点

2.2.2.2 数据读取方式

数据读取方式是 primary-secondary 类协议需要解决的第二个问题。与数据更新流程类似,读取方式也与一致性高度相关。如果只需要最终一致性,则读取任何副本都可以满足需求。如果需要会 话一致性,则可以为副本设置版本号,每次更新后递增版本号,用户读取副本时验证版本号,从而 保证用户读到的数据在会话范围内单调递增。使用 primary-secondary 比较困难的是实现强一致性。

2.2.2.3 数据同步

Primary-secondary 型协议一般都会遇到 secondary 副本与 primary 不一致的问题。此时,不一致 的 secondary 副本需要与 primary 进行同步(reconcile)。 通常不一致的形式有三种:一、由于网络分化等异常,secondary 上的数据落后于 primary 上的 数据。二、在某些协议下,secondary 上的数据有可能是脏数据,需要被丢弃。所谓脏数据是由于 primary 副本没有进行某一更新操作,而 secondary 副本上反而进行的多余的修改操作,从而造成 secondary 副本数据错误。三、secondary 是一个新增加的副本,完全没有数据,需要从其他副本上 拷贝数据。

2.2.3 去中心化副本控制协议

去中心化副本控制是另一类较为复杂的副本控制协议。与中心化副本系统协议最大的不同是,去中心化副本控制协议没有中心节点,协议中所有的节点都是完全对等的,节点之间通过平等协商 达到一致。从而去中心化协议没有因为中心化节点异常而带来的停服务等问题。图 2-9 给出了去中 心化副本控制协议的示意图。



然而,没有什么事情是完美的,去中心化协议的最大的缺点是协议过程通常比较复杂。尤其当 去中心化协议需要实现强一致性时,协议流程变得复杂且不容易理解。由于流程的复杂,去中心化 协议的效率或者性能一般也较中心化协议低。一个不恰当的比方就是,中心化副本控制协议类似专 制制度,系统效率高但高度依赖于中心节点,一旦中心节点异常,系统受到的影响较大;去中心化 副本控制协议类似民主制度,节点集体协商,效率低下,但个别节点的异常不会对系统总体造成太 大影响。xd

2.3 Lease 机制

Lease 机制是最重要的分布式协议,广泛应用于各种实际的分布式系统中。即使在某些系统中 相似的设计不被称为 lease,但我们可以分析发现其本质就是一种 lease 的实现。本节从一个分布式 cache 系统出发介绍最初的 lease 机制,接着加以引申,探讨 lease 机制的本质。最后介绍了 lease 机 制最重要的应用:判定节点状态。

2.3.1 基于 lease 的分布式 cache 系统

在一个分布式系统中,有一个中心服务器节点,中心服务器存储、维护 着一些数据,这些数据是系统的元数据。系统中其他的节点通过访问中心服务器节点读取、修改其 上的元数据。由于系统中各种操作都依赖于元数据,如果每次读取元数据的操作都访问中心服务器 节点,那么中心服务器节点的性能成为系统的瓶颈。为此,设计一种元数据 cache,在各个节点上 cache 元数据信息,从而减少对中心服务器节点的访问,提高性能。设计的 cache 系统要能最大可能的处理节点宕机、网络中断等 异常,最大程度的提高系统的可用性。 为此,利用 lease 机制设计一套 cache 系统,其基本原理为如下。中心服务器在向各节点发送数 据时同时向节点颁发一个 lease。每个 lease 具有一个有效期,和信用卡上的有效期类似,lease 上的 有效期通常是一个明确的时间点,例如 12:00:10,一旦真实时间超过这个时间点,则 lease 过期失效。 这样 lease 的有效期与节点收到 lease 的时间无关,节点可能收到 lease 时该 lease 就已经过期失效。 这里首先假设中心服务器与各节点的时钟是同步的,下节中讨论时钟不同步对 lease 的影响。中心服 务器发出的 lease 的含义为:在 lease 的有效期内,中心服务器保证不会修改对应数据的值。因此, 节点收到数据和 lease 后,将数据加入本地 Cache,一旦对应的 lease 超时,节点将对应的本地 cache 数据删除。中心服务器在修改数据时,首先阻塞所有新的读请求,并等待之前为该数据发出的所有 lease 超时过期,然后修改数据的值。 具体的服务器与客户端节点一个基本流程如下: 流程 2.3.1:基于 lease 的 cache,客户端节点读取元数据

  1. 判断元数据是否已经处于本地 cache 且 lease 处于有效期内 1.1 是:直接返回 cache 中的元数据 1.2 否:向中心服务器节点请求读取元数据信息 1.2.1 服务器收到读取请求后,返回元数据及一个对应的 lease 1.2.2 客户端是否成功收到服务器返回的数据 1.2.2.1 失败或超时:退出流程,读取失败,可重试 1.2.2.2 成功:将元数据与该元数据的lease记录到内存中,返回元数据 流程 2.3.2:基于 lease 的 cache,客户端节点修改元数据流程
  2. 节点向服务器发起修改元数据请求。
  3. 服务器收到修改请求后,阻塞所有新的读数据请求,即接收读请求,但不返回数据。 3. 服务器等待所有与该元数据相关的 lease 超时。
  4. 服务器修改元数据并向客户端节点返回修改成功。 上述机制可以保证各个节点上的 cache 与中心服务器上的中心始终一致。这是因为中心服务器 节点在发送数据的同时授予了节点对应的 lease,在 lease 有效期内,服务器不会修改数据,从而客 户端节点可以放心的在 lease 有效期内 cache 数据。上述 lease 机制可以容错的关键是:服务器一旦 发出数据及 lease,无论客户端是否收到,也无论后续客户端是否宕机,也无论后续网络是否正常, 服务器只要等待 lease 超时,就可以保证对应的客户端节点不会再继续 cache 数据,从而可以放心的 修改数据而不会破坏 cache 的一致性。 上述基础流程有一些性能和可用性上的问题,但可以很容易就优化改性。优化点一:服务器在 修改元数据时首先要阻塞所有新的读请求,造成没有读服务。这是为了防止发出新的 lease 从而引起 不断有新客户端节点持有 lease 并缓存着数据,形成“活锁”。优化的方法很简单,服务器在进入修 改数据流程后,一旦收到读请求则只返回数据但不颁发 lease。从而造成在修改流程执行的过程中, 客户端可以读到元数据,只是不能缓存元数据。进一步的优化是,当进入修改流程,服务器颁发的 lease 有效期限选择为已发出的 lease 的最大有效期限。这样做,客户端可以继续在服务器进入修改 流程后继续缓存元数据,但服务器的等待所有 lease 过期的时间也不会因为颁发新的 lease 而不断延 长。实际使用中,第一层优化就足够了,因为等待 lease 超时的时间会被“优化点二”中的优化方法 大大减少。优化点二:服务器在修改元数据时需要等待所有的 lease 过期超时,从而造成修改元数据 的操作时延大大增大。优化的方法是,在等待所有的 lease 过期的过程中,服务器主动通知各个持有 lease 的节点放弃 lease 并清除 cache 中的数据,如果服务器收到客户端返回的确认放弃 lease 的消息, 则服务器不需要在等待该 lease 超时。该过程中,如果因为异常造成服务器通知失败或者客户端节点 发送应答消息失败,服务器只需依照原本的流程等待 lease 超时即可,而不会影响协议的正确性。 最后,我们分析一下 cache 机制与多副本机制的区别。Cache 机制与多副本机制的相似之处都 27

是将一份数据保存在多个节点上。但 Cache 机制却要简单许多,对于 cache 的数据,可以随时删除 丢弃,并命中 cache 的后果仅仅是需要访问数据源读取数据;然而副本机制却不一样,副本是不能 随意丢弃的,每失去一个副本,服务质量都在下降,一旦副本数下降到一定程度,则往往服务将不 再可用。

2.5 日志技术

日志技术是宕机恢复的主要技术之一[3]。日志技术最初使用在数据库系统中。严格来说日志技 术不是一种分布式系统的技术,但在分布式系统的实践中,却广泛使用了日志技术做宕机恢复,甚 至如 BigTable 等系统将日志保存到一个分布式系统中进一步增强了系统容错能力。


github源代码

喜欢就star一下吧!👻👻👻

作者原创,转载请注明出处,如有错误描述,请评论纠正,谢谢大家!🐳🐳🐳

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦