Peer-to-peer system 把 storage、bandwidth 與 responsibility 分散給 participant。它的演進可以看成 lookup cost 與 centralization 的取捨史。
| Design | Lookup | 優點 | 弱點 |
|---|---|---|---|
| Napster | Central directory | Lookup 快 | Directory bottleneck／failure |
| Gnutella | 向 neighbor flood query | 無 central index | Message 多、search horizon 有限 |
| FastTrack | Supernode 索引 local peer | Scale 較好 | Role 不平等、hotspot |
| BitTorrent | Tracker／DHT 找 swarm，再交換 piece | Parallel download、incentive | Discovery／availability 仍重要 |
| Chord | Structured ring、finger table | Expected logarithmic lookup | Churn 下需要維護 |
Chord 是 distributed hash table
Chord 將 node identity 與 key hash 到同一個 (m)-bit circular space。Key 屬於順時針第一個 ID 大於等於它的 node，也就是 successor。
key K42 ──clockwise──> node N45Consistent hashing 讓 node join／leave 時主要搬動鄰近 key，而非 remap 全部 dataset。
每個 node 保存 successor，加上按指數距離分布的 finger。Table 使用 (O(log N)) state，lookup 預期 (O(log N)) hops。
白話來說： 每一 hop 大約跳過剩餘距離的一半。
Churn 讓漂亮 ring 變成維運問題
Node 會 join、leave、fail。Stabilization 修正 successor；successor list 降低直接 neighbor 故障後 ring 斷裂風險；replication 保護 value。Lookup complexity 的前提，是 maintenance 追得上 churn。
Pastry 使用 prefix routing，並考慮 network locality；Kelips 用更多 membership state 換接近 constant-hop lookup。沒有 overlay 在所有維度都贏：routing latency、memory、maintenance traffic、locality 與 churn tolerance 會互相交換。
複習卡
- P2P 分散 resource ownership，但仍需要 discovery。
- Unstructured flooding 用 message cost 換簡單。
- Structured overlay 限制 topology，使 lookup 可預測。
- Chord 將 node 與 key 放在同一 ring。
- Finger table 帶來 logarithmic state 與 expected hops。
- Churn 讓 routing 變成持續 repair。