對(duì)業(yè)務(wù)系統(tǒng)連續(xù)性要求較高的企業(yè)或機(jī)構(gòu)，其數(shù)據(jù)安全極為重要^[1]。傳統(tǒng)的RAID、遠(yuǎn)程鏡像、周期性備份和快照等技術(shù)都會(huì)引起數(shù)據(jù)丟失的問(wèn)題^[2-4]。因此對(duì)數(shù)據(jù)可靠性和安全級(jí)別要求較高的業(yè)務(wù)部門急需存儲(chǔ)系統(tǒng)能提供連續(xù)數(shù)據(jù)保護(hù)(CDP)功能^[5]。

        國(guó)內(nèi)外在CDP系統(tǒng)研究方面已經(jīng)開(kāi)展了大量研究^[6]。但這些工作主要集中在存儲(chǔ)架構(gòu)設(shè)計(jì)、存儲(chǔ)空間優(yōu)化和一致點(diǎn)恢復(fù)等方面，對(duì)快速恢復(fù)研究不多。針對(duì)海量的塊級(jí)變化數(shù)據(jù)，設(shè)計(jì)高效快速的索引方法是個(gè)研究難點(diǎn)。本文主要針對(duì)卷級(jí)系統(tǒng)歷史數(shù)據(jù)索引和查詢的優(yōu)化，提出一種面向連續(xù)數(shù)據(jù)的分時(shí)分段的層次式快速索引方法HSTIM(Hierarchical Spatial-Temporal Indexing Method)。 

1 HSTIM設(shè)計(jì) 

        在磁盤(pán)邏輯卷層次，數(shù)據(jù)由連續(xù)的數(shù)據(jù)塊組成。每個(gè)數(shù)據(jù)塊有固定的大小，并通過(guò)邏輯塊地址LBA來(lái)標(biāo)識(shí)。連續(xù)數(shù)據(jù)保護(hù)實(shí)現(xiàn)的關(guān)鍵技術(shù)是對(duì)數(shù)據(jù)變化的記錄和保存，以便實(shí)現(xiàn)任意時(shí)間點(diǎn)的快速恢復(fù)。CDP一般有3種實(shí)現(xiàn)方式：基準(zhǔn)參考數(shù)據(jù)模式、復(fù)制參考數(shù)據(jù)模式和合成參考數(shù)據(jù)模式^[7-8]。其中，合成參考數(shù)據(jù)模式是前兩種模式性能的折衷，較好地實(shí)現(xiàn)了前兩種模式的妥協(xié)，因此可以得到較好的資源占用和恢復(fù)時(shí)間效果，但需要復(fù)雜的軟件管理和數(shù)據(jù)處理功能，實(shí)現(xiàn)比較復(fù)雜。

1.1 分時(shí)分段索引數(shù)據(jù)組織 

        HSTIM中索引數(shù)據(jù)按分時(shí)和分段策略組織，數(shù)據(jù)組織如圖1所示。圖1例中在t₃~t₄時(shí)間段內(nèi)共產(chǎn)生N+1個(gè)索引文件(元數(shù)據(jù)單獨(dú)索引)。段區(qū)間的長(zhǎng)度采用不等成劃分方法，長(zhǎng)度按磁盤(pán)寫(xiě)IO密度來(lái)確定。索引文件記錄了R_t(a) ，即t時(shí)刻邏輯地址為a的增量數(shù)據(jù)在增量存儲(chǔ)空間的位置。為加速索引的讀取速度，可采用多個(gè)物理硬盤(pán)存放索引文件。

1.2 索引快照 

        索引快照提取了一個(gè)時(shí)間段的索引階段結(jié)果。在圖2的例子中，t₁和t₂兩個(gè)時(shí)刻插入了索引快照。所有索引快照結(jié)果存放至一個(gè)獨(dú)立的索引文件，如圖2的右側(cè)的索引快照獨(dú)立索引文件?？煺摘?dú)立索引文件采用OVBT索引方式。如果用戶需要查詢圖1中t時(shí)刻的索引結(jié)果，則可通過(guò)先查詢索引快照獲得t₁和t₂時(shí)刻的索引，然后查詢t₂~t時(shí)刻的索引，最后將索引結(jié)果進(jìn)行合并即可。HSTIM通過(guò)索引快照避免了索引數(shù)據(jù)的全查詢，加快了特定時(shí)刻索引的快速查詢，尤其適用于歷史數(shù)據(jù)保護(hù)時(shí)間窗口較長(zhǎng)的應(yīng)用場(chǎng)景。由于索引快照文件較小，在實(shí)現(xiàn)上沒(méi)有采用分段策略，即將LBA地址從0~MAX索引快照存放至一個(gè)索引文件中。

