張 猛，錢育蓉，蒲勇霖，范迎迎，杜 嬌

(新疆大學(xué) 軟件學(xué)院，新疆 烏魯木齊 830008)

0 引 言

隨著信息技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)呈爆炸式增長(zhǎng)，社交網(wǎng)絡(luò)、信息檢索和電子商務(wù)等在線數(shù)據(jù)密集型(on line data intensive,OLDI)應(yīng)用[1]成為研究的熱點(diǎn)話題，這些應(yīng)用對(duì)于數(shù)據(jù)的訪問(wèn)性能(帶寬、延遲等)提出了更高的要求[2]。雖然在現(xiàn)有的云計(jì)算平臺(tái)下，虛擬化技術(shù)的普及以及CPU與內(nèi)存性能有很大的提升，但是網(wǎng)絡(luò)帶寬和磁盤I/O仍然是制約OLDI應(yīng)用發(fā)展的瓶頸[3]。一方面，大、小數(shù)據(jù)塊在數(shù)據(jù)密集型應(yīng)用中大量存儲(chǔ)[4]。例如大量的MB級(jí)別乃至GB級(jí)別的視頻和音頻對(duì)象存儲(chǔ)在在線視頻或者音樂(lè)應(yīng)用當(dāng)中，而且用戶對(duì)其點(diǎn)擊閱覽要求也非常高，這就要求在線數(shù)據(jù)密集型應(yīng)用要有很高的性能。另一方面，隨著計(jì)算機(jī)技術(shù)的不斷成熟以及內(nèi)存成本的不斷降低，內(nèi)存云[5](RAMCloud)的設(shè)計(jì)理念應(yīng)運(yùn)而生，并且性能很好地滿足了當(dāng)前此類應(yīng)用的要求。內(nèi)存云是由大量的普通服務(wù)器內(nèi)存組成的一種新型數(shù)據(jù)中心存儲(chǔ)系統(tǒng)，使用鍵值的存儲(chǔ)方式將所有的應(yīng)用數(shù)據(jù)都時(shí)刻存儲(chǔ)在內(nèi)存中[6]。一般的傳統(tǒng)硬盤只是將被動(dòng)隨機(jī)訪問(wèn)存儲(chǔ)器(dynamic random access memory,DRAM)取代而作為內(nèi)存云的備份介質(zhì)。相比傳統(tǒng)的硬盤，內(nèi)存云的吞吐量和訪問(wèn)延遲要比傳統(tǒng)磁盤存儲(chǔ)系統(tǒng)好100～1 000倍。

當(dāng)前內(nèi)存云設(shè)計(jì)只考慮了大、小數(shù)據(jù)塊對(duì)象在內(nèi)存中如何管理以提供高效的讀寫性能的問(wèn)題，以及在現(xiàn)有的研究中只關(guān)心大、小塊數(shù)據(jù)對(duì)象的存儲(chǔ)優(yōu)化問(wèn)題[7]和硬件節(jié)能策略[8]卻忽略了數(shù)據(jù)存儲(chǔ)在內(nèi)存中的精確度問(wèn)題，基于此，研究?jī)?nèi)存云的數(shù)據(jù)存儲(chǔ)的精確度將會(huì)成為必然。因此，基于內(nèi)存云中數(shù)據(jù)存儲(chǔ)精確度低的問(wèn)題，文中提出一種數(shù)據(jù)存儲(chǔ)優(yōu)化策略。

1 內(nèi)存云系統(tǒng)架構(gòu)

