[发明专利]一种结合指纹抽样和减少数据碎片的数据块路由方法

摘要

本发明提出一种结合指纹抽样和减少数据碎片的用于分布式重复数据删除系统的数据块路由方法。该方法提出对数据块指纹进行抽样，对抽样后的数据块指纹采用布隆过滤器快速地查找重复数据，估算数据重复率，其采用的路由算法结合了数据的重删率、数据节点服务器的碎片量以及存储空间使用率来确定路由节点。与已有的路由方法相比，该方法能提高整个系统的重删率，系统的吞吐率以及数据恢复速度。

主权项

1.一种结合指纹抽样和减少数据碎片的数据块路由方法，其特征在于，包括步骤：(1)客户端接收用户需要备份的数据流；(2)客户端对接收到的数据流进行预处理，其中，包括步骤：(2.1)使用数据块变长算法对备份数据流进行分块，得到具有一定平均长度的数据块,并使用哈希算法(SHA‑1)计算每个所述数据块的指纹；(2.2)按照备份数据流中数据块出现的顺序，将连续的数据块依次合并为具有一定平均长度的合并块；(2.3)将所述合并块对应的指纹序列，按固定的采样率进行等距抽样，生成新的指纹序列，将新的指纹序列发送给各个数据节点服务器；(3)数据节点服务器对接收到的所述新的指纹序列进行处理并确定最终路由的数据节点服务器，其中，包括步骤：(3.1)数据节点服务器对接收到的指纹序列进行布隆过滤器查询，得到重复数据块指纹的数量，并计算指纹重复率DN，存储空间使用率UN，以及重复率DN和存储空间使用率UN的比值RN，RN＝DN/UN，数据节点服务器将得到的RN值发送给客户端；(3.2)客户端接收每个数据节点服务器的RN值，将步骤(2.2)中得到的合并块的所有指纹发送给RN值最高的K个数据节点服务器；(3.3)数据节点服务器接收到客户端发送的所有数据块指纹之后，查找这些数据块对应的数据碎片，并将数据碎片量返回给客户端；(3.4)客户端接收到对应的数据碎片量之后，选择碎片量最少的一个数据节点服务器，作为最终路由的数据节点服务器；(4)客户端将步骤(2.2)中得到的合并块的所有数据块指纹序列，发送给步骤(3.4)得出的数据节点服务器，对应的数据节点服务器在数据指纹索引表中查找是否存在重复的数据块指纹，若存在，则仅更新数据指纹索引表的块引用数；若不存在，则向客户端索取对应的数据块，将对应的数据块存放在数据节点服务器的数据区域，并将该数据块的指纹，存储地址，以及块引用数添加至数据指纹索引表中。