李夢(mèng)寒　 鄭小盈　 李明齊　 張宏鑫

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

?

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

李夢(mèng)寒1,2鄭小盈1*李明齊1張宏鑫3

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

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

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

0　引　言

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

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

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

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

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

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

1　云存儲(chǔ)的流量與帶寬管理

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

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

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

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

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

圖2　Dropbox工作流程

1.2流量與帶寬管理

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

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

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

1.3國(guó)內(nèi)外研究進(jìn)展

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

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

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

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

2.1ARIMA技術(shù)簡(jiǎn)介

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

2.1.1差分整合移動(dòng)平均自回歸模型

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

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

(1)

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

(2)

d為差分階數(shù)

Yt=▽dXt

(3)

當(dāng)d=1時(shí)，

Yt=Xt-Xt-1

(4)

當(dāng)d=2時(shí)，

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

(5)

2.1.2算法流程

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

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

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

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

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

圖3　ARIMA模型建立

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

2.2帶寬預(yù)留算法

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

3　流量負(fù)載均衡

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

3.1貪心算法

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

算法1貪心算法負(fù)載均衡

輸入：請(qǐng)求信息req

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

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

負(fù)載均衡器：

1.while (1) do

2.if 請(qǐng)求到來(lái)

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

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

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

6.更新負(fù)載bs[]=s[]

7.更新bal[]

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

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

3.2二次隨機(jī)選擇算法

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

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

算法2二次選擇負(fù)載均衡算法

輸入：請(qǐng)求信息req

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

1.while (1) do

2.if 請(qǐng)求到來(lái)

3.隨機(jī)引導(dǎo)至一臺(tái)負(fù)載均衡器x

4.隨機(jī)選擇此均衡器下兩臺(tái)塊服務(wù)器節(jié)點(diǎn)a,b

5.獲取這兩臺(tái)節(jié)點(diǎn)流量負(fù)載

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

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

8.else

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

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

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

3.3算法分析

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

表2　簡(jiǎn)化模型下，算法開(kāi)銷和性能比較

4　仿真與分析

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

4.1采用Dropbox流量日志

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

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

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

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

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

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

圖7比較了二次隨機(jī)選擇算法模式下，服務(wù)器獨(dú)立進(jìn)行預(yù)測(cè)并上報(bào)預(yù)測(cè)值以及服務(wù)器上報(bào)流量并進(jìn)行統(tǒng)一預(yù)測(cè)的性能?？梢?jiàn)將塊服務(wù)器的流量分別預(yù)測(cè)后的預(yù)留帶寬之和與將塊服務(wù)器總流量進(jìn)行預(yù)測(cè)后的預(yù)留帶寬值之間的基本一致?？梢?jiàn)服務(wù)器進(jìn)行獨(dú)立預(yù)測(cè)并沒(méi)有影響預(yù)測(cè)的效果。

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

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

4.2采用隨機(jī)生成流量日志

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

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

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

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

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

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

(1) 不同算法仿真的負(fù)載均值和標(biāo)準(zhǔn)差

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

表3　仿真結(jié)果

二次隨機(jī)選擇算法獲得的負(fù)載標(biāo)準(zhǔn)方差為2.148 Mbps，貪心算法獲得的負(fù)載標(biāo)準(zhǔn)方差略低于2 Mbps，并在3 s同步間隔時(shí)取得最小值1.703 Mbps。可見(jiàn)，二次隨機(jī)選擇算法的性能接近于貪心算法，負(fù)載分布比較均衡，并且系統(tǒng)開(kāi)銷低，可擴(kuò)展性好。此外，試驗(yàn)說(shuō)明對(duì)于貪心算法，并不是同步的頻率越高越好。

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

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

圖8　二次隨機(jī)選擇算法

圖9　貪心算法

(3) 500臺(tái)機(jī)器每小時(shí)平均負(fù)載累計(jì)分布函數(shù)

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

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

5　結(jié)　語(yǔ)

網(wǎng)盤(pán)服務(wù)日益成為人們?nèi)粘Ｐ畔⒋鎯?chǔ)的工具之一。本文分析了dropbox云存儲(chǔ)服務(wù)的系統(tǒng)架構(gòu)，針對(duì)當(dāng)今用戶數(shù)量規(guī)模增大，存在海量數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)特點(diǎn)，為類dropbox服務(wù)設(shè)計(jì)了兩種流量調(diào)度算法。在小型的云存儲(chǔ)網(wǎng)絡(luò)中，貪心算法能獲得更好的負(fù)載均衡，在大型的云存儲(chǔ)網(wǎng)絡(luò)中，考慮到貪心算法所需的系統(tǒng)開(kāi)銷較大，采用二次隨機(jī)選擇負(fù)載均衡算法能夠取得接近于貪心算法的性能，其所需的信息交換量由O(n)降低為O(2)，非常適用于大規(guī)模在線存儲(chǔ)系統(tǒng)的流量管理。主流的云計(jì)算網(wǎng)絡(luò)資源計(jì)費(fèi)策略是基于預(yù)留帶寬的多少，本文提出了使用ARMIA模型通過(guò)流量預(yù)測(cè)合理調(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。國(guó)家自然科學(xué)基金項(xiàng)目(61100238);中科院先導(dǎo)項(xiàng)目(XDA06010301);中國(guó)科學(xué)院重點(diǎn)部署項(xiàng)目(KGZD-EW-103);上海市科委項(xiàng)目(14510722300，13DZ1511200);中國(guó)科學(xué)院青年創(chuàng)新促進(jìn)會(huì)，浙江大學(xué)CAD&CG國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題(A1314)。李夢(mèng)寒，碩士生，主研領(lǐng)域：通信網(wǎng)絡(luò)。鄭小盈，副研究員。李明齊，研究員。張宏鑫，副教授。

TP3

A

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