针对云存储系统中重复冗余数据的高效去重方法
针对云存储系统中重复冗余数据的高效去重方法
【技术领域】
[0001]本发明涉及计算机信息存储技术领域，特别涉及一种针对云存储系统中重复冗余数据的高效去重复方法。
【背景技术】
[0002]重复数据删除技术是一种粗粒度的无损的冗余数据去除的特殊数据压缩技术。重复数据删除技术通过对数据进行粗粒度的划分，然后通过指纹计算技术提取数据块的Hash指纹，通过指纹的索引查询来判断数据是否冗余，如果新数据块与存储系统中已有数据内容相同，则不会对新数据进行存储，而是通过保存指向原有数据块的指针，确定数据的存储位置，对于指针存储的开销远远小于对数据的占用空间。因此，重复数据删除技术可以有效的提升存储系统的空间使用率，节省磁盘存储容量。
[0003]云存储环境中实现重复数据删除技术是指在云存储架构中加入重删功能，提升存储空间利用率，降低存储成本。在大规模集群中，实现海量数据的存储，基于块级别的在线重复数据删除技术在数据去重率以及存储管理开销上具有很大的优势，受到学术界以及工业界的广泛认可与应用。但是在大规模存储系统中，也存在两大挑战，一是数据块索引查询磁盘瓶颈，二是大规模数据路由问题。
[0004]在重复数据删除过程中，对数据块的去重是基于指纹的查找与匹配来判定的。因此索引查询优化是提高重删系统I/O性能，解决磁盘查找瓶颈的关键因素。目前针对于数据块索引优化的策略主要有三类:一是基于数据局部性的优化策略；二是基于相似性理论的优化策略;三是基于SSD的索引优化策略。在集群存储系统中，数据的存储位置是衡量一个存储系统的重要指标，因为这不仅涉及到各节点存储的负载均衡性，也会对上层应用造成一定的影响。而在集群重复数据删除过程中，出于对系统整体性能开销的考虑，跨节点的全局去重会严重降低系统存储性能，所以一般都是采用只对节点内部数据进行数据去重。所以基于集群重复数据删除技术的集群重删系统在数据路由问题上，将会对系统整体去重效果产生很大影响。
【发明内容】
[0005]本发明旨在至少在一定程度上解决上述相关技术中的技术问题之一。
[0006]为此，本发明的目的在于提出一种针对云存储系统中重复冗余数据的高效去重方法，该方法能够快速地在云存储系统中去除冗余数据，提升存储磁盘利用率，保证系统的吞吐性能，从而降低存储成本。
[0007]为了实现上述目的，本发明的实施例提出了一种针对云存储系统中重复冗余数据的高效去重方法，所述云存储系统包括多个数据存储服务器和多个客户端，其中，所述多个数据存储服务器组成的集群包括由多个数据服务器组成的数据服务器集群和一个元数据服务器，所述方法包括以下步骤:S1:所述多个客户端接收用户的上传数据，将所述数据组织成数据超块以作为数据路由单位，并提取其中的数据路由特征指纹，用于数据路由选择；S2:所述元数据服务器与数据服务器集群根据路由策略来处理所述多个客户端的数据路由选择请求，其中，所述数据服务器集群对所述数据路由特征指纹进行相似指纹匹配以确定相似路由节点，所述元数据服务器根据负载均衡策略确定最终的数据路由地址;S3:确定数据路由地址后，所述客户端与相应的数据服务器进行交互，以将相似冗余数据发送至选择的数据服务器，所述选择的数据服务器在接收到相似冗余数据后，在线对冗余数据进行快速去重。
[0008]根据本发明实施例的针对云存储系统中重复冗余数据的高效去重方法，通过在分布式文件系统的基础上融入了集群重复数据删除技术，在云存储环境中构建大规模、高性能、分布式重删系统，该方法能够有效地解决在大规模存储时冗余数据去重过程中的数据块查找的磁盘瓶颈问题，减少了指纹匹配的次数，从而提高了去重性能；另外，在具有重删功能的集群存储系统的数据路由选择上，可以快速定位数据路由地址，使系统保持高效的全局去重率；同时，该方法还可以减少路由选择过程中的网络带宽消耗，提升磁盘使用率，降低数据管理成本。
[0009]另外，根据本发明上述实施例的针对云存储系统中重复冗余数据的高效去重方法还可以具有如下附加的技术特征:
[0010]在一些示例中，根据局部相似路由算法生成所述路由策略。
[0011]在一些示例中，所述步骤S2进一步包括:在上传数据时，每个客户端对所述数据超块进行逻辑划分，生成多个数据段，并根据采样策略对每个数据段进行指纹采样，以获取数据路由特征指纹;所述客户端与集群中的各数据服务器进行指纹数据交互，通过查询相似索引表确定各数据服务器的匹配信息;所述客户端与元数据服务器进行通信，根据所述各数据服务器的匹配信息与集群中选择的路由节点使用情况，确定最终的数据路由地址。
[0012]在一些示例中，所述各数据服务器的匹配信息包括每个数据服务器的匹配成功的指纹个数。
[0013]在一些示例中，所述采样策略是基于布罗德最小独立置换原理，对每个数据段进行指纹采样，并获取数据路由特征指纹。
[0014]在一些示例中，所述步骤S3进一步包括:所述数据服务器在接收到客户端发送的存储请求时，启动相应的数据处理线程，对到达的数据超块进行处理;所述数据服务器在接收数据时，根据数据路由特征指纹将相似容器元数据加载到内存的相似索引查找子集，并与到达的数据超块进行数据冗余匹配;如果未匹配到的相似的数据超块，则结合热点索引库进一步地进行数据去重处理。
[0015]在一些示例中，其中，所述数据服务器集群根据系统缓存中相似冗余数据的访问频率异步更新所述热点索引库。
[0016]本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
【附图说明】
[0017]本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中:
[0018]图1是根据本发明一个实施例的针对云存储系统中重复冗余数据的高效去重方法的流程图；
[0019]图2是根据本发明一个实施例的针对云存储系统中重复冗余数据的高效去重系统的架构图；
[0020]图3是根据本发明另一个实施例的针对云存储系统中重复冗余数据的高效去重方法的流程示意图；
[0021 ]图4是根据本发明一个实施例的数据服务器中数据存储模型的设计图；
[0022]图5是根据本发明一个实施例的局部路由算法特征指纹选取过程示意图；
[0023]图6是根据本发明一个实施例的局部路由算法有状态路由选择过程示意图；
[0024]图7是根据本发明一个实施例的云存储系统中的数据写入过程示意图；
[0025]图8是根据本发明一个实施例的云存储系统中的数据重组过程示意图。
【具体实施方式】
[0026]下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
[0027]以下结合附图描述根据本发明实施例的针对云存储系统中重复冗余数据的高效去重方法。
[0028]首先结合图2所示，本发明实施例中的云存储系统例如包括多个数据存储服务器组成的集群以及多个客户端，其中，多个数据存储服务器组成的集群包括由多个数据服务器组成的数据服务器集群和一个元数据服务器。
[0029]图1是根据本发明一个实施例的针对云存储系统中重复冗余数据的高效去重方法的流程图。如图1所示，该方法包括以下步骤:
[0030]步骤S101:多个客户端接收用户的上传数据，将数据组织成数据超块以作为数据路由单位，并提取其中的数据路由特征指纹，用于数据路由选择。
[0031]换言之，每个接入的客户端通过系统提供的对外交互接口进行数据的存储操作。根据提供的文件操作接口实现基于重复数据删除技术的存储逻辑，主要完成数据预处理阶段。具体包括:将数据组织成数据超块(SuperBlock)，然后通过网络与分布式文件系统中各节点进行交互以确定数据超块的路由地址，最后将数据与数据路由特征指纹发送到数据服务器。
[ 0032]具体地说，上述步骤S101包括:首先，客户端加载本地数据，采用⑶C算法将数据划分为chunk，按照超块组织方法组织成SuperBlock。其次，对SuperBlock中的所有chunk采用SHA1算法进行指纹计算，并提取出特征指纹，最后客户端负责将SuperBlock和对应特征指纹发送到由元数据服务器确定的路由地址节点中。
[0033]步骤S102:元数据服务器与数据服务器集群根据路由策略来处理多个客户端的数据路由选择请求，其中，数据服务器集群对数据路由特征指纹进行相似指纹匹配以确定相似路由节点，元数据服务器根据负载均衡策略确定最终的数据路由地址。其中，在本发明的一个实施例中，根据局部相似路由算法生成上述路由策略。
[0034]具体地说，在本发明的一个实施例中，步骤S102具体包括:
[0035]首先，在上传数据时，每个客户端对数据超块进行逻辑划分，生成多个数据段，并根据采样策略对每个数据段进行指纹采样，以获取数据路由特征指纹。更为具体地，在本发明的一个实施例中，采样策略是基于布罗德最小独立置换原理，对每个数据段进行指纹采样，并获取数据路由特征指纹。
[0036]然后，多个客户端与集群中的数据服务器进行指纹数据交互，通过查询相似索引表确定各数据服务器的匹配信息。
[0037]最后，多个客户端与元数据服务器进行通信，根据各数据服务器的匹配信息与集群中选择的路由节点使用情况，确定最终的数据路由地址。其中，在本发明的一个实施例中，每个数据服务器的匹配信息包括每个数据服务器的匹配情况，例如匹配个数。
[0038]简言之，即客户端通过将SuperBlock中采样选择的数据路由特征指纹发送到各个数据服务器进行匹配查询，然后，将匹配情况返回给元数据服务器，最后，元数据服务器根据各个数据服务器的匹配结果以及各个数据服务器的存储情况选择最佳的数据路由地址，并返回给客户端。
[0039]步骤S103:确定数据路由地址后，多个客户端与相应的数据服务器进行交互，以将相似冗余数据发送至选择的数据服务器，被选择的数据服务器在接收到相似冗余数据后，在线对冗余数据进行快速去重。
[0040]在本发明的一个实施例中，步骤S103具体包括:数据服务器在接收到多个客户端发送的存储请求时，启动相应的数据处理线程，对到达的数据超块进行处理;数据服务器在接收数据时，根据数据路由特征指纹将相似容器元数据加载到内存的相似索引查找子集，并与到达的数据超块进行数据冗余匹配;如果未匹配到相似的数据超块，则结合热点索引库进一步地进行数据去重处理。其中，在本发明的一个实施例中，数据服务器集群根据系统缓存中相似冗余数据的访问频率异步更新热点索引库。
[0041]具体地说，数据服务器通过网络与客户端进行通信，响应客户端的读写请求，与元数据服务器通过网络异步更新数据服务器的数据接收状况以及节点存储状况。换言之即，数据服务器负责对到达的SuperBlock进行去重，完成数据的接送功能，并汇报给元数据服务器。同时数据服务器也负责提取数据完成客户端的读请求。具体而言，在数据服务器端内进行去重过程中，利用数据的相似性与局部性通过相似匹配，并使用自描述的Container来管理数据和指纹的存储。当SuperBlock到达数据服务器时，根据相似索引加载最佳相似匹配的容器中所有的指纹信息，构成相似索引查找子集，SuperBlock通过与相似索引子集进行匹配进行去重，避免加载全局指纹到内存时的频繁10操作，降低了指纹查询的性能开销。虽然这样减少了一定的去重率，但是性能得到很大的提升。为了提升只匹配相似容器造成的去重率问题，根据数据流的局部性原理设计了容器缓存策略以及热点指纹索引策略来优化索引查询过程，进一步提升单节点数据去重率。
[0042]作为具体地示例，以下结合图3-8对本发明上述实施例的针对云存储系统中重复冗余数据的高效去重方法做进一步详细地描述。
[0043]具体而言，图3概括了本发明实施例的方法的数据重删过程。如图3所示，在该示例中，该方法主要包括以下步骤:
[0044]步骤31:首先，客户端对备份数据流进行分块划分，计算数据分块的指纹，将分块组织成SuperBlock，以用于数据路由传输。然后根据数据路由算法，提取出SuperBlock中的数据路由特征指纹，并与元数据服务器的数据路由引擎交互，确定SuperBlock的路由地址。最后根据选择的数据路由节点将SuperBlock发送到相应的数据服务器上进行数据存储。
[0045]步骤32:在上述步骤31中，最后需要确定SuperBlock的路由地址，元数据服务器通过路由选择策略，以局部相似路由算法为基础来确定最佳存储节点，同时在分配的过程中需要综合考虑系统中各节点的存储状态和检索结果，动态调节选择的存储节点，用于平衡数据服务器各节点的存储资源，达到系统的存储负载均衡。
[0046]步骤33:在上述步骤32中，确定SuperBlock的路由地址后，返回给客户端，客户端根据路由地址将SuperBlock发送到相应的数据服务器中，在选择的数据服务器中将数据去重的软件模块作为去重引擎，系统基于相似去重原理，当数据到达后，根据与相似索引表的匹配情况，从磁盘中加载相似索引子集用于数据的去重对比；同时为了提升系统性能，基于数据局部性的特点，设计LRU Cache，减少磁盘查找。
[0047]图4为根据本发明一个实施例的数据服务器中数据存储模型的设计图。如图4所示，在本系统架构设计中，数据去重的主要部分在数据服务器中，所以在数据服务中，需要快速查询判断数据是否重复，因此数据的存储组织模型是数据服务器设计的重点，也是去重系统保证数据去重率，优化指纹查询的关键。在该示例中，对于数据存储模型的设计主要包括以下步骤:
[0048]步骤41:例如Block Meta为SuperBlock对应的元数据，当SuperBlock被发送到本节点后，通过冗余数据去重后，需要对每个SuperBlock中的元数据信息进行保存，读取数据时可以根据Block Meta对应的元数据信息进行数据的重组，将数据提取出来。由于只有在数据读取时才会涉及到对Block Meta的加载，因此将元数据信息完全在磁盘上进行存储即可。
[0049]步骤42:例如Container是一个自描述的并且保存数据局部性的存储结构，包含数据部分和元数据(Con-Meta)部分。在数据存储过程中，数据服务器针对每个数据流始终保持一个开放的容器用以接收数据，当容器存储完毕时，需要封装容器，并打开一个空容器用以接收数据。同时为了提升系统的吞吐率，当多个数据流到达时，数据服务器满足对容器选择的并行化操作，可以同时打开几个未关闭且当前未使用的容器用于接收到达的数据。[OOM]步骤43:例如Similarity Index(相似索引表)存储于内存中的全局特征指纹索引表，表中每一条内容为本节点中Container的代表指纹与Container的ID之间的映射。如果将所有指纹信息加载在内存中，会造成严重的性能开销，因此，在该示例中，采用相似索引的概念，在全局保存相似索引表，表中的特征指纹依据数据相似性原理，在Container封闭时，得到容器中数据的相似代表指纹，通过将小部分的特征指纹来代表整个Container，减少了内存使用量，当新来数据匹配到相似指纹时，即可通过查找Similarity Index来定位Container，然后加载对应Container中的指纹信息。
[0051]步骤44:由于没有将所有指纹加载到内存，每次匹配到相似容器后都要将磁盘中Container的元数据加载到内存中，会造成多次的磁盘读操作，而且备份数据流中存在一定的局部性，因此设计了基于Container的容器缓存模块，其中每一条用于缓存一个Container中存储的所有分块指纹信息，S卩加载容器对应的Con-meta部分，并采用LRU方式对缓存进行更新。当Similarity Index命中一个Container时，首先查询Cache中是否包含了对应的Container，如果命中则可直接将Container在Cache中的所有指纹 信息加载，供新来数据匹配，如果未命中，则需要将对应Container中的所有指纹加载到Cache并提供给新来数据查询。
[0052]步骤45:在采用相似去重的过程中，冗余数据查找时并不能保证较高的去重率，因此在该示例中，根据备份数据流的特性设计了Hot Index(热点索引库)来进一步提升数据去重率。Hot Index也是存储于内存的Hash表，Hot Index是基于LRU Cache中每个容器中指纹访问频率来更新的。在一个Container中，所有指纹被匹配的频率，在一定的程度上可以更好的反应Container中的存储数据的状况。Hot Index中每一条内容为Cache中相应Container中匹配频率最大的前k条chunk指纹，与对应的Container的映射。通过将当前Cache中每个Container对应的热点指纹，加入到Hot Index中来代表Container，可以更好代表指纹在Container中的访问频率，以及备份数据流的特征。在去重过程中通过与HotIndex中的指纹进行匹配，确定相关Container，可以进一步提升在节点内的数据去重率。
[0053]图5为根据本发明一个实施例的云存储中集群重删系统局部路由算法特征指纹选取过程示意图。
[0054]具体而言，为了解决在大规模集群中加入重复数据删除技术引入的数据路由问题，同时为了达到集群存储系统高去重率、高性能以及负载均衡等目标，在该示例中，本发明的方法提出了一个面向重删的数据路由算法-局部相似路算法。该算法主要分为两个主要过程:一是数据路由特征指纹的选取过程，另一个是有状态路由选择过程。其中，数据路由特征指纹选取过程主要包括以下步骤:
[0055]步骤51:在路由粒度选择问题上，本发明的实施例采用固定大块的思想，将备份数据流进行大块划分，划分成SuperBlock，这样数据可以保持一定局部性特征。另外，在实验中测试得到:在SuperBlock大小为8M左右时，可以达到系统性能与去重的最佳效果。
[0056]步骤S52:针对每个SuperBlock，采用⑶C算法将数据划分为平均大小为4KB的数据块chunk，并计算每个chunk的指纹信息，然后SuperBlock中所有的chunk指纹信息构成的集合中，选出一定的指纹作为路由特征指纹，用以指导数据路由。在选择的过程中，基于布罗德最小独立置换原理进行选择。由于在SuperBlock中有2048条chunk指纹，基于数据局部性以及相似性的特点将SuperBlock进一步逻辑划分，将SuperBlock划分为逻辑大小相等的Segment (数据段)，其中每个Segment的大小由实验测得为512KB时最佳，即平均128个chunk组成一个Segment。
[0057]步骤S53:经过步骤S52的数据组织后，一个SuperBlock由16个逻辑的Segment组成，其中每个Segment又由128个chunk组成，然后根据布罗德最小独立置换原理选择每个Segment中最小分块的指纹作为Segment的代表指纹，最后将SuperBlock中选择出的16个指纹作为特征指纹作为路由选择依据。
[0058]图6为根据本发明一个实施例的云存储中集群重删系统局部路由算法有状态路由选择过程示意图。具体而言，在局部路由算法中，第二个主要的过程就是基于有状态的路由选择框架，如图6所示，该过程的主要包括以下步骤:
[0059]步骤61:客户端首先将SuperBlock选择出的特征指纹集合序列化，然后异步建立与数据服务的远程连接，将序列化的特征指纹集合发送到数据服务中。
[0060]步骤62:数据服务器接收到序列化的特征指纹集合后，反序列化数据，并与本地的Similarity Index进行索引查询，确定匹配成功的指纹个数，返回给客户端。
[0061]步骤63:客户端将得到的各数据服务器匹配成功的指纹个数，加入SuperBlock的地址请求队列中，发送到元数据服务器中。元数据服务器接收到SuperBlock地址请求后，根据集群中的使用情况，以及设计的负载判断情况，确定最佳的存储地址返回给客户端。
[0062]需要说明的是，在上述过程中，为了节省路由时的网络带宽消耗，在该示例中，采用基于相似的特征指纹选样方式，节约一定的性能消耗，同时，为了保证系统的去重率，采用有状态路由方式，根据匹配成功的指纹个数，确定最佳节点，避免无状态路由的不平衡性以及低去重率问题。
[0063]图7为根据本发明一个实施例的云存储系统中的数据写入过程示意图。同时，图7展示了在云存储实际系统中数据服务器节点接收数据时系统的去重引擎的实现过程，在该示例中，以Hadoop的底层分布式文件系统HDFS作为实现的了本方案的系统原型，其中去重引擎的实现主要在DataNode中体现，具体步骤包括:
[0064]步骤71:在DataNode中DataXceiver线程负责接送并处理从Client发送过来的写请求，当SuperBlock发送到DataNode时，启动BlockReceiver线程负责对数据的接收和去重存储过程。
[0065]步骤72:首先BlockReceiver线程接收SuperBlock的数据路由特征指纹与元数据信息，通过与Hot Index和Simi larity Index索引表的查询匹配，确定需要匹配的Container，由于Container都是存储于磁盘的数据，可能需要进行10读操作，在实现过程中通过设计的LRU Cache，进行一次匹配，这样在一定程度上可以避免10操作，然后将确定Container元数据信息组成相似索引子集。
[0066]步骤73:在步骤72中加载得到相似索引子集后，就可以对SuperBlock中的数据进行索引查找。如果匹配到，则不必在对原数据进行存储，如果没有匹配到，则选择一个开放的Container，并将未去重的数据进行存储。最后，将SuperBlock的中每条chunk的存储信息写入磁盘Block Meta文件中。
[0067]需要说明的是，在上述示例中，还需要处理的一个重要方面就是对索引表的维护。索引更新主要分为三个部分:一是Cache中的索引更新，LRU Cache的更新是根据数据节点的读写请求并基于LRU方式对缓存进行更新；二是Similarity Index表的更新，当一个Container存储完毕后，需要选出Container中存储SuperBlock中对应的数据路由特征指纹更新到Simi larity Index索引库中，用于相似指纹的查找匹配;三是对应Hot Index库中的索引更新，由LRU Container Cache中对一个Container中chunk指纹的访问频率设定的，通过访问频率来定时更新Hot Index。
[0068]图8为根据本发明一个实施例的云存储系统中的数据重组过程示意图。如图8所示，展示了在云存储系统中数据服务器节点加载数据时在Hadoop中的数据重组过程，具体包括以下步骤:
[0069]步骤81:在DataNode中DataXceiver线程负责接送并处理从Client发送过来的读请求，当需要发送数据时，启动BlockSend线程负责对请求SuperBlock的本地读取与网络发送。
[°07°] 步骤82:首先，在启动子线程定位SuperBlock的Block Meta的物理存储位置后，加载Block Meta中所有chunk元数据到内存，然后针对chunk中的元数据，读取chunk的物理存储位置以及存储信息，并根据逻辑偏移量对SuperBlock进行数据重组。
[0071 ] 步骤83:在步骤82中对SuperBlock按照顺序组织其中的数据，然后由BlockSend线程将重组后的SuperBlock中的数据部分发送到客户端，客户端接收到数据后，按照SuperBlock的编号组织数据返回给用户请求的文件。
[0072]需要说明的是，在上述过程中，根据chunk的物理地址加载数据时，为了减轻随机读造成的磁盘瓶颈，在实现过程中，基于相似去重的 原理，一个SuperBlock中的chunk数据只会存在几个Container中，这样就会尽量减少打开文件的数量，在数据重组的过程中，不会产出太多的10操作请求打开很多的文件进行数据的重组，大大降低随机读的可能性。虽然这种方式在一定程度降低了数据去重率，但是在很大程度上减轻了对磁盘的读写需求，提升单节点的存储性能。
[0073]综上，本发明上述实施例的控制方法通过在分布式文件系统的基础上融入了集群重复数据删除技术，在云存储环境中构建大规模、高性能、分布式重删系统。其主要原理可概述为:控制每个客户端可以与集群交互进行数据的上传与下载;元数据服务器负责对每个客户端的读写请求响应以及负责整个集群的管理，并通过设计的局部相似路由算法，按照一定的采样策略提取数据路由特征指纹，按照有状态路由方式完成客户端存储数据的路由选择;数据服务器根据元数据服务器的调度完成对客户端的存储需求，当接收数据时按照设定的去重引擎进行数据的去重，当需要加载读取数据时根据数据重组引擎以完成对数据的重组过程。
[0074]根据本发明实施例的针对云存储系统中重复冗余数据的高效去重方法，通过在分布式文件系统的基础上融入了集群重复数据删除技术，在云存储环境中构建大规模、高性能、分布式重删系统，该方法能够有效地解决在大规模存储时冗余数据去重过程中的数据块查找的磁盘瓶颈问题，减少了指纹匹配的次数，从而提高了去重性能；另外，在具有重删功能的集群存储系统的数据路由选择上，可以快速定位数据路由地址，使系统保持高效的全局去重率；同时，该方法还可以减少路由选择过程中的网络带宽消耗，提升磁盘使用率，降低数据管理成本。
[0075]在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“长度”、“宽度”、“厚度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底” “内”、“外”、“顺时针”、“逆时针”、“轴向”、“径向”、“周向”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。
[0076]此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。
[0077]在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体;可以是机械连接，也可以是电连接;可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。
[0078]在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。
[0079]在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0080]尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。
【主权项】
1.一种针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述系统包括多个数据存储服务器组成的集群以及多个客户端，其中，所述多个数据存储服务器组成的集群包括由多个数据服务器组成的数据服务器集群和一个元数据服务器，所述方法包括以下步骤: S1:所述多个客户端接收用户的上传数据，将所述数据组织成数据超块以作为数据路由单位，并提取其中的数据路由特征指纹，用于数据路由选择； S2:所述元数据服务器与数据服务器集群根据路由策略来处理所述多个客户端的数据路由选择请求，其中，所述数据服务器集群对所述数据路由特征指纹进行相似指纹匹配以确定相似路由节点，所述元数据服务器根据负载均衡策略确定最终的数据路由地址； S3:确定数据路由地址后，所述客户端与相应的数据服务器进行交互，以将相似冗余数据发送至选择的数据服务器，所述选择的数据服务器在接收到相似冗余数据后，在线对冗余数据进行快速去重。2.根据权利要求1所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，根据局部相似路由算法生成所述路由策略。3.根据权利要求1所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述步骤S2进一步包括: 在上传数据时，每个客户端对所述数据超块进行逻辑划分，生成多个数据段，并根据采样策略对每个数据段进行指纹采样，以获取数据路由特征指纹； 所述客户端与集群中的各数据服务器进行指纹数据交互，通过查询相似索引表确定各数据服务器的匹配信息； 所述客户端与元数据服务器进行通信，根据所述各数据服务器的匹配信息与集群中选择的路由节点使用情况，确定最终的数据路由地址。4.根据权利要求3所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述各数据服务器的匹配信息包括每个数据服务器的匹配成功的指纹个数。5.根据权利要求3所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述采样策略是基于布罗德最小独立置换原理，对每个数据段进行指纹采样，并获取数据路由特征指纹。6.根据权利要求1所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述步骤S3进一步包括: 所述数据服务器在接收到客户端发送的存储请求时，启动相应的数据处理线程，对到达的数据超块进行处理； 所述数据服务器在接收数据时，根据数据路由特征指纹将相似容器元数据加载到内存的相似索引查找子集，并与到达的数据超块进行数据冗余匹配； 如果未匹配到相似的数据超块，则结合热点索引库进一步地进行数据去重处理。7.根据权利要求6所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，其中，所述数据服务器集群根据系统缓存中相似冗余数据的访问频率异步更新所述热点索引库。
【专利摘要】本发明提出一种针对云存储系统中重复冗余数据的高效去重方法，包括以下步骤：多个客户端接收用户的上传数据，以数据超块作为数据路由单位，并提取其中的路由特征指纹，用于数据路由选择；元数据服务器与数据服务器集群根据路由策略来处理客户端的数据路由选择请求，其中，数据服务器集群对路由特征指纹进行相似指纹匹配确定相似路由节点，元数据服务器根据负载均衡策略确定最终的数据路由地址；客户端与相应的数据服务器交互，接收到相似冗余数据的数据服务器对冗余数据进行高效快速去重。本发明的方法能够使云存储系统在保持高性能、大规模、高吞吐的系统特性的同时，达到高效的重复冗余数据去重效果，提升磁盘使用率，降低数据管理成本。
【IPC分类】G06F3/06
【公开号】CN105487818
【申请号】CN201510848801
【发明人】张广艳, 杨松霖, 舒继武, 郑纬民
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月27日
【技术领域】
[0001]本发明涉及计算机信息存储技术领域，特别涉及一种针对云存储系统中重复冗余数据的高效去重复方法。
【背景技术】
[0002]重复数据删除技术是一种粗粒度的无损的冗余数据去除的特殊数据压缩技术。重复数据删除技术通过对数据进行粗粒度的划分，然后通过指纹计算技术提取数据块的Hash指纹，通过指纹的索引查询来判断数据是否冗余，如果新数据块与存储系统中已有数据内容相同，则不会对新数据进行存储，而是通过保存指向原有数据块的指针，确定数据的存储位置，对于指针存储的开销远远小于对数据的占用空间。因此，重复数据删除技术可以有效的提升存储系统的空间使用率，节省磁盘存储容量。
[0003]云存储环境中实现重复数据删除技术是指在云存储架构中加入重删功能，提升存储空间利用率，降低存储成本。在大规模集群中，实现海量数据的存储，基于块级别的在线重复数据删除技术在数据去重率以及存储管理开销上具有很大的优势，受到学术界以及工业界的广泛认可与应用。但是在大规模存储系统中，也存在两大挑战，一是数据块索引查询磁盘瓶颈，二是大规模数据路由问题。
[0004]在重复数据删除过程中，对数据块的去重是基于指纹的查找与匹配来判定的。因此索引查询优化是提高重删系统I/O性能，解决磁盘查找瓶颈的关键因素。目前针对于数据块索引优化的策略主要有三类:一是基于数据局部性的优化策略；二是基于相似性理论的优化策略;三是基于SSD的索引优化策略。在集群存储系统中，数据的存储位置是衡量一个存储系统的重要指标，因为这不仅涉及到各节点存储的负载均衡性，也会对上层应用造成一定的影响。而在集群重复数据删除过程中，出于对系统整体性能开销的考虑，跨节点的全局去重会严重降低系统存储性能，所以一般都是采用只对节点内部数据进行数据去重。所以基于集群重复数据删除技术的集群重删系统在数据路由问题上，将会对系统整体去重效果产生很大影响。
【发明内容】
[0005]本发明旨在至少在一定程度上解决上述相关技术中的技术问题之一。
[0006]为此，本发明的目的在于提出一种针对云存储系统中重复冗余数据的高效去重方法，该方法能够快速地在云存储系统中去除冗余数据，提升存储磁盘利用率，保证系统的吞吐性能，从而降低存储成本。
[0007]为了实现上述目的，本发明的实施例提出了一种针对云存储系统中重复冗余数据的高效去重方法，所述云存储系统包括多个数据存储服务器和多个客户端，其中，所述多个数据存储服务器组成的集群包括由多个数据服务器组成的数据服务器集群和一个元数据服务器，所述方法包括以下步骤:S1:所述多个客户端接收用户的上传数据，将所述数据组织成数据超块以作为数据路由单位，并提取其中的数据路由特征指纹，用于数据路由选择；S2:所述元数据服务器与数据服务器集群根据路由策略来处理所述多个客户端的数据路由选择请求，其中，所述数据服务器集群对所述数据路由特征指纹进行相似指纹匹配以确定相似路由节点，所述元数据服务器根据负载均衡策略确定最终的数据路由地址;S3:确定数据路由地址后，所述客户端与相应的数据服务器进行交互，以将相似冗余数据发送至选择的数据服务器，所述选择的数据服务器在接收到相似冗余数据后，在线对冗余数据进行快速去重。
[0008]根据本发明实施例的针对云存储系统中重复冗余数据的高效去重方法，通过在分布式文件系统的基础上融入了集群重复数据删除技术，在云存储环境中构建大规模、高性能、分布式重删系统，该方法能够有效地解决在大规模存储时冗余数据去重过程中的数据块查找的磁盘瓶颈问题，减少了指纹匹配的次数，从而提高了去重性能；另外，在具有重删功能的集群存储系统的数据路由选择上，可以快速定位数据路由地址，使系统保持高效的全局去重率；同时，该方法还可以减少路由选择过程中的网络带宽消耗，提升磁盘使用率，降低数据管理成本。
[0009]另外，根据本发明上述实施例的针对云存储系统中重复冗余数据的高效去重方法还可以具有如下附加的技术特征:
[0010]在一些示例中，根据局部相似路由算法生成所述路由策略。
[0011]在一些示例中，所述步骤S2进一步包括:在上传数据时，每个客户端对所述数据超块进行逻辑划分，生成多个数据段，并根据采样策略对每个数据段进行指纹采样，以获取数据路由特征指纹;所述客户端与集群中的各数据服务器进行指纹数据交互，通过查询相似索引表确定各数据服务器的匹配信息;所述客户端与元数据服务器进行通信，根据所述各数据服务器的匹配信息与集群中选择的路由节点使用情况，确定最终的数据路由地址。
[0012]在一些示例中，所述各数据服务器的匹配信息包括每个数据服务器的匹配成功的指纹个数。
[0013]在一些示例中，所述采样策略是基于布罗德最小独立置换原理，对每个数据段进行指纹采样，并获取数据路由特征指纹。
[0014]在一些示例中，所述步骤S3进一步包括:所述数据服务器在接收到客户端发送的存储请求时，启动相应的数据处理线程，对到达的数据超块进行处理;所述数据服务器在接收数据时，根据数据路由特征指纹将相似容器元数据加载到内存的相似索引查找子集，并与到达的数据超块进行数据冗余匹配;如果未匹配到的相似的数据超块，则结合热点索引库进一步地进行数据去重处理。
[0015]在一些示例中，其中，所述数据服务器集群根据系统缓存中相似冗余数据的访问频率异步更新所述热点索引库。
[0016]本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
【附图说明】
[0017]本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中:
[0018]图1是根据本发明一个实施例的针对云存储系统中重复冗余数据的高效去重方法的流程图；
[0019]图2是根据本发明一个实施例的针对云存储系统中重复冗余数据的高效去重系统的架构图；
[0020]图3是根据本发明另一个实施例的针对云存储系统中重复冗余数据的高效去重方法的流程示意图；
[0021 ]图4是根据本发明一个实施例的数据服务器中数据存储模型的设计图；
[0022]图5是根据本发明一个实施例的局部路由算法特征指纹选取过程示意图；
[0023]图6是根据本发明一个实施例的局部路由算法有状态路由选择过程示意图；
[0024]图7是根据本发明一个实施例的云存储系统中的数据写入过程示意图；
[0025]图8是根据本发明一个实施例的云存储系统中的数据重组过程示意图。
【具体实施方式】
[0026]下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
[0027]以下结合附图描述根据本发明实施例的针对云存储系统中重复冗余数据的高效去重方法。
[0028]首先结合图2所示，本发明实施例中的云存储系统例如包括多个数据存储服务器组成的集群以及多个客户端，其中，多个数据存储服务器组成的集群包括由多个数据服务器组成的数据服务器集群和一个元数据服务器。
[0029]图1是根据本发明一个实施例的针对云存储系统中重复冗余数据的高效去重方法的流程图。如图1所示，该方法包括以下步骤:
[0030]步骤S101:多个客户端接收用户的上传数据，将数据组织成数据超块以作为数据路由单位，并提取其中的数据路由特征指纹，用于数据路由选择。
[0031]换言之，每个接入的客户端通过系统提供的对外交互接口进行数据的存储操作。根据提供的文件操作接口实现基于重复数据删除技术的存储逻辑，主要完成数据预处理阶段。具体包括:将数据组织成数据超块(SuperBlock)，然后通过网络与分布式文件系统中各节点进行交互以确定数据超块的路由地址，最后将数据与数据路由特征指纹发送到数据服务器。
[ 0032]具体地说，上述步骤S101包括:首先，客户端加载本地数据，采用⑶C算法将数据划分为chunk，按照超块组织方法组织成SuperBlock。其次，对SuperBlock中的所有chunk采用SHA1算法进行指纹计算，并提取出特征指纹，最后客户端负责将SuperBlock和对应特征指纹发送到由元数据服务器确定的路由地址节点中。
[0033]步骤S102:元数据服务器与数据服务器集群根据路由策略来处理多个客户端的数据路由选择请求，其中，数据服务器集群对数据路由特征指纹进行相似指纹匹配以确定相似路由节点，元数据服务器根据负载均衡策略确定最终的数据路由地址。其中，在本发明的一个实施例中，根据局部相似路由算法生成上述路由策略。
[0034]具体地说，在本发明的一个实施例中，步骤S102具体包括:
[0035]首先，在上传数据时，每个客户端对数据超块进行逻辑划分，生成多个数据段，并根据采样策略对每个数据段进行指纹采样，以获取数据路由特征指纹。更为具体地，在本发明的一个实施例中，采样策略是基于布罗德最小独立置换原理，对每个数据段进行指纹采样，并获取数据路由特征指纹。
[0036]然后，多个客户端与集群中的数据服务器进行指纹数据交互，通过查询相似索引表确定各数据服务器的匹配信息。
[0037]最后，多个客户端与元数据服务器进行通信，根据各数据服务器的匹配信息与集群中选择的路由节点使用情况，确定最终的数据路由地址。其中，在本发明的一个实施例中，每个数据服务器的匹配信息包括每个数据服务器的匹配情况，例如匹配个数。
[0038]简言之，即客户端通过将SuperBlock中采样选择的数据路由特征指纹发送到各个数据服务器进行匹配查询，然后，将匹配情况返回给元数据服务器，最后，元数据服务器根据各个数据服务器的匹配结果以及各个数据服务器的存储情况选择最佳的数据路由地址，并返回给客户端。
[0039]步骤S103:确定数据路由地址后，多个客户端与相应的数据服务器进行交互，以将相似冗余数据发送至选择的数据服务器，被选择的数据服务器在接收到相似冗余数据后，在线对冗余数据进行快速去重。
[0040]在本发明的一个实施例中，步骤S103具体包括:数据服务器在接收到多个客户端发送的存储请求时，启动相应的数据处理线程，对到达的数据超块进行处理;数据服务器在接收数据时，根据数据路由特征指纹将相似容器元数据加载到内存的相似索引查找子集，并与到达的数据超块进行数据冗余匹配;如果未匹配到相似的数据超块，则结合热点索引库进一步地进行数据去重处理。其中，在本发明的一个实施例中，数据服务器集群根据系统缓存中相似冗余数据的访问频率异步更新热点索引库。
[0041]具体地说，数据服务器通过网络与客户端进行通信，响应客户端的读写请求，与元数据服务器通过网络异步更新数据服务器的数据接收状况以及节点存储状况。换言之即，数据服务器负责对到达的SuperBlock进行去重，完成数据的接送功能，并汇报给元数据服务器。同时数据服务器也负责提取数据完成客户端的读请求。具体而言，在数据服务器端内进行去重过程中，利用数据的相似性与局部性通过相似匹配，并使用自描述的Container来管理数据和指纹的存储。当SuperBlock到达数据服务器时，根据相似索引加载最佳相似匹配的容器中所有的指纹信息，构成相似索引查找子集，SuperBlock通过与相似索引子集进行匹配进行去重，避免加载全局指纹到内存时的频繁10操作，降低了指纹查询的性能开销。虽然这样减少了一定的去重率，但是性能得到很大的提升。为了提升只匹配相似容器造成的去重率问题，根据数据流的局部性原理设计了容器缓存策略以及热点指纹索引策略来优化索引查询过程，进一步提升单节点数据去重率。
[0042]作为具体地示例，以下结合图3-8对本发明上述实施例的针对云存储系统中重复冗余数据的高效去重方法做进一步详细地描述。
[0043]具体而言，图3概括了本发明实施例的方法的数据重删过程。如图3所示，在该示例中，该方法主要包括以下步骤:
[0044]步骤31:首先，客户端对备份数据流进行分块划分，计算数据分块的指纹，将分块组织成SuperBlock，以用于数据路由传输。然后根据数据路由算法，提取出SuperBlock中的数据路由特征指纹，并与元数据服务器的数据路由引擎交互，确定SuperBlock的路由地址。最后根据选择的数据路由节点将SuperBlock发送到相应的数据服务器上进行数据存储。
[0045]步骤32:在上述步骤31中，最后需要确定SuperBlock的路由地址，元数据服务器通过路由选择策略，以局部相似路由算法为基础来确定最佳存储节点，同时在分配的过程中需要综合考虑系统中各节点的存储状态和检索结果，动态调节选择的存储节点，用于平衡数据服务器各节点的存储资源，达到系统的存储负载均衡。
[0046]步骤33:在上述步骤32中，确定SuperBlock的路由地址后，返回给客户端，客户端根据路由地址将SuperBlock发送到相应的数据服务器中，在选择的数据服务器中将数据去重的软件模块作为去重引擎，系统基于相似去重原理，当数据到达后，根据与相似索引表的匹配情况，从磁盘中加载相似索引子集用于数据的去重对比；同时为了提升系统性能，基于数据局部性的特点，设计LRU Cache，减少磁盘查找。
[0047]图4为根据本发明一个实施例的数据服务器中数据存储模型的设计图。如图4所示，在本系统架构设计中，数据去重的主要部分在数据服务器中，所以在数据服务中，需要快速查询判断数据是否重复，因此数据的存储组织模型是数据服务器设计的重点，也是去重系统保证数据去重率，优化指纹查询的关键。在该示例中，对于数据存储模型的设计主要包括以下步骤:
[0048]步骤41:例如Block Meta为SuperBlock对应的元数据，当SuperBlock被发送到本节点后，通过冗余数据去重后，需要对每个SuperBlock中的元数据信息进行保存，读取数据时可以根据Block Meta对应的元数据信息进行数据的重组，将数据提取出来。由于只有在数据读取时才会涉及到对Block Meta的加载，因此将元数据信息完全在磁盘上进行存储即可。
[0049]步骤42:例如Container是一个自描述的并且保存数据局部性的存储结构，包含数据部分和元数据(Con-Meta)部分。在数据存储过程中，数据服务器针对每个数据流始终保持一个开放的容器用以接收数据，当容器存储完毕时，需要封装容器，并打开一个空容器用以接收数据。同时为了提升系统的吞吐率，当多个数据流到达时，数据服务器满足对容器选择的并行化操作，可以同时打开几个未关闭且当前未使用的容器用于接收到达的数据。[OOM]步骤43:例如Similarity Index(相似索引表)存储于内存中的全局特征指纹索引表，表中每一条内容为本节点中Container的代表指纹与Container的ID之间的映射。如果将所有指纹信息加载在内存中，会造成严重的性能开销，因此，在该示例中，采用相似索引的概念，在全局保存相似索引表，表中的特征指纹依据数据相似性原理，在Container封闭时，得到容器中数据的相似代表指纹，通过将小部分的特征指纹来代表整个Container，减少了内存使用量，当新来数据匹配到相似指纹时，即可通过查找Similarity Index来定位Container，然后加载对应Container中的指纹信息。
[0051]步骤44:由于没有将所有指纹加载到内存，每次匹配到相似容器后都要将磁盘中Container的元数据加载到内存中，会造成多次的磁盘读操作，而且备份数据流中存在一定的局部性，因此设计了基于Container的容器缓存模块，其中每一条用于缓存一个Container中存储的所有分块指纹信息，S卩加载容器对应的Con-meta部分，并采用LRU方式对缓存进行更新。当Similarity Index命中一个Container时，首先查询Cache中是否包含了对应的Container，如果命中则可直接将Container在Cache中的所有指纹 信息加载，供新来数据匹配，如果未命中，则需要将对应Container中的所有指纹加载到Cache并提供给新来数据查询。
[0052]步骤45:在采用相似去重的过程中，冗余数据查找时并不能保证较高的去重率，因此在该示例中，根据备份数据流的特性设计了Hot Index(热点索引库)来进一步提升数据去重率。Hot Index也是存储于内存的Hash表，Hot Index是基于LRU Cache中每个容器中指纹访问频率来更新的。在一个Container中，所有指纹被匹配的频率，在一定的程度上可以更好的反应Container中的存储数据的状况。Hot Index中每一条内容为Cache中相应Container中匹配频率最大的前k条chunk指纹，与对应的Container的映射。通过将当前Cache中每个Container对应的热点指纹，加入到Hot Index中来代表Container，可以更好代表指纹在Container中的访问频率，以及备份数据流的特征。在去重过程中通过与HotIndex中的指纹进行匹配，确定相关Container，可以进一步提升在节点内的数据去重率。
[0053]图5为根据本发明一个实施例的云存储中集群重删系统局部路由算法特征指纹选取过程示意图。
[0054]具体而言，为了解决在大规模集群中加入重复数据删除技术引入的数据路由问题，同时为了达到集群存储系统高去重率、高性能以及负载均衡等目标，在该示例中，本发明的方法提出了一个面向重删的数据路由算法-局部相似路算法。该算法主要分为两个主要过程:一是数据路由特征指纹的选取过程，另一个是有状态路由选择过程。其中，数据路由特征指纹选取过程主要包括以下步骤:
[0055]步骤51:在路由粒度选择问题上，本发明的实施例采用固定大块的思想，将备份数据流进行大块划分，划分成SuperBlock，这样数据可以保持一定局部性特征。另外，在实验中测试得到:在SuperBlock大小为8M左右时，可以达到系统性能与去重的最佳效果。
[0056]步骤S52:针对每个SuperBlock，采用⑶C算法将数据划分为平均大小为4KB的数据块chunk，并计算每个chunk的指纹信息，然后SuperBlock中所有的chunk指纹信息构成的集合中，选出一定的指纹作为路由特征指纹，用以指导数据路由。在选择的过程中，基于布罗德最小独立置换原理进行选择。由于在SuperBlock中有2048条chunk指纹，基于数据局部性以及相似性的特点将SuperBlock进一步逻辑划分，将SuperBlock划分为逻辑大小相等的Segment (数据段)，其中每个Segment的大小由实验测得为512KB时最佳，即平均128个chunk组成一个Segment。
[0057]步骤S53:经过步骤S52的数据组织后，一个SuperBlock由16个逻辑的Segment组成，其中每个Segment又由128个chunk组成，然后根据布罗德最小独立置换原理选择每个Segment中最小分块的指纹作为Segment的代表指纹，最后将SuperBlock中选择出的16个指纹作为特征指纹作为路由选择依据。
[0058]图6为根据本发明一个实施例的云存储中集群重删系统局部路由算法有状态路由选择过程示意图。具体而言，在局部路由算法中，第二个主要的过程就是基于有状态的路由选择框架，如图6所示，该过程的主要包括以下步骤:
[0059]步骤61:客户端首先将SuperBlock选择出的特征指纹集合序列化，然后异步建立与数据服务的远程连接，将序列化的特征指纹集合发送到数据服务中。
[0060]步骤62:数据服务器接收到序列化的特征指纹集合后，反序列化数据，并与本地的Similarity Index进行索引查询，确定匹配成功的指纹个数，返回给客户端。
[0061]步骤63:客户端将得到的各数据服务器匹配成功的指纹个数，加入SuperBlock的地址请求队列中，发送到元数据服务器中。元数据服务器接收到SuperBlock地址请求后，根据集群中的使用情况，以及设计的负载判断情况，确定最佳的存储地址返回给客户端。
[0062]需要说明的是，在上述过程中，为了节省路由时的网络带宽消耗，在该示例中，采用基于相似的特征指纹选样方式，节约一定的性能消耗，同时，为了保证系统的去重率，采用有状态路由方式，根据匹配成功的指纹个数，确定最佳节点，避免无状态路由的不平衡性以及低去重率问题。
[0063]图7为根据本发明一个实施例的云存储系统中的数据写入过程示意图。同时，图7展示了在云存储实际系统中数据服务器节点接收数据时系统的去重引擎的实现过程，在该示例中，以Hadoop的底层分布式文件系统HDFS作为实现的了本方案的系统原型，其中去重引擎的实现主要在DataNode中体现，具体步骤包括:
[0064]步骤71:在DataNode中DataXceiver线程负责接送并处理从Client发送过来的写请求，当SuperBlock发送到DataNode时，启动BlockReceiver线程负责对数据的接收和去重存储过程。
[0065]步骤72:首先BlockReceiver线程接收SuperBlock的数据路由特征指纹与元数据信息，通过与Hot Index和Simi larity Index索引表的查询匹配，确定需要匹配的Container，由于Container都是存储于磁盘的数据，可能需要进行10读操作，在实现过程中通过设计的LRU Cache，进行一次匹配，这样在一定程度上可以避免10操作，然后将确定Container元数据信息组成相似索引子集。
[0066]步骤73:在步骤72中加载得到相似索引子集后，就可以对SuperBlock中的数据进行索引查找。如果匹配到，则不必在对原数据进行存储，如果没有匹配到，则选择一个开放的Container，并将未去重的数据进行存储。最后，将SuperBlock的中每条chunk的存储信息写入磁盘Block Meta文件中。
[0067]需要说明的是，在上述示例中，还需要处理的一个重要方面就是对索引表的维护。索引更新主要分为三个部分:一是Cache中的索引更新，LRU Cache的更新是根据数据节点的读写请求并基于LRU方式对缓存进行更新；二是Similarity Index表的更新，当一个Container存储完毕后，需要选出Container中存储SuperBlock中对应的数据路由特征指纹更新到Simi larity Index索引库中，用于相似指纹的查找匹配;三是对应Hot Index库中的索引更新，由LRU Container Cache中对一个Container中chunk指纹的访问频率设定的，通过访问频率来定时更新Hot Index。
[0068]图8为根据本发明一个实施例的云存储系统中的数据重组过程示意图。如图8所示，展示了在云存储系统中数据服务器节点加载数据时在Hadoop中的数据重组过程，具体包括以下步骤:
[0069]步骤81:在DataNode中DataXceiver线程负责接送并处理从Client发送过来的读请求，当需要发送数据时，启动BlockSend线程负责对请求SuperBlock的本地读取与网络发送。
[°07°] 步骤82:首先，在启动子线程定位SuperBlock的Block Meta的物理存储位置后，加载Block Meta中所有chunk元数据到内存，然后针对chunk中的元数据，读取chunk的物理存储位置以及存储信息，并根据逻辑偏移量对SuperBlock进行数据重组。
[0071 ] 步骤83:在步骤82中对SuperBlock按照顺序组织其中的数据，然后由BlockSend线程将重组后的SuperBlock中的数据部分发送到客户端，客户端接收到数据后，按照SuperBlock的编号组织数据返回给用户请求的文件。
[0072]需要说明的是，在上述过程中，根据chunk的物理地址加载数据时，为了减轻随机读造成的磁盘瓶颈，在实现过程中，基于相似去重的 原理，一个SuperBlock中的chunk数据只会存在几个Container中，这样就会尽量减少打开文件的数量，在数据重组的过程中，不会产出太多的10操作请求打开很多的文件进行数据的重组，大大降低随机读的可能性。虽然这种方式在一定程度降低了数据去重率，但是在很大程度上减轻了对磁盘的读写需求，提升单节点的存储性能。
[0073]综上，本发明上述实施例的控制方法通过在分布式文件系统的基础上融入了集群重复数据删除技术，在云存储环境中构建大规模、高性能、分布式重删系统。其主要原理可概述为:控制每个客户端可以与集群交互进行数据的上传与下载;元数据服务器负责对每个客户端的读写请求响应以及负责整个集群的管理，并通过设计的局部相似路由算法，按照一定的采样策略提取数据路由特征指纹，按照有状态路由方式完成客户端存储数据的路由选择;数据服务器根据元数据服务器的调度完成对客户端的存储需求，当接收数据时按照设定的去重引擎进行数据的去重，当需要加载读取数据时根据数据重组引擎以完成对数据的重组过程。
[0074]根据本发明实施例的针对云存储系统中重复冗余数据的高效去重方法，通过在分布式文件系统的基础上融入了集群重复数据删除技术，在云存储环境中构建大规模、高性能、分布式重删系统，该方法能够有效地解决在大规模存储时冗余数据去重过程中的数据块查找的磁盘瓶颈问题，减少了指纹匹配的次数，从而提高了去重性能；另外，在具有重删功能的集群存储系统的数据路由选择上，可以快速定位数据路由地址，使系统保持高效的全局去重率；同时，该方法还可以减少路由选择过程中的网络带宽消耗，提升磁盘使用率，降低数据管理成本。
[0075]在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“长度”、“宽度”、“厚度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底” “内”、“外”、“顺时针”、“逆时针”、“轴向”、“径向”、“周向”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。
[0076]此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。
[0077]在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体;可以是机械连接，也可以是电连接;可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。
[0078]在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。
[0079]在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0080]尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。
【主权项】
1.一种针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述系统包括多个数据存储服务器组成的集群以及多个客户端，其中，所述多个数据存储服务器组成的集群包括由多个数据服务器组成的数据服务器集群和一个元数据服务器，所述方法包括以下步骤: S1:所述多个客户端接收用户的上传数据，将所述数据组织成数据超块以作为数据路由单位，并提取其中的数据路由特征指纹，用于数据路由选择； S2:所述元数据服务器与数据服务器集群根据路由策略来处理所述多个客户端的数据路由选择请求，其中，所述数据服务器集群对所述数据路由特征指纹进行相似指纹匹配以确定相似路由节点，所述元数据服务器根据负载均衡策略确定最终的数据路由地址； S3:确定数据路由地址后，所述客户端与相应的数据服务器进行交互，以将相似冗余数据发送至选择的数据服务器，所述选择的数据服务器在接收到相似冗余数据后，在线对冗余数据进行快速去重。2.根据权利要求1所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，根据局部相似路由算法生成所述路由策略。3.根据权利要求1所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述步骤S2进一步包括: 在上传数据时，每个客户端对所述数据超块进行逻辑划分，生成多个数据段，并根据采样策略对每个数据段进行指纹采样，以获取数据路由特征指纹； 所述客户端与集群中的各数据服务器进行指纹数据交互，通过查询相似索引表确定各数据服务器的匹配信息； 所述客户端与元数据服务器进行通信，根据所述各数据服务器的匹配信息与集群中选择的路由节点使用情况，确定最终的数据路由地址。4.根据权利要求3所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述各数据服务器的匹配信息包括每个数据服务器的匹配成功的指纹个数。5.根据权利要求3所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述采样策略是基于布罗德最小独立置换原理，对每个数据段进行指纹采样，并获取数据路由特征指纹。6.根据权利要求1所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，所述步骤S3进一步包括: 所述数据服务器在接收到客户端发送的存储请求时，启动相应的数据处理线程，对到达的数据超块进行处理； 所述数据服务器在接收数据时，根据数据路由特征指纹将相似容器元数据加载到内存的相似索引查找子集，并与到达的数据超块进行数据冗余匹配； 如果未匹配到相似的数据超块，则结合热点索引库进一步地进行数据去重处理。7.根据权利要求6所述的针对云存储系统中重复冗余数据的高效去重方法，其特征在于，其中，所述数据服务器集群根据系统缓存中相似冗余数据的访问频率异步更新所述热点索引库。
【专利摘要】本发明提出一种针对云存储系统中重复冗余数据的高效去重方法，包括以下步骤：多个客户端接收用户的上传数据，以数据超块作为数据路由单位，并提取其中的路由特征指纹，用于数据路由选择；元数据服务器与数据服务器集群根据路由策略来处理客户端的数据路由选择请求，其中，数据服务器集群对路由特征指纹进行相似指纹匹配确定相似路由节点，元数据服务器根据负载均衡策略确定最终的数据路由地址；客户端与相应的数据服务器交互，接收到相似冗余数据的数据服务器对冗余数据进行高效快速去重。本发明的方法能够使云存储系统在保持高性能、大规模、高吞吐的系统特性的同时，达到高效的重复冗余数据去重效果，提升磁盘使用率，降低数据管理成本。
【IPC分类】G06F3/06
【公开号】CN105487818
【申请号】CN201510848801
【发明人】张广艳, 杨松霖, 舒继武, 郑纬民
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月27日
最新回复(0)