采用弧映射的雙層對象分布算法

聶世強(qiáng),伍衛(wèi)國,崔金華,薛尚山,劉釗華

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

對象存儲系統(tǒng)由于可擴(kuò)展和易管理等特點(diǎn),已經(jīng)發(fā)展成為主流存儲系統(tǒng)架構(gòu)。常見的對象存儲系統(tǒng)有Red Hat公司的Ceph存儲系統(tǒng)[1]、Facebook的Cassandra存儲系統(tǒng)[2]等。對象存儲系統(tǒng)中對象是讀寫的基本單位。客戶端調(diào)用對象分布算法將對象分布到對象存儲設(shè)備(OSD)。高效簡潔的對象分布算法可以均衡I/O負(fù)載、自適應(yīng)系統(tǒng)的變化、提高數(shù)據(jù)可靠性[3]。

對象分布算法是對象存儲系統(tǒng)的核心組件,針對對象分布問題已有很多研究。為了解決對象分布的均勻性問題，提出一致性哈希算法[4]、層次化一致性哈希算法[5]、雙模對象分布算法[6]、Crush算法[7]、分層對象分布算法[8]、隨機(jī)切片算法[9]等。為了提高存儲I/O性能和降低數(shù)據(jù)熱點(diǎn)問題,Xu等提出了EDP算法以保證去重存儲系統(tǒng)中均勻讀[10];Jouini等提出了適用于文檔存儲的副本放置算法[11];Gao等提出了根據(jù)數(shù)據(jù)的訪問頻率分布對象算法[12];Shen等提出了一種應(yīng)用于BCube網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的提高數(shù)據(jù)修復(fù)速率的對象分布算法[13];Qin等提出了對象分布算法分別針對糾刪碼存儲中降級讀和寫性能進(jìn)行優(yōu)化[14],以上提及的對象分布算法雖然各具特色,但是在對象存儲系統(tǒng)的應(yīng)用中受到諸多約束,不具有普適性。本文利用存儲系統(tǒng)批量擴(kuò)容和刪除的特點(diǎn),設(shè)計(jì)了弧映射雙層對象分布(TMHR)算法。將同一批次的多個存儲節(jié)點(diǎn)劃分為子集群,對象分布過程中,TMHR算法首先采用可擴(kuò)展的子集群哈希(SHFC)算法選擇存放對象的子集群,其次采用隨機(jī)置換算法在目標(biāo)子集群內(nèi)計(jì)算存放對象的存儲節(jié)點(diǎn)。該算法可以在較短時(shí)間內(nèi)計(jì)算任意對象的目標(biāo)OSD節(jié)點(diǎn),保證對象均勻分布,遷移較少的對象以適應(yīng)OSD節(jié)點(diǎn)的動態(tài)變化。

1 問題定義

設(shè)存儲系統(tǒng)以子集群為單位進(jìn)行擴(kuò)容和刪除,擴(kuò)容、刪除的第i個子集群用Ci表示,其權(quán)值用wi表示,wi是子集群Ci內(nèi)節(jié)點(diǎn)容量、性能等特征的量化,根據(jù)具體需求賦予權(quán)值不同的含義。如以存儲容量為量化標(biāo)準(zhǔn),則1 TB的存儲節(jié)點(diǎn)和500 GB的存儲節(jié)點(diǎn)的權(quán)值之比為2∶1。Ci擁有的存儲節(jié)點(diǎn)數(shù)為mi。初始時(shí)存儲系統(tǒng)僅包括子集群C0,所有子集群用子集群集合C表示,所有子集群數(shù)用k表示。對象數(shù)為y(y≥1),每個對象擁有唯一的識別符,對象數(shù)理論上無限,且對象數(shù)遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)數(shù)。

2 TMHR算法

