您现在的位置是：首页 > 技术资料 > 物联网环境下负载均衡的低代价云存储数据副本分布

推荐星级：

物联网环境下负载均衡的低代价云存储数据副本分布

更新时间：2019-12-10 14:18:13 大小：705K 上传用户：xiaohei1810 查看TA发布的资源 标签：物联网云存储 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

为满足物联网终端结点移动性和数据访问实时性要求,根据云存储中副本分布与访问的模式,提出结合数据访问点位置和访问频率,具有低访问代价的存储服务器选取方法.考虑负载对访问代价的影响,通过动态更新代价矩阵,提出负载均衡机制.研究结果表明:该方法在最少副本数目的前提下,将副本分配到与访问情况相适应的具有较低访问代价的存储服务器上,可有效减少数据访问开销,并避免副本集中分布,保证各存储服务器的负载均衡,更适合于物联网环境中云存储数据管理.

部分文件列表

文件名	大小
物联网环境下负载均衡的低代价云存储数据副本分布.pdf	705K

立即下载

【关注视频号领20积分】【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）

第43卷第4期

2012年4月

中南大学学 (自然科学版)

Journal of Central South

、

．43

No．4

and

University(Science

Technology)

Apr．2012

物网境下

均衡的低代价云存数据副本分布

何典1,2吴敏1，胡春

(1．中南大学信息科学与工程学院，湖南沙，410083；

2．湖南商学院算机与子工程学院，湖南沙，410205)

摘要：

足物

网

端

点移性和数据

率，具有低代价的存

均衡机制。研究果表明：方法在最少副本数目的前提下，将副本分配到与

代价的存器上，可有效减少数据，并避免副本集中分布，保各存

均衡，更适合于物境中云存数据管理。

：云存：物网；副本分布；

号：’rP31l 文献

性要求，根据云存中副本分布与

的模式，提出合数

据

点位置和

服

器

取方法。考代价的影响，通

更新

代价矩，提出

的具有

情况相适

低

服

开

服

器的

网

关

中

均衡；

：A

代价

文章号：1672-7207(2012)04-1355-07

分

志

and low cost

data

cloud

distribution method in

replica

environment

Load-balancing

Internet

Things

Chun．hua2

Dianl一，WU Minl，HU

(1．SchoolofInformafionScienceandEngineering，CentralSouthUniversity,Changsha410083，China；

2．School

and Electronic

ofComputer

Engineering，Hunan University ofCommerce，Changsha 410205，Chin)

Abstract：In order to meet

terminal in tarms

real time in the

for

method

storage，a

the

of mobile

and

Interact of

low access

selecting

recluircments

mobility

and data

flCCeSS in cloud

the model

distribution

Things，according

ofreplica

was

Oll

cost

Sffl"Ver

the basis ofaccess

and

the effect ofthe load on

results show that when

presented．The

storage

presented

positions

matrix

cost

frequencies．Considering

was

dynamicauy

access

cost，the

technique by

load-balancing

updating

the miniEdum number of

are

distributed to the

servers

to the

replicas，the

storage

achieving

replicas

adaptively

according

data aoccss status with low access cost．With reduced

distribution and

cost，avoided

accessing

ofcloud

replicas non-equalizing

enhanced load _{balance，the}method is

words：cloud

storage

favorable

the Intemet

cost

management

ofThings．

Key

distribution；load

balancing；access

storage；Intemet ofThings；replica

物

网

刻在生大量的数据，需要

些数据

的全局分布式源存

和

模型，能同向大量的

率和高吞吐量的数据服。云存

算的重要基和主要域，能管理大数据

理、分析和

象。有的云存数据管理技包括Google

行采集、理、存、分析和用等操作。物

点数目多，数据模巨大，需要有一个分布式数据

管理体系来管理和整合。的分布式数据

网

用

云

提供高

是

用

系

，

集，高效地在海量数据中存

、

特

局部故障和数据同步更新来的开影响系性能，

使得数据量和点数目均受到限制⋯ ，无法足物

定

PNUTSl31。Amazon

