LOL赛事下注 - 英雄联盟投注 -(中国)Riot Games

　　MD5 和 SHA1 可以说是目前应用最广泛的 Hash 算法。MD5(RFC 1321)是对输入以 512 位分组，其输出是 4 个 32 位字的级联，尽管 MD5 被破解过，但仍然比较安全；SHA1 产生长 度为 160 位的 Hash 值，因此抗穷举(brute-force)性更好。 Hash 算法可以看作管道， 文件内容从一端流入， 文件或数据块的 Hash 就从另一端流出， 如图 2 所示。

　　content 和 content，使满足 H c (content )  H c (content ) ，此谓强抗冲突性。  第三是映射分布均匀性和差分分布均匀性，Hash 结果中，为 0 的 位 和为 1 的 位 ，其总数应该大致相等；输入中一个位的变化，Hash 结果中将有一半以上的位 改变，这又叫做雪崩效应(avalanche effect)；要实现使 Hash 结果中出现 1 位的 变化，则输入中至少有一半以上的位必须发生变化。

　　图 2 Hash 计算过程的示意图 在存储领域中，Hash 算法首先被应用于内容寻址存储（Content Addreeable Storage， CAS），它用于在存储系统中唯一地表征特定的数据实体，称为内容地址（Content Address， CA）或数字指纹（fingerprint）。 在 CAS 中，通过 Hash 实现一种独特文件寻址与定位方法， 并有效地消除文件复制。这可以说是重复数据删除技术的一个开端，不过在重复数据删除技术

　　块的划分方法是数据块的大小固定， 可变大小方法就文件被分成大小可变的数据块， 块大小 在一个规定的最小尺寸和最大尺寸之内， 固定尺寸可以看成可变尺寸的退化。 可变大小的数 据块用一个滑动的窗口来划分，当滑动窗口的 Hash 值与一个基准值相匹配时就创建一个分 块，这样数据块的尺寸分布就可到达一个希望的情形。 通常， 基准值可以采用 Rabin 指纹进行计算， 并可通过设定块尺寸上下限减少块大小变 化范围。在确定数据块边界的同时，即增加一个滑动窗口，就可计算出数据块的 hash。对 数据块的存储类似于整个文件 Hash 法的方式，相同的块用线性的块号进行标识。虽然细化 粒度比整个文件 Hash 要好，但每个块都进行 hash 计算以进行匹配，并必须同时计算两个 Hash 序列；另外，固定块尺寸可以减少对块划分算法的需求，但相同块的相似性检测将降 低。分块 Hash 的缺点是，必须保存块的 hash 索引，当没有冗余存在时，反而加进了不必要 的开销，虽然这存储开销不大，但当数据块的平均尺寸变大时（1KB，甚至更大） ，冗余消除 效率就会降到很低。 加州大学的研究结果： 使用与上相同普通的硬件条件下， 块尺寸设定为 64～16384 字节 范围，采用 32 位的 Rabin 指纹，文件分块 Hash 的处理速度为 36MB/S。 2.2.4 delta 压缩 Delta 压缩用于计算一个新文件和一个已经存储在系统中的参考文件之间的 delta 编 码，当两文件间的相似性超过了预先设定阀值时，那么就计算出一个 delta，并只需把这个 delta 存储在系统里。在具有相似性的文件集进行存储时，使用 delta 编码实现文件间压缩 可以极大地减少存储。Delta 压缩分四个步骤： 首先， 采用内容无关的方法从文件中选取特征集。 一种选取特征的方法是对整个文件沿 着字节边界的滑动窗口计算 Rabin 指纹。 滑动窗口的大小是一个预先选定的参数， 产生的中 间指纹数量与文件大小成正比。 然后， 在系统中找出一个与新文件具有高度相似性的参考文件。 为了加快检测的速度必 须减少了需要比较的指纹数量， 具体方法是把特征集降为超级特征或超级指纹组成的更小数 量的特征集合，选择固定数量的指纹作为特征子集，每个超级指纹是特征子集的一个 Hash。 如果一个或更多的超级指纹匹配了，那将可能有更大的相似性。 第三，对两个相似的文件计算 delta。由 delta 所得的存储效率与文件的相似性相关， 文件的相似性越高在降低存储空间的效率更高。加州大学的研究结果：Delta 压缩的性能较 差，相同的硬件条件下，采用 32 位的 Rabin 指纹，delta 编码的处理速度为 8.7MB/S。 最后，存储压缩文件。

　　数据备份系统中不同的备份中的数据具有极高的相似性， 而传统的备份方法会将许多文 件内容变化极少的、 甚至只是文件属性发生变化而内容没有改变的文件进行完整的备份， 因 此，将不同的备份集中重复数据量很大。 数据备份系统中重复数据删除技术分为基于 Hash 和基于内容识别的两种方法。 基于 Hash 的方法主要是采用 SHA-1、 MD5 或自己开发的算法， 将备份的数据流分成块并 且为每个数据块生成一个 Hash，如果新数据块的 Hash 与已备份数据块的 Hash 索引中的一 个 Hash 匹配，表明该数据块已经被备份，因此对数据块不进行存储，只更新备份数据索引 表。 基于内容识别的方法主采用文件的元数据进行文件识别，找到该文件已存储的版本后, 通过对不同版本文件进行比较来消除重复的数据。