內(nèi)存云是由成千上萬(wàn)的服務(wù)器(它是由動(dòng)態(tài)隨機(jī)訪問(wèn)存儲(chǔ)器構(gòu)成的內(nèi)存集群，里面存儲(chǔ)著所有的應(yīng)用數(shù)據(jù))組成并且在數(shù)據(jù)中心運(yùn)行的集群存儲(chǔ)系統(tǒng)[9]。在內(nèi)存云中，每一臺(tái)服務(wù)器不僅被作為響應(yīng)客戶端請(qǐng)求的主服務(wù)器(Master)，而且又作為備份其他主服務(wù)器內(nèi)存信息的備份服務(wù)器(Backup)。每一個(gè)內(nèi)存云集群都擁有一個(gè)類似于Hadoop分布式文件系統(tǒng)(Hadoop distributed file system，HDFS)[10]中的NameNode節(jié)點(diǎn)的Coordinator節(jié)點(diǎn)，用來(lái)存儲(chǔ)文件的Mapping映射信息，通過(guò)運(yùn)用鍵值對(duì)來(lái)保存用戶所請(qǐng)求的信息在哪一臺(tái)主服務(wù)器上，而集群的管理配置信息是由Coordinator執(zhí)行的并且存儲(chǔ)服務(wù)器的網(wǎng)絡(luò)地址和對(duì)象的位置等不參與客戶請(qǐng)求。RAMCloud的客戶端包含存儲(chǔ)表和存儲(chǔ)服務(wù)器的映射關(guān)系的緩存，并且在第一時(shí)間獲取映射表?？蛻舳丝梢圆唤?jīng)過(guò)Coordinator直接向相關(guān)的服務(wù)器發(fā)送存儲(chǔ)請(qǐng)求[11-12]。它的整體結(jié)構(gòu)如圖1所示。

圖1 內(nèi)存云基本結(jié)構(gòu)模型

存儲(chǔ)在內(nèi)存中的數(shù)據(jù)會(huì)因?yàn)殡娔X宕機(jī)掉電而丟失，為了避免以上這種情況的發(fā)生，保證數(shù)據(jù)的可靠性，需要在每一臺(tái)的主機(jī)服務(wù)器中隨時(shí)備份數(shù)據(jù)到各個(gè)磁盤中，這里的存儲(chǔ)方式是基于日志結(jié)構(gòu)的[13]。首先，將內(nèi)存中的部分?jǐn)?shù)據(jù)以日志的形式保存起來(lái)，其次切分成段(Segment)，然后，將切分好的數(shù)據(jù)存儲(chǔ)到不同的服務(wù)器的內(nèi)存緩沖區(qū)(Buffer)中，最后用哈希表進(jìn)行記錄。主服務(wù)器繼續(xù)執(zhí)行其他命令，此時(shí)備份服務(wù)器的報(bào)告才算完成，接著備份服務(wù)器周而復(fù)始地接受其他備份操作請(qǐng)求，當(dāng)內(nèi)存緩沖區(qū)滿后采用批處理方式異步順序傳輸?shù)奖镜卮疟P，當(dāng)某臺(tái)主機(jī)宕機(jī)時(shí)，各個(gè)備份服務(wù)器就會(huì)根據(jù)其存儲(chǔ)的日志來(lái)進(jìn)行數(shù)據(jù)恢復(fù)，這樣大大提升了恢復(fù)系統(tǒng)崩潰的速度，而且也提高了文件的寫入速率。

內(nèi)存云的存儲(chǔ)模型是以鍵值對(duì)來(lái)表現(xiàn)的，在RAMCloud集群系統(tǒng)中，這種模型是由數(shù)據(jù)塊對(duì)象(key)組成，并且被組織到可以在RAMCloud集群中跨越多個(gè)主服務(wù)器的表中，每一個(gè)主服務(wù)器的內(nèi)存中都包含一個(gè)由眾多表和鍵組成的哈希表和一個(gè)對(duì)象集合[14]，如圖2所示。這樣的內(nèi)存管理機(jī)制能夠快速地定位任何一個(gè)對(duì)象，并且每一個(gè)對(duì)象都被一個(gè)知識(shí)偏移量[15]所標(biāo)識(shí)。

圖2 主服務(wù)器備份服務(wù)器的內(nèi)部結(jié)構(gòu)

2 相關(guān)模型與定義

本節(jié)首先對(duì)數(shù)據(jù)的儲(chǔ)存機(jī)制進(jìn)行建模，并在此基礎(chǔ)上建立了節(jié)點(diǎn)矩陣、文件分塊矩陣，兩個(gè)層次的可用性模型。