利用存儲系統(tǒng)批量擴(kuò)容、刪除的特性,TMHR算法采用雙層映射模式,存儲節(jié)點(diǎn)按照加入系統(tǒng)的批次被分為多個子集群,相同的子集群內(nèi)節(jié)點(diǎn)性能、容量相似?？蛻舳俗x寫對象時(shí)只需要從存儲系統(tǒng)獲取當(dāng)前子集群和節(jié)點(diǎn)的描述信息,客戶端在本地完成對象和其存儲節(jié)點(diǎn)映射關(guān)系的計(jì)算,即在子集群間采用SHFC算法以權(quán)值為概率選取目標(biāo)子集群,在目標(biāo)子集群內(nèi)采用隨機(jī)置換算法等概率選擇目標(biāo)節(jié)點(diǎn)。

2.1 子集群間SHFC算法

基于動態(tài)區(qū)間映射算法和隨機(jī)切片算法兩者都將對象存儲在以區(qū)間為單位的邏輯單元中,兩種算法的時(shí)間復(fù)雜度與區(qū)間數(shù)均正相關(guān)。系統(tǒng)擴(kuò)容過程中兩種算法都會產(chǎn)生大量小區(qū)間,雖然隨機(jī)切片算法提出了4種減小區(qū)間碎片化的策略,但是區(qū)間數(shù)仍然較大,極大地影響了系統(tǒng)I/O性能。為了解決系統(tǒng)擴(kuò)容造成的區(qū)間碎片化問題,SHFC算法將對象和子集群的哈希值映射在半徑為R的環(huán)形空間,根據(jù)子集群的權(quán)值將整個環(huán)形空間分為相應(yīng)比例的弧,每個子集群負(fù)責(zé)存儲映射在弧上的對象,并將最大相鄰弧合并策略應(yīng)用于系統(tǒng)的擴(kuò)容、刪除過程。

當(dāng)映射在子集群Ci上的弧序列需要重映射部分弧到子集群Cj時(shí),設(shè)需要遷移的弧長為L,設(shè)子集群Ci上的弧序列為{a1,a2,…,ae},則最大相鄰弧合并策略會盡可能的從子集群Ci的弧序列中找到多個弧au(1≤u≤e)之和的長度接近L。當(dāng)需要對存在的弧切割時(shí),切割滿足如下條件的弧,該弧切割后可以與目標(biāo)子集群Cj的弧合并,同時(shí)該弧是所有滿足條件的弧中最長的弧。

存儲系統(tǒng)擴(kuò)容、刪除子集群后,SHFC算法不需要重新分割整個環(huán)形區(qū)間,而是更新發(fā)生變化的弧和子集群之間的映射關(guān)系,這種策略使重映射的弧長度最短,從而使需要遷移的對象最少。

2.2 子集群內(nèi)隨機(jī)置換算法

子集群內(nèi)的對象分布采用隨機(jī)置換算法降低計(jì)算時(shí)間開銷。隨機(jī)置換算法實(shí)現(xiàn)了對副本機(jī)制的支持,保證同一對象的多個副本均勻分布在OSD節(jié)點(diǎn)上。計(jì)算對象x的第r個副本存放節(jié)點(diǎn)的函數(shù)為

f(x,r,m)=(hash(x)+rp)modm

(1)

式中:x是對象的標(biāo)識符;r是小于m的副本數(shù);p和m都是質(zhì)數(shù),且滿足p>m。m默認(rèn)等于子集群Ci(0≤i≤k-1)的節(jié)點(diǎn)數(shù)mi,但是如果子集群Ci的節(jié)點(diǎn)數(shù)mi并非質(zhì)數(shù),則m取大于mi的最小質(zhì)數(shù)。式(1)對序列{0,1,…,m-1}進(jìn)行隨機(jī)置換生成等概率的新序列,對象x的第t(0≤t≤r-1)個副本存放在新序列的第t位。若新序列的第t位序號大于節(jié)點(diǎn)數(shù)mi,則順次選擇下一位。存儲系統(tǒng)的擴(kuò)容和刪除等都是批量操作,很少或者幾乎不會出現(xiàn)單個存儲節(jié)點(diǎn)加入、刪除的情況,單個存儲節(jié)點(diǎn)故障失效后很快會被替換,子集群內(nèi)的節(jié)點(diǎn)數(shù)是維持不變的,因此不需要考慮子集群內(nèi)的節(jié)點(diǎn)變化情況。

