云存儲的多維離線調(diào)度算法

王 勇 田 博 王 端

(桂林電子科技大學(xué)計算機科學(xué)與工程學(xué)院 廣西 桂林 541004)

云存儲的多維離線調(diào)度算法

王 勇 田 博 王 端

(桂林電子科技大學(xué)計算機科學(xué)與工程學(xué)院 廣西 桂林 541004)

由于使用云塊存儲系統(tǒng)是OpenStack的Cinder，且Cinder默認使用的調(diào)度算法只是從存儲節(jié)點的可用空間容量方面考慮，所以它不能夠有效地保障卷請求的IOPS。針對這種情況，綜合考慮存儲節(jié)點的可用空間容量和I/O吞吐量兩個方面，同時基于APX-hard 多維向量集裝箱(Vector Bin Packing)算法，提出了一個多維離線調(diào)度算法(MVCFD)。實驗結(jié)果表明，該算法與現(xiàn)有的塊存儲調(diào)度算法相比，在卷請求的空間與IOPS兩方面都滿足的情況下，還能夠有效地減少活動主機的數(shù)量。

云塊存儲 OpenStack 資源調(diào)度 矢量裝箱

0 引 言

由于云計算基礎(chǔ)設(shè)施(也可稱為基礎(chǔ)設(shè)施即服務(wù)(IaaS))，允許高彈性，具有高可用性，降低硬件和運營成本的特性，所以云計算得到快速發(fā)展。云計算可以存儲和處理由租戶所產(chǎn)生的大量的數(shù)據(jù)，因此被用于許多行業(yè)[1]。云存儲主要有三類: (a) 臨時存儲：數(shù)據(jù)存儲在虛擬機上，虛擬機重啟或釋放后丟失；(b) 塊存儲：數(shù)據(jù)被存儲在持久的塊層次的存儲空間(即卷)，它能夠被掛載或卸載到生命周期內(nèi)的虛擬機，它獨立于虛擬機本身；(c)對象存儲：對象和文件被分散寫入到數(shù)據(jù)中心中的服務(wù)器的多個磁盤驅(qū)動器，并且可以從所有的云服務(wù)中服務(wù)API來被訪問。

由于部署在云端的應(yīng)用程序和數(shù)據(jù)庫隨著時間的推移，最終需要增加存儲容量。添加物理存儲或升級到一個具有更高容量的存儲系統(tǒng)費用很高，并且不能伸縮。云的塊存儲為托管在云上的應(yīng)用程序提供了一個可靠的、高性能、按需分配的存儲，此外，它可以支持無縫的饑餓資源工作負載，并且對空間擴展的請求可以快速處理，例如卷擴展要求。然而，最大限度地利用資源，最大限度地減少能源消耗和維護承租人和云服務(wù)提供商之間的服務(wù)等級協(xié)議(SLA)的塊存儲調(diào)度請求的問題還沒有得到很好的研究。這個問題變得更加重要，因為新的開源的IaaS解決方案，如OpenStack的[2]，已經(jīng)超過500家公司部署。

目前主要的研究集中在了數(shù)據(jù)中心最優(yōu)的虛擬機放置[3]，或能量感知的虛擬機分配[4]。最近的一些研究都集中于在虛擬機放置過程加入SLA[5]，或優(yōu)化工作完成時間在大數(shù)據(jù)集群[6]，也有研究工作在云存儲中加入了SLA[7]。本文提出了一個調(diào)度算法，可以為卷請求提供高效的和快速的分配，并盡量減少云存儲基礎(chǔ)設(shè)施中后端存儲節(jié)點的數(shù)量。更具體而言，本文設(shè)計了一種基于多維向量集裝箱multi-dimensional Vector Bin Packing(VBPd)的調(diào)度器，其中多維指的是調(diào)度程序可以使用的資源維度，如容量、I/O吞吐量等。該問題等價于給定箱尺寸Rd和要裝的物品并將物品裝入箱中，最后使所使用的箱子數(shù)最少。這樣做是為了最大限度處理卷請求，并最小化云存儲系統(tǒng)后端存儲節(jié)點的數(shù)量。當(dāng)問題是APX-hard時[8]，這意味著不存在漸進多項式時間近似方案(PTAS)的問題。一系列的啟發(fā)式可以被運用并解決該問題[9]?？墒牵@些啟發(fā)式將卷的請求大小設(shè)為一個固定值，這與卷請求的實際情況完全不同。同時，據(jù)我們的了解，這種想法很少被運用在云存儲系統(tǒng)中。所以，我們的工作目標是：

