云存儲多卷負(fù)載均衡的LSM鍵值存儲系統(tǒng)

徐 鵬,周元輝,陳書寧,劉 瑋,李大平,萬繼光

1(華中科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院 武漢光電國家研究中心,武漢 430074) 2(北京平凱星辰科技發(fā)展有限公司,北京 100192)

1 引 言

建設(shè)“數(shù)字化中國”是《十四五規(guī)劃》提出的重要目標(biāo)之一,數(shù)字化建議意味著海量的數(shù)據(jù)[1].隨著網(wǎng)絡(luò)技術(shù)的不斷進(jìn)步,在一些場景下,用戶通過網(wǎng)絡(luò)獲取數(shù)據(jù)的速度接近甚至是超過了從本地存儲中獲取數(shù)據(jù)的速度.因此,數(shù)據(jù)上云是一大趨勢,云存儲具有數(shù)據(jù)可靠性高[2,3]、擴(kuò)展性強(qiáng)[4,5]、按需付費(fèi)和性能穩(wěn)定等特點,能夠為用戶提供豐富的服務(wù)[6,7].但是單個云存儲卷(以下簡稱卷)可使用的最大IOPS和帶寬受到限制[8],無法滿足用戶的高性能,特別是IOPS需求.基于云存儲服務(wù)商的對云存儲卷的計費(fèi)規(guī)則和實際性能測試,發(fā)現(xiàn)相比于單個卷,在容量相同時,組合使用多個小容量的卷能夠以相同的費(fèi)用獲得更高的IOPS和帶寬性能.然而,測試表明,簡單組合使用多個卷的方式會導(dǎo)致各個成員卷之間的負(fù)載嚴(yán)重不均衡,不能充分發(fā)揮出多卷所累加的最大性能.

為充分發(fā)揮多卷的性能,需要基于實際的存儲系統(tǒng)進(jìn)行分析和優(yōu)化.日志結(jié)構(gòu)歸并樹(Log-structured Merge-tree,LSM)[9]以讀性能為代價的設(shè)計思想極大地提升了寫性能,因此已被廣泛應(yīng)用于各大互聯(lián)網(wǎng)服務(wù)廠商的鍵值存儲系統(tǒng)(例如Facebook的RocksDB[10]、Apache的Cassandra[11]、Google的BigTable[12]和LevelDB[13]以及阿里云的X-Engine[14]),成為了各類存儲系統(tǒng)的重要組成部分.對此,本文旨在充分發(fā)揮部署在LSM鍵值存儲系統(tǒng)的多云存儲卷性能.

LSM的數(shù)據(jù)分層設(shè)計使得LSM鍵值存儲系統(tǒng)在處理讀請求時產(chǎn)生大量的I/O請求[15-17].雖然鍵值對在Li層內(nèi)的各sstable文件之內(nèi)和之間均保持有序且不存在重復(fù),但是Li層與Li+1層之間的鍵值對則不然.因此,在查找鍵值對時,LSM鍵值存儲系統(tǒng)必須逐層進(jìn)行查找,且在未命中目標(biāo)鍵值對或遍歷完所有的層之前無法確保查詢結(jié)果的正確性.相較于將寫請求在內(nèi)存中進(jìn)行聚合之后再批量地寫入存儲的設(shè)計[18],在最壞情況下,LSM鍵值存儲系統(tǒng)處理讀請求時需要向每一層發(fā)出隨機(jī)I/O請求,導(dǎo)致大量的讀I/O放大.因而,依賴于隨機(jī)I/O請求的讀性能受到卷的IOPS性能和鍵值對在LSM各層分布的影響.

現(xiàn)有的多卷負(fù)載均衡方案僅依靠寫數(shù)據(jù)策略來最終決定數(shù)據(jù)在成員卷之間的分布,不僅無法充分應(yīng)對多變的讀負(fù)載(例如順序讀寫、隨機(jī)讀寫或晝夜變化等[19,20])的問題,同時依然存在將LSM不同層鍵范圍重合度高的sstable(或者一部分)分配到同一個成員卷的問題,導(dǎo)致成員卷之間的讀負(fù)載嚴(yán)重不均衡.

因此,需要將在多卷的成員卷之間遷移讀負(fù)載熱數(shù)據(jù)的方式作為現(xiàn)有多卷負(fù)載均衡方案的補(bǔ)充.而為了實現(xiàn)讀負(fù)載均衡,需要實現(xiàn)鍵范圍在各個成員卷之間均勻分布,從而避免讀負(fù)載的熱數(shù)據(jù)引起單個成員卷的I/O壓力超過其購買的IOPS性能、進(jìn)而造成多卷整體性能無法充分發(fā)揮的問題.

為此,以提升多卷讀性能為目標(biāo),提出一種云存儲多卷負(fù)載均衡的LSM鍵值存儲系統(tǒng)TANGO.TANGO通過優(yōu)化LSM的合并操作過程以實現(xiàn)多卷的讀寫負(fù)載均衡.在合并操作新生成的sstable落盤前,先根據(jù)統(tǒng)計的多卷中各個成員卷的關(guān)鍵信息,判斷該sstable與各個成員卷的鍵范圍重疊情況,選擇鍵范圍重疊最小的成員卷執(zhí)行寫入;針對讀為主的負(fù)載,無法通過合并操作達(dá)到負(fù)載均衡,TANGO采用后臺數(shù)據(jù)遷移方式進(jìn)一步達(dá)到負(fù)載均衡.由此,針對每個鍵范圍數(shù)據(jù)的讀I/O請求會被均勻分散至多個成員卷,實現(xiàn)多卷讀負(fù)載均衡的目標(biāo),從而充分發(fā)揮多卷的性能.

