分布式系统原理介绍——读书笔记

一、概念

1.模型

TCP:TCP为传输的每一个字节设置顺序递增的序列号,由接收方在收到数据后按序列号重组数据并发送确认信息,当发现数据包丢失时,TCP协议重传丢失的数据包。

分布系统的三态:成功、失败、超时

超时解决方案:1.发起读取数据以验证RPC是否成功;2.设计分布式协议时将执行步骤设计为可重试,既具有所谓的“幂等性”。

2.副本

数据副本是分布式系统解决数据丢失的唯一手段。

副本协议是贯穿整个分布式系统的理论核心。

副本一致性:

  • 强一致性:任何时刻任何用户或节点都可以读到最近一次成功更新的副本数据;
  • 单调一致性:任何时刻,任何用户一旦读到某个数据在某次更新后的值, 这个用户不会再读到比这个值更旧的值;
  • 会话一致性:任何用户在某一次会话内一旦读到某个数据在某次更新后的值, 这个用户在这次会话过程中不会再读到比这个值更旧的值;
  • 最终一致性:最终一致性要求一旦更新成功,各个副本上的数据最终将达 到完全一致的状态,但达到完全一致状态所需要的时间不能保障;
  • 弱一致性:旦某个更新成功,用户无法在一个确定时间内读到这次更新的 值,且即使在某个副本上读到了新的值,也不能保证在其他副本上可以读到新的值。

3.衡量分布式系统的指标

性能:

  • 系统的吞吐能力:指系统在某 一时间可以处理的数据总量,通常可以用系统每秒处理的总的数据量来衡量;
  • 系统的响应延迟:指系统完成某一功能需要使用的时间;
  • 系统的并发能力:指系统可以同时完成某一功能的能力,通常也用 QPS(query per second)来衡量。
    系统的可用性:可以用系统停服务的时间与正常服务的时间的比例来衡量,也可以用某功能的失败次数与成功次数的 比例来衡量。

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

二、分布式系统原理

1.数据分布方式

1.1 哈希方式

其方法是按照数据的某一特征计算哈希值,并将哈希值与 机器中的机器建立映射关系,从而将不同哈希值的数据分布到不同的机器上;
工程中,扩展哈希分布数据的系统时,往往使得集群规模成倍扩 展,按照数据重新计算哈希,这样原本一台机器上的数据只需迁移一半到另一台对应的机器上即可 完成扩展。

针对哈希扩展性较差的问题:一种思路是将对应关系作为元数据由专门的元数据服务器管理。同时,哈希值取模个数往往大于机器个数,这样同一台机器上需 要负责多个哈希取模的余数。在集群扩容时,将部分余数分配到新加入的机器并迁移对应的数据到 新机器上,从而使得扩容不再依赖于机器数量的成本增长。

1.2 数据范围分布

将数据按特征值的值域范围划分为不同的区间,使得集群中每台(组)服务器处理不同区间的数据。
实际工程中,一般也不按照某一维度划分数据范围,而是使用全部数据划分范围,从而避免数 据倾斜的问题。
哈希分布数据的方式使得系统中的数据类似一个哈希表。按范围分数据的方式则使得从全局看 数据类似一个 B 树。每个具体的服务器都是 B 树的叶子节点,元数据服务器是 B 树的中间节点。

1.3 按数据量分布

数据量分布数据与具体的数据特征无关,而是将数据视为一个顺序增长的文件,并将这个文件按照某 一较为固定的大小划分为若干数据块(chunk),不同的数据块分布到不同的服务器上。

1.4 一致哈希

用一个哈希函数计算数据或数据特征的哈希值,令该哈希函数的输出值域为一个封闭的环,即哈希 函数输出的最大值是最小值的前序。将节点随机分布到这个环上,每个节点负责处理从自己开始顺 时针至下一个节点的全部哈希值域上的数据。
使用一致性哈希的方式需要将节点在一致性哈希环上的位置作为元信息加以管理。