(1) 開發(fā)一個用于塊存儲，可以集成在云基礎(chǔ)設(shè)施平臺中，模塊化的調(diào)度框架；

(2) 調(diào)度卷請求到云塊存儲系統(tǒng)后端存儲節(jié)點時考慮多維度屬性，包括可用空間和I/O吞吐量；

(3) 管理塊存儲基礎(chǔ)設(shè)施的利用率、能源和卷I/O性能。

1 云塊存儲

1.1 塊存儲SLA背景

塊存儲的目的是為各種云應(yīng)用提供可靠的、高性能、按需和持久性的存儲容量。在一般情況下，存儲容量可以以虛擬化邏輯卷的形式來被訪問。塊存儲系統(tǒng)管理這些卷的創(chuàng)建，掛載和卸載到通常由計算服務(wù)提供的虛擬機上。若要在云基礎(chǔ)架構(gòu)上部署塊存儲服務(wù)則需要建立一個專門的存儲服務(wù)器集群。一個存儲節(jié)點或后端系統(tǒng)經(jīng)常由許多的硬盤驅(qū)動器以RAID的形式來提供冗余和大規(guī)模的存儲容量。在對數(shù)據(jù)存儲速率、故障率、環(huán)保等方面要求高的情況下，固態(tài)驅(qū)動器(SSD)或定制的SSD[10]可用來滿足I/O性能等方面的要求。存儲服務(wù)可以經(jīng)由預(yù)定義服務(wù)API訪問，使得云端租戶能夠按需發(fā)送請求以創(chuàng)建、連接、分離或遷移卷。

在云中的數(shù)據(jù)塊存儲服務(wù)還需要滿足客戶的需求,這是一個法律文件保證，例如SLA(Service-LevelAgreement)。SLA服務(wù)等級協(xié)議是指一定開銷下為保障服務(wù)的性能和可靠性，服務(wù)提供商與用戶相互認可的一個協(xié)定。在SLA中各服務(wù)等級被描述為一個服務(wù)等級目標(SLO)，它是SLA具體的表現(xiàn)，如可用性、吞吐量、響應(yīng)時間、頻率和延遲等。對于塊存儲提供商，未能達到SLA的指標，應(yīng)進行相應(yīng)處罰。在云存儲域，通常有兩種SLOs：可用性SLO和SLO性能?？捎眯許LO指定的云服務(wù)必須成功地在合同期內(nèi)或由提供者定義的時段內(nèi)訪問的級別。例如,在亞馬遜的彈性塊存儲(EBS)[11],有SLA保證每月至少99.9%正常運行時間性能。同樣，其他云存儲提供商都在提供可用性SLO設(shè)定非常高的標準。性能SLO限制了存儲平臺上數(shù)據(jù)轉(zhuǎn)換速度的最低界限。

塊存儲的性能SLO最常用的單位是每秒輸入/輸出操作數(shù)(IOPS)。與可用性SLO相比,性能SLO幾乎從來沒有被任何云塊存儲提供商所揭露。在某些情況下，云存儲供應(yīng)商可能會聲稱他們的服務(wù)能夠提供XIOPS/GB的一致的基準，而不在其SLA透露具體的SLO。

1.2OpenStackCinder

