基于去中心化索引的IPFS数据获取方法研究

石秋娥，周 喜，王 轶

1.中国科学院 新疆理化技术研究所，乌鲁木齐 830011

2.中国科学院大学，北京 100049

3.中国科学院 新疆理化技术研究所 新疆民族语音语言信息处理实验室，乌鲁木齐 830011

随着计算机技术的发展，数据的规模量级也不断提高，去中心化数据存储方式可以满足大数据环境下的数据存储需求。星际文件系统[1]创造了一个点对点（peerto-peer，P2P）的分布式文件系统，升级了现有的网络结构，实现了真正意义上的去中心化存储。

每一个上传到IPFS系统中存储的文件，系统都会返回一个唯一的文件标识符CID，但是资源请求者只有准确提供CID才能下载IPFS中相应文件。IPFS仅支持基于CID的数据获取方式，制约了它的应用。由于缺乏相应的搜索功能，资源请求者很难通过关键词或者其他描述信息获取相关数据。研究IPFS的数据获取方法，可以帮助用户根据自身需求搜索数据，有利于IPFS数据的共享与发现，使IPFS满足更多的应用场景。此外，当文件标识符丢失或遗忘时，可以通过其他方式获取原来的数据，避免数据的“失联”。

在IPFS之上建立数据检索层可以解决数据获取问题。传统的集中式索引虽然容易实现、便于管理，但是削弱了IPFS的去中心化程度，并限制IPFS网络的可伸缩性。在为IPFS建立去中心化索引方面，已有研究实现的都是基于关键词的索引，没有充分考虑长查询和短查询之间的区别，一般认为三个以上关键词的查询属于长查询[2]，将长查询分词为多个关键词进行搜索会对网络造成更多的负担。为使数据的获取更加高效，引入了缓存机制，由发布搜索的节点缓存相关结果，却忽视了搜索发布节点与相关结果存储节点之间的距离，使网络中存储大量不必要的冗余数据，未充分利用缓存空间。

基于此，本文针对缓存空间的浪费问题，改进了缓存存储机制，降低其所占存储空间。针对IPFS数据获取问题，设计了一种去中心化混合索引，使得搜索在长短查询上都能有较好的表现，对长查询语句，使用word2vec[3]建立句子索引，使语义内容相似的句子索引能够相邻存储，以有效获取IPFS系统数据。

1 相关工作

目前，关于IPFS的数据获取这一方面的研究比较少，还没有成熟的解决方案。IPFS-search[4]是github上的一个开源项目，该项目尝试在IPFS上建立一个基于Elasticsearch的集中式搜索引擎，能为用户提供关键词搜索功能。然而集中式索引的服务器面临着更多的攻击，对存储能力的要求也更高。文献[5]提出为IPFS建立一个去中心化的搜索引擎，建立关键词和CID的倒排索引，并使用DHT存储索引文件，通过缓存层和过滤器加快搜索过程，该方法在较短的平均查询时间内取得了较好的缓存命中率，但是当查询语句有多个关键词，对每个关键词分别进行搜索会增加网络的通讯路由。Desema[6]是一个基于IPFS和区块链的去中心化服务市场，使用IPFS存储数据，并通过区块链共享IPFS数据。虽然解决了区块链存储限制，但区块链上实现的仍然是基于CID的数据获取方式。Zhu等人[7]以去中心化的B+树和HashMap为IPFS等去中心化存储数据建立索引，实现了关键字搜索功能。基于DHT的索引结构存在大量相关工作，文献[8-9]结合向量空间模型（VSM）和潜在语义索引（LSI）将文档表示为笛卡尔空间的向量，但是其计算过程中对文档矩阵进行SVD分解的计算代价太大，时间复杂度是O(N2)，空间复杂度O(N3)。Reynolds等人[10]提出使用布隆过滤器和缓存加快DHT网络中关键词搜索过程，然而缓存也增加了大量的冗余数据。Hassanzadeh等人[11]提出了LANS和GLARAS方法，分别为节点分配地址及放置副本，使系统中每对节点之间的延迟对应于其地址的公共前缀长度，该方法提高了地址的位置感知能力，降低了搜索的端到端延迟及平均访问延迟。Joung等人[12]使用超立方体索引关键字，相似关键字集的对象很可能被映射到彼此接近的点，削弱了DHT的哈希映射方式对数据邻近性存储的破坏。Armada[13]和LIGHT[14]通过使用前缀哈希树（PHT）分布其索引结构，在DHT上实现轻量级的范围查询。而Echo[15]则使用了一种新的分布式结构TRT来扩展前缀哈希树（PHT），通过TRT提高范围查询的效率。Ngom等人[16]提出一种名为摘要前缀树（SPT）的新结构来解决DHT上关键词超集搜索问题。董祥千等人[17]使用局部敏感哈希（locality sensitive Hashing，LSH）建立基于DHT的域索引，但主要是针对结构化数据集的连接搜索问题，仅对结构化数据开展了实验。虽然目前关于IPFS数据获取的研究有了一定进展，但是对长查询带来的网络负担及搜索效率问题并没有很好的解决方案。

