Kademlia协议

Kademlia协议

 

 

1. ID and Key

 

Node ID：160 bit （每一个Node拥有一个ID，随机产生）

Key：160 bit （Key也许是某个很大的数据的SHA-1 hash值）

 

(Key,Value)这一对数据保存在ID最“接近”Key的Node上。

“接近”的意思是Key和ID之间的“距离”很短。

Kad网络中“距离”的定义是：d(x,y) = x XOR y，也就是x和y的异或值。

 

* 选择XOR作为衡量距离的尺度，是因为XOR有xxx,yyy,zzz,...等特性，具体请看Kademlia的paper [1] section 2.1。

 

2. k-bucket

 

每一个Node保持160个 list。对于第 i (0 <= i < 160) 个 list，此 list 中保存着和该 Node 距离为 2*i ~ 2*(i+1) 【2的 i 次方到 2的 i+1 次方】的一些 Node 的信息（Node ID，IP地址，UDP端口）。这些 list 叫做 k-bucket 。k是每一个 listk 中保存的 Node 的最大

个数（比如，20）。

 

        +------------------------+

list 0: |                        |   距离为[1,2)的node 

        +------------------------+

（ID前159 bit相同，第160 bit一定不同的node: 1个）

 

        +------------------------+

list 1: |                        |   距离为[2,4)的node 

        +------------------------+

（ID前158 bit相同，第159 bit一定不同的node: 2个）

 

        +------------------------+

list 2: |                        |   距离为[4,8)的node 

        +------------------------+

（ID前157 bit相同，第158 bit一定不同的node: 4个）

 

        +------------------------+

list 3: |                        |   距离为[8,16)的node 

        +------------------------+

（ID前156 bit相同，第157 bit一定不同的node: 8个）

 

        +------------------------+

list 4: |                        |   距离为[16,32)的node 

        +------------------------+

（ID前155 bit相同，第156 bit一定不同的node: 16个）

 

。

。

。

          +------------------------+

list 159: |                        |   距离为[2*159,2*160)的node 

          +------------------------+

（ID第1 bit不同的node: 2*159个。此list中最多保存最近访问的k个）

 

每一个list （k-bucket）中的node按照访问的时间顺序排列，最先访问的在list头部，最近访问的在list的尾部：

 

Head                                        Tail

 |                                           |

 V                                           V

+--+   +--+   +--+   +--+   +--+            +--+

|  |-->|  |-->|  |-->|  |-->|  |--> ... --> |  |

+--+   +--+   +--+   +--+   +--+            +--+

Node0  Node1  ...                           Node[N]

 A                                            A

 |                                            |

least-recently                              most-recently

 

3.k-bucket的刷新

 

当一个Node收到另一个Node发来的消息的时候，它根据以下规则（least-recently seen eviction policy）来刷新相应的k-bucket:

 1) 如果发送者已经在某一个k-bucket中，将它在该 k-bucket 中移动到尾部

 2) 如果发送者不在其对应的k-bucket中，并且该 k-bucket 还不满 k 个Node，将这个发送者加入到 k-bucket 的尾部

      如果该 k-bucket 已经满了（有k个Node），那么接受消息的 Node 向该 k-bucket 中最老的（也就是头部的）Node发送一个 ping 消息

        如果这个最老的 Node 没有响应，则将它从 k-bucket 中删除，将新的发送消息的 Node 加入到 k-bucket 的尾部

        如果这个最老的 Node 响应了，则将它移动到 k-bucket 的尾部，并抛弃新的 Node 的信息

 

* 为什么要采取这样的规则，请看Kademlia的paper [1] section 2.2

 

4. 基本协议(protocol)

 

四种基本的RPC：PING, STORE, FIND_NODE, FIND_VALUE

 

1) PING

PING 探测一个Node是否在线

 

2) STORE

STORE 以(Key,Value)为参数。指示另一个Node（消息接收者）保存一个(Key, Value)对，以供以后取用。

 

3) FIND_NODE

FIND_NODE 以一个160 bit的ID作为参数。接收者返回它所知道的最接近该ID的 k 个 Node 的 Contact 信息（ID,UPD Port,IP）。这些 Node 不一定要从同一个 k-bucket 中产生。除非它所有的 k-bucket 中所有的 Node 加在一起都不到 k 个，否则它必需凑足 k 个。

 

4) FIND_VALUE

FIND_VALUE 以一个160 bit的ID/Key作为参数。如果接收者先前已经收到一个 STORE RPC，而且 STORE 的参数之一 Key 就是当前 FIND_VALUE 的参数，那么，接收者将 STORE 的另一个参数 Value 返回给发送者。否则，FIND_VALUE 和 FIND_NODE 一样，返回它所知道的最接近该ID的 k 个 Node 的 Contact 信息（ID,UPD Port,IP）。

