并行重删如何保证效率？（下篇）
在“并行重删如何保证效率？（上篇）”中已经讲到，保证效率的奥秘关键在于指纹映射规则，那么这个规则具体是怎样实现的呢？下面我会用一个简化的示例来帮助大家理解。但在此之前我们先来了解一个名词——单向散列函数（One-way Hash Function）。
看了这么多枯燥的概念，和重删有什么关系呢？AnyBackup 的重删技术中的指纹计算使用的就是具有强抗碰撞性的单向散列函数，我们常说的指纹也就是散列值。回到我们讨论的核心——指纹映射规则。接下来用一个简化的示例来帮助大家理解这个规则，下面是一段 Python 代码：
什么是单向散列函数
- 单向散列函数有一个输入和一个输出，输入被称为消息（message），输出被称为散列值（hash value）。
- 消息的类型不受限制，可以是声音或者图片或者人类无法读懂的消息。因为单向散列函数会将任何输入作为单纯的比特序列来处理，即根据比特序列计算出散列值。
- 散列值的长度和消息的长度无关。无论消息是 1 比特，还是 100 MB，甚至是 100 GB，单向散列函数都会计算出固定长度的散列值，也被称为指纹。
- 单向散列函数实际应用在密码、压缩和重复数据删除技术中；常见的单向散列函数有 MD5、SHA-256 等
单向散列值的性质
- 根据任意长度的消息计算出固定长度的散列值。
- 能够快速计算出散列值。
- 消息不同散列值也不同。
- 密码技术中所使用的单向散列函数，必须同时具备“弱抗碰撞性”和“强抗碰撞性”。
- 碰撞。就是如果两份不同的输入，却产生相同的散列值，则称为“碰撞”。
- 抗碰撞性。难以发现碰撞的性质称为”抗碰撞性“。
- 弱抗碰撞性。当给定某条消息的散列值时，单向散列函数必须确保要找到和该条消息具有相同散列值的另外一条消息是非常困难的。单向散列函数都必须具备弱抗碰撞性。
- 强抗碰撞性。指要找到散列值相同的两条不同的消息是非常困难的，这里的散列值可以是任意值。
- 具备单向性。指的是无法通过散列值反推出消息的性质。
看了这么多枯燥的概念，和重删有什么关系呢？AnyBackup 的重删技术中的指纹计算使用的就是具有强抗碰撞性的单向散列函数，我们常说的指纹也就是散列值。回到我们讨论的核心——指纹映射规则。接下来用一个简化的示例来帮助大家理解这个规则，下面是一段 Python 代码：
def choose_node(file_path): # 定义选择节点的函数，这个函数接受一个参数：文件路径
"""模拟指纹映射规则的示例函数"""md5 = get_md5(file_path) # get_md5 函数的功能是计算文件的 MD5 值
md5_ascii = convert_ascii(md5) # convert_ascii 将 MD5 值的每个字符转为 ASCII 码
s = sum(md5_ascii) # 将每个字符的 ASCII 码值相加
node_count = 3 # 定义节点数为 3
node = s % node_count # ASCII 码的和对节点数取余
return node # 返回取余的结果，结果可能是 0、1、2，分别对应 3 个节点
上述函数其实就是用文件模拟备份数据的一个切片后的数据块，使用 MD5 作为单向散列算法（MD5 的强抗碰撞性已经被攻破，这里只是作为简单示例帮助理解，AnyBackup 不是使用这种算法），然后将 MD5 值转化为数值后简单的进行取余运算，就可以实现指纹到节点的映射。
接下来我将一个文件 D:\test.txt 拷贝一份为 C:\test2.txt，并分别作为 choose_node 函数的参数传入，来验证结果是否符合预期。为了更直观的查看运行过程，我添加了一些输出，将 md5 等变量打印出来：
拷贝的文件并未改变文件内容，所以散列值（指纹）一样，后续选择的节点也一样，符合指纹映射规则的预期。
相信通过以上的示例，可以帮助到大家理解并行重删中的指纹映射规则，再次说明下以上的示例都是我根据理解简化模拟的，软件代码里真正的使用的会强大完善很多。
最后我们再来总结回顾下 AnyBackup 并行重删：
参考资料：《图解密码技术》 [日] 结城浩
接下来我将一个文件 D:\test.txt 拷贝一份为 C:\test2.txt，并分别作为 choose_node 函数的参数传入，来验证结果是否符合预期。为了更直观的查看运行过程，我添加了一些输出，将 md5 等变量打印出来：
choose_node(r'D:\test.txt')
choose_node(r'C:\test2.txt')
执行结果：
file_path: D:\test.txt
md5: 87d9479fb312acf6de462e2d163038ed
md5_ascii: [56, 55, 100, 57, 52, 55, 57, 102, 98, 51, 49, 50, 97, 99, 102, 54, 100, 101, 52, 54, 50, 101, 50, 100, 49, 54, 51, 48, 51, 56, 101, 100]
s: 2252
node: 2
file_path: C:\test2.txt
md5: 87d9479fb312acf6de462e2d163038ed
md5_ascii: [56, 55, 100, 57, 52, 55, 57, 102, 98, 51, 49, 50, 97, 99, 102, 54, 100, 101, 52, 54, 50, 101, 50, 100, 49, 54, 51, 48, 51, 56, 101, 100]
s: 2252
node: 2
拷贝的文件并未改变文件内容，所以散列值（指纹）一样，后续选择的节点也一样，符合指纹映射规则的预期。
相信通过以上的示例，可以帮助到大家理解并行重删中的指纹映射规则，再次说明下以上的示例都是我根据理解简化模拟的，软件代码里真正的使用的会强大完善很多。
最后我们再来总结回顾下 AnyBackup 并行重删：
- 指纹库以逻辑指纹库和物理指纹库映射的形式分布到多个节点；利用多个节点的资源进行并行重删。
- 指纹通过一致的指纹映射规则发送至节点内进行查询；保证相同的指纹一定存放在同一节点指纹库内。
参考资料：《图解密码技术》 [日] 结城浩
赞
点个赞吧！
请就本文对您的益处进行评级：
