在線云存儲服務(wù)的流量管理研究

李夢寒　 鄭小盈　 李明齊　 張宏鑫

1(中國科學(xué)院上海高等研究院　上海 201210)2(中國科學(xué)院大學(xué)電子電氣與通信工程學(xué)院　北京 100190)3(浙江大學(xué)CAD&CG國家重點實驗室　浙江 杭州 310035)

?

在線云存儲服務(wù)的流量管理研究

李夢寒1,2鄭小盈1*李明齊1張宏鑫3

1(中國科學(xué)院上海高等研究院上海 201210)2(中國科學(xué)院大學(xué)電子電氣與通信工程學(xué)院北京 100190)3(浙江大學(xué)CAD&CG國家重點實驗室浙江 杭州 310035)

云存儲是云計算應(yīng)用的一個重要分支，有效利用數(shù)據(jù)中心的帶寬資源，設(shè)計高效、均衡、可擴展性良好的帶寬資源管理和流量負載均衡算法十分重要。在云存儲服務(wù)典型應(yīng)用Dropbox的架構(gòu)下，可設(shè)計最小帶寬優(yōu)先的貪心算法和二次隨機選擇算法來實現(xiàn)負載均衡，并將其和流量預(yù)測、帶寬預(yù)留技術(shù)結(jié)合在一起，實現(xiàn)一套流量負載均衡和帶寬預(yù)留方案。貪心算法的負載均衡技術(shù)能夠取得良好的性能，但是復(fù)雜度高、系統(tǒng)開銷較大、可擴展性較差；二次隨機選擇算法復(fù)雜度低并且顯著減少了系統(tǒng)通信開銷。通過Dropbox真實流量數(shù)據(jù)和大規(guī)模仿真數(shù)據(jù)的實驗，表明二次隨機選擇算法能夠?qū)崿F(xiàn)接近于貪心算法性能的均衡流量調(diào)度?；陬A(yù)測的帶寬預(yù)留技術(shù)保證了服務(wù)質(zhì)量，提高了網(wǎng)絡(luò)資源利用率。

云存儲負載均衡流量管理流量預(yù)測帶寬預(yù)留

0　引　言

面向個人的云存儲也即網(wǎng)盤服務(wù)是云計算概念中最為人們熟悉和喜愛的應(yīng)用之一。其中，由Dropbox公司在2007年推出的在線存儲服務(wù)Dropbox，通過互聯(lián)網(wǎng)為用戶提供了本地文件和云端文件同步的服務(wù)。通過Dropbox，用戶可以存儲并共享文件和文件夾。截止2014年4月，Dropbox已擁有大約2億7500萬用戶，用戶日均上傳10億個文件，占用了互聯(lián)網(wǎng)0.29%的流量。此外，類似的在線存儲服務(wù)也不斷興起，例如國外的Box.com，UbuntuOne，Google Drive等，國內(nèi)的百度云、微云、360云盤。這些在線云存儲服務(wù)以其免費、方便以及良好的用戶體驗贏得了大量的用戶，成為互聯(lián)網(wǎng)和云計算的重要應(yīng)用。

Dropbox在線存儲采用了云計算架構(gòu)，是體現(xiàn)云計算彈性資源分配優(yōu)勢的完美實例之一。Dropbox使用Amazon公司的AWS云計算服務(wù)為其存儲提供基礎(chǔ)架構(gòu)，通過AWS的EC2虛擬機服務(wù)和S3存儲服務(wù)來搭建云端文件存儲服務(wù)器。Dropbox公司僅維護了少量的本地服務(wù)器用于用戶認證、通知、系統(tǒng)日志以及元數(shù)據(jù)管理等功能。這一設(shè)計理念完全體現(xiàn)了云計算按需付費、彈性擴充資源、無需承擔系統(tǒng)運維和硬件投資的優(yōu)勢。

Dropbox在線云存儲服務(wù)通過互聯(lián)網(wǎng)來實現(xiàn)文件的同步和共享，勢必要占用大量的互聯(lián)網(wǎng)資源，其所在的數(shù)據(jù)中心必須預(yù)留大量出口/入口帶寬，來保障Dropbox用戶的服務(wù)體驗。因此如何有效利用數(shù)據(jù)中心的帶寬資源，設(shè)計高效、均衡、可擴展性良好的帶寬資源管理和流量負載均衡算法十分重要。

首先，Dropbox通過租用大量AWS EC2虛擬機來彈性搭建文件存儲服務(wù)器。AWS EC2虛擬機租用可以指定虛擬機的出口/入口流量帶寬，并按照帶寬收費。為了提供良好的用戶體驗，租用的帶寬應(yīng)該能夠滿足用戶實際的下載/上傳需求；為了節(jié)約成本，租用的帶寬不應(yīng)超過實際需求過多，以免造成浪費。因此帶寬的租用應(yīng)在成本和用戶體驗兩者之間達到一定的平衡。流量預(yù)測算法能夠為帶寬預(yù)留提供依據(jù)，既能為用戶體驗提供保障，又能節(jié)約成本、避免浪費帶寬。本文提出了基于時間序列技術(shù)的流量預(yù)測算法，為Dropbox-like在線存儲服務(wù)的帶寬預(yù)留提供了支持。

