分布式系统原理与范型

前言

复习了分布式系统相关的内容后,得出了一个模型,包括分布式系统的目的,分布式系统的分层结构,以及在这个结构之上的相关技术。为了矫正模型,以及更深入的了解分布式系统,学习了一下《分布式系统原理与范性》这本书。

这本书最主要的是讲技术原理,而不是实现或者细节,它先总的讲了一下分布式系统的体系结构,然后分开来讲进程、通信、命名、同步、一致性、容错、安全等几个特性,最后又将了几个分布式系统的示例。这本书有些地方读来有些费解,而有些地方让我感到叹为观止,这里对其中一些点进行梳理。

这本书可以从“分”、“合”两个概念来展开,“分”的概念指的如何来设计分布式系统的体系,它有纵向划分方式、横向划分方式,可以是分层的结构,也可以点对点的结构。“合”的概念首先是建立在通信基础之上的,没有通信谈不上“合”,“合”的概念还表现在“协作”(选举)与“竞争”(一致性)等方面。

分布式系统概念图

分布式体系结构

分布式体系样式

根据服务与通信方式,给出了4种样式:

  1. 分层体系结构

    如通信网络,请求从上往下,响应从下网上。

  2. 基于对象的体系结构

    每个对象都是一个服务,服务之间很松散。也就是微服务的样式了。

  3. 以数据为中心的体系结构

    基于web的分布式系统大多也是以数据为中心的,进程通信使用了共享的基于web的数据服务。

  4. 基于事件的体系结构

    事件传播通常与发布-订阅系统有关。

这些样式放到微服务中看,都有有点相似,分层的、基于服务的、服务之间通过发布-订阅方式的。

分布式系统-1

分布式系统-2

多种分层结构

分层结构最常用的是用户接口(view)、应用程序(controller)、数据库(model)3层的结构,同时根据客户端与服务器的差异,可以划分出一下几种结构。

多种分层结构

这个看到之后就根据很有启发,常用的是b,前端管显示,后端管逻辑与存储。其次是c,这种像在线编辑器,很多功能要拿到前端来实现,同时后端也有逻辑与存储。再次是d,这种有点像是GraphQL的感觉,也像是一些桌面程序。

分布式系统自我管理

一下这个图与K8S中的控制器很相似。

反馈控制模型

反馈控制循环有3个元素,首先,本身需要被监视组件,然后分析组件,将参考值与关注值比较,反馈分析,得到调整策略,最后是调整组件,执行调整策略。

该控制器相当于系统的决策、执行、监察3个方面。

精准的监视有些情况下很难做到,就多了一个预测组件。

MIPv6的路径优化

这个优化是防止网络流量都要流经网关而带来的瓶颈,而从网络协议层去解决。做法大概是先从网关获取到服务的真实的地址,然后客户端直接与服务通信,而绕过网关。

MIPv6

通信

书中介绍了远程过程调用、面向消息的通信(尤其是消息队列)、面向流的通信(尤其是流中不同通道的同步)、多播通信等。这里仅对其中几个点进行记录。

消息队列

这种方式有点类似于RabbitMQ,消息队列除了能缓存消息外,还增加了路由的概念。这里不深入了。

数据流与同步

数据流有几个特点:1.有先后顺序;2.分段处理;这里又提到了2种:缓存、子流。

缓存指的在传输上数据并不匀速,而在使用上对数据有匀速要求,比如播放音乐,这样就使用缓存,做一下防抖。

在多媒体系统中,一个重要的问题就是不同流,需要互相保持同步。比如电影的视频流与音频流保持同步。

需要有一个专门在少数几个流上进行读写的进程,该进程保证这些流的同步。

更进一步,这个进程提供一些接口,可以由应用程序进行控制,这样这个进程就已经是中间件了。想上图的多媒体中间件,提供了一组接口用于控制视频流和音频流,包括显示器、照相机、麦克风等设备。每个设备和每个流都有自己的高级接口,其中包括发生某些事件时通知应用程序,应用程序编写用于流同步的处理程序。

基于gossip的多播数据通信

我们在一致性协议中介绍过gossip协议,这里在简单介绍一下。

它解决的信息在多个节点传播的问题,将节点分成3类:已感染、未感染、已隔离(已感染但不会传播数据)。传播的过程有3种,可以是已传染的push给未传染的,也可以是未传染从已传染的主动去pull,再有就是2者的结合push-pull的方法。

如果节点P正好更新数据x,那么它将与任意节点Q通信,并把更新信息发送给Q。但是有可能Q被另外一个节点已更新了,这种情况下,P可能不再传播该更新信息(隔离)的概率为1/k。

同步