1.3 增量式快速查找 

        HSTIM通過(guò)改進(jìn)OVBT索引節(jié)點(diǎn)結(jié)構(gòu)實(shí)現(xiàn)了增量查找支持。原先的OVBT內(nèi)部節(jié)點(diǎn)包括了引用數(shù)目和分裂值列表。HSTIM中的內(nèi)部節(jié)點(diǎn)通過(guò)新增時(shí)間戳列表實(shí)現(xiàn)了增量查找。HSTIM和OVBT的內(nèi)部結(jié)構(gòu)比較如圖3所示。

        卷級(jí)CDP一次IO更新產(chǎn)生一條索引記錄項(xiàng)，索引記錄項(xiàng)可用{LBA,timestamp,R}表示，其中LBA表示IO的LBA地址，timestamp表示時(shí)間戳，R代表數(shù)據(jù)在存儲(chǔ)池中的位置。OVBT索引需要對(duì)每一個(gè)索引項(xiàng)進(jìn)行記錄，針對(duì)每一個(gè)IO的時(shí)間戳生成一個(gè)獨(dú)立的B+樹(shù)索引。OVBT有兩種類型的節(jié)點(diǎn)：葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)。兩種節(jié)點(diǎn)由通用的索引項(xiàng){ref, entries}組成，其中ref表示節(jié)點(diǎn)被引用的次數(shù)，entries 由{entry, entry,…, entry}列表組成。每個(gè)entry由{key, timestamp, info}3個(gè)元素構(gòu)成。對(duì)葉子節(jié)點(diǎn)，key表示IO的LBA地址，timestamp表示時(shí)間戳，info表示數(shù)據(jù)在存儲(chǔ)池中的位置，即索引記錄項(xiàng)中的R。對(duì)非葉子節(jié)點(diǎn)，key代表B+的分裂鍵值，timestamp代表所指向下一層節(jié)點(diǎn)的插入時(shí)間，info是指向下一層節(jié)點(diǎn)的指針。 

        為記錄每一更新IO產(chǎn)生的B+樹(shù)的根節(jié)點(diǎn)，OVBT維護(hù)一張根節(jié)點(diǎn)記錄表(root table)。根節(jié)點(diǎn)記錄表由{root, root,…, root}列表組成，每個(gè)root項(xiàng)由{timestamp, ptr}組成，其中timestamp代表獨(dú)立B+樹(shù)的產(chǎn)生時(shí)間，ptr指向B+樹(shù)的根節(jié)點(diǎn)。 

2 性能評(píng)測(cè)

2.1 測(cè)試方法和實(shí)驗(yàn)平臺(tái) 

        通過(guò)對(duì)實(shí)際應(yīng)用中的IO trace文件進(jìn)行回放的方式對(duì)HSTIM性能進(jìn)行了評(píng)測(cè)。測(cè)試選擇的IO trace是Msr-cambridge Trace。該Trace文件采集了企業(yè)數(shù)據(jù)中心13臺(tái)服務(wù)器上共36個(gè)磁盤(pán)卷連續(xù)14天的塊級(jí)數(shù)據(jù)。實(shí)驗(yàn)選取文件集合中數(shù)據(jù)量最大的文件CAMRESISAA02_ lvm1.csv(以下簡(jiǎn)稱AA02_Trace)作為樣本。所有的IO請(qǐng)求塊都按最小磁盤(pán)扇區(qū)大小(512 B)進(jìn)行了等長(zhǎng)切割和對(duì)齊存儲(chǔ)。實(shí)驗(yàn)平臺(tái)主要硬件包括Pentium(R) Dual-core E5200 2.50 GHz處理器、4 GB DDR2內(nèi)存和500 GB Seagate ST3500620A硬盤(pán), 操作系統(tǒng)是Windows 7。 

