畢業(yè)設(shè)計(jì)（論文）基于iSCSI的重復(fù)數(shù)據(jù)刪除系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

1、摘 要信息化的快速發(fā)展致使數(shù)據(jù)量與日俱增，簡(jiǎn)單的存儲(chǔ)這些數(shù)據(jù)對(duì)企業(yè)而言并不是最佳的解決方案存儲(chǔ)需要投入成本，大量的文件最終將會(huì)加重企業(yè)數(shù)據(jù)備份以及災(zāi)難恢復(fù)系統(tǒng)的負(fù)擔(dān)。企業(yè)與其不斷的擴(kuò)充磁盤容量來(lái)應(yīng)對(duì)數(shù)據(jù)量的增加，還不如轉(zhuǎn)向數(shù)據(jù)刪除技術(shù)，以存儲(chǔ)更少的數(shù)據(jù)。近年來(lái)新興的重復(fù)數(shù)據(jù)刪除技術(shù)就是減少存儲(chǔ)空間的有效方式之一。通過(guò)對(duì)重復(fù)數(shù)據(jù)刪除技術(shù)的深入研究，提出了一種基于 iscsi 平臺(tái)的重復(fù)數(shù)據(jù)刪除存儲(chǔ)系統(tǒng)。該系統(tǒng)實(shí)現(xiàn)了 lba 映射、指紋計(jì)算、指紋檢索和指紋索引表管理等功能。通過(guò) lba 映射表的組織和管理，實(shí)現(xiàn)了重復(fù)數(shù)據(jù)刪除前后數(shù)據(jù)塊邏輯地址的轉(zhuǎn)化和對(duì)應(yīng)關(guān)系；指紋計(jì)算模塊中采用基于散列的 sha-

2、1 算法，實(shí)現(xiàn)了將 4kb 數(shù)據(jù)塊轉(zhuǎn)化為 160 位摘要值的過(guò)程；指紋檢索和指紋索引表的管理采用三級(jí)索引結(jié)構(gòu)，實(shí)現(xiàn)了指紋的精確定位和快速查找。為了彌補(bǔ)重復(fù)數(shù)據(jù)刪除帶來(lái)的系統(tǒng)性能的損失，針對(duì)重復(fù)數(shù)據(jù)刪除功能中指紋檢索性能瓶頸進(jìn)行了優(yōu)化，提出了基于布魯姆過(guò)濾的指紋檢索算法，大量的指紋檢索請(qǐng)求被過(guò)濾掉，從而提高檢索效率。對(duì)系統(tǒng)性能、重復(fù)數(shù)據(jù)刪除壓縮比和檢索過(guò)濾算法的效果進(jìn)行了相關(guān)測(cè)試。分別測(cè)試了標(biāo)準(zhǔn) iscsi 和加入重復(fù)數(shù)據(jù)刪除模塊后的 iscsi 系統(tǒng)的性能，結(jié)果表明，加入重復(fù)數(shù)據(jù)刪除之后，雖然系統(tǒng)性能有所下降，但是下降的幅度還是預(yù)期的范圍之內(nèi)；對(duì)重復(fù)數(shù)據(jù)刪除壓縮比進(jìn)行了測(cè)試，測(cè)試結(jié)果表明壓縮效

3、果的好壞與應(yīng)用環(huán)境密切相關(guān)，當(dāng)應(yīng)用于那些信息重復(fù)度較高的環(huán)境如備份存儲(chǔ)系統(tǒng)、歸檔存儲(chǔ)系統(tǒng)等時(shí)，具有較好的壓縮效果；最后對(duì)檢索過(guò)濾算法進(jìn)行了測(cè)試，測(cè)試出的過(guò)濾率和誤判率都可以達(dá)到預(yù)期效果。關(guān)鍵詞關(guān)鍵詞：重復(fù)數(shù)據(jù)刪除，指紋檢索優(yōu)化，存儲(chǔ)性能abstractresulted in the rapid development of information technology increasing the amount of data, simple storage of these data to enterprises is not the best solution - storage need

4、s input costs, a large number of documents that will ultimately increase the enterprise data backup and disaster recovery burden. compared to expand disk capacity to respond to the increase in the amount of data, companies might as well turn to remove the technical data to store less data.in recent

5、years, new data deduplication technology is one of effective way to reduce storage space.data de-duplication technology by further research, a platform based on iscsi deduplication storage systems. this system has lba mapping, fingerprint calculation, fingerprints and fingerprint search index table

6、management. lba mapping table by the organization and management, and data de-duplication before data blocks the conversion of logical address and correspondence; fingerprint calculation module based on sha-1 hash algorithm, implemented into the 4kb block 160 summary value of the process; fingerprin

7、ts and fingerprint index table to retrieve the management of all three index structure is used to achieve precise positioning and fast fingerprint search. to make up for deduplication performance caused the loss of data deduplication feature for fingerprint retrieval performance bottlenecks, for a s

8、pecial algorithm optimization, proposed fingerprint retrieval based on bloom filter filtering algorithm to filter out a large number of fingerprint retrieval request, thereby enhancing the efficiency of retrieval. on system performance, data deduplication, compression ratio and the effect of filteri

9、ng algorithms to retrieve the relevant tests. iscsi and standard were tested by adding data deduplication module of the iscsi system performance, results show that adding data deduplication, the system performance has declined; on data deduplication compression ratio were tested, the test results sh

10、ow that good compression bad environment is closely related with the application, when applied to repeat that information environment such as a higher degree of backup storage systems, archival storage systems, etc., and has good compression effect; finally, the search filter algorithm has been test

11、ed, tested the filtration rate and false positive rate can achieve the desired results. keywords: de-duplication, fingerprint search optimization, storage performance目 錄摘摘 要要 .iabstract .ii目目 錄錄.iv1緒緒 論論.11.1課題背景.11.2課題研究目的及意義.21.3國(guó)內(nèi)外發(fā)展現(xiàn)狀.21.4課題的主要研究工作.41.5課題的來(lái)源.52系統(tǒng)關(guān)鍵技術(shù)概述系統(tǒng)關(guān)鍵技術(shù)概述 .62.1iscsi 平臺(tái)簡(jiǎn)介.62

12、.2重復(fù)數(shù)據(jù)簡(jiǎn)介.72.3重復(fù)數(shù)據(jù)刪除的基本原理 .82.4數(shù)據(jù)處理粒度分析.92.5bloom filter 算法 .102.6本章小結(jié).133重復(fù)數(shù)據(jù)刪除方案設(shè)計(jì)重復(fù)數(shù)據(jù)刪除方案設(shè)計(jì).143.1系統(tǒng)功能需求.143.2系統(tǒng)總體設(shè)計(jì).143.3lba 映射表.163.4指紋計(jì)算模塊.163.5指紋管理和檢索模塊.173.6基于 bloom filter 算法的指紋檢索優(yōu)化.193.7本章小結(jié).204重復(fù)數(shù)據(jù)刪除系統(tǒng)實(shí)現(xiàn)重復(fù)數(shù)據(jù)刪除系統(tǒng)實(shí)現(xiàn).214.1lba 映射表實(shí)現(xiàn).214.2指紋計(jì)算模塊實(shí)現(xiàn).224.3指紋索引表的建立與指紋檢索 .224.4bloom filter 過(guò)濾算法的實(shí)現(xiàn).23

13、4.5處理流程分析.244.6本章小結(jié).275系統(tǒng)測(cè)試與分析系統(tǒng)測(cè)試與分析.285.1測(cè)試環(huán)境介紹.285.2測(cè)試結(jié)果及分析.285.3本章小結(jié).326總結(jié)與展望總結(jié)與展望.336.1總結(jié).336.2未來(lái)展望.33致致 謝謝.35參考文獻(xiàn)參考文獻(xiàn).361緒 論本章首先介紹了當(dāng)前存儲(chǔ)系統(tǒng)面臨的挑戰(zhàn)和技術(shù)發(fā)展趨勢(shì)，然后簡(jiǎn)述了本論文研究的目的及意義，接著分析了重復(fù)數(shù)據(jù)刪除技術(shù)的發(fā)展現(xiàn)狀，介紹了國(guó)內(nèi)外在重復(fù)數(shù)據(jù)刪除領(lǐng)域的相關(guān)研究工作，最后對(duì)本文的主要研究?jī)?nèi)容及課題來(lái)源作了具體說(shuō)明。1.1課題背景隨著信息化時(shí)代的推進(jìn)，各企事業(yè)單位的信息數(shù)據(jù)量也不斷增長(zhǎng)，存儲(chǔ)管理員不斷努力地處理日益激增的數(shù)據(jù)，比如，文本