其次，由于Dropbox采用大量AWS EC2虛擬機作為其文件存儲服務(wù)器，并在前端設(shè)置多個負載均衡器來分配工作負荷。因此研究簡單高效、可擴展性好的負載均衡算法很重要。本文首先提出了基于貪心算法的負載均衡算法，并將其和流量預(yù)測、帶寬預(yù)留技術(shù)結(jié)合在一起，設(shè)計了一套流量負載均衡和帶寬預(yù)留算法。由于貪心算法需要維護系統(tǒng)內(nèi)服務(wù)器負載情況這一全局信息，所需的系統(tǒng)通信開銷較高、可擴展性較差，本文繼而提出了二次隨機選擇算法來均衡負載。二次隨機選擇算法無需維護服務(wù)器負載這一全局信息，其在處理用戶請求時，只需隨機選擇2臺服務(wù)器，因此所需的系統(tǒng)信息交互量低、算法復(fù)雜度低、可擴展性良好。于此同時，我們的性能分析以及實驗仿真結(jié)果都表明，二次隨機選擇算法在低復(fù)雜度低系統(tǒng)開銷的前提下，依然能保證負載均衡算法的良好性能。

本文根據(jù)歐洲某大學(xué)監(jiān)測到的Dropbox流量公開日志[1]，對提出的算法進行了仿真驗證。此外，為了驗證所提出的算法在大規(guī)模系統(tǒng)上的性能，我們仿真生成了大規(guī)模的流量數(shù)據(jù)用于測試。測試結(jié)果表明二次隨機選擇負載均衡算法取得了接近于貪心算法的性能，而其所需的系統(tǒng)開銷低，非常適用于大規(guī)模在線存儲系統(tǒng)的流量管理。

1　云存儲的流量與帶寬管理

1.1Dropbox云存儲系統(tǒng)架構(gòu)

如圖1所示，Dropbox系統(tǒng)主要由兩部分組成：由Dropbox公司本地維護的控制服務(wù)器，和位于Amazon云平臺的存儲服務(wù)器[2]。

位于本地的控制服務(wù)器主要包括通知服務(wù)器和元數(shù)據(jù)服務(wù)器。當多個客戶設(shè)備之間文件發(fā)生異動時，通知服務(wù)器負責(zé)發(fā)出同步通知，元數(shù)據(jù)服務(wù)器查找存儲所需的元數(shù)據(jù)，內(nèi)存對象緩存系統(tǒng)(memcache)負責(zé)緩存數(shù)據(jù)庫中的元數(shù)據(jù)。元數(shù)據(jù)服務(wù)器首先查找緩存系統(tǒng)，如果找到了所需的元數(shù)據(jù)就直接返回，否則就查找元數(shù)據(jù)數(shù)據(jù)庫。通過內(nèi)存對象緩存系統(tǒng)，可以極大地加速元數(shù)據(jù)的查找過程。

位于云端的塊服務(wù)器負責(zé)文件數(shù)據(jù)的存取。當元數(shù)據(jù)服務(wù)器獲取了客戶所需的元數(shù)據(jù)之后，由負載均衡器指定的塊服務(wù)器將通過遠程調(diào)用RPC從元數(shù)據(jù)服務(wù)器獲取所需的元數(shù)據(jù)。此后文件數(shù)據(jù)的上傳下載將在位于云端的塊服務(wù)器和客戶設(shè)備之間進行。圖2 描述了Dropbox系統(tǒng)工作的一個基本流程。

圖1　Dropbox系統(tǒng)架構(gòu)圖[2]

圖2　Dropbox工作流程

1.2流量與帶寬管理

Dropbox體系架構(gòu)中，位于Amazon云端的塊服務(wù)器是Dropbox公司向Amazon AWS云服務(wù)租用的EC2虛擬機集群。塊服務(wù)器的前端直接和客戶設(shè)備進行文件的傳輸，塊服務(wù)器的后端負責(zé)在Amazon S3存儲系統(tǒng)中數(shù)據(jù)的讀寫。因此，Dropbox公司在租用虛擬機作為塊服務(wù)器的時候，除了CPU個數(shù)、內(nèi)存大小等性能外，還必須預(yù)留虛擬機的互聯(lián)網(wǎng)出口/入口帶寬。在其他互聯(lián)網(wǎng)應(yīng)用中，例如視頻點播、社交網(wǎng)絡(luò)，往往是中心機房的出口流量遠遠大于入口流量。但是Dropbox在線存儲的出口流量和入口流量基本相等，也就是客戶上傳和下載文件的流量基本相等。因此在Dropbox架構(gòu)中，把塊服務(wù)器區(qū)分成讀和寫兩個部分[2]。

