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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 問題分析

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

3.1 組合使用多個(gè)單卷性價(jià)比更高

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

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

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

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

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

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

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

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

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

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

圖3 鍵范圍1.4×1010～1.5×1010在各卷分布的局部放大,每一種灰度表示一個(gè)成員卷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個(gè)成員卷上的分布情況,每種灰度表示一個(gè)成員卷.從圖3可以看到:數(shù)據(jù)在各個(gè)存儲(chǔ)卷上的分布是不均勻的,有的灰度在單層中占得比例更大一些,表明某些鍵范圍更多地分布該灰度表示的卷中;相鄰層之間鍵范圍重疊的數(shù)據(jù)灰度相同,說明這些數(shù)據(jù)都被存儲(chǔ)在一個(gè)成員卷中.因此,若鍵范圍重疊較高的數(shù)據(jù)被頻繁讀取時(shí),大量的讀請(qǐng)求將會(huì)聚集在同一個(gè)成員卷上.因?yàn)槊總€(gè)存儲(chǔ)卷都存在帶寬和IOPS限制,熱數(shù)據(jù)較多的成員卷達(dá)到性能瓶頸后無法提供更高的性能,但是其它成員卷因?yàn)闊釘?shù)據(jù)較少,帶寬和IOPS反而得不到有效利用,從而使多卷的整體性能下降.

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

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

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

4 TANGO設(shè)計(jì)

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

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

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

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

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

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

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

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

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

(1)

其中,N(t-1,t]表示在時(shí)間間隔(t-1,t]內(nèi)第i個(gè)sstable被訪問的次數(shù),WRio為sstable的大小除以256KB所得的實(shí)際寫入的I/O請(qǐng)求數(shù)量(因?yàn)樵拼鎯?chǔ)卷會(huì)自動(dòng)地將小寫請(qǐng)求盡可能地聚合為256KB的大寫請(qǐng)求[26]),α為冷卻系數(shù),在0～1之間(默認(rèn)為0.5).

(2)

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

4.2 寫入決策

4.2.1 鍵范圍重疊情況判斷

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

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

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

4.2.2 選擇要寫入的成員卷

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

如圖5所示,展示了一個(gè)合并操作生成的sstable寫入時(shí)選擇成員卷的例子.圖5中,先對(duì)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 寫入時(shí)選擇成員卷的示意圖Fig.5 Write the sstable to a volume with the minimal key range overlap

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

4.3 負(fù)載遷移

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

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

5 實(shí)驗(yàn)與分析

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

5.1 測(cè)試環(huán)境

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

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

測(cè)試工具:本文采用常用的云服務(wù)器標(biāo)準(zhǔn)測(cè)試集YCSB[25]進(jìn)行的測(cè)試,它提供了一個(gè)框架和一組默認(rèn)的7個(gè)工作負(fù)載,用于評(píng)估鍵值存儲(chǔ)的性能.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分布.

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

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

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

5.2 多卷整體性能評(píng)估

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3 各成員卷性能

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

5.3.1 各成員卷的平均IOPS

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

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

5.3.2 各成員卷的實(shí)時(shí)IOPS

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

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

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

圖10 兩種讀請(qǐng)求比例下多卷方案各成員卷的實(shí)時(shí)IOPS

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

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

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

圖11 不同讀請(qǐng)求比例下各種方案的實(shí)時(shí)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的開銷可以分為兩個(gè)部分:1) 寫入決策改變合并操作中新生成sstable寫入位置帶來的開銷;2) 數(shù)據(jù)遷移的開銷.寫入決策的執(zhí)行可以減輕數(shù)據(jù)遷移的壓力,因?yàn)閿?shù)據(jù)被按照鍵范圍分布的更加均勻.

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

因?yàn)樵诙嗑泶鎯?chǔ)體中,熱點(diǎn)聚集于某個(gè)存儲(chǔ)卷中的多個(gè)sstable中,并且該卷的性能達(dá)到上限后限制了其余卷的訪問,因此需要進(jìn)行熱數(shù)據(jù)的遷移來進(jìn)行讀負(fù)載均衡.

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

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

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

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

6 總 結(jié)

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