因此本文为IPFS数据建立去中心化混合索引，并利用DHT网络存储索引文件，实现IPFS的数据获取。主要工作如下：第一，将文件存储在IPFS得到的CID值与文档关键词组合，构成关键词索引发布到DHT网络中存储，然后计算文档的句子索引并存储在DHT网络中；第二，节点对搜索结果缓存，加快后续相同查询的搜索过程；第三，对长查询进行句子搜索，可以在索引存储节点的邻近范围搜索；对短查询，提取关键词后对每个关键字分别搜索。

2 相关技术

2.1 星际文件系统

IPFS系统并不是一个全新的技术，而是集成并充分利用了BitTorrent、Git、P2P和密码学等已有的技术[1]。IPFS系统中，以256 KB为块大小对文件进行分块存储，每个分块会分散存储在IPFS网络中的节点上，如果文件小于256 KB则直接存储。如图1所示，IPFS对文件分块后，会计算每一个块的哈希值，然后将所有块的哈希值拼凑起来，再做一次哈希运算，从而得到最终哈希值，即文件的唯一标识符称为CID。资源请求者只需要使用CID就可以在IPFS网络中下载相应文件[18]。

图1 文件唯一标识符的生成过程Fig.1 Generation process of unique content identifier

2.2 分布式哈希表

DHT是一种用于在分布式系统中存储大量数据的数据结构，目前已经得到了广泛的应用，P2P、IPFS、区块链等系统使用DHT作为底层架构。在DHT网络中节点是动态变化的，一个节点很难获取并存储全网节点的相关信息，因此采用每个节点仅负责维护部分路由信息的网络拓扑结构。DHT网络使用哈希算法为每个节点分配一个节点地址（nodeID），为资源计算一个唯一标识的键值，使节点nodeID和资源键值具有相同值域，将资源存储在nodeID与资源键值相同或相近的节点。为了实现网络中资源的快速查找和定位，需要借助能保证路由查询收敛的路由算法。相关的实现算法有很多，例如CAN[19]、Chord[20]、Kademlia[21]。DHT网络具有以下特性：

（1）鲁棒性。DHT能够支持节点频繁地加入和退出网络，DHT具有良好的可扩展性。

（2）负载均衡。DHT通过哈希运算向网络分配资源，能一定程度上实现负载均衡[22]。

（3）可用性。同一资源在多个节点存储，单点故障或节点退出网络时保证资源的可用性。

（4）高效性。在具有N个节点的网络中，DHT保证路由收敛，在有限跳数内可以查找到目标资源。

3 总体结构设计

图2为IPFS数据获取方法IPFS-DDAM（IPFSdecentralized data acquisition method）的过程总览图。该方法主要包括：索引构建、索引存储、搜索过程、结果缓存等几个过程。如图2所示，步骤1~4为索引构建和索引存储过程，步骤a~e为搜索过程。

3.1 索引构建及存储