本文的主要貢獻(xiàn)如下:

1)將現(xiàn)有多路徑負(fù)載均衡或哈希負(fù)載均衡的方案應(yīng)用于使用多云存儲卷的LSM鍵值存儲系統(tǒng),并對云存儲卷進(jìn)行了大量的組合測試,通過實驗證明同等存儲容量下多卷性能更好;但是,各成員卷之間仍然存在負(fù)載不均衡的問題,不能充分發(fā)揮出多卷的最大性能.進(jìn)一步通過實驗和觀察,發(fā)現(xiàn)了基于LSM鍵值存儲系統(tǒng)的多卷中各成員卷I/O負(fù)載嚴(yán)重不均衡的原因.以上發(fā)現(xiàn)為設(shè)計更為高效的多卷性能優(yōu)化方案提供了依據(jù).

2)針對1)中分析的結(jié)果,提出一種云存儲多卷負(fù)載均衡的LSM鍵值存儲系統(tǒng)TANGO.在LSM中合并操作新生成的sstable確定落盤的目標(biāo)卷之前,先根據(jù)統(tǒng)計的多卷中各個成員卷的關(guān)鍵信息,判斷要寫入sstable與各個成員卷的鍵范圍重疊情況,選擇鍵范圍重疊最小的成員卷寫入.TANGO也通過選擇性復(fù)制的熱點數(shù)據(jù)遷移方法進(jìn)一步均衡讀請求熱點數(shù)據(jù)分布.TANGO方案從讀和寫兩個角度對多卷性能進(jìn)行優(yōu)化,彌補(bǔ)了現(xiàn)有多卷使用方案應(yīng)對LSM鍵值存儲系統(tǒng)的讀請求熱數(shù)據(jù)分布嚴(yán)重不均的缺點.

3)在亞馬遜云的彈性塊存儲卷上實現(xiàn)了TANGO以及對比方案,并將所有方案進(jìn)行了詳細(xì)的對比和分析,從多卷整體性能、各成員卷平均性能、成員卷實時性能和遷移開銷等方面驗證了TANGO的高效性.

2 背景及相關(guān)工作

2.1 LSM鍵值存儲系統(tǒng)架構(gòu)

如圖1所示,基于LSM的鍵值存儲系統(tǒng)中包含多層存儲結(jié)構(gòu)(L0、L1至底層),每層存儲容量有限,但每層的容量隨層數(shù)的增加而逐層增大.所有到來的寫請求都會被緩存至內(nèi)存的緩存區(qū)memtable,而后寫入到一個固定大小的sstable文件中,該sstable會被放入L0層.L0層中數(shù)據(jù)總量達(dá)到設(shè)定閾值時會觸發(fā)合并操作(compaction),該操作將L0層和L1層有鍵范圍重疊的多個sstable進(jìn)行整理,合并重復(fù)數(shù)據(jù)、刪去無效數(shù)據(jù)后,對剩下的鍵值對以鍵為序進(jìn)行排序,并且將鍵范圍相近的數(shù)據(jù)放在一起構(gòu)成新的sstable,之后再寫入到L1層中.其它Li～Li+1層的合并操作以此類推.

具體而言,合并操作通常需要執(zhí)行以下3個步驟:

①讀:將選定的Li和Li+1層sstable讀取到內(nèi)存.

②歸并:將鍵值對從這些sstable數(shù)據(jù)塊中的緊湊格式解包為鍵值對格式,然后將這些Li和Li+1層所有的鍵值對歸并排序、刪去Li和Li+1有相同鍵的鍵值對.接著將余下排序好的鍵值對重新打包為緊湊的sstable數(shù)據(jù)塊格式,同時為每個新sstable生成對應(yīng)的索引塊和過濾器等元數(shù)據(jù)信息.

③寫:將這些新sstable寫回存儲系統(tǒng)、插入到Li+1層,最后刪去Li和Li+1層的舊sstable.

在上述寫請求的數(shù)據(jù)流動路徑下,LSM鍵值存儲系統(tǒng)處理讀請求時,首先在內(nèi)存的memtable查找,然后從L0～Ln層依次進(jìn)行查找.在Li層查找時,根據(jù)sstable的鍵值范圍確定每層的候選sstable,然后使用候選sstable的元數(shù)據(jù)查找候選數(shù)據(jù)塊,并在該數(shù)據(jù)塊中進(jìn)行查找.如果該層未讀命中,則繼續(xù)在下一層進(jìn)行查找,直至命中或所有層均未命中.

2.2 多卷負(fù)載均衡方式

亞馬遜云是目前應(yīng)用最為廣泛的云服務(wù),因此本文以亞馬遜云存儲為例進(jìn)行研究.在亞馬遜彈性塊云存儲(Elastic Block Store)的計費(fèi)策略下,實現(xiàn)多卷中各個成員卷之間的負(fù)載均衡是高效、低成本地充分提高和發(fā)揮多卷性能的關(guān)鍵之一.數(shù)據(jù)寫入時在各個成員卷之間的落盤策略會對后續(xù)負(fù)載均衡狀況產(chǎn)生巨大影響.在基于LSM的鍵值存儲系統(tǒng)中,各層的寫入都包含在合并操作中.因此合并操作決定了絕大部分鍵范圍在各個成員卷之間的分布情況.