3 算法理論分析

3.1 公平性和自適應(yīng)性分析

以下證明隨機(jī)置換算法滿足公平性。第2.2節(jié)中隨機(jī)置換算法的核心思想可以用式(1)表示,式(1)可以分解為如下3個運(yùn)算操作

d=hash(x)modm

(2)

h=rpmodm

(3)

l=(d+h)modm

(4)

式(2)表示以對象x為種子生成隨機(jī)數(shù),取模映射在{0,1,…,m-1}整數(shù)范圍內(nèi),其值為d。式(3)表示以對象的副本為特征值對序列{0,1,…,m-1}隨機(jī)置換,文獻(xiàn)[15]指出,如果gcd(b,c)=1,bp≡gmodc并且p是解,那么p一定是唯一解,因此可以得出對象x的副本數(shù)r和h存在一一映射關(guān)系。式(4)表示將置換后的整數(shù)序列循環(huán)右移了d位得到l。綜上可得,式(1)以對象x和副本數(shù)r為特征值,將序列{0,1,…,m-1}等概率隨機(jī)置換生成新序列。若m與子集群Ci的節(jié)點(diǎn)數(shù)mi相等,則任意節(jié)點(diǎn)被選中的概率是1/mi,若m是大于mi的最小質(zhì)數(shù),重復(fù)依次選擇下一位,則任意節(jié)點(diǎn)被選中的概率是(1/m)·(m/mi)=1/mi,因此隨機(jī)置換算法滿足公平性。

3.2 復(fù)雜度分析

4 實(shí)驗(yàn)對比分析

在計(jì)算時(shí)間、均勻性、公平性和自適應(yīng)性4個方面比較TMHR算法、一致性哈希算法和隨機(jī)切片算法,實(shí)驗(yàn)的操作系統(tǒng)為ubuntu 14.04 LTS系統(tǒng),采用python語言實(shí)現(xiàn)3種算法。

圖1 對象分布時(shí)間開銷的比較

圖2給出了將15萬個對象分布到由25個節(jié)點(diǎn)組成的存儲系統(tǒng)后的對象分布情況,25個節(jié)點(diǎn)共分為5個子集群,每個子集群包括5個節(jié)點(diǎn),子集群與子集群之間的OSD節(jié)點(diǎn)是異構(gòu)的,5個子集群的權(quán)值比為1∶2∶3∶4∶5,從圖2可以看出,對象在0～4號子集群內(nèi)是均勻分布的,子集群間呈現(xiàn)比例分布,也就是說異構(gòu)環(huán)境中對象的分布會隨加入OSD節(jié)點(diǎn)特性的變化而變化,因此本文算法是完全適應(yīng)于異構(gòu)環(huán)境的。

圖2 不同權(quán)值OSD組成的子集群間對象數(shù)比較

圖3給出了由120～360個節(jié)點(diǎn)組成的存儲系統(tǒng)中3種算法分別分布100萬個對象的均勻性比較。從圖3可以看到,TMHR算法和隨機(jī)切片算法的方差比一致性哈希算法的方差小,即這兩種算法對象分布的更加均勻,有效保證了存儲節(jié)點(diǎn)的負(fù)載均衡。TMHR算法和隨機(jī)切片算法都可以通過理論證明節(jié)點(diǎn)分配的對象數(shù)和其權(quán)值成正比,并且TMHR算法將對象進(jìn)行雙層映射細(xì)粒度分布,比隨機(jī)切片算法分布更加均勻。一致性哈希算法只是將節(jié)點(diǎn)、對象隨機(jī)分布到環(huán)形空間,當(dāng)數(shù)據(jù)量較大時(shí)對象才能均勻分布,因此其公平性相對較差。

圖3 對象分布算法的公平性比較

