消息排序与组通信：从因果顺序到传播树算法

# 消息排序与组通信：从因果顺序到传播树算法 在分布式系统中，消息排序和组通信是至关重要的概念，它们直接影响着系统的一致性、可靠性和性能。本文将深入探讨消息排序的相关知识，包括因果顺序、总顺序，以及实现这些顺序的算法，最后介绍用于多播的传播树方法。 ## 1. 因果顺序中的消息处理 ### 1.1 消息传递与日志更新 在分布式系统中，消息的传递和处理需要遵循一定的顺序，以确保系统的一致性。当消息发送和接收时，相关的信息会被记录在各个进程的日志中。例如，当消息 M5 - 1 被传递到 P6 时，“M5 - 1Dests = {P4}” 会被添加到 Log6 中。后续消息传递时，会携带相关的信息，如 M4 - 3 携带 “M5 - 1Dests = {P6}”，这些信息在不同进程中有不同的处理方式。 ### 1.2 各进程的信息处理逻辑 #### P2 和 P3 的信息学习 当 P2 和 P3 收到消息 M4 - 2 时，它们会将新的信息 “M5 - 1Dests = {P6}” 插入到本地日志中。随着消息的继续传递，当它们分别在事件 (2, 4) 和 (3, 2) 收到消息 M3 - 3 和 M4 - 3 时，会得知未来的消息相对于 M5 - 1 发送到 P6 会按因果顺序传递。此时，根据约束 II，它们会从日志中删除相关信息。以 P3 为例，当收到携带 “M5 - 1Dests = ∅” 的 M4 - 3 时，由于 Log3 中已有 “P6 ∈ M5 - 1Dests”，会推断该信息过时并删除，将 M5 - 1Dests 设置为 ∅。P2 的逻辑与此相同。 #### P6 的信息处理 P6 在接收和处理消息时，会根据日志中的信息和收到的消息携带的信息来确定消息的传递顺序。当收到携带 “M5 - 1Dests = {P6}” 的 M4 - 3 时，该信息仅用于确保 M4 - 3 的因果传递，不会插入 Log6。因为 Log6 中已有 “M5 - 1Dests = {P4}”，意味着 M5 - 1 已传递到 P6，且收到信息中 P4 的缺失暗示 M5 - 1 已按因果顺序传递到 P4，所以将 M5 - 1Dests 设置为 ∅。同理，收到携带 “M5 - 1Dests = {P4, P6}” 的 M5 - 2 时，也不会插入 Log6。 #### P1 的信息处理 P1 在收到携带不同信息的消息时，会根据日志中的信息进行判断。当收到携带 “M5 - 1Dests = {P6}” 的 M2 - 2 时，会将该信息插入 Log1。当收到携带 “M5 - 1Dests = {P4}” 的 M6 - 2 时，会通过信息的缺失得知 “M5 - 1 已传递到 P6”，并标记 “P6 ∈ M5 - 1Dests” 为待删除，同时将 M5 - 1Dests 设置为 ∅。后续收到携带 “P6 ∈ M5 - 1Dests” 的 M2 - 3 时，会根据 Log1 中的 “M5 - 1Dests = ∅” 推断该信息过时并忽略。 ## 2. 总顺序的概念与实现 ### 2.1 总顺序的定义 虽然因果顺序在很多场景中很有用，但总顺序也是一种重要的排序方式。总顺序要求所有消息的接收者以相同的顺序接收消息。正式定义为：对于每对进程 Pi 和 Pj，以及每对都传递给这两个进程的消息 Mx 和 My，Pi 在 My 之前接收 Mx 当且仅当 Pj 也在 My 之前接收 Mx。 ### 2.2 总顺序的实现算法 #### 2.2.1 集中式算法 集中式算法适用于所有进程广播消息的系统，且系统中的通道为 FIFO 通道。该算法的核心思想是每个进程将想要广播的消息发送给一个集中进程，集中进程再将收到的消息转发给其他所有进程。具体步骤如下： 1. 当进程 Pi 想要向组 G 多播消息 M 时，发送 M(i, G) 到中央协调器。 2. 当中央协调器收到来自 Pi 的 M(i, G) 时，将其发送给组 G 的所有成员。 3. 当进程 Pj 收到来自中央协调器的 M(i, G) 时，将其传递给应用程序。 该算法的复杂度为每个消息传输需要两个消息跳，在 n 个进程的系统中需要 n 条消息。但它存在单点故障和拥塞的缺点。 ```plaintext (1) 当进程 Pi 想要向组 G 多播消息 M 时： (1a) 发送 M(i, G) 到中央协调器。 (2) 当 M(i, G) 从 Pi 到达中央协调器时： (2a) 发送 M(i, G) 到组 G 的所有成员。 (3) 当 M(i, G) 从中央协调器到达 Pj 时： (3a) 将 M(i, G) 传递给应用程序。 ``` #### 2.2.2 三相分布式算法 三相分布式算法用于强制封闭组中的总顺序和因果顺序。该算法从发送者和接收者的角度分别有不同的处理阶段。 ##### 发送者阶段 1. **第一阶段**：进程将消息 M 与本地唯一标签和本地时间戳一起多播给组成员。 2. **第二阶段**：发送者等待所有组成员的回复，成员会为消息 M 提供一个暂定的修订时间戳。发送者在收到所有回复后，计算这些时间戳的最大值作为最终时间戳。 3. **第三阶段**：发送者将最终时间戳多播给组内成员。 ##### 接收者阶段 1. **第一阶段**：接收者收到带有暂定时间戳的消息，更新跟踪最高提议时间戳的变量 priority，将消息及其标签和修订后的时间戳放入队列 temp_Q 尾部，并标记为不可传递。 2. **第二阶段**：接收者将修订后的时间戳和标签发送回发送者，然后非阻塞地等待最终时间戳。 3. **第三阶段**：接收者收到最终时间戳后，更新 temp_Q 中的相应消息条目，将其标记为可传递，重新排序队列。如果消息在队列头部，则将其移动到 delivery_Q 中。 ```plaintext record Q_entry M: int; // 应用程序消息 tag: int; // 唯一消息标识符 sender_id: int; // 消息发送者 timestamp: int; // 分配给消息的暂定时间戳 deliverable: boolean; // 消息是否可传递 (local variables) queue of Q_entry: temp_Q, delivery_Q int: clock // 用作 Lamport 标量时钟的变体 int: priority // 用于跟踪最高提议的时间戳 (message types) REVISE_TS(M, i, tag, ts) // Pi 发送的第一阶段消息，带有初始时间戳 ts PROPOSED_TS(j, i, tag, ts) // Pj 发送的第二阶段消息，带有修订后的时间戳，发送给 Pi FINAL_TS(i, tag, ts) // Pi 发送的第三阶段消息，带有最终时间戳 (1) 当进程 Pi 想要多播带有标签 tag 的消息 M 时： (1a) clock ← clock + 1; (1b) 发送 REVISE_TS(M, i, tag, clock) 到所有进程; (1c) temp_ts ← 0; ( ```