現(xiàn)有多卷負(fù)載均衡方案以調(diào)控寫請求數(shù)據(jù)布局為主,可以歸納為3類:輪詢方式,RAID方式和哈希方式.

①輪詢方式:現(xiàn)有文獻(xiàn)中沒有發(fā)現(xiàn)針對云存儲多卷優(yōu)化的LSM鍵值存儲系統(tǒng)的工作.為證明本文提出方案的有效性,現(xiàn)將現(xiàn)有其它多路徑的負(fù)載均衡方法用于云存儲多卷作為對比.通過輪詢方式依次選取多卷中的成員卷[21,22],將上層通過合并操作新生成的sstable寫入其中,可以讓數(shù)據(jù)量在所有成員卷之間均勻分布.當(dāng)然,也僅能實現(xiàn)數(shù)據(jù)量的均衡分布.

在LSM鍵值存儲系統(tǒng)中,由于Li與Li+1層之間的鍵范圍存在重疊,且寫負(fù)載的鍵值范圍不確定,所以合并操作所涉及的層數(shù)同樣存在較大的不確定性.因此,在多個成員卷之間以輪循方式寫sstable時,無法實現(xiàn)鍵范圍在各個成員卷之間的均衡分布.最終,導(dǎo)致輪循方案只能一定程度上解決寫負(fù)載的均衡問題,而無法有效避免讀負(fù)載的熱鍵范圍集中在某個成員卷上的問題.

②RAID方式:文獻(xiàn)采用RAID0的方式組織多卷來充分發(fā)揮其所有成員卷的并行性能[23],但未注意到多卷之間的負(fù)載均衡問題.先將多卷中的N個成員卷組成RAID0,接著將要寫入到下一層的sstable切分為多個固定大小的數(shù)據(jù)塊(Chunk),然后將這些數(shù)據(jù)塊并行地寫入到每個成員卷.具體地,sstable的大小、切分的數(shù)據(jù)塊大小以及成員卷的數(shù)量等因素綜合決定了數(shù)據(jù)塊在各個成員卷上的分布情況.RAID0布局策略不僅能使每個sstable的鍵范圍分散到各個成員卷上,還能夠充分利用多個成員卷的并行寫性能.

但RAID0布局方式存在以下問題:首先,RAID0分割sstable進(jìn)行數(shù)據(jù)布局時沒有考慮各個數(shù)據(jù)塊所包含鍵范圍的熱度,仍然無法解決讀負(fù)載不均衡導(dǎo)致的讀I/O請求集中在單個成員卷上的問題,從而會造成RAID0整體性能下降.其次,RAID0擴(kuò)容時需要進(jìn)行數(shù)據(jù)重構(gòu),會對所有數(shù)據(jù)產(chǎn)生影響,需要進(jìn)行大量的數(shù)據(jù)遷移,也會對性能產(chǎn)生影響.

③哈希方式:現(xiàn)有文獻(xiàn)中沒有發(fā)現(xiàn)結(jié)合云存儲多卷負(fù)載均衡和LSM鍵值存儲系統(tǒng)的哈希優(yōu)化方案.為證明本文提出方案的有效性,現(xiàn)將現(xiàn)有其它負(fù)載均衡的哈希方法[24]用于云存儲多卷作為對比.哈希布局方案通過哈希算法來管理多卷中的各個成員卷,基于sstable文件名進(jìn)行哈希,根據(jù)哈希結(jié)果將各個sstable分配到對應(yīng)的成員卷.哈希布局方案相比輪循方式更加隨機(jī),也能夠避免成員卷數(shù)量變動時帶來的大量的數(shù)據(jù)遷移,減少對整體性能的影響.

但是,若成員卷數(shù)量較少,則容易發(fā)生哈希沖突,從而導(dǎo)致各成員卷之間負(fù)載不均衡.此外,現(xiàn)有哈希布局方案同樣無法感知sstable內(nèi)的鍵范圍,存在將LSM不同層鍵范圍重合度高的sstable分配到同一個成員卷的問題.

3 問題分析

在本節(jié)中,首先展示了組合使用多個云存儲卷具有更高的性價比這一現(xiàn)象,然后揭示了目前多卷性能無法充分發(fā)揮這一問題并作出了進(jìn)一步探索和說明.最后,基于發(fā)現(xiàn)的現(xiàn)象和問題,提出本文的設(shè)計思想.

3.1 組合使用多個單卷性價比更高

如表1所示,展示了大型云服務(wù)提供商亞馬遜的云存儲服務(wù)收費(fèi)情況.亞馬遜為單個云存儲卷的IOPS和帶寬都設(shè)置了最大值,并且提供了不同的容量性能模式.用戶可以根據(jù)自己需求選擇相應(yīng)類型的云存儲卷并進(jìn)行參數(shù)配置.用戶可基于初始IOPS選擇是否購買額外的IOPS,購買時以IOPS/GB為單位,但是不能超過最大IOPS和帶寬限制.所以如果只使用單個云存儲卷提供服務(wù),容易陷入帶寬和IOPS瓶頸.因此考慮通過多卷組合的方式以打破單卷的性能限制、獲得更高的存儲性能.