14、、聲頻、視頻、圖像，還有不斷增加的大容量郵件附件。然而存儲(chǔ)這些數(shù)據(jù)對(duì)企業(yè)而言并不是最佳的解決方案存儲(chǔ)需要投入成本，大量的文件最終將會(huì)加重企業(yè)數(shù)據(jù)備份以及災(zāi)難恢復(fù)系統(tǒng)的負(fù)擔(dān)。企業(yè)與其尋求更多的存儲(chǔ)數(shù)據(jù)的不同方式，還不如轉(zhuǎn)向數(shù)據(jù)刪除技術(shù)，以存儲(chǔ)更少的數(shù)據(jù)。近年來(lái)新興的重復(fù)數(shù)據(jù)刪除技術(shù)1就是減少存儲(chǔ)空間的一種方式，它通過(guò)識(shí)別和消除數(shù)據(jù)環(huán)境中的冗余數(shù)據(jù)，確保只將單一的數(shù)據(jù)保存在存儲(chǔ)介質(zhì)中，從而節(jié)省了大量的存儲(chǔ)空間，降低了存儲(chǔ)成本。這意味著只需要更少的磁盤和更低頻率的磁盤采購(gòu)。更有效地利用磁盤空間，就能夠延長(zhǎng)磁盤保存期限，這樣，提供了更好的恢復(fù)時(shí)間目標(biāo)，更長(zhǎng)的備份時(shí)間。同時(shí)，重復(fù)數(shù)據(jù)刪除還可以縮減必須通

15、過(guò)無(wú)線網(wǎng)絡(luò)傳送來(lái)實(shí)現(xiàn)遠(yuǎn)程備份、復(fù)制和災(zāi)難恢復(fù)的數(shù)據(jù)2。這樣不僅顯著提高現(xiàn)有磁盤存儲(chǔ)空間的有效容量，從而使保護(hù)數(shù)據(jù)所需的物理磁盤數(shù)量更少，還有助于企業(yè)對(duì)數(shù)據(jù)的維護(hù)管理。這便可以幫助企業(yè)減輕硬件投資和后期維護(hù)所帶來(lái)的經(jīng)濟(jì)壓力。由于重復(fù)數(shù)據(jù)刪除技術(shù)可使一些因存儲(chǔ)容量需求巨大而成本高的數(shù)據(jù)管理和保護(hù)方案變得經(jīng)濟(jì)可行，因此，在工業(yè)領(lǐng)域，重復(fù)數(shù)據(jù)刪除技術(shù)在數(shù)據(jù)保護(hù)和歸檔留存領(lǐng)域得到了應(yīng)用。當(dāng)前，在學(xué)術(shù)研究領(lǐng)域，重復(fù)數(shù)據(jù)刪除技術(shù)也是研究的熱點(diǎn)之一。本課題的研究中，在基本的 iscsi 平臺(tái)中加入重復(fù)數(shù)據(jù)刪除技術(shù)，數(shù)據(jù)存儲(chǔ)之前先進(jìn)行去重處理。為了彌補(bǔ)重復(fù)數(shù)據(jù)刪除帶來(lái)的性能損失，利用過(guò)濾技術(shù)對(duì)數(shù)據(jù)檢索模塊進(jìn)行了

16、優(yōu)化，提高檢索性能。1.2課題研究目的及意義重復(fù)數(shù)據(jù)刪除技術(shù)通過(guò)有效地減少數(shù)據(jù)，消除備份成為減低數(shù)據(jù)存儲(chǔ)成本的重要技術(shù)，成為大家關(guān)注的焦點(diǎn)。在一個(gè)完整的備份工作中往往會(huì)存在大量的重復(fù)數(shù)據(jù)，如果所有的數(shù)據(jù)不加處理的進(jìn)行備份，那么這種備份開(kāi)銷是巨大的，更何況很多情況下數(shù)據(jù)會(huì)備份好幾份。在使用磁帶作為存儲(chǔ)介質(zhì)的系統(tǒng)中，這種完全備份還是可以接受的；但是在磁盤系統(tǒng)中，完全備份會(huì)消耗大量的磁盤空間，使成本增加。這種開(kāi)銷多數(shù)情況下是企業(yè)不愿意去承受的。將重復(fù)數(shù)據(jù)刪除技術(shù)應(yīng)用于備份系統(tǒng)中帶來(lái)的優(yōu)勢(shì)就很明顯了：（1）減少備份容量需求，節(jié)約成本。研究表明，這種容量縮減幅度一般保持在10-20 倍，在這個(gè)幅度中實(shí)現(xiàn)

17、的磁盤容量需求減縮將為用戶帶來(lái)強(qiáng)有力的成本節(jié)約，包括：更小的磁盤、更低的能耗和冷卻成本。（2） “釋放”容量意味著以更少的介質(zhì)管理，完成更多的備份數(shù)據(jù)，獲取更長(zhǎng)的數(shù)據(jù)保留時(shí)間。（3）重復(fù)數(shù)據(jù)刪除改善恢復(fù)時(shí)間目標(biāo)（rto）和可靠性。用戶備份到磁盤的數(shù)據(jù)越多，就越能滿足 rto 需求，重復(fù)數(shù)據(jù)刪除技術(shù)使客戶在磁盤上備份更多的數(shù)據(jù)，保留更長(zhǎng)的時(shí)間，從而提高 rto。通過(guò)重復(fù)數(shù)據(jù)刪除技術(shù)，所有到來(lái)的數(shù)據(jù)請(qǐng)求都要先進(jìn)行檢索，如果發(fā)現(xiàn)該數(shù)據(jù)已經(jīng)存在，則只進(jìn)行相關(guān)的映射處理，而不再重復(fù)存儲(chǔ)。這樣就可以保證沒(méi)有重復(fù)數(shù)據(jù)，從而降低存儲(chǔ)消耗，降低成本。1.3國(guó)內(nèi)外發(fā)展現(xiàn)狀當(dāng)前國(guó)際上的各大存儲(chǔ)廠商均開(kāi)始在自己的存儲(chǔ)

18、系統(tǒng)中開(kāi)始應(yīng)用重復(fù)數(shù)據(jù)刪除技術(shù)，比如 emc, netapp, datadomain 等。目前比較成熟的產(chǎn)品中，重復(fù)數(shù)據(jù)刪除技術(shù)一般是用于備份和歸檔系統(tǒng)；用于主存儲(chǔ)系統(tǒng)和分布式系統(tǒng)中的還相當(dāng)少。國(guó)內(nèi)的存儲(chǔ)廠商如華賽、h3c 等公司，也開(kāi)始了重復(fù)數(shù)據(jù)刪除方面的研究，并已申請(qǐng)了相關(guān)專利。目前，市場(chǎng)上提供重復(fù)數(shù)據(jù)刪除的廠商基本上可以分為兩個(gè)陣營(yíng)：in-line（帶內(nèi)）重復(fù)數(shù)據(jù)刪除和 post-process（帶外）重復(fù)數(shù)據(jù)刪除。in-line 重復(fù)數(shù)據(jù)刪除是指數(shù)據(jù)保存到存儲(chǔ)系統(tǒng)之前就進(jìn)行重復(fù)數(shù)據(jù)刪除，這樣做的優(yōu)勢(shì)在于備份過(guò)程只需進(jìn)行一次。post-process 重復(fù)數(shù)據(jù)刪除是指在數(shù)據(jù)備份處理之后才

19、進(jìn)行重復(fù)數(shù)據(jù)刪除，它的優(yōu)勢(shì)在于我們無(wú)需擔(dān)心由于重復(fù)數(shù)據(jù)處理使 cpu 負(fù)擔(dān)加重而導(dǎo)致備份服務(wù)器和存儲(chǔ)目標(biāo)之間出現(xiàn)瓶頸。重復(fù)數(shù)據(jù)刪除技術(shù)大致分為兩個(gè)方向，一方面是數(shù)據(jù)備份領(lǐng)域，另一方面是基礎(chǔ)存儲(chǔ)領(lǐng)域。從目前市場(chǎng)情況來(lái)看大部分應(yīng)用主要還是在備份領(lǐng)域，重復(fù)數(shù)據(jù)刪除技術(shù)通過(guò)識(shí)別和消除數(shù)據(jù)環(huán)境中的冗余數(shù)據(jù)，從而大大減少需要保護(hù)的數(shù)據(jù)量，確保同樣的數(shù)據(jù)信息只被保存一次，這樣不僅顯著提高現(xiàn)有磁盤存儲(chǔ)空間的有效容量，從而使保護(hù)數(shù)據(jù)所需的物理磁盤數(shù)量更少，還有助于企業(yè)對(duì)數(shù)據(jù)的維護(hù)管理。這便可以幫助企業(yè)減輕硬件投資和后期維護(hù)所帶來(lái)的經(jīng)濟(jì)壓力。隨著數(shù)字信息的爆炸式增長(zhǎng)，所存在的重復(fù)數(shù)據(jù)越來(lái)越多，造成了存儲(chǔ)資源的極大

