北工大分布式简略版

更新: 12/24/2025 字数: 0 字 时长: 0 分钟

本质是对yishu 北工大分布式系统中复杂篇章的简略与小白化的版本，方便没有相关基础的人快速熟悉相关知识。

文件系统

DFS 文件架构

服务器端通常由 flat file service 和 directory service 组成。

• flat file service 负责给每个文件分配一个 UFID 来标记文件。
• directory service 负责将目录和文件名转化为 UFID。

Sun NFS

一种基于远程访问模型的无状态分布式文件系统的实现。使用者需要用 mount 命令把远程文件夹挂载到自己的目录树上。

• 硬挂载：一直尝试直到成功，常用。
• 软挂载：挂载失败了就多试几次，不行就报错推出，实际上不好处理。

SUN NFS 基于时间戳检查缓存是否过期，即客户端定期询问服务器文件是否需要更新。

AFS

AFS 是一种基于上传/下载模型的有状态分布式文件系统的实现。

在每次下载和访问的文件都很小且读多于写的情况下，上传/下载模型一次性获取整个文件的特点使其比远程访问模型更加有效。

AFS 服务器会给客户端一个 callback promise：向客户端承诺当服务器上的文件被修改时，服务器会主动通知客户端，使得客户端缓存失效。

P2P

P2P 是一种适用于存储大量只需要读取的，很特殊的 DFS 系统：其没有中心服务器，所有节点既是客户端又充当服务器。

P2P 在应用层上采用 routing overlays 来寻址，避免了在一个随时有节点加入和推出的系统中 IP 不断变化的寻址问题：

• GUID：P2P 系统十分依赖 GUID 来标识文件，每个文件的 GUID 是根据其自身的内容计算出来的。也因此，节点在收到文件时可以通过再次计算文件的 GUID 来验证文件的完整性。
• DHT：P2P 系统中节点也有 GUID，文件会被存放在与其 GUID 最相近的节点上。在根据 GUID 寻找文件时，节点会根据其 DHT 路由表逐步将请求转发给 GUID 更接近目标文件的节点，直到找到目标文件为止。

简单来说，IP 地址是用来定位机器的，而 routing overlays 是用来定位文件的。DHT 路由表相比 IP 路由表来说更为轻量，所以更新速度相对非常快；其次它的地址数量也可以是无限的，不会像 IPV4 那样面临地址耗尽的问题。

Pastry 算法

Pastry 算法是一种常见的 DHT 路由算法：

每个节点储存两个表：

1. 叶子集合 (Leaf Set)：记录了在 ID 数值上里自身最近的一批节点。
2. 路由表 (Routing Table)：记录了前缀相同的节点，按前缀长度分层储存。

当节点收到一个 package，目标是发给 GUID 的节点：

1. 首先，会在叶子集合中查看是否有这个节点，如果有就直接发给它。
2. 如果没有，就在路由表中寻找与 X 前缀相同且相同前缀更长的节点。
3. 如果没有比自己前缀更长的节点，那就在叶子集合和路由表中找一个前缀长度和自己相同且数值上更接近的节点。

BitTorrent 协议

BitTorrent 协议是一种常见的 P2P 文件分发协议，有 4 个关键角色：

1. .torrent 文件：一个很小的元数据文件，记录了 tracker 地址、文件块数、每一块的哈希值等信息。
2. Tracker：唯一的中心化组件，维护下载同一文件的 peer 列表，帮助 peer 互相发现。
3. Seeder：拥有完整文件的节点。
4. Leecher：只拥有部分文件的节点。

文件最初的发布者把大文件切片（Chopping）成无数个小块（Piece）。当用户想要下载对应文件时，需要使用 .torrent 去联系 Tracker，Tracker 会记录这个用户并返回一些其他的也在下载的 peer 列表，用户就可以根据这份名单去向其他 peer 请求文件块。当用户拥有第一块时候，其本身也变成了“源”，它可以把这块文件分享给其他 peer 下载。

BitTorrent 采用最稀有优先（Rarest First），这意味着 peer 会优先下载那些最稀缺的块，从而保证整个分布式系统中文件副本的数量，避免“孤本”。简而言之，这个策略是为了提升系统的健康性，防止某个块意外丢失后文件就不能完整拼凑。

组通信

多播

使用单播放会导致要多次发送同一消息，才能让所有节点都接受到你的消息。而使用多播，你只需发送一次，让网络帮你复制消息以发送给所有的人。

IP Multicast (IP多播) 是最底层的技术，虽然它支持发给一组人，但它基于 UDP 是不可靠的。

在多播的环境下，我们将 Receive 和 Deliver 两个概念做一个区分：

• Receive：只是网卡收到了包，可能是乱序或缺少部分包的。
• Deliver：中间件把消息整理好，确保包的顺序和完整，正式递交给应用程序。

可靠多播

可靠多播：确保所有接收者都能正确（顺序和完整）收到发送者发送的消息。

虽然可以使用 TCP 协议来保证消息传播的可靠性，可是 TCP 本身也导致一个问题——ACK Implosion（确认风暴）：如果 给 1000 个人发消息，这 1000 个人也同时回 ACK，发送方接收压力会爆涨，导致网络拥塞，甚至丢掉重要的确认包。

为了既要效率（像 IP 多播），又要可靠（像 TCP），最终有了可靠多播。可靠多播必须保证三件事：

