云存儲的多維離線調度算法

王 勇 田 博 王 端

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

云存儲的多維離線調度算法

王 勇 田 博 王 端

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

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

云塊存儲 OpenStack 資源調度 矢量裝箱

0 引 言

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

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

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

(1) 開發一個用于塊存儲，可以集成在云基礎設施平臺中，模塊化的調度框架；

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

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

1 云塊存儲

1.1 塊存儲SLA背景

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

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

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

1.2OpenStackCinder

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

在OpenStack中，塊存儲的項目名為Cinder。其系統架構如圖1所示。Cinder-Scheduler響應客戶端發出的請求然后選擇合適的后端存儲節點并在該節點上創建卷。

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

圖2 在Cinder 調度的主機過濾與計算主機權重排序

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

2 優化問題及解決方案

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

2.1 卷放置的數學模型

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

(1)

約束條件為：

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

(2)

(3)

(4)

(5)

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

2.2 基于CF算法的多維離線調度算法

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

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

輸出：使用的物理主機數目Pused。

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

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

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

第四步：輸出Pused。

3 仿真實驗與性能分析

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

3.1 性能指標

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

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

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

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

3.2 實驗裝置

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

表1 存儲主機硬件配置

表2 仿真參數設置

3.3 實驗結果

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

圖3 10臺存儲節點主機使用率

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

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

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

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

4 結 語

本文闡述了卷分配問題是一個多維VBP和基于活動的存儲實體的數量最優化的問題。為了解決這個問題本文提出了MVCFD調度算法。所提出的調度算法考慮多種資源，對卷請求隊列進行預排序，應用SLO約束每個維度，并選擇適當的存儲節點。本文的實驗設計是基于OpenStack的原則，以便它可以很容易地集成到大多數云平臺。模擬實驗的結果表明，MVCFD算法對I/O吞吐量，可擴展性和已使用主機數量的相對于OpenStack的默認調度算法與文獻[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]．計算機工程與設計，2012，33(5):2053-2056.

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

[16] 孫春玲, 陳智斌, 李建平. 裝箱問題的一種新的近似算法[J]. 云南大學學報: 自然科學版, 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。王勇，教授，主研領域：云計算，計算機網絡技術及應用，信息安全。田博，碩士。王端，碩士。

TP391.9

A

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