實(shí)驗(yàn)?zāi)M比較一致性哈希算法、TMHR算法在存儲系統(tǒng)批量擴(kuò)容、刪除后對象的遷移量,對象遷移量越少表示算法自適應(yīng)性越好。圖4、5給出了180個節(jié)點(diǎn)組成的存儲系統(tǒng)擴(kuò)容、刪除后每個節(jié)點(diǎn)的對象遷移量。存儲系統(tǒng)中每5個節(jié)點(diǎn)為1個子集群。圖4是模擬存儲系統(tǒng)的61～120號節(jié)點(diǎn)失效后剩余節(jié)點(diǎn)的對象遷移量。存儲系統(tǒng)中預(yù)先已分布了100萬個對象,因此理論上可以計(jì)算得到在節(jié)點(diǎn)刪除前每個節(jié)點(diǎn)存儲的對象數(shù)為106/180≈5 555個。在節(jié)點(diǎn)刪除后,每個節(jié)點(diǎn)存儲的對象數(shù)為106/120≈8 333個,則被刪除的節(jié)點(diǎn)平均遷移2 778個對象到剩余的節(jié)點(diǎn)。從圖4可以看出,TMHR算法在1～60號節(jié)點(diǎn)和121～180號節(jié)點(diǎn)的變化量在2 800左右,實(shí)際遷移量和理論值相近,而一致性哈希算法在1～60號節(jié)點(diǎn)和121～180號節(jié)點(diǎn)的變化量在5 000～6 700左右波動,遷移量較大。此外,61～120號節(jié)點(diǎn)的遷移量表示在節(jié)點(diǎn)刪除前節(jié)點(diǎn)的對象數(shù),可以看出在刪除前TMHR算法的對象分布相對均勻,每個節(jié)點(diǎn)都大致分布了5 500個對象,和理論值5 555大致相等,而一致性哈希算法每個節(jié)點(diǎn)分布的對象數(shù)波動較大,公平性較差。

圖4 61～120節(jié)點(diǎn)失效后的數(shù)據(jù)遷移量比較

如圖5所示是模擬180個節(jié)點(diǎn)組成的存儲系統(tǒng)加入60個節(jié)點(diǎn)后1～180號節(jié)點(diǎn)的對象遷移量。系統(tǒng)擴(kuò)容前每個節(jié)點(diǎn)分配的對象數(shù)為106/180≈5 555個。在節(jié)點(diǎn)增加后,每個節(jié)點(diǎn)存儲的對象數(shù)為106/240≈4 166個,因此擴(kuò)容后每個節(jié)點(diǎn)都要遷移5 555-4 166=1 389個對象到新加入節(jié)點(diǎn)。從圖5可以看出,TMHR算法中每個節(jié)點(diǎn)的對象遷移量和理論值相近,且每個節(jié)點(diǎn)遷移量也大致相等,而一致性哈希算法對象遷移量波動較大。

圖5 節(jié)點(diǎn)增加后的數(shù)據(jù)遷移量比較

通過模擬實(shí)驗(yàn),從圖1～5可以得出如下結(jié)論:與一致性哈希算法和隨機(jī)切片算法相比,TMHR算法在對象分布時(shí)間上分別縮短了20%和28%,較快的對象分布有利于客戶端快速讀寫對象,提高系統(tǒng)性能;實(shí)驗(yàn)結(jié)果表明,TMHR算法可以使對象分布的更加均勻,保證系統(tǒng)負(fù)載均衡;當(dāng)系統(tǒng)擴(kuò)容、刪除后,可以遷移較少的對象以保證對象均勻分布。

5 結(jié) 論

大數(shù)據(jù)時(shí)代下,對象分布算法對于對象存儲系統(tǒng)的性能影響更加顯著。目前,大部分對象分布算法無法在公平性、自適應(yīng)性、高效性和簡潔性取得一定的平衡,很難應(yīng)用于EB級混合異構(gòu)存儲系統(tǒng)中。本文提出了一種高效簡潔的TMHR對象分布算法,算法支持權(quán)值和副本機(jī)制,在具有較低的時(shí)間復(fù)雜度的前提下,兼顧了算法的公平性、高效性、簡潔性和自適應(yīng)性。實(shí)驗(yàn)?zāi)M結(jié)果表明,與一致性哈希算法和隨機(jī)切片算法相比,TMHR算法在對象分布時(shí)間上分別縮短了20%和28%,數(shù)據(jù)的分布也更加接近于理論情況,對象遷移量方面更加接近理論最優(yōu)值。異構(gòu)存儲系統(tǒng)中對象分布數(shù)量與OSD節(jié)點(diǎn)的權(quán)值成正比,因此TMHR算法更加適用于異構(gòu)對象存儲系統(tǒng)。