表1 亞馬遜彈性塊存儲的gp3和io1性能和費(fèi)用概要Table 1 Summary of Amazon EBS performance and price

以亞馬遜gp3類型的云存儲卷為例,1個容量3000GB的單卷與3個容量1000GB的多卷的總?cè)萘亢涂傎M(fèi)用都相同.表2示意了應(yīng)用廣泛的LSM鍵值存儲系統(tǒng)RocksDB在總?cè)萘亢涂傎M(fèi)用相同的gp3單卷(3000GB)和多卷(3×1000GB)上的隨機(jī)寫性能.多卷時,RocksDB采用輪循的方式在3個單卷之間寫sstable.從表2中可以觀察到,相比同費(fèi)用和容量的單卷,多卷時RocksDB的隨機(jī)寫IOPS和吞吐率均提升了一倍、平均時延降低了一半.因為單卷受到了帶寬的限制,導(dǎo)致實際使用的IOPS也受到明顯的影響.而3個存儲卷理論上帶寬可以提高2倍,但實際測試中只提高了1倍,性能并沒有完全發(fā)揮.

表2 RocksDB在總?cè)萘亢涂傎M(fèi)用相同的gp3單卷和多卷上的隨機(jī)寫性能(歸一化結(jié)果)Table 2 RocksDB random write performance with a single or three volumes(normalized)

直觀來看,通過將單個大容量云存儲卷拆分為多個小容量卷的方式,可在費(fèi)用和容量相同的情況下獲得更高的性能.但是多卷性能沒有完全發(fā)揮,需要進(jìn)一步驗證和探討.

3.2 多卷性能無法充分發(fā)揮的現(xiàn)象

測試采用的系統(tǒng)為RocksDB,負(fù)載通過YCSB(Yahoo!Cloud Servering Benchmark,YCSB)[25]進(jìn)行仿真.測試中配置了6個單卷,類型為亞馬遜彈性塊存儲gp3的卷,每個卷的容量為60GB、購買的IOPS為3000.

測試時,先通過YCSB加載5000萬條鍵值對,然后運(yùn)行1000萬條請求的測試負(fù)載,包含80%的讀操作和20%的更新操作.RocksDB生成的sstable被以輪循的方式分配到6個卷中.

圖2 多卷整體和各成員卷的實時IOPS情況,一種灰度的形狀代表一個成員卷Fig.2 Realtime IOPS of the six volumes and each volume

圖2示意了測試時多卷整體(上半圖)和每個成員卷(下半圖)的實時IOPS情況,通過不同的灰度表示不同的卷.從圖2可以觀察到,每個時間段,整體IOPS由于LSM聚合寫的效果而超過購買的18000,但立即又下降到10000～15000的水平;另外,每個時間段都有一個卷的IOPS長時間運(yùn)行在最高IOPS(3000)水平,其它卷的IOPS則在1000～2000之間的水平.該現(xiàn)象導(dǎo)致了絕大部分單卷IOPS性能未被充分利用,所以多卷性能存在較大波動,且多卷性能的起伏與大部分單卷的IOPS密切相關(guān).

圖3 鍵范圍1.4×1010～1.5×1010在各卷分布的局部放大,每一種灰度表示一個成員卷Fig.3 Distribution of the key range 1.4×1010 to 1.5×1010for each layer of the LSM over 6 volumes

3.3 多卷性能無法充分發(fā)揮的原因

圖3表示了LSM各層的鍵范圍(1.4×1010～1.5×1010)在6個成員卷上的分布情況,每種灰度表示一個成員卷.從圖3可以看到:數(shù)據(jù)在各個存儲卷上的分布是不均勻的,有的灰度在單層中占得比例更大一些,表明某些鍵范圍更多地分布該灰度表示的卷中;相鄰層之間鍵范圍重疊的數(shù)據(jù)灰度相同,說明這些數(shù)據(jù)都被存儲在一個成員卷中.因此,若鍵范圍重疊較高的數(shù)據(jù)被頻繁讀取時,大量的讀請求將會聚集在同一個成員卷上.因為每個存儲卷都存在帶寬和IOPS限制,熱數(shù)據(jù)較多的成員卷達(dá)到性能瓶頸后無法提供更高的性能,但是其它成員卷因為熱數(shù)據(jù)較少,帶寬和IOPS反而得不到有效利用,從而使多卷的整體性能下降.

3.4 問題分析小結(jié)和設(shè)計思路

LSM的數(shù)據(jù)分層機(jī)制造成了層與層之間鍵范圍的重疊,導(dǎo)致讀負(fù)載的小范圍熱數(shù)據(jù)分散在多層的多個sstable中,但是現(xiàn)有數(shù)據(jù)布局方案無法有效地將多卷中分布在多層、含有同一鍵范圍的熱sstable分散至多個成員卷.若多卷中數(shù)據(jù)無法根據(jù)鍵范圍情況均勻地分散到各個成員卷中,各成員卷的讀I/O數(shù)量將無法均衡.

