BETHASH官方网站(访问: hash.cyou 领取999USDT）

　　基于去中心化索引的IPFS数据获取方法研究石秋娥，周喜，王轶1.中国科学院新疆理化技术研究所，乌鲁木齐8300112.中国科学院大学，北京1000493.中国科学院新疆理化技术研究所新疆民族语音语言信息处理实验室，乌鲁木齐830011随着计算机技术的发展，数据的规模量级也不断提高，去中心化数据存储方式可以满足大数据环境下的数据存储需求。星际文件系统[1]创造了一个点对点（peerto-peer，P2P）的分布式文件系统，升级了现有的网络结构，实现了真正意义上的去中心化存储。每一个上传到IPFS系统中存储的文件，系统都会返回一个唯一的文件标识符CID，但是资源请求者只有准确提供CID才能下载IPFS中相应文件。IPFS仅支持基于CID的数据获取方式，制约了它的应用。由于缺乏相应的搜索功能，资源请求者很难通过Key或者其他描述信息获取相关数据。研究IPFS的数据获取方法，可以帮助用户根据自身需求搜索数据，有利于IPFS数据的共享与发现，使IPFS满足更多的应用场景。此外，当文件标识符丢失或遗忘时，可以通过其他方式获取原来的数据，避免数据的“失联”。在IPFS之上建立数据检索层可以解决数据获取问题。传统的集中式索引虽然容易实现、便于管理，但是削弱了IPFS的去中心化程度，并限制IPFS网络的可伸缩性。在为IPFS建立去中心化索引方面，已有研究实现的都是基于Key的索引，没有充分考虑长查询和短查询之间的区别，一般认为三个以上Key的查询属于长查询[2]，将长查询分词为多个Key进行搜索会对网络造成更多的负担。为使数据的获取更加高效，引入了缓存机制，由发布搜索的节点缓存相关结果，却忽视了搜索发布节点与相关结果存储节点之间的距离，使网络中存储大量不必要的冗余数据，未充分利用缓存空间。基于此，本文针对缓存空间的浪费问题，改进了缓存存储机制，降低其所占存储空间。针对IPFS数据获取问题，设计了一种去中心化混合索引，使得搜索在长短查询上都能有较好的表现，对长查询语句，使用word2vec[3]建立句子索引，使语义内容相似的句子索引能够相邻存储，以有效获取IPFS系统数据。1相关工作目前，关于IPFS的数据获取这一方面的研究比较少，还没有成熟的解决方案。IPFS-search[4]是github上的一个开源项目，该项目尝试在IPFS上建立一个基于Elasticsearch的集中式搜索引擎，能为用户提供Key搜索功能。然而集中式索引的服务器面临着更多的攻击，对存储能力的要求也更高。文献[5]提出为IPFS建立一个去中心化的搜索引擎，建立Key和CID的倒排索引，并使用DHT存储索引文件，通过缓存层和过滤器加快搜索过程，该方法在较短的平均查询时间内取得了较好的缓存命中率，但是当查询语句有多个Key，对每个Key分别进行搜索会增加网络的通讯路由。Desema[6]是一个基于IPFS和区块链的去中心化服务市场，使用IPFS存储数据，并通过区块链共享IPFS数据。虽然解决了区块链存储限制，但区块链上实现的仍然是基于CID的数据获取方式。Zhu等人[7]以去中心化的B+树和HashMap为IPFS等去中心化存储数据建立索引，实现了关键字搜索功能。基于DHT的索引结构存在大量相关工作，文献[8-9]结合向量空间模型（VSM）和潜在语义索引（LSI）将文档表示为笛卡尔空间的向量，但是其计算过程中对文档矩阵进行SVD分解的计算代价太大，时间复杂度是O(N2)，空间复杂度O(N3)。Reynolds等人[10]提出使用布隆过滤器和缓存加快DHT网络中Key搜索过程，然而缓存也增加了大量的冗余数据。Hassanzadeh等人[11]提出了LANS和GLARAS方法，分别为节点分配地址及放置副本，使系统中每对节点之间的延迟对应于其地址的公共前缀长度，该方法提高了地址的位置感知能力，降低了搜索的端到端延迟及平均访问延迟。Joung等人[12]使用超立方体索引关键字，相似关键字集的对象很可能被映射到彼此接近的点，削弱了DHT的哈希映射方式对数据邻近性存储的破坏。Armada[13]和LIGHT[14]通过使用前缀哈希树（PHT）分布其索引结构，在DHT上实现轻量级的范围查询。而Echo[15]则使用了一种新的分布式结构TRT来扩展前缀哈希树（PHT），通过TRT提高范围查询的效率。Ngom等人[16]提出一种名为Summary前缀树（SPT）的新结构来解决DHT上Key超集搜索问题。董祥千等人[17]使用局部敏感哈希（localitysensitiveHashing，LSH）建立基于DHT的域索引，但主要是针对结构化数据集的连接搜索问题，仅对结构化数据开展了实验。虽然目前关于IPFS数据获取的研究有了一定进展，但是对长查询带来的网络负担及搜索效率问题并没有很好的解决方案。因此本文为IPFS数据建立去中心化混合索引，并利用DHT网络存储索引文件，实现IPFS的数据获取。主要工作如下：第一，将文件存储在IPFS得到的CID值与文档Key组合，构成Key索引发布到DHT网络中存储，然后计算文档的句子索引并存储在DHT网络中；第二，节点对搜索结果缓存，加快后续相同查询的搜索过程；第三，对长查询进行句子搜索，可以在索引存储节点的邻近范围搜索；对短查询，提取Key后对每个关键字分别搜索。2相关技术2.1星际文件系统IPFS系统并不是一个全新的技术，而是集成并充分利用了BitTorrent、Git、P2P和密码学等已有的技术[1]。IPFS系统中，以256KB为块大小对文件进行分块存储，每个分块会分散存储在IPFS网络中的节点上，如果文件小于256KB则直接存储。如图1所示，IPFS对文件分块后，会计算每一个块的哈希值，然后将所有块的哈希值拼凑起来，再做一次哈希运算，从而得到最终哈希值，即文件的唯一标识符称为CID。资源请求者只需要使用CID就可以在IPFS网络中下载相应文件[18]。图1文件唯一标识符的生成过程Fig.1Generationprocessofuniquecontentidentifier2.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；然后，需要对文件建立两 种索引，一种是Key 索引，对文件进行Key 提取，由这若干个Key 与CID 组 合构成若干个Key 索引，另一种是句子索引，对提取出来的Key 或文档的中心 句使用机器学习的方法构建文档的句子向量表示，由降维后的句子向量和CID 构成句子索引；最后，将生成的句子索引及 Key 索引发布到 DHT 网络中存储。 IPFS 网络和DHT 网络只是逻辑上的划分，物理上同一节点可以同时属于两个 网络。 图2 IPFS-DDAM过程总览图Fig.2 Overview of IPFS-DDAM 3.1.1 Key 索引 本文为IPFS 系统实现了基于Key 的搜索功能，使用TF-IDF[23]（term frequency-inverse document frequency）算法提取文档的前n 个或者权重大于 阈值的Key(k1,k2,…,k n)，每个Key 经过哈希运算得到的Key 哈希与文档CID 组成键值对，即为Key 索引。Key 哈希与nodeID 具有相同值域。每个索引存 储节点负责存储与其nodeID 相同或相近的Key 索引。 3.1.2 句子索引 为了将句子索引存储在DHT 网络中，句子索引一方面需要体现文档的内容，另 一方面需要与DHT 网络的节点地址具有可映射性。为了使句子索引反映文档内 容，本文提出了一种使用机器学习的方式计算句子索引——SICP（sentence index calculation process）。首先，提取文档的中心语句，分词后得到若干 Key(k1,k2,…,k n)，或者使用TF-IDF 算法提取文档的前n 个或者权重大于阈值 的Key；然后采用word2vec 将Key 转为词向量表示： 其中，dimt i(t=1,2,…,m)表示第i 个词向量的第t 维，此时句子可表示为，将各 个词向量乘以其权重比后对应维度相加，得到句子的向量表示： 其中，wi(i=1,2,…,n)表示第i 个Key 的权重值。 此时，得到句子向量保留了文档的内容信息，句子之间的向量夹角反映了内容 的相似程度。然而句子向量是一个高维空间的向量表示，不能够映射到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 将Key 转为词向量表示，本质上就是 利用哈希表查值，故其时间复杂度为O(1)。由表1 可知，SICP 的时间复杂度 为O(M×N)，空间复杂度为O(M×V)。 图3 展示了一个由中心语句构建句子索引键值的示例。 图3 句子索引构造过程Fig.3 Process of building sentence index