一種OpenStack塊存儲調度算法

◆李靖民

?

一種OpenStack塊存儲調度算法

◆李靖民

（四川大學計算機學院 四川 610065）

在基于OpenStack的云平臺中，默認的塊存儲調度方法存在著無法給出確定的用戶服務水平目標（service level objective,SLO），以及一定的存儲資源浪費等問題。本文在降序首次適應 (First Fit Decreasing,FFD) 算法的基礎上提出一種塊存儲降序首次適應調度算法。該算法可以給出確定的SLO，從而提高云服務供應商的服務質量。仿真實驗結果表明，該算法與OpenStack默認的存儲調度算法相比，在滿足同樣的存儲調度請求的情況下有效地減少了所需的存儲節點，提高了資源利用率。

云存儲；OpenStack塊存儲；資源調度；存儲調度算法

0 引言

自從2006年云計算這一概念被Google提出以來，云計算技術飛速發展，云端所需要承載的數據量也越來越大，從而對云存儲技術提出了包括提高調度請求處理能力，提高資源利用率，提高包括性能與可用性等在內的云存儲服務的質量等一系列的要求。其中云服務供應商之間用于衡量服務質量的服務等級協議（service level Agreements,SLA）被描述為一個用戶服務水平目標（service level objective,SLO），SLO是SLA的具體表現，用于衡量可用性和性能。如果云服務供應商未能達到承諾的SLO，將會被要求賠償。這些要求極大地增加了存儲調度問題的復雜度，對調度方法也提出了更大的挑戰。

OpenStack Cinder組件作為OpenStack中的一部分負責云平臺存儲服務中的塊存儲服務，為塊存儲服務的管理與針對不同場景的應用提供了較好的解決方案。然而OpenStack Cinder目前的工作主要集中在開發不同的驅動，從而在虛擬機與具體的異構存儲設備之間進行“邏輯存儲卷”的抽象，保證存儲管理服務的高可用性等方向上。其在存儲調度上雖然保留了較高的可擴展性，但使用的默認算法仍然較為簡單。在資源的利用率，以及給出用戶SLO等方向上仍具有一定的缺陷。

塊存儲的調度技術對云平臺的可用性、效率、以及供應商的經濟效益都有著極大的影響。當前對云存儲的調度研究主要考慮的是資源的最大化應用，而針對塊存儲調度主要包括傳統的啟發式算法，遺傳算法等，也有為云存儲添加SLA的相關研究。在上述研究的基礎上，本文根據OpenStack Cinder存儲調度原理，結合適用于裝箱問題的降序首次適應算法，提出一種針對Cinder的塊存儲調度的算法。

1 一種OpenStack塊存儲調度算法

1.1 OpenStack Cinder塊存儲調度流程

OpenStack Cinder通過在虛擬機與存儲設備間引入“邏輯存儲卷”的抽象對用戶提供進行邏輯存儲卷管理的RESTful API。當用戶發出申請卷的請求后，Cinder會將用戶的請求放入消息隊列中，隨后Cinder的調度器cinder-scheduler從消息隊列中獲取對應的請求，對請求進行處理。調度器首先從所有的被管理的存儲節點中通過用戶自定義的filter選取符合要求的等待被調度的存儲節點，然后通過用戶指定的調度算法對用戶申請的卷進行導讀，OpenStack Cinder的基本調度流程如圖1所示。

1.2 OpenStack Cinder塊存儲調度流程

Cinder-Scheduler在如圖1所示的scheduler部分，有兩種內置的存儲調度算法：

（1） 隨機調度算法，經過用戶設置篩選條件的filter過濾后剩余的存儲節點中隨機選擇1個存儲節點放置卷的請求。該算法不是默認的算法，僅具備極低的實用價值。

圖1 OpenStack Cinder調度流程

（2） 根據剩余存儲容量調度算法，經過用戶設置篩選條件的filter過濾后，根據存儲節點剩余的存儲容量大小進行排序，優先將卷調度到剩余容量多的存儲節點上。

可以看到這兩種算法均無法保證較好的資源利用率，同時因為cinder的調度流程會逐個處理請求，所以在請求的處理性能上缺少優化，且無法給出用戶確定的SLO，比如讀寫性能，從而使云存儲供應商無法給出用戶可以量化的服務質量承諾。

