Tiny_DHT_Lab

A distribute hash table learning project based on Chord protocol.

分布式哈希表

聊聊分布式散列表（DHT）的原理 - - 以 Kademlia（Kad） 和 Chord 为例

保存数据（以下只是大致原理，具体的协议实现可能会有差异）当某个节点得到了新加入的数据（K/V），它会先计算自己与新数据的 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。如果计算下来，自己与 key 的距离最小，那么这个数据就保持在自己这里。否则的话，把这个数据转发给距离最小的节点。收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

获取数据（以下只是大致原理，具体的协议实现可能会有差异）当某个节点接收到查询数据的请求（key），它会先计算自己与 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。如果计算下来，自己与 key 的距离最小，那么就在自己这里找有没有 key 对应的 value。有的话就返回 value，没有的话就报错。否则的话，把这个数据转发给距离最小的节点。收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

Chord协议

一致性哈希

“一致散列”把散列值空间（keyspace）构成一个【环】。对于m比特的散列值，其范围是[0, 2^m-1]。你把这个区间头尾相接就变成一个环，其周长是2^m。然后对这个环规定了一个移动方向（比如顺时针）。

如果 node ID 和 data key 是同构的，那么这两者都可以映射到这个环上（对应于环上的某点）。

Chord的前提：

• 节点间数据按一致性hash分布，可以使用虚拟节点。

假设网络是：

• 对称的（如果A能访问B，则B也能访问A）。
• 可传递的（如果A能访问B，B能访问C，则A也能访问C）。

分享会