Bigtablet2l，Yahoo

Dynam014】，

Amazon

S3和Microsoft Live Mesh等。另外，数据的

网

境下数据管理的要求。云存是～种基于互

网

收稿日期：20Il_05— 19：修回日期：201I-08r25

基盒目：国家自然科学基金 ff(60074045，643111m4)：湖南省自然科学基金重点

湖南省教育助重点科研 B(I 1A062)

助

助日(11JJ2033)-湖南省科技划 fl(2010JT4053)；

通倌作者：何典(1977_)，男t湖南湘阴人．副教授，从事云存与云算研究l

；0731-88689238：E-mail=．c咖

万方数据

1356

中南大学学 (自然科学版)

第43卷

可靠性、可用性和

性

数据的提供者和使用者至

些特性，云存同一数据复

制多个副本，副本的分布将直接影响到副本存

和更新的开。在一些云存中【5刊，副本所在

的存器通 Hash算法等随机，具有随机

适

数据

的

情况，数据

代价将会减少。

器，会造成集中

关重要。

保

系

考

代价来

存

服

、

低代价存

服

器来存副本，出各服

器

不

系

均衡的象。本文作者提出在最少副本前提下，考

代价和数据被

情况的副本分布方法，并

服

均衡机制，使云存

系

中

用程序的数据

整体均衡。

的分布位置。A．nlazon脚o[41采用静方法行副

代价低，各云存

服

器的

本分布。由于没有考到副本份的地理位置、开

和数据

可能

位置等

高的

，静或随机的数据分布，均

代价【7】。物网中有大量的移

来

云存副本分布及

代价

。移

不断膨和移

限制、算能力限制和无

网中各个点的通信能力不同，

能在物网的每一个部分都得到保。因此，物

中的数据需要有低的

提出一种有成本效益分析的、可伸的云存副本复

数据的存和管理困在于数据量的

本身的固有限制，例如存

接的歇性等。而且，

空

1．1副本数目与

型

副本数目与型是

副本分布方法的前提。

物

的

并不

网

1．1．1副本教目

了容，同一数据至少保留3个副本。如果

存在数据副本不一致，可通投票机制，决出

代价。Bonvm掣¨】

生

的副本。当然，副本数目也可以是任意大于2的奇

数。但多的副本会增加持数据一致性的复性和

制策略。但物网中的移

端在不同

点

数

据

，需要快的响速度，各个

点的数据

开

。在云存

快，同一数据保留多的副本，典型的云存

提供3个副本。

系

中，数据量太大，存

空消耗

代价并不相同，

根据

大的

据网格是有效的分布式数据存

关的研究成果 lo-tt]。但云存

数目均比网格境大。在数据网格算法中，多从

网格点或者网格系的角度出来考效益，例如

代价行副本复制和迁

性能，足要求。数

，与副本管理有

用范和面向

以

移的决策会

失

以

系

1．1．2副本

副本分

型

的

