本节书摘来自华章出版社《云数据管理》一书中的第2章，第1节，作者迪卫艾肯特·阿格拉沃尔，更多章节内容可以访问云栖社区“华章计算机”公众号查看

基于广播和多播的组通信

如果数据被复制到多个节点上进行存储，数据更新操作需要发送给所有的副本。广播或多播操作是一种简单的通信原语。一般来说，广播方式把同一条消息发送给系统中的所有站点，而多播只发送给部分站点。不失一般性，我们用多播来表示发送信息到特定的节点集合。下面将介绍已经提出的多种不同的原语，这些原语已经在分布式系统和数据中心等不同场景中得到了应用。

FIFO多播或发送者有序的多播：消息按照被发送的顺序传输（单个发送者）。

因果序多播：如果发送m1和m2两个消息，并且m1的发送事件在m2的发送事件之前发生，那么在所有相同的目的地上，m1都必须先于m2传输。

全序（或原子）多播：所有消息都以相同的顺序发送给接收者。

实现不同多播协议的关键在于如何设计一种方法从而保证顺序一致性约束。假设底层网络只支持点对点通信，不支持任何多播原语。另外，需要把网络中消息的接收者和应用层中消息的实际传输者进行区分。接收到一条消息之后，该消息被插入到队列中，当序列条件满足时，消息才能开始传输。下面将对实现这些原语的协议进行描述。图2-5展示了一个包含3个因果相关多播e1、e2和e3的示例。如果这些多播都是因果相关多播，那么，部分消息的传输就需要推迟，直到因果序条件得到满足以后才能继续传输。例如，虽然进程r接收到e2的时间比e1的接收者时间早，但是因为e1发生在e2之前，所以，必须等到r对e1完成接收和传输之后才能对e2开始传输。同样，e3必须等到e1和e2传输完成之后才能开始传输。再看另外一个例子，图2-6也包含了3个多播e1、e2和e3。尽管e1和e2不是因果相关，并且是从不同的进程p和q发出的，如果它们是全序多播的话，那么所有的站点都要按照相同的顺序进行传输，而与它们的接收顺序无关。例如，虽然进程r接收e2的时间比接收e1的时间早，而在进程s中该顺序刚好相反，但是，所有的站点都必须按照相同的顺序来传输这两个多播，比如先传输e2，再传输e1。需要说明的是，即使发送操作是因果相关的，全序也不需要一定要满足因果序。例如，e2和e3是因果相关的，并且e2发生在e3之前，但是所有的进程仍可能是先传输e3，再传输e2。

 

图2-5　因果序

 

 

图2-6　全序

FIFO多播可以用一种类TCP传输协议来简单地实现，即消息发送者可以设置一个有序的消息标识符，任意一条消息在其之前的消息完成接收和传输之前都需要等待。如果有消息丢失了，接受者可以向发送者请求丢失的消息。

因果多播可以通过如下方式来实现：要求每一个广播消息都携带所有因果前置消息。在传输之前，接受者必须通过传输任何丢失的因果前置消息来确保因果关系。但是，这种协议的开销非常大。还有另外一种可供选择的协议（ISIS [Birman, 1985]），该协议使用向量时钟来延迟消息的传输，直到所有的因果前置消息都被传输完成。每一个进程负责维护一个长度为n的向量时钟V，n是系统中节点的数量。V的元素被初始化为0。当节点i发送一个新的消息m时，对应节点i的元素值就加1。每一个消息都与发送者的本地向量组合在一起。当节点发送消息时，该节点需要利用如下方式对其向量进行更新：选择本地向量和随消息到达的向量之间的元素的较大值来更新。节点i利用向量VT发送消息m，如果向量VT中与发送者相对应的元素刚好比接收端本地向量中的发送者元素大1（即是下一条消息），并且，本地向量的所有元素都大于等于VT中的对应元素，那么接收者就接收到了所有的因果前置消息。

全序多播可以通过集中式方法来实现，例如固定的协调者（使用在Amoeba [Kaashoek et al., 1989]中），或者移动令牌等[Défago et al., 2004]。另外，ISIS [Birman, 1985]也提出了分布式协议。在ISIS分布式协议中，所有进程通过三轮来对序号（或优先级）达成一致意见。发送者将具有唯一标识符的消息m发送给所有接收者。接受者会建议一个优先级（序号），并把建议的优先级反馈给发送者。发送者收集完所有的优先级建议，并确定一个最终的优先级（通过进程编号打破关系），然后针对消息的重新发送最终达成一致意见的优先级。最后，接收者再按照最终的优先级来传输消息m。