同步与异步是相对的概念,讲同步也是从另外一个角度讲异步,这里介绍了如GPS系统、时钟同步算法等内容,我这里关注两个算法。

分布式互斥算法

这是一种分布式锁的实现方法,包括:集中式算法与非集中算法,以及这里的分布式算法。集中式算法相当于当有节点想要访问某个节点时,都向协作节点请求,协作节点访问确定资源没有访问后,给节点反馈ok,若有则加入等待队列。

这里主要来看看分布式互斥算法,这个是paxos作者Lamport设计的算法。

当一个进程要访问一个共享资源时,它构造一个消息,其中包含它要访问的资源名、它的进程号喝当前(逻辑)时间。然后,它将该消息发送给其他的进程,也包括它自己。假设消息的传送是可靠的,没有消息丢失。

当另一个进程接收到它的请求消息时,它根据自己与消息中资源相关的状态来决定它要采取的动作,可以分成三种情况:

  • 当接受者没有访问资源,而且也不想访问它,就向发送者发送一个OK消息。
  • 当接收者已获得对资源的访问,那么它就不进行应答,而是将请求放入队里中。
  • 如果接收者想访问资源但尚未访问时,它将收到的消息的时间戳与它自己的消息时间戳进行比较。时间戳最早的那个进程获胜。如果对方的比较早,那么它就给对方发送一个OK消息,反之,它就将消息放入队列,并且不发送任何消息。

发送许可申请后,进程进程等待,知道其他所有进程偶给予许可消息位置。一旦得到许可,它就可以继续了。当它完成后,他向所用进程发送OK消息,并从队列中删除。

这个算法本身也有一些问题,如如果有1个进程发生故障,申请者将得不到资源。

这样可以通过接收者无论是否准许还是拒绝都发送应答。

算法使用的多播通信,每个进程必须自己维护组成员的列表,该列表中包括进入组的进程、离开组的进程以及崩溃的进程。该方法最适用于进程数目较少并且不改变组成员的情况。

一个进程许可另一个进程后,它在第一个进程释放许可之前,是不能授给其他进程许可的。【ps: 该进程并不能确定对方获取到最终的许可,触发申请者获取成功之后,再广播一边,有单次变成2次】

欺负选举算法

很多分布式算法都需要一个进程作为写作者,通常哪个进程充当这个角色并不重要,重要的是有这个角色。选举算法就是由节点选举出协作者的算法。

这里介绍了传统的欺负算法、环算法,以及无线系统中的选举算法,大型系统中的选举算法等。

这里简单介绍一下欺负算法。

当任何一个进程发现协作者不再响应请求时,他就发起一次选举。进程P如下过程主持一次选举:

  • P向所用编号比它大的进程发送一个Election消息
  • 如果无人响应,P获胜并成为协作者
  • 如果编号比它大的进程响应,则由响应者接管选举工作。P的工作完成。
  • 响应者继续这个循环,直到无人响应,选注协作者

任何时候,一个进程智能从编号比它小的进程得到Election消息。

一致性和复制

通过数据的复制,可以提高系统的稳定性,当一个副本破坏,系统仍然能运行,也能提高系统的吞吐量,但却存在数据的一致性问题,一旦某个副本被修改了,它必须保证所有副本都进行修改,才能保证一致性。

这里介绍了以数据为中心的一致性模型,以及以客户为中心的一致性模型(最终一致性),并介绍了了复制的管理,一致性协议。

这里来看看几个概念。

  • 持续一致性

    为了区分不一致性,这里给出了3个相互独立的偏差:副本之间的数值偏差、副本之间新旧程度的偏差、更新操作顺序的偏差,这3个构成了持续一致性的范围。

    复制的过程可以是同步数据单元,也可以同步操作。

    同步时,数据的粒度是需要掌控好的,粒度太细,效率会太低,粒度太粗,一致性会变大。

    同步操作时,需要所有的副本写操作的顺序是一致的。

  • 最终一致性

    如果在一段很长时间内没有更新操作,那么所有的副本将逐渐的成为一致的。这种形式的一致性成为最终一致性。最终一致性只要求更新操作被保证传播到所用副本。如果假设只有一小部分进程可以执行更新,那么写-写操作冲突将相对容易解决了。它允许一定程度的读不一致,但不能允许写写操作的不一致。

    本质上,以客户为中心的一致性为单一客户提供一致性保证,保证他对数据存储的访问一致性,但不为不同客户的并发访问提供一致性性保证。

    这里有几个概念:

    单调读一致性:如果一个进程读取数据项x的值,那么该进程后续读操作,不会再看到较老版本的x值。

    单调写一致性:一个进程对数据项x执行的写操作必须在该进程对x执行任何后续写操作之前完成。

    读写一致性:一个进程对数据项x执行一次写操作的结果,总是会被该进程的后续读操作所看见。

    写读一致性:同一进程对数据项x执行读操作之后的写操作,保证发生在与x读操作相同或比之更新的值上。这里指的是不同副本之间更新时,写操作在一个副本上给予此刻读的值,在另外一个副本上也应该是基于该值。

