文档介绍：一种精确的基于DHT的p2p网络搜索算法与网络拓扑模型
一、目前的p2p搜索算法研究状况及其缺点
     目前对于p2p系统的自动搜索算法研究已经成为p2p研究的一个热点。最初的p2p系统,如Napster,采用的是中心服务器式的搜索算法,在这样的系统中,中央搜索服务器很容易就成为系统性能的瓶颈和不稳定的根源。其后的一些系统,如Gnutella,采用的是分布式的搜索算法,查找按照简单洪泛(flooding)的方式进行。查找命令首先传播到用户的所有相邻结点,然后再传播到相邻节点的相邻节点,直到达到预先确定的层次为止。这样的查找算法无疑会造成巨大的带宽和资源浪费。
     现在的分布式p2p系统普遍采取的是DHT(Distributed Hash Table,分布式哈希表)搜索方法。该方法的思想是:每一份资源都由一组关键字进行标识。系统对其中的每一个关键字进行hash,根据hash的结果决定此关键字对应的那条信息由哪个用户负责储存。用户搜索的时候,用同样的算法计算出每个关键字的hash,再根据hash知道该关键字对应信息的储存位置,从而能够迅速定位资源的位置。下面举例说明。
     例如某份文件名为““。当用户共享此文件时,客户端把““这个字符串进行分词,结果可能是"雪","狼","湖","mp3"(其中点号已经被自动去掉)四个词。我们假设上面几个词的hash结果分别为15,26,37,48。DHT一般规定系统中第一个id号比hash值大的用户(记作newid=ess(hash),下同),负责保存这些关键字所对应的信息。假设此时系统中有id号分别为1, 9, 11, 19, 21, 29, 31, 39, 41几个用户,那么其中id=19的用户应当储存“雪”字对应的信息(可能包括文件hash,用户id等等)。同样id=29的用户储存“狼”字对应的信息,如此类推。
     用户在搜索关键字“雪狼湖”的时候,客户端用同样的分词算法分得"雪","狼","湖"三词,并用同样的方式确定了这三个词分别由id=19, id=29, id=39的用户保存,于是客户端就分别向这三个用户发出查询请求。这三个用户分别将每个关键字对应的文件信息返回,客户端再将其中不包括所有关键字的信息过滤掉,最后将结果文件列表上报给用户,搜索完成。
     这种DHT算法有多个变体,如Chord,CAN,Pastry,Tapestry等等,这几个系统的区别主要是路由算法的不同,在资源定位方法上并无不同。
我们先讨论资源定位的方法,第三章再讨论网络拓扑模型与路由算法。
     一般认为,用这种DHT算法,用户基本上都可以在一次跳转之内得到查找结果,所以非常方便。每个用户要储存的数据=平均文件数*平均每文件关键字数,与系统规模无关,所以采取这种方案的系统可以支撑起非常多的用户。
但是用户加入和退出时,相关的用户要进行处理,这方面的花销比较大,所以当用户频繁加入和退出时,有可能导致系统性能的下降。这方面的处理算法,可以参考其它文献,这里仅指出一点:通常,用户上线下线对系统的影响是按O(logN)的方式随用户数增大而递增的。
     这种算法最大的问题在于:无法精确查找,往往会浪费很多带宽。以上面的搜索“雪狼湖”为例,系统中所有关于“雪”,“狼”,“湖”的文件信息都会返回给搜索者,搜索者需要过滤掉不包含所有关键词的条目,才能得到比较精确的结果。我们知道,查找单独一个关键字的结果往往是非常多的,所有包含“雪”字的文件中,可能只有不到1%的文件含有完整的“雪狼湖”一词。因此这种算法中,%的搜索都是无用功,带宽和CPU资源的浪费非常大。
   
二、改进的DHT算法
 改进的DHT算法中,每个用户储存的信息不是文件的信息,而是其它用户的信息。
     前面所说的DHT算法中,一般每个关键字所指向的值都是文件的hash(可能还有用户id,扩展资料等信息)。实际上,我们只要将关键字对应的值改为用户id和地址即可,不需要保存文件的信息。
     搜索者在搜索一组关键字的时候(这组关键字之间可以有并、或、减等通用的逻辑运算符),用同样的算法可以定位关键字信息的保存位置(即用户,可称为关键字保存者),然后向这个位置查询,得到一组与查询的关键字联系的用户列表。搜索者再对各个关键字对应的用户列表的并、交、相减,最后得到可能拥有所需信息的用户(以下简称目标用户)列表。
客户端得到目标用户列表后,再逐个向这些用户发送查询请求。目标用户进行精确搜索后将结果返回,搜索完成。
     这样,搜索被划分为两步进行:首先根据关键字组得到目标用户列表,再对目标用户逐个进行精确查找。这种搜索的速度比通常的DHT要稍慢一些,