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 個人發布，公眾號發布：存儲之谷】，如需轉載，請于本人聯系，謝謝。