Hash 算法在去重技术中的运用

时间:2017-03-24

Hash 算法 Hash一般翻译为散列,或音译为哈希,就是把任意长度的输入(称为预映射) 通过Hash算法变换成固定长度的输出,该输出就是Hash值。

这种转换是一种压缩映射, Hash值的空间通常远小于输入的空间。 Hash 算法的数学表述为:CA= Hc(content) 其中: Hc---单向 Hash 函数,content---任意长度字符串,CA---固定长度 Hash 值。 Hash 算法在信息安全领域中广泛应用,具有如下关键特性:

第一:单向性(one-way),

从预映射,能够简单迅速的得到Hash值,而在计算上不 可能构造一个预映射,使其Hash结果等于某个特定的Hash值,即构造相应的content=Hc-1 (CA) 不可行。 第二:抗冲突性(collision-resistant),即在统计上无法产生 2 个 Hash 值相同的预 映射。给定 content,计算上无法找到 content´,满足 Hc(content)=Hc(content´),此 谓弱抗冲突性;计算上也难以寻找一对任意的 content 和 content´使满足,此谓强抗冲突 性。

第三:映射分布均匀性和差分分布均匀性,

Hash 结果中,为 0 的 位 和为 1 的 位,其总数应该大致相等;输入中一个位的变化,Hash 结果中将有一半以上的位改变, 这又叫做雪崩效应(avalanche effect);要实现使 Hash 结果中出现 1 位的变化,则输入 中至少有一半以上的位必须发生变化。 MD5 和 SHA1 可以说是目前应用最广泛的 Hash 算法。MD5(RFC 1321)是对输 入以 512 位分组,其输出是 4 个 32 位字的级联,尽管 MD5 被破解过,但仍然比较安全; SHA1 产生长度为 160 位的 Hash 值,因此抗穷举(brute-force)性更好。 Hash 算法可以看作管道,文件内容从一端流入,文件或数据块的 Hash 就从另一端 流出,如图 1所示。

图1 Hash 计算过程的示意图 在存储领域中,Hash 算法首先被应用于内容寻址存储(Content Addreeable Storage, 29华南理工大学硕士学位论文 CAS),它用于在存储系统中唯一地表征特定的数据实体,称为内容地址(Content Address,CA)或数字指纹(fingerprint)。在 CAS 中,通过 Hash 实现一种独特文件寻 址与定位方法,并有效地消除文件复制。这可以说是重复数据删除技术的一个开端,不 过在重复数据删除技术中,一个文件可以计算一个 Hash,也可以分成多个数据块计算 多个 Hash。 Hash 用整个文件进行 Hash,然后对不同文件的 Hash 进行排序,将相同的文件找出。这 种方法好处是:在普通硬件条件下计算速度非常快,加州大学的研究表明,SHA-1 是 83MB/S,而 MD5 是 227MB/S;如果对很多文件进行了处理,可以检测到所有相同的 文件,节省存储空间是巨大的。这种方法的主要缺点是:即使不同文件存在很多相同的 数据,也不能被检测和实现冗余消除。

Hash 文件分块 Hash 方法类似于数据压缩技术,从本质上讲,数据压缩就是要消除信息 冗余。早期的数据压缩技术就是基于编码上的优化技术,对信息进行编码时,如果为出 现概率较高的字符串赋予较短的编码,为出现概率较低的字母赋予较长的编码,总的编 码长度就能缩短不少。统计文件里面的字符串概率要消耗很长的计算时间,实际的方法 是采用自适应编码的方式,也就是在压缩的时候统计字符串的概率。 现在应用更多的数据压缩技术是字典型的模式压缩。字典压缩算法就是构造一本实 际的字典,通用算法使用的动态创建字典方法,把每一个第一次出现的字符串放入字典 中,并用一个数字来表示,这个数字与此字符串在字典中的位置有关,并将这个数字存 入压缩文件中,如果这个字符串再次出现时,即可用表示它的数字来代替,并将这个数 字存入文件中,压缩完成后将串表丢弃。字典型的数据压缩方式压缩比例远远比编码上 的优化的压缩要高,而且这种压缩算法无论是在压缩还是在解压的执行效率都比编码优 化压缩要高得多。 字

典型数据压缩的关键问题是如何确定字符串的位置和字符串的长度。文件分块 Hash 与字典型数据压缩非常相似。 文件分块 Hash 分为两个步骤,首先是数据块的划分,然后对数据块进行 Hash。最 简单块的划分方法是数据块的大小固定,可变大小方法就是文件被分成大小可变的数据 块,块大小在一个规定的最小尺寸和最大尺寸之内,固定尺寸可以看成可变尺寸的退化。

重复数据删除技术 可变大小的数据块用一个滑动的窗口来划分,当滑动窗口的 Hash 值与一个基准值相匹 配时就创建一个分块,这样数据块的尺寸分布就可到达一个希望的情形。 通常,基准值可以采用 Rabin 指纹进行计算,并可通过设定块尺寸上下限减少块大 小变化范围。在确定数据块边界的同时,即增加一个滑动窗口,就可计算出数据块的 hash。对数据块的存储类似于整个文件 Hash 法的方式,相同的块用线性的块号进行标 识。虽然细化粒度比整个文件 Hash 要好,但每个块都进行 hash 计算以进行匹配,并必 须同时计算两个 Hash 序列;另外,固定块尺寸可以减少对块划分算法的需求,但相同 块的相似性检测将降低。分块 Hash 的缺点是,必须保存块的 hash 索引,当没有冗余存 在时,反而加进了不必要的开销,虽然存储开销不大,但当数据块的平均尺寸变大时 (1KB,甚至更大),冗余消除效率就会降到很低。

Copyright © 2017 . All rights reserved. 扬州飞浩数据处理服务有限公司 版权所有 Power by DedeCms  苏ICP备16040889号-2
返回顶部