下载:
-
在复杂的网络环境下，多副本不仅为了防止数据丢失，还可以提高存储系统的数据服务质量。分布式文件系统中的副本管理复杂，涉及到副本量控制、多副本选择与定位、多副本一致性保障等多种技术。本文研究数据副本量的控制策略，目的是给类似于智慧城市的应用中存在的大规模公众用户的并发访问需求提供相应的数据服务质量保障。简言之，如何动态配置云存储中数据副本量，才能既满足并发需求又能使资源消耗最低，即云存储系统性能最优化。
副本创建策略可分为静态创建和动态创建两种类型。静态副本数量不随应用场景改变，难以适应多样化环境。动态创建策略会依据一定条件自动产生副本，以提高储系统的性能。目前，动态创建策略主要有以下几种：
1) 最佳客户策略[1]会在一定程度上提高数据的访问效率，减少带宽的消耗。但该策略没有限制副本的总量，可能会降低存储设备的利用率，且副本存储在客户端，如果是极热点数据会导致副本的大量传送而占用大量带宽资源。这种方式一般适用于P2P存储网络，并不适合于建立数据中心的云存储系统。
2) 瀑布式复制策略[2]主要针对具有层次结构的分级存储系统。这种复制策略能够实现系统负载的均衡性，但由于要求存储系统具备层次性网格拓扑结构，不宜应用到云存储系统。
3) 快速扩展策略[3]将副本复制到客户节点经过的所有路径上的每一个节点上，对存储资源提出了苛刻的要求，一般应用于各节点性能较好且均衡的数据网格中。
4) 基于市场应用的副本创建策略根据不同的需求产生不同的控制副本[4]。这类副本创建策略关注的重点是根据存储系统内部资源确定副本创建位置和副本选择问题，未考虑外部需求和副本量的控制问题，不适合云存储系统。
5) 基于访问频率的副本策略[4]以数据文件的访问频率作为增减副本的依据，同时将存储系统开销作为副本创建的判断条件，不适合云存储系统。此外，该策略一般没有副本数量限制机制。
可见，现有的策略普遍是从内部资源的角度考虑副本创建问题，未考虑外部需求。
从信息的角度讲，智慧城市的重要标志就是“随时获取所需信息，据此判断主次，并做出决策”。因此,在技术层面必须有更透彻的感知、更全面的互联互通、更深入的智能化服务(即“智慧”的三要素)作为支撑。这一切的实现必须依赖于智慧城市存储系统对海量“动态时空数据”的高效存储处理。因此，智慧城市信息系统的数据存储需求主要表现在两个方面。
第一，既然智慧城市存储系统由主要面向“静态时空数据”向“动态时空数据”存储转变，必然要求存储系统的性能由原来的主要注重“O”性能(出口带宽)转向“I、O”并重。
第二，智慧城市信息的服务对象正在从某些领域专业人士向公众转变。智慧城市建设的本质目标是“城市让生活更美好，让人更具智慧”。智慧是从数据中来——由数据挖掘出信息，从而形成智慧。所以，智慧城市中的数据内涵不应该存在边界，即城市生活中产生的所有数据都可以是智慧城市中的数据来源，以便形成更大的“智慧”，这需要公众的参与。智慧城市的落脚点是为大众服务的，公众用户的参与和使用才是智慧城市建设的真正意义所在。从存储的角度看，公众用户数量大，为保障良好的用户体验和服务质量，存储系统在并发服务性能上必须有保障。
根据上述智慧城市中数据特点的分析可知，存储系统应该尽可能地提供“低延时，高并发”的存储服务。本文针对这一需求，研究利用云存储系统中的动态副本技术，改善存储性能。
-
以公众服务为基础，内部存储资源丰富的智慧城市云存储中心，不应该依据存储系统内部资源量来创建副本，而必须以满足低延时、高并发服务的角度创建副本数量。因此，为保障效率，必须利用副本选择的预测算法来预测出热点位置，并根据预测的服务需求来合理控制副本数量。理想的状态是：在确定最小副本量(保障数据安全)的基础上，副本的数量应该与预测文件的流行度结合起来，根据预测流行度动态调整副本数量。
-
要运用动态副本管理策略，必须先确定文件的最小副本量。最小副本量的确定以云环境中的文件可用概率和用户期望的文件可用性为度量依据。
设P(Ni)为节点Ni的可用概率(即节点可达)，
设P(F)为文件F可用概率。不失一般性，假设文件F分割为m块，F={b1, b2, b3...bm}分配到不同的数据节点。
设P(Bj)为块bj可用概率，
一个数据块只有在所有副本块完全失效的情况下才失效，所以数据块bi的失效概率可以表示为：
(1) 因此，数据块bi的可用概率可表示为：
(2) 为了读取整过文件F，必须保证m块全部可用，因此文件的可用概率为：
(3) 对于同一文件中的m个数据块，均有相同的副本数据量，即有：
(4) 由式(3)、式(4)得：
(5) 设用户期望的可用性为U，因此为满足性能要求，必有：
(6) rmin即可根据式(6)计算。rmin是在系统中平均节点故障概率基础上满足预期有效性的副本最小需求，是保证数据可靠性的基本要求。当有节点故障出现而导致系统副本量小于rmin时，系统会自动增加副本。
-
从客户端看，副本数量应该能够在极端情况下满足客户的访问需求。设一段时间τ内，系统总的用户数为Nuser；一维向量F=[p r s]为某文件对应的各项参数，其中，p表示该文件的请求概率，r表示该文件的副本数(r分布在Nr个不同的节点上，访问针对文件，不考虑文件分块的情况)，s表示该文件大小；假设云中负载均衡(云存储应该基本满足此条件)，在时间τ内，每个节点应该提供的平均带宽为Bave，节点Ni的带宽为BNi。
要保障用户对文件访问的出口带宽，必有：
(7) 在初始条件下BNi是固定值，而Bave可以认为长时间内变化很小，因此，因此满足服务需求的最经济副本数量rQ可以表示为：
(8) 从式(8)可以看出，rQ完全依赖于文件访问概率以及时间段τ。在大数据集中文件的访问概率一般使用文件的访问频率来近似表示，也习惯性成为文件的流行度。智慧城市中的数据服务是一种典型的Web大数据应用，Web大数据集中文件的流行度的研究和选取的统计时段有很大关系，因此rQ和流行度统计的准确性正相关。
-
当前，Web大数据集中数据流行度的预测有两种方法，一种是基于Zipf-like分布的流行度预测模型，一种是基于马尔科夫链的预测模型。它们各自的适应性和缺点也是明确的，Zipf-like分布模型对于大数据集的长期流行度预测有优势，马尔科夫模型则刚好相反，对短时期内数据访问概率预测较为准确。因此，笔者采用长期流行度和短期流行度结合的双时间粒度预测的副本量控制算法(double time granularity prediction algorithm,DTGPA)。
1) 长期流行度预测。
文献[5]研究发现网页访问分布接近Zipf-like分布。文献[6]研究指出，Web请求近似服从Zipf-like分布模型，且特征指数在0.64~0.83之间。文献[7]发现多媒体文件被访问的次数服从Zipf-like 分布。文献[8]证实微软虚拟地球的瓦片请求也服从Zipf-like分布。文献[9]根据GlobeSIGht系统中的服务器日志证实了文献[8]的结论。智慧城市中的“动态时空数据”是一种典型的Web大数据集数据应用，因此其长期流行度可以使用Zipf-like分布模型来预测。
Zipf-like定律描述为:
(9) 式中，C是一个常数；i为某文件被访问次数的排列位次；α为大于零的参数；Pi是访问次数排第i位的文件的访问概率。因此，根据Zipf-like定律预测访问概率，只需统计一段时期内各文件的访问次数即可。将式(9)代入式(8)可以得到根据Zipf-like分布模型计算的满足服务需求的最经济副本数量rzipf为：
(10) 2) 短期流行度预测。
文献[10]首次提出将马尔科夫链应用于预测Web用户数据访问，取得良好效果。文献[11]采用多阶转移矩阵，提高了模型的预测准确率。文献[12]提出了更加准确的多马尔科夫链预测模型。马尔科夫及其改进模型的优点在于短期预测比较准确，所以在信息技术领域马尔科夫模型主要应用于Web缓存预取等短期预测方面。
马尔科夫链模型可以表示为一个三元组，M(D,A,Π(k)) ，其中D是一个随机变量，值域是{d1, d2, d3,…,dn}(本文应用中每个di对应云中的一个数据，称为模型中的一个状态)。A为一步转移概率矩阵，pij=P〈Dt=dj|Dt-1=di〉表示由状态di转移到状态dj的概率；Π(k)是k时刻状态分布概率，即每一项pi(k)=P(Dt-k=di)表示在k时刻各个文件的访问概率。Π(0)表示初始状态。算法的关键就是利用Π(0)和A的值来预测任意时刻k各个文件的访问概率，即Π(k)。
(11) 
(12) 按照时间顺序t1、t2、t1、…、tk，记录一个用户在云中访问的所有数据，就能得到一个随机变量D的一个取值系列；记录m个用户的访问历史，就能得到m个取值系列作为学习数据的集合{D1, D2, D2,…,Dm}，采用极大似然估计即可算出马尔科夫链模型中的所有参数。
(13) 
(14) 其中，Sij表示学习数据集中状态对(di, dj)出现的次数。计算出Π(0)和A，由递推公式可以计算出任意时刻的状态分布：
(15) 为提高预测准确率，可采用多阶加权组合模型，以充分利用用户的历史访问信息：
(16) 其中，Ah表示马尔科夫链的h阶状态转移矩阵；ωi是加权值，满足等式ω1+ω2+…ωh=1的要求。实验证明，h的取值越大，模型预测越准确，当然需要的计算量也越大。
将式(16)代入式(8)可以得到基于马尔科夫链模型计算的满足服务需求的最经济副本数量rmarkov为：
(17) 由式(10)和式(17)得到基于双时间粒度的副本量控制算法的动态副本数rD为：
(18) 式中，max表示取最大值运算。同时还限定rD的最大值不能超过云存储系统中的数据存储节点数,即单一存储节点只能存放一个副本。
-
本文以云计算仿真环境Cloudsim为仿真实验平台。云存储系统中存在存储能力均为100 G的200个存储节点，每个节点的最大带宽是133 M/s。网络环境为1 000 M以太网，数据资源为100 M大小的20 000个数据源文件。实验环境模拟多个云用户的访问请求，每个节点按照一定的模式产生数据访问请求。仿真用户请求到达服从泊松过程，请求到达率λ设为5；用户对数据的访问符合Zipf-Like分布，并默认地将α参数设为0.9。
-
1) 云端采用静态副本和本文动态副本的对比测试情况。分别测试多个用户从云端访问取出多个数据文件所需的最长时间和平均时间，每个用户从云端取出1 000个数据，记录的单个数据获取的最长时延和单数据获取平均时延分别如图 1和图 2所示。可以看出，相比于三副本的静态副本策略，本文提供的策略在最大时间延迟方面最高降低了42.3%(并发数为1 000)，在平均访问时间方面也降低了34.44%，且呈现出并发数越高、性能改善越显著的趋势。
图 1 单数据获取最长时延对比图
Figure 1. Comparison Chart of Maximum Delay in Single Data Acquisition
图 2 单数据获取平均时延对比图
Figure 2. Comparison Chart of Average Delay in Single Data Acquisition
2) 存储资源占用情况对比测试。设用户期望的最小可靠性为0.95，云中单个节点的可靠性为0.8，根据此参数要求，依据式(6)计算的最小副本量为2。在这种条件下对比不同副本策略下存储空间的占用情况(见图 3)(以单副本条件下占用的存储空间为单位1)。图 3中的BF是前文介绍的基于频率的预测算法[4]，该算法没有考虑副本量的上限控制，系统资源充足时，副本的数量将得不到控制。本文算法副本增长缓慢，其占用的存储资源和Hadoop[13]采用的静态副本相差无几，能有效应对高并发需求。
图 3 不同算法平均副本数量变化情况
Figure 3. Changes of Average Replica in Different Algorithms
-
本文针对云存储中采用的静态副本在应对大规模并发访问方面的不足，提出了一种动态副本策略。该动态副本算法中，最小副本数量的决定因素是用户期望的文件可用性概率，副本数量动态调整是依据预测的文件访问概率和现有的服务资源量来进行的。仿真实验结果表明，相比原有的静态副本，基于双时间粒度预测的动态副本机制在应对突发的大规模并发访问方面有显著优势。同时，相比常规的基于访问频率的动态副本，本文方案的存储资源占用量更少。
-
摘要: 传统分布式文件系统中的副本量控制策略，主要是从内部资源的角度考虑副本的创建，未考虑外部需求的变化。这种策略不适合部署在以服务为基础、内部存储资源丰富的智慧城市云存储中心上。提出了一种结合数据安全（最小副本量）和服务需求（最优副本量）的副本量控制模型。模型中采用基于双时间粒度预测算法预测文件流行度，依据文件的流行度和系统资源动态调整云中副本数量。仿真实验结果表明，本文采用的动态副本机制在应对突发的大规模并发访问方面有显著优势；同时，相比常规的基于访问频率的动态副本，本文策略的存储资源占用量更少。Abstract: The number of replicas in the control strategy of a traditional distributed file system is calculated based on internal resources while changes in external demand are ignored. However, this strategy is not suitable for deployment in a service-based, resource-rich internal storage "smart city" cloud storage center. We propose a control model for the number of replicas ,which combines data security(the minimum amount of copies)together with service needs (best copy volume). A predictive algorithm based on double time granularity is included in this model to predict the popularity of a file. In addition, the number of copies in the cloud adjusts itself dynamically according to the popularity of a file and system resources. Simulation experiment results show that the accuracy of double time granularity forecasting is greatly increased. Compared to the original static copy, a dynamic copy mechanism based on double time granularity prediction has a significant advantage in response to sudden large-scale concurrent accesses and its storage resources occupancy rate is low.
-
Key words:
- dynamical replica /
- cloud storage /
- prediction /
- smart city
-
图 1 单数据获取最长时延对比图
Figure 1. Comparison Chart of Maximum Delay in Single Data Acquisition
图 2 单数据获取平均时延对比图
Figure 2. Comparison Chart of Average Delay in Single Data Acquisition
-
[1] 李静,陈蜀宇,吴长泽. 一种基于安全的网格数据副本策略模型[J]. 计算机应用,2006,26(10):2282-2284 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJY200610006.htm Li Jing,Chen Shuyu,Wu Changze. Model of a Data Replication Strategy Base on Security in Grid[J]. Journal of Computer Applications, 2006,26(10):2282-2284 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJY200610006.htm [2] Ranganathan K, Foster I. Identifying Dynamic Replication Strategies for a High Performance Data Grid [C]. The Second International Workshop on Grid Computing,Denver, 2003 [3] 刘田甜,李超.云环境下多副本管理综述[J].计算机研究与发展,2011,48(增刊):254-260 http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ2011S3036.htm Liu Tiantian, Li Chao. Multiple Replicas Management in the cloud Environment[J].Journal of Computer Research and Development,2011,48(Suppl):254-260 http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ2011S3036.htm [4] 林承达,孟令奎,彭溢. 无线GIS空间数据动态副本管理研究[J]. 武汉大学学报·信息科学版,2007, 32(3):263-266 http://ch.whu.edu.cn/CN/abstract/abstract1852.shtml Lin Chengda, Meng Lingkui, Peng Yi. On Dynamic Replication Management of Wireless GIS Spatial Data[J].Geomatics and Information Science of Wuhan University, 2007,32(3):263-266 http://ch.whu.edu.cn/CN/abstract/abstract1852.shtml [5] 李德仁,姚远,邵振峰.智慧城市中的大数据[J]. 武汉大学学报·信息科学版,2014,39(6):631-640 http://ch.whu.edu.cn/CN/abstract/abstract2999.shtml Li Deren, Yao Yuan, Shao Zhenfeng. Big Data in Smart City[J].Geomatics and Information Science of Wuhan University, 2014,39(6):631-640 http://ch.whu.edu.cn/CN/abstract/abstract2999.shtml [6] Breslau L,Cao P ,Fan L ,et al.Web Catching and Zipf-like Distributions :Evidence and Implications[C]. IEEE INFOCOM, New York,1999 [7] Chesire M ,Wolman A,Voelker G,et al. Measurement and Analysis of a Streaming Media Workload[C]. 2001 USENIX Symp on Internet Technologies and Systems, Francisco,2001 [8] Fisher D.Hotmap: Looking at Geographic Attention[J].IEEE Transactions on Visualization and Computer Graphics, 2007,13(6) :1184-1191 doi: 10.1109/TVCG.2007.70561 [9] 王浩,潘少明,彭敏,等.数字地球中影像数据的Zipf-like访问分布及应用分析[J]. 武汉大学学报·信息科学版,2010,35(3):356-359 http://ch.whu.edu.cn/CN/abstract/abstract873.shtml Wang Hao,Pan Shaoming, Peng Min, et al. Zipf-like Distribution and Its Application to Image Data Tile Request in Digital Earth[J].Geomatics and Information Science of Wuhan University, 2010,35(3):356-359 http://ch.whu.edu.cn/CN/abstract/abstract873.shtml [10] Zuckerman I, Albrecht D W, Nicholson A E. Predicting User'S Requests on the WWW [C]. The 7th Int Confon User Modeling, Berlin,1999 [11] Borges J, Levene M. Datamining of User Navigation Patterns [C]. Workshop on Web Usage Analysis and User Profiling, Berlin,1999 [12] 邢永康,马少平.多Markov链用户浏览预测模型[J],计算机学报,2003,26(11): 1510-1517 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200311012.htm Xing Yongkang, Ma Shaoping. Modeling User Navigation Sequences Based on Multi Markov Chains[J]. Chinese Journal of Computers, 2003, 26(11):1510-1517 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200311012.htm [13] Chang R S, Chang H P. A Dynamic Data Replication Strategy Using Access-Weights in Data Grids[J]. The Journal of Super Computing, 2008, 45(3): 277-295 http://cn.bing.com/academic/profile?id=2145781941&encoded=0&v=paper_preview&mkt=zh-cn -
点击查看大图
图(3)
计量
- 文章访问数: 1210
- HTML全文浏览量: 50
- PDF下载量: 312
- 被引次数: 0