　　为了理解文件相似性对重复数据删除效率的重要性，首先我们看看相似性与存储量之间 的关系。数据的相似性变化范围极大，压缩效率变化范围也很大，然而，文件相似性和文件 压缩量之间的关系是相同的。 使用不同版本的 Linux 的源代码来评估文件相似性，对 gzip 压缩（仅文件内压缩）与 delta 压缩（文件内文件间压缩）进行比较，结果见图 1：在 8 万多个文件(1GB 大小)中， 有相当多的文件具有很高的相似性，事实上，很多是相同的，gzip 压缩后文件体积减少到 原来的 25％到 30％，delta 压缩后文件体积减少到原来的 4%。这表明利用文件相似性对文 件内和文件间压缩大有好处，对文件内和文件间的冗余数量进行删除实现高压缩是可能的， 即使包含压缩计算产生的索引数据，因为这些数据不足原始数据总大小的 1％。

　　目前， 重复数据删除技术并没有成为一个独立存储产品， 而是作为存储系统的一个重要 功能。 首先， 重复数据删除技术为数据保护领域带来革命性突破， 有效地改善了基于磁盘数据 保护的成本效益。 因为在传统数据保护中无法实现重复数据删除的， 往往采用廉价的磁带库 作为备份设备，磁带备份在备份窗口、恢复速度方面难以用户的需求。现在，基于盘的数据 保护方案例如 VTL(虚拟磁带库)被广泛采用，并且在未来会继续增长。备份到 VTL 或其他基 于磁盘的备份已经缩短了备份窗口，改善了备份和恢复能力；但由于数据量的不断增加，我 们所要备份的数据越来越多，面临容量膨胀的压力，重复数据删除技术的出现，为最小化存 储容量找到有效的方法。 其次，重复数据删除技术对归档存储也非常重要。由于参考数据的数量不断增长，而法 规遵从要求数据在线保留的时间更长，并且由于高性能需求需要采用磁盘进行归档，因此， 企业一旦真正开始进行数据的归档存储就面临成本问题。 理想的归档存储系统应能满足长期 保存归档数据的需求， 并且总拥有成本也要低于生产环境。 重复数据删除技术通过消除冗余 实现高效率的归档存储，从而实现最低的成本。

　　同但是内容完全相同的文件，或者不同目录下相同的文件，可以避免相同文件的多次存储； 数据块冗余消除比文件复制消除的存储效率更高， 它可以在文件中搜索相同的数据块， 将相 同的块保存一个唯一的副本。 重复数据删除是一种独特存储技术， 分析师认为它可能是存储行业最重要的一项新兴技 术，将改写存储行业的经济规则：借助于重复数据删除技术，使得实际存档的数据呈几何级 别递减，用户的存档数据所占用的空间将会缩减为现在的 5%，从而大幅削减存储成本。

　　2.2.2 全文件 Hash 用整个文件进行 Hash，然后对不同文件的 Hash 进行排序，将相同的文件找出。这种方 法好处是：在普通硬件条件下计算速度非常快，加州大学的研究表明，SHA-1 是 83MB/S，而 MD5 是 227MB/S；如果对很多文件进行了处理，可以检测到所有相同的文件，节省存储空间 是巨大的。这种方法的主要缺点是：即使不同文件存在很多相同的数据，也不能被检测和实 现冗余消除。 2.2.3 文件分块 Hash 文件分块 Hash 的类似于数据压缩技术，从本质上讲，数据压缩就是要消除信息冗余。 早期的数据压缩技术就是基于编码上的优化技术， 对信息进行编码时， 如果为出现概率 较高的字符串赋予较短的编码， 为出现概率较低的字母赋予较长的编码， 总的编码长度就能 缩短不少。 统计文件里面的字符串概率要消耗很长的计算时间， 实际的方法是采用自适应编 码的方式，也就是在压缩的时候统计字符串的概率。 现在应用更多的数据压缩技术是字典型的模式压缩。 字典压缩算法就是构造一本实际的 字典，通用算法使用的动态创建字典方法，把每一个第一次出现的字符串放入字典中，并用 一个数字来表示， 这个数字与此字符串在字典中的位置有关， 并将这个数字存入压缩文件中， 如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中，压缩 完成后将串表丢弃。 字典型的数据压缩方式压缩比例远远比编码上的优化的压缩要高， 而且 这种压缩算法无论是在压缩还是在解压的执行效率都比编码优化压缩要高得多。 字典型数据压缩的关键问题是如何确定字符串的位置和字符串的长度。文件分块 Hash 与字典型数据压缩非常相似。 文件分块 Hash 分为两个步骤，首先是数据块的划分，然后对数据块进行 Hash。最简单