支持多关键字的P2P搜索技术研究.docx

支持多关键字的 p2p 搜索技术研究廖季萍 1，文大化 2，赵建平 1（1.长春理工大学 计算机科学技术学院，长春 130022； 2.中国科学院长春光学精密机械与物理研究所，长春 130033）摘 要：在结构化的 p2p 网络中，传统的资源搜索过程大多采用 dht 路由算法进行资源的定位和搜索，但这类网络只能支 持单一关键字的精确匹配查询。针对这个问题，本文提出混合式的 p2p 网络模型，并在此基础上实现了支持多关键字搜索 的搜索算法。首先为节点和资源关键字分配唯一的标识符，然后对资源关键字标识符进行拆分操作，并将拆分后的标识符 存储到相应的节点上。在搜索过程中，只需根据拆分后的标识符查找相应的节点即可。结果表明，采用这种搜索算法的网 络不仅能够支持多关键搜索，同时也能实现网络的负载均衡。关键词：p2p 网络；多关键字；负载均衡中图分类号： tn711 文献标识码：a 文章编号：1672-9870（2014）03-0128-04research on supporting multi-keyword search mechanism in p2p networksliao jiping1，wen dahua2，zhao jianping1（1.school of computer science and technology，changchun university of science and technology，changchun 130022； 2.changchun institute of optics，fine mechanics and physics，chinese academy sciences，changchun 130033）abstract： in structured p2p networks， traditional resource search processes are mostly based on dht routing algo- rithm， such networks can only support the exact matching queries of one single keyword .to solve this problem， in this paper a hybrid p2p network structure is presented； and a algorithm which support multi-keyword search is pro- posed.at first， a unique identifier is allocated for the nodes and the resource keywords， then the resource keywords identifier is split and stored in the corresponding nodes.in the search process，the corresponding nodes are searched ac- cording to the split identifiers to find the resources.the results show that not only multiple keywords can be supported but also load balancing is achieved in network by using this search algorithm.key words：p2p network；multi-keyword；load balancing目前，随着 p2p 技术的广泛应用，人们对基于 p2p 技术在资源共享方面的研究也越来越多。在 p2p 网络中，由于资源分布在网络的各个节点上，网 络中节点的动态加入与退出使得资源的定位与搜索 变得更加复杂，如何设定一个良好的 p2p 资源搜索 算法成为目前大多数 p2p 网络的核心问题。p2p 的搜索算法与 p2p 的网络结构息息相关。 目前可以把 p2p 的网络结构分成两类：一类是结构 化的 p2p 网络，另一类是非结构化的 p2p 网络1。 在非结构化的 p2p 模式中，资源的搜索主要采用泛 宏和随机转发机制，用 ttl 限制数据包的转发次数，在这种机制下，数据包转发量呈幂级增长，而且 可能错过网络中的某些资源，使资源定位无法得到 保证2。结构化的 p2p 网络模式利用 dht 技术组 织网络中的各个节点，通过规定的散列函数将资源 存储到各个节点上，然后使用特定的路由算法实现 资源的定位与搜索。采用 dht 的网络只能够支持 精确关键字查询，无法支持复杂查询3，然而通常情 况下，当用户搜索所需资源时，只能给出资源的部分 信息或大概描述，并不能给出精准的描述，此时在结 构化的 p2p 网络中研究一个能够支持多关键字搜索 功能的算法则十分有必要。收稿日期：2013-11-15作者简介：廖季萍 （1990-），女，硕士研究生，e-mail：776571925 通讯作者：赵建平 （1964-），男，博士，教授，博士生导师，e-mail：1研究现状为了在 p2p 网络中实现多关键字查询，研究人 员进行了大量的研究。广泛应用的解决方案是将查 询分成几个子查询集合，通过集合的交、差、并等操 作获得查询结果，在搜索过程中，节点每次将满足查 询的资源进行 and 操作，并将该结果转发给下一个 节点，最后把结果返回给资源请求端4。此外，还存 在 另 一 种 搜 索 算 法 ，该 算 法 结 合 了 bloom filter， cache 及增量式查询技术，其中，bloom filter 用于 压缩数据空间，cache 用于减少查询的次数，增量式 查询方法允许用户在发现返回结果数量足够时停止 搜索5。但是，在上述的解决方法中，节点的存储成 本和搜索成本都随着存储关键字和搜索关键字的增 加呈线性增长，显然，都不适用于查询关键字数量较 多的情况。2算法的实现2.1网络模型为了解决上述问题，我们提出了一个混合式的 结构化 p2p 网络模型，该网络的结构如图 1 所示，簇 首节点相互连接构成一个结构化的网络，簇内成员 构成一个非结构化的网络，共同承担存储负载，并向 簇首节点返回搜索结果。一般情况下，簇首的选择当前簇的簇首，再由该簇首转发给一个或多个其他 簇首成员，其他簇首收到存储请求后，将该索引存储 在本地或继续转发给其他簇首成员。当查找一个数 据项时，搜索请求通过簇首路由到其他簇首，其他簇 首收到查询请求后，将其转发给簇中的所有成员，查 看是否存在该资源，并将结果返回给发起查询的节 点，所有节点返回的结果集合就是查询的最终结果。2.2 bloom filter 技术的应用bloom filter 是一种二进制向量的数据结构，它 主要用于检测一个元素是否存在于一个集合。现假 设向量的长度为 m ，哈希函数的个数为 k ，且向量 中每位初始值均为 0，为了给元素创建 bloom fil- ter，首先使用这 k 个哈希函数得到 k 个不同的哈希 值，然后将向量中对应位置的值置为 1。因此，当需 要判断一个元素是否存在时，只需判断该元素经过 哈希运算后的值所对应的向量位的值是否都为 1。基于 bloom filter 的检测机制，本算法将其应 用在两个部分：（1）在共享资源的存储过程中，为资源关键字创 建 bloom filter，其创建过程如下：procedure bloomfilter（set a，hash functions， integer m）/set a 表示关键字集合/ 将 filter 数组所有元素初始化为 0采用的是加入网络时间先后原则，加入时间早的节filterm = 0点作为簇首，在各个簇首所组成的网络构建完成之 后，新节点即可选择一个簇首加入。foreach ai in a/对集合中的每个元素进行哈希运算 foreach hash function hj/将 filter 对应位置置为 1filterhj（ai ） = 1end foreach end foreach return filter（2）在资源搜索过程中，检测搜索的关键字是否 属于某个共享资源的关键字集合，其检测代码如下：procedure query（element，filter，hash functions）图 1 网络模型我们将一个共享资源的关键字集合称为数据/判断元素 element 是否存在foreach hash function hi/不存在返回 no项，该数据项可以包含一个或多个关键字且被多个if filterhi（element） ! = 1 return no节点所共享。在这种网络模型中，当对数据项进行 存储时，首先为其分配一个索引，并把该索引发送给end foreach/存在返回 yes130长春理工大学学报 （自然科学版）2014 年return yes2.3新节点的加入及标识符的分配传统的 dht 技术是通过对节点的 ip 地址进行 哈希运算，并将所得的哈希值作为节点的标识符，但 在本算法中我们对节点的 id 标识符进行了严格的 限制：将所有的 id 节点标识符划分为两类，一类是 firstclass，另 一 类 是 secondclass，其 中 ，firstclass 节点标识符只包含一位 1，secondclass 包含两位 1， 如表 1 所示。firstclass 由节点 id 标识符管理器分 配给簇首节点，firstclass 节点负责管理并分配 sec- ondclass 给簇内结点。为了实现 firstclass 节点对 secondclass 节点的管理，要求每个 secondclass 节 点 周 期 性 的 发 送 alive 消 息 给 firstclass 节 点 ，在 firstclass 节点收到消息后，更新本地的可用 sec- ondclass 的信息表。表 1 节点标识符的管理将该标识符分配给新节点，反之则将该信息路由到 其他 firstclass 节点上，直到新节点获得标识符。新 节点加入网络流程如图 2 所示。2.4 关键字的存储当共享资源的关键字被提取后，组成一个关键 字集合，我们称其为存储关键字集合。在对该集合 中的关键字进行存储时，我们将其映射到长度为 m 位的 bloom filter 中，并将这个 bloom filter 称为资 源描述符，显然它是由多个 0 和 1 组成。在本算法 中，为了能够方便的存储这 m 位的 bloom filter，我 们严格限制了节点 id 标识符的形式：所有的节点 id 标识符都必须是 m 位，并将其分成两类，一类是只 包含一位 1 的节点 id 标识符 firstclass，另一类是包 含两位 1 的节点 id 标识符 secondclass。那么，我们 可以将任意的资源描述符拆分成若干个 firstclass 和若干个 secondclass 标识符。现给定一个包含三个关键字 key1，key2，key3 的firstclass 000001000010000100001000010000100000secondclass无000011000110、000101001100、001010、001001011000、010100、010010、010001110000、101000、100100、100010、100001资源描述符 01010111，为了存储该资源，我们将该 描述符拆分成 01010000，00000110 及 00000001，并将拆分后的标识符直接路由到对应的节点上即可， 其存储过程如图 3 所示，关键字标识符如表 2 所示。存储关键字 key1 key2 key3图 3 资源存储过程 表 2 关键字标识符关键字标识符0000 00010000 01100101 0000图 2 新节点加入网络流程图当有新节点请求加入网络时，其请求信息将路 由给节点 id 管理器，在管理器收到消息后，检查是 否有可分配的 firstclass 节点标识符，若有，则将该 标识符分配给该节点；否则，管理器将该消息转发给 firstclass 节点，该节点根据本地的信息表判断是否 存在可分配的 secondclass 标识符，若存在，则直接2.5关键字的搜索在资源搜索过程中，一个查询可能包含一个或 多个关键字，这些关键字通过使用相同的散列函数 散列到一个 m 位的向量中，我们称这个向量为查询 描述符。当给定一个查询描述符后，我们将该标识 符拆分为若干个 firstclass 和若干个 secondclass 标 识符，在搜索过程中只需搜索相应的节点即可。根据资源的存储过程可知，搜索过程中所需搜索的节 点个数由查询描述符中 1 的个数所决定，可将其分 成以下三种情况：（1）至少包含三个 1 的向量。按照从左到右的 顺序，我们将三个连续的 1（忽视其中出现的 0）所出 现 的 位 置 表 示 成 left，center，right，然 后 搜 索 以 下 secondclass 节点：center 位置为 1，left 和 right 之间 有一位为 1，其他位为 0，如图 4 所示。为了缩小搜索 范围，提高搜索效率，通常选取当 right-left 值最小 时的位置。例如，给定一个查询描述符 10010010， 那 么 所 需 查 询 的 第 二 类 节 点 为 ：10010000、 01010000、00110000、00011000、00010100、00010010。图 4 至少包含三个 1 的向量搜索（2）只包含两个 1 的向量。按照从左到右的顺序 ，我 们 将 向 量 中 值 为 1 出 现 的 位 置 依 次 表 示 为left，right，其 搜 索 范 围 可 选 取1，right，也 可 选 取left，m，显然在上述两种情况下选择较小的范围 可以减少搜索的节点数，如图 5 所示。图 5 包含两个 1 的向量搜索（3）只包含 1 个 1 的向量。这种情况下不需要限 定其搜索范围，直接根据向量搜索对应的节点即可。2.6 网络路由及负载均衡该算法中的路由方式分为两级：簇首网络路由 和簇内成员网络路由，簇首网络路由承担该网络的 全局路由，簇内成员网络路由承担网络的局部路 由。节点的路由查询首先确定目标簇首节点，簇首 节点内部通过簇内节点的网络机制实现目标节点的 定位。在本算法中，簇首路由采用 pastry 算法，簇内 成员路由采用 flooding 机制。在该网络模型下，簇首节点被设置成一个动态平衡的模型，当簇首节点内的簇内成员数达到一个 临界点时，需要对簇内成员进行分裂或合并操作。在本算法中，我们设置了一个定时器，当簇内成员节 点数达到分裂或合并的临界点超过时间阈值后，便 开始实施分裂或合并，使网络保持负载均衡。3实验结果为了对该算法性能进行评估，我们现假设向量 m=128，散 列 函 数 为 sha1，网 络 中 的 节 点 数 为 1000，比较该算法和利用倒排列表算法在搜索过程 中分别访问的节点数，如图 6 所示