1.3塊存儲降序首次適應算法

為了解決上述一系列問題，實現資源的盡可能大的利用，我們可以認將存儲調度的場景抽象成為一個裝箱問題，數學模型可以描述為：

約束條件為：

式(2)表示所有的卷請求所占用的資源量要少于所有存儲節點總共擁有的資源量，式(3)表示保證一個卷能且僅能被調度到一個存儲節點中。根據如上的裝箱問題的模型，本文參考FFD算法提出了如下的塊存儲降序最佳適應算法，算法具體流程如下：

輸入：存儲節點集合P，待調度卷集合V

（4） 重復調用流程（2）、（3），直到所有的卷請求都被處理完成；

2 仿真實驗與結果分析

為了評估塊存儲降序首次適應算法與OpenStack Cinder默認調度算法的性能與成效。本節將通過仿真實驗使用兩個性能指標來衡量兩種算法的性能：

（1）存儲節點利用率：整個存儲集群中使用的主機比上總的主機數。

（2）被使用的存儲節點的平均空間利用率：被使用的每臺存儲節點存儲空間利用率的平均值。

實驗平臺物理配置為：

表1 仿真平臺物理配置

參考Rackspace提出的標準商業硬件標準，在本文的實驗評估中，調度器考慮到兩個維度: 主機的容量和I/O吞吐量。每隔10秒調用一次本文提出的塊存儲首次適應算法。為簡化實驗，卷請求僅包括卷容量。卷容量是基于以下值隨機生成: 100GB、500GB、1000GB，調度請求的發起時間基于泊松分布λ=1請求/秒來分布的。每個實驗運行10次并且計算出指標的平均值。仿真參數如表2所示：

表2 仿真參數

圖2給出了在模擬程序中假設有10個容量為18T的存儲節點時，不同數量的調度請求以及不同的調度算法條件下的主機使用率，可以看到塊存儲降序首次適應算法與OpenStack Cinder的默認算法相比，在卷請求所消耗的空間沒有達到物理資源上限時，所占用的存儲節點更少。

圖2 存儲節點利用率

其次，圖3中給出了不同數量的調度請求以及不同的調度算法條件下的主機平均空間的利用率，可以看到塊存儲降序首次適應算法與OpenStack Cinder的默認算法相比，存儲節點的平均空間利用率更高。

圖3 存儲節點平均空間利用率

3 總結

本文為了提高OpenStack云平臺中存儲調度所影響的存儲資源利用率，并使云存儲供應商能夠給出確定的塊存儲服務的SLO指標，提出了一種基于裝箱問題的算法——塊存儲降序首次適應算法。該算法改在線算法為離線算法，同時按照一定的時間收集的該事件內所收到的卷請求，并對卷請求進行調度。該算法符合OpenStackd的調度原則，可以方便的集成到云平臺中。模擬實驗表明，相比OpenStack的默認調度算法，塊存儲降序首次適應算法在資源利用率方面有較大的改善，但該算法對于其他資源的SLO比如IO吞吐量和cpu占用率等的研究還不完善，應該在下一步工作中進行研究。

[1]Beloglazov A, Abawajy J, Buyya R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future generation computer systems, 2012.

[2]Xian Wu,Guanfeng Liu,Jiajie Xu. A QoS-Constrained Scheduling for Access Requests in Cloud Storage. 2015 IEEE 10th Conference on Industrial Electronics and Applications (ICIEA).

[3]Calheiros RN, Ranjan R, Rose CAFD, Buyya R. Cloudsim: A novel framework for modeling and simulation of cloud computing infrastructures and services. arXiv preprint arXiv:0903.2525, 2009.

[4]Lu K，Yahyapour Ｒ，Wieder P，et al.Qos-aware vm place-ment in multi-domain service level agreements scenarios［C］2013 IEEE Sixth International Conference on Cloud Computing.IEEE，2013.

[5]https://blog.rackspace.com/laying-cinder-block-volumes-in-openstack-part-2-solutions-design.

本課題得到國家重點研發計劃（2016yfb0800604，2016yfb0800605）和國家自然科學基金項目（61572334）的資助。