20、浪費(fèi)。重復(fù)數(shù)據(jù)消除技術(shù)的出現(xiàn)在很大程度上緩解了該問(wèn)題，該技術(shù)也得到了越來(lái)越廣泛的認(rèn)可。目前重復(fù)數(shù)據(jù)刪除技術(shù)在工業(yè)上主要應(yīng)用于三個(gè)方面：數(shù)據(jù)備份系統(tǒng)、歸檔存儲(chǔ)系統(tǒng)和遠(yuǎn)程災(zāi)備系統(tǒng)。為了滿足用戶的需求，備份設(shè)備已漸漸從傳統(tǒng)的磁帶庫(kù)過(guò)渡到磁盤設(shè)備，但是考慮到成本不可能為磁盤設(shè)備無(wú)限擴(kuò)容，而隨著數(shù)據(jù)量的不斷增加，所有備份的數(shù)據(jù)越來(lái)越多，面臨容量膨脹的壓力，重復(fù)數(shù)據(jù)刪除技術(shù)的出現(xiàn)，為最小化存儲(chǔ)容量找到有效的方法。由于參考數(shù)據(jù)的數(shù)量不斷增長(zhǎng)，而法規(guī)遵從要求數(shù)據(jù)在線保留的時(shí)間更長(zhǎng)，并且由于高性能需求需要采用磁盤進(jìn)行歸檔，因此，企業(yè)一旦真正開(kāi)始進(jìn)行數(shù)據(jù)的歸檔存儲(chǔ)就面臨成本問(wèn)題，重復(fù)數(shù)據(jù)刪除技術(shù)通過(guò)消除冗余實(shí)現(xiàn)高

21、效率的歸檔存儲(chǔ)，從而實(shí)現(xiàn)最低的成本，目前，歸檔存儲(chǔ)系統(tǒng)的重復(fù)數(shù)據(jù)刪除技術(shù)主要是基于 hash 的方法，產(chǎn)品的銷售理念是以內(nèi)容尋址存儲(chǔ)(cas)技術(shù)為主，分為純軟件和存儲(chǔ)系統(tǒng)兩類。在遠(yuǎn)程災(zāi)備系統(tǒng)中，需要將大量的數(shù)據(jù)遷移到異地的系統(tǒng)中，隨著數(shù)據(jù)量的不斷增長(zhǎng)，數(shù)據(jù)傳輸?shù)膲毫υ絹?lái)越大，通過(guò)重復(fù)數(shù)據(jù)刪除技術(shù)在數(shù)據(jù)傳輸前檢測(cè)并刪除重復(fù)的數(shù)據(jù)，可以有效地減少傳輸?shù)臄?shù)據(jù)量，提高數(shù)據(jù)傳輸速度，例如飛康的microscan 軟件就采用了該技術(shù)。重復(fù)數(shù)據(jù)刪除技術(shù)正在不斷發(fā)展，因此，可以預(yù)計(jì)其應(yīng)用也會(huì)不斷拓展，用戶將在多種應(yīng)用環(huán)境中可獲得重復(fù)數(shù)據(jù)刪除帶來(lái)的成本效益，這些應(yīng)用環(huán)境不僅只是包括備份和歸檔，而且將覆蓋其它存

22、儲(chǔ)應(yīng)用、網(wǎng)絡(luò)應(yīng)用和桌面應(yīng)用中。1.4課題的主要研究工作本論文研究的主要內(nèi)容有以下幾個(gè)方面：（1）重復(fù)數(shù)據(jù)刪除技術(shù)的設(shè)計(jì)與實(shí)現(xiàn)。通過(guò)分析重復(fù)數(shù)據(jù)刪除的一般流程，實(shí)現(xiàn)了重復(fù)數(shù)據(jù)刪除模塊的基本功能，包括 lba 映射表的管理、指紋計(jì)算以及指紋索引表的建立與管理。（2）重復(fù)數(shù)據(jù)刪除中指紋檢索優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)。指紋檢索過(guò)程是重復(fù)數(shù)據(jù)刪除技術(shù)中的一大瓶頸，本系統(tǒng)通過(guò)基于 bloom filter 算法的檢索過(guò)濾技術(shù)的實(shí)現(xiàn)，極大的提高了指紋檢索的性能。本論文內(nèi)容組織如下：第一章對(duì)重復(fù)數(shù)據(jù)刪除技術(shù)的相關(guān)背景知識(shí)做了簡(jiǎn)單的介紹，對(duì)課題研究的目的、意義以及國(guó)內(nèi)外研究發(fā)展?fàn)顩r做了簡(jiǎn)要的描述。第二章詳細(xì)介紹了重復(fù)數(shù)據(jù)刪

23、除系統(tǒng)的總體設(shè)計(jì)。首先闡述了重復(fù)數(shù)據(jù)刪除技術(shù)的基本原理和系統(tǒng)的總體設(shè)計(jì)框架，然后對(duì)各個(gè)功能模塊分別進(jìn)行介紹，包括lba 映射表、指紋計(jì)算模塊和指紋檢索模塊。第三章描述了重復(fù)數(shù)據(jù)刪除系統(tǒng)的具體實(shí)現(xiàn)過(guò)程。首先分模塊詳述了各個(gè)模塊的實(shí)現(xiàn)方案，然后重點(diǎn)對(duì)檢索優(yōu)化算法部分的設(shè)計(jì)和實(shí)現(xiàn)進(jìn)行了說(shuō)明，最后分析了系統(tǒng)的處理流程。第四章對(duì)重復(fù)數(shù)據(jù)刪除系統(tǒng)各方面的性能進(jìn)行測(cè)試。第五章總結(jié)目前所做的工作并展望未來(lái)的研究工作。1.5課題的來(lái)源本課題受國(guó)家 973 重大基礎(chǔ)研究計(jì)劃 “高效能存儲(chǔ)系統(tǒng)組建方法研究” （項(xiàng)目編號(hào)：2011cb302300）資助。2系統(tǒng)關(guān)鍵技術(shù)概述目前國(guó)內(nèi)外已經(jīng)在很多平臺(tái)上實(shí)現(xiàn)了重復(fù)數(shù)據(jù)刪除技

24、術(shù)，在本文的研究中，是基于 iscsi 平臺(tái)實(shí)現(xiàn)的。本章首先介紹了 iscsi 存儲(chǔ)平臺(tái)的相關(guān)知識(shí)，然后介紹了重復(fù)數(shù)據(jù)刪除技術(shù)，最后就 bloom filter 算法的背景、算法基本原理和誤判率作了簡(jiǎn)要分析。2.1iscsi 平臺(tái)簡(jiǎn)介iscsi3(互聯(lián)網(wǎng)小型計(jì)算機(jī)系統(tǒng)接口)是一種在 internet 協(xié)議網(wǎng)絡(luò)上4，特別是以太網(wǎng)上進(jìn)行數(shù)據(jù)塊傳輸?shù)臉?biāo)準(zhǔn)。它是由 cisco 和 ibm 兩家發(fā)起的，并且得到了 ip 存儲(chǔ)技術(shù)擁護(hù)者的大力支持。是一個(gè)供硬件設(shè)備使用的可以在 ip 協(xié)議上層運(yùn)行的 scsi指令集。簡(jiǎn)單地說(shuō)，iscsi 可以實(shí)現(xiàn)在 ip 網(wǎng)絡(luò)上運(yùn)行 scsi 協(xié)議，使其能夠在諸如高速千兆以

25、太網(wǎng)上進(jìn)行路由選擇。iscsi 的主要功能是在 tcp/ip 網(wǎng)絡(luò)上的主機(jī)系統(tǒng)（啟動(dòng)器 initiator）和存儲(chǔ)設(shè)備（目標(biāo)器 target）之間進(jìn)行大量數(shù)據(jù)的封裝和可靠傳輸過(guò)程。其工作流程如圖 2. 1 所示：當(dāng)客戶端發(fā)出一個(gè)數(shù)據(jù)、文件或應(yīng)用程序的請(qǐng)求后，操作系統(tǒng)就會(huì)根據(jù)客戶端請(qǐng)求的內(nèi)容生成一個(gè) scsi 命令和數(shù)據(jù)請(qǐng)求，scsi 命令和數(shù)據(jù)請(qǐng)求通過(guò)封裝后會(huì)加上一個(gè)信息包標(biāo)題，并通過(guò)以太網(wǎng)傳輸?shù)浇邮斩?；?dāng)接收端接收到這個(gè)信息包后，會(huì)對(duì)信息包進(jìn)行解包，分離出的 scsi 命令與數(shù)據(jù)，而分離出來(lái)的 scsi 命令和數(shù)據(jù)將會(huì)傳輸給存儲(chǔ)設(shè)備，當(dāng)完成一次上述流程后，數(shù)據(jù)又會(huì)被返回到客戶端，以響應(yīng)客戶端

