一種OpenStack塊存儲調(diào)度算法

◆李靖民

?

一種OpenStack塊存儲調(diào)度算法

◆李靖民

（四川大學(xué)計算機學(xué)院 四川 610065）

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

云存儲；OpenStack塊存儲；資源調(diào)度；存儲調(diào)度算法

0 引言

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

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

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

1 一種OpenStack塊存儲調(diào)度算法

1.1 OpenStack Cinder塊存儲調(diào)度流程

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

1.2 OpenStack Cinder塊存儲調(diào)度流程

Cinder-Scheduler在如圖1所示的scheduler部分，有兩種內(nèi)置的存儲調(diào)度算法：

（1） 隨機調(diào)度算法，經(jīng)過用戶設(shè)置篩選條件的filter過濾后剩余的存儲節(jié)點中隨機選擇1個存儲節(jié)點放置卷的請求。該算法不是默認(rèn)的算法，僅具備極低的實用價值。

圖1 OpenStack Cinder調(diào)度流程

（2） 根據(jù)剩余存儲容量調(diào)度算法，經(jīng)過用戶設(shè)置篩選條件的filter過濾后，根據(jù)存儲節(jié)點剩余的存儲容量大小進(jìn)行排序，優(yōu)先將卷調(diào)度到剩余容量多的存儲節(jié)點上。

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

1.3塊存儲降序首次適應(yīng)算法

為了解決上述一系列問題，實現(xiàn)資源的盡可能大的利用，我們可以認(rèn)將存儲調(diào)度的場景抽象成為一個裝箱問題，數(shù)學(xué)模型可以描述為：

約束條件為：

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

輸入：存儲節(jié)點集合P，待調(diào)度卷集合V

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

2 仿真實驗與結(jié)果分析

為了評估塊存儲降序首次適應(yīng)算法與OpenStack Cinder默認(rèn)調(diào)度算法的性能與成效。本節(jié)將通過仿真實驗使用兩個性能指標(biāo)來衡量兩種算法的性能：

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

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

實驗平臺物理配置為：

表1 仿真平臺物理配置

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

表2 仿真參數(shù)

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

圖2 存儲節(jié)點利用率

其次，圖3中給出了不同數(shù)量的調(diào)度請求以及不同的調(diào)度算法條件下的主機平均空間的利用率，可以看到塊存儲降序首次適應(yīng)算法與OpenStack Cinder的默認(rèn)算法相比，存儲節(jié)點的平均空間利用率更高。

圖3 存儲節(jié)點平均空間利用率

3 總結(jié)

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

[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.

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