device-mapper 块级重删 (dm dedup) <2>设计

二、dm dedup的原理

dmdedup在github上面的代码：
https://github.com/dmdedup/dmdedup4.13
设计文档
http://www.fsl.cs.stonybrook.edu/docs/ols-dmdedup/dmdedup-ols14.pdf
作者：
dm-dedup was developed in the File system and Storage Lab (FSL) at Stony Brook University Computer Science Department, in collaboration with Harvey Mudd College and Dell-EMC.

Key people involved in the project were Vasily Tarasov, Geoff Kuenning, Sonam Mandal, Karthikeyani Palanisami, Philip Shilane, Sagar Trehan, and Erez Zadok.

We also acknowledge the help of several students involved in the deduplication project: Teo Asinari, Deepak Jain, Mandar Joshi, Atul Karmarkar, Gary Lent, Amar Mudrankit, Meg O'Keefe, Nidhi Panpalia, Vinothkumar Raja, Ujwala Tulshigiri and Nabil Zaman.

上面是现有的资料，大家也可以直接下源码和看原版的设计文档。

我就直接开始，从它的设计开始说起：

dmdedup的设计思想，其实非常简单，从图中可以看出来三个主要的逻辑：
1、hash index
2、LBN Mapping
3、space manager

1.hash index，首先dm dmdedup支持非常多中hash算法，那么我们这里需要理解hash index产生的冲突概率
如果简单来讲，大致的算法产生hash碰撞的概率如下：
对于n个hash 128，产生hash碰撞的概率为
   p = （1＋2＋3＋...+(n-1))×r = (1/2)×n×(n-1)×r
如果hash 128为md5,r＝1/2e128 代入，得到重复的概率为：
   p = (1/2)×n×(n-1)x(1/2e128).
其中 硬盘可能产生数据的错误的概率是10^-18 ~ 10^15,如果p<这个概率就可以极大的保证数据是真的可去重
那么n x (n -1) < 10^-18 /(1/2e128) => n = (1/3)x 10^20 约等于10^10，如果每个数据块平均是4k，那么可代表大概是37TB,原论文这里说是有100TB，我这里是粗略计算，也就是一个重删集合的数据总量是可以确立的。
如果熟悉了它的hash index的原理，我们就可以确立下来，只要是数据范围小于论文中描述的：100TB。
就可以使用hash index来描述，hash to pbn的关系。

2. LBN mapping 逻辑块号映射，如果说hash index是描述了所有存在的PBN（物理块），那么LBN mapping则是描述了所有的有意义的PBN，LBN mapping这个应该大家比较熟悉。他描述逻辑块到物理块的映射关系，在dm的另一个模块Thin provisioning大量运用这个思想。

3.space manager 空间管理器，好的，如果说hash index和LBN mapping还不足够让你理解dedup的原理，那么space manager以后，似乎应该是更清楚了一点。

我们刚才来谈的三个组合在这里会将他们组合成一组逻辑映射关系。

这个逻辑处理大致分为三个步骤：
1、chunk DATA，这个是块级映射中最常用的方法：切块。在raid和快照中被广泛使用。为了让变化的数据得以清晰的记录，切块后的数据直接可以用它的lba来代表，这样变化的数据就具有它的唯一确定域。
chunk的方式去让每个request在chunk边界为分割（例如：{lba:3k,size:4k}->{lba:3k,size=1k}+{lba:4k,size=3k}）

2、对于chunk data后的request，我们需要计算数据的HASH，并且查找是否这个HASH已经存在。
如果存在，即代表有我们已经有了这份数据，如果没有而需要去spare manager申请chunk大小的block来放置这个request并且计算和保存它的hash值。
hash index的作用，主要用来描述某个hash-PBN是否已经存在（即数据内容相同）。

3.接下来是LBN的情况，这里共有四种情况：
首要介绍这里需要另一种LBN MAP，LBN-PBN的对应关系，可以理解为呈现出的具备重删功能的虚拟设备的映射表。
① no hash && no lbn，这种情况指的是没有发现hash-PBN存在，并且也没有发现LBN-PBN,也就是这个request的数据内容是没有见过的，并且他要被放置的位置也是新的，之前没有访问过的。通常这是产生了新的文件和新的内容。接来下就是需要把所需要的新的hash index和LBN都产生出来，并且记录。

② no hash && lba，这种情况指的是hash-PBN是不存在的，但是LBN-PBN存在，说明曾经的某个LBN数据被更改成了新的内容，因为我们hash的窗口是定长的（4k or 8k），所以这种情况是较为常见。只要应用层修改的数据小于4k，比如我们的文档和代码工作。出现这种情况程序需要去将曾经的LBN-oldPBN给替换成新的LBN-newPBN，并且将hash index的refcount -1代表，我们少了一次映射在这个已经存在的hash-PBN上，这时这个hash-PBN很可能成为了孤儿，没有LBN与之map，但是程序并不着急释放掉它，更希望它能够被情况③所利用。

③ hash && no lba，这种情况说明，来了一次最为想要的，在这种情况下只需要添加一条LBN-PBN的映射关系，并将PBN的引用+1，即可以节省一个BLOCK的空间。这就是最能够体现重删程序价值的地方，节省了实际空间。

④ hash && lba，这种情况指的是request的数据内容是存在的，而且要访问的LBA也是存在的，但是这并不是代表数据一定没有发生改变，因为hash-PBN的存在，仅仅是某个物理块和request的内容一样，但是不代表曾经的LBA里面存在内存也是这个内容，所以还需要判断曾经的LBA里面是否也是这个内容，那么需要比对一下LBN-PBN ?= hash-PBN的PBN-number），如果不一样就把PBN-old refcount -1和把PBN-new refcount+1，并且更新LBN-PBN。通常这种情况是：在一个系统下的批量文件同步/覆盖的，这种情况副本A和副本B的引用不变，逻辑映射关系改变。

【本文只在51cto博客作者 “底层存储技术” https://blog.51cto.com/12580077 个人发布，公众号发布：存储之谷】，如需转载，请于本人联系，谢谢。