eMule中的分布式哈希表技术:Kademlia中的分布式哈希表技术前两天在网上看到世界知名的电骡服务器Razorback2被查封、4人被拘禁的消息，深感当前做eMule/BitTorrent等P2P文件交换软件的不易。以分布式哈希表方式(DHT，DistributedHashTable)来代替集中索引服务器可以说是目前可以预见到的为数不多的P2P软件发展趋势之一，比较典型的方案主要包括：CAN、CHORD、Tapestry、Pastry、Kademlia和Viceroy等，而Kademlia协议则是其中应用最为广泛、原理和实现最为实用、简洁的一种，当前主流的P2P软件无一例外地采用了它作为自己的辅助检索协议，如eMule、Bitcomet、Bitspirit和Azureus等。鉴于Kademlia日益增长的强大影响力，今天特地在blog里写下这篇小文，算是对其相关知识系统的总结。1.Kademlia简述Kademlia(简称Kad)属于一种典型的结构化P2P覆盖网络(StructuredP2POverlayNetwork)，以分布式的应用层全网方式来进行信息的存储和检索是其尝试解决的主要问题。在Kademlia网络中，所有信息均以<key,value>的哈希表条目形式加以存储，这些条目被分散地存储在各个节点上，从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典：只要知道了信息索引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，而不管这个value信息究竟是存储在哪一个节点之上。在eMule、BitTorrent等P2P文件交换系统中，Kademlia主要充当了文件信息检索协议这一关键角色，但Kad网络的应用并不仅限于文件交换。下文的描述将主要围绕eMule中Kad网络的设计与实现展开。2.eMule的Kad网络中究竟存储了哪些信息网络中究竟存储了哪些信息?只要是能够表述成为<key,value>字典条目形式的信息Kad网络均能存储，一个Kad网络能够同时存储多张分布式哈希表。以eMule为例，在任一时刻，其Kad网络均存储并维护着两张分布式哈希表，一张我们可以将其命名为关键词字典，而另一张则可以称之为文件索引字典。a.关键词字典：主要用于根据给出的关键词查询其所对应的文件名称及相关文件信息，其中k关键词字典ey的值等于所给出的关键词字符串的160比特SHA1散列，而其对应的value则为一个列表，在这个列表当中，给出了所有的文件名称当中拥有对应关键词的文件信息，这些信息我们可以简单地用一个3元组条目表示：(文件名，文件长度，文件的SHA1校验值)，举个例子，假定存在着一个文件“warcraft_frozen_throne.iso”，当我们分别以“warcraft”、“frozen”、“throne”这三个关键词来查询Kad时，Kad将有可能分别返回三个不同的文件列表，这三个列表的共同之处则谟谒蔷乓桓鑫募皐arcraft_frozen_throne.iso”的信息条目，通过该条目，我们可以获得对应iso文件的名称、长度及其160比特的SHA1校验值。b.文件索引字典用于根据给出的文件信息来查询文件的拥有者(即该文件的下载服务提供者)，文件索引字典：其中key的值等于所需下载文件的SHA1校验值(这主要是因为，从统计学角度而言，160比特的SHA1文件校验值可以唯一地确定一份特定数据内容的文件)；而对应的value也是一个列表，它给出了当前所有拥有该文件的节点的网络信息，其中的列表条目我们也可以用一个3元组表示：(拥有者IP，下载侦听端口，拥有者节点ID)，根据这些信息，eMule便知道该到哪里去下载具备同一SHA1校验值的同一份文件了。3.利用Kad网络搜索并下载文件的基本流程是怎样的网络搜索并下载文件的基本流程是怎样的?基于我们对eMule的Kad网络中两本字典的理解，利用Kad网络搜索并下载某一特定文件的基本过程便很明白了，仍以“warcraft_frozen_throne.iso”为例，首先我们可以通过warcraft、frozen、throne等任一关键词查询关键词字典，得到该iso的SHA1校验值，然后再通过该校验值查询Kad文件索引字典，从而获得所有提供“warcraft_frozen_throne.iso”下载的网络节点，继而以分段下载方式去这些节点下载整个iso文件。在上述过程中，Kad网络实际上所起的作用就相当于两本字典，但值得再次指出的是，Kad并不是以集中的索引服务器(如华语P2P源动力、Razorback2、DonkeyServer等，骡友们应该很熟悉吧)方式来实现这