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

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

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

3、果的好壞與應(yīng)用環(huán)境密切相關(guān)，當(dāng)應(yīng)用于那些信息重復(fù)度較高的環(huán)境如備份存儲系統(tǒng)、歸檔存儲系統(tǒng)等時，具有較好的壓縮效果；最后對檢索過濾算法進行了測試，測試出的過濾率和誤判率都可以達到預(yù)期效果。關(guān)鍵詞關(guān)鍵詞：重復(fù)數(shù)據(jù)刪除，指紋檢索優(yōu)化，存儲性能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國內(nèi)外發(fā)展現(xiàn)狀.21.4課題的主要研究工作.41.5課題的來源.52系統(tǒng)關(guān)鍵技術(shù)概述系統(tǒng)關(guān)鍵技術(shù)概述 .62.1iscsi 平臺簡介.62

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、loom filter 算法主要包含兩個操作：插入操作和查詢操作。元素插入操作就是將元素插入到集合，完成元素到 bloom 過濾器的向量表示；元素的查詢操作就是利用 bloom 判斷元素是否在集合中。bloom 過濾器在使用前必須初始化，即將 v 向量的各位初始化為 0。集合中元素的插入過程就是元素到向量的映射過程。元素插入操作如圖 2.2 所示：1）計算元素 x 的 k 個哈希地址，即 h1(x), h2(x),.,hk(x)。2）將 bloom 過濾器向量中對應(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 元素插入過程示意圖元素查詢操作如圖 2.3 所示，基本上是插入操作的反過程，也分為兩步：1）計算出元素 x 的 k 個哈希地址。2）檢查 bloom 過濾器向量中對應(yīng)位置上的值是否為 1。它們只要有一個是0，x 必不在集合中。如果全為 1，則 x 可能在集合中，但不一定。此時就出現(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 元素查詢過程示意圖2.5.3 算法誤判率bloom 過濾器作為一種支持集合查詢的數(shù)據(jù)結(jié)構(gòu)，在達到其高效、簡潔的表示集合效果的同時，卻存在某元素不屬于數(shù)據(jù)集合而被指稱屬于該數(shù)據(jù)集合的可能性?？梢酝ㄟ^數(shù)據(jù)模型來估算誤判率的大小。假設(shè)哈希函數(shù)取值服從均勻分布，則當(dāng)集合中所有元素都映射完畢后，v 向量任意一位為 0 的概率:/1(1)knkn mpem (2.1)在發(fā)生誤判時，要求 k 個哈希函數(shù)計算得出的位都不為 0，則其概率為 (2.2)/(1)kn mkpe由公式 2.2 可以看出，誤判率的大小和 n/m 的值相關(guān)。對公式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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