為此,以提升多卷讀性能為目標(biāo),提出一種云存儲多卷負(fù)載均衡的LSM鍵值存儲系統(tǒng)TANGO.TANGO通過優(yōu)化LSM的合并操作的寫過程來實現(xiàn)多卷的讀負(fù)載均衡.在LSM鍵值存儲系統(tǒng)執(zhí)行合并操作并將新生成的Li+1層sstable寫入到Li+1層中之前,先檢測每個成員卷所擁有的Li+2層sstable與要寫入的sstable的鍵范圍重疊情況,選擇鍵范圍重疊最小的成員卷寫入.這樣一來,針對每個鍵范圍數(shù)據(jù)的讀I/O請求會被均勻分散至多個成員卷,能夠達(dá)到多卷讀負(fù)載均衡的目的,從而充分發(fā)揮多卷的性能.此外,TANGO主動地通過選擇性復(fù)制的方式將滿負(fù)荷卷的I/O請求卸載至其它卷,進(jìn)一步處理由負(fù)載變化導(dǎo)致的各成員卷熱點數(shù)據(jù)變化的問題.

4 TANGO設(shè)計

如圖4所示,為TANGO的整體架構(gòu)圖,從讀和寫兩個方面進(jìn)行多卷的負(fù)載均衡調(diào)度.

圖4 TANGO整體架構(gòu)Fig.4 Architecture of TANGO

在處理寫請求時,不論是將memtable經(jīng)由flush操作寫入到L0層,或是將合并操作新生成的Li+1層sstable寫入到Li+1層,都可以視為對新生成sstable的處理過程,都通過寫入決策進(jìn)行寫數(shù)據(jù)分布.

寫入決策:在寫入新sstable時,先檢測每個成員卷所擁有的sstable與要寫入的新sstable的鍵范圍重疊情況,選擇鍵范圍重疊最小的成員卷寫入.通過寫入決策的調(diào)整,鍵范圍更均勻地分布在多個卷之間,主動地均衡了各卷之間可能的讀負(fù)載.

讀請求到來時,會直接分發(fā)給數(shù)據(jù)所在的sstable,但是為了防止熱點數(shù)據(jù)過于集中,會定期通過負(fù)載遷移將讀熱點數(shù)據(jù)復(fù)制到負(fù)載較低的卷,以對讀負(fù)載在各個卷之間進(jìn)行重新分布.

負(fù)載遷移:負(fù)載遷移針對的是熱的讀請求數(shù)據(jù),通過數(shù)據(jù)遷移操作來直接調(diào)整各個成員卷讀負(fù)載的大小.若某個成員卷的IOPS達(dá)到其付費(fèi)IOPS,則說明該成員卷數(shù)據(jù)熱度過高,需要遷移部分熱數(shù)據(jù)到其它IOPS較低的成員卷,遷移時以sstable為最小單位.需要指出的是,遷出的數(shù)據(jù)通過復(fù)制的方式進(jìn)行,因此無須將數(shù)據(jù)遷回的操作.

4.1 關(guān)鍵信息統(tǒng)計

在進(jìn)行具體的讀寫調(diào)度之前,需要收集每個成員卷信息,包括每個sstable的被訪問情況以及鍵范圍等,然后計算出每個sstable的熱度值以整個成員卷的訪問權(quán)重,為寫入決策和數(shù)據(jù)遷移提供依據(jù).

關(guān)鍵信息統(tǒng)計部分除了需要簡單記錄各個成員卷中每個sstable的鍵范圍,還需要計算出每個sstable的熱度值和每個成員卷的訪問權(quán)重.

(1)

其中,N(t-1,t]表示在時間間隔(t-1,t]內(nèi)第i個sstable被訪問的次數(shù),WRio為sstable的大小除以256KB所得的實際寫入的I/O請求數(shù)量(因為云存儲卷會自動地將小寫請求盡可能地聚合為256KB的大寫請求[26]),α為冷卻系數(shù),在0～1之間(默認(rèn)為0.5).

(2)

上述統(tǒng)計的關(guān)鍵信息反映了每個卷的總體負(fù)載情況、對每個卷的I/O訪問以及卷內(nèi)的鍵范圍分布,為寫入決策和負(fù)載遷移提供了均衡各卷負(fù)載的依據(jù).另外,上述統(tǒng)計信息可以從LSM的相關(guān)處理過程中直接獲得,且需要的計算開銷低,所以不會帶來明顯的開銷.

4.2 寫入決策

4.2.1 鍵范圍重疊情況判斷

寫入sstable時除了對數(shù)據(jù)總量均勻分布的考量,還要盡量讓后續(xù)對該sstable所包含鍵范圍數(shù)據(jù)的讀取I/O請求分散在多個成員卷中,從而實現(xiàn)多個成員卷之間的I/O請求數(shù)量均衡.

因此,寫入新生成的sstable時,需要避免寫入到與該sstable對應(yīng)鍵范圍重疊比例較大的成員卷.所以,要先確認(rèn)新生成的Li+1層sstable與每個成員卷已有的Li+2層sstable鍵范圍的重疊情況,然后將新生成的sstable寫入到重疊次數(shù)最小的成員卷.寫入memtable時的操作相當(dāng)于L0層的特例,不再單獨(dú)說明.

在選擇成員卷寫入新生成的Li+1層sstable時,將該sstable與每個成員卷中Li+2層sstable的鍵范圍進(jìn)行對比.如果該sstable的鍵范圍與Li+2層某個成員卷的sstable存在鍵范圍重疊現(xiàn)象,則將該成員卷的重疊次數(shù)加1.

4.2.2 選擇要寫入的成員卷

根據(jù)統(tǒng)計結(jié)果,選取重疊次數(shù)最小的成員卷寫入新生成的sstable.當(dāng)有多個成員卷的重疊次數(shù)相同時,優(yōu)先考慮訪問權(quán)重最低的成員卷,若仍有相同項,則隨機(jī)選擇一個成員卷寫入新生成的sstable.