眾多的服務(wù)器組成了一個(gè)RAMCloud集群[16]，它們主要分為三類：協(xié)調(diào)器(Coordinator)、主服務(wù)器(Master)、備份服務(wù)器(Backup)。一般一個(gè)Coordinator和storage server組成一個(gè)典型的RAMCloud集群，然而一個(gè)RAMCloud內(nèi)部是由一個(gè)Coordinator以及Master、Backup組成。

Cluster={,…,

}

(1)

定義1(集群節(jié)點(diǎn)矩陣)：設(shè)Coordinator集合組成了一個(gè)RAMCloud集群，其中元素表示編號(hào)Coordinator1的RAMCloud集群中有s1臺(tái)Coordinator服務(wù)器。設(shè)該集群由i個(gè)Coordinator組成，所以可得出|Cluster|=i，并且用dn表示Coordinator服務(wù)器，那么可以用Csm×i來(lái)表示RAMCloud集群中所有的Coordinator：

(2)

其中，Csm×i中的第i列表示編號(hào)為Coordinatori的RAMCloud集群K中的si個(gè)Coordinator服務(wù)器，其中節(jié)點(diǎn)數(shù)量集合{s1,s2,…,si}中的最大值用sm表示。設(shè)k=∑si表示Coordinator節(jié)點(diǎn)數(shù)量，矩陣Csm×i可以表示sm×i個(gè)元素，當(dāng)sm×i>∑si時(shí)，用sm×i-∑si個(gè)0來(lái)填充矩陣Csm×i，在RAMCloud集群中該位置沒(méi)有放置Coordinator服務(wù)器。

定義2：文件分塊矩陣。

存儲(chǔ)在RAMCloud集群中的文件都會(huì)被拆分，并且以數(shù)據(jù)塊的形式存儲(chǔ)在table中，并且table可以跨越多個(gè)server，在同一個(gè)集群中提高數(shù)據(jù)的可靠性。如果由k(k>3)個(gè)Coordinator{dn∈Csm×i}組成的RAMCloud集群中，設(shè)F為RAMCloud集群中存儲(chǔ)的某一文件，數(shù)據(jù)庫(kù)的大小為bs，則文件F的大小為n×bs，那么F就會(huì)有n×m個(gè)數(shù)據(jù)塊存儲(chǔ)在k個(gè)Coordinator中，則矩陣Fn×m表示文件的分塊，使用{b11,b21,…,bn1}來(lái)表示原文件F的數(shù)據(jù)塊，文件的原始數(shù)據(jù)塊用n表示，并且該文件的副本用矩陣Fn×(m-1)表示。

(3)

(4)

當(dāng)RAMCloud集群得到用戶傳輸?shù)臄?shù)據(jù)時(shí)，數(shù)據(jù)塊b11就會(huì)存儲(chǔ)在table節(jié)點(diǎn)中，數(shù)據(jù)塊b12作為b11的副本存放在與b11不同的Backup中，同樣b12作為b11的副本2，也存放在與b12相同的機(jī)架但是卻不同的Backup中。假設(shè)m為副本系數(shù)且m>3，則其他數(shù)據(jù)塊就會(huì)存儲(chǔ)在b11、b12、b13以外的Backup中且該Backup是任意的。并且在數(shù)據(jù)的存儲(chǔ)過(guò)程中，重復(fù)存儲(chǔ)的數(shù)據(jù)會(huì)影響到內(nèi)存的緩存，還會(huì)影響到數(shù)據(jù)存儲(chǔ)的精度，所以在RAMCloud中設(shè)置MD5索引，查找內(nèi)存中重復(fù)的數(shù)據(jù)，其中重復(fù)的數(shù)據(jù)文件要經(jīng)過(guò)布隆過(guò)濾器過(guò)濾，在這里該策略不做詳細(xì)論述。

算法：存儲(chǔ)優(yōu)化策略。