作為最流行的開源云基礎(chǔ)設(shè)施框架之一，OpenStack是開發(fā)商和云計算技術(shù)專家針對公有云和私有云的特性合作創(chuàng)建的，并且目前有超過200家公司加入OpenStack的開發(fā)。OpenStack的目的是為各種云提供一個易于搭建、擴展和功能豐富的云基礎(chǔ)設(shè)施解決方案，而OpenStack是由包含許多組件的項目/服務(wù)構(gòu)成的云基礎(chǔ)設(shè)施解決方案[2]。

在OpenStack中，塊存儲的項目名為Cinder。其系統(tǒng)架構(gòu)如圖1所示。Cinder-Scheduler響應(yīng)客戶端發(fā)出的請求然后選擇合適的后端存儲節(jié)點并在該節(jié)點上創(chuàng)建卷。

圖2顯示了在OpenStack中的調(diào)度過程。主要分兩個步驟：(1)過濾：當(dāng)Cinder過濾調(diào)度程序接收邏輯卷的請求時，通過濾器的策略來確定哪些主機能夠滿足卷請求，并創(chuàng)建符合條件的主機列表，在Cinder中默認的過濾策略是最大可用空間過濾；(2)權(quán)重排序：根據(jù)過濾后的主機列表計算每個主機的權(quán)重，然后根據(jù)權(quán)重策略選擇一個最合適的主機，在Cinder中默認的權(quán)重策略是最大可用空間權(quán)重。

圖2 在Cinder 調(diào)度的主機過濾與計算主機權(quán)重排序

從Cinder的系統(tǒng)架構(gòu)與調(diào)度過程來看，在塊存儲服務(wù)的資源管理中，Cinder調(diào)度起著至關(guān)重要的作用。然而，在當(dāng)前的調(diào)度方法中，有一些局限性。首先，默認基于空間的調(diào)度算法尚未在I/O性能方面進行評估。例如，調(diào)度程序不知道I/O性能這種狀態(tài)，因此可能安排一個能夠滿足卷請求空間大小的實體上,但是在I/O性能方面已經(jīng)超載。而且，目前的方法沒有考慮其中在同一時段到達的卷請求的競爭情況。因此，如果卷請求到達速率較高，則可能導(dǎo)致次優(yōu)配置、高能耗和因此產(chǎn)生更高的運營費用。

2 優(yōu)化問題及解決方案

資源分配的目標是映射卷請求到若干個存儲節(jié)點，其中每一個卷表示一個包含若干個維度的元組?？紤]將每個存儲實體視為一個箱子，其維度(大小)，作為它的屬性，以及目標是在單個存儲實體的各個屬性的允許范圍內(nèi)，最大化單個實體的空間利用率并減少必須用于服務(wù)卷請求的實體總數(shù)。這個問題是NP完全問題[12]，可以通過線性規(guī)劃或啟發(fā)式求解。

2.1 卷放置的數(shù)學(xué)模型

由于卷的放置問題屬于典型的裝箱問題，則其數(shù)學(xué)模型[13]可以描述為：數(shù)據(jù)中心物理機集合可以表示為P=(p1,p2,…,pn)，卷請求集合V=(v1,v2,…,vm)，其中n和m表示為數(shù)據(jù)中心中存儲節(jié)點的數(shù)量和卷請求的數(shù)量。假定一個存儲節(jié)點共有(1,2,3,…,d)種資源(如存儲空間，IOPS等)，則單個存儲節(jié)點可以表示為pi=(si1,si2,…,sid),s表示第i存儲節(jié)點上某種資源的提供量，同理，單個卷請求可以表示為vj=(rj1,rj2,rj3,…,rjd)，r表示第j個卷請求對某種資源的需求量。目標函數(shù)為了所使用的存儲節(jié)點數(shù)最少可描述為：

(1)

約束條件為：

i∈(1,2,…,n) j∈(1,2,…,m)

(2)

(3)

(4)

(5)

其中，約束式(2)保證了卷請求的所有資源需求都不會超過存儲節(jié)點的上限；約束式(3)保證了一個卷只能唯一的放置在一個存儲節(jié)點上；式(4)和式(5)是決策變量。

