一个小巧的DHT/KAD实现(来自transmission-2.33)

昨天下载了 transmission-2.33, 大致浏览的代码。发现很代码的third-party目录里面有个很小巧的dht实现。

只有三个文件就可以实现dht的功能: dht.c dht.h dht-example.c，并且接口很简单，复用性很好。
粗略的阅读了一下代码，把大致的实现思路整理如下(后面会贴出代码)：

代码分成三部分:
1、路由表的插入操作。
1）如果节点已经在路由表中，则更新节点，返回。
2）如果桶没有满，则插入，返回。
3）如果发现失效节点，替换，返回。
4）发现可疑节点，则保存新节点到缓存中并且如果该可疑节点没有ping,发出ping_node操作，返回。
5）现在，桶已经充满了好的节点，如果自己的ID没有落在这个桶中，返回。
6）将桶空间分成两半。跳到步骤1）。

2、KAD远程处理调用。
这部分又分成3种，
1）ping/pong操作。
所有的包的tid都使用pg\0\0
2）find_node操作。
所有的包的tid都使用fn\0\0
3）get_peers/annouce_peer操作。
对同一个HASH的一次递归查询中，tid保持不变。
其中只有3)种实现bittorrent的DHT规范里面提到的递归查询操作，1)和2)仅仅用来维护路由表，并且不保存状态。

3、定时器处理：
为了检测路由表中节点的有效性（根据规范，路由表中应该只保存有效节点），在代码中，在执行krpc操作时如果发现时对路由表中的节点操作，那么则保存操作的开始时间 pinged_time，通过操作的开始时间来判断操作是否超时。

expire_stuff_time 超时时，会执行下面的操作:
1、检查路由表中失效的节点（根据pinged_time来判定），并将该节点删除。
2、检查用来保存annoounce_peer的节点是否超过30分钟（这个不打算深入讨论，故不做解析）。
3、检查递归查询操作超时。

rotate_secrets_time 定时器。
用来每隔大约15分左右就更换token(见DHT规范).

confirm_nodes_time 定时器。
查找长期没有活动的桶，然后通过执行一个find_node的krpc操作来刷新它。

search_time定时器。
有可能出现发出的所有的get_peers操作，都没有应答，那么search_time定时器遇到这种情形时负责重发所有请求。（注意: get_peers操作最大未决的krpc请求数是3）

用于维持路由表的ping/pong操作:
在试图插入节点时，发现桶已经满，而存在可疑节点时会触发ping_node操作。未响应的节点会有可疑最终变为失效节点，而被替换。

缺点就是完成整个路由引导的速度比较慢。

其实，我自己也写过一个DHT的实现，不过估计相对来说，应该会需要更多的带宽。