輸入：數(shù)據(jù)文件{F1,F2,…,Ft},表示用戶上傳t個(gè)數(shù)據(jù)文件到系統(tǒng)。

輸出：Disk，表示數(shù)據(jù)文件存儲(chǔ)到磁盤。

1.{F1,F2,…,Ft}←getUpDatafile();

/*獲得用戶上傳數(shù)據(jù)文件*/

2.t←Datafiles.length();

/*數(shù)據(jù)文件的個(gè)數(shù)*/

3.RAMCLOUDfile←file[t];

/*數(shù)據(jù)文件存儲(chǔ)到內(nèi)存云*/

4.fori=0 tot-1 do

5.DatafileInfo={F1,F2,…,Fm}.get(file[j]);

/*獲得數(shù)據(jù)文件i的信息*/

6.ni=Datafile.getBlockDivNum();

/*取得數(shù)據(jù)原始分塊數(shù)*/

7.mi=Datafile.getBlockDuplicateNum();

/*副本系數(shù)*/

8.(Fn×m)i← createBlock×F(ni,mi)；

/*構(gòu)造數(shù)據(jù)文件矩陣模型*/

9.MD5Stri← {t(file),get(i),MD5(64)}；

/*MD5的值，刪除內(nèi)存中的重復(fù)文件*/

10.fors=0 tonido

11.foru=0 tomido

12.Blocksuget MatrixValue((Fn×m)i)；

/*獲得數(shù)據(jù)文件中的一條數(shù)據(jù)流*/

13.DiskDatafile←Blocksu；

/*將數(shù)據(jù)塊存儲(chǔ)到磁盤文件區(qū)中*/

14.end for

15.end for

16.end for

通過(guò)64位MD5索引刪除內(nèi)存云中的重復(fù)數(shù)據(jù)，節(jié)省了大量的內(nèi)存空間，該方法既有效提高了內(nèi)存云系統(tǒng)的讀/寫準(zhǔn)確性，又節(jié)省了內(nèi)存活動(dòng)狀態(tài)的空間，完全符合優(yōu)化內(nèi)存云數(shù)據(jù)存儲(chǔ)的思想。

(5)

(6)

基于負(fù)載均衡，數(shù)據(jù)分類將系統(tǒng)中所有數(shù)據(jù)存儲(chǔ)到內(nèi)存中。設(shè)數(shù)據(jù)文件冗余率為r%，由于對(duì)重復(fù)覆蓋的數(shù)據(jù)進(jìn)行布隆過(guò)濾器過(guò)濾，過(guò)濾后的數(shù)據(jù)塊大小為a，那么過(guò)濾的數(shù)據(jù)占有的內(nèi)存空間為：

(7)

設(shè)原系統(tǒng)內(nèi)存存儲(chǔ)的數(shù)據(jù)文件占有的內(nèi)存空間為SUMOm，經(jīng)過(guò)重復(fù)覆蓋原系統(tǒng)內(nèi)存中存儲(chǔ)的數(shù)據(jù)文件并且經(jīng)過(guò)濾重復(fù)的文件后，現(xiàn)在存儲(chǔ)的數(shù)據(jù)文件占有的內(nèi)存空間SUMMem為：

SUMMem=SUMMem+SUMOm-SUMown=SUMMem+

a×r%]/u

(8)

數(shù)據(jù)文件副本系數(shù)m的值越大，數(shù)據(jù)的可用性越高，且數(shù)據(jù)精準(zhǔn)度越高。精確度原數(shù)據(jù)模型可根據(jù)用戶對(duì)不同的數(shù)據(jù)文件可用性要求對(duì)m進(jìn)行動(dòng)態(tài)調(diào)節(jié)。在滿足用戶可用性QoS的前提下最大限度地節(jié)約對(duì)存儲(chǔ)資源的消耗。根據(jù)文獻(xiàn)[13]定理2，m的最小值的函數(shù)目標(biāo)為：

(9)