在Dropbox系統(tǒng)中，數(shù)據(jù)中心通過預(yù)留足夠的出口/入口帶寬來保障用戶服務(wù)體驗，因此用戶設(shè)備傳輸文件的網(wǎng)絡(luò)瓶頸往往位于用戶側(cè)?？紤]到Amazon AWS云根據(jù)預(yù)留帶寬的數(shù)值來收費，如果Dropbox系統(tǒng)預(yù)留了過多的帶寬，那么勢必造成浪費；如果帶寬預(yù)留少了，那么會影響用戶體驗。因此如何估計帶寬的預(yù)留值，是本文研究的兩個問題之一。

其次，Dropbox公司并未披露其所使用的負載均衡算法，只說明了Dropbox系統(tǒng)使用了多個負載均衡器。因此如何利用多個負載均衡器為文件傳輸請求分配塊服務(wù)器，從而達到負載均衡算法的高效、低系統(tǒng)開銷以及可擴展性良好，是本文探討的另一個問題。

1.3國內(nèi)外研究進展

2012年，Dropbox公司服務(wù)器開發(fā)團隊的負責(zé)人Modzelewski在斯坦福大學(xué)的講座上介紹了Dropbox體系架構(gòu)的演進歷程[2]，給出了如圖1中所示的體系架構(gòu)。文獻[1]中，Drago等研究人員通過在歐洲的兩所大學(xué)校園網(wǎng)和兩個大型ISP網(wǎng)絡(luò)上分別部署的四個監(jiān)測點，截取了42天Dropbox相關(guān)流量日志數(shù)據(jù)。文獻[1]通過截獲的日志，分析了Dropbox的體系架構(gòu)和協(xié)議，并研究了Dropbox流量特征和性能瓶頸。

云計算環(huán)境下的負載預(yù)測以及資源調(diào)度的研究已經(jīng)得到了廣泛的開展。文獻[3]提出了基于支持向量機和Kalman平穩(wěn)器的負荷預(yù)測算法，并根據(jù)預(yù)測值來預(yù)留資源。相比文獻[3]，本文采用ARIMA技術(shù)作為流量預(yù)測算法，并進一步考慮了任務(wù)調(diào)度和負載均衡的可擴展性問題。文獻[4,5]研究了云計算資源拍賣模式下網(wǎng)絡(luò)帶寬資源的拍賣，依據(jù)網(wǎng)絡(luò)流量日志數(shù)據(jù)來預(yù)測未來的網(wǎng)絡(luò)帶寬需求，進而研究帶寬拍賣標的、用戶競拍策略、帶寬資源復(fù)用和分配算法。文獻[4,5]基于視頻流媒體這一特定的應(yīng)用，其主要流量為數(shù)據(jù)中心的出口流量，并且少量熱點視頻吸引了大量用戶并占據(jù)主要帶寬，無法直接推廣到云存儲應(yīng)用。

此外不少相關(guān)工作研究了云計算環(huán)境下資源管理問題。云計算集群資源管理問題往往被建模成NP-hard難度的背包問題，希望能夠在滿足用戶資源需求的前提下，最小化分配的物理節(jié)點數(shù)目。例如，文獻[6]將資源分配問題建模成隨機背包問題，文獻[7]也是通過解決背包問題來進行服務(wù)器的整合。文獻[8]首先預(yù)測下一個周期虛擬機的資源需求，然后通過背包算法進行資源分配，最后通過虛擬機遷移來實現(xiàn)資源的調(diào)整。文獻[9]設(shè)計了三種用戶需求預(yù)測模型，包括標準自動回歸模型AR(standard autoregressive)、符合ANOVA-AR模型,和多脈沖模型MP(multi-pulse)。根據(jù)預(yù)測到的用戶需求，文獻[9]為虛擬機分配物理資源。這些工作對于算法可擴展性的考慮并不多。目前比較流行的集群計算系統(tǒng)往往采用master-slave的架構(gòu)，使用單個集中控制器管理集群資源，進行資源調(diào)度和負載均衡，例如MapReduce[10]、Apache Mesos[11]、Spark[12]等。Master-slave架構(gòu)中，集中控制器掌握全局資源信息，能夠較優(yōu)地進行資源分配和負載均衡，但是其系統(tǒng)開銷較大，并且可擴展性和系統(tǒng)魯棒性較差。在文獻[13]中，研究人員采用去中心化的調(diào)度系統(tǒng)Sparrow，使用隨機采樣為對調(diào)度延遲要求非常高的短任務(wù)設(shè)計高吞吐量的調(diào)度算法并達到負載均衡。

2　基于預(yù)測技術(shù)的帶寬預(yù)留

2.1ARIMA技術(shù)簡介

使用時間序列分析技術(shù)可以實現(xiàn)流量未來時刻的帶寬需求的預(yù)測。長相關(guān)性、短相關(guān)性、大時間尺度下的自相似性以及小時間尺度下的多重分形性是網(wǎng)絡(luò)流量重要的統(tǒng)計特征，經(jīng)濟學(xué)領(lǐng)域得到廣泛使用的線性時間序列ARIMA模型能為此提供較好的數(shù)學(xué)模型，也是網(wǎng)絡(luò)預(yù)測的主流技術(shù)[14]。

2.1.1差分整合移動平均自回歸模型