复制管理

将哪些信息传播出去,这里给出了3种可能:

  1. 只传播更新的通知

    无效化协议一般采用这种方式,只传播副本已经失效,当再访问时,先去更新该副本。这个想redis缓存更新就如此。

  2. 把数据从一个副本传送到另一个副本(同步数据)

  3. 把更新操作传播到其他副本(同步操作)

基于主备份的协议

原文中介绍了2种:远程写协议与本地写协议。这里只介绍一些远程写协议。

这指的是所有写协议都转发给单个固定的远程服务器(协作节点),读操作在本地执行,由远程服务器来进行数据同步。这其实就是读写分离的情况。

基于多数表决的协议

主备协议是需要专门的协作节点,这里的却不是,基本思想是要求客户在读写一个数据项之前,向多个服务器提出请求。一个客户要读取一个具有N个副本的文件,它必须组织一个读团体,该读团体是NR 个以上服务器的任意集合。同事修改一个文件,客户必须组织一个至少NW个服务器的写团体, NR 与NW满足以下2个条件:

  • NR + NW > N;
  • NW > N/2

容错性

容错性总体思路是通过增加冗余来掩盖故障,其实与上边的多数据副本概念相同,这里先对故障进行了划分,将故障分成了崩溃性故障、遗漏性故障(没崩溃但不响应)、定时故障、影响故障(能响应但响应不正确);然后研究了进程的恢复,恢复的前提是及时的发现故障,也包括兼容一定的故障,接着讲了一下可靠的点对点通信与多播通信两种方式下的容错问题,最后介绍分布式提交。;

在这里主要看由Lamport发明的故障系统的协定算法,以及分布式提交中的两段提交算法。

故障系统的协定

分布式协议算法的一般目标是所有的非故障进程就一个些问题达成一致,而且是在有限的步骤内达成一致。Lamport称之为拜占庭协定问题,意识在众多战争中,面临反叛将军的情况下,多个军队需要达成协定。它建设进程是同步的,消息的单播的,且按顺序进行,通信的延时是有限制的。以一个例子来描述一下这个算法。

假设有N个进程,每个进程为其他进程提供一个值Vi,目标是让每个进程构建一个长度为N的向量,这样如果进程i是无故障的,那么V[i] = Vi。否则,V[i]就是未定义的。以N=4,k=1为例。

  • 每个无故障进程i使用可靠单播给其他每个进程发送它的Vi。故障进程可以发送其他内容(可能给不同进程发送不同的值)
  • 每个进程把第一步的收到结果集合成向量形式
  • 每个进程把它集成的向量形式发送给其他进程,此时每个进程都得到了3个向量,分别来自不同的进程
  • 最后每个进程检查每个新接收向量中的第i个元素。如果值占大多数,那么该值就放置到结构向量中,如果不占就标记为unknown。闪图中可以看到,1-2-4都与Vi一致,是正确的结果。

两段提交

分布式提交的问题涉及要使一个操作被进程组中的每个成员都执行或一个成员都补执行。分布式提交通常以设立协作者的方式建立。

协议由以下2个阶段组成,每个阶段又由两步组成。

  • 协作者向所有的参与者发送一个VOTE_REQUEST消息

  • 当参与者接收到VOTE_REQUEST消息时,就向协作者返回一个VOTE_COMMIT消息,通知协作者它已经准备好本地提交事务中属于它的部分,否则就返回一个VOTE_ABOUT消息。

  • 协作者收集来自参与者的所有选票。如果所有参与者都表决提交事务,那么协作者就进行提交,向所有参与者发送一个GLOBAL_COMMIT消息。

    但如果有一个参与者要取消事务,那么协作者就取消事务,并多播一个GLOBAL_ABORT消息

  • 每个提交表决的参与者都等待协作者的最后反应。如果参与者接收到一个GLOBAL_COMMIT消息,那么它就在本地提交事务,反之接收到一个GLOBAL_ABORT,就在本地取消事务。如下图所示:

两段式中有些超时问题需要解决。

  • 协作节点在WAIT处阻塞,当等到超时没有收到每个参与者的表决,它就取消事务,发送VOTE_ABORT
  • 参与者可能在READY处阻塞,这样它可以向其他参与者询问状态,同步其他参与者的状态。
# 微服务 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×