26、 iscsi 的請(qǐng)求。含iscsi控制單元的服務(wù)器iscsiip數(shù)據(jù)存儲(chǔ)設(shè)備或saniscsiip數(shù)據(jù)ip網(wǎng)絡(luò)圖 2. 1 iscsi 工作流程圖作為一種基于網(wǎng)絡(luò)的數(shù)據(jù)存儲(chǔ)技術(shù)，iscsi 具有很多優(yōu)點(diǎn)：（1）硬件成本低廉?；?iscsi 技術(shù)的適配卡、交換機(jī)和纜線這些產(chǎn)品的價(jià)格相對(duì)較低，而且 iscsi 可以在現(xiàn)有的網(wǎng)絡(luò)上直接安裝，并不需要更改企業(yè)的網(wǎng)絡(luò)體系，這樣可以最大程序的節(jié)約投入。（2）操作簡(jiǎn)單。此技術(shù)主要是通過(guò) ip 網(wǎng)絡(luò)實(shí)現(xiàn)存儲(chǔ)資源共享，只需要現(xiàn)有的網(wǎng)絡(luò)功能即可管理，其設(shè)置也非常簡(jiǎn)單。（3）擴(kuò)充性強(qiáng)。由于 iscsi 存儲(chǔ)系統(tǒng)可以直接在現(xiàn)有的網(wǎng)絡(luò)系統(tǒng)中進(jìn)行組建，并不需要改變網(wǎng)絡(luò)體

27、系，加上運(yùn)用交換機(jī)來(lái)連接存儲(chǔ)設(shè)備，對(duì)于需要增加存儲(chǔ)空間的企業(yè)用戶來(lái)說(shuō)，只需要增加存儲(chǔ)設(shè)備就可完全滿足，因此，iscsi 存儲(chǔ)系統(tǒng)的可擴(kuò)展性高。此外，iscsi 技術(shù)維護(hù)方便、傳輸速度快、突破距離限制等等，這些優(yōu)勢(shì)使得該技術(shù)在各方面的應(yīng)用越來(lái)越廣泛。本文的研究工作也是以 iscsi 為基礎(chǔ)平臺(tái)而展開(kāi)的。2.2重復(fù)數(shù)據(jù)簡(jiǎn)介相同的數(shù)據(jù)在存儲(chǔ)系統(tǒng)中反復(fù)存儲(chǔ)了多次，這樣的數(shù)據(jù)就可以簡(jiǎn)單的理解為是重復(fù)數(shù)據(jù)，也叫做冗余數(shù)據(jù)。重復(fù)數(shù)據(jù)在很多地方都存在，比如，備份系統(tǒng)由于其系統(tǒng)本身的特點(diǎn)就決定了總是存在大量的冗余數(shù)據(jù)。在不同用戶的個(gè)人電腦上也會(huì)有很多數(shù)據(jù)是相同的，像操作系統(tǒng)文件、office 文件等等。大部分網(wǎng)

28、絡(luò)上的重復(fù)數(shù)據(jù)量大到令人吃驚，如果不加于處理的話，隨著網(wǎng)絡(luò)上信息量的不斷增加，可能會(huì)造成磁盤空間嚴(yán)重不足，而且我們會(huì)發(fā)現(xiàn)磁盤中存儲(chǔ)的數(shù)據(jù)大多都是重復(fù)的，所以我們必須想個(gè)辦法解決重復(fù)數(shù)據(jù)的問(wèn)題。2.3重復(fù)數(shù)據(jù)刪除的基本原理重復(fù)數(shù)據(jù)刪除8，也被稱為智能數(shù)據(jù)壓縮或單一實(shí)例存儲(chǔ)。它是一種可以減小數(shù)據(jù)存儲(chǔ)需求的手段。重復(fù)數(shù)據(jù)刪除的處理過(guò)程是通過(guò)刪除冗余數(shù)據(jù)，確保實(shí)際上只有第一個(gè)單一實(shí)例數(shù)據(jù)被存儲(chǔ)。而被刪除的重復(fù)數(shù)據(jù)將由一個(gè)指向元數(shù)據(jù)的指針?biāo)?。這樣就可以大大節(jié)省存儲(chǔ)開(kāi)銷，降低成本。獲取待存儲(chǔ)的數(shù)據(jù)流（文件或者數(shù)據(jù)）利用某種算法計(jì)算出獲取到的數(shù)據(jù)的指紋比對(duì)計(jì)算出的數(shù)據(jù)指紋與指紋庫(kù)中的指紋根據(jù)比對(duì)結(jié)果進(jìn)行

29、重復(fù)數(shù)據(jù)刪除操作圖 2. 2 重復(fù)數(shù)據(jù)刪除基本流程如圖 2. 2 所示，重復(fù)數(shù)據(jù)刪除的一般分為以下四個(gè)流程：（1）獲取待存儲(chǔ)的數(shù)據(jù)流。重復(fù)數(shù)據(jù)刪除可以對(duì)文件、數(shù)據(jù)塊或者位進(jìn)行操作。所以這個(gè)數(shù)據(jù)流有可能是整個(gè)文件，也有可能是數(shù)據(jù)塊。分別對(duì)應(yīng)于文件級(jí)重復(fù)數(shù)據(jù)刪除和塊級(jí)重復(fù)數(shù)據(jù)刪除。（2）計(jì)算出獲取到的數(shù)據(jù)的指紋值。在重復(fù)數(shù)據(jù)刪除系統(tǒng)中，通常都會(huì)對(duì)數(shù)據(jù)進(jìn)行標(biāo)識(shí)，一般采用數(shù)據(jù)指紋來(lái)作為唯一的標(biāo)識(shí)。獲取指紋值的算法常采用md5、sha-1910等散列算法。（3）將計(jì)算出的數(shù)據(jù)指紋值與指紋庫(kù)中的值進(jìn)行比對(duì)。以指紋值去檢索指紋庫(kù)，查找該指紋值是否在已有的指紋庫(kù)中。（4）根據(jù)比對(duì)結(jié)果進(jìn)行重復(fù)數(shù)據(jù)刪除操作。如果

30、數(shù)據(jù)指紋值在指紋庫(kù)中，說(shuō)明該數(shù)據(jù)流已存在，只需要保存一個(gè)指向元數(shù)據(jù)的指針即可；如果沒(méi)有找到相同的指紋，說(shuō)明該數(shù)據(jù)流不存在，那么要將該指紋加入到指紋庫(kù)中，同時(shí)要存儲(chǔ)該數(shù)據(jù)流?；旧现貜?fù)數(shù)據(jù)刪除的流程就是這樣，但是在不同的系統(tǒng)中，具體的流程要比這個(gè)復(fù)雜一些。在本文的研究中，采用的是基于 iscsi 的重復(fù)數(shù)據(jù)刪除方式，整個(gè)系統(tǒng)在 iscsi 平臺(tái)上實(shí)現(xiàn)，獲取的數(shù)據(jù)流會(huì)被分為固定大小（4kb）的數(shù)據(jù)塊，然后利用 sha-1 散列算法計(jì)算出各個(gè)數(shù)據(jù)塊的指紋值，接著以指紋值為關(guān)鍵字進(jìn)行檢索，根據(jù)檢索結(jié)果進(jìn)行相應(yīng)的處理。2.4數(shù)據(jù)處理粒度分析按照數(shù)據(jù)處理粒度來(lái)劃分，重復(fù)數(shù)據(jù)刪除技術(shù)包括文件級(jí)重復(fù)數(shù)據(jù)刪除、