差分整合移動平均自回歸模型ARIMA模型(Autoregressive Integrated Moving Average model)是時間序列預(yù)測分析方法之一。ARIMA(r,d,m)模型中，AR是“自回歸”，r為自回歸項數(shù)，MA為“滑動平均”，m為滑動平均項數(shù)，d為使之成為平穩(wěn)序列所作的差分次數(shù)(階數(shù)) 。ARIMA模型可以表示為:

ΔdXt=φ(B)ΔdXt+Zt+θ(B)Zt

(1)

其中Xt是要分析的時間序列，φ(B)和θ(B)分別表示AR(r)模型中的r次多項式和MA(m)模型中的m次多項式，B是后向移位算子(BjCt=Xi-j)。

(2)

d為差分階數(shù)

Yt=▽dXt

(3)

當d=1時，

Yt=Xt-Xt-1

(4)

當d=2時，

Yt=(Xt-Xt-1)-(Xt-1-Xt-2)

(5)

2.1.2算法流程

為了根據(jù)訓(xùn)練集預(yù)測數(shù)據(jù)，我們首先需要建立模型，確定ARIMA(r,d,m)的階數(shù)，然后對模型的各個參數(shù)進行估計，也就是確定φ(B)、θ(B)等多項式的系數(shù)。

ARIMA模型適用于平穩(wěn)的時間序列，對于非平穩(wěn)的隨機過程，則要通過多次差分直到序列達到平穩(wěn)，而差分的次數(shù)為參數(shù)d的取值。ARIMA(r,d,m)的階數(shù)m和r可以從自相關(guān)函數(shù)(ACF)和偏自相關(guān)函數(shù)(PACF)中觀察拖尾和截尾的特征確定。

序列經(jīng)過平穩(wěn)化處理后，模型的選擇與自相關(guān)函數(shù)和偏自相關(guān)函數(shù)性質(zhì)關(guān)系如表1所示。

表1　模型選擇與ACF/PACF關(guān)系

對于計算機定階，一般采用AIC、BIC準則定階，也就是排列組合所有可能的r和m，通過AIC函數(shù)得到的值越小，那么說明那一組r和m最好。在上述模型識別的基礎(chǔ)上，進行參數(shù)估計，通過樣本矩估計法、極大似然法等確定模型中的各未知系數(shù)：

圖3　ARIMA模型建立

建立了ARIMA模型之后，可以預(yù)測未來一個時間序列點的流量數(shù)學(xué)期望。ARIMA模型支持單步預(yù)測，也支持k步預(yù)測。k步預(yù)測是通過遞歸使用單步預(yù)測實現(xiàn)的。

2.2帶寬預(yù)留算法

預(yù)測值會包括下一時刻流量均值μ和標準差σ,我們將μ+θσ作為帶寬的預(yù)留值，根據(jù)不同的服務(wù)質(zhì)量要求，θ取不同的值。以統(tǒng)計中常見的3σ原則為例，當θ=2時，可以保證實際帶寬以95.44%的概率不超過預(yù)留帶寬，落在置信區(qū)間[μ-2σ,μ+2σ]中,因此可以將此區(qū)間的上界μ+2σ作為帶寬預(yù)留值。

3　流量負載均衡

如圖1所示，Dropbox系統(tǒng)配置了多個負載均衡器，負責(zé)將用戶請求引導(dǎo)到元數(shù)據(jù)服務(wù)器/塊服務(wù)器，以實現(xiàn)元數(shù)據(jù)服務(wù)器/塊服務(wù)器的負載均衡。本文的工作主要關(guān)注塊服務(wù)器的流量這一負載指標，擬實現(xiàn)塊服務(wù)器之間流量負載的均衡。文獻[1]提供的測量數(shù)據(jù)表明，Dropbox公司租用了大量Amazon EC2虛擬機用作塊服務(wù)器，僅文獻[1]的日志數(shù)據(jù)就已包含了500多臺塊服務(wù)器，并且隨著在線存儲服務(wù)的快速發(fā)展，塊服務(wù)器的規(guī)模也勢必增長，因此負載均衡算法的設(shè)計必須考慮算法的系統(tǒng)開銷以及可擴展性。我們首先提出了基于貪心算法的負載均衡策略。貪心算法能夠取得較好的負載均衡性能，但是其所需的系統(tǒng)開銷較大，可擴展性不夠好。然后我們進一步提出了基于二次隨機選擇算法的負載均衡策略，希望在減小系統(tǒng)開銷的同時，能夠取得較好的系統(tǒng)負載均衡。

3.1貪心算法