參考文獻(xiàn):

[1] WEIL S A,BRANDT S A,MILLER E L,et al. Ceph: a scalable,high-performance distributed file system [C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation. New York,USA: ACM,2006: 307-320.

[2] LAKSHMAN A,MALIK P. Cassandra: a decentralized structured storage system [J]. ACM SIGOPS Operating Systems Review,2010,44(2): 35-40.

[3] FACTOR M,METH K,NAOR D,et al. Object storage: the future building block for storage systems [C]//Proceedings of the 2005 IEEE International Symposium on Mass Storage Systems and Technology. Piscataway,NJ,USA: IEEE,2005: 119-123.

[4] KARGER D,LEHMAN E,LEIGHTON T,et al. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web [C]//Proceedings of the 29th ACM Symposium on Theory of Computing. New York,USA: ACM,1997: 654-663.

[5] ZHOU J,XIE W,GU Q,et al. Hierarchical consistent hashing for heterogeneous object-based storage [C]//Proceedings of the 14th IEEE International Symposium on Parallel and Distributed Processing with Applications. Piscataway,NJ,USA: IEEE,2016: 1597-1604.

[6] XIE W,ZHOU J,NOBLE J,et al. Two-mode data distribution scheme for heterogeneous storage in data centers [C]//Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway,NJ,USA: IEEE,2015: 327-332.

[7] WEIL S A,BRANDT S A,MILLER E L,et al. CRUSH: controlled,scalable,decentralized placement of replicated data [C]//Proceedings of the 2006 ACM/IEEE Conference on Super-Computing. Piscataway,NJ,USA: IEEE,2006: 31.

[8] 陳濤,肖儂,劉芳. 對象存儲系統(tǒng)中一種高效的分層對象布局算法 [J]. 計(jì)算機(jī)研究與發(fā)展,2012,49(4): 887-899.

CHEN Tao,XIAO Nong,LIU Fang. An efficient hierarchical object placement algorithm for object storage systems [J]. Journal of Computer Research and Development,2012,49(4): 887-899.

[9] MIRANDA A,EFFERT S,KANG Y,et al. Random slicing: efficient and scalable data placement for large-scale storage systems [J]. ACM Transactions on Storage,2014,10(3): 1-35.

[10] XU M,ZHU Y,LEE P P C,et al. Even data placement for load balance in reliable distributed deduplication storage systems [C]//Proceedings of the 23th IEEE International Symposium on Quality of Service. Piscataway,NJ,USA: IEEE,2016: 349-358.

[11] JOUINI K. Distorted replicas: intelligent replication schemes to boost I/O throughput in document-stores [C]// Proceedings of the 2017 IEEE/ACS International Conference on Computer Systems and Applications. Piscataway,NJ,USA: IEEE,2017: 25-32.

[12] GAO Y,LI K,JIN Y. Compact,popularity-aware and adaptive hybrid data placement schemes for heterogeneous cloud storage [J]. IEEE Access,2017,5(99): 1306-1318.

[13] SHEN Z,LEE P P C,SHU J,et al. Encoding-aware data placement for efficient degraded reads in XOR-coded storage systems [C]// Proceedings of the 35th IEEE Symposium on Reliable Distributed Systems. Piscataway,NJ,USA: IEEE,2016: 239-248.

[14] QIN Y,AI X,CHEN L,et al. Data placement strategy in data center distributed storage systems [C]// Proceedings of the 2016 IEEE International Conference on Communication Systems. Piscataway,NJ,USA: IEEE,2017: 1-6.

[15] STINSON D R. Combinatorial designs: constructions and analysis [M]. Berlin,Germany: Springer-Verlag,2003: 56-57.