如圖5所示,展示了一個合并操作生成的sstable寫入時選擇成員卷的例子.圖5中,先對L1層的sstable 0(鍵范圍b-d)與L2層的sstable 1(鍵范圍a-b)和sstable 2(鍵范圍c-d)進(jìn)行合并,然后生成了新sstable 11(鍵范圍a-b)和sstable 12(鍵范圍c-d).通過鍵范圍重疊情況判斷可知,sstable 11與卷1、卷2、卷3、卷4的重疊次數(shù)分別為1、0、0、0,所以sstable 11可以寫入到負(fù)載較低的卷2中;sstable 12與卷1、卷2、卷3、卷4的重疊次數(shù)分別為0、1、0、0,所以sstable 12可以寫入到負(fù)載較低的卷3中.

圖5 寫入時選擇成員卷的示意圖Fig.5 Write the sstable to a volume with the minimal key range overlap

至此,借助LSM鍵值存儲系統(tǒng)flush操作和合并操作寫入新生成sstable的時機(jī),以較少的額外寫操作,可以將相鄰層之間具有鍵范圍重疊的sstable均勻分散至多個成員卷,在整體上實現(xiàn)各成員卷之間的負(fù)載均衡.

4.3 負(fù)載遷移

數(shù)據(jù)在寫入各成員卷后,因為讀負(fù)載發(fā)生變化,導(dǎo)致部分?jǐn)?shù)據(jù)過熱,使得各成員卷之間的I/O壓力不均衡.為此,只能主動遷移熱點數(shù)據(jù)來進(jìn)行平衡,將集中在單個成員卷上的熱點數(shù)據(jù)分散至負(fù)載較低的成員卷,從而使得多個成員卷的IOPS均勻且接近其購買的IOPS.

負(fù)載遷移功能彌補(bǔ)了寫入決策無法應(yīng)對負(fù)載變化引起的各卷之間讀負(fù)載不均的問題.由于負(fù)載遷移采用的是復(fù)制熱數(shù)據(jù)的方式,因此避免了遷回數(shù)據(jù)的開銷.

5 實驗與分析

本章節(jié)基于亞馬遜彈性塊云存儲卷進(jìn)行測試,測試所用負(fù)載由YCSB生成.

5.1 測試環(huán)境

測試平臺:使用應(yīng)用最為廣泛的亞馬遜云服務(wù)作為測試平臺.測試時,使用EC2 m5d.2xlarge云計算實例,該計算實例配置了8個vCPU、32GB內(nèi)存.組合使用6個容量均為60GB的gp3卷,理論上最高可提供18000的IOPS性能;作為對比,使用單個容量為360GB的gp3卷,該大容量的卷購買3000的IOPS性能.

對比方案:在應(yīng)用廣泛的LSM鍵值存儲系統(tǒng)RocksDB的基礎(chǔ)上,實現(xiàn)使用多個成員卷的TANGO及對比方案,同時對比使用單個大容量卷的性能.具體對比了TANGO、輪詢、RAID和哈希4種方案.多卷方案中,輪詢方案通過循環(huán)的方式為每個sstable選擇寫入的成員卷;RAID采用RAID0的方式將sstable切分為塊大小后組織為條帶的形式寫入所有的成員卷;哈希則是通過哈希sstable文件名來確定該sstable所寫入的成員卷.

測試工具:本文采用常用的云服務(wù)器標(biāo)準(zhǔn)測試集YCSB[25]進(jìn)行的測試,它提供了一個框架和一組默認(rèn)的7個工作負(fù)載,用于評估鍵值存儲的性能.1)負(fù)載Load:100%寫操作,生成數(shù)據(jù)集滿足Uniform分布;2)負(fù)載A:50%讀操作,50%寫操作,Zipfian分布;3)負(fù)載B:95%讀操作,5%寫操作,Zipfian分布;4)負(fù)載C:100%讀操作,Zipfian分布;5)負(fù)載D:95%讀操作,5%寫操作,Latest分布;6)負(fù)載E:95%范圍查詢,5%寫操作,Zipfian分布;7)負(fù)載F:50%寫操作,50%讀改寫操作,Zipfian分布.

測試時,首先基于YCBS自帶的A～F負(fù)載評估各種方案的整體效果,最后使用YCSB的合成負(fù)載進(jìn)行驗證.

默認(rèn)參數(shù):RocksDB的鍵大小為16B、值大小為256B,sstable大小為8MB,同時僅將sstable的元數(shù)據(jù)緩存在內(nèi)存中,以精確觀察TANGO對多卷IOPS性能的利用情況.

需要注意的是,觀察YCSB整體性能的測試獲取的是RocksDB之上的用戶IOPS請求,由于在RocksDB內(nèi)部將寫請求聚合后再處理,因此統(tǒng)計得到的IOPS可能高于多個卷的IOPS之和.觀察每個卷IOPS性能的測試獲取的是與云存儲卷實際交互的I/O信息,因此統(tǒng)計得到的IOPS將在卷所購買的IOPS性能附近.

5.2 多卷整體性能評估

5.2.1 YCSB默認(rèn)負(fù)載下的IOPS

本小節(jié)使用YCSB的6種默認(rèn)負(fù)載(負(fù)載A～F)來模擬工作負(fù)載,分別測試評估輪詢、RAID、哈希和TANGO 4種方案性能.