我們首先設(shè)計了貪心算法這一基于局部最優(yōu)策略的負載均衡器。其核心思想是，當用戶請求到來時，總是將用戶請求引導(dǎo)至當前負載最低的塊服務(wù)器。由于貪心算法需要選擇當前負載最低的服務(wù)器，勢必要求負載均衡器維護當前所有塊服務(wù)器的負載信息。當塊服務(wù)器的數(shù)量龐大時，由一臺負載均衡器來維護所有服務(wù)器負載狀態(tài)這一全局信息并不現(xiàn)實。考慮到Dropbox系統(tǒng)設(shè)置了多個負載均衡器，我們的貪心負載均衡算法采用分層次的策略。將塊服務(wù)器劃分成多個組，每個負載均衡器管理一個組。因此單個負載均衡器只需要維護其所轄組內(nèi)的服務(wù)器負載狀態(tài)，減輕了負載均衡器的維護負擔。組之間的負載均衡由一個集中式管理器負責(zé)。我們在算法1中給出了貪心算法的偽代碼。

算法1貪心算法負載均衡

輸入：請求信息req

輸出：響應(yīng)請求的塊服務(wù)器

/*所有塊服務(wù)器實際負載為s[i],均衡器上各塊服務(wù)器信息bs[i]，各均衡器所管理的最小負載以及所在機器編號bal[i]=(minload,server id)*/

負載均衡器：

1.while (1) do

2.if 請求到來

3.尋找均衡器x，確定塊服務(wù)器索引a

4.將請求引導(dǎo)至塊服務(wù)器a

5.if 收到塊服務(wù)器更新信息

6.更新負載bs[]=s[]

7.更新bal[]

算法流程可簡述為，用戶發(fā)出任務(wù)請求后，該任務(wù)首先通過集中式的管理器到達擁有最小負載塊服務(wù)器所在的均衡器，根據(jù)該均衡器信息，將請求交由負載最小的塊服務(wù)器。每當均衡器收到塊服務(wù)器的負載更新信息時，就同步更新bs[]以及bal[]記錄。

貪心算法中，每臺塊服務(wù)器周期性地向其所在的負載均衡器發(fā)送負載信息。在周期性的更新過程中，全局的信息交換量為O(n),n代表塊服務(wù)器數(shù)量。由于更新周期通常為數(shù)秒，更新的頻率較高，因此周期性負載更新帶來的系統(tǒng)開銷比較高。此外當服務(wù)器數(shù)量較多時，不僅會產(chǎn)生較大的通信開銷，網(wǎng)絡(luò)傳輸?shù)母哐舆t還會造成負載信息和實際信息的不一致，降低了系統(tǒng)性能。

3.2二次隨機選擇算法

貪心算法需要塊服務(wù)器周期性地向負載均衡器發(fā)送負載信息。如果負載更新的頻率增加，全局性的信息交換量也隨之增加。另一方面，負載周期性更新也表明負載均衡器維護的負載信息并非全局實時信息。因此我們考慮設(shè)計一種負載均衡策略，能夠在不維護全局信息的情況下，仍然取得流量負載的均衡。

我們采用文獻[15]提出的二次隨機選擇算法。二次隨機算法中，負載均衡器無需維護塊服務(wù)器負載這一全局信息，也無需將塊服務(wù)器分組管理。當用戶請求到來時，請求被隨機引導(dǎo)到一臺負載均衡器。該負載均衡器隨機選擇兩臺塊服務(wù)器節(jié)點，獲取這兩臺服務(wù)器的流量負載，并把用戶請求分配給負載較小的服務(wù)器節(jié)點。算法2中，我們給出了二次隨機選擇負載均衡算法。

算法2二次選擇負載均衡算法

輸入：請求信息req

輸出：響應(yīng)請求的塊服務(wù)器

1.while (1) do

2.if 請求到來

3.隨機引導(dǎo)至一臺負載均衡器x

4.隨機選擇此均衡器下兩臺塊服務(wù)器節(jié)點a,b

5.獲取這兩臺節(jié)點流量負載

6.if s[a]>s[b]

7.將請求引導(dǎo)至塊服務(wù)器a

8.else

9.將請求引導(dǎo)至塊服務(wù)器b

10.if 均衡器收到塊服務(wù)器更新信息

11.更新均衡器記錄的負載信息bs[]和bal[]

3.3算法分析

在算法1所示貪心算法中，我們通過增加塊服務(wù)器分組機制以及負載狀態(tài)周期性更新，來節(jié)約系統(tǒng)通信開銷，提高系統(tǒng)可擴展性。在原始的貪心算法中，每當用戶請求到來時，負載均衡器需要采樣所有n個塊服務(wù)器節(jié)點的流量負載，從而獲得負載最小的服務(wù)器節(jié)點，其通信開銷為O(n)；在二次隨機選擇算法中，對于每個請求，我們僅僅采樣了2個服務(wù)器節(jié)點的流量，其通信開銷為O(2)。因此，二次隨機選擇算法顯著減少了所需的系統(tǒng)通信開銷。下面我們將通過簡化的模型來研究貪心算法和二次隨機算法的性能。我們假設(shè)所有用戶請求的流量值均為單位流量1。如果系統(tǒng)中服務(wù)器的平均流量負載為r，那么對于僅隨機選擇一個服務(wù)器的算法(隨機選擇算法)，其服務(wù)器的最大負載為rlogn/log logn；而采用二次隨機選擇算法，通過增加一個隨機選擇，此最大負載降低到r(log logn+θ(1)),呈指數(shù)式遞減[15]。由此可見，通過增加一次隨機采樣的過程，我們顯著降低了服務(wù)器的最大負載。文獻[15]還表明，繼續(xù)增加采樣的次數(shù)，對于降低最大負載的作用有限。當然，貪心算法在一般情況下可以將服務(wù)器最大負載保持在r左右。表2中，我們總結(jié)了簡化模型下，這三種算法的系統(tǒng)開銷和性能。