图2中步骤1~4为索引构建及索引存储过程。首先，文件拥有者将文件上传到IPFS系统中存储，IPFS会返回文件唯一标识CID；然后，需要对文件建立两种索引，一种是关键词索引，对文件进行关键词提取，由这若干个关键词与CID组合构成若干个关键词索引，另一种是句子索引，对提取出来的关键词或文档的中心句使用机器学习的方法构建文档的句子向量表示，由降维后的句子向量和CID构成句子索引；最后，将生成的句子索引及关键词索引发布到DHT网络中存储。IPFS网络和DHT网络只是逻辑上的划分，物理上同一节点可以同时属于两个网络。

图2 IPFS-DDAM过程总览图Fig.2 Overview of IPFS-DDAM

3.1.1 关键词索引

本文为IPFS系统实现了基于关键词的搜索功能，使用TF-IDF[23]（term frequency-inverse document frequency）算法提取文档的前n个或者权重大于阈值的关键词(k1,k2,…,k n)，每个关键词经过哈希运算得到的关键词哈希与文档CID组成键值对，即为关键词索引。关键词哈希与nodeID具有相同值域。每个索引存储节点负责存储与其nodeID相同或相近的关键词索引。

3.1.2 句子索引

为了将句子索引存储在DHT网络中，句子索引一方面需要体现文档的内容，另一方面需要与DHT网络的节点地址具有可映射性。为了使句子索引反映文档内容，本文提出了一种使用机器学习的方式计算句子索引——SICP（sentence index calculation process）。首先，提取文档的中心语句，分词后得到若干关键词(k1,k2,…,k n)，或者使用TF-IDF算法提取文档的前n个或者权重大于阈值的关键词；然后采用word2vec将关键词转为词向量表示：

其中，dimt i(t=1,2,…,m)表示第i个词向量的第t维，此时句子可表示为，将各个词向量乘以其权重比后对应维度相加，得到句子的向量表示：

其中，wi(i=1,2,…,n)表示第i个关键词的权重值。

此时，得到句子向量保留了文档的内容信息，句子之间的向量夹角反映了内容的相似程度。然而句子向量是一个高维空间的向量表示，不能够映射到DHT网络的nodeID。为了满足句子向量与nodeID之间的映射关系，本文使用minhash[24]对句子向量进行降维。首先，选取N个随机的哈希函数；然后，对句子向量中的每个元素进行哈希运算，取其中的最小值；最后，重复N次上一步骤，得到代表句子向量的N个数值，即将句子向量降至N维。minhash是局部敏感哈希函数的一种，降维的同时可以保留高维度向量之间的相似性。使用minhash进行降维的合理性，是基于对两个集合随机求最小哈希值相等的概率等于两个集合的Jaccard系数，公式表示如下：

其中，Jac(A,B)是集合A、B之间的Jaccard系数，采用公式（4）计算：

将降维后的向量各维度拼接后得到160 bit的值与文档CID组成键值对，即为句子索引。句子索引的键值与nodeID具有相同值域。此外，句子索引保留了原内容的相似性，则相似内容的句子索引会相邻存储。用户对同一对象的描述既具有差异性也具有相似性，因此无法精确匹配查询对象时，可以在索引存储节点的邻近范围搜索。

使用SICP计算句子索引的复杂度，如表1所示。

表1 计算复杂度Table 1 Computational complexity

表1中，M为词向量维度，N为minhash过程中选取的哈希函数个数，V为word2vec词表的大小。其中，word2vec将关键词转为词向量表示，本质上就是利用哈希表查值，故其时间复杂度为O(1)。由表1可知，SICP的时间复杂度为O(M×N)，空间复杂度为O(M×V)。

图3展示了一个由中心语句构建句子索引键值的示例。

图3 句子索引构造过程Fig.3 Process of building sentence index

3.1.3 索引存储

索引使用去中心化的方式存储，利用DHT网络存储索引文件。本文中的DHT网络基于Kademlia（KAD）算法实现。如图4所示，DHT网络中每个索引存储节点都会存储一个索引表及一个缓存表，并使用倒排表的结构对索引进行整合、存储。DHT网络中的节点提供索引存储和搜索功能。

图4 索引的存储结构Fig.4 Storage structure of index

3.2 搜索过程及结果缓存

