初遇分布式系统(二)

点击量:78

《好玩又实在的分布式系统理论》的第二部分主要分析抽象的分布式系统模型并提出问题.
抽象是为了得到能充分描述系统的最少元素,能够排除干扰,分析本质的作用.

系统模型

程序在分布式系统中运行也就是,

  • 在独立节点并发运行
  • 通过网络连接节点并伴随着不确定性如信息丢失等
  • 无共享的存储器与时钟

以上这些也就意味着,

  • 信息是局部的,很有可能其余节点得到的信息是过时的
  • 独立节点存在失效的情况以及需要恢复
  • 传输的信息可能丢失也可能延迟
  • 节点点间的物理时钟是不同步的

系统模型是分布式系统实现中对于环境和基本条件的假设,包括

  • 节点的能力和可能失败的原因
  • 节点间通信的方式及其失败的原因
  • 系统特性,例如时序的假设

一个健壮的系统应该有最弱的假设:可以在这样一个系统中实现面向不同环境的算法并良好运行.下面主要针对系统模型中的各个部分进行分析.

节点

节点作为计算和存储的关键部件,主要提供计算能力、存储能力以及非必须精确的节点本地时钟.

关于节点的故障模型,其中,崩溃-恢复模型是其中一个假设模型,假设节点只会在崩溃宕机的时候失效(不再处理任何信息),不存在其他失效的情况,在这种情况下,只需要恢复该节点即可.还有另外一类假设,即是节点任何错误的行为都算作失效,例如拜占庭问题(会一直传递错误信息).

网络连接

时序

由于物理距离的不同及信息传输速度有限导致节点看到的可能存在不一致

关于时序的模型主要有两类:

  • 同步系统
    进程在lock-step内运行,有一个已知的信息传输时间开销上界,每个节点的时钟都是精确同步的
  • 异步系统
    没有时间保证,每个进程都各自运行,没有消息传输上界,也没有有效的时钟信息

一致性问题

关于多节点达成一致的形式化定义为:

  • 协定:每个正常的节点必在同一个值上达成一致
  • 完整:每个正常的节点最多只能提出一个值,
  • 终止:所有节点都达成共识
  • 有效:如果所有正常的节点都提出相同的值,那么这个值就是有效的

一致性问题是许多商业分布式系统肿瘤的核心问题,解决一致性问题能够帮助解决一些更加深远的问题,如原子性广播?和原子性提交.

两个不可能的结果

一个是FLP,与设计分布式系统相关,更偏学术意义,一个是CAP,与分布式实践相关.

FLP

FLP的名字以这个理论的提出者组成(Fischer, Lynch and Patterson),重点考察异步系统下的一致性问题,它假设节点只会因为宕机崩溃而失效并且网络是可靠的,当然没有信息传输时间上界的假设.

在以上假设下,FLP叙述为“在可靠网络的异步系统中,即便只存在一个节点失效,也不可能存在一个解决一致性问题的确定算法”,其理论上证明了不存在异步分布式系统设计在任意场景下都能实现共识的算法.
这里是FLP的简要证明.借鉴其他资料上的一个例子:

三个人在不同房间,进行投票(投票结果是 0 或者 1).三个人彼此可以通过电话进行沟通,但经常会有人时不时地睡着.比如某个时候,A 投票 0,B 投票 1,C 收到了两人的投票,然后 C 睡着了.A 和 B 则永远无法在有限时间内获知最终的结果.如果可以重新投票,则类似情形每次在取得结果前发生.

当然了,在实际中,这是非常极端的情况,发生的概率没有那么大.Paxos/Raft算法就是在实际中能够使用的一致性保证算法.

CAP也是类似的理论,但是在假设上做了改变(不是节点错误而是网络错误)

CAP

这是一个非常有效在系统设计中做出权衡的方法.这个理论中主要包含三个部分:

  • 一致性(Consistency):所有节点在同一时间看到相同的数据值.
  • 可靠性(Availability):失效节点能够被恢复并继续运行
  • 分区容错性(Partition tolerance):在节点间的网络通信无法保障的时候系统依然能够正常运行.

而三者不能同时满足,最多只能满足其二.由此得到了三种类型的系统,如下图所示.

  • CA:严格的仲裁协议,例如两阶段提交.
  • CP:多数裁定协议,这种情况少数分区不可用,例如Paxos.
  • AP:冲突消解协议,例如Dynamo.

CA和CP系统设计都提供了强一致性,但是CA不能接受任何节点错误,CP系统能够在2f+1个节点中容忍f个节点的非拜占庭式失效.CA系统不能区分节点失效和网络错误,因此会停止接受写入,避免发生分歧(多份拷贝)

一致性模型

由于在分布式系统中,往往都有分区存储的特点,因此产生了一致性的问题.其意义就在于,不同节点之间由于读写之间的交错可能出现一系列的问题.一般,分布式系统中一致性保证可以分为强一致性与弱一致性.

下面为了方便一致性的理解,首先对于分布式系统中的事件、时间和因果进行描述.其中,事件的发生不是一瞬间完成的,有一个时间段,由此,多个事件之间可能会存在重叠.

由于物理上的误差,理论上企图想根据物理时钟来分辨事件发生的先后顺序在实际中,是不可能的

强一致性

  • Linearizable consistency(线性一致性)
    有时又被称作原子一致性,其表述为基于全局的统一时钟,任何一个节点的读操作都将返回最近的写的值.

  • Sequential consistency(顺序一致性)

其描述包含两个部分,一个是整个程序的指令执行在所有进程上看是一致有序的,第二个是每个进程的内部指令是按照程序规定的顺序执行的.

弱一致性

  • Client-centric consistency models
  • Causal consistency: strongest model available
  • Eventual consistency models

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行许可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注