◆李靖民

?

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

◆李靖民

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

約束條件為：

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

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

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

2 仿真實(shí)驗(yàn)與結(jié)果分析

為了評(píng)估塊存儲(chǔ)降序首次適應(yīng)算法與OpenStack Cinder默認(rèn)調(diào)度算法的性能與成效。本節(jié)將通過(guò)仿真實(shí)驗(yàn)使用兩個(gè)性能指標(biāo)來(lái)衡量?jī)煞N算法的性能：

（1）存儲(chǔ)節(jié)點(diǎn)利用率：整個(gè)存儲(chǔ)集群中使用的主機(jī)比上總的主機(jī)數(shù)。

（2）被使用的存儲(chǔ)節(jié)點(diǎn)的平均空間利用率：被使用的每臺(tái)存儲(chǔ)節(jié)點(diǎn)存儲(chǔ)空間利用率的平均值。

實(shí)驗(yàn)平臺(tái)物理配置為：

表1 仿真平臺(tái)物理配置

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

表2 仿真參數(shù)

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

圖2 存儲(chǔ)節(jié)點(diǎn)利用率

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

圖3 存儲(chǔ)節(jié)點(diǎn)平均空間利用率

3 總結(jié)

本文為了提高OpenStack云平臺(tái)中存儲(chǔ)調(diào)度所影響的存儲(chǔ)資源利用率，并使云存儲(chǔ)供應(yīng)商能夠給出確定的塊存儲(chǔ)服務(wù)的SLO指標(biāo)，提出了一種基于裝箱問(wèn)題的算法——塊存儲(chǔ)降序首次適應(yīng)算法。該算法改在線算法為離線算法，同時(shí)按照一定的時(shí)間收集的該事件內(nèi)所收到的卷請(qǐng)求，并對(duì)卷請(qǐng)求進(jìn)行調(diào)度。該算法符合OpenStackd的調(diào)度原則，可以方便的集成到云平臺(tái)中。模擬實(shí)驗(yàn)表明，相比OpenStack的默認(rèn)調(diào)度算法，塊存儲(chǔ)降序首次適應(yīng)算法在資源利用率方面有較大的改善，但該算法對(duì)于其他資源的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.

本課題得到國(guó)家重點(diǎn)研發(fā)計(jì)劃（2016yfb0800604，2016yfb0800605）和國(guó)家自然科學(xué)基金項(xiàng)目（61572334）的資助。