当网络中的一个对等节点发起搜索时，首先根据查询语句的长度判断执行句子索引或关键词索引，还需要检查缓存中的数据，如果该节点自身缓存了搜索结果则直接返回结果并进行缓存的更新；其次，在搜索消息路由过程中，如果其他对等节点缓存了该搜索的结果，则中断搜索并返回结果，否则对搜索消息进行转发直到负责存储该搜索结果的对等节点；然后，如果是关键词索引，需要精确匹配关键词哈希，如果是句子索引，无法精确匹配的情况下，因为相似内容的句子索引相邻存储，在存储句子索引的节点附近进行搜索，搜索时会按照制定的规则添加搜索结果；最后，对搜索结果进行整合过滤，结束搜索并返回结果，发起搜索的对等节点将此次搜索及相关结果加入到它的缓存中。

此外，由于缓存空间有限，并不是所有节点都会缓存搜索结果。发布查询的节点在收到目的节点发送的搜索结果时，会根据其与目的节点的距离决定是否对搜索结果进行缓存，只有当该节点的最近邻节点或者若干路由跳数范围内的节点没有相关数据才进行缓存。如果缓存空间已满，为了避免出现随着缓存空间增大缓存的使用反而减少的情况，将采用最近最久未访问算法对缓存结果进行置换，保证对热数据的快速搜索，同时减少缓存的空间开销。

如图5所示，网络中的一个对等节点发起搜索的执行过程如下：

图5 搜索流程图Fig.5 Flow diagram of querying

（1）对等节点发起查询时，对查询语句进行分词，判断是否执行句子索引，若判断为是，则执行步骤（2）；若判断为否，执行步骤（4）。

（2）使用SICP计算查询语句的160 bit哈希值，判断缓存中是否存储相关查询结果，若判断为是，则执行步骤（6）；若判断为否，执行（3）。

（3）执行句子索引，若在索引存储节点无法精确匹配的情况下，因为相似内容的句子索引相邻存储，在存储句子索引的节点附近进行搜索，然后执行步骤（6）。

（4）使用与建立关键词索引同样的哈希算法，计算查询关键词的160 bit哈希值，判断缓存中是否存储相关查询结果，若判断为是，则执行步骤（6）；若判断为否，执行步骤（5）。

（5）执行关键词索引，在索引存储节点需要精确匹配存储的关键词哈希，然后执行步骤（6）。

（6）发起查询的对等节点得到搜索结果，更新缓存，结束查询。

4 实验结果及分析

4.1 实验配置及数据集

用于实验的环境如下：操作系统为Windows 7旗舰版64位，Inter®Core™i5-3470 CPU@3.20 GHz，931 GB硬盘，12 GB内存，peersim版本为1.0.5，IntelliJ IDEA版本为2020.2.2。

本文使用peersim软件在两个数据集上进行了仿真实验，一个是雅虎的匿名数据集[25]，另一个是github上的数据集ChineseSTS[26]。雅虎数据集是对真实用户的查询进行匿名处理后得到的。ChineseSTS数据集中每一行数据会有两个句子和一个相似度值，相似度值取值范围为[0，5]，0表示语义相反或不相干，相似度值越大表示两个句子的相似度越高。

4.2 句子索引分析

从ChineseSTS数据集抽取相似度值标记为4和5的数据，选择其中分词后词数大于等于3的数据，得到相似数据对1 190对。使用SICP计算相似数据对的句子索引，计算每个相似数据对句子索引的切比雪夫距离[27]。在执行句子索引时，会设置切比雪夫距离作为阈值，然后根据阈值在句子索引存储节点的邻近范围搜索满足条件的结果。图6展示了相似数据对总数与切比雪夫距离的关系，其中91.34%的相似数据对的切比雪夫距离小于等于25。

图6 相似数据对总数与距离关系图Fig.6 Total number of similar data variation with distance

将每对相似数据对拆分成两部分，分别是用于存储的数据及用于搜索查询的数据，而且数据对中存在多对相似的情况。将1 190条数据建立句子索引并存入DHT网络，另外1 190条数据用于搜索。首先，不使用句子索引，按照文献[5]所述方法，将长查询语句分词后，对每个关键词分别查询，设置并行搜索数目为3，搜索满足要求的数据。统计查询语句的关键词个数及搜索的平均网络跳数，得到结果如图7所示。