2.2 基于CF算法的多維離線調(diào)度算法

求解裝箱問題的算法有很多種，常見的有啟發(fā)式算法，如FFD(First Fit Decreasing)、BFD(Best Fit Decreasing)等；元啟發(fā)式算法，如遺傳算法[14]、蟻群算法[15]等。文獻[16]提出了一種解決一維裝箱問題的新的近似算法——交叉裝填算法(CF 算法)，并證明了該算法達到裝箱問題最好的近似值3/2，同時算法的復(fù)雜度也能達到非線性最優(yōu)，特別，當(dāng)物件的大小按非增性質(zhì)預(yù)先排序后，CF算法的復(fù)雜度是線性的，因此，可以將該算法應(yīng)用到卷的放置。因為本文主要從存儲節(jié)點的空間大小與IOPS這兩個維度考慮卷的放置，所以在CF算法的基礎(chǔ)上提出了一個改進的多維離線交叉裝填算法MVCFD。算法具體流程如下：

輸入：物理主機集合P，卷集合V。

輸出：使用的物理主機數(shù)目Pused。

第一步：將V=(v1,v2,…,vm)按存儲空間需求大小進行非增排序，不妨設(shè)排序后的結(jié)果為r11≥r21≥…≥rm1，這里下標1指的是存儲空間資源。

第二步：首先檢測是否有存儲節(jié)點被使用，如果有則首先從已使用存儲節(jié)點選出能夠滿足卷集合中左端第一個卷請求v1需求的并且可用空間最大的節(jié)點，否則開啟一臺新的存儲節(jié)點。選出存儲節(jié)點Pi其中i∈(1,2,…,n),則把v1放入Pi中，然后從卷列表的最右端開始放置卷到Pi中直到放入卷vk，如果Pi再放置vk-1就會有卷請求的某種資源超出存儲節(jié)點的資源上限，此時有r11+rm1+r(m-1)1+…+rk1≤si1且r12+rm2+r(m-1)2+…+rk2≤si2，其中這里的下標2是指IOPS這種資源。這時未被處理的卷集合為V=(v2,v3,…,vk-1)。

第三步：采用上述處理算法處理未完成的卷集合，直到所有卷請求都被處理結(jié)束。

第四步：輸出Pused。

3 仿真實驗與性能分析

本文實驗將上一節(jié)提出的算法與OpenStack中cinder默認的調(diào)度算法和文獻[17]提出的MVBFD算法進行云存儲性能分析。由于受評估系統(tǒng)是一個IaaS,在現(xiàn)實條件下重復(fù)實驗將消耗大量的時間與費用。因此，本文用Java開發(fā)了一個模擬器，來模擬一個存儲集群，進而在這個模擬器上對要對比的算法進行重復(fù)的仿真實驗。

3.1 性能指標

本文使用三種指標來評估提出的調(diào)度算法和要對比的調(diào)度算法的性能。

1) 主機利用率：整個存儲集群中處于使用中的主機數(shù)比上總的主機數(shù)。

2) 已使用主機平均空間利用率：處于使用中的每臺主機空間利用率的和比上已使用的主機數(shù)。

3) 已使用主機平均可分配IOPS：處于使用中的每臺主機可用IOPS的和比上已使用的主機數(shù)。

3.2 實驗裝置

該模擬器的部署方案是根據(jù)Rackspace公司提出的現(xiàn)在商用的一般硬件標準[18]。I/O性能方面按照IO塊大小8K，70%讀取和30%寫入的標準要求來計算，那么一個硬盤驅(qū)動器能夠?qū)崿F(xiàn)175IOPS，并使用RAID計算器[19]發(fā)現(xiàn)每個存儲主機最大的I/O吞吐量是8800IOPS。存儲硬件特性在表1中描述。在本文的實驗評估中，調(diào)度器考慮到兩個維度：主機的容量和I/O吞吐量。該MVCFD算法每隔10秒被啟用一次。卷請求包括三個方面：卷容量，I/O性能SLO和持續(xù)時間。卷容量是基于以下值隨機生成：100、500、1 000GB。該卷的請求到達時間是基于泊松分布λ=1請求/秒來分布的。每個卷將運行2小時、4小時和6小時的概率分別為25%、50%和25%。每個實驗已運行10次，并且計算出指標的平均值。對單個存儲節(jié)點的配置信息在表1中，對模擬參數(shù)的完整列表列于表2中。本文實驗設(shè)置的集群大小為10臺存儲節(jié)點。

