Ceph云存儲中基于強化學習的QoS優化

李新鵬，王 勇，葉 苗

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

0 引 言

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

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

1 相關工作

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

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

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

2 問題描述

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

圖1 Ceph集群拓撲結構

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

圖2 小、大規模隨機讀性能的測試

另外，統計上述測試過程中各個OSD上的PG數量和磁盤使用率的關系，橫坐標表示OSD設備節點編號，第一縱坐標表示PG數量，第二縱坐標表示OSD節點磁盤使用率。結果如圖3所示。

圖3 OSD上的PG數目與數據量的正比關系

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

(1)

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

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

圖4 OSD的利用率對比

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

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

3 RL-CRUSH：基于Q-learning的數據分布算法

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

3.1 模型建立

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

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

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

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

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

(2)

(3)

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

(4)

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

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

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

定義2 動作集合A?？紤]到要在上述權重列表的基礎上，并結合CRUSH算法計算OSD的過程中要利用RL動態調整各個OSD的權重值，設計如下兩組動作集合

left,right分別表示狀態s向左、右移動；left_up,left_down,right_up,right_down分別表示狀態s向左、右移動后選擇的OSD節點的權重值向上、下按照步長調整權重。

(5)

圖5 RL-CRUSH算法流程

RL-CRUSH算法中Q值函數是狀態和行為的評價值，計算公式為

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

(6)

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

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

(7)

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

4 實驗設計與結果分析

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

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

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

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

4.1 實驗環境

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

4.2 實驗設計與結果分析

4.2.1 不同規模OSD，PG數量及PG數量標準差對比

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

圖6 不同規模OSD的PG數量分布對比

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

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

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

4.2.3 不同規模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中可以看出經過RL-CRUSH算法分布到各個OSD上的PG，在客戶端進行訪問操作時，都可以準確計算出PG在OSD上的映射位置，驗證了RL-CRUSH算法的有效性。

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

5 結束語

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