2024年6月11日发(作者：)

P2P中DHT网络介绍

作者

撰写时间 2010年5月5日

文档类型 研究小结

文档状态 草稿

一、P2P及DHT网络简单介绍：

P2P在思想上可以说是internet思想/精神/哲学非常集中的体现，共同的参与，透明的开放，平等的

分享（让我想起之前学习过的，现在正在疯狂热炒的云计算的“中央集权”制度）。基于P2P技术的应用

有很多，包括文件分享，即时通信，协同处理，流媒体通信等等。通过这些应用的接触，分析和理解，P2P

其本质是一种新的网络传播技术，这种新的传播技术打破了传统的C/S架构，逐步地去中心化，扁平化，

这或许在一定程度上应证了”世界是平的”趋势，呵呵。P2P文件分享的应用(BTs/eMules等)是P2P技术最

集中的体现，我们这里的研究也是以P2P文件分享网络作为入口，P2P文件分享网络的发展大致有以下几

个阶段，包含tracker服务器的网络，无任何服务器的纯DHT网络， 混合型P2P网络。DHT网络发展

即有“思想/文化”上的“发展”，也有一定的商业上的需求（版权管理）。

DHT全称叫分布式哈希表(Distributed Hash Table)，是一种分布式存储方法，一类可由键值来唯

一标示的信息按照某种约定/协议被分散地存储在多个节点上，这样也可以有效地避免“中央集权式”的服

务器（比如：tracker）的单一故障而带来的整个网络瘫痪。实现DHT的技术/算法有很多种，常用的有：

Chord, Pastry, Kademlia等。我们这里要研究的是Kademlia算法，因为BT及BT的衍生派（Mainline,

Btspilits, Btcomet, uTorrent…），eMule及eMule各类Mods(verycd, easy emules, xtreme…)等

P2P文件分享软件都是基于该算法来实现DHT网络的，BT采用Python的Kademlia实现叫作khashmir

（科什米尔，印巴冲突地带？），有如下官网。eMule采用C++的Kademlia实现干脆就叫作Kad，当然

它们之间有些差别，但基础都是Kademlia。我们这里以BT-DHT为例进行分析介绍，下面说到的DHT

都可以默认是BT-Kademlia-DHT。

官方网站：/trac/wiki/Khashmir

二、Kademlia实现原理

各种DHT的实现算法，不论是Chord, Pastry还是Kademlia，其最直接的目标就是以最快的速度

来定位到期望的节点，在P2P文件分享应用中则是以最快的速度来查找到正在分享某一文件/种子的peers

列表信息。因为每个节点都是分布式存在于地球的任何角落，如果用地理距离来衡量两节点间的距离则可

能给计算带来极大复杂性甚至不可能进行衡量，因此基本所有的DHT算法都是采用某种逻辑上的距离，在

Kademlia则采用简单的异或计算来衡量两节点间的距离，它和地理上的距离没有任何关系，但却具备几

何公式的绝大特征：

（1）节点和它本身之间的异或距离是0

（2）异或距离是对称的：即从A到B的异或距离与从B到A的异或距离是等同的

（3）异或距离符合三角形不等式：给定三个顶点A B C，假如AC之间的异或距离最大,那么AC之

间的异或距离必小于或等于AB异或距离和BC异或距离之和.

Kademlia中规定所有的节点都具有一个节点ID，该节点ID的产生方法和种子文件中的info hash采用相

同算法:即sha-1（安全hash算法），因此每个节点的id，以及每个共享文件/种子的info-hash都是唯一

的，并且都是20个字符160bits位组成。两个节点间的距离就是两个节点id的异或结果，节点离键值（种

子）的距离为该节点的id和该种子文件的info-hash的异或结果。Kademlia在异或距离度量的基础上又把

整个DHT网络拓扑组织成一个二叉前缀树（XuanWu系统中arp的实现则是一个例子），所有的节点(所

有的正在运行的，并且开取了DHT功能的Bt,Btspilits应用)等作为该二叉前缀树的叶子节点，可以想象

这棵二叉树可以容纳多达2

128

个叶子（节点），这足以组织任何规模的网络了。对于每个节点来说按照离自

己的远近区域又可以把这棵树划分为160棵子树，每一个子树和该节点都有一个共同的前缀，共同前缀越

少离得越远。如下图所示：

（4）对于给定的一个距离，距离A只存在有唯一的一个节点B，也即单向性，在查找路径上也是单

向的，这个和地理距离不同。