其中，bais表示內(nèi)存中數(shù)據(jù)可用概率；QoSava表示該數(shù)據(jù)的可用性QoS。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采取的是模擬RAMCloud集群的方式，集群中共有20個(gè)節(jié)點(diǎn)，其中包括1個(gè)協(xié)調(diào)器節(jié)點(diǎn)，19個(gè)存儲(chǔ)服務(wù)器節(jié)點(diǎn)。這20個(gè)節(jié)點(diǎn)中的每一個(gè)服務(wù)器節(jié)點(diǎn)和硬盤不僅是集群中的主服務(wù)器而且是備份服務(wù)器，在這20個(gè)節(jié)點(diǎn)中的每一個(gè)服務(wù)器均配置了8 GB內(nèi)存和100 GB的硬盤。硬盤的緩沖區(qū)為64 MB，磁盤副本參數(shù)為3，主服務(wù)器的段大小參數(shù)默認(rèn)為8 MB，20個(gè)服務(wù)器節(jié)點(diǎn)模擬聯(lián)想集群服務(wù)器(Syatem X3950 X6241JCC)，其配置為48個(gè)CPU，可擴(kuò)展112個(gè)節(jié)點(diǎn)。

3.2 實(shí)驗(yàn)結(jié)果分析

內(nèi)存云運(yùn)行期間數(shù)據(jù)需要不斷地從各個(gè)服務(wù)器傳送至協(xié)調(diào)器，通常數(shù)據(jù)存儲(chǔ)的精確度與數(shù)據(jù)量的大小以及數(shù)據(jù)傳輸中各節(jié)點(diǎn)的性能有關(guān)，準(zhǔn)確率通過(guò)式10計(jì)算：

(10)

(1)有效存儲(chǔ)準(zhǔn)確率對(duì)比。

圖3展示了在不同數(shù)據(jù)大小下，引入DSOS后的準(zhǔn)確率對(duì)比，未引入DSOS時(shí)隨著存儲(chǔ)數(shù)據(jù)的增大數(shù)據(jù)存儲(chǔ)的準(zhǔn)確率逐漸減小。

(2)有效存儲(chǔ)效率對(duì)比。

從圖4可以明顯看出，采用存儲(chǔ)優(yōu)化算法在不同數(shù)據(jù)下呈現(xiàn)出類似于線性的理想存儲(chǔ)效率，并且隨著存儲(chǔ)數(shù)據(jù)的增加，存取效率對(duì)比原系統(tǒng)也在不斷提高。實(shí)驗(yàn)結(jié)果表明，采用存儲(chǔ)優(yōu)化算法的數(shù)據(jù)越大，其存儲(chǔ)效率也越高。該實(shí)驗(yàn)體現(xiàn)出了基于內(nèi)存云的大數(shù)據(jù)存儲(chǔ)優(yōu)化算法具有較好的性能和效果。

圖3 相同存儲(chǔ)數(shù)據(jù)下有效存儲(chǔ)準(zhǔn)確率的對(duì)比

圖4 相同存儲(chǔ)數(shù)據(jù)下有效存儲(chǔ)效率的對(duì)比

4 結(jié)束語(yǔ)

內(nèi)存云框架的出現(xiàn)為線數(shù)據(jù)密集(OLDI)的應(yīng)用帶來(lái)了新的機(jī)遇與挑戰(zhàn)，但是在大數(shù)據(jù)的背景下，海量的數(shù)據(jù)想要準(zhǔn)確無(wú)誤地存儲(chǔ)到內(nèi)存中已經(jīng)成為制約其發(fā)展的一個(gè)重要問(wèn)題。針對(duì)該問(wèn)題，提出了基于內(nèi)存云提升數(shù)據(jù)存儲(chǔ)精確度的策略。該策略根據(jù)RAMCloud的體系結(jié)構(gòu)，將原系統(tǒng)中已存在的數(shù)據(jù)重復(fù)覆蓋，經(jīng)過(guò)布隆過(guò)濾器過(guò)濾掉重復(fù)的數(shù)據(jù)，從而提升了數(shù)據(jù)存儲(chǔ)到RAMCloud的準(zhǔn)確率。

