Chord 协议

概述

Chord 是 MIT 的 Ion Stoica、Robert Morris 等人于 2001 年发表的分布式哈希表查找协议，回答"在无中心的对等网络中，如何快速定位某个键属于哪个节点"，与 CAN、Pastry、Tapestry 并列为结构化 P2P 的四大经典。

原理

节点与键经 SHA-1 哈希映射到同一个环形标识空间，键由顺时针方向第一个不小于它的节点（successor）负责。每个节点维护 finger table，第 i 项指向距离自己 2^(i-1) 的位置的后继节点，查找时每跳至少缩短一半距离，复杂度 O(log N)；节点加入退出由稳定化协议增量修复指针。

影响

Chord 论文获 SIGCOMM 时间检验奖，其"一致性哈希 + 对数路由"思想影响了 Dynamo、Cassandra 的数据分布设计与众多去中心化存储系统。