Peer-to-peer systems distribute storage, bandwidth, and responsibility across participants. Their history is a sequence of trade-offs in lookup cost and centralization.
| Design | Lookup idea | Strength | Weakness |
|---|---|---|---|
| Napster | Central directory | Fast lookup | Directory bottleneck/failure |
| Gnutella | Flood query to neighbors | No central index | Many messages, bounded horizon |
| FastTrack | Supernodes index local peers | Better scale | Unequal roles and hotspots |
| BitTorrent | Tracker/DHT finds swarm; peers exchange pieces | Parallel download, incentives | Discovery and availability still matter |
| Chord | Structured ring and finger table | Expected logarithmic lookup | Maintenance under churn |
Chord as a distributed hash table
Chord hashes node identities and keys into the same (m)-bit circular space. A key belongs to the first node clockwise whose ID is equal to or follows the key: its successor.
key K42 ──clockwise──> node N45Consistent hashing moves mainly the keys adjacent to a node that joins or leaves, rather than remapping the whole dataset.
Each node keeps a successor plus fingers at exponentially increasing distances. The table uses (O(log N)) entries and routes a lookup in expected (O(log N)) hops.
In plain terms: every hop skips roughly half the remaining distance around the ring.
Churn makes the elegant ring operational
Nodes join, leave, and fail. Stabilization repairs successor information; successor lists reduce the risk of losing the ring when an immediate neighbor fails; replication protects values. Correct lookup complexity assumes this maintenance keeps pace with churn.
Pastry uses prefix-based routing and locality-aware choices. Kelips spends more membership state to approach constant lookup hops. No overlay wins every dimension: routing latency, memory, maintenance traffic, locality, and churn tolerance trade against one another.
Review card
- P2P design distributes resource ownership but still needs discovery.
- Unstructured flooding trades simplicity for message cost.
- Structured overlays constrain topology to make lookup predictable.
- Chord maps nodes and keys onto one ring.
- Finger tables give logarithmic state and expected hops.
- Churn turns routing into a continuous repair problem.
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。