针对一致性哈希动态增加节点后,即使原先的分布均匀也很难保证继续均匀,以及节点异常后负责承接流量的邻居节点压力过大的问题:引入虚节点。系统初始时就创建许多虚节点, 虚节点的个数一般远大于未来集群中机器的个数,将虚节点均匀分布到一致性哈希值域环上;
操作数据时,首先通过数据的哈希值在环上找到对应的虚节点,进而查找元数据找到对应的真实节点。使用虚节点改进有多个 优点。首先,一旦某个节点不可用,该节点将使得多个虚节点不可用,从而使得多个相邻的真实节 点负载失效节点的压里。

1.5 副本与数据分布

一种基本的数据副本策略是以机器为单位,若干机器互为副本,副本机器之间的数据完全相同。

更合适的做法不是以机器作为副本单位,而是将数据拆为较合理的数据段,以数据段为单位作 为副本。一旦副本分布与机器无关,数据丢失后的恢复效率将非常高。这是因为,一旦某台机器的数据丢失,其上数据段的副本将分布在整个集群的所有机器中,而不是仅在几个副本机器中,从而可以从整个集群同时拷贝恢复数据,而集群中每台数据源机器都可以以非常低的资源做拷贝。

1.6 本地化计算

移动数据不如移动计算

1.7 数据分布方式的选择

灵活组合

1.8 工程投影

2.基本副本协议

副本控制协议指按特定的协议流程控制副本数据的读写行为,使得副本满足一定的可用性和一 致性要求的分布式协议。

2.1 中心化副本控制协议

由一个中心节点协调副本数据的更新、维护副本之间的一致 性

2.2 primary-secondary协议

副本被分为两大类,其中有且仅有一个副本作为 primary 副本, 除 primary 以外的副本都作为 secondary 副本。维护 primary 副本的节点作为中心节点,中心节点负 责维护数据的更新、并发控制、协调副本的一致性。

数据更新:由primary将更新操作发给secondary。工程上,因为primary需要发给N个secondary,则受限于primary出口带宽。为了解决这个问题,有些系统(例如,GFS),使用接力的方式同步数据;

数据读取:如何实现强一致性

  • 只读primary副本:只要 primary 副本分散到集群中,即使只有 primary 副本提供读写服务, 也可以充分利用集群机器资源。
  • 由 primary 控制节点 secondary 节点的可用性:当 primary 更新某个 secondary 副本不成功 时,primary 将该 secondary 副本标记为不可用
  • 基于Quorum

primary副本的确定与切换

数据同步:secondary 副本与 primary 不一致的问题

1.网络分化,secondary落后于primary:回放 primary 上的操作日志

2.secondary上可能有脏数据:设计不产生脏数据的分布式协议;设计产生脏数据概率极低的分布式协议,一旦产生就丢弃副本;设计一些基于 undo 日志的方式从而可以删除脏数据

3.secondary新加入,完全没数据:直接拷贝 primary 副本的数据

2.3 去中心化副本控制协议

协议中所有的节点都是完全对等的,节点之间通过平等协商 达到一致

2.4 工程投影

Chubby[13]和 Zookeeper 使用了基于 Paxos 的去中心化协议选出 primary 节点,但完成 primary 节点的选举后,这两个系统都转为中心化的副本控制协议,即由 primary 节点负责同步更新操作到 secondary 节点。

3.Lease机制

3.1 基于lease的分布式cache系统

解决分布式系统中心节点负载过高的问题。

中心服务器在给各节点发送数据的同时颁发一个lease证书,保证在lease的有效期内不会修改数据的内容。

节点收到lease后把数据保存到cache,直到lease超时则删除数据。

中心服务器在修改数据时,首先阻塞所有读请求,然后等到所有lease过期后修改其值。

