高级分布式系统-第6讲 分布式系统的容错性--可靠的组通信

可靠的组通信

组内通信最好是每个进程之间都建立点到点的通信， 但实际中这样的组织结构不是有效的， 因为会浪费很大的通信带宽。

在平等组中， 多播是主要的组织结构。 但多播是具有同步性质的容错结构， 并不适用拜占庭模型。

多播服务需要保证消息被传送给进程组中的所有成员， 但由于进程成员管理的动态性（ 创建、 删除、 加入、 离去等） ， 可靠多播的实现是十分困难的。

可靠的组通信， 就是指发送到一个组的消息被传递给该组的每个成员。 可分为哪两类： 存在故障进程时的可靠通信与假定所有进程都正确的操作时的可靠通信。

假定所有进程都不会失败时的可靠通信

在这种情况下， 如果通信期间不会有进程加入或离开组， 那么可靠多播就简单意味着每个消息都应该被传递到组的每个当前成员处。 实现这种简单的可靠多播的一种方法就是为每个多播消息分配一个序列号。

假定所有进程都不会失败时的可靠通信

简单的可靠多播存在一个问题： 如果接受者众多， 在每个接收者都要回复确认信息时， 那么发送者可能被大量的反馈消息淹没而产生反馈拥塞。

解决方法： 采用否定确认的消息机制， 接收者不对消息接收进行反馈， 而是只在通知发送者消息丢失时才返回一个反馈消息。

缺点： 发送者不得不永远在历史缓存器中保留消息。 因为发送者永远不会知道消息是否已被传送到所有的接收者， 所以总是需要准备处理来自接收者的要求重发旧消息的请求。

两种具体方案： 无等级的反馈控制和分等级的反馈控制

无等级的反馈控制

一个没有接收到消息m的接收者R延迟一个随机的时间然后发送反馈消息。

如果同时有其他对m的重发请求到达R， 那么R就抑制自己的反馈， 因为它知道m会短时间内重发。

分等级的反馈控制

如果一个发送者需要向一个非常大的接收组进行多播， 可将接收组分为多个子组， 组织成树的形式。

每个子组制定一个本地协调者， 它负责处理子组中包含的接收者的重发请求。 本地协调者具有自己的历史缓存器。

存在进程失败情况下的可靠通信

如果多播通信满足下列两个条件， 则称为原子多播（ atomicmulticast） ：

（ 1） 分布式系统中保证消息要么被发送给所有的进程， 要么就不向任何一个进程发送。

（ 2） 所有的消息都按照相同的顺序发送给所有的进程。

在上述两个机制中， 第（ 1） 个机制通常由虚拟同步完成， 第（ 2） 个机制由消息排序实现。

虚拟同步

多播消息m唯一地跟它应该传送的一个进程表相关联。 这个表对应一个包含组中进程的组视图。 列表中的每个进程都具有相同的视图， 即它们都同意m应该被传送给它们中的每一个而且不被传送到别的进程。

进程的加入或离开会影响到组视图的构成。

如果消息的发送者在多播期间崩溃， 那么消息或者被投递给所有剩余的进程， 或者被每个进程忽略。 具有这种属性的可靠多播被称为虚拟同步。

虚拟同步的原理是所有多播都在视图改变之间进行。 换句话说， 视图改变作为一个屏障， 不能跨越它进行多播。

例子： 下图所示4个进程。 在某个时刻， 进程P1加入了一个进程组， 然后这个进程组就由P1、 P2、 P3和P4组成。 在多播了一些消息之后， 进程P3崩溃了， 但是在崩溃之前它成功地将消息多播到了进程P2和P4， 但是没有多播到P1。 此时， 虚拟同步的机制保证这个消息不会传送至进程， 这就有效地建立起一种情况， 使得在P3崩溃之前的消息像是从来没有被发送（ 被丢弃） 。

消息排序

????????多播的消息排序种类：

????????不排序的多播

????????FIFO顺序的多播

????????按因果关系排序多播

????????全序多播

不排序的多播

FIFO顺序的多播

FIFO顺序的多播： 同一进程传送的消息有顺序约束， 不同进程传送的消息顺序没有约束。

按因果关系排序多播

按因果关系排序多播： 如果消息m1和m2之间存在因果关系， 即m1导致了m2的产生， 那么无论它们是否由同一个发送者多播的， 每个接收者的通信层都应该在接收m1之后传送m2。

全序多播

不论消息传送是无序、 FIFO顺序还是因果关系排序，都需要在传送消息时， 对所有的成员按照相同的次序来传送。

六种不同的虚拟同步可靠多播

提供了全序的消息传送的虚拟同步可靠多播称为原子多播。