• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 11
    • 下载费用:30 金币  

    重庆时时彩介绍微博: 一种并行重复数据删除方法.pdf

    关 键 词:
    一种 并行 重复 数据 删除 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410204599.0

    申请日:

    2014.05.15

    公开号:

    CN103970875A

    公开日:

    2014.08.06

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20140515|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 华中科技大学
    发明人: 曹强; 万胜刚; 林川; 黄国强; 谢长生
    地址: 430074 湖北省武汉市洪山区珞喻路1037号
    优先权:
    专利代理机构: 华中科技大学专利中心 42201 代理人: 朱仁玲
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410204599.0

    授权公告号:

    ||||||

    法律状态公告日:

    2017.02.15|||2014.09.03|||2014.08.06

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明公开了一种并行重复数据删除方法,包括以下步骤:客户端先对要重删的数据进行分块,然后通过哈希函数计算出每个分块的哈希指纹,然后把哈希指纹发送到不同的重删服务器节点上进行指纹的查重工作。如果某个指纹经过对比,确认是重复的指纹,则只用更新查询服务器上元数据和重删服务器节点上的指纹计数器。如果某个指纹经过对比,确认是一个新的数据块,则传输该数据块到重删服务器并且更新指纹库和查询服务器上的元数据。本发明具重删节点可扩展性,可根据不同的需求扩展不同的节点来满足性能的需求,而且利用了多节点之间的并行性,有效的提升了重删系统的性能,提供高效可靠的服务。

    权利要求书

    权利要求书
    1.  一种并行重复数据删除方法,其特征在于,包括:
    写过程,包括以下步骤:
    (1)客户端将虚拟机镜像文件划分为多个相同大小的数据块,并且为每一个数据块分配一个数据块ID;
    (2)客户端设置计数器i=1;
    (3)客户端利用哈希算法对第i个数据块进行处理,以生成哈希指纹值,根据哈希指纹值生成对应的节点ID,并将<第i个数据块ID,哈希指纹值>二元组传送到哈希指纹值对应的节点ID所对应的数据节点进行哈希指纹查询;
    (4)数据节点在其指纹库中查询该哈希指纹值是否命中,如果命中则转到步骤(5),否则转到步骤(8);
    (5)数据节点将<第i个数据块ID,PBA)>二元组传送到查询节点;
    (6)查询节点根据<第i个数据块ID,PBA>二元组更新其地址映射表;
    (7)客户端判断是否虚拟机镜像文件中的所有数据块都已处理完毕,如果是,则过程结束,否则设置i=i+1,并返回步骤(1);
    (8)客户端将第i个数据块ID传送到查询节点,并向该查询节点请求分配新的PBA;
    (9)查询节点为第i个数据块分配新的PBA,更新其地址映射表,并将<哈希指纹值,PBA>二元组发回到数据节点;
    (10)数据节点根据<哈希指纹值,PBA>二元组更新其指纹库,将<第i个数据块ID,PBA>二元组发给客户端,并通知客户端发送第i个数据块;
    (11)客户端根据<第i个数据块ID,PBA>二元组发送第i个数据块到数据节点;
    (12)数据节点保存第i个数据块,并返回步骤(7);
    读过程,包括以下步骤:
    (1’)客户端向查询节点发送地址映射表读请求;
    (2’)查询节点根据地址映射表读请求将其地址映射表发送到客户端;
    (3’)查询节点设置计数器j=1;
    (4’)客户端根据地址映射表将虚拟机镜像文件的第j个数据块的PBA发送到对应的数据节点;
    (5’)对应的数据节点根据PBA在其指纹库中读取对应的第j个数据块,并将该数据块发回客户端;
    (6’)客户端判断是否虚拟机镜像文件的所有数据块均处理完毕,若是则过程结束,否则设置j=j+1,并返回步骤(2’)。

    2.  根据权利要求1所述的并行重复数据删除方法,其特征在于,每个数据块ID包括文件ID和LBA,且每个数据块的大小是4KB至2MB。

    3.  根据权利要求1所述的并行重复数据删除方法,其特征在于,哈希算法包括SHA-1、SHA-2、以及MD5算法。

    4.  根据权利要求1所述的并行重复数据删除方法,其特征在于,步骤(3)是采用DHT算法对哈希指纹值进行计算,以得到节点ID。

    5.  一种并行重复数据删除系统,其特征在于,包括:
    第一???,其设置于客户端中,用于将虚拟机镜像文件划分为多个相同大小的数据块,并且为每一个数据块分配一个数据块ID;
    第二???,其设置于客户端中,用于设置计数器i=1;
    第三???,其设置于客户端中,用于利用哈希算法对第i个数据块进行处理,以生成哈希指纹值,根据哈希指纹值生成对应的节点ID,并将<第i个数据块ID,哈希指纹值>二元组传送到哈希指纹值对应的节点ID所对应的数据节点进行哈希指纹查询;
    第四???,其设置于数据节点中,用于在其指纹库中查询该哈希指纹 值是否命中,如果命中则转到第五???,否则转到第八???;
    第五???,其设置于数据节点中,用于将<第i个数据块ID,PBA)>二元组传送到查询节点;
    第六???,其设置于查询节点中,用于根据<第i个数据块ID,PBA>二元组更新其地址映射表;
    第七???,其设置于客户端中,用于判断是否虚拟机镜像文件中的所有数据块都已处理完毕,如果是,则过程结束,否则设置i=i+1,并返回第一???;
    第八???,其设置于客户端中,用于将第i个数据块ID传送到查询节点,并向该查询节点请求分配新的PBA;
    第九???,其设置于查询节点中,用于为第i个数据块分配新的PBA,更新其地址映射表,并将<哈希指纹值,PBA>二元组发回到数据节点;
    第十???,其设置于数据节点中,用于根据<哈希指纹值,PBA>二元组更新其指纹库,将<第i个数据块ID,PBA>二元组发给客户端,并通知客户端发送第i个数据块;
    第十一???,其设置于客户端中,用于根据<第i个数据块ID,PBA>二元组发送第i个数据块到数据节点;
    第十二???,其设置于数据节点中,用于保存第i个数据块,并返回第七???;
    第十三???,其设置于客户端中,用于向查询节点发送地址映射表读请求;
    第十四???,其设置于查询节点中,用于根据地址映射表读请求将其地址映射表发送到客户端;
    第十五???,其设置于查询节点中,用于设置计数器j=1;
    第十六???,其设置于客户端中,用于根据地址映射表将虚拟机镜像文件的第j个数据块的PBA发送到对应的数据节点;
    第十七???,其设置于数据节点中,用于根据PBA在其指纹库中读取对应的第j个数据块,并将该数据块发回客户端;
    第十八???,其设置于客户端中,用于判断是否虚拟机镜像文件的所有数据块均处理完毕,若是则过程结束,否则设置j=j+1,并返回第十四???。

    说明书

    说明书一种并行重复数据删除方法
    技术领域
    本发明属于计算机存储技术领域,更具体地,涉及一种并行重复数据删除方法。
    背景技术
    随着信息技术的发展和科技的进步,海量信息的保存对存储系统提出了严峻的挑战,PB级别甚至EB级别的信息存储对数据中心的压力也越来越大。由于海量数据中有很多重复数据,如果直接存储这些重复数据,不但会加重存储系统的负担,而且还会占用宝贵的网络带宽。重复数据删除技术可以消除数据中的重复部分,只保留数据的唯一副本,从而减少了数据所需求的物理存储空间,提高了存储效率,减少传输重复数据对网络带宽的占用。
    目前很多的重复数据删除系统都是基于单节点的,虽然可以用高配置的服务器来一定程度上缓解重删对性能的需求,但是对于海量数据的重删来说,单节点系统会存在以下缺点:首先,重复数据删除由于进行了分块和哈希指纹计算,会占用CPU资源,而且哈希指纹存放在内存中几乎要占用全部的内存资源,而且指纹库不能完全放入内存的时候还有一部分指纹库必须放入磁盘,这样查找比较哈希指纹的时候也会带来瓶颈;其次,基于单节点的系统的扩展性有限,无法随着系统规模的扩大而线性的扩展;第三,基于单节点的系统还会受限于网络传输的带宽限制;最后,该系统同时也牺牲了一些重复数据删除率,没有做到100%重复数据删除,使得重复数据删除过后的数据中仍然有重复的数据。同时也牺牲了一些重删率,没有做到100%重删,使得重删过后的数据中仍然有重复的数据。
    发明内容
    针对现有技术的以上缺陷或改进需求,本发明提供了一种并行重复数据删除方法,其目的在于,解决现有单节点重复数据系统中存在的重删处理性能瓶颈、扩展性有限从而无法随着系统规模的扩大而线性的扩展、受限于网络传输的带宽限制、不能实现100%重复数据删除的技术问题。
    为实现上述目的,按照本发明的一个方面,提供了一种并行重复数据删除方法,包括:
    写过程,包括以下步骤:
    (1)客户端将虚拟机镜像文件划分为多个相同大小的数据块,并且为每一个数据块分配一个数据块ID;
    (2)客户端设置计数器i=1;
    (3)客户端利用哈希算法对第i个数据块进行处理,以生成哈希指纹值,根据哈希指纹值生成对应的节点ID,并将<第i个数据块ID,哈希指纹值>二元组传送到哈希指纹值对应的节点ID所对应的数据节点进行哈希指纹查询;
    (4)数据节点在其指纹库中查询该哈希指纹值是否命中,如果命中则转到步骤(5),否则转到步骤(8);
    (5)数据节点将<第i个数据块ID,PBA)>二元组传送到查询节点;
    (6)查询节点根据<第i个数据块ID,PBA>二元组更新其地址映射表;
    (7)客户端判断是否虚拟机镜像文件中的所有数据块都已处理完毕,如果是,则过程结束,否则设置i=i+1,并返回步骤(1);
    (8)客户端将第i个数据块ID传送到查询节点,并向该查询节点请求分配新的PBA;
    (9)查询节点为第i个数据块分配新的PBA,更新其地址映射表,并将<哈希指纹值,PBA>二元组发回到数据节点;
    (10)数据节点根据<哈希指纹值,PBA>二元组更新其指纹库,将<第i 个数据块ID,PBA>二元组发给客户端,并通知客户端发送第i个数据块;
    (11)客户端根据<第i个数据块ID,PBA>二元组发送第i个数据块到数据节点;
    (12)数据节点保存第i个数据块,并返回步骤(7);
    读过程,包括以下步骤:
    (1’)客户端向查询节点发送地址映射表读请求;
    (2’)查询节点根据地址映射表读请求将其地址映射表发送到客户端;
    (3’)查询节点设置计数器j=1;
    (4’)客户端根据地址映射表将虚拟机镜像文件的第j个数据块的PBA发送到对应的数据节点;
    (5’)对应的数据节点根据PBA在其指纹库中读取对应的第j个数据块,并将该数据块发回客户端;
    (6’)客户端判断是否虚拟机镜像文件的所有数据块均处理完毕,若是则过程结束,否则设置j=j+1,并返回步骤(2’)。
    优选地,每个数据块ID包括文件ID和LBA,且每个数据块的大小是4KB至2MB。
    优选地,哈希算法包括SHA-1、SHA-2、以及MD5算法。
    优选地,步骤(3)是采用DHT算法对哈希指纹值进行计算,以得到节点ID。
    按照本发明的另一方面,提供了一种并行重复数据删除系统,包括:
    第一???,其设置于客户端中,用于将虚拟机镜像文件划分为多个相同大小的数据块,并且为每一个数据块分配一个数据块ID;
    第二???,其设置于客户端中,用于设置计数器i=1;
    第三???,其设置于客户端中,用于利用哈希算法对第i个数据块进行处理,以生成哈希指纹值,根据哈希指纹值生成对应的节点ID,并将< 第i个数据块ID,哈希指纹值>二元组传送到哈希指纹值对应的节点ID所对应的数据节点进行哈希指纹查询;
    第四???,其设置于数据节点中,用于在其指纹库中查询该哈希指纹值是否命中,如果命中则转到第五???,否则转到第八???;
    第五???,其设置于数据节点中,用于将<第i个数据块ID,PBA)>二元组传送到查询节点;
    第六???,其设置于查询节点中,用于根据<第i个数据块ID,PBA>二元组更新其地址映射表;
    第七???,其设置于客户端中,用于判断是否虚拟机镜像文件中的所有数据块都已处理完毕,如果是,则过程结束,否则设置i=i+1,并返回第一???;
    第八???,其设置于客户端中,用于将第i个数据块ID传送到查询节点,并向该查询节点请求分配新的PBA;
    第九???,其设置于查询节点中,用于为第i个数据块分配新的PBA,更新其地址映射表,并将<哈希指纹值,PBA>二元组发回到数据节点;
    第十???,其设置于数据节点中,用于根据<哈希指纹值,PBA>二元组更新其指纹库,将<第i个数据块ID,PBA>二元组发给客户端,并通知客户端发送第i个数据块;
    第十一???,其设置于客户端中,用于根据<第i个数据块ID,PBA>二元组发送第i个数据块到数据节点;
    第十二???,其设置于数据节点中,用于保存第i个数据块,并返回第七???;
    第十三???,其设置于客户端中,用于向查询节点发送地址映射表读请求;
    第十四???,其设置于查询节点中,用于根据地址映射表读请求将其地址映射表发送到客户端;
    第十五???,其设置于查询节点中,用于设置计数器j=1;
    第十六???,其设置于客户端中,用于根据地址映射表将虚拟机镜像文件的第j个数据块的PBA发送到对应的数据节点;
    第十七???,其设置于数据节点中,用于根据PBA在其指纹库中读取对应的第j个数据块,并将该数据块发回客户端;
    第十八???,其设置于客户端中,用于判断是否虚拟机镜像文件的所有数据块均处理完毕,若是则过程结束,否则设置j=j+1,并返回第十四???。
    总体而言,通过本发明所构思的以上技术方案与现有技术相比,能够取得下列有益效果:
    (1)由于本发明采用了多台数据节点实现并行性重复数据删除,从而解决了单节点重复数据删除系统中存在的处理性能瓶颈问题;
    (2)由于本发明数据节点的数量可以根据需要灵活配置,因此可以实现良好的可扩展性,以满足不同的性能需求;
    (3)由于本发明的多数据节点拥有更大的总内存容量、更多的CPU资源和更大的网络传输总带宽,因此能满足大规模系统的需求,并克服网络传输带宽的瓶颈限制;
    (4)本发明采用多数据节点的并行性方式,不用牺牲复删除率来保证性能,从而可以实现100%重复数据删除,并将现有资源利用率最大化。
    附图说明
    图1是本发明并行重复数据删除方法的系统架构图。
    图2是本发明并行重复数据删除方法写过程的流程图。
    图3是本发明并行重复数据删除方法读过程的流程图。
    具体实施方式
    为了使本发明的目的、技术方案及优点更加清楚明白,以下结合附图及实施例,对本发明进行进一步详细说明。应当理解,此处所描述的具体 实施例仅仅用以解释本发明,并不用于限定本发明。此外,下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
    如图1所示,本发明的计算机集群包括多台客户端、查询节点和多个数据节点,其中客户端、查询节点和数据节点通过交换机相连接,三者之间可以互相通信。
    如图2所示,本发明的并行重复数据删除方法包括:
    一、写过程,包括以下步骤:
    (1)客户端将虚拟机镜像文件划分为多个相同大小的数据块,并且为每一个数据块分配一个块ID(Block Id),每个块ID包括文件ID和逻辑块地址(Logical Block Address,简称LBA);具体而言,每个数据块的大小是4KB至2MB,并可由客户端自由设定;
    (2)客户端设置计数器i=1;
    (3)客户端利用哈希算法对第i个数据块进行处理,以生成哈希指纹值;具体而言,本发明中的哈希算法包括SHA-1、SHA-2、MD5算法;
    (4)客户端根据哈希指纹值生成对应的节点ID;具体而言,采用分布式哈希表(简称Distributed Hash Table,简称DHT)算法对哈希指纹值进行计算,得到的结果就是节点ID;
    (5)客户端将<第i个数据块ID,哈希指纹值>二元组传送到哈希指纹值对应的节点ID所对应的数据节点进行哈希指纹查询;
    (6)数据节点在其指纹库中查询该哈希指纹值是否命中,如果命中则转到步骤(7),否则转到步骤(10);
    (7)数据节点将<第i个数据块ID,物理块地址(Physical BlockAddress,简称PBA)>二元组传送到查询节点;
    (8)查询节点根据<第i个数据块ID,PBA>二元组更新其地址映射表;
    (9)客户端判断是否虚拟机镜像文件中的所有数据块都已处理完毕, 如果是,则过程结束,否则设置i=i+1,并返回步骤(1);
    (10)客户端将第i个数据块ID传送到查询节点,并向该查询节点请求分配新的PBA;
    (11)查询节点为第i个数据块分配新的PBA,更新其地址映射表,并将<哈希指纹值,PBA>二元组发回到数据节点。
    (12)数据节点根据<哈希指纹值,PBA>二元组更新其指纹库,将<第i个数据块ID,PBA>二元组发给客户端,并通知客户端发送第i个数据块。;
    (13)客户端根据<第i个数据块ID,PBA>二元组发送第i个数据块到数据节点;
    (14)数据节点保存第i个数据块,并返回步骤(9);
    二、读过程,包括以下步骤:
    (1’)客户端向查询节点发送地址映射表读请求;
    (2’)查询节点根据地址映射表读请求将其地址映射表发送到客户端;
    (3’)查询节点设置计数器j=1;
    (4’)客户端根据地址映射表将虚拟机镜像文件的第j个数据块的PBA发送到对应的数据节点;
    (5’)对应的数据节点根据PBA在其指纹库中读取对应的第j个数据块,并将该数据块发回客户端;
    (6’)客户端判断是否虚拟机镜像文件的所有数据块均处理完毕,若是则过程结束,否则设置j=j+1,并返回步骤(2’)。
    本发明的并行重复数据删除系统包括:
    第一???,其设置于客户端中,用于将虚拟机镜像文件划分为多个相同大小的数据块,并且为每一个数据块分配一个数据块ID;
    第二???,其设置于客户端中,用于设置计数器i=1;
    第三???,其设置于客户端中,用于利用哈希算法对第i个数据块进 行处理,以生成哈希指纹值,根据哈希指纹值生成对应的节点ID,并将<第i个数据块ID,哈希指纹值>二元组传送到哈希指纹值对应的节点ID所对应的数据节点进行哈希指纹查询;
    第四???,其设置于数据节点中,用于在其指纹库中查询该哈希指纹值是否命中,如果命中则转到第五???,否则转到第八???;
    第五???,其设置于数据节点中,用于将<第i个数据块ID,PBA)>二元组传送到查询节点;
    第六???,其设置于查询节点中,用于根据<第i个数据块ID,PBA>二元组更新其地址映射表;
    第七???,其设置于客户端中,用于判断是否虚拟机镜像文件中的所有数据块都已处理完毕,如果是,则过程结束,否则设置i=i+1,并返回第一???;
    第八???,其设置于客户端中,用于将第i个数据块ID传送到查询节点,并向该查询节点请求分配新的PBA;
    第九???,其设置于查询节点中,用于为第i个数据块分配新的PBA,更新其地址映射表,并将<哈希指纹值,PBA>二元组发回到数据节点;
    第十???,其设置于数据节点中,用于根据<哈希指纹值,PBA>二元组更新其指纹库,将<第i个数据块ID,PBA>二元组发给客户端,并通知客户端发送第i个数据块;
    第十一???,其设置于客户端中,用于根据<第i个数据块ID,PBA>二元组发送第i个数据块到数据节点;
    第十二???,其设置于数据节点中,用于保存第i个数据块,并返回第七???;
    第十三???,其设置于客户端中,用于向查询节点发送地址映射表读请求;
    第十四???,其设置于查询节点中,用于根据地址映射表读请求将其地址映射表发送到客户端;
    第十五???,其设置于查询节点中,用于设置计数器j=1;
    第十六???,其设置于客户端中,用于根据地址映射表将虚拟机镜像文件的第j个数据块的PBA发送到对应的数据节点;
    第十七???,其设置于数据节点中,用于根据PBA在其指纹库中读取对应的第j个数据块,并将该数据块发回客户端;
    第十八???,其设置于客户端中,用于判断是否虚拟机镜像文件的所有数据块均处理完毕,若是则过程结束,否则设置j=j+1,并返回第十四???。
    本领域的技术人员容易理解,以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等,均应包含在本发明的?;し段е?。

    关于本文
    本文标题:一种并行重复数据删除方法.pdf
    链接地址://www.4mum.com.cn/p-6142793.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 免费陕西麻将 澳洲幸运5总和路珠 篮球让分胜负刚好 双色球斜跳分布图 gta5线下在哪赚钱最快 黄金城棋牌游戏官网 山东时时彩走势 新疆35选7大星彩票走势图 电子游艺玩家群 四川快乐12基本走势 内蒙古十一选五彩票控 麻将来了角色攻略 河南11选5视频 彩票投注群 体育彩票广东11选5 鼎盛彩票苹果