首先隨機(jī)加載5000萬條鍵值對數(shù)據(jù),然后運(yùn)行1000萬條鍵值對的工作負(fù)載.測試結(jié)果如圖6所示.6種工作負(fù)載下TANGO的性能都優(yōu)于其它多卷方案,且單卷相同容量時的IOPS明顯低于所有其它多卷方案.負(fù)載D時,TANGO的IOPS為23013,相較于其它多卷方案的IOPS至少提升了52%.由于6種默認(rèn)負(fù)載的讀寫比例和數(shù)據(jù)分布方式變量控制較為復(fù)雜,后續(xù)控制負(fù)載的變量只改變讀請求比例做進(jìn)一步觀察測試.

圖6 不同YCSB負(fù)載下各種方案的多盤整體IOPS

5.2.2 不同讀寫比例合成負(fù)載下的IOPS

本次測試基于YCBS的負(fù)載C合成的不同讀寫比例的負(fù)載以評估TANGO及其對比方案的整體IOPS性能,相比YCSB的默認(rèn)負(fù)載,讀寫比例設(shè)定更加靈活.首先隨機(jī)加載5000萬條鍵值對,然后執(zhí)行1000萬條鍵值對的隨機(jī)請求,統(tǒng)計不同讀請求比例下的整體IOPS,結(jié)果如圖7所示.

圖7 不同讀請求比例下各種方案的多卷整體IOPS

從圖7中可以觀察到,組合使用6×60GB gp3卷的TANGO、輪詢、RAID以及哈希方案在不同讀操作比例負(fù)載下的IOPS,均顯著高于使用單個容量為360GB的gp3卷.

在使用多個成員卷的方案中,TANGO在不同讀寫比例的負(fù)載下均表現(xiàn)出最高的IOPS性能.在100%隨機(jī)讀的負(fù)載下,TANGO的IOPS為17363,實現(xiàn)了多卷理論上最高18000 IOPS的94.4%利用率;相較于輪詢、RAID和哈希方案的IOPS性能,TANGO分別提升了26%、21%和30%,是費(fèi)用相同的情況下單個大容量卷IOPS的7倍左右.

隨著負(fù)載中寫請求比例的增加,所有方案的IOPS性能均有增加;主要原因是LSM鍵值存儲系統(tǒng)對寫請求I/O的聚合作用.在50%讀和50%寫的混合負(fù)載下,TANGO的IOPS性能為33419,比RAID0高25%;雖然RAID0通過并行寫6個卷提升了寫性能,但無法在多個成員卷之間進(jìn)行熱點數(shù)據(jù)均衡.哈希方案由于無法有效地在多個成員卷之間分散鍵范圍,因此在讀寫混合負(fù)載下致使單個成員卷的壓力超過該卷的付費(fèi)IOPS、限制了多卷整體IOPS的發(fā)揮.輪詢方案相對于RAID和哈希方案,能夠?qū)懢獾讲煌拇鎯砩?從而間接地使讀操作均衡,因此性能提高較快.

5.2.3 不同讀寫比例合成負(fù)載下的平均響應(yīng)時間

如圖8所示,不同讀請求比例下各種方案的平均響應(yīng)時間.可以看到TANGO方案的平均響應(yīng)時間最小,隨著讀請求比例降低,平均響應(yīng)時間持續(xù)減少.在讀比例為70%時,TANGO的平均時延僅為41us,比其它多卷方案中最低的輪詢方案降低了22%.這是因為TANGO在寫的過程中借助合并操作,實行了深入的數(shù)據(jù)分散布局,將數(shù)據(jù)寫入到鍵范圍重合度最低的成員卷中,以避免過多請求訪問同一個成員卷從而造成排隊時間過長.

圖8 不同讀請求比例下各種方案的平均響應(yīng)時間Fig.8 Average response time under varied read-write ratios

5.3 各成員卷性能

需要指出的是,受云計算實例和亞馬遜云的限制,無法獲取RAID方式中各成員卷的I/O性能.

5.3.1 各成員卷的平均IOPS

如圖9所示,顯示了兩種讀請求比例下3種方案各成員卷的平均IOPS.可以看到,對于輪詢和哈希方案,在90%和50%的讀請求比例下,各成員卷之間的平均IOPS參差不齊,始終存在較大的差距.在90%讀請求比例下,輪詢方案和哈希方案的IOPS最高成員卷與最低成員卷的IOPS相差分別達(dá)到35%和37%.對于TANGO方案,兩種讀比例下的各成員卷IOPS均在2900附近,差異都很小,尤其是在50%的讀請求下,各成員卷的IOPS相差小于1%,且均接近每個卷的3000最大IOPS.

圖9 兩種讀請求比例下3種方案的成員卷的平均IOPS

5.3.2 各成員卷的實時IOPS

為更直觀地說明各成員卷之間讀負(fù)載不均衡對總體性能的影響,本次測試使用YCBS合成的不同比例的讀寫負(fù)載,使用iostat獲取每個卷的實時IOPS,每種標(biāo)記表示一個卷,結(jié)果如圖10所示.

從圖10中可以觀察到,輪詢和哈希方案下各個成員卷的實時IOPS在2000～3000間呈現(xiàn)明顯的分層,大部分時間只有1個或2個成員卷能夠運(yùn)行在最高的3000的IOPS狀態(tài),因此多卷整體性能沒有被充分發(fā)揮.