表2　簡化模型下，算法開銷和性能比較

4　仿真與分析

本節(jié)通過搭建仿真來研究貪心算法和二次隨機選擇算法的性能。Dropbox系統(tǒng)在云端預(yù)留大量傳輸帶寬，因此數(shù)據(jù)傳輸?shù)钠款i一般位于用戶側(cè)。本節(jié)實驗假設(shè)數(shù)據(jù)傳輸瓶頸位于用戶端。另外，Dropbox系統(tǒng)的讀寫數(shù)據(jù)量大致相當，并且我們通過分析Dropbox流量日志[1]，發(fā)現(xiàn)文件上傳量多于文件下載量。因此我們的仿真實驗集中于文件的上傳流量。

4.1采用Dropbox流量日志

本節(jié)使用歐洲某大學(xué)監(jiān)測到的Dropbox應(yīng)用流量公開數(shù)據(jù)[1]。該公開數(shù)據(jù)包含了從4個監(jiān)測點監(jiān)測到的2012年3月24日至2012年5月5日期間的Dropbox應(yīng)用相關(guān)網(wǎng)絡(luò)流量日志。該數(shù)據(jù)經(jīng)過匿名化處理保護用戶的隱私。原始數(shù)據(jù)是由Tsat開源工具截取的與Dropbox應(yīng)用相關(guān)的所有TCP數(shù)據(jù)包相關(guān)信息。由于該流量日志數(shù)據(jù)比較小，本節(jié)將2012年3月24日至2012年5月5日之間所有監(jiān)測數(shù)據(jù)歸并為一天的流量數(shù)據(jù)用于實驗。本節(jié)假設(shè)這些用戶請求訪問5臺塊服務(wù)器，并配置了一臺負載均衡器。

圖4和圖5分別展示了采用貪心算法和二次隨機選擇算法時，5臺服務(wù)器使用各自的流量負載變化情況，可見這兩種算法都能夠?qū)崿F(xiàn)均衡的流量調(diào)度。其中，貪心算法調(diào)度下的塊服務(wù)器之間負載差異很小,二次隨機選擇算法在某些時刻不同服務(wù)器的負載較為分散，表明在塊服務(wù)器數(shù)量規(guī)模較小時，貪心算法能夠更好地實現(xiàn)均衡的流量調(diào)度。

圖4　貪心算法調(diào)度下塊服務(wù)器負載

圖5　二次隨機算法調(diào)度下塊服務(wù)器負載

我們采用ARIMA(0，1，1)模型作為帶寬預(yù)留模塊的預(yù)測算法。我們每10分鐘統(tǒng)計一次平均流量，生成流量時間序列，作為流量預(yù)測的訓(xùn)練數(shù)據(jù)，進而根據(jù)不同服務(wù)質(zhì)量的要求預(yù)留帶寬。對于貪心算法，由于負載均衡器維護其管轄的服務(wù)器組內(nèi)的全局負載信息，所以負載均衡器負責(zé)執(zhí)行流量預(yù)測算法；對于二次隨機選擇算法，由于負載均衡器不維護全局負載信息，如果由負載均衡器執(zhí)行預(yù)測，需要服務(wù)器將流量上報負載均衡器，系統(tǒng)通信開銷較大。因此每臺塊服務(wù)器獨立執(zhí)行流量預(yù)測算法。預(yù)測完成后，各服務(wù)器將流量預(yù)測的數(shù)學(xué)期望和標準方差上報到集中管理節(jié)點(某臺指定的負載均衡器)，取和后作為系統(tǒng)的帶寬預(yù)留值。這種方式不僅減小了通信開銷，也方便協(xié)調(diào)不同服務(wù)器服務(wù)質(zhì)量的要求，擴展性較好。

圖6描述了貪心算法模式下，負載均衡器對5臺服務(wù)器總流量的預(yù)測效果。其中黑實線表示真實流量，點虛線表示流量的預(yù)測值，最上面的點線代表預(yù)測值的95%置信區(qū)間上界。只有1.19%的預(yù)留值小于真實值；預(yù)留值比真實值平均多了30%。

圖7比較了二次隨機選擇算法模式下，服務(wù)器獨立進行預(yù)測并上報預(yù)測值以及服務(wù)器上報流量并進行統(tǒng)一預(yù)測的性能?？梢妼K服務(wù)器的流量分別預(yù)測后的預(yù)留帶寬之和與將塊服務(wù)器總流量進行預(yù)測后的預(yù)留帶寬值之間的基本一致?？梢姺?wù)器進行獨立預(yù)測并沒有影響預(yù)測的效果。

圖6　真實流量預(yù)測值與帶寬預(yù)留值

圖7　帶寬預(yù)留值比較