表1 存儲主機硬件配置

表2 仿真參數(shù)設(shè)置

3.3 實驗結(jié)果

首先，圖3給出了在10臺存儲節(jié)點時，不同卷請求以及不同的調(diào)度算法的條件下主機的使用率。同時，圖3也表明了MVCFD與OpenStack中默認的最大可用空間調(diào)度算法與文獻[17]提出的MVBFD算法相比，在卷請求需求沒有達到物理資源上限時所使用的主機更少。

圖3 10臺存儲節(jié)點主機使用率

其次，圖4給出了在10臺存儲節(jié)點時，不同卷請求以及不同的調(diào)度算法的條件下已使用主機平均空間利用率。同時，圖4也表明了MVCFD與OpenStack中默認的最大可用空間調(diào)度算法與文獻[17]提出的MVBFD算法相比，在卷請求需求沒有達到物理資源上限時，MVCFD的已使用空間平均利用率更高。

圖4 10臺存儲節(jié)點已使用主機平均空間利用率

最后，圖5所示，在10臺存儲節(jié)點時不同卷請求以及不同的調(diào)度算法的條件下已使用主機平均空間利用率。同時，圖5也表明了MVCFD與OpenStack中默認的最大可用空間調(diào)度算法與文獻[17]提出的MVBFD算法相比，在卷請求需求沒有達到物理資源上限時，MVCFD的已使用空間平均可用IOPS的值最小。通過圖3與圖5可知MVCFD使用更少的主機滿足更多的卷請求，而每個存儲節(jié)點的IOPS值是固定的，所以MVCFD在相同的卷請求數(shù)時平均可用IOPS最小。

圖5 10臺存儲節(jié)點已使用主機平均可用IOPS

4 結(jié) 語

本文闡述了卷分配問題是一個多維VBP和基于活動的存儲實體的數(shù)量最優(yōu)化的問題。為了解決這個問題本文提出了MVCFD調(diào)度算法。所提出的調(diào)度算法考慮多種資源，對卷請求隊列進行預(yù)排序，應(yīng)用SLO約束每個維度，并選擇適當(dāng)?shù)拇鎯?jié)點。本文的實驗設(shè)計是基于OpenStack的原則，以便它可以很容易地集成到大多數(shù)云平臺。模擬實驗的結(jié)果表明，MVCFD算法對I/O吞吐量，可擴展性和已使用主機數(shù)量的相對于OpenStack的默認調(diào)度算法與文獻[17]所提出的算法都有較大改善以及該MVCFD算法揭示了能源和降低運營成本的進一步潛力，但是本文所提出的算法在卷請求排序的方法還存在缺陷，下一步工作準備重點研究卷請求排序。

[1]GhoshR,PapapanagiotouI,BoloorK.Asurveyonresearchinitiativesforhealthcareclouds[J].CloudComputingApplicationsforQualityHealthCareDelivery, 2014: 1-18.

[2]Openstack[OL].http://www.openstack.org.

[3]XuJ,FortesJAB.Multi-objectivevirtualmachineplacementinvirtualizeddatacenterenvironments[C]//GreenComputingandCommunications(GreenCom), 2010IEEE/ACMInt'lConferenceon&Int'lConferenceonCyber,PhysicalandSocialComputing(CPSCom).IEEE, 2010: 179-188.

[4]BeloglazovA,AbawajyJ,BuyyaR.Energy-awareresourceallocationheuristicsforefficientmanagementofdatacentersforcloudcomputing[J].Futuregenerationcomputersystems, 2012, 28(5): 755-768.

