Ceph云存儲中基于強化學習的QoS優(yōu)化

李新鵬，王 勇，葉 苗

(1.桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004；2.桂林電子科技大學 廣西云計算與復雜系統(tǒng)高校重點實驗室，廣西 桂林 541004；3.桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

0 引 言

隨著全球數(shù)據(jù)總量的迅速增長[1]，人類已經(jīng)進入大數(shù)據(jù)時代，為了可靠的存儲這些海量數(shù)據(jù)，云存儲應(yīng)運而生，其專注于解決海量數(shù)據(jù)的存儲和處理，且隨著云存儲的廣泛應(yīng)用，如何提高云存儲系統(tǒng)的服務(wù)質(zhì)量QoS(quality of service)性能已成為一個研究熱點[2,3]。

在設(shè)計一個云存儲系統(tǒng)時，面臨的首要問題就是如何將海量的數(shù)據(jù)分布在不同的存儲節(jié)點上，且盡可能分布均衡，解決這個問題的關(guān)鍵就是要設(shè)計一個好的數(shù)據(jù)分布策略，其對云存儲系統(tǒng)的QoS性能起著至關(guān)重要的作用。以一個具體的云存儲系統(tǒng)為基礎(chǔ)展開研究，Ceph作為最近幾年熱門研究的云存儲系統(tǒng)，不僅具有高擴展性、高性能和高可靠性的特點，而且實現(xiàn)了集群真正意義上的無中心節(jié)點。但是，Ceph的數(shù)據(jù)分布算法CRUSH(controlled replication under scalable hashing)存在數(shù)據(jù)在設(shè)備空間上分布的不均衡問題，從而影響分布式存儲系統(tǒng)的讀寫QoS性能。針對此問題，從算法的數(shù)據(jù)分布過程著手進行研究、實驗，得出放置組PG(placement group)在存儲節(jié)點OSD(object storage daemon)間分布不夠均衡，會造成用戶數(shù)據(jù)在各存儲設(shè)備上分布不均衡。在此基礎(chǔ)上，首先將PG在OSD上分布不均衡問題建模為分布的PG數(shù)量標準差的優(yōu)化問題；然后利用強化學習與環(huán)境不斷交互、反饋、自動決策及優(yōu)化目標的能力，建立強化學習模型，訓練調(diào)整PG在分布過程中的OSD權(quán)重，從而在不改變原有CRUSH算法邏輯的基礎(chǔ)上，使得數(shù)據(jù)在各設(shè)備上分布更加均衡，提高分布式存儲系統(tǒng)的資源利用率和QoS性能。

1 相關(guān)工作

如何提高云存儲系統(tǒng)的QoS性能已成為一個研究熱點。研究者從各個方面嘗試提高存儲系統(tǒng)的QoS性能，方法包括：使用多副本與糾刪碼方法提高系統(tǒng)的可靠性[4,5]；使用網(wǎng)絡(luò)編碼與數(shù)據(jù)索引方法降低系統(tǒng)的開銷[6,7]；以及使用數(shù)據(jù)分布與數(shù)據(jù)遷移方法提高分布式存儲系統(tǒng)負載的均衡性[8,9]。以下從數(shù)據(jù)分布的角度來介紹其是如何影響存儲系統(tǒng)的QoS性能，以及對當前的研究現(xiàn)狀、問題和改進方案展開描述。

分布式云存儲系統(tǒng)都有自己的數(shù)據(jù)分布算法， Niu SQ、Wu WG、Zhang XJ等在哈希算法的基礎(chǔ)上提出一種跳躍Hash算法[10]，利用二維矩陣來定位目標存儲節(jié)點，但是該算法通用性比較受限，在集群中節(jié)點失效的情況下，容易造成集群中同一行內(nèi)的其它節(jié)點負載過重，使集群負載不均衡。針對Ceph數(shù)分布算法CRUSH偽隨機性導致的數(shù)據(jù)分布不均衡問題，賀昱潔由CRUSH算法改進提出了一種B-CRUSH算法，該算法通過設(shè)計新的哈希算法、新的Bucket類型并設(shè)計一種自適應(yīng)模型來優(yōu)化數(shù)據(jù)分布不均衡的問題[11]，但是該算法對原有算法的邏輯改動較大，破壞了原有算法在集群擴容時數(shù)據(jù)遷移量小的優(yōu)點。穆彥良等提出一種Ceph存儲中基于溫度因子的CRUSH算法改進方案[12]，所提的算法通過計算用戶寫請求訪問集群中某個節(jié)點的頻率，動態(tài)增加該節(jié)點的溫度因子，利用溫度因子對原始CRUSH算法進行加權(quán)計算，得出更適合的存儲節(jié)點，但該算法的實驗數(shù)據(jù)不足以說明對多副本數(shù)據(jù)的分布具有同樣的效果。Ceph的新版本Luminous針對數(shù)據(jù)分布算法CRUSH存在的PG分布不夠均勻的問題，在集群上線之前，利用新增的balancer模塊對PG分布進行優(yōu)化，但優(yōu)化效果有限且需要手工配置參數(shù)。

針對Ceph中數(shù)據(jù)分布算法CRUSH在數(shù)據(jù)分布均衡性方面的不足，在深入研究CRUSH算法的基礎(chǔ)上，結(jié)合強化學習提出RL-CRUSH算法，該算法嘗試通過利用強化學習與環(huán)境不斷交互、反饋、自動決策及優(yōu)化目標的能力，改進原有CRUSH算法PG在OSD上的分布不均衡問題。

2 問題描述

在Ceph云存儲中，對象是數(shù)據(jù)存儲的基本單元。數(shù)據(jù)存儲的過程主要是通過兩次映射完成：首先客戶端按要求將用戶文件切分成一個個固定大小的對象，然后在對象之上添加一個邏輯層PG，對象都會被唯一映射到一個PG中，最后通過CRUSH算法按照設(shè)置好的副本規(guī)則把每一個PG映射到一組OSD節(jié)點中。分析上述過程可知，造成用戶數(shù)據(jù)在各個設(shè)備節(jié)點上分布不均衡的原因可能有兩方面：一方面是對象的數(shù)量在各PG中分布不均衡，另一方面是PG數(shù)量在各個OSD節(jié)點上分布不均衡。已有文獻說明對象可以被均衡地映射到各PG中，下面將通過實驗分析驗證PG數(shù)量在各個OSD間分布不均衡是造成集群中數(shù)據(jù)分布不均衡的原因，從而導致系統(tǒng)瓶頸的產(chǎn)生，影響集群整體QoS性能，本節(jié)將通過實驗驗證數(shù)據(jù)分布不均衡對集群性能和磁盤利用率的影響。搭建如圖1所示的Ceph集群拓撲結(jié)構(gòu)。

圖1 Ceph集群拓撲結(jié)構(gòu)

在上述搭建的Ceph集群中，利用FIO對Ceph云存儲系統(tǒng)進行小、大規(guī)模的讀寫性能測試。在小規(guī)模場景下，對5000個大小均為10 MB的對象進行隨機讀操作，此時，集群的吞吐率可以達到節(jié)點間最大網(wǎng)卡帶寬；在大規(guī)模場景下(其它測試參數(shù)與小規(guī)模測試保持一致)，對9000個大小均為10 MB的對象進行隨機讀操作，此時，與小規(guī)模場景下相比，集群的吞吐率下降了25%，如圖2所示。

圖2 小、大規(guī)模隨機讀性能的測試

另外，統(tǒng)計上述測試過程中各個OSD上的PG數(shù)量和磁盤使用率的關(guān)系，橫坐標表示OSD設(shè)備節(jié)點編號，第一縱坐標表示PG數(shù)量，第二縱坐標表示OSD節(jié)點磁盤使用率。結(jié)果如圖3所示。

圖3 OSD上的PG數(shù)目與數(shù)據(jù)量的正比關(guān)系

分析圖3可知，首先可以看出各個OSD上的PG數(shù)量分布很不均勻。例如，OSD4上的PG數(shù)目最多有119個，使用率為94.04%；而OSD2上的PG數(shù)目最少，只有88個，使用率為70.54%。根據(jù)Ceph官方文檔所推薦的經(jīng)驗式(1)所示

(1)

可以計算出上述搭建的Ceph集群的PG總數(shù)量應(yīng)設(shè)置為10*100/2=500，考慮到PG數(shù)目最好為2的整數(shù)次冪，故取值512。可以計算出，每個OSD節(jié)點經(jīng)過CRUSH算法分配后的平均PG總數(shù)量應(yīng)為512*2/10=102.4，從圖3中分析可知，與每個OSD的平均PG數(shù)量相比，平均值的變化范圍從-15%到18%，PG分布的標準差為8.85，可以看出，PG在OSD節(jié)點分布很不均勻。其次，圖3中的兩條折線基本重合，這表明OSD節(jié)點上的PG總數(shù)量和節(jié)點使用率兩者之間有直接關(guān)聯(lián)，基本成正比關(guān)系。因此可以將數(shù)據(jù)在集群中的分布不均衡問題轉(zhuǎn)化為PG在各OSD節(jié)點間的分布不均衡問題，也就是說，各個OSD節(jié)點間PG數(shù)量分布不均衡直接導致了用戶數(shù)據(jù)在各設(shè)備上分布不均衡。

為了進一步探究在進行大規(guī)模隨機讀測試時，集群吞吐量下降的原因，統(tǒng)計了PG數(shù)量最多的OSD4和PG數(shù)量最少的OSD2節(jié)點在測試期間的利用率，如圖4所示。

圖4 OSD的利用率對比

分析圖4可知，在大規(guī)模隨即讀測試的場景下，PG數(shù)量最多的OSD4節(jié)點的利用率一直處于超負荷狀態(tài)，說明該OSD負載過重，達到了瓶頸；而PG數(shù)量最少的OSD2節(jié)點的利用率一直處于較低的水平，說明該OSD節(jié)點未得到充分利用。可以看出，集群在讀寫過程中，數(shù)據(jù)量較多的OSD節(jié)點必然將承受過重的負載，很容易成為系統(tǒng)性能瓶；而另一方面對數(shù)據(jù)量少的OSD節(jié)點，又是一種資源的浪費，降低系統(tǒng)的QoS性能。

綜合上述實驗分析以及Ceph的存儲過程，可以得出PG數(shù)量在各個OSD間分布不均衡是造成集群中數(shù)據(jù)分布不均衡的原因，從而導致磁盤使用率不均衡、系統(tǒng)瓶頸的產(chǎn)生和降低集群吞吐量。

3 RL-CRUSH：基于Q-learning的數(shù)據(jù)分布算法

一個優(yōu)秀的數(shù)據(jù)分布算法應(yīng)當考慮的因素包括：時間復雜度、數(shù)據(jù)分布均衡性和數(shù)據(jù)遷移量。時間復雜度方面，在集群上線之前，通過CRUSH算法將PG分布在各個OSD上，此時，PG和OSD的映射關(guān)系就確定下來，只有在添加、刪除OSD節(jié)點的情況下，才需要重新計算PG在OSD上的映射，因此服務(wù)端對時間要求不嚴格，并且這種模式不會影響到客戶端訪問Ceph集群時計算OSD的過程，這就為使用強化學習來改進CRUSH算法奠定了基礎(chǔ)。數(shù)據(jù)遷移量方面，Ceph提供了多種選擇一個item的算法，這些算法統(tǒng)稱bucket算法，CRUSH默認使用的bucket算法為straw，straw算法可以做到新增和刪除OSD時，只有少量PG產(chǎn)生遷移，從而保證了數(shù)據(jù)遷移量較小。因此，在Ceph集群上線之初時，使用下面提出的RL-CRUSH算法通過利用強化學習與環(huán)境不斷交互、反饋、自動決策及優(yōu)化目標的能力，改進原有CRUSH算法PG在OSD上的分布不均衡問題，并保留了原有CRUSH算法數(shù)據(jù)遷移量小的優(yōu)勢。

3.1 模型建立

基于Q-learning的數(shù)據(jù)分布算法的模型建立包括兩部分：首先將PG數(shù)量在各個OSD間分布不均衡的問題規(guī)劃為標準差的優(yōu)化問題；然后將標準差優(yōu)化問題轉(zhuǎn)化為可以使用Q-learning算法解決的RL問題。

首先介紹第一個問題，將PG數(shù)量在各個OSD間分布不均衡的問題規(guī)劃為求較小標準差的問題。假設(shè)Ceph集群中共有：m個OSD存儲節(jié)點表示為：OSD_Number=(OSD0,OSD1,…,OSDm-1)，n個PG表示為：PG_Number=(PG0,PG1,…,PGn-1)，每個OSD節(jié)點最大的不同就是它們的容量，根據(jù)容量大小每個OSD有各自的權(quán)重，m個OSD的權(quán)重集合表示為：Weight=(W0,W1,…,Wm-1)。

CRUSH算法要解決的目標就是如何將n個PG映射到有各自權(quán)重的OSD上，為了便于理解后續(xù)問題的建模，這里簡單介紹一下CRUSH算法的流程。當集群中有了上述m個OSD、n個PG和m個OSD的權(quán)重集合，使用CRUSH算法為每一個PG選擇一組OSD的過程如下：

第一步：給定一個PGi，作為CRUSH_HASH的輸入，CRUSH_HASH(PGi,OSDir)得出一個隨機數(shù)。第二步：對于所有的OSD用它們各自的權(quán)重乘以O(shè)SDi對應(yīng)的隨機數(shù)，得到乘積。第三步：選出乘積最大的OSD節(jié)點，這個PG就會保存到這個OSD上。

在計算第i個PG的OSD映射位置時，當前每個OSD中的PG數(shù)量分別為

(2)

(3)

CRUSH_PG_Number=(t0,t1,…tm-1)

(4)

下面介紹第二個問題，將標準差優(yōu)化問題轉(zhuǎn)化為可以使用Q-learning算法解決的RL問題。

3.2 基于強化學習Q-learning的RL-CRUSH算法

Ceph集群中的bucket類型均指定為默認的straw類型，CRUSH默認使用的straw算法流程如下，首先給定一個PGi作為CRUSH_HASH的輸入,利用crush_hash32_rjenkins(PGi，OSDi，r)函數(shù)進行哈希得到一個隨機數(shù)；然后，對于所有的OSD,用每個OSD的隨機數(shù)乘以其對應(yīng)的權(quán)重，得到乘積并進行比較，選出乘積最大的OSD，最終得出PGi映射到該OSD上，上述兩個過程均會導致PG在OSD上的分布不均衡。接著依據(jù)3.1的標準差問題模型設(shè)計Q-learning算法，從而改進CRUSH算法的PG在OSD上的分布不均衡問題，命名改進的算法為RL-CRUSH。結(jié)合上述所提的PG數(shù)量在各個OSD間分布均衡問題，設(shè)計Q-learning算法模型的狀態(tài)空間、動作集合和收益函數(shù)，可分別將其定義如下。

定義2 動作集合A。考慮到要在上述權(quán)重列表的基礎(chǔ)上，并結(jié)合CRUSH算法計算OSD的過程中要利用RL動態(tài)調(diào)整各個OSD的權(quán)重值，設(shè)計如下兩組動作集合

left,right分別表示狀態(tài)s向左、右移動；left_up,left_down,right_up,right_down分別表示狀態(tài)s向左、右移動后選擇的OSD節(jié)點的權(quán)重值向上、下按照步長調(diào)整權(quán)重。

(5)

圖5 RL-CRUSH算法流程

RL-CRUSH算法中Q值函數(shù)是狀態(tài)和行為的評價值，計算公式為

Q(st,at)=R(st,at)+gmax{(st+1,at+1)}

(6)

其中，st和at表示時刻t的下一個狀態(tài)和行為，衰減因子g是滿足0

Qt+1(st,at)=(1-g)Qt(st,at)+g[R(st,at)+gmaxQ(st+1,at+1)]

(7)

有了Q值就可以進行學習，然后根據(jù)Q值來選取能夠獲得最大收益的動作。

4 實驗設(shè)計與結(jié)果分析

為全面評估提出的基于Q-learning的RL-CRUSH算法的有效性，以下將從3個方面進行詳細的仿真實驗。

(1)在不同規(guī)模OSD的情況下，分別對比RL-CRUSH算法及CURSH算法的PG數(shù)量分布、PG數(shù)量標準差。

(2)在不同規(guī)模OSD的情況下，分別對比RL-CRUSH算法及CURSH算法的PG分布訓練時間、PG計算時間。

(3)在雙副本、不同規(guī)模OSD的情況下，模擬客戶端讀取過程中，計算PG在OSD上的映射位置，驗證同一個PG映射的OSD集合是否固定。

4.1 實驗環(huán)境

為了驗證本文設(shè)計的數(shù)據(jù)分布方法的性能和效果，在配置為Windows 10 64位操作系統(tǒng)的Intel Core i3-2330M @2.20 GHz、8 GB內(nèi)存的PC機上進行仿真實驗。使用Python 語言編寫算法RL-CRUSH及CRUSH算法中PG到OSD映射機制的功能，并利用PyCharm工具運行算法及對實驗結(jié)果進行收集、分析。

4.2 實驗設(shè)計與結(jié)果分析

4.2.1 不同規(guī)模OSD，PG數(shù)量及PG數(shù)量標準差對比

圖6是在3副本的場景下，執(zhí)行CRUSH算法、RL-CRUSH算法分別計算5、10、15個OSD上的PG分布，圖6(a)、圖6(b)、圖6(c)每個OSD上的平均PG數(shù)量分別應(yīng)該為153.6、153.6和102.4。可以看出CRUSH算法PG在各個OSD上的分布很不均勻，圖6(a)、圖6(b)、圖6(c)各OSD上的PG數(shù)目相對平均值的變化范圍分別為：-6.6%到5.4%、-19.6%到17.4%、-14.4%到11.6%，PG分布的標準差分別為4.17、9.23、6.1；分析RL-CRUSH算法的PG分布結(jié)果，從圖6(a)、圖6(b)、圖6(c)計算可得各OSD上的PG數(shù)目相對平均值的變化范圍分別為：-1.4%到1.6%、-2.6%到2.4%、-1.4%到3.6%，PG分布的標準差分別為1.02、2、1.5。

圖6 不同規(guī)模OSD的PG數(shù)量分布對比

4.2.2 不同規(guī)模OSD，PG分布時間及計算時間對比

表1是在3副本、不同數(shù)量的OSD的場景下，分別執(zhí)行CRUSH算法、RL-CRUSH算法時，PG在OSD上的分布訓練時間以及客戶端讀取Ceph集群時，計算PG在OSD節(jié)點映射位置的平均時間。CRUSH算法沒有訓練過程，這里只統(tǒng)計RL-CRUSH算法的分布訓練時間。從表中可以得出相比CRUSH算法，提出的RL-CRUSH算法由于PG在OSD分布過程中加入了強化學習訓練的過程，導致PG在OSD上分布的訓練時間較長。PG在OSD節(jié)點的分布時間和均勻性，后者對Ceph集群使用的作用更為重要。原因有兩點：第一，PG在OSD上的分布操作，是在創(chuàng)建Ceph集群時一次性完成的，此時，集群中還沒有存儲對象，對PG分布進行優(yōu)化收益最大，且對創(chuàng)建集群時間要求不嚴格(借鑒Ceph的新版本Luminous新增的balancer模塊對PG分布進行優(yōu)化)；第二，當客戶端讀取Ceph集群時，RL-CRUSH算法收斂后，保存最佳OSD權(quán)重值，從而不影響計算PG在OSD節(jié)點映射位置的時間，從表中可以看出這一點，CRUSH算法和提出的算法讀取時計算一個PG映射位置的平均時間都是0.9 ms。

表1 OSD上的PG分布訓練時間、計算時間比較

4.2.3 不同規(guī)模OSD，計算PG的OSD映射位置

圖7(a)、圖7(b)是在2副本的場景下，模擬客戶端讀取Ceph集群時，RL-CRUSH算法計算PG在OSD上映射位置的過程。分別在5個OSD、10個OSD的情況下，隨機選取10個PG進行計算OSD映射位置的尋址操作，例如，圖7(a)中，副本1和副本2的散點分別表示PG.6的第一、第二個副本存在OSD.0、OSD.2；尋址副本1和尋址副本2的散點分別表示客戶端訪問Ceph集群時，計算PG.6兩個副本的映射位置為OSD.0、OSD.2。從圖7中可以看出經(jīng)過RL-CRUSH算法分布到各個OSD上的PG，在客戶端進行訪問操作時，都可以準確計算出PG在OSD上的映射位置，驗證了RL-CRUSH算法的有效性。

圖7 不同規(guī)模OSD、2副本下，計算PG的OSD位置

5 結(jié)束語

針對CRUSH算法存在PG映射到OSD分布不均勻的問題，利用強化學習改進CRUSH算法，提出RL-CRUSH算法來優(yōu)化PG分布不均勻的問題。該算法首先將PG數(shù)量在各個OSD間分布不均衡的問題規(guī)劃為PG數(shù)量標準差的優(yōu)化問題，建立問題模型；然后依據(jù)問題建立強化學習模型，包括狀態(tài)空間、動作空間和獎勵函數(shù)的設(shè)計；最后依據(jù)上述設(shè)計的RL模型，使用Q-learning算法來解決問題。通過實驗與結(jié)果分析可知，提出的RL-CRUSH算法在不影響客戶端訪問Ceph集群時，計算PG到OSD映射時間的前提下，較好解決了PG分布不均勻的問題，使得PG可以近似均勻的分配到各個OSD上，消除了數(shù)據(jù)分布不均衡帶來的系統(tǒng)瓶頸，提高OSD磁盤使用率和云存儲負載均衡QoS性能。