1. 完整性 (Integrity)：不丢、不重。
2. 有效性 (Validity)：发送者自己也能收到自己发送的消息。
3. 一致性 (Agreement)：全有或全无。要么所有人都收到，要么都没收到。

实现很精妙：

• 序列号 ($S_p,R_q$)：每个人都记录：我发了多少条信息，又收到了某人多少条。
• 捎带确认 (Piggy-backed ACKs)：
  • 不专门发 ACK。
  • 在发送下一条消息时，顺便夹带信息：「某人的前 N 条信息我都收到了」。
• NAK (Negative ACK) 与 缓存队列 (Hold-back Queue)：
  • 如果有节点在接受别人的消息时发现：「咦？你都收某人的第 5 条消息了，我才收到第 3 条？」这说明我漏了第 4 条。
  • 这时候节点会主动发 NAK 求救：「你有 4 条？给我也整一个！」。
  • 在第 4 条补发回来之前，收到的第 5、6 条不能给应用层，必须先放在 Hold-back Queue 里等着，直到补齐了顺序再一起交付。

视图同步

当一个发送者（Progress P）在发消息的过程中突然 Crash 了，系统该如何判决那条「遗言」？

总之，为了维护一个可靠的多播系统，我们要确保：消息，要么让所有节点在 P 挂掉之前收到，要么在挂掉之后作为新消息处理。绝不允许有人觉得是挂掉之前发的的，有人觉得是挂掉之后发的。

假设 P 发送消息 $m$ 给 Q 和 R，然后 P 突然崩溃了：

• 情况：P 的消息还没有传到任何节点那里
  • Q 和 R 都没收到 $m$，随后 GMS 宣布新视图 {Q, R}
  • 这种情况是允许的，毕竟这条消息就像从未存在过一样，大家都不知道，故一致性仍在。
• 情况：P 在挂掉之前，消息 $m$ 成功传给 Q 和 R。
  • Q 和 R 都收到了 $m$，然后 GMS 才宣布新视图 {Q, R}。
  • 允许，大家都收到了信息，故一致性也没问题。
• 情况：P 挂了，GMS 通知新视图给 Q 和 R，然 Q 和 R 在这之后都收到了来自 P 的消息，或者一个在新视图一个在旧视图收到了消息。
  • 不允许的，这破坏了一致性，Q 和 R 在同一个组却对消息有不同的了解。
  • 只有前两种情况是允许的，类似此类破坏一致性的情况是不允许，需要避免的。

复制系统、

一致性

复制（Replication）虽然能备份数据，但也引入了新的问题：如何保证多个副本存的数据是一样的？我们需要维护多个副本的一致性（Consistency）。

为了衡量副本同步得好不好，定义两个标准：

• 线性一致性 (Linearisability)：所有操作必须看起来像是按真实时间顺序发生的，有严格的先后顺序。
• 顺序一致性 (Sequential Consistency)：只要保证每个客户端有自己的操作顺序没有问题，并且大家看到的总交错顺序是一样的就行，即逻辑上有先后。

被动复制

有两个角色：

• Primary：只有一个。处理所有写请求（Update） 。
• Backup： 有好几个。平时只从 primary 那里同步数据。

优缺点：

• 优点：它是线性一致性的，因为所有的操作都是 primary 一人操刀。
• 缺点：如果老大 crash，必须进行新的选举，这段时间服务会中断 。

此外还有变体，使 backup 可以帮忙读，但这会使一致性降级为顺序一致，因为 backup 可能无法及时同步。

主动复制

也叫状态机复制，这个模式里，大家地位平等。

工作流程：

1. User 通过组播（Multicast）把请求同时发给所有 RM。
2. 这个组播必须是完全有序（Totally Ordered）的。保证所有人收到请求的顺序一模一样。
3. 每个 RM 各自独立执行请求。
4. 每个 RM 都给前端回复结果。前端收到第一个（或大多数）回复就算成功。

优缺点：

• 优点：容错性强，单个 RM 的损坏不会造成影响。
• 缺点：它通常只能保证顺序一致性，而且对底层的组播协议要求很高。

Gossip 架构

Gossip 架构是一种最终一致性（Eventual Consistency）的复制系统实现。

在 Gossip 架构里，系统不再强求「此时此刻，所有人知道的事情必须一模一样」，只要当真正需要顺序一致的时候，逻辑顺序会保持一致。

• 高可用性 (High Availability)：
  • 客户端可以随便找任何一个还活着的 Replica Manager (RM) 发请求。
  • 只要客户端能连上至少一台机器，服务就能继续。
• 八卦传播 (Gossip Messages)
  • 收到更新的这台机器，不会立刻去通知所有人。
  • 定期随机找几个邻居，通知发生的事。
  • 一传十，十传百... 最终所有机器都会知道。这就是最终一致。

如果 RM 都在乱传八卦，会不会出现因果错乱？为了解决这个问题，Gossip 引入了向量时间戳 (Vector Timestamps) 。

• 客户端每次跟系统说话时，都会随身带着一个时间戳，记录它上次跟每个 RM 说话时，各自的最新状态是怎么样的。
• 如果客户端换了一台服务器（比如从 RM A 换到了 RM B）， 客户端会把这个时间戳展示给 RM B 看。
• RM B 通过查看时间戳，发现自身的状态比时间戳里记录的还要旧，就知道自己落后了。
• RM B 会阻塞客户端的请求，或者是赶紧去问别的 RM 要数据，直到它追上客户端的进度为止。

这保证了客户端一致性 (Client Consistency)：客户端永远不会感到时光倒流。