device-mapper 塊級(jí)重刪 (dm dedup) <2>設(shè)計(jì)

二、dm dedup的原理

dmdedup在github上面的代碼：
https://github.com/dmdedup/dmdedup4.13
設(shè)計(jì)文檔
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.

上面是現(xiàn)有的資料，大家也可以直接下源碼和看原版的設(shè)計(jì)文檔。

我就直接開始，從它的設(shè)計(jì)開始說(shuō)起：

dmdedup的設(shè)計(jì)思想，其實(shí)非常簡(jiǎn)單，從圖中可以看出來(lái)三個(gè)主要的邏輯：
1、hash index
2、LBN Mapping
3、space manager

1.hash index，首先dm dmdedup支持非常多中hash算法，那么我們這里需要理解hash index產(chǎn)生的沖突概率
如果簡(jiǎn)單來(lái)講，大致的算法產(chǎn)生hash碰撞的概率如下：
對(duì)于n個(gè)hash 128，產(chǎn)生hash碰撞的概率為
?? p = （1＋2＋3＋...+(n-1))×r = (1/2)×n×(n-1)×r
如果hash 128為md5,r＝1/2e128 代入，得到重復(fù)的概率為：
???p = (1/2)×n×(n-1)x(1/2e128).
其中 硬盤可能產(chǎn)生數(shù)據(jù)的錯(cuò)誤的概率是10^-18 ~ 10^15,如果p<這個(gè)概率就可以極大的保證數(shù)據(jù)是真的可去重
那么n x (n -1) < 10^-18 /(1/2e128) => n = (1/3)x 10^20 約等于10^10，如果每個(gè)數(shù)據(jù)塊平均是4k，那么可代表大概是37TB,原論文這里說(shuō)是有100TB，我這里是粗略計(jì)算，也就是一個(gè)重刪集合的數(shù)據(jù)總量是可以確立的。
如果熟悉了它的hash index的原理，我們就可以確立下來(lái)，只要是數(shù)據(jù)范圍小于論文中描述的：100TB。
就可以使用hash index來(lái)描述，hash to pbn的關(guān)系。

2. LBN mapping 邏輯塊號(hào)映射，如果說(shuō)hash index是描述了所有存在的PBN（物理塊），那么LBN mapping則是描述了所有的有意義的PBN，LBN mapping這個(gè)應(yīng)該大家比較熟悉。他描述邏輯塊到物理塊的映射關(guān)系，在dm的另一個(gè)模塊Thin provisioning大量運(yùn)用這個(gè)思想。

3.space manager 空間管理器，好的，如果說(shuō)hash index和LBN mapping還不足夠讓你理解dedup的原理，那么space manager以后，似乎應(yīng)該是更清楚了一點(diǎn)。

我們剛才來(lái)談的三個(gè)組合在這里會(huì)將他們組合成一組邏輯映射關(guān)系。

這個(gè)邏輯處理大致分為三個(gè)步驟：
1、chunk DATA，這個(gè)是塊級(jí)映射中最常用的方法：切塊。在raid和快照中被廣泛使用。為了讓變化的數(shù)據(jù)得以清晰的記錄，切塊后的數(shù)據(jù)直接可以用它的lba來(lái)代表，這樣變化的數(shù)據(jù)就具有它的唯一確定域。
chunk的方式去讓每個(gè)request在chunk邊界為分割（例如：{lba:3k,size:4k}->{lba:3k,size=1k}+{lba:4k,size=3k}）

2、對(duì)于chunk data后的request，我們需要計(jì)算數(shù)據(jù)的HASH，并且查找是否這個(gè)HASH已經(jīng)存在。
如果存在，即代表有我們已經(jīng)有了這份數(shù)據(jù)，如果沒(méi)有而需要去spare manager申請(qǐng)chunk大小的block來(lái)放置這個(gè)request并且計(jì)算和保存它的hash值。
hash index的作用，主要用來(lái)描述某個(gè)hash-PBN是否已經(jīng)存在（即數(shù)據(jù)內(nèi)容相同）。

3.接下來(lái)是LBN的情況，這里共有四種情況：
首要介紹這里需要另一種LBN MAP，LBN-PBN的對(duì)應(yīng)關(guān)系，可以理解為呈現(xiàn)出的具備重刪功能的虛擬設(shè)備的映射表。
① no hash && no lbn，這種情況指的是沒(méi)有發(fā)現(xiàn)hash-PBN存在，并且也沒(méi)有發(fā)現(xiàn)LBN-PBN,也就是這個(gè)request的數(shù)據(jù)內(nèi)容是沒(méi)有見過(guò)的，并且他要被放置的位置也是新的，之前沒(méi)有訪問(wèn)過(guò)的。通常這是產(chǎn)生了新的文件和新的內(nèi)容。接來(lái)下就是需要把所需要的新的hash index和LBN都產(chǎn)生出來(lái)，并且記錄。

② no hash && lba，這種情況指的是hash-PBN是不存在的，但是LBN-PBN存在，說(shuō)明曾經(jīng)的某個(gè)LBN數(shù)據(jù)被更改成了新的內(nèi)容，因?yàn)槲覀僪ash的窗口是定長(zhǎng)的（4k or 8k），所以這種情況是較為常見。只要應(yīng)用層修改的數(shù)據(jù)小于4k，比如我們的文檔和代碼工作。出現(xiàn)這種情況程序需要去將曾經(jīng)的LBN-oldPBN給替換成新的LBN-newPBN，并且將hash index的refcount -1代表，我們少了一次映射在這個(gè)已經(jīng)存在的hash-PBN上，這時(shí)這個(gè)hash-PBN很可能成為了孤兒，沒(méi)有LBN與之map，但是程序并不著急釋放掉它，更希望它能夠被情況③所利用。

③ hash && no lba，這種情況說(shuō)明，來(lái)了一次最為想要的，在這種情況下只需要添加一條LBN-PBN的映射關(guān)系，并將PBN的引用+1，即可以節(jié)省一個(gè)BLOCK的空間。這就是最能夠體現(xiàn)重刪程序價(jià)值的地方，節(jié)省了實(shí)際空間。

④ hash && lba，這種情況指的是request的數(shù)據(jù)內(nèi)容是存在的，而且要訪問(wèn)的LBA也是存在的，但是這并不是代表數(shù)據(jù)一定沒(méi)有發(fā)生改變，因?yàn)閔ash-PBN的存在，僅僅是某個(gè)物理塊和request的內(nèi)容一樣，但是不代表曾經(jīng)的LBA里面存在內(nèi)存也是這個(gè)內(nèi)容，所以還需要判斷曾經(jīng)的LBA里面是否也是這個(gè)內(nèi)容，那么需要比對(duì)一下LBN-PBN ?= hash-PBN的PBN-number），如果不一樣就把PBN-old refcount -1和把PBN-new refcount+1，并且更新LBN-PBN。通常這種情況是：在一個(gè)系統(tǒng)下的批量文件同步/覆蓋的，這種情況副本A和副本B的引用不變，邏輯映射關(guān)系改變。

【本文只在51cto博客作者 “底層存儲(chǔ)技術(shù)” https://blog.51cto.com/12580077 個(gè)人發(fā)布，公眾號(hào)發(fā)布：存儲(chǔ)之谷】，如需轉(zhuǎn)載，請(qǐng)于本人聯(lián)系，謝謝。