TANGO方案下,各個成員卷的IOPS均維持在單卷最高的3000的IOPS附近運(yùn)行,且成員卷之間的IOPS差距較小.所以TANGO方案下的多卷整體性能最好.

圖10 兩種讀請求比例下多卷方案各成員卷的實時IOPS

另外,由于TANGO在寫入時將負(fù)載進(jìn)行均勻分布,使每個成員卷都能以最高性能運(yùn)行,整體性能上移,因此能夠在更快的時間內(nèi)完成操作.

5.3.3 多卷方案各成員卷實時IOPS的標(biāo)準(zhǔn)差

如圖11所示,不同讀請求比例下各種方案的實時IOPS標(biāo)準(zhǔn)差,該標(biāo)準(zhǔn)差由所有成員卷的最高IOPS與最低IOPS計算而來.可以觀察到,整體上,TANGO的標(biāo)準(zhǔn)差遠(yuǎn)小于輪詢和哈希方案.隨著運(yùn)行時間推移,TANGO各成員卷IOPS之間的標(biāo)準(zhǔn)方差逐漸減少,且穩(wěn)定在100左右.因為TANGO能夠識別冷熱數(shù)據(jù)并且進(jìn)行負(fù)載調(diào)度遷移,而輪詢和哈希方案無法減少各卷之間的I/O負(fù)載不均衡,其標(biāo)準(zhǔn)差穩(wěn)定在400左右.

圖11 不同讀請求比例下各種方案的實時IOPS標(biāo)準(zhǔn)方差Fig.11 Realtime IOPS standard deviations of each volume for varied read-write ratio and approaches

5.4 數(shù)據(jù)遷移開銷

TANGO的開銷可以分為兩個部分:1) 寫入決策改變合并操作中新生成sstable寫入位置帶來的開銷;2) 數(shù)據(jù)遷移的開銷.寫入決策的執(zhí)行可以減輕數(shù)據(jù)遷移的壓力,因為數(shù)據(jù)被按照鍵范圍分布的更加均勻.

寫入決策需要統(tǒng)計各個成員卷的關(guān)鍵信息,判斷鍵范圍重疊情況,所有的信息統(tǒng)計和判斷操作都是通過額外線程來執(zhí)行的.因為sstable的粒度在MB級別,所以只需要少量的存儲空間和CPU計算資源即可,不會引起明顯的性能開銷.由于TANGO僅改變了sstable的寫位置,因此不會對sstable的持久化和合并操作造成額外影響.

因為在多卷存儲體中,熱點聚集于某個存儲卷中的多個sstable中,并且該卷的性能達(dá)到上限后限制了其余卷的訪問,因此需要進(jìn)行熱數(shù)據(jù)的遷移來進(jìn)行讀負(fù)載均衡.

因此,TANGO的主要開銷是數(shù)據(jù)遷移.為了驗證TANGO方案的遷移開銷,引入了一個基于IOPS的數(shù)據(jù)遷移方案進(jìn)行對比.基于IOPS的遷移方案將I/O壓力最高的卷中的熱數(shù)據(jù)遷移到當(dāng)前I/O壓力最小的卷.

表3 TANGO與基于IOPS策略的遷移數(shù)據(jù)量和次數(shù)對比(歸一化后的結(jié)果)Table 3 Migration times and data size(normalized)

測試結(jié)果如表3和圖12所示,表3展示了兩種遷移方案的遷移次數(shù)和遷移數(shù)據(jù)總量的對比,圖12展示了每次遷移耗時的分布情況.從表3可以觀察到,基于IOPS的遷移方案遷移次數(shù)比TANGO多了65%,遷移數(shù)據(jù)量也比TANGO多了65.5%.從圖12可以觀察到,基于IOPS的遷移方案中75%的遷移耗時100ms左右,因基于IOPS的方案從IOPS最高的存儲卷中遷移sstable時讀取較慢,這進(jìn)一步增加其遷移耗時.表3和圖12的結(jié)果表明,TANGO的讀負(fù)載遷移開銷較低.

圖12 TANGO與基于IOPS策略的單次遷移耗時對比Fig.12 Time for one migration

6 總 結(jié)

相比同容量的單個云存儲卷,組合使用多個小容量的單卷能夠獲得更好的性能.但是簡單地組合使用多個成員卷并不能充分發(fā)揮出多卷的最大性能,且現(xiàn)有的多卷負(fù)載均衡方案依然存在單個成員卷讀訪問熱度過高而使整體性能無法完全發(fā)揮的問題.為此,提出云存儲多卷負(fù)載均衡的LSM鍵值存儲系統(tǒng)TANGO.TANGO從讀和寫兩方面入手來調(diào)整負(fù)載在多卷之間的分布:在寫方面,通過改善LSM的合并操作來優(yōu)化初始數(shù)據(jù)布局,選擇鍵范圍重疊最小的成員卷寫入新生成的sstable;在讀方面,通過遷移少量熱點數(shù)據(jù)來進(jìn)一步均衡各成員卷間的負(fù)載.在亞馬遜云存儲卷上評估表明,相比相同存儲容量的單卷,采用了TANGO方案的同等容量的多卷可提高7倍左右的性能;相比采用其它方案的多卷,TANGO能提升20%以上的性能,且各成員卷間負(fù)載更加均衡.