一种结合指纹抽样和减少数据碎片的数据块路由方法

专利类型：发明专利

语言：中文

申请号：CN201610368325.4

申请日：20160527

发明人：谭玉娟王奏鸣晏志超

申请人：重庆大学

申请人地址：400044 重庆市沙坪坝区沙正街174号

公开日：20160824

公开号：CN105897921A

代理人：

代理机构：

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

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

关键词：

法律状态：公开

IPC专利分类号：H04L29/08(2006.01)I;G06F17/30(2006.01)I