COMP5313 Week 11 Distributed Hash Table 与 Consistent Hashing 讲课总结

Posted on Edited on In Word count in article: 1.1k Reading time ≈ 4 mins.
COMP5313 Week 11 讲课总结，整理 lookup problem、distributed hash table、Chord ring、finger table、consistent hashing 与 CAN 的考点重点。

COMP5313 Week 11 讲课总结：Distributed Hash Table 与 Consistent Hashing

老师明确说 P2P 系统介绍部分是 optional，用来引出 lookup problem。下面只保留 lookup、DHT、Chord/consistent hashing 和 CAN 的重点。

1. 本讲主题

本讲把 Week 10 的 decentralized search 思想放到分布式系统中：

在没有中心服务器的系统里，给定一个 file key，如何用局部邻居信息找到负责存储它的 computer node？

这个问题叫 lookup problem。

2. Lookup Problem

系统中有很多计算机节点，每个节点只知道少数邻居。

目标：

  • 给定 key。
  • 找到负责这个 key 的 computer。
  • 全过程不能依赖中心服务器。
  • 路径要短，消息数量要少。

这和 Milgram / decentralized search 类似：每一步只把请求转给一个合适邻居。

3. Hash Table 回顾

普通 hash table 存 key-value pairs。

操作：

  • put(key, value)：插入。
  • get(key)：按 key 查找 value。

hash function：

[ h(k) ]

把 key 映射到 bucket。

4. Distributed Hash Table, DHT

DHT 是把 hash table 分布存到多台机器上。

核心区别：

  • 普通 hash table 只要找 bucket。
  • DHT 还要先找哪台 computer 负责这个 key。

因此 DHT 需要额外操作：

  • lookup(key)：返回负责该 key 的 computer node。

然后再在那台机器上执行 get(key)。

5. Chord / Consistent Hashing Ring

老师重点讲 ring structure。

设 ID 和 key 都用 \(m\) bits 表示，因此 ID space 大小是：

[ 2^m ]

做法：

  • 把 computer IDs hash 到同一个 circular identifier space。
  • 把 file keys 也 hash 到同一个 space。
  • IDs 按顺时针递增排列成 ring。

6. Key 分配规则

文件 key \(k\) 存在：

顺时针方向第一个 ID 不小于 \(k\) 的 node 上。

这个 node 叫 key \(k\) 的 successor / responsible node。

如果没有正好等于 \(k\) 的 node，就存到下一个更大的 node。

这个规则的好处是：

  • 每个 key 有唯一负责节点。
  • 新节点加入或旧节点离开时，主要影响邻近区间。
  • 这就是 consistent hashing 的核心直觉。

7. Naive Ring Lookup

如果每个 node 只知道 successor：

  • 查询只能顺时针一个个往后传。
  • 最坏情况要走过几乎所有 nodes。

时间复杂度：

[ O(n) ]

其中 \(n\) 是参与系统的 computer 数量。

8. Finger Table

为了加速 lookup，每个 node 维护 finger table。

node \(i\) 的第 \(j\) 个 finger 指向负责以下 key 的 node：

[ i+2{j-1}\pmod{2m} ]

其中 \(j=1,\dots,m\)。

直觉：

  • finger table 提供不同尺度的跳跃边。
  • 距离有 \(1,2,4,8,\dots\) 这些量级。
  • 类似 Week 10 中不同距离尺度的 weak ties。

9. Chord Lookup 规则

老师总结为：

Go as far as possible, but never pass the target.

查找 key \(k\) 时：

  1. 如果 \(k\) 在当前 node 和 successor 之间，交给 successor。
  2. 否则，在 finger table 中选择不超过 \(k\) 的最大 ID。
  3. 把请求转给该 node。
  4. 重复直到找到 responsible node。

做题时要能根据 ring 和 finger table 走出 lookup path。

10. Chord 复杂度

每一步大致把到目标的距离减半。

因此 lookup message 数：

[ O(n) ]

每个 node 存储：

  • finger table，大小约 \(m\)。
  • 若干 successors / predecessors 用于处理 join、leave、failure。

空间复杂度：

[ O(n) ]

因为 \(m\) 与 \(\log n\) 同量级。

11. CAN: Content Addressable Network

老师最后讲了 CAN 作为另一种 DHT。

设 key 和 node ID 是 \(d\) 维空间中的点，例如二维 \([0,1]\times[0,1]\)。

做法：

  • 整个空间被划分为 zones。
  • 每个 node 负责一个 zone。
  • key 落在哪个 zone，就由对应 node 负责。
  • 新 node 加入时，随机选点并分裂已有 zone。

12. CAN Routing

每个 node 只知道相邻 zones 的 nodes。

查找时：

  • 目标是 key 所在的空间坐标。
  • 当前 node 选择欧氏距离目标最近的邻居。
  • 一步步 greedy routing 到负责 zone。

复杂度：

  • 二维时大约 \(O(\sqrt n)\)。
  • \(d\) 维时 lookup 大约 \(O(d n^{1/d})\)。
  • 每个 node 维护邻居数量约 \(O(d)\)。

老师说 CAN 细节不需要过深，重点知道复杂度和思想。

13. 考点重点

  • 知道 P2P intro 是背景，核心是 lookup problem。
  • 会解释 DHT 比普通 hash table 多了 lookup(key)。
  • 会说明 consistent hashing ring：nodes 和 keys hash 到同一 circular ID space。
  • 会用 successor rule 判断 key 存在哪个 node。
  • 会构造或使用 finger table。
  • 会按 “go as far as possible, but never pass target” 走 Chord lookup path。
  • 记住 Chord lookup 时间 \(O(\log n)\)，每节点空间 \(O(\log n)\)。
  • 知道 CAN 用 \(d\) 维 zones，routing 走最近邻，时间约 \(O(dn^{1/d})\)，空间约 \(O(d)\)。