第
31
卷增刊
2
2011
年
12
月
计算机应用
Joumal
of Computer Applications
句,,缸
'A
1
1)
平啊
A
U
工
qu
剧
'Anu
句
3
-A
O
VV
文章编号:
1001 - 9081
(2011)
S2
-0039
-
04
基于灰色马尔可夫链预测模型的
HDFS
云存储副本选择策略
徐挠勇,潘郁,丁燕艳
(南京工业大学经济与管理学院,南京
211816)
摘
要:在
Hadoop
分布式文件系统
(HDFS)
云存储环境下,网络带宽和节点性能有限且动态变化,现有的副本选
择策咯无法根据环境的变化选择最合适副本。针对这一问题,提出一种综合考虑了网络带宽、节点1/
0
性能以及节点
存储空间等因素,基于灰色马尔可夫链预测模型的副本选择策略,以此在系统可用性和负载均衡性之间寻求一个平
衡。最后通过仿真实验,验证了该策略的可行性与有效性。
关键词:云存储;副本选择;灰色马尔可夫链
;Had
∞
p
分布式文件系统
中图分类号
:T
凹
93
文献标志码
:A
Strategy of replica
selection
based
on
grey
1\也
rkov
chain
prediction
model
in
HDFS
XU
Xiao-yong
,
PAN
Yu
,
DING
Yan-yan
(Sc
仇。
1
0/
Ecorwmics
and
Managemem
,
Nanjing
University
0/
Techrwlogy
,
N
,
α
njing
1ia
,
啄
'SU
211816,
China)
Abstract:
In Ha邮
p
Di
strihuted Fùe
S:
严
tem
(HDFS)
训班
rethene
士
work
bandwidth
and
严
rfonnance
of
IXJ(如
are
limited
and
changed
句
namiω
助,
the current
strat
咽
of
replica selection can
not
a
均,
t
the most suitable
replica
缸:co
rding
to the
chan
伊
of
the
environmen
t.
Ai
ming
at
也
is
prohle
m,
a
new
s
田
tegy
of replica selection
based
on
grey
地
rkov
chain
pr
叫
iction
IIJO(如
l
耐
ch
takes
netwOIX
band
wi
dth,
performance of
1/
0
and
sto
吨
es
归
ce
ofn
仪Ies
into
the
∞呻,
rehensive
∞
nsideration
was
p
叩时
ωseek
a
baIanCe
between system
us
抽出
ty
and load balancing.
Simulation
缸
perimental
results prove the validity
and
practiωb
山
tyof
由
is
new
跑回
íegy.
Key
words:
cloud storage; replica selection; grey Markov chain; Hadoop Distrihuted File System (HDFS)
0
引言
云存储
(Cloud
Storage)
是从云计算
(Cloud
Computing)
概
念上延伸发展出来的一个新的概念,它是指通过集群应用、网
格技术或分布式文件系统等功能,将网络中大量各种不同类
型的存储设备通过应用软件集合起来协同工作,共同对外提
供数据存储和业务访问功能的一个系统。云存储的优势在于
海量存储、高性能/离访问量、低成本、超强的可扩展性、不受
具体地理位置所限、基于商业组件、按照使用收费、可跨不同
应用等。因此,云存储的兴起给整个存储领域带了根本性的
变革,受到广泛的关注和支持。目前一些企业已经推出了各
自的云存储系统,如
G
∞
gle
的
GFS
、
Yah
∞的
HDFS
、
Amazon
的
S3
和
IBM
的"蓝云"等。其中,
Hadoop
分布式文件系统
(Had
∞
p
Distrihuted File System,
HDFS)
是
Apache
组织开发的
一个开源云存储系统,可以运行在廉价硬件设备上,非常适合
于学术研究及其商用开发,因此这里研究的云存储副本选择
策略是基于
HDFS
框架的。
云存储系统由于运行在普通硬件设备上,节点失效、数据
损坏难以避免,因此云存储系统采用冗余存储来达到系统容
错目的,提高系统可靠性。冗余存储指的是对同一数据块进
行多份数据副本备份,当其中一个副本失效,可以读取其他副
本进行替代,从而保证系统的高可靠持续运行。其中,对于读
取副本的选择是云存储研究的一项重要内容。副本选择策略
的优劣将直接影响到系统性能、负载平衡以及可靠性。
在网格环境下对副本选择问题的研究很多。首先一种常
用的方式是利用经济模型,例如
Carman
等人
[1]
和
Bell
等
人
[2]
采用拍卖模型,客户端向副本发出购买信息以及标明价
格,副本通过竞价的方式提供给客户端,最后价格最低即网络
传输消耗最低的副本提供给客户端。
Rahman
等人
[3J
使用博
弈模型,设计了各个副本的行动和博弈策略,得到包括副本和
客户端在内的所有参与者的最优战略组合,即达到纳什均衡。
预测模型也是一种非常常用的方式,例如
Sudharshan
等人
[4J
提出了一种基于网络负载变化以及
GridITP
数据传输历史信
息的回归模型,但是这种预测模型的缺点在于需要收集大量
历史记录。而李静
[5]
分析了影响数据副本选择的因素,将灰
色系统理论应用于副本响应时间的预测,建立
GM(
1
,1)灰色
动态拟合模型。现代集群智能算法在该问题上也有了一定的
应用,陈蕾等人
[6J
分析了影响副本选择性能的
4
个主要因素:
网络带宽、存储副本节点的负载完成率、磁盘1/
0
读取速度以
及副本响应时间,设计了基于蚁群算法的副本选择策略。而
张新亮等人
[7J
在价格机制模型和并行数据传输的基础上,采
用了遗传算法实现副本的创建和选择。
而在云存储环境下,对副本选择策略的研究相对较少。
主要原因是云存储系统大多运行在低廉的普通硬件设备上,
其网络状况以及节点性能都很有限且不稳定,带宽、磁盘
νo
读取速度以及副本响应时间等因素波动都比较大,而网格环
境中经常使用的依据以上各因素制定的动态副本选择策略在
这种云存储环境中会导致计算复杂度加大,反而影响系统的
可用性,降低了副本择优的效果。因此,现在各大云存储系统
倾向于采用静态的副本选择策略,例如
HDFS
采用了客户端
选择与之拓扑臣离最短的副本的策略问。针对这种情况,建
立了基于灰色马尔可夫链预测模型的副本动态选择策略,对
现有的
HDFS
框架的云存储系统的副本选择策略进行了改
进,使之能根据环境状况的变化,相应地选择合适的副本,既
保证了读取速度又保证了系统的负载平衡,以此在系统可用
性和负载均衡间寻找到一个平衡。
收稿日期
:2011-04-02;
修回日期
:2011-10-12
0
基金项目:国家自然科学基金资助项目
(70801036)
。
作者简介:徐挠勇(1
986-)
,男,江苏无锡人,硕士研究生,主要研究方向:智能算法、商务智能;
潘郁
(1955
- )
,男,江苏南通人,教授,博
士,主要研究方向:计算管理、商务智能;
了燕艳
(1987
- )
,女,江苏无锡人,硕士研究生,主要研究方向:智能算法、商务智能。。