FIND_VALUE 的意思就是：如果接收者有发送着所要的 Value，就将该 Value 返回。否则，接收者就帮忙找更接近该 ID/Key 的 Node。

 

所有的 RPC 消息都带有一个 160 bit的随机 RPC ID，由发送者产生，接收者在响应每一个消息的时候，返回的消息里面都必需拷贝此 RPC ID。目的是防止地址伪造。PING 消息可以在 RPC 响应里使用捎带确认机制来获得发送者网络地址（原文：pings can also be piggy-backed on RPC replies for the RPC recipient to obtain additional assurance of the sender's network address.）。

 

* piggyback

  捎带确认(法)

  A technique used to return acknowledgement information across a full-duplex  (two-way simultaneous) data link without the use of special (acknowledgement) message. The acknowledgement information relating to the flow of message in one direction is embedded (piggybacked) into normal data-carrying message flowing in the reverse direction.

  经全双工(双向同时)数据链路,不用专门(确认)报文返回确认信息所用的技术。与一个方向的报文流有关的确认信息钳在反方向正常携带数据的报文流中。

 

5. 节点查找(node lookup)

node lookup:找到距离给定的 ID 最近的 k 个 node

定义 a:系统范围内的并发参数，比如3。

步骤：

 1) 从最近的 k-bucket 里面取出 a 个最近的 node，然后向这 a 个 node 发送并行的、异步的 FIND_NODE RPC。

 2) 再次发送 FIND_NODE RPC 给从前一步返回的 node（这一步可以不必等到前一步中所有 a 个 PRC 都返回之后才开始）：

    从发送者已知的 k 个最接近目标的 node 当中，取出 a 个还没有查询的 node，向这 a 个 node 发送 FIND_NODE RPC。

    没有迅速响应的 node 将被排除出考虑之列，直到其响应。

    如果一轮 FIND_NODE RPC 没有返回一个比已知的所有 node 更接近目标的 node，发送者将再向 k 个最接近目标的、还没有查询的 node 发送 FIND_NODE RPC。

 3) 查找结束的条件：发送者已经向 k 个最近的 node 发送了查询，并且也得到了响应。

 

6. 存储<Key, Value>(store a <Key,Value> pair)

步骤：

 1) 使用node lookup算法，找到距离 Key 最近的 k 个 node

 2) 向这 k 个 node 发送 STORE RPC

 3) 每一个 node 必要的时候重新发布(re-publish)所有的<Key,Value>

    （对于当前的 Kademlia 应用(文件共享)，每一个<Key,Value>的原始发布者被要求每隔24小时重新发布一次，否则<Key,Value>将在发布之后的24小时之后过期。对于其他一些应用，比如digital certificates, cryptographic hash to value mapping，过期时间可以更长一些）

 

7. 搜索<Key,Value> （find a <Key,Value> pair)

步骤：

 1) 使用 FIND_VALUE 代替 FIND_NODE 进行"node lookup"过程。一旦任何其他 node 返回了所要的 Value，搜索的过程就结束。

 2) cache: 如果搜索成功，搜索的发起者将这个<Key,Value>对存储到已知的、最近的、但是在第一步中没有返回该 Value 的 node 上。

    显然，有了cache之后，以后对于该 <Key,Value> 的搜索很可能首先找到 cache，而不是直到找到最接近 Key 的那个 node。

    如果一个 <Key,Value> 被频繁的搜索，那么它很可能被缓存到很多 ID 不太接近 Key 的 node 中。

    为了避免过度缓存(over-caching)，每一个 <Key,Value> 都有一个过期时间，这个过期时间和 当前node 和“最接近Key之node”之间的 node 的个数（这个数目可以从当前node的bucket接口推断出）的指数倒数成正比。（To avoid "over-caching", we make the expiration time of a <key,value> pair in any node's database exponentially inversely proportional to the number of nodes between the current node and the node whose ID is closest to the key ID. This number can be inferred from the bucket structure of the current node）

 

8. 刷新bucket (refresh bucket)

 所有的 bucket 通过node之间的请求来刷新。

 如果某一个bucket在过去一个小时之内没有任何的node lookup操作，那么这个node就随机搜索一个在这个bucket覆盖范围内的ID。

 

9. node加入网络

步骤：

 1) 一个新加入的node（假设为u）必需首先获得一个已经在网络中的node（比如为w）的contact信息。

 2) u 首先将 w 加入到其对应的 k-bucket 中

 3) u 执行一个对自己ID的 node lookup 操作

 4) u 刷新所有的 k-bucket