31、塊級(jí)重復(fù)數(shù)據(jù)刪除兩種11。盡管結(jié)果存在差異，但判斷文件或塊是否唯一都能帶來(lái)好處。兩者的差異在于減少的數(shù)據(jù)容量不同，判斷重復(fù)數(shù)據(jù)所需的時(shí)間不同。文件級(jí)重復(fù)數(shù)據(jù)刪除技術(shù)通常也稱為單實(shí)例存儲(chǔ)(sis)，根據(jù)索引檢查需要備份或歸檔的文件的屬性，并與已存儲(chǔ)的文件進(jìn)行比較。如果沒(méi)有相同文件，就將其存儲(chǔ)，并更新索引；否則，僅存入指針，指向已存在的文件。因此，同一文件只保存了一個(gè)實(shí)例，隨后的副本都以指針替代，而指針指向原始文件。塊級(jí)重復(fù)數(shù)據(jù)刪除技術(shù)將數(shù)據(jù)流分割成塊，檢查數(shù)據(jù)塊，并將這些部分與之前存儲(chǔ)的信息予以比較，檢查是否存在冗余。同樣，如果存在相同數(shù)據(jù)塊，就增加一個(gè)引用指針；否則，就將其存儲(chǔ)。文件級(jí)和塊級(jí)各

32、有各的優(yōu)缺點(diǎn)。文件級(jí)重復(fù)數(shù)據(jù)刪除的索引非常小，在判斷重復(fù)數(shù)據(jù)和檢索時(shí)所花費(fèi)的時(shí)間少。由于索引小、比較次數(shù)少，文件級(jí)刪除技術(shù)所需的處理負(fù)荷較低，對(duì)恢復(fù)時(shí)間的影響較少。但是當(dāng)文件內(nèi)部發(fā)生一點(diǎn)小變化，那么整個(gè)文件都必須重新存儲(chǔ)，而且以文件為基本單位進(jìn)行重復(fù)數(shù)據(jù)刪除時(shí)，重復(fù)率低，所以壓縮比相對(duì)較低。塊級(jí)重復(fù)數(shù)據(jù)刪除中數(shù)據(jù)要分塊處理，因而會(huì)花大量的精力去索引和管理各塊數(shù)據(jù)，檢測(cè)重復(fù)數(shù)據(jù)時(shí)的匹配工作也是比較大的。但通過(guò)將文件中的數(shù)據(jù)分塊處理，可以大大提高數(shù)據(jù)的重復(fù)率，數(shù)據(jù)壓縮比會(huì)是文件級(jí)的好幾倍，可以更好的實(shí)現(xiàn)重復(fù)數(shù)據(jù)刪除。不管數(shù)據(jù)流是文件級(jí)的還是塊級(jí)的，在標(biāo)準(zhǔn) iscsi 平臺(tái)中，最終都是被分成一頁(yè)一頁(yè)

33、的數(shù)據(jù)來(lái)進(jìn)行處理的，也就是說(shuō)，iscsi 平臺(tái)自動(dòng)完成了數(shù)據(jù)分塊的操作，所以為了不與平臺(tái)本身的結(jié)構(gòu)起沖突，基于 iscsi 的重復(fù)數(shù)據(jù)刪除系統(tǒng)我們也選擇按塊級(jí)來(lái)處理。不同的重復(fù)數(shù)據(jù)刪除系統(tǒng)檢查的數(shù)據(jù)塊大小各不相同，通常情況下分為兩種，變長(zhǎng)塊和定長(zhǎng)塊。由于變長(zhǎng)塊處理起來(lái)比較繁瑣，所以在本文研究中采用定長(zhǎng)塊的方式。固定塊的大小可能為 4kb、8kb 或者 64kb 等等，區(qū)別在于數(shù)據(jù)塊大小越小，被判定為冗余的幾率越大。這就意味著消除的冗余更多，存儲(chǔ)的數(shù)據(jù)更少。但顯而易見(jiàn)的，數(shù)據(jù)塊大小越小，文件被分得的數(shù)據(jù)塊數(shù)量就越龐大，這也意味著要花更多的空間去管理塊結(jié)構(gòu)，判斷重復(fù)的過(guò)程消耗更多的時(shí)間。在本論文研

34、究中選擇的塊大小是 4kb。將數(shù)據(jù)流分成一塊一塊的數(shù)據(jù)，每一塊的數(shù)據(jù)大小為 4kb，塊大小比較小，以期望可以獲得更高的去重率。在數(shù)據(jù)管理和重復(fù)數(shù)據(jù)比對(duì)的過(guò)程中，希望可以通過(guò)利用一些比較高效的方式來(lái)緩解這一部分的缺陷，同時(shí)也可以采取一些優(yōu)化措施來(lái)避免這一部分成為系統(tǒng)瓶頸。2.5bloom filter 算法2.5.1 算法背景bloom filter1213是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。bloom filter 的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（fa

35、lse positive） 。因此，bloom filter 不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，bloom filter 通過(guò)極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。2.5.2 算法基本原理bloom 過(guò)濾器14對(duì)集合采用一個(gè)位串表示，并支持元素的哈希查找。既能表示集合，支持集合元素查詢，又能有效地過(guò)濾掉不屬于集合的元素。其算法結(jié)構(gòu)的實(shí)質(zhì)是將集合中的元素通過(guò) k 個(gè)哈希函數(shù)映射到位串向量中。近年來(lái) bloom filter 算法在實(shí)際中的應(yīng)用越來(lái)越廣泛，關(guān)于這種算法的相關(guān)研究工作也備受關(guān)注。標(biāo)準(zhǔn)的bloom filter 算法的工作原理如下：如圖 2.1 所示，數(shù)據(jù)集

36、合 s=s1,s2,sn共有 n 個(gè)元素通過(guò) k 個(gè)哈希函數(shù) h1,h2,hk 映射到長(zhǎng)度為 m 的位串向量 v 中。通常, bloom 過(guò)濾器表示的匯總信息就是向量 v。每一個(gè)哈希函數(shù)相互獨(dú)立且函數(shù)的取值范圍為0,1,2,m1。初始狀態(tài)下，向量中的每個(gè)位都為 0，對(duì)任意一個(gè)元素，第 i個(gè)哈希函數(shù)映射的位置 h（i）就會(huì)被置為 1。注意，如果一個(gè)位置多次被置為 1，那么只有第一次會(huì)起作用，后面幾次將沒(méi)有任何效果。 集合外 a b c d 集合內(nèi) e f g hh1(x)h2(x)h3(x)hk(x)01100010000.10向量vk個(gè)哈希函數(shù)圖 2.1 bloom filter 算法原理圖b

37、loom filter 算法主要包含兩個(gè)操作：插入操作和查詢操作。元素插入操作就是將元素插入到集合，完成元素到 bloom 過(guò)濾器的向量表示；元素的查詢操作就是利用 bloom 判斷元素是否在集合中。bloom 過(guò)濾器在使用前必須初始化，即將 v 向量的各位初始化為 0。集合中元素的插入過(guò)程就是元素到向量的映射過(guò)程。元素插入操作如圖 2.2 所示：1）計(jì)算元素 x 的 k 個(gè)哈希地址，即 h1(x), h2(x),.,hk(x)。2）將 bloom 過(guò)濾器向量中對(duì)應(yīng)位置置 1，即 vh1(x) = vh2(x) = =vhk(x) = 1。x x000100010100010h h1 1( (

38、x x) )h h2 2( (x x) ) h h3 3( (x x) )h hk k( (x x) )圖 2.2 元素插入過(guò)程示意圖元素查詢操作如圖 2.3 所示，基本上是插入操作的反過(guò)程，也分為兩步：1）計(jì)算出元素 x 的 k 個(gè)哈希地址。2）檢查 bloom 過(guò)濾器向量中對(duì)應(yīng)位置上的值是否為 1。它們只要有一個(gè)是0，x 必不在集合中。如果全為 1，則 x 可能在集合中，但不一定。此時(shí)就出現(xiàn)了誤判，即將不屬于集合的元素誤判為屬于集合中。由于算法本身的缺陷，這種誤判是始終存在的。a a000100010100010h h1 1( (x x) )h h2 2( (x x) ) h h3 3(

39、(x x) )h hk k( (x x) )b bc cd d圖 2.3 元素查詢過(guò)程示意圖2.5.3 算法誤判率bloom 過(guò)濾器作為一種支持集合查詢的數(shù)據(jù)結(jié)構(gòu)，在達(dá)到其高效、簡(jiǎn)潔的表示集合效果的同時(shí)，卻存在某元素不屬于數(shù)據(jù)集合而被指稱屬于該數(shù)據(jù)集合的可能性。可以通過(guò)數(shù)據(jù)模型來(lái)估算誤判率的大小。假設(shè)哈希函數(shù)取值服從均勻分布，則當(dāng)集合中所有元素都映射完畢后，v 向量任意一位為 0 的概率:/1(1)knkn mpem (2.1)在發(fā)生誤判時(shí)，要求 k 個(gè)哈希函數(shù)計(jì)算得出的位都不為 0，則其概率為 (2.2)/(1)kn mkpe由公式 2.2 可以看出，誤判率的大小和 n/m 的值相關(guān)。對(duì)公式