副本、永久副本和期副本(16】：

性能(位于存器上)，永久

副本用来各份数据，期副本用来副本档。假

副本 3，本文同一数据定 2个副本和1

个永久副本，既可以提高数据效率，又能

数据份。本文中，代价是指

用

副本用来提高

服

通

效益函数，或者算任完成

等【12-141。物

要求高的移性和

代价的角度，是从

数

网中用程序的数据

性，无是从用程序数据

系

行

副本

的开的角度来看，物网中的用

存

的

代价，副本位置是指存 2个

器的位置。

副本的云存

的

代价均要着重考，即从用的角度来考

。而且由于数据量急，同一数

服

体的

开

膨

1．2

代价描述

据的副本数目不能太多，多的副本冗余将降低存

的使用效率并加重数据更新的担，需要更高的

空

通

用程序接口(AFD，用程序在数据

云存中的数据。云存数据管理系

求之后，将数据果返回

用程序。整个数据可以看作一系列虚化的程，

用程序而言是透明的。整个系的模型

可用 l来表示。

l中，云存

成，服器的集合作S，各存

服

数据一致性保

网

通信能力。当数据网格中提出的

点数 100个，若副本数目超 20

中无法。云存

一数据提供副本数目很少。例如，Google和Amazon

提供的云存的数据副本均 3个。因此，数据

网格中的副本分布方法不能直接用于云存，特

提供点

接到

等

方法在存

爪【b1，在云存

系

同

服

系

由分布在多个地点的存

服

器

是物

网

境中。

器

服

物

网各个点的存能力和网

状

不同，

不同。同

确定副本分布方法的

西E&，=1，2,---,万。用程序

提供云存接入服

份开不同，所承担的副本存

数据副本被的情况也

任

也

，

的各服提供点，些提供点的集合作A，各服

作

A，i=1，2，⋯ ，棚。将服提供点

存

服

提供点ai

器的

依据之一。如果副本能按照某些条件行分布，并

代价

在矩 c中，即：

万方数据

第4期

fuI ．等：物鞋州珂：境r

均衡的低代价云存数据副本分布

1357

元素属于矩的某2列，并且元素之和最小。

用

程序没有

用程序

的服提供点不参与算。使用集合

提供点的情况：

V={vl，v2，⋯ ，‰}

服

国一．Q

(2)

S．

‘、萎

其中：若Ⅵ卸，表示用程序未在服提供点i

数据，：若vFl，表示用程序在服提供点i

(

数据r。未

的点不需要参与代价

算。由于考整个拓扑构的一部分，减少了

算

的复度，

代价算公式

算

：

果与

情况相符合。数据，最低

三

／蒜Ⅷt(，，功=min{ nxmin{Ck，f，Ck，卅

．API．API

．API

(3)

目√自k=l

／一L、／‘＼、

⋯ ⋯ ＼√

由式(3) 算得到最小

代价．，二砒。，与之

＼√

用程序

的i和_，表示2个副本

分

存放在存

服器S和

I云存数据

模型

弓上。

Data access model in cloud

2．2

合

率

Fig．1

storage

用程序在不同的数据

某一数据，将内

服

提供点多次

～

生

段

数据的副本

代价。由于用程序在不同的服提供点

数据

～；

的次数并不相同，由式(3) 取的存

在来自低代价服提供点的数据

服

器，可能存

Crmx月=

次数少，而

～；

高代价服提供点的数据

代价不一定最小。因此，

代价更合理。

次数多的情况，使得其

率来的

～；～；～

～

Q；Q．．．鼠

瓯瓯；Q；鼠

q@．．．a；鼠

n函；瓯；m

合

算

其中：G』表示服提供点嘶

存

服

器昂

的

使用集合P

用程序某数据，的

率，

代价O=l，2，⋯ ，m；j=l，2，⋯ ，以)。具体的

代价受通信开

利用率和

【8_9】a

、

分配、硬件配置、存容量及

等因素的影响，其文献

如式(4)所示：

算

(4)

芦伽l，P2，⋯ ，m)(O ≤ 1)

其中：P，表示用程序在服提供点i 数据，

的

率，即在

提供点

服

提供点

数据的次数占所有服

数据

次数的比例。p尸0表示在服

2低

代价副本分布

提供点i未

数据r。

将

用程序在服提供点i

某数据的次数

在物网中，考

数据

到

小

和可靠性等限制，

用

☆， P，算方法

：

程序

提高

代价的存服器，以

(5)

效率。而且，物网中点具有移性，当

p一=tdy

』=I

用程序在多个服提供点

些服提供点相的低代价存

根据当前位置

存放位置和是否行迁移的方法，

性的要求。低代价存器的位置可通分析数

数据副本

，

找出

可以将集合中的元素作

算最小代价的加

与

服

器。

行代价算，决定副本

足物

。修改式(3) 行数据r最低代价算和

存

以

网

服

器：

州

服

(6)

允。。t(，，即=rain匹p,xmin{Ck，f，Ck，卅

据

的

史数据来确定，并根据情况化适当

行代价算。

行

l目√自k=l

2．3考

由下例

率的合理性

合

修正，不必

2．1低代价副本分布方法

找到最低代价的2个存

明

率的副本分布的合理性和

正确性。例如，有10个

器，根据式(1)，其

服

提供点，5个存

服

器来布置数据

，的副本，相当于在矩 C中找出m个元素， m个

代价矩 C如下所示：

万方数据

1358

中南大学学 <自然科学版)

第43卷

当

中低代价存

增加，可

更新代价矩，使

价的增加，那么，服器下一次被中成布置

服

器布置某个副本后，其剩

余容量减少，

其

代价增加。若

B侈m

增加的存

服

器

代

他9屹3

9埔9

副本的服器的可能性将减小，使整体的

到均衡。

能达

3．1

代价矩

的

修正方法

由式(6)可知，根据副本被

的情况，包括

5均2

点的位置、

次数、

代价来决定2个副本的位

有尽可能小的代价。当副

3插侈m心m

B●坦4：2“8

5屹¨4擂6

№屹H，掩媳：。D屹"

置，使得副本将来被

如果某数据的

情况肛{1，l，0，1，0，0，0，0，1，

本存放到存

当提高

存放在存

元素修改方法如下；

服

器后，其

增加。

点的

，可以适

存

服

器

各

代价。若副本

0}，使用的代价矩相当于：

13 12 16 13

服

器k和，上，那么代价矩中的相

ll 18

Cs，』=(i+口)×o，J

<7)

其中：毋，，；，≤ ，≤ 珊：a是一个代价增加参数。云

中数据副本数目一般都很大，当存器上增

加副本，a取略大于0的小数即可。

18 12 12

然后，找出具有代价之和最小的2列，如下面矩

中的有下划的数字所示。数据，＆和

器具有最小的代价， 2l。

存

服

于

存

服

3．2基于

引入

均衡机制的副本分布算法

均衡机制的副本分布算法(RDLBLC)，

12 16 13

每一个副本的分布位置可以由算法来确定。作

11 18

充，若某存

倍，即便其

服

器的

超

了目前平均

服

的口

当

18 12 12

代价最小，也不

器作

若在某一段

内，在 4个服提供点

60，100，10和30，

前副本分布的点，

可以保当代价矩增加太

数据的次数分

：

慢

，

的相均衡。声根据存

的比例定。

服器最大

与平均

P=-{0．3，0．5，0．05，O．15}

使用的

代价矩 C相当于：

算法1：引入

(RDLBLC)

均衡机制的副本分布算法

9 5

2—

l—

O—

入代价矩 Ck。。和数据

For

率数只。

to行

6 5

∞：2名

生乞一n—

如∞～跖～

3— O—

to晶)／／最大

O一

IfLoad(Sf)<pXAvgLoad(Sl

to一

根据代价矩 C和式(6) 算得出有最小的

价的2列 &和，各数据提供点

器如表中有下划的数字示。其

990。如果不考率，采用式(3)将

410。可以看出，

代

的存

代价

For f+1

服

使用式(6) 算最小代价厶iD枷

的墨和昌的存

服

相

服器

EndFor

EndIf

EndFor

和

合

存

服

器，生代价l

率的代价算方法能更准确反映

的

情况。

出S，S／／确定副本所在存

服器&和sj

Fork=l

／／

均衡机制

使用式(7)修正和更新代价矩的第i列和第，列

EndFor

基于

代价矩的

均衡

机制

End RDLBLC

3．3副本位置重新分布

考

代价，每次均

取

代价最低的存

当代价矩

生

化后，决定副本位置所依据的

了低

服

器来布置副本，使低代价存

服

器被

的可

代价也生了化。但是，每次副本分布均

能性大大增加，将造成各存

服

器

不均衡。

万方数据

第4期

何典．等：物

网

境下

均衡的低代价云存数据副本分布

1359

代价的存

服

器，而且增加了

服

器的

代

价，更新了代价矩，使副本比均匀地分布到各个

服

相

器上。当大批量的副本被布置到云存

系

，

于初始状。各个存服器代价的增

也

墨

是均衡的。即整个代价矩各个元素的在同比增加。

因此，副本仍分布在与情况相的低代价存

奉

蘧

j蠹；

服

器上，整个系

的

代价仍然小。

lll∈

3种副本分布方法的系

代价比

CPU 2．60GHZ，2．0G

在Pentium(R)Dual．Core

Total∞,CCS8 costs ofthree

distribution methods

Fig．2

replicates

Memory，Windows7，Javal．6 境下，包括一系列

数据存

行了模

个服提供点。每l

予1个随机数，

c中。了便于

【l，loo]之的一个整数，表示在初始状，最大代

价至多是最小代价的100倍。在此基上，模

服

器和数据

服

提供点的云存

系

。

模

境包括30个存

服

器和100

程序

代价，但

率的最小代价

代价与其

3可以看出，代价小的存

担的副本存

分布于不均衡。

根据上述分析和算法，令a--O．01，鼻 1．3，采用

不均衡。 3所示按照

存

服

器和服提供点被

代价，在代价矩

合

存

服

器后各个服

器

数

数据

的

的照。

，代价矩 c各元素的初始

从

服

器其承

任

重。有一定的合理性，但

生

105个数据及其

将随机

位置和率。

副本位置的方法

RS，合

均衡机制后，各个存

比情况如 4所示。

服

器

代价与

率的最小代价

方法

LBS。

MFS，

50次模

均衡的低代价

，求出各次

将采用

均衡机制各个存

的比

些比的平均

4和5

服

器的

数据

代价的平均。上述3种方法生的

2所示。

均衡方法生的数据

率的方法，但相于随机

代

代价与其

如

5所示。其中，

后的分布果。

均衡方法使副本的分布比

器的代价

坐

各

价平均

从

比

如

2可

，

代

比

与

从

比

：

价略高于

合

平均，而且使副本的分布与存

服

方法，减少了一半以上的数据

开。

合

率

存

服

器

然有最小的

用

合

好。

委

存

服

器号

合

率的最小代价方法各服

器

代价与

access

Total ac∞ cost and load ofselection mc出od with minimum COSt

integrating

frequency

FigJ

万方数据

1360

中南大学学 (自然科学版)

第43卷

色。

蠢

存

服

器号

均衡的低代价方法各服器数据

代l价与

with

Total access cost and load ofselection method

load banlancc and low cost

Fig．4

1．2

1．0

酃0·

盎0．

蘧0．

O．2

12 13 14 15 16 17 I 8 19 20 21 22 23 24 25 26 27 28 29 30

存

服

器号

5各数据存

服

器的代价，

的比分布

Values oftotal access cost／load ofdata

SeTVeI'S

storage

Fig．5

(4)使用最少副本数目，最大限度地减少保持数

据一致性和更新的开

。

参考文献：

(1)将

起考，通

云存

位置、

取

率、

代价合在一

a1．Data

代价小的存

服

器，减少

D。Abbadi

E，Antony

【l】

Agrawal

nmnagement

in cloud

challenges

computing in㈣es[C]／／Proceedings

系

中

用程序行数据

的

代价，降低

the 6th International

on Databases in Networked

Workshop

系

数据

开。

Information

Systems．Japan：Springer,2010：l— IO．

(21充分考

物

网中用程序数据

的移

F，Dean J，Ghemawat S，et a1．Bigtabk：a disu'ibutEⅡl

【2】

[3】

Chang

性和

有

性，使副本分布与用

代价，提高用数据

情况相适，具

效率。

for

s缸uctured

Transactions on

da 【J】．ACM

storage system

低的

。Computer Systems，2006，26(2)：205-218．

(3)采用基于

代价矩

的

均衡机制，使

a1．PNUTS．

F，Ramakiishnan＆Srivastava U，et

Cooper

副本能均匀地分布到与

情况相适的低代价存

代价副本分布

的效果，适

Yahoo!’s hosted dam

serving platform[J]．Proc∞din笋ofVLDB

服

器上，避免

考

集

Endowment,2008，l(2)：1277-1288．

Hasumam

中的

，达到平衡各存

服

器

D，Jampani M，ct a1．Dyllalno：跏'窖

【4】DeCandia

of 21st

available

ACM

highly

key-value store[c]／／Procccdings

数据量增加后

代价的化。

万方数据

1361

第4期

何典，等；物

Operating Systems Principles．

Washington,USA：ACM，2007：205— 220．

网

境下

均衡的低代价云存数据副本分布

Verlag，2001：75— 86．

$1GOPS

Symposium

【12】

游新冬，学耀，朱川，等．数据网格中基于效益函数的副

Rowstron

and

caching

A．Druschel

Storage manageraent

本管理策略m．北大学学：自然科学版，2007。28(8)：

1122-1126．

【5】

PAST

large-scale，persistent peer-to-peer storage utility[C]／／

0111

YOU

Chuan。et

XinMong,CHEN Xue-yao．ZHU

a1．Bcnofit

Proceedings of ACM

Symposium

Operating Systems

fanction based

data

Banff．Alberta．Canada：ACM．2001：188— 201．

Principles

replication strategies

grids[f1．Journal

Kubiatowiez

J，Bindel D，Chin

global-scale persistent

Oeeanstom：all architecture for

Interest

Nottheastom

1122 1126．

【6】

University：Natural Scicn∞，2007，28(8)：

011

storage哪．Special

Group

Programming Languages Notices，2000，35(11)：190-201．

Abadi J．Data in the cloud：limitations and

【13】易侃，王汝．分布式任

度与副本复制集成策略研究【J】．

通信学，2010，3l(9)：94— 101．

[7】

【8】

management

of the IEEE

YI妣ⅥrANG Ru— chuan．Decentralized

of task

integration

oppommities[J]．Bulletin

Computer Society

Technical Committee∞Data

with

Engineering，2009。32(1)：3-12．

scheduling

replica placemom suatcgy[J]．Journal

Bonvin

Aberer IC

cost-efficient

Dyuamic

N，papaloarmou

in data

Communic撕ons，2010，31(9)：94-101．

of the 1st

co-allocation model

and deadline in

budget computational grid[J]．

Workshop

[14】

【15】

Zki-gang，XlAO Pang．Anovel[e洲ce

replication

clouds[C]／／Procecdiugs

O／1 Automated Control for Datacenters and

with eonsa'aInts tO

Clouds．Barcelona,

Aberer k

G stir-organized,

Journal ofCcat∞l South

458-466．

Spajn：ACM,2009：49-56．

University ofTechnology,2009，16(3)：

Bonvin

【9】

N，Papaioannou

fault-tolerant and scalable

scheme for cloud

replication

付

，肖

，

城．个体Qos受限的数据网格副本管理与

of the 1st ACM

011 Cloud

Symposium

更新方法[J】算机研究与展，2009，46(8)：1408— 1415．

storage[C]#Proceedings

and

Wei，XIAO

Computing．Indianapolis，Indiana，USA：ACM，2010：205— 216．

Nong,LU Xi-cheng．Replica placement

all

mechanism

individual

for

A’Foster

Kesselman c．The

【10】Chervonak

data d：Towards

and

update

data

QoS-mstricted requirement

architecture

forthe distributed

Research and

management

analysis oflarge

grids[q．Journal

Computer

Development,

and

Stol醒e

scientific

of Network and

Computer

datasets[f1．Journal

2009， 8)：1408— 1415．

Grossrnan

Appficafions，2000，23(3)：187-200．

f16】

L，Gu H’Sabala M，et a1．Compute

clouds

wide a／ca

l(，Foster I．Identifying dy,amlc replication

data of

using

high ix-ff㈣oe nctworks[J】．Future

【1l】 Ranganathan

for

Generation

grid[C]／／Proceedings

strategies

high perfommce

Computer Systems，2009，25(2)：179-183．

the International Grid

Computing Workshop．Berlin：Springer

(

履翔)

万方数据

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

物联网环境下负载均衡的低代价云存储数据副本分布

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

推荐下载

专栏首页