4.2采用隨機生成流量日志

由于Dropbox真實流量日志的規(guī)模較小，在4.1節(jié)中，我們只仿真了5臺塊服務(wù)器和1臺負載均衡器。而Dropbox系統(tǒng)部署了大量的塊服務(wù)器。為了研究本文提出的算法在大規(guī)模系統(tǒng)情況下的性能，本節(jié)仿真生成了大規(guī)模流量數(shù)據(jù)，用于對比兩種調(diào)度算法的性能。

對于測試數(shù)據(jù)的生成以及仿真環(huán)境假定如下：

(1) 用戶端上載的傳輸率服從幾何分布，其均值分別設(shè)為1、2、5、10和20 Mbps。用戶每秒請求次數(shù)服從均值為200的Poisson分布。用戶上傳文件的數(shù)據(jù)量服從幾何分布，數(shù)據(jù)量的均值為10 MB。仿真過程最小時間粒度為1秒，傳輸時間不足1秒按照1秒處理。測試數(shù)據(jù)持續(xù)時間為1小時(3600秒)。

(2) 系統(tǒng)配置有5臺負載均衡器和500臺塊服務(wù)器。

(3) 仿真貪心算法時，每臺負載均衡器負責(zé)100臺服務(wù)器的任務(wù)調(diào)度。每個負載均衡器都存著其所管理的服務(wù)器的負載信息，以5秒一個心跳時間間隔來進行負載信息的同步。當一個請求到來時，首先查找5個負載均衡器，找出擁有最小負載的服務(wù)器索引，把任務(wù)分配給此服務(wù)器，并在此負載均衡器上更新當前服務(wù)器狀態(tài)信息。

我們根據(jù)不同的調(diào)度算法首先仿真出500臺服務(wù)器每秒的負載變化情況，據(jù)此得出如下結(jié)論：

(1) 不同算法仿真的負載均值和標準差

表3為各調(diào)度算法的仿真結(jié)果。

表3　仿真結(jié)果

二次隨機選擇算法獲得的負載標準方差為2.148 Mbps，貪心算法獲得的負載標準方差略低于2 Mbps，并在3 s同步間隔時取得最小值1.703 Mbps。可見，二次隨機選擇算法的性能接近于貪心算法，負載分布比較均衡，并且系統(tǒng)開銷低，可擴展性好。此外，試驗說明對于貪心算法，并不是同步的頻率越高越好。

(2) 服務(wù)器最大負載，最小負載，和平均負載

在圖8和圖9中，我們統(tǒng)計了500臺服務(wù)器的最大流量負載，最小流量負載，和服務(wù)器的平均負載。上線代表500臺服務(wù)器中當前負載最高的服務(wù)器的負載值，下線代表負載最低的服務(wù)器的負載值，中線代表500臺服務(wù)器的負載均值?？梢?，二次隨機選擇算法和貪心算法取得的負載分布基本一致。

圖8　二次隨機選擇算法

圖9　貪心算法

(3) 500臺機器每小時平均負載累計分布函數(shù)

圖10中，我們給出了服務(wù)器每小時平均負載的累積分布函數(shù)CDF(cumulative distribution function)。可以看出，大部分服務(wù)器(80%)的流量負載集中在116到122 Mbps這一區(qū)間。兩種算法的性能并沒有顯著差異?？傊?，在大規(guī)模系統(tǒng)環(huán)境下，二次隨機選擇算法取得了和貪心算法接近的性能，負載比較均衡。相比于貪心算法，二次隨機選擇算法無需維護系統(tǒng)全局信息，顯著減少了系統(tǒng)間信息交互量，魯棒性好，可擴展性強。

圖10　單位小時平均負載累計分布函數(shù)

5　結(jié)　語

網(wǎng)盤服務(wù)日益成為人們?nèi)粘Ｐ畔⒋鎯Φ墓ぞ咧?。本文分析了dropbox云存儲服務(wù)的系統(tǒng)架構(gòu)，針對當今用戶數(shù)量規(guī)模增大，存在海量數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)特點，為類dropbox服務(wù)設(shè)計了兩種流量調(diào)度算法。在小型的云存儲網(wǎng)絡(luò)中，貪心算法能獲得更好的負載均衡，在大型的云存儲網(wǎng)絡(luò)中，考慮到貪心算法所需的系統(tǒng)開銷較大，采用二次隨機選擇負載均衡算法能夠取得接近于貪心算法的性能，其所需的信息交換量由O(n)降低為O(2)，非常適用于大規(guī)模在線存儲系統(tǒng)的流量管理。主流的云計算網(wǎng)絡(luò)資源計費策略是基于預(yù)留帶寬的多少，本文提出了使用ARMIA模型通過流量預(yù)測合理調(diào)整帶寬預(yù)留值的方案，不僅可以保證服務(wù)質(zhì)量，也為網(wǎng)絡(luò)資源租用者節(jié)約了成本。

[1] Drago I,Mellia M,M Munafo M,et al.Inside dropbox:understanding personal cloud storage services[C]//Proceedings of the 2012 ACM conference on Internet measurement conference.ACM,2012:481-494.