40、 2.2 求偏導(dǎo)，可以得到誤判率最小時(shí) k，m，n 三者之間的關(guān)系，如公式 2.3： (2.3)ln2mkn一般情況下，可以固定集合總元素個(gè)數(shù) n 和誤判率 p 這兩個(gè)參數(shù)，然后就可以根據(jù)公式（2.2）和公式（2.3）來(lái)計(jì) k 值和 m 值。網(wǎng)上有提供的專門的計(jì)算器（bloom filter calculator） ，可以輸入 n 和 p，計(jì)算出 k 和 m。2.6 本章小結(jié)本章首先介紹了 iscsi 存儲(chǔ)平臺(tái)的相關(guān)知識(shí)，然后介紹了重復(fù)數(shù)據(jù)刪除技術(shù)，分別就重復(fù)數(shù)據(jù)刪除的基本原理以及重復(fù)數(shù)據(jù)刪除的處理粒度問(wèn)題作了說(shuō)明，最后介紹了 bloom filter 算法，包括該算法的背景、算法基本原理和誤

41、判率分析。3重復(fù)數(shù)據(jù)刪除方案設(shè)計(jì)上一章我們已經(jīng)分別討論了 iscsi 平臺(tái)工作流程、重復(fù)數(shù)據(jù)刪除技術(shù)的基本原理、數(shù)據(jù)處理粒度以及布魯姆算法，基于這些理論背景，我們將設(shè)計(jì)實(shí)現(xiàn)一個(gè)基于iscsi 平臺(tái)的重復(fù)數(shù)據(jù)刪除系統(tǒng)。該系統(tǒng)是在標(biāo)準(zhǔn) iscsi 協(xié)議的基礎(chǔ)上，加入重復(fù)數(shù)據(jù)刪除模塊來(lái)實(shí)現(xiàn)的。本章主要介紹了系統(tǒng)的總體設(shè)計(jì)，并簡(jiǎn)要說(shuō)明 lba 映射表、指紋計(jì)算、指紋管理和檢索等各模塊的功能，然后介紹了基于 bloom filter 算法的指紋檢索優(yōu)化設(shè)計(jì)。3.1 系統(tǒng)功能需求本研究要實(shí)現(xiàn)的是基于 iscsi 平臺(tái)的重復(fù)數(shù)據(jù)刪除系統(tǒng)，具有以下幾個(gè)方面的功能需求和性能要求：（1）搭建基于 iscsi 平臺(tái)

42、下的存儲(chǔ)系統(tǒng)。（2）重復(fù)數(shù)據(jù)刪除模塊功能的實(shí)現(xiàn)。要實(shí)現(xiàn)重復(fù)數(shù)據(jù)刪除的基本流程，完成數(shù)據(jù)指紋的計(jì)算、指紋表的建立與管理、指紋檢索等基本功能。（3）實(shí)現(xiàn)對(duì)指紋檢索模塊的優(yōu)化。當(dāng)存儲(chǔ)的數(shù)據(jù)量較大時(shí)，那么相應(yīng)的指紋庫(kù)也會(huì)很龐大，在進(jìn)行指紋檢索時(shí)就需要消耗較長(zhǎng)的時(shí)間，會(huì)成為整個(gè)系統(tǒng)的性能瓶頸所在。為了提高檢索性能，我們可以在檢索之前先采用基于 bloom filter 算法的索引檢索過(guò)濾技術(shù)對(duì)指紋進(jìn)行過(guò)濾，這樣可以極大的提高檢索性能。3.2 系統(tǒng)總體設(shè)計(jì)整個(gè)系統(tǒng)采用 iscsi 啟動(dòng)器作為客戶端，iscsi 目標(biāo)器作為服務(wù)器端，重復(fù)數(shù)據(jù)刪除模塊就嵌在 iscsi 目標(biāo)器代碼中。如圖 3.1 所示，重復(fù)數(shù)

43、據(jù)刪除模塊主要包括lba 映射表、指紋計(jì)算、指紋檢索幾個(gè)功能模塊和檢索性能優(yōu)化部分?？蛻舳?iscsi initiator)客戶端(iscsi initiator)客戶端(iscsi initiator)交換機(jī)(switch)iscsilba映射表指紋計(jì)算模塊指紋索引表的建立與指紋檢索模塊重復(fù)數(shù)據(jù)刪除模塊存儲(chǔ)設(shè)備(disk)指紋檢索過(guò)濾性能優(yōu)化圖 3.1 重復(fù)數(shù)據(jù)刪除系統(tǒng)總體設(shè)計(jì)圖系統(tǒng)總體基本功能實(shí)現(xiàn)包括以下幾個(gè)子模塊：（1）lba 映射表。用來(lái)記錄重復(fù)數(shù)據(jù)刪除前請(qǐng)求的 lba 與重復(fù)數(shù)據(jù)刪除之后的 lba 的映射關(guān)系，由于重復(fù)數(shù)據(jù)的存在，去重前幾個(gè)不同的 lba 去重后有可能對(duì)應(yīng)同一個(gè) lb

44、a。（2）指紋計(jì)算模塊。利用基于散列的 sha-1 算法計(jì)算出數(shù)據(jù)塊的指紋值，4kb的數(shù)據(jù)頁(yè)對(duì)應(yīng)唯一的一個(gè) 160bit 的指紋值。（3）指紋索引表的建立與指紋檢索模塊。本系統(tǒng)中指紋索引表的建立采用多級(jí)索引的方式，指紋的檢索也是采用多級(jí)檢索的方式。在進(jìn)行指紋檢索之前，先利用基于 bloom filter 算法的過(guò)濾技術(shù)對(duì)指紋值進(jìn)行過(guò)濾處理，過(guò)濾掉部分指紋檢索請(qǐng)求從而提高檢索性能。將過(guò)濾掉的那部分指紋加入到摘要向量中，對(duì)剩下的指紋值再進(jìn)行指紋檢索。3.3lba 映射表在磁盤設(shè)備中，每個(gè)存儲(chǔ)單元都會(huì)有一個(gè)標(biāo)識(shí)位置的邏輯地址即 lba，當(dāng)數(shù)據(jù)被存儲(chǔ)到磁盤設(shè)備后，都會(huì)記錄下該數(shù)據(jù)被存儲(chǔ)在哪個(gè)地址單元中

45、以便后來(lái)對(duì)數(shù)據(jù)進(jìn)行讀寫操作。在標(biāo)準(zhǔn)的 iscsi 平臺(tái)中，用戶對(duì)數(shù)據(jù)進(jìn)行 i/o 操作時(shí)，都是對(duì)真實(shí)磁盤空間進(jìn)行操作，所以只需要記錄下數(shù)據(jù)存儲(chǔ)的位置即可。但加入重復(fù)數(shù)據(jù)刪除模塊之后，重復(fù)數(shù)據(jù)只會(huì)在磁盤中存儲(chǔ)一遍，用戶對(duì)重復(fù)數(shù)據(jù)的操作會(huì)被定位到同一個(gè)邏輯地址單元。也就是說(shuō)用戶請(qǐng)求處理的 lba 不再是真實(shí)磁盤的 lba，這中間會(huì)進(jìn)行映射處理，將用戶請(qǐng)求的 lba 轉(zhuǎn)化為對(duì)應(yīng)磁盤的 lba。lba 映射表結(jié)構(gòu)是重復(fù)數(shù)據(jù)刪除系統(tǒng)涉及到的核心數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)需要將上層模塊中的請(qǐng)求地址 lba_u 映射到下層提供的某個(gè) lba_l 之上，對(duì)于包含有相同數(shù)據(jù)的不同 lba_u 需映射到同一個(gè) lba_l

