Kademlia协议简述

1 基本介绍

分布式哈希表（DHT ）是一类去中心化的技术，提供了节点之间的查找服务。通常在一个中心化系统中，中心节点可以负责管理子节点，告诉彼此位置，像Napster，虽然是点对点下载，但是查找资源的位置时，还是通过中心服务器获得的。而DHT解决的问题是，在一个没有中心化节点的系统中，各个节点如何相互发现、查找以及路由。其解决方案大体是每个节点各自按一定规则维护一个结构化的路由表，当有节点加入和离开的时候，更新自己的路由表，这样就可以按照这个规则互相查找了。

Kademlia协议（以下简称Kad）是一种DHT技术实现，除此以外，还有其他像Chord、CAN、Pastry等DHT实现。相较而言，Kad通过异或算法计算节点间距离，建立了一种全新的拓扑结构，使得路由的查询和跳转更加快速清晰。目前像BitTorrent、IPFS都是采用的类kad协议来做节点路由。

Kad协议论文可以参考这里: 英文版，中文翻译版。

2 协议要点

2.1 XOR

Kad协议中，节点的ID是160bit的值，两个节点间的距离采用两个节点ID异或（XOR）值表示。XOR来描述距离有以下几个特性：

每个点到自己的距离是0， d(x,x)=0
点到其他点的距离大于0， d(x,y)>0 (x != y)
点到其它点的距离等于其它点到自己的距离，d(x,y)=d(y,x)
点X到点Y的距离 + 点Y到点Z的距离 >= 点X到点Z距离， d(x,y)+d(y,z) >= d(x,z)

2.2 Kbuckets和路由表

Kad协议中，每个节点自己维护有路由表，对于位于[0,160)中的每个i，每个节点都保存有一个 <IP 地址， UDP 端口，节点 ID> 三元组列表，三元组中的节点 ID 为那些和其距离位于 2ⁱ 和 2⁽ⁱ⁺¹⁾之间的节点的 ID 。这些列表为 k-buckets。所以对于小的i值来说，k-buckets一般都是空的（因为不存在没有合适节点），对于大一些的i值，列表的长度可以扩展到k ， k是系统范围内定义的参数。

节点在将一个新节点加入路由表时，会将其插入相应的kbucket, 如果该kbucket已满而且包含自身节点，那么将该kbucket分裂成两个，并重新重复插入节点流程。

2.3 RPCs

Kad协议由4个RPC组成

PING : 对一个节点进行探测以确定其是否在线
STORE : 指示一个节点存储一个 <key,value> 对，以用于以后的获取
FIND_NODE : 向一个节点发送查询节点的请求，接收者要返回它所知道的距离目标最近的k个节点的三元组<IP 地址， UDP 端口，节点 ID> 列表
FIND_VALUE : 和 FIND_NODE 的行为相似，也是返回三元组 <IP 地址， UDP 端口，节点 ID> 列表，不过有一个例外。如果该 RPC 的接收者曾经收到过针对该 key 的 STORE请求，那么它仅返回所存储的值

所以Kad节点主要需要的事情就是找出距离给定节点ID最近的k个节点。其算法大体是：节点先从自己路由表中找到距离ID最近的K个节点，挑选出“aplha”个，“aplha”是一个系统范围并发参数，挑选出“aplha”个节点后，向其同时发送异步的 FIND_NODE RPC , 对于每一个获得的结果，对返回的结果中未联系过的的节点，再发送 FIND_NODE RPC，直到所有已知的节点都联系过，找出最近的K个节点。

3 Q&A

3.1 新节点如何加入网络

新节点u需要找到一个已在网络中的节点w,然后向w发起查找自身的请求(FIND_{NODE,参数为u})，

对于u来说，当连接上w的时候，已经将w加入自己的kbucket，

对于w来说，其向自己的距离u来说最近的kbucket中断å个节点同时发送查找u(FIND_{NODE,参数为u})的请求，每个请求一般会返回k个<ip,port,nodeid>节点。 u再比较(TODO 如何比较)所有这些节点，向其发送查找u的请求，知道返回最接近的节点， w会将k个距离u最近的节点返回给u。

u接受到w返回的k个节点后，根据这些节点更新自己的路由表，也就是相应的更新kbuckets.

3.2 TODO 如何查找某一资源

3.3 TODO 如何存储某一资源

3.4 TODO 某一点节点u如何寻找距离资源w最近的k个节点

3.5 TODO 算法层面上有哪些优化

3.6 TODO 亦或算法意义

4 我的实现

自己尝试用Commin Lisp实现Kad协议，项目在这里，项目结构参考了这个 python的实现。目前还只是完成了基本的几个RPC和初始的bootstrap，整体非常粗糙，对于论文中所提的一些优化和考虑还没有实现。在实践过程中遇到一个common lisp里并发异步地发送UDP的RPC请求的问题。

目前在项目里实现了一个基于udp的RPC框架，但还不能异步并发地执行。问题在于没有找到合适的同时发送udp请求方式。可以考虑的方式有基于 select, poll, epoll, kqueue 等的事件循环机制，或者采用多线程的方式。而在python里，有asyncio库可以方便地封装udp RPC，在golang里，也可以用goroutine方便地实现并发请求。为此我在reddit 的提问里有一些讨论。所以近期在看相关内容，有时间尝试下看能不能成功。