[2] Kevin Modzelewski.How We’ve Scaled Dropbox[OL].2012-09-11[2015-03-20].http://youtu.be/PE4gwstWhmc

[3] Rongdong Hu,Jingfei Jiang,Guangming Liu，et al.Efficient resources provisioning based on load forecasting in cloud[J].The scientific world journal,2014;5(2):1661-1667.

[4] Niu D,Feng C,Li B.A theory of cloud bandwidth pricing for video-on-demand providers[C]//INFOCOM,2012 Proceedings IEEE.IEEE,2012:711-719.

[5] Niu D,Feng C,Li B.Pricing cloud bandwidth reservations under demand uncertainty[C]//ACM SIGMETRICS Performance Evaluation Review.ACM,2012,40(1):151-162.

[6] Chen M,Zhang H,Su Y Y,et al.Effective vm sizing in virtualized data centers[C]//Integrated Network Management (IM),2011 IFIP/IEEE International Symposium on.IEEE,2011:594-601.

[7] Ajiro Yasuhiro,Atsuhiro Tanaka.Improving Packing Algorithms for Server Consolidation[C]//Proceedings of 33rd International Computer Measurement Group Conference.San Diego,2007:399-406.

[8] Bobroff N,Kochut A,Beaty K.Dynamic placement of virtual machines for managing sla violations[C]//Integrated Network Management,2007.IM’07.10th IFIP/IEEE International Symposium on.IEEE,2007:119-128.

[9] Xu W,Zhu X,Singhal S.Predictive Control for Dynamic Resource Allocation in Enterprise Data Centers[C] //Network Operations and Management Symposium,Vancouver,Canada,2006:115-126.

[10] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[11] Matei Zaharia,Mosharaf Chowdhury,Michael J Franklin,et al.Spark:cluster computing with working sets[C]//Proceedings of the 2nd USENIX conference on Hot topics in cloud computing (HotCloud’10).USENIX Association,Berkeley,CA,USA,2010:10-10.

[12] Benjamin Hindman,Andy Konwinski,Matei Zaharia,et al.Mesos:a platform for fine-grained resource sharing in the data center[C] //Proceedings of the 8th USENIX conference on Networked systems design and implementation (NSDI’11) Berkeley,CA,USA.USENIX Association,2011:22-22.

[13] Ousterhout K,Wendell P,Zaharia M,et al.Sparrow:distributed,low latency scheduling[C]//Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles.ACM,2013:69-84.

[14] Zhou B,He D,Sun Z,et al.Network traffic modeling and prediction with ARIMA/GARCH[C]//Proc.of HET-NETs Conference.2005:1-10.

[15] Mitzenmacher,Michael.The power of two choices in randomized load balancing[J].Parallel and Distributed Systems,IEEE Transactions,2001; 12(10):1094-1104.

ON TRAFFIC MANAGEMENT OF ONLINE CLOUD STORAGE SERVICE

Li Menghan1,2Zheng Xiaoying1*Li Mingqi1Zhang Hongxin3

1(Shanghai Advanced Research Institute,Chinese Academy of Sciences,Shanghai 201210,China)2(SchoolofElectronic,ElectricalandCommunicationEngineering,UniversityofChineseAcademyofSciences，Beijing100190,China)3(StateKeyLabofCAD&CG,ZhejiangUniversity,Hangzhou310035,Zhejiang,China)

Cloud storage is an important branch of cloud computing applications,for effectively making use of bandwidth resources in data centre,it is important to design the bandwidth management with efficiency,equilibrium and good scalability and the traffic load balancing algorithm.Under the architecture of Dropbox which is the typical application of cloud storage service,it is able to realise load balance by designing the greedy algorithm with the priority of minimum bandwidth and the secondary random selection algorithm,and they are integrated with traffic predicting and bandwidth reservation techniques to realise a set of traffic load balancing and bandwidth reservation schemes.The greedy algorithm-based load balancing technique can archive good performance but is highly complex,communication costing and poor in scalability.The secondary random selection algorithm has low complexity while significantly decreases system communication cost.We test the two algorithms in experiments on both the real Dropbox traffic data and the large-scale simulated data,results show that the secondary random selection algorithm is able to achieve the balanced load scheduling in performance close to that obtained by the greedy algorithm.The traffic prediction-based bandwidth reservation technique ensures the QoS and raises the utilisation of network resource.

Cloud storageLoad balancingTraffic managementTraffic predictionBandwidth reservation

2015-04-07。國家自然科學(xué)基金項目(61100238);中科院先導(dǎo)項目(XDA06010301);中國科學(xué)院重點部署項目(KGZD-EW-103);上海市科委項目(14510722300，13DZ1511200);中國科學(xué)院青年創(chuàng)新促進會，浙江大學(xué)CAD&CG國家重點實驗室開放課題(A1314)。李夢寒，碩士生，主研領(lǐng)域：通信網(wǎng)絡(luò)。鄭小盈，副研究員。李明齊，研究員。張宏鑫，副教授。

TP3

A

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