46、上。3.4 指紋計(jì)算模塊新到來(lái)的數(shù)據(jù)流被劃分為一個(gè)個(gè)的 4kb 的數(shù)據(jù)塊，要判斷這些數(shù)據(jù)塊是否是重復(fù)數(shù)據(jù)，如果不加任何處理，那么最直接的方法就是一個(gè)字節(jié)一個(gè)字節(jié)的去和其他已經(jīng)存儲(chǔ)的數(shù)據(jù)塊去比對(duì)。大家可以想象一下，這樣處理效率是極低的，低到重復(fù)數(shù)據(jù)刪除模塊失去了存在的意義。為了提高效率簡(jiǎn)化操作，我們必須想辦法來(lái)簡(jiǎn)化數(shù)據(jù)塊。類比人的識(shí)別，通常情況下，人與人的指紋是不一樣的，因此我們可以用指紋來(lái)識(shí)別和標(biāo)記某個(gè)人。數(shù)據(jù)塊也一樣，我們可以通過(guò)某種方式，將數(shù)據(jù)塊轉(zhuǎn)變成數(shù)據(jù)指紋，用該指紋來(lái)唯一標(biāo)記這個(gè)數(shù)據(jù)塊。數(shù)據(jù)指紋通常是一個(gè)哈希值，對(duì)哈希值的比對(duì)就要比數(shù)據(jù)塊的比對(duì)要簡(jiǎn)單快捷得多。一般采用哈希散列算法來(lái)計(jì)算

47、數(shù)據(jù)指紋，比如 sha-1 算法、md5 算法等等。在本論文的設(shè)計(jì)中，哈希算法是作為一個(gè)獨(dú)立的模塊存在的，這樣就便于替換不同的算法。在本系統(tǒng)中，采用的是 sha-1 算法來(lái)計(jì)算數(shù)據(jù)指紋。sha(secure hash algorithm)全稱為安全散列算法，由一系列密碼散列函數(shù)組成。sha-1 為較早的一種散列算法，可以從最大 264 位的原數(shù)據(jù)中產(chǎn)生 160bit 的摘要值，來(lái)對(duì)原數(shù)據(jù)進(jìn)行唯一性標(biāo)識(shí)。也就是說(shuō)，在本系統(tǒng)中，4kb 的數(shù)據(jù)塊經(jīng)由指紋計(jì)算模塊后產(chǎn)生出160bit 的指紋值，用此值來(lái)作為原數(shù)據(jù)塊的標(biāo)識(shí)。sha-1 算法在標(biāo)準(zhǔn) rfc 文檔中有詳細(xì)的說(shuō)明，并且提供了標(biāo)準(zhǔn)的實(shí)現(xiàn)代碼，系

48、統(tǒng)中直接使用了此代碼，具體的算法原理在此不再詳述。3.5 指紋管理和檢索模塊3.5.1 指紋索引表的組織與建立指紋索引表是整個(gè)重復(fù)數(shù)據(jù)刪除模塊的核心元數(shù)據(jù)管理部分，經(jīng)過(guò)重復(fù)數(shù)據(jù)刪除后的每個(gè)數(shù)據(jù)塊都是單一實(shí)例數(shù)據(jù)塊，每一個(gè)單一實(shí)例數(shù)據(jù)塊都對(duì)應(yīng)一個(gè)指紋索引節(jié)點(diǎn)。合理的組織和管理這些索引節(jié)點(diǎn)，是重復(fù)數(shù)據(jù)刪除模塊設(shè)計(jì)的關(guān)鍵問(wèn)題，也決定了指紋檢索的方式和效率。4kb 大小的數(shù)據(jù)塊通過(guò) sha-1 散列算法得到的指紋值為 160bit，直接通過(guò)這160bit 值來(lái)進(jìn)行全哈希顯然是不可行的。為此，在本系統(tǒng)中，采用了多級(jí)索引表組織方式，即取 160bit 指紋值中的前 24bit 值共 3 個(gè)字節(jié)作為多級(jí)索引

49、關(guān)鍵字。將三個(gè)字節(jié)分別設(shè)為 key1、key2 、key3，則每個(gè) key 的取值都在 0255，通過(guò)這三個(gè) key 值可以建立三級(jí)索引表，key1、key2 、key3 分別作為三級(jí)索引的關(guān)鍵字，每級(jí)索引最多有 256 個(gè)關(guān)鍵字，最后一級(jí)索引后掛接的便是指紋索引節(jié)點(diǎn)。指紋索引表結(jié)構(gòu)如圖 3.2 所示。三級(jí)索引表的每個(gè)索引節(jié)點(diǎn)只用一個(gè)指針記錄即可，即每個(gè)節(jié)點(diǎn)需要占用4 個(gè)字節(jié)的空間，整個(gè)三級(jí)索引表一共有 1 + 256 + 2562 + 2563 個(gè)節(jié)點(diǎn)，通過(guò)計(jì)算可以得到共占用約 64mb 內(nèi)存，這種程度是可以接受的。 root0索引節(jié)點(diǎn)123254255索引節(jié)點(diǎn)0125425501255索引

50、節(jié)點(diǎn)key1key2key3指紋索引節(jié)點(diǎn)三級(jí)索引部分圖 3.2 三級(jí)索引表結(jié)構(gòu)圖3.5.2 指紋檢索流程分析指紋檢索就是確定待檢索的指紋值是否存在于指紋索引表中。根據(jù)指紋索引表的組織方式，可以確定指紋檢索也采用三級(jí)檢索的方式，其基本流程如下：取指紋值的部分作為key1、key2、key3根據(jù)key1進(jìn)行一級(jí)索引得到二級(jí)索引頭指針根據(jù)key2進(jìn)行二級(jí)索引得到三級(jí)索引頭指針根據(jù)key3進(jìn)行三級(jí)索引得到指紋索引鏈表根節(jié)點(diǎn)遍歷指紋索引鏈表，確定是否能找到相應(yīng)索引節(jié)點(diǎn)圖 3.3 指紋檢索流程由指紋檢索流程可以看出，假設(shè) n 為三級(jí)索引后某一個(gè)指紋索引鏈表的平均長(zhǎng)度，指紋檢索的算法復(fù)雜度為 o（3 +n）

51、 。由于 sha-1 算法的高散列性，可以預(yù)見(jiàn)到經(jīng)過(guò)三級(jí)索引后，所有的指紋索引節(jié)點(diǎn)將較為均勻的分配到整個(gè)鏈表上，即 n 的離散性較低，這樣就可以保證每一次的指紋檢索其算法復(fù)雜度相當(dāng)。3.6 基于 bloom filter 算法的指紋檢索優(yōu)化3.6.1 重復(fù)數(shù)據(jù)刪除檢索性能瓶頸重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用必然會(huì)對(duì)存儲(chǔ)系統(tǒng)的性能造成一定的影響。主要的性能損耗出現(xiàn)在指紋檢索模塊中，隨著數(shù)據(jù)量的不斷增加，指紋索引表會(huì)變得越來(lái)越龐大，大量的元數(shù)據(jù)會(huì)使指紋數(shù)據(jù)檢索成為系統(tǒng)的瓶頸?；?sha-1 算法的數(shù)據(jù)指紋計(jì)算模塊會(huì)為每一頁(yè) 4kb 的數(shù)據(jù)塊產(chǎn)生 160bit 的指紋值。當(dāng)指紋索引節(jié)點(diǎn)不斷增加，對(duì)指紋的索引

52、和對(duì)指紋值的比對(duì)都將消耗更長(zhǎng)的時(shí)間。為了避免指紋索引成為瓶頸，本系統(tǒng)中采用了三級(jí)索引結(jié)構(gòu)來(lái)管理和檢索數(shù)據(jù)指紋，這樣可以有效地減小指紋檢索算法的時(shí)間復(fù)雜度。除了優(yōu)化索引表的結(jié)構(gòu)之外，我們還可以在檢索之前先判斷該數(shù)據(jù)指紋需不需要進(jìn)行檢索，如果我們事先能判定出該數(shù)據(jù)指紋值一定在或者一定不在指紋索引表中，那么我們就可以省去指紋檢索的過(guò)程，從而可以提高檢索效率。在本系統(tǒng)中，我們采用的是基于 bloom filter算法的檢索過(guò)濾技術(shù)，可以過(guò)濾掉大量不需要進(jìn)行的數(shù)據(jù)指紋檢索請(qǐng)求。3.6.2 基于 bloom filter 算法的檢索過(guò)濾基本原理檢索過(guò)濾算法是針對(duì)重復(fù)數(shù)據(jù)刪除模塊中的指紋檢索性能瓶頸而進(jìn)行的

53、優(yōu)化設(shè)計(jì)，基于 bloom filter 算法。其基本工作原理如下：指紋索引表中的所有數(shù)據(jù)指紋值構(gòu)成了一個(gè)集合，每個(gè)數(shù)據(jù)指紋值通過(guò) k 個(gè)哈希函數(shù)計(jì)算轉(zhuǎn)換成一個(gè)定長(zhǎng)的位串，然后插入到向量 v 中。當(dāng)一個(gè)新的待檢索的數(shù)據(jù)指紋到來(lái)時(shí)，同樣計(jì)算出一個(gè)位串，并與向量 v 中的相應(yīng)位置的位對(duì)比，如果所有位串中出現(xiàn)一位不相同，則說(shuō)明該數(shù)據(jù)指紋一定不在指紋庫(kù)中，不需要再去進(jìn)行指紋檢索操作。這樣就可以過(guò)濾掉很多不需要進(jìn)行檢索的數(shù)據(jù)指紋。如圖 3.4 所示。如果所有位串都相同，我們也無(wú)法肯定的判定該指紋一定在指紋索引表中，這就是 bloom filter 算法中存在的誤判問(wèn)題。h1(x)h2(x)h3(x)hk