上述 lease 机制可以容错的关键是:服务器一旦 发出数据及 lease,无论客户端是否收到,也无论后续客户端是否宕机,也无论后续网络是否正常, 服务器只要等待 lease 超时,就可以保证对应的客户端节点不会再继续 cache 数据,从而可以放心的 修改数据而不会破坏 cache 的一致性。

针对修改数据时无法读取、修改数据时延长的问题做的优化:

1.在修改数据时,中心节点在读请求到来时发送数据但是不颁发lease证书;中心节点在读请求到来时发送过去已经发过的最长的lease证书;

2.中心节点主动通知各个持有lease的节点放弃证书。如果收到所有节点的放弃确认则可以立即修改数据。

3.2 lease机制的分析

Lease 颁发过程只依赖于网络可以单向通信

3.3 基于lease机制确定节点状态

节点 Q 可以给 primary 节点一个特殊的 lease,表示节点可以作为 primary 工作。一旦节点 Q 希 望切换新的 primary,则只需等前一个 primary 的 lease 过期,则就可以安全的颁发新的 lease 给新的 primary 节点。

3.4 lease的有效时间选择

常选择的 lease 时长是 10 秒级别

3.5 工程投影

Zookeeper 中的 secondary 节点(在 zookeeper 中称之为 follower)并不向 primary 节点(在 zookeeper 中称之为 leader)发送 lease,zookeeper 中的 secondary 节点如果发现没有 primary 节点则发起新的 paxos 选举,只要 primary 与 secondary 工作正常,新发起的选举由于缺乏多数 secondary 的参与而不会成功。与 Chubby 类似的是,Zookeeper 的 primary 节点也会向 client 颁发 lease, lease 的时间正是 zookeeper 中的 session 时间。在 Zookeeper 中,临时节点是与 session 的生命期绑定 的,当一个 client 的 session 超时,那么这个 client 创建的临时节点会被 zookeeper 自动删除。通过监 控临时节点的状态,也可以很容易的实现对节点状态的监控。

4.Quorum机制

在 Quorum 机制下,当某次更新操作 wi 一旦在所有 N 个副本中的 W 个副本上都成功,则就称 该更新操作为“成功提交的更新操作”,称对应的数据为“成功提交的数据”。

单纯使用 Quorum 机制时,若要确定最新的成功提交的版本,最多需要读取 R+ (W-R-1)=N 个副本。

基于 Quorum 机制选择 primary:在引入 quorum 机制后,常用的 primary 选择方式与读取数据的方式类似,即中心节点读取 R 个副本,选择 R 个副本中版本号最高的副本作为新的 primary。新 primary 与至少 W 个副本完成数据同步后作为新 的 primary 提供读写服务。

5.日志技术

5.1 Redo Log:

1.将更新操作的结果(例如 Set K1=1,则记录 K1=1)以追加写(append)的方式写入磁盘的日志文件

2.按更新操作修改内存中的数据

3.返回更新成功

宕机时:从头读取日志文件中的每次更新操作的结果,用这些结果修改内存中的数据。

5.2 Checkpoint

check point 技术的过程即将内存中的数据以某种易于重新加载的数据组织方式完整的 dump 到磁盘

5.3 No Undo/No Redo log

0/1 目录:0/1 目录将批量事务操作的原子性通过目录手段归结到主记录的原子切换。由于多条记录的原 子修改一般较难实现而单条记录的原子修改往往可以实现,从而降低了问题实现的难度。

6.两阶段提交协议

两阶段提交的思路比较简单,在第一阶段,协调者询问所有的参与者是否可以提交事务(请参 与者投票),所有参与者向协调者投票。在第二阶段,协调者根据所有参与者的投票结果做出是否事 务可以全局提交的决定,并通知所有的参与者执行该决定。

成功提交:需要所有参与者都发送了vote-commit。

ABORT:只要有一个参与者发送了vote-abort。

end-transaction需要所有参与者都发送了确认。

ranker001-1.png
20160225174829_89564

7.基于MVCC的分布式事务

