2016-07-25
Kademlia笔记

Kademlia 是为p2p网络设计的分布式hash表算法。bt的DHT,emule的kad网络等都是基于它实现的去中心化资源节点搜索。

Kademlia的设计思想跟ip地址的设计思想很相似,即, 将网络节点的拓扑位置结构化,一个节点对离它越近的节点知道得越清楚。当一个节点要查询一个特定位置时,总是询问它所知的离该位置最近的节点,来获得离目标位置更近的节点信息。反复循环这个过程,以期最终达到目标位置。

但不同的地方在于:

  1. Kademlia的节点位置(Node ID)是节点自己随机出的160bit长的整型,而ip地址是由运营商分配的。

  2. Kademlia里两个节点间的距离完全由两者的ID决定,而ip距离与地理相关,取决于两点间的路由跳数。

  3. Kademlia里所有的节点都是路由节点,而ip网络里路由和终端是一般是分开的。

节点ID

节点ID是节点自己随机出的160bit长的整型, 两个节点间的距离完全有两者的ID决定,具体算法非常巧妙:两个ID取异或。

比如节点A为:0b0101 ,节点B为: 0b0010, 节点C为: 0b1010, 则dist(A,B) = 0b0111 = 7 < dist(B, C) = 0b1000 = 8

异或具备作为距离函数需要的三个要素:

  1. 与自身的距离为0

  2. 互换性。xor(A,B) = xor(B,A)

  3. 三角定律。 xor(A,C) <= xor(A,B) + xor(B, C)

关于第三点的证明,可以先证明单个bit位上成立,然后推广到任意长度。

路由

Kademlia网络的拓扑结构是一个二叉树结构,每个节点是树的叶子。从根节点到某个叶子的路径上,路径中的每个点都可以分出一个不包含该叶子的子树。随着路径点的后移,不包含该叶子的子树大小以2的倍率减小,如第一个路径点(根节点)分出的不包含该叶子的子树为整个树大小的1/2,第二个路径点分出1/4,第三个1/8 …… 一共有160个这样的子树,离叶子越近的子树越小,子树的大小即key的空间大小。该节点为每个这样的子树维护一个长度为k的列表,被称作k-bucket. 其他节点的路由信息根据它们落在哪个子树内而放到对应的k-bucket里。

通过这样的路由划分,就实现了离自己越近的节点自己知道的越清楚。

节点0011...的路由信息

节点查找

<key, value>存储在节点ID离key最近的节点上。key必须是160位的,一般是value的sha1值。这样Kademlia巧妙地实现了寻找存储有某资源的节点等同于寻找ID为该资源的sha1值的节点.

要实现这点,就要求每个节点要定期把存储在自身上的<key,value> 对publish到比自己离key更近的节点上。

所以不管是publish还是lookup都依赖一个核心算法,即给出一个key, 找到离该key最近的k个节点。

该算法的大致流程是: 维护一个长度为k的列表l,它维护查询过程中离key最近的k个节点。 起初在自己的k-bucket里找出离key最近的k个节点放进l,轮个向它们查询。(被查询到的节点,返回它知道的离key最近的k个节点)。若收到返回值则用返回的新节点去更新l, 若长时间没响应,则从l里去掉,并从k-bucket里补充一个离key最近的节点。然后继续查询l里没有查询过的节点(补充的新节点)。 一直循环这个流程,直到l里的节点不再被更新为止,则此时l里的节点是该节点能够找到的离key最近的节点。

k-bucket的更新

当收到任意节点的消息时,不论是查询消息还是回复消息,都用它去更新k-bucket. 一句话总结:凡是遇到新节点,就用它去更新k-bucket.

k-bucket内的节点只在bucket满了并且有新节点更新的时候删除,这个时候找出最长时间没活跃的节点(LRU), ping它后没返回则删掉它,插入新节点;否则丢掉新节点。 一句话总结:偏爱旧节点。因为1. 如果一个节点长时间运行的话那么它很大概率上还会长时间的运行。2. 防止恶意节点的DOS攻击。

如果一个k-bucket 1h内没更新,则通过随机查询一个能落在k-bucket对应的key空间内的key来更新。

路由表的动态分裂

relax rules

(待补充) 结合relax rules, 可以应对unbalanced binary tree 的极端情况

bootstrap

一个新加入网络的节点,一定要至少知道一个其他节点,即bootstrap节点。向bootstrap查询自身,不仅快速地找到了离自己近的节点,而且还把自己的信息更新了出去。

参考

  1. Kademlia: A Peer-to-Peer Infomation System Based on then XOR Metric

lazyrobot.me