下一步研究工作將著重在以下幾方面：在保持RAMCloud中數(shù)據(jù)存儲(chǔ)精確度不變的條件下降低RAMCloud的能耗；在保持內(nèi)存云較高的性能前提下，降低內(nèi)存云的能耗；擴(kuò)展內(nèi)存云的應(yīng)用范圍以及更加合理地設(shè)計(jì)存儲(chǔ)框架。

參考文獻(xiàn)：

[1] DEAN J,CHEMAWAT S.MapReduce:simplified data processing on large clusters[J].Communication of the ACM,2008,51(1):107-113.

[2] 于 炯，廖 彬，張 陶，等.云存儲(chǔ)系統(tǒng)節(jié)能研究綜述[J].計(jì)算機(jī)科學(xué)與探索，2014,8(9):1025-1040.

[3] ARMBRUST M, FOX A,GRIFFITH R,et al. A view of cloud computing[J].Communications of ACM,2010,53(4):50-58.

[4] 褚 征，于 炯，魯 亮，等. 基于內(nèi)存云的大塊數(shù)據(jù)對(duì)象

并行存取策略[J].計(jì)算機(jī)應(yīng)用，2016,36(6):1526-1532.

[5] RUMBLE S, KEJRIWAL A, OUSTERHIUT J.Log-struchured memory for DRAM-based storage[C]//Proceeding of the 12th USENIX conference on file and storage technologies.Berkeley:USENIX Association,2014:1-6.

[6] 宋寶燕，王俊陸，王 研.基于范德蒙碼HDFS優(yōu)化存儲(chǔ)策略研究[J].計(jì)算機(jī)學(xué)報(bào)，2015,38(9):1825-1837.

[7] 英昌甜，于 炯，魯 亮，等.基于小文件的內(nèi)存云存儲(chǔ)優(yōu)化策略[J].計(jì)算機(jī)應(yīng)用，2014,34(11):3104-3108.

[8] 魯 亮，于 炯，英昌甜，等.內(nèi)存云架構(gòu)的磁盤節(jié)能策略[J].計(jì)算機(jī)應(yīng)用，2016,34(9):2518-2522.

[9] OUSTERHOUT J,AGRAWL P,ERICKSON D,et al.The case for RAMCLouds:scalable high-performance storage entirely in DRAM[J].ACM SIGOPS Operating Systems Review,2010,43(4):92-105.

[10] 董新華，李瑞軒，周彎彎，等.Hadoop系統(tǒng)性能優(yōu)化與功能增強(qiáng)綜述[J].計(jì)算機(jī)研究與發(fā)展，2013,50：1-15.

[11] ZHENG Zhiyun,ZHAO Shaofeng,ZHANG Xingjin,et al.Cloud storage management technology for small file based on two-dimensional packing algorithm[C]//Proceedings of the 2013 international conference on computer engineering and networking.Berlin:Spriang-Verlag,2013.

[12] STUTSMAN R.Durability and crash recovery in distributed in-memory storage system[D].Stanford:Stanford University,2013.

[13] ROSENBLUM M,OUSTERHOUT J K.The design and implementation of a log-structured file system[J].ACM SIGOPS Operating System Review,1991,25(5):1-15.

[14] 錢育蓉，于 炯，王衛(wèi)源，等.云計(jì)算環(huán)境下軟硬件節(jié)能和負(fù)載均衡策略[J].計(jì)算機(jī)應(yīng)用，2013,33(12):3326-3330.

[15] RUMBLE S M,KEJRIWA L A,OUSTERHOUT J.Log-stractured memory for DPAM-based storage[C]//Proceedings of the 12th USENIX conference on file and storage technologies.Berkeley:USENIX Association,2014:1-6.

[16] 郭 剛，于 炯，魯 亮，等.內(nèi)存云分級(jí)存儲(chǔ)架構(gòu)下的數(shù)據(jù)遷移模型[J].計(jì)算機(jī)應(yīng)用，2015,35(12):3392-3397.