图7 网络跳数随关键词数变化Fig.7 Hop number variation with keywords number

查询语句中有117条语句的关键词数3，对应的平均网络跳数为19.78跳，当查询语句的关键词数为5时，对应的平均网络跳数为33.06跳，随着关键词个数的增加，搜索网络跳数也不断增加。

使用句子索引，设置切比雪夫距离为20，并行搜索数目为3时，搜索满足要求的数据。每个查询语句的平均网络路由为8.19跳。具体而言，在不同网络跳数时，能搜索得到的结果数如图8所示。

图8 搜索结果数对应的网络跳数分布Fig.8 Hop number distribution of search results

使用句子索引时，无需关心查询语句的关键词数，每个查询语句的平均网络路由为8.19跳，而不使用句子索引查询，即使关键词数仅为3，也需要19.78跳，可见句子索引加快了对长查询语句的搜索过程，减少了网络负担，实验结果证明了本文提出的句子索引搜索方式的有效性。

4.3 关键词索引及缓存分析

从雅虎数据集中抽取1 500 000条数据，对其建立关键词索引，并将其索引信息存入DHT网络。为测试改进存储后的缓存所占空间进行了如下实验，从1 500 000条数据中抽取1 000条数据，然后对这1 000条数据随机采样10 000次，构成用于搜索的10 000条数据，模拟重复查询，其中数据的平均重复数为10。搜索结果如表2所示。

表2 在500个节点下的仿真实验结果Table 2 Results of simulation experiment with 500 nodes

缓存空间表示节点缓存搜索结果的能力，例如5表示节点可以缓存5条搜索结果。缓存总数是指DHT网络中所有节点缓存搜索结果的总数。为尽可能地贴近真实情况，在指定范围内随机选取干扰概率模拟节点的加入和退出网络。因此在表2中，对10 000条数据进行搜索，而对应实际有效搜索次数却低于10 000次。当缓存空间设为20时，DHT网络所有节点的缓存空间为10 000，实际执行的有效搜索为9 616次，按照文献[5]及文献[10]采用的缓存方式，此时缓存空间将使用9 616，而改进缓存存储机制后，缓存空间使用了8 559，缓存占用空间减少了10.99%，实验结果表明改进后的缓存机制，缓存占用空间更少，可以缓存更多的查询结果。

为说明缓存空间、数据的平均重复数、缓存命中之间的关系，进行了如下实验，从1 500 000条数据中抽取3 000条数据，然后对这3 000条数据随机采样10 000次，构成用于搜索的10 000条数据，其中数据的平均重复数为3.3。得到搜索结果与表2的结果进行对比，如表3所示。

表3 不同平均重复数的结果对比Table 3 Comparison results of different average duplicate data

平均重复数越大表示用于搜索的数据中重复查询越多，即数据被频繁搜索的次数越多。在表3中，缓存空间大小相同，数据平均重复数不同的，进行了三次对照实验。无论缓存空间大小如何变化，平均重复数为10的缓存命中次数均约为平均重复数为3.3的实验缓存命中次数的3倍。实验结果表明缓存可以为被频繁搜索的数据提供更好的搜索机制，可以保证对热数据的快速搜索。实验中，随着节点缓存空间的增大，缓存命中次数也随之增大，而搜索会在缓存命中时中断，无需将搜索消息转发到最终目的节点，因此，减少了消息转发路由，加快了搜索过程。

5 结束语

本文鉴于目前在IPFS文件系统上缺乏有效的数据获取方法，提出一种去中心化混合索引的IPFS数据获取方法——IPFS-DDAM。实验结果表明，本文方法IPFS-DDAM在句子搜索和关键词搜索上都能有较好的表现，加快了搜索过程，对缓存机制的改进，降低了缓存所占存储空间。在未来的工作中将探索能否改进句子索引，使相似内容的句子索引存储相邻这一特性更加明显，进一步提高搜索效率。