基于 MVCC 的分布式事务的方法为:为每个事务分配一个递增的事务编号,这个编号也代表了 数据的版本号。当事务在各个节点上执行时,各个节点只需记录更新操作及事务编号,当事务在各 个节点都完成后,在全局元信息中记录本次事务的编号。在读取数据时,先读取元信息中已成功的 最大事务编号,再于各个节点上读取数据,只读取更新操作编号小于等于最后最大已成功提交事务 编号的操作,并将这些操作应用到基础数据形成读取结果。

8.Paxos协议

Paxos 协议是少数在工程实践中证实的强一致性、高可用的去中心化分布式协议。

Paxos 协议中,有一组完全对等的参与节点(称为 accpetor),这组节点各自就某一事件做出决议,如果某个决议获得了超过半数节点的同意则生效。

Paxos协议的三种角色:

  • Proposer提案者,提出议案(value)(比如修改某个value、设置当前primary为某个节点)。一轮Paxos过程最多只有一个value被批准。
  • Acceptor批准者,Proposer提出的议案必须通过半数以上(N/2+1)Acceptor同意。
  • Learner学习者,Learner学习被批准的value。通过读取各个Proposer对value的选择结果。如果某个 value 被超过半数 Proposer 通过,则 Learner 学习到了这个 value。

流程描述:

Paxos 协议一轮一轮的进行,每轮都有一个编号。每轮 Paxos 协议可能会批准一个 value,也可能无法批准一个 value。如果某一轮 Paxos 协议批准了某个 value,则以后各轮 Paxos 只能批准这个value。上述各轮协议流程组成了一个 Paxos 协议实例,即一次 Paxos 协议实例只能批准一个 value, 这也是 Paxos 协议强一致性的重要体现。

流程 2.8.1:Proposer 的流程

(准备阶段)

  1. 向所有的 Acceptor 发送消息“Prepare(b)”; 这里 b 是 Paxos 的轮数,每轮递增

  2. 如果收到任何一个 Acceptor 发送的消息“Reject(B)”,则对于这个 Proposer 而言本轮 Paxos 失败, 将轮数 b 设置为 B+1 后重新步骤 1;

(批准阶段,根据收到的 Acceptor 的消息作出不同选择)
3. 如果接收到的 Acceptor 的“Promise(b, v_i)”消息达到 N/2+1 个(N 为 Acceptor 总数,除法取整,下同);v_i 表示Acceptor 最近一次在 i 轮批准过 value v。

3.1 如果收到的“Promise(b, v)”消息中,v 都为空,Proposer 选择一个 value v,向所有 Acceptor广播 Accept(b, v);

3.2 否则,在所有收到的“Promise(b, v_i)”消息中,选择 i 最大的 value v,向所有 Acceptor 广播消息 Accept(b,v);
  1. 如果收到 Nack(B),将轮数 b 设置为 B+1 后重新步骤 1;

流程 2.8.2:Accpetor 流程

(准备阶段)
1. 接受某个 Propeser 的消息 Prepare(b)。

参数 B 是该 Acceptor 收到的最大 Paxos 轮数编号;V 是 Acceptor 批准的 value,可以为空

    1.1 如果 b>B,回复 Promise(b, V_B),设置 B=b; 表示保证不再接受编号小于 b 的提案。

    1.2 否则,回复 Reject(B)

(批准阶段)
2. 接收 Accept(b, v),

    2.1 如果 b < B, 回复 Nack(B),暗示 proposer 有一个更大编号的提案被这个 Acceptor 接收了
    2.2 否则设置 V=v。表示这个 Acceptor 批准的 Value 是 v。广播 Accepted 消息。

Paxos协议正常执行流程:
3d577129cdad44273d92c72ece8d7a15

9.CAP理论

C: Consistence 强一致性

A: Availability 系统在出现异常时可用

P: tolerance to the partition of network 对于网络分区容忍

comments powered by Disqus