2.2 HSTIM與B+-tree和OVBT性能綜合比較 

        實(shí)驗(yàn)對(duì)AA02_Trace文件進(jìn)行了24 h的數(shù)據(jù)回放，經(jīng)統(tǒng)計(jì)在24 h內(nèi)，系統(tǒng)共產(chǎn)生8 660 679個(gè)IOR (寫(xiě)IO請(qǐng)求)。如果對(duì)每個(gè)IOR按512 B等長(zhǎng)切割,則共產(chǎn)生224 356 508個(gè)對(duì)齊的塊級(jí)IO(Aligned Block IO,以下簡(jiǎn)稱ABI)，表1給出了AA02_Trace文件24 h內(nèi)的寫(xiě)IO統(tǒng)計(jì)結(jié)果。為描述方便，本實(shí)驗(yàn)中對(duì)HSTIM采用了等長(zhǎng)分時(shí),時(shí)長(zhǎng)分別為0.5 h和2 h,分別稱HSTIM-0.5和HSTIM-2。實(shí)驗(yàn)從索引文件大小、插入性能和查詢性能三方面對(duì)HSTIM、B+-tree和OVBT進(jìn)行了綜合比較，給出了周期為2 h的性能統(tǒng)計(jì)結(jié)果。

        (1)查詢性能比較 

        表2給出了OVBT與B+-tree的查詢性能比較。實(shí)驗(yàn)表明，B+-tree的查詢速度在RPO小于5 h可以接受，基本在1 min內(nèi)得出查詢結(jié)果。但在RPO大于5 h的情況下,查詢性能急劇下降,在RPO=6 h查詢時(shí)間為838 s，RPO=12 h查詢時(shí)間長(zhǎng)達(dá)2.27 h。對(duì)OVBT而言，由于每一個(gè)時(shí)間點(diǎn)索引數(shù)據(jù)由一顆獨(dú)立B+樹(shù)組成，查詢時(shí)間相對(duì)穩(wěn)定。RPO小于12 h內(nèi)任意點(diǎn)查詢時(shí)間小于44 s。本實(shí)驗(yàn)同時(shí)說(shuō)明,傳統(tǒng)的分別對(duì)LBA和Timestamp建立B+-tree的索引方式不適合大數(shù)量的任意點(diǎn)恢復(fù)索引的需要。

        HSTIM由于采用分時(shí)策略并將分時(shí)索引快照獨(dú)立組織，因此查詢時(shí)間包括索引快照查詢時(shí)間和時(shí)間段內(nèi)索引查詢時(shí)間。圖4給出了HSTIM-2、HSTIM-0.5和OVBT的查詢性能比較。實(shí)驗(yàn)結(jié)果表明，HSTIM在查詢性能上較OVBT有較大提高。在RPO=24 h，HSTIM-0.5的查詢時(shí)間僅為OVBT的11.6%。HSTIM-0.5與HSTIM-2相比，由于分時(shí)頻率高，因此查詢索引快照時(shí)間略長(zhǎng)于HSTIM-2，但時(shí)段內(nèi)的索引查詢速度明顯少于HSTIM-2。但從整體上看，HSTIM-0.5和HSTIM-2的查詢速度并無(wú)大的差別。

        (2)索引空間消耗比較 

        圖5給出了OVBT與B+-tree索引空間比較結(jié)果。測(cè)試表明，OVBT索引存儲(chǔ)空間平均是B+-tree的5.2~5.5倍。由于OVBT內(nèi)部有大量重復(fù)數(shù)據(jù)，采用壓縮工具對(duì)索引文件進(jìn)行壓縮，壓縮后的OVBT索引文件大小平均僅為原索引文件的3%。但壓縮帶來(lái)的問(wèn)題是，恢復(fù)時(shí)需要引入額外的解壓縮時(shí)間開(kāi)銷。為減少存儲(chǔ)空間，在實(shí)際應(yīng)用中可以將離當(dāng)前時(shí)間點(diǎn)較遠(yuǎn)的索引文件壓縮存儲(chǔ)。

        本文針對(duì)卷級(jí)CDP任意點(diǎn)恢復(fù)提供了一種快速的索引方法-HSTIM，并對(duì)該方法的性能進(jìn)行了評(píng)估。實(shí)驗(yàn)結(jié)果表明，在一定的備份窗口內(nèi)，HSTIM能為卷級(jí)CDP任意點(diǎn)的恢復(fù)提供快速索引支持。高效的索引可快速定位到變化數(shù)據(jù)在增量空間中的存放位置，解決恢復(fù)中數(shù)據(jù)“在哪里”的問(wèn)題。

參考文獻(xiàn)

[1] 梁知音，段鐳，韋韜，等. 云存儲(chǔ)安全技術(shù)綜述[J].電子技術(shù)應(yīng)用, 2013,39(4):130-132.

[2] SMITH D M. The cost of lost data[J]. Journal of Contemporary Business Practice, 2003,6(3):113-119.

[3] PATTERSON D, BROWN A, BROADWELL P, et al. Recovery oriented computing(ROC): motivation, definition, techniques, and case studies[R]. Computer Science Technical Report UCB/CSD-0201175, San Francisco: U.C. Berkeley, 2002:997-1013.

[4] SANKARAN A, GUINN K, NGUYEN D.  Volume shadow copy service[J]. Power, 2004,14(2):2272-2284.

[5] SNIA. Continuous data protection-solving the problem of Recovery[EB/OL].(2008-08-08)[2014-02-22].http://www.snia.org/forums/dmf/knowledge/white_papers_and_reports/CDP_Solving_recovery_20080808.pdf.

[6] SNIA.DMF-Getting_started_with_ILM-20050415[EB/OL].(2005-04-15)[2014-02-22].http://www.snia.org/forums/dmf/programs/ilmi/DMF-Getting_started_with_ILM-20050415.pdf. 

[7] PIERNAS J, CORTES T,CARC′IA J, DualFS: a new journaling file system without meta-data duplication[C]. In Proceedings of the 16th International Conference on Supercomputing. New York: ACM press, 2002:146-159. 

[8] KAVALANEKAR S, WORTHINGTON B, ZHANG Q, et al.Characterization of storage workload traces from production Windows servers[C]. In IEEE International Symposium on Workload Characterization, IEEE press, 2008:671-686.