（计算机应用技术专业论文）高可用系统中组通信的研究与实现.pdf

中国科学技术大学硕士学位论文 摘要 摘要 在分布式系统中，成员之间通过信息交换共同完成某个特定的功能，这些成 员的集合称为组。组通信是指组中某个成员将消息发送到组中所有成员的操作， 为一对多的数据传输提供了一种有效方法。因此，组通信已经成为构建分布式系 统的重要基础。我们所实现的组通信系统是构建高可用平台的基础。所谓高可用 性是指是在特殊的场合下，应用程序要求连续运行，在发生故障时能自动切换到 其他节点继续提供服务。高可用平台提供了实现服务高可用性的统一接口，保证 通过使用高可用接口编写的应用能够自动的实现高可用的功能，使得应用能够将 精力集中在实现业务逻辑和功能服务上，从而提高了高可用应用的开发速度，降 低开发成本和维护成本。 本文根据高可用平台运行的环境，设计和实现了在局域网和广域网环境下的 组通信系统，保证了组中消息通信的可靠性、有序性和自适应性，并已经应用于 华为高可用刀片式服务器中。研究的具体内容如下： 1 ) 分析不同应用环境下典型的组通信系统模型，对这些己有的系统模型进 行概括和抽象，提出了实现组通信模型的关键技术。 2 ) 在局域网环境下，针对当前许多应用要求通信组中有大量相互协作的成 员，且其个数是动态变化的，我们设计并实现了一种分级可扩放全序组 通信协议，并进行了协议分析和性能分析。该协议通过令牌传递来完成 消息的有序递送：通过消息缓存重发的方式来完成消息的可靠递送；采 用分级的方式来管理组，将组划分为全局组和本地组。为了减少组成员 加入或离开时处理过程所占用的时间，采用了两种方法：尽量减少此过 程中的消息交换次数和尽量减小此过程中所交换的成员改变消息的大 小。 3 ) 在广域网环境下，针对当前的基于p 2 p 的组通信不能适用于高可用系统 的现状，我们设计并实现了一种基于p 2 p 的可靠全序组通信协议，并进 行有序性和可靠性分析。该协议将相似性原则与物理网络拓扑相结合， 提出了节点簇的概念，实现了覆盖网络的快速高效构建；在覆盖网络的 基础上，通过核心多播环的方式实现消息的全序递送，避免了单多播树 中汇聚点的单点故障；采用多播树重构和消息缓存重发机制来实现消息 的可靠递送。 关键词：高可用；组通信；全序；可靠性；可扩展性 中国科学技术大学硕士学位论文 a b s t r a c t a b s t r a c t i np a r a l l e la n dd i s t r i b u t e ds y s t e m ag r e a td e a lo fm e m b e r si nag r o u pi s c o o p e r a t i n gt oa c h i e v es o m ef u n c t i o n s g r o u pc o m m u n i c a t i o nt e c h n o l o g yi s a n e f f e c t i v ew a yf o ro n e t o m a n yd a t at r a n s m i s s i o n t h e r e f o r eg r o u pc o m m u n i c a t i o nh a s b e c o m ea ni m p o r t a n tb a s i st ob u i l dp a r a l l e la n dd i s t r i b u t e ds y s t e m i nt h i st h e s i s g r o u pc o m m u n i c a t i o ni su s e dt ob u i l dh i g ha v a i l a b i l i t yp l a t f o r m h i g ha v a i l a b i l i t y p l a t f o r mp r o v i d e sas e r i a l o fp r o g r a m m i n gi n t e r f a c e st oi m p l e m e n ts e r v i c eh i g h a v a i l a b i l i t y a n ds o f t w a r ew h i c hd e v e l o p e dw i t ht h e s ep r o g r a m m i n gi n t e r f a c e sc a n a c h i e v eh i g ha v a i l a b i l i t ya u t o m a t i c a l l y i tm a k e sa p p l i c a t i o no n l yf o c u so nb u s i n e s s l o g i ca n df u n c t i o ns e r v i c e ，i m p r o v e st h ed e v e l o p m e n ts p e e do fh i g ha v a i l a b i l i t y s e r v i c e ，a n dr e d u c e st h ec o s t so fd e v e l o p m e n ta n dm a i n t e n a n c e a c c o r d i n g t od i f f e r e n te n v i r o n m e n t s ，w e d e s i g n a n d i m p l e m e n tg r o u p c o m m u n i c a t i o np r o t o c o lf o rl a na n d r a n i tp r o v i d e sr e l i a b i l i t y , m e s s a g eo r d e ra n d s c a l a b i l i t yi ng r o u p t h em a i nw o r k so ft h i st h e s i sa r ei nt h ef o l l o w i n g ： 1 、w ea n a l y z e dt h ee x i s t i n gc l a s s i cg r o u pc o m m u n i c a t i o nm o d e l sf o rd i f f e r e n t e n v i r o n m e n t s b a s e do nt h e s em o d e l s ，w ep r o p o s e ds o m ek e yt e c h n o l o g i e st o i m p l e m e n tg r o u pc o m m u n i c a t i o n 2 ) i nl a n ，w ed e s i g na n di m p l e m e n tap r o t o c o l ，c a l l e d “ah i e r a r c h i c a lg r o u p c o m m u n i c a t i o np r o t o c o lf o rs e a l a b l et o t a lo r d e r i n g ”t h eh i e r a r c h i c a l g r o u pi sd e s i g n e d t h i sp r o t o c o ls u p p o r t st o t a lo r d e rm e s s a g ed e l i v e r ya n d d y n a m i c a l l yc h a n g i n go ft h em e m b e r s h i po fag r o u pb yt o k e np a s s i n g i t s e p a r a t e sg l o b a lg r o u pf r o ml o c a lg r o u p s i no r d e rt or e d u c ec o m m u n i c a t i o n o v e r h e a d sa n di m p r o v er e l i a b i l i t y , t h ep r o t o c o ld e c r e a s e st h en u m b e ro f m e s s a g e se x c h a n g e dd u r i n gt h em e m b e r s h i pc h a n g i n go fag r o u p i ti s p r o v e dt h a tt h ep r o p o s e dp r o t o c o l i sr e l i a b l ea n ds c a l a b l e 3 )i nw a n ，w ed e s i g na n di m p l e m e n tan o v e lp r o t o c o l ，c a l l e d “ap 2 p b a s e d r e l i a b l eg r o u pc o m m u n i c a t i o ns y s t e mf o rt o t a lo r d e r i n g ”c o m b i n i n g c o m p a r a b i l i t yw i t hp h y s i c a l n e t w o r kt o p o l o g y , w ep r o p o s en o d ec l u s t e r a b s t r a c t ，a n di m p l e m e n tt h er a p i dc o n s t r u c t i o no fo v e r l a yn e t w o r k b a s e do n o v e r l a yn e t w o r k i ts u p p o r t st o t a lo r d e rm e s s a g ed e l i v e r yb yc o r em u l t i c a s t r i n g ，w h i c ha v o i d ss i n g l ef a u l tw h i c hi su s u a l l ym e ti ns i n g l em u l t i c a s tt r e e i t a l s os u p p o r t sr e l i a b l em e s s a g ed e l i v e r yb ym u l t i c a s tt r e er e b u i l d i n g k e y w o r d s ：h i g ha v a i l a b i l i t y ；g r o u pc o m m u n i c a t i o n ；t o t a lo r d e r ；r e l i a b i l i t y ； s c a l a b i l i t y l i 中国科学技术大学硕士学位论文图目录 图目录 图卜l 单播通信和广播通信示意图1 图卜2 组播通信示意图2 图卜3 组播通信的四个状态3 图卜4 组播通信f i f o 序和因果序意图5 图卜5t o t a lo r d e r 示意图7 图卜6 组通信中单组和多组示意图8 图卜7h o r u s 系统中的协议栈1 2 图2 一l 全序消息发送和递送示意图1 9 图3 一1 分级组2 5 图3 2 分级组的体系结构2 6 图3 3 消息递送过程演示2 7 图3 4 本协议中消息处理示意图2 7 图3 5r e g u l a rt o k e n 的处理流程2 8 图3 - 6 主动监测模型的工作原理一2 9 图3 7 主动监测模型中消息交换示意图2 9 图3 8 被动监测模型中h e a r t b e a t 消息交换示意图2 9 图3 9 普通成员的失效探测服务3 0 图3 一l o 代表成员的失效探测服务3l 图3 - 1l 成员关系服务示意图3 2 图3 一1 2 成员加入的处理流程3 2 图3 - 1 3 消息发送算法3 3 图3 - 1 4 消息接收算法3 4 图3 1 5 全序消息递送3 4 图3 一1 6 虚拟同步服务提供的消息保证3 5 图3 - 1 7 可靠性随成员个数变化图3 7 图3 一1 8 可靠性随成员失效率变化图3 8 图4 - 1 节点簇生成算法一4 2 图4 - 2 路有算法4 3 图4 - 3 消息递送算法4 5 图4 4 消息接收算法4 5 图4 - 5 消息转发算法4 6 中国科学技术大学硕士学位论文 表目录 表目录 表2 - 1 几个典型的关于组播的r f c 文件 表3 - 1 基于环的分级结构的可靠性概率 表4 - 1e p p 协议中的节点结构 4 弘钉 中国科学技术大学硕士学位论文 第1 章绪论 第1 章绪论 本章在概述了组通信技术给高可用服务带来的发展契机和相应挑战的基础 上，说明了随着网络服务要求的不断增加，新一代面向分布式、大范围、大规模 的应用是组通信技术的发展趋势，指出信息交换的可靠性和安全性、组成员的可 扩展性、通信的效率、消息递送的有序性将成为组通信技术发展的关键技术。在 进一步简要分析了组通信技术的研究背景、研究现状和基于可靠有序组通信基础 上的高可用服务之后，介绍了本文的研究内容，并说明论文的组织结构。 1 1 研究背景 在计算机网络中，传统的单播通信( u n i c a s t ) 和广播通信( b r o a d c a s t ) 是两 种主要的通信方式。单播通信允许单个网络节点一次向同一网络上的另一节点发 送数据；而广播通信则允许某个网络节点将一个数据不加区别的一次性发送给网 上的所有节点。图1 - 1 给出了传统的单播通信和广播通信的示意图。 ( a ) 单播通信 3 ( b ) 广播通信 图卜1 单播通信和广播通信示意图 但是近年来，随着通信技术与计算机技术的飞速发展，和用户对于计算机性 能要求的不断增加，以往那种单机形式的服务已经不能满足用户的需求，因此分 布式系统得到了越来越广泛的应用。通常，分布式系统由若干个实体( 如进程、 a g e n t 等) 组成，每个实体分别运行在不同的节点上，实体之间通过消息传递进 行通信。其基本的通信通常涉及两个实体，分别称为客户和服务器：客户端发出 请求，服务器端响应请求。然而在很多分布式应用中，通信不仅仅涉及两个实体， 而是涉及多个实体，其要求将某个信息传递给分布式系统中的所有实体。例如， 在分布式检查点服务中，为了提高系统的可靠性和容错能力，通常将重要的数据 备份成多份，分别放置在不同的节点上；检查点服务接受来自不同用户的请求， 并对请求按一定的顺序排序，使分布式系统中的所有实体都按照相同的顺序对来 自不同用户的请求进行处理，以保持数据的一致性，当某个实体发生故障时其他 实体仍可以继续工作，从而提高了系统的可靠性。这种涉及多个实体的通信是非 常复杂的，如一个实体通常要将一个操作或消息可靠的广播给其他实体，以使得 各个实体相互了解彼此的意愿和动作，以保证“你所见即我所见”的特性；同时 中国科学技术大学硕士学位论文第1 章绪论 个实体还要接受来自多个实体的应答信息，并采用相应的策略对这些应答进行 处理，以得到正确的结果。这就需要一种一对多( o n e t o m a n y ) 通信模式，以 支持多个实体之间的消息传递。 若采用传统的单播技术，向分布式系统中每个实体发送一次该消息，则会造 成对同一消息的重复发送，降低了消息的发送效率，浪费了处理器d e 时间，并 消耗了大量的网络带宽，因此传统的单播通信并不是最佳的解决方案。若采用广 播通信，每个节点将所接收到的消息发送给所有与其相连的主机，又会在网络中 造成大量冗余的网络报文分组，增加了网络的传输负担，严重地影响网络的传输 效率，且广播技术有一个最大的缺点就是其基本不能在i n t e r n e t 上传输，因为 i n t e r n e t 对于广播通信是不友好的。因此，传统的单播通信和广播通信都无法高 效的解决此类一对多的通信问题。 而组通信( g r o u pc o m m u n i c a t i o n ) 正是针对此类问题所提出的一种新的、高 效的网络通信模型，它是面向“组”的介于单播和广播通信之间的一种数据传送 方式。组中每个成员之间都是平等关系，每个组成员都可以将消息发送给组中其 他的所有成员，实现了从一个发送者向多个接收者传递消息。因此，组通信是构 建分布式系统的基础。图卜2 给出了组通信的示意图。 组播通信 图卜2 组播通信示意图 如图卜2 所示，i p 地址为1 9 2 1 6 8 0 2 、1 9 2 1 6 8 0 3 、1 9 2 1 6 8 0 4 、1 9 2 1 6 8 0 5 的节点构成一个组，而1 9 2 1 6 8 0 1 的节点并不是组成员。从图1 - 2 中可以看出， 在组通信模式中用户通过一个发送操作就可以将一条消息发送给一个服务器组 中的所有成员，从而方便了用户应用与服务器组之间的消息交换。同时可以看出 组通信不会将信息发送给不需要该信息的节点。 1 2 组通信简介 1 2 1 组通信基本概念 组这一抽象概念最初是在v k e m e l 【1 系统中作为一种方便的地址引用机制 而引入的，后来被逐步扩展到多个支持基于组的应用系统中，如i s i s 【2 1 、t o t e m 3 1 1 4 1 、t r a n s i s 5 】以及a m o e b a 6 1 【7 1 等系统。组通信的主要思想是将分布式系统中处 于不同节点上的多个实体( 如进程、对象、a g e n t 等) 组织成一个逻辑实体 组【8 】 9 1 【1 0 1 ，分布在不同节点上每个实体是组的一个成员，组成员之间可以高效 2 中国科学技术大学硕士学位论文 第1 章绪论 简洁实现一对多的发送和接收数据。所谓组通信是指把同一数据块( 报文、分组 或文件等) 从一台计算机传送到一个由若干台计算机组成的集合中每个成员的过 程。因此，组通信为组成员之间的通信提供了各种通信原语，并且这些原语大部 分都提供各种消息顺序语义的保证，使得组成员可以按照某种消息顺序语义进行 通信。 在组通信系统中，一个组被作为一个实体来看待，一个组构成了一个逻辑地 址单元，我们将其称为组的标示。组通信系统中的每个组都有一个唯一的组的标 示，利用组的标示信息可以将一条消息发送给组中的所有成员，而不需要知道组 成员的个数、状态及各个成员的位置等信息。我们将一条发送给组中所有成员的 消息称为组播消息。一个实体( 如进程、对象、a g e n t 等) 将一条消息发送给组 中所有成员的过程称为组播通信( g r o u pc o m m u n i c a t i o n 或者m u l t i c a s t c o m m u n i c a t i o n ) 。在组播通信中，消息的发送者既可以是同组内的成员，也可 以是来自组外的非组成员，我们将该非组成员称为组的用户。因此，组播通信是 组的用户与一个组之间以及组内部成员之间消息交换的基础，它为用户与一个组 之间以及组内成员之间的通信提供支持，将一个用户或者一个组成员发送的消息 组播给组内的所有成员。 1 2 2 组播通信 组播通信中消息的发送过程为：当一个用户提出组播消息的请求时，用户首 先将消息发送给组通信系统，然后组通信系统根据用户要求的不同，给消息添加 消息顺序，最后组通信系统使用网络传输协议将消息发送到组中的所有成员。组 播消息的接受过程为：首先组通信系统从传输协议层接收消息，然后将接收到的 消息进行缓存和排序，当满足规定的有序性要求的所有消息全部到达时，将该消 息集合递送给上层的用户。由此可以看出，一个组播过程开始于某个组成员接收 组播服务请求，结束于组中的所有成员都将该信息传递给上层用户。 图1 - 3 组播通信的四个状态 因此，我们必须提出了四个概念来表示多播过程中的四个状态消息组播 ( m u l t i c a s t i n g ) 、消息发送( s e n d i n g ) 、消息接收( r e c e i v i n g ) 矛h 消息递：i 差( d e l i v e r y ) 。 消息组播( m e s s a g em u l t i c a s t i n g ) ，是指上层用户将要组播的消息发送给组通信系 统，并由组通信系统来完成消息的缓存和定序。消息发j 差( m e s s a g es e n d i n g ) ，是 指组通信系统将消息发送给底层网络协议( 一般为传输层协议) 。消息接收 中国科学技术大学硕士学位论文 第i 章绪论 ( m e s s a g er e c e i v i n g ) ，是指组通信系统从底层网络协议接收数据包，并缓存和定 序消息。而消息递送( m e s s a g ed e l i v e r y ) ，指的是组通信系统向上层用户( 也称为 目的地) 传递消息，它们之间的关系如图卜3 所示。 1 2 3 消息递送 消息递送( m e s s a g ed e l i v e r y ) 定义了一个进程必须递送哪些消息和递送过程 中必须坚持的基本的一致性条件。按照消息递送的服务质量的不同，消息递送 ( m e s s a g ed e l i v e r y ) 可以分为两类： 1 a g r e e dd e l i v e r y t 3 】：递送给组中每个成员的消息集合是相同的，且每个 消息按照相同的协商好的次序递送给通信组中的所有组成员。通信组内 的每个组成员在同一时刻并不需要递送同一个消息，只需要将消息按照 相同的顺序递送给应用程序即可，即组成员递送消息的时机是允许各不 相同的。例如：成员p l 可能早就收到了消息m l ，t 时刻时可能正在接受 消息m 2 ，而成员p 2 可能在t 时刻刚刚接受消息m i ，但是所有的组播消 息都必须按照相同的顺序递送给组中的每个成员。也就是说，在某个时 刻，a g r e e dd e l i v e r y 并不要求组中某个成员必须知道其他成员是否递送 了某个消息。 2 s a f ed e l i v e r y 列：在a g r e e dd e l i v e r y 的基础上，要求组中的所有成员必 。须清楚地知道其他成员当前已经递送了的消息的序号。例如：进程p l 可 能早就收到了消息m l ，t 时刻时可能正在接受消息m 2 ，而成员p 2 可能在 t 时刻刚刚接受消息m l ，于是在成员p 2 收到并递送消息之前m i ，成员 p l 也不能递送消息m 】。这就保证了不仅所有的组播消息都必须按照相同 的顺序递送给组中的每个成员，而且每个成员在递送完毕某条消息之后， 就可以断定其他成员也递送了该消息。 由定义可以看出s a f ed e l i v e r y 比a g r e e dd e l i v e r y 的递送要求更加严格， a g r e e dd e l i v e r y 仅仅是在组中的成员关系没有发生变化时，所有的消息递送都是 按照消息发送时确定的消息序号来对消息进行排序，但是却不能保证在组成员关 系发生变化时，消息的递送顺序仍然是一致的：而s a f ed e l i v e r y 不仅保证在组的 成员关系没有发生变化时，消息的递送顺序是一致的，而且可以保证在组中的成 员关系发生变化时，保证在同一新组中的成员对于旧组中发送的消息仍然按照一 致的消息顺序进行递送，且保证新组中发送的消息要在旧组所发送的消息之后递 送。 当某个组成员按照a g r e e dd e l i v e r y 递送某条消息时，则该成员已经递送了该 消息之前的所有消息。而且，该消息在所有的组成员递送消息集合中的相对顺序 都是一致的。 当某个组成员按照s a f ed e l i v e r y 递送某条消息时，除了要满足a g r e e d d e l i v e r y 之外，还必须知道通信组中其他成员是否已经收到并递送了该消息。一 条消息是否可以按照s a f ed e l i v e r y 来递送，主要是基于从其他成员捎带来的确认 消息。一旦组成员确认了某个消息已经被其他成员接收并递送了，则立即递送该 消息除非进程失效。因为网络的不稳定性，特别是网络容易发生分割，所以不能 在两个组中要求消息按照s a f ed e l i v e r y 的方式进行递送。然而，在同一个组中的 成员却知道组中的其他成员是否接收并递送了该消息。 4 中国科学技术大学硕士学位论文 第1 章绪论 1 2 4 消息序 对于大部分分布式应用程序来说，消息顺序的缺少是不能令人满意的。不同 的应用要求系统中的组成员按相应的顺序接受和处理来自用户或组成员的消息， 以保证分布式系统的正确运行。因此，按照期望的消息顺序向应用进程递送消息 是组通信中一个非常重要的特性，同时消息顺序还决定了分布式应用程序的功 能、实现方案和性能。例如：在一个核电站里，表示安全条件的威胁事件和表示 控制单元的动作事件，被系统中所有的进程以同样的顺序接收到是至关重要的。 然而，在一个动态的分布式环境中，由于网络延迟、资源竞争等原因，不同的组 成员可能会按照不同的顺序接收到发送到一个组的消息。因此，要保证系统的正 确运行，组通信必须解决消息顺序的问题。 通常的，在组通信中有几种不同程度的信息排序。按照顺序要求的程度由弱 到强依次是无序( a r b i t r a r yo r d e r ) t j 、f i f o 序( f i f oo r d e r ) 、因果序( c a u s a l o r d e r ) 1 1j 和全序( t o t a lo r d e r ) t 1 2 1 。图1 - 4 显示了各种消息序的示意图。 卜 图1 - 4 组播通信f i f o 序和因果序意图 1 a r b i t r a r yo r d e r 消息以任意的次序传递给目的地。即先发送的消息有可能比后发送的消息后 到。 2 f i f oo r d e r 如果一个成员发送消息m l 先于消息m 2 ，那么组中所有正确的进程必须在递 送消息m 2 之前递送消息m i 。组通信的f i f o 消息序通常是依赖于底层传输协议 来支持，其基本的思想是使用序列号来表示消息源成员处的信息序号，然后所有 组成员在接受到消息之后，按照信息序号大小顺序将信息地送给上层应用。 由定义可以看出，f i f o 序是一个组中的所有成员都按照相同的顺序接收处 理来自同一个用户或者组成员的消息。对于每个成员来说的，其排序的消息对象 中国科学技术大学硕士学位论文 第l 章绪论 是由同一个组成员发送的，根据组成员发送消息顺序的先后，向上层应用递送消 息。f i f o 通信是组通信中一种最基本的通信方式，它为组通信提供最基本的顺 序语义保证，它是其他通行方式的基础。 在图卜4 中，消息f l 和消息f 2 都由成员p l 发送，其中消息f l 在消息f 2 之 前发送，因此，在每个成员上，消息f l 的递送顺序都在消息f 2 之前。而消息f 3 是成员p 3 发送的，因此，消息f 3 与消息f l 和消息f 2 之间的先序关系是不确定 的，其可以在消息f l 和消息f 2 之前也可以在消息f i 和消息f 2 之后。 3 c a u s a lo r d e r 在给定组和组中的所有成员时，c a u s a lo r d e r 的定义是自反的传递的闭包。 消息m 2 因果地依赖于消息m l 当且仅当满足以下四个条件： 1 )初始化组播组的成员改变消息先于所有在组上发送的消息。 2 )对于组成员p 递送的消息m i 和产生的消息m 2 来说，若消息m i 的递送 先于消息m 2 的产生，则称为消息m l 先于消息m 2 。 3 )对于组成员p 产生的消息m l 和消息m 2 来说，若消息m l 的产生先于消 息m 2 的产生，则称为消息m l 先于消息m 2 。 4 )所有组中正常递送的消息都先于标志着组发生改变的成员改变消息之 ，1 上 刚o c a u s a lo r d e r 隐含了f i f oo r d e r ，因为同一成员的任何两次组播通信操作之 间都被c a u s a lo r d e r 关系联系起来。注意f i f oo r d e r 和c a u s a lo r d e r 都是偏序： 一般地，不是所有的消息都由同一成员发送；因此，不同成员之间的组播操作有 可能是c a u s a lo r d e r ，也有可能不是c a u s a lo r d e r 。不存在c a u s a lo r d e r 关系的组 播操作之间是并发的。 c a u s a lo r d e r 的定义允许组成员在发生网络分割的时候，仍然按照消息产生 的c a u s a lo r d e r 来递送消息；也允许在网络分割后形成的新组中，组成员不需要 递送从本组中离开的组成员所发送的消息。网络分割可能会导致网络的不同部分 和不同拓扑之间递送的消息集合不同。而且，在新组中的组成员不必递送其他组 中的组成员所发送的最后几个消息。然而，每个消息按照时间戳递送，因此任意 两个消息之间的相对关系可以由组成员识别出来。 在大多数应用中，仅仅当一个消息的输出可能因果关系的( c a u s a l l y ) 影响另一 个信息时，才需要对这两个消息的传递进行排序。在以上两个消息因果关系的定 义中，是通过消息发送和接收的时间来定义的因果关系的，而不是根据消息的语 义。它反映的是潜在的因果。i 生( p o t e n t i a lc a u s a l i t y ) ，而不是实际上的因果性( a c t u a l c a u s a l i t y ) 。两个消息如果有潜在的因果关系，也可能实际上相互没有任何关系。 如果两个消息在语义上一个因果依赖于另一个，那么它们就说是有实际的因果关 玄 ，j 、0 消息传递时仅仅保留实际的因果序，可以获得较高的并发性，可以减少消息 的瓶颈。这是因为一个消息的传递仅仅会被那些和它有实际因果关系的消息所阻 塞。然而，对于系统而言要分析应用层信息实际的因果关系时非常困难的。有些 系统允许用户在组播信息时确定因果地依赖信息，这增加了程序的复杂性。大多 数保证因果序的组播协议仅仅简单的通过时间戳来保证潜在的因果序。 在图1 - 4 中，消息c l 和消息c 2 都由成员p l 发送，必然满足f i f o 序，对于 同一个成员来说满足f i f o 序就等价于满足因果序。而消息c 3 仅仅与c l 有因果 序关系，因此在图中其始终在c l 之后接受。 4 t o t a lo r d e r 6 中国科学技术大学硕士学位论文 第l 章绪论 全序的定义可以有两种，分别可以从l a m p o r t 的“一 h a p p e n s b e f o r e ”关系来 定义全序；也可以在消息因果序的基础上，加上一些限制性的条件，从而实现消 息的全序递送。 l a m p o r t 定义了一种关系叫做“一 h a p p e n s b e f o r e ”。表达式“a - b ”读做“a h a p p e n sb e f o r eb ”，意思是在组中的所有进程中事件a 先发生，然后事件b 发生。 这种h a p p e n s b e f o r e 关系可以由以下两种情况看出来： 1 ) 如果事件a 和事件b 是同一个进程里的两个事件，并且a 在b 之前发生， 那么a - ) b 成立。 2 )如果a 是一个进程发送某一信息的事件，b 是另一个进程接收该信息的 事件，那么a 一 b 也成立。一条信息不可能在它被发送之前接收到，也 不可能是它被发送的同一时刻接收到。 h a p p e n s b e f o r e 关系具有传递性，即如果a 一 b 和b 一 c 同时成立，那么a 一 c 。 如果两个事件x 和y ，发生在两个不相互交换信息的进程里( 也不间接通过第三 方通信) ，那么x 一 y 不成立，而且y 一 x 也不成立。这样的事件叫做并发的 ( c o n c u r r e n t ) ，它意味着没有办法说明( 也没有必要) 这两个事件哪一个先发生。 按照l a m p o r t 关于两个事件“一 h a p p e n s b e f o r e ”关系的定义，可以确定两 个消息m l 和m 2 的先序关系：a ) 如果两个进程发送消息m l 先于消息m 2 ，那么 m 厂 m 2 ：b ) 如果进程接收消息m l 先于发送m 2 ，那么m 广 m 2 ：c ) 如果m 广) m 2 并 且m 2 - ) m 3 ，那么m 广 m 3 。根据上述先序关系定义，我们可以定义全序。所谓组 通信中的全序消息递送，就必须满足以下两个条件：a ) 存在“一 h a p p e n s b e f o r e ” 关系的消息要按照相同的“一 h a p p e n s b e f o r e ”关系的顺序向组中的所有接收者 进行递送：b ) 并发的信息必须按照相同的相对次序向组中的所有接收者进行递 送。 p l 图卜5t o t a lo r d e r 示意图 图卜5 中有三个进程p l ，p 2 和p 3 和三条信息t l ，t 2 和t 3 。从图中可以看出 消息t l 按照因果序先于消息t 2 和消息t 3 ，而消息t 2 和消息t 3 之间却没有因果 序的要求，因此消息t 2 和消息t 3 相互并发的。全序要求这三个进程必须：a ) 在消 息t 2 ，消息t 3 之前接收消息t l ：b ) 以相同的次序接收消息t 2 和消息t 3 ，但是至 于到底谁在前谁在后无关紧要。在这个例子中，因为进程p 和p 2 在接收t 2 之前 接收了t 3 ，所以p 2 只有当向应用进程递送了消息t 3 才能够递送消息t 2 。 从图卜5 中我们可以看出，全序消息的递送与他们被发送的物理时间的顺序 相反。事实上，全序的定义允许消息的递送可以随机排序，条件是该顺序在不同 中国科学技术大学硕士学位论文 第1 章绪论 的进程中是一致的。因为全排序不必同时也是f i f o 或者因果排序，我们把f i f o 一 全的混合排序定义为消息既遵守f i f o 也遵守全排序的排序。同样的，在因果- 全排序下，消息递送既遵守因果也遵守全排序。 同样的，我们也可以在因果序消息递送的基础上增加一些限制来定义全序消 息递送，a ) 如果两个信息存在因果关系，那么它们必须按照因果序被组中的所有 接受者接收：b ) 女l l 果两个信息没有因果关系( 它们是并发的) ，那么它们必须要 被组中所有接受者按照相同的相对次序接收到。这种顺序特征也叫做 c a u s a l t o t a l 顺序。 全序通信获得了一致性视 蛩( a g r e e dv i e w ) 的性质：组中的所有进程都以相同 的次序来接受相同的消息集合，因此在收到某个消息时，进程所处的状态都是一 致的，而收到该消息后所作的操作也实现相同的。该性质对于分布式事件来说， 就好像它们是在一个单处理器系统里一样，有很多应用在通信中都需要这种类型 的排序。 消息有序性处理的基本思路是这样的，组通信系统不能从网络中接收到一个 数据包，解开( 使网络层数据包变成应用层可识别的消息) 后就立即提交给应用 层，必须对其进行缓存排序处理，达到所要求的有序性之后再提交。这也就是在 群组通信系统中我们为什么要区别信息的接收( r e c e i v i n g ) 和信息的传递 ( d e l i v e r y ) 两个概念的原因( 接收和传递详细差别见1 2 3 节) 全序的范围可能是在单个的组里面，也可能是在多个组( 即系统范围内) 。对 于单个的组排序，发送给同一组的消息被组中所有的成员按照相同的次序接收 到，如图卜6 ( 左) 。这种单个的组的全序不需要考虑组成员的重叠。对于系统范 围内的全序，整个系统中所有的按照相同的次序接收相同的消息。那就是说，当 两个组相互重叠的时候，传递给两个组共同成员的消息要以相同的次序传递。如 图卜6 ( 右) 所示。 s l s 2 g 1 s s 2 图1 - 6 组通信中单组和多组示意图 5 e x t e n s i v ev i r t u a ls y n c h r o n y 扩展虚拟同步( e x t e n s i v ev i r t u a ls y n c h r o n y ) 也是t o t a lo r d e r 的一种，通常 的t o t a lo r d e r 的定义和实现中仅仅假设组中的成员关系并不会发生变化，都没 有考虑节点失效、链路故障和网络分割合并等异常情况的出现。但是在现实世 界中，由节点失效、链路故障和网络分割合并等异常现象引起的消息在组中不 能按照t o t a lo r d e r 的顺序递送的情况比比皆是，有时候异常现象有可能导致机 中国科学技术大学硕士学位论文第1 章绪论 群中消息通信的死锁。而虚拟扩展同步能够满足在最坏的情况下，即使发生了网 络分割，在分割后的每个部分之内仍然按照t o t a lo r d e r 的顺序递送在组成员关 系发生改变之前就已经发送的正常消息，以及在组成员关系发生改变之后新组中 发送的正常消息：对于那些被分割到不同网络部分之间的节点在成员关系发生改 变之前所发送的正常消息，可以不用接受。因此，扩展虚拟同步的定义如下： 在组中成员关系没有发生变化时，整个组按照a g r e e do r d e r 的顺序或者 s a f eo r d e r 的顺序来递送消息。 若发生网络分割，则分割后出于不同网络部分的节点，在成员关系改变 之前所发送的消息，必须依旧能够按照a g r e e do r d e r 的顺序或者s a f e o r d e r 的顺序来递送。 若发生网络合并，则合并之前处于不同网络部分的节点，在成员关系改 变之前所发送的正常的消息，必须依然能够按照a g r e e do r d e r 的顺序或 者s a f eo r d e r 的顺序来递送。 扩展虚拟同步确保在系统范围内按照一致全序递送消息，即使网络分割和重 组、处理器失效和重启等。与此相比较，虚拟同步只要求在网络分割后的主部分 中提供这种一致全序递送消息。这种基于虚拟同步的系统治能保证网络分割的主 部分能够正常地工作。而在其他部分中的处理器停止工作，在其停止工作前可能 递送的消息的一致性也不能保证。 1 3 高可用技术 所谓高可用性【i 川，是指在特殊的场合下，很多应用程序要求连续运行，并 且每年仅有几分钟的停止运行的时间，例如银行、电信、生命支撑系统等等非常 重要的系统，其停止运行的代价是十分昂贵的。对于这些应用就希望在发生故障 的时候( 不论是硬件故障还是软件故障) ，能够将当前的环境状态保存起来，并 自动切换到其他正常运行的状态，继续执行或者提供服务。因此，高可用性必须 通过软件和硬件两个方面来保证，其中硬件方面就是通过硬件冗余的方案来实 现，其中一台硬件作为活动硬件，而其余的作为备份硬件，从而当某台或者某几 台硬件发生故障的时候，备份硬件就自动接管活动硬件的工作，实现硬件方面的 高可用性。对于软件的故障，就必须通过高可用平台来完成。在本文中所说的高 可用性都指的是软件的高可用性。 高可用平台是要对那些在该平台上运行的应用提供一种便利的实现高可用 的软件环境，其目标就是为高可用编程提供一种统一的接口，使得通过这种方式 编写出来的应用程序能够自动具有高可用的性质。为了实现软件的高可用性，就 必须实现服务冗余，使得当服务发生故障不能正常运行时，能够自动的切换到备 份并继续提供服务，因此在当前服务和备份服务之间不仅需要提供相同的消息集 合，而且消息集合中的消息序的相同也是非常重要的。而组通信系统是实现高可 用平台的重要基础，所以消息的可靠性和有序性就必须通过组通信系统来完成。 1 3 1 容错技术 提高硬件可靠性依赖于工业工艺技术的进步，提高软件可用性则依赖于软件 开发过程和软件设计。一般而言，处理软件错误可以分为四种方法：预防、移除、 中国科学技术大学硕士学位论文 第1 章绪论 容错、输入序列工作区。错误预防是指通过使用一些设计方法、技术、技巧等防 止设计时错误的引入，错误移除是指使用审查、分析、测试等手段来检查软件实 现并移除发现的错误。错误预防和移除都是从软件开发过程的角度考虑