[5]LuK,YahyapourR,WiederP,etal.Qos-awarevmplacementinmulti-domainservicelevelagreementsscenarios[C]//2013IEEESixthInternationalConferenceonCloudComputing.IEEE, 2013: 661-668.

[6]SchwarzkopfM,KonwinskiA,Abd-El-MalekM,etal.Omega:flexible,scalableschedulersforlargecomputeclusters[C]//Proceedingsofthe8thACMEuropeanConferenceonComputerSystems.ACM, 2013: 351-364.

[7]YaoZ,PapapanagiotouI,CallawayRD.SLA-awareresourceschedulingforcloudstorage[C]//IEEE,InternationalConferenceonCloudNETWORKING.IEEE, 2014:14-19.

[8]WoegingerGJ.ThereisnoasymptoticPTASfortwo-dimensionalvectorpacking[J].InformationProcessingLetters, 1997, 64(6): 293-297.

[9]PanigrahyR,TalwarK,UyedaL,etal.HeuristicsforVectorBinPacking[Z].MicrosoftResearch,Tech.Rep., 2011.

[10]OuyangJ,LinS,JiangS,etal.SDF:software-definedflashforweb-scaleinternetstoragesystems[J].ACMSIGPLANNotices.ACM, 2014, 49(4): 471-484.

[11]Amazonelasticblockstore[OL].http://aws.amazon.com/ebs/.

[12]GareyMR,JohnsonDS.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[M].W.H.Freeman, 1979.

[13] 李靜，吳耀華，肖際偉．一種求解裝箱問題的混合算法[J]．物流科技,2009,31(12):29-31.

[14] 李進超，陳靜怡，吳杰，等．基于改進分組遺傳算法的虛擬機放置研究[J]．計算機工程與設(shè)計，2012，33(5):2053-2056.

[15]GaoY,GuanH,QiZ,etal.Amulti-objectiveantcolonysystemalgorithmforvirtualmachineplacementincloudcomputing[J].JournalofComputerandSystemSciences, 2013, 79(8): 1230-1242.

[16] 孫春玲, 陳智斌, 李建平. 裝箱問題的一種新的近似算法[J]. 云南大學(xué)學(xué)報: 自然科學(xué)版, 2004, 26(5): 392-396.

[17]YaoZ,PapapanagiotouI,CallawayRD.Multi-DimensionalSchedulinginCloudStorageSystems[C]//InternationalCommunicationsConference(ICC). 2015.

[18]LevensteinK.Configuringopenstackblockstorage[OL].https://www.rackspace.com/blog/laying-cinderblock-volumes-in-openstack-part-2-solutions-design/.

[19]Raidperformancecalculator[OL].http://wintelguy.com/raidperf.pl.

MULTIDIMENSIONAL OFF-LINE SCHEDULING ALGORITHM FOR CLOUD STORAGE

Wang Yong Tian Bo Wang Duan

(CollegeofComputerScienceandEngineering,GuilinUniversityofElectronicTechnology,Guilin541004,Guangxi,China)

Since the cloud block storage system used is the Cinder of OpenStack, and the default scheduling algorithm used by Cinder is only from the available space capacity of the storage node, it can not guarantee the IOPS of the volume request effectively. In view of this situation, considering the available space capacity and I / O throughput of the storage node, a multidimensional off-line scheduling algorithm (MVCFD) is proposed based on the APX-hard Vector Bin Packing algorithm. Experimental results show that the proposed algorithm can effectively reduce the number of active hosts in the case of both the space request and the IOPS of the existing block storage scheduling algorithm.

Cloud storage OpenStack Resource scheduling Vector packing

2016-05-10。王勇，教授，主研領(lǐng)域：云計算，計算機網(wǎng)絡(luò)技術(shù)及應(yīng)用，信息安全。田博，碩士。王端，碩士。

TP391.9

A

10.3969/j.issn.1000-386x.2017.06.055