54、(x)01100010000.10向量vk個(gè)哈希函數(shù)160bit指紋值指紋索引庫(kù)圖 3.4 檢索過(guò)濾基本原理圖3.6.3 算法關(guān)鍵參數(shù)確定及哈希函數(shù)的選取在 bloom filter 算法中一共有四個(gè)參數(shù)需要確定，即元素集合個(gè)數(shù)、集合向量長(zhǎng)度、哈希函數(shù)個(gè)數(shù)和誤判率。經(jīng)過(guò)分析，通過(guò) bloom filter 計(jì)算器最終可以算出我們需要設(shè)定的兩個(gè)參數(shù)值。哈希函數(shù)的選取關(guān)鍵在于其不相關(guān)性，各個(gè)哈希函數(shù)要獨(dú)立存在，這樣才能保證過(guò)濾的準(zhǔn)確性。我們可以采用異或移位型哈希函數(shù)，異或移位型哈希函數(shù)是一個(gè)較普遍的哈希函數(shù)，經(jīng)大量驗(yàn)證證明，具有良好的獨(dú)立性。3.7 本章小結(jié)本章詳細(xì)敘述了重復(fù)數(shù)據(jù)刪除模塊的設(shè)計(jì)方案

55、。首先對(duì)系統(tǒng)功能需求進(jìn)行了分析，然后介紹了系統(tǒng)總體設(shè)計(jì)，接著對(duì) lba 映射表、指紋計(jì)算、指紋管理和檢索等功能模塊進(jìn)行了簡(jiǎn)單的說(shuō)明，最后介紹了基于 bloom filter 算法的指紋檢索優(yōu)化設(shè)計(jì)，分別敘述了該檢索過(guò)濾算法的基本原理、算法參數(shù)的確定和哈希函數(shù)的選取。4重復(fù)數(shù)據(jù)刪除系統(tǒng)實(shí)現(xiàn)在系統(tǒng)總體設(shè)計(jì)的基礎(chǔ)上，本章主要詳述了基于 iscsi 的重復(fù)數(shù)據(jù)刪除系統(tǒng)的實(shí)現(xiàn)，包括 lba 映射表的實(shí)現(xiàn)、指紋計(jì)算和指紋檢索模塊的實(shí)現(xiàn)以及 bloom filter過(guò)濾算法的實(shí)現(xiàn)，最后分析了整個(gè)系統(tǒng)的讀寫流程。4.1 lba 映射表實(shí)現(xiàn)lba 映射表實(shí)現(xiàn)的功能就是將重復(fù)數(shù)據(jù)刪除之前的請(qǐng)求地址 lba_u 轉(zhuǎn)

56、換成重復(fù)數(shù)據(jù)刪除之后的 lba_l，多個(gè)去重前的 lba_u 有可能被轉(zhuǎn)換為同一個(gè) lba_l。其映射關(guān)系如圖 4.1 所示，lba 映射表主要有兩個(gè)內(nèi)容：一是去重前的請(qǐng)求地址，二是指紋索引節(jié)點(diǎn)指針，它指向相應(yīng)數(shù)據(jù)塊的指紋索引節(jié)點(diǎn)，通過(guò)該節(jié)點(diǎn)可以獲取數(shù)據(jù)塊真實(shí)的存儲(chǔ)地址，即 lba_l。l lb ba a_ _u u指紋索引節(jié)點(diǎn)指針l lb ba a_ _u u指紋索引節(jié)點(diǎn)指針l lb ba a_ _u u指紋索引節(jié)點(diǎn)指針lba映射節(jié)點(diǎn)l lb ba a_ _l l其他信息l lb ba a_ _l l其他信息指紋索引節(jié)點(diǎn)圖 4.1 lba 映射關(guān)系圖lba 映射表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：type

57、def struct _l_map_item u64 lba_u; /去重前的請(qǐng)求地址 hmap_item *hash_item; /指向?qū)?yīng)的指紋索引節(jié)點(diǎn)l_map_item;重復(fù)數(shù)據(jù)刪除之前用戶下發(fā)的請(qǐng)求地址用 lba_u 表示，hash_item 表示的是一個(gè)指向?qū)?yīng)數(shù)據(jù)塊指紋索引節(jié)點(diǎn)的指針，通過(guò)該指針可以讀取數(shù)據(jù)塊真實(shí)的存儲(chǔ)地址lba_l。lba 映射表是一個(gè)全局映射結(jié)構(gòu)，針對(duì)全局的數(shù)據(jù)進(jìn)行記錄。每到來(lái)一個(gè)新的用戶請(qǐng)求，先查找 lba 映射表，看該請(qǐng)求是否記錄過(guò)，如果沒(méi)有命中，那么就新建一個(gè) lba 映射節(jié)點(diǎn)插入到映射表中；如果命中，就直接在該節(jié)點(diǎn)上更新記錄。lba 映射表中的所有映射

58、節(jié)點(diǎn)利用 linux 內(nèi)核提供的 radix_tree 來(lái)組織，并對(duì)外提供查詢、插入、刪除等接口。4.2 指紋計(jì)算模塊實(shí)現(xiàn)本系統(tǒng)中使用 sha-1 作為指紋計(jì)算算法，經(jīng)過(guò)該算法將 4kb 的數(shù)據(jù)頁(yè)轉(zhuǎn)化為160bit 的指紋值。系統(tǒng)中直接使用了 sha-1 算法的標(biāo)準(zhǔn) c 源代碼，具體實(shí)現(xiàn)過(guò)程在此不再詳述。4.3 指紋索引表的建立與指紋檢索為了實(shí)現(xiàn)對(duì)指紋索引表的管理，系統(tǒng)實(shí)現(xiàn)中定義了一個(gè)三級(jí)索引表節(jié)點(diǎn)的結(jié)構(gòu)體：typedef struct hindex_node u32 count; /本索引結(jié)點(diǎn)下屬索引結(jié)點(diǎn)個(gè)數(shù) union struct hindex_node *nextindex_sanou

59、t; /多級(jí)索引子數(shù)組 hmap_sub *subindex_sanout; /指紋索引指數(shù)組 ;hmap_index;在此結(jié)構(gòu)體中，count 用來(lái)統(tǒng)計(jì)本索引結(jié)點(diǎn)下屬索引結(jié)點(diǎn)的個(gè)數(shù)。通過(guò) union 定義了一個(gè)聯(lián)合結(jié)構(gòu)，聯(lián)合結(jié)構(gòu)中的成員都是指針數(shù)據(jù)，如果該節(jié)點(diǎn)為三級(jí)索引結(jié)構(gòu)中的第一級(jí)或第二級(jí)索引節(jié)點(diǎn)，那么選擇 struct hindex_node *nextindex_sanout數(shù)組，此時(shí)下面掛接的仍然是多級(jí)索引節(jié)點(diǎn)；如果該節(jié)點(diǎn)為第三極索引節(jié)點(diǎn)，那么選擇 hmap_sub *subindex_sanout數(shù)組，此時(shí)下面掛接的是指紋索引節(jié)點(diǎn)。其中 index_sanout 為常量，值為 25

60、6。在指紋檢索過(guò)程中，為了記錄數(shù)據(jù)頁(yè)的真實(shí) lba，還定義了一個(gè)指紋索引節(jié)點(diǎn)結(jié)構(gòu)體：typedef struct _hmap_item unsigned char hashhash_size; /保存160bit的指紋值 u64 lba_l; /去重后的真實(shí)地址 int ref_cnt; /重復(fù)度hmap_item;結(jié)構(gòu)體中 hashhash_size用來(lái)保存數(shù)據(jù)塊的指紋值，lba_l 是重復(fù)數(shù)據(jù)刪除之后數(shù)據(jù)塊的真實(shí)存儲(chǔ)地址，ref_cnt 表示的是該數(shù)據(jù)頁(yè)的重復(fù)度，即有多少個(gè) lba_u映射到這個(gè) lba_l 上。lba 映射表結(jié)構(gòu)體中的 hash_item 指針指向的節(jié)點(diǎn)就是此結(jié)構(gòu)體聲明的