云存储中基于竞标模式的副本管理策略

张 鸿，林 兵，刘漳辉，2

(1．福州大学数学与计算机科学学院，福建福州 350116;

2．福建省网络计算与智能信息处理重点实验室，福建福州 350116)

0 引言

云计算具有超大规模、高可扩展性、高可靠性、虚拟化、按需服务和价格低廉等特点，能够很好地满足海量数据存储的要求．云计算使得用户不必构建自己的数据中心，他们只需要根据自身需求支付一定的费用，就能够把数据存储到云服务商的数据中心上．在未来4年内，云服务的市场规模将从现在的174亿美元增长到442亿美元，其中，云存储的市场比例将从目前的9%增长到14%［1］．然而，在当前的云存储数据中心中，任何类型的故障都是很常见的，如电源故障，机架故障，网络攻击，硬件驱动挂机等［2］，从而使网络中单个节点失效成为一种常态．GFS和HDFS文件系统用生成多个数据副本的方法来提高数据可用性［3］．但副本也会带来几个问题:副本集的统一性问题，副本均衡负载问题以及合适的副本数量及放置问题．副本数量的增多可以有效提高数据的可靠性，但副本的过度增加会导致数据中心运营商的成本过高，导致经济效益下降．云计算服务的基础设施和数据中心一般分布在世界范围内的适宜地点，因为用户的访问请求来自全球范围内的不同的地方，为了兼顾用户的访问需求和数据中心的负载均衡，要求副本的放置策略要有效合理．如果副本放置不当，如集中于某个地区，则会导致远处的用户数据访问带宽下降，网络延迟;如果副本的放置过于分散，则会导致副本的管理和维护成本代价过高．应该如何放置和管理这些副本，以有效地分配工作负载，保证负载均衡，提高系统性能?

通过副本提高数据的访问率已经在许多存储系统中应用，如P2P系统［4］、分布式数据库［5－6］和分布式文件系统［7－8］．然而，在这些系统中，都是采用静态副本机制，副本的数量和位置都是事先决定的，这样会消耗不必要的成本代价．在动态副本机制中，也有很多文献对此做了研究．Agnesswaran等［9］提出了一种副本管理策略，通过建立一个模型，来维持数据可用性水平．该方法首先根据用户要求的可用率计算每个文件块需要被复制的数量，然后根据网络带宽和存储成本选择副本放置的最佳节点．Ranganathan等［10］提出了动态模型驱动的副本策略，在这个机制中，在P2P存储系统的对等两端都运行这个模型区计算文件所需要的最低副本数量．IFoster等［11］在数据网格中提出了动态副本策略，根据用户的不同访问模式来应用不同的副本策略．Mistarihi等［12］提出应该根据数据块的请求次数和生命周期来选择最好的数据块进行复制．以上这些文献都是在分布式存储系统的背景下展开的．Wei等［13］提出了一种有效节约成本的动态副本管理模型CDRM，这种模型兼顾了可用性和副本数量．在保证所需可用性的基础上，CDRM维持了所需的最小副本数量．副本的放置位置是由数据节点的容量和阻塞概率决定的．根据负载变化和节点容量来调整副本数量和位置．Jeon等［14］提出检测用户的数据访问模式的变化来动态改变副本的最优复制策略，因为副本策略大多与用户的访问模式有密切的关系．但是，以上文献没有考虑到云存储系统中网络的广域性和动态性等特点，未对副本在云环境系统中的成本和效率做充分考虑．

本文提出一个云存储系统下基于竞标模式的云存储副本管理策略来解决上述问题．将竞标模式和云存储中的副本结合起来，在文件的可用性达不到用户的要求时，举行竞标，将新的副本放置在最适合的节点上面．同时，在副本放置完之后，优化和管理副本的分布情况．这个方案能够找出适合副本放置的节点且动态适应环境的变化，在满足用户需求的基础上，缩短用户的响应时间，保持整个存储系统的稳定．仿真实验表明，该方案能够显著提高系统性能．

在文中，首先提出文件系统的存储结构;然后，提出基于竞标的副本管理策略和实验环境，并给出算法的实验结果以及比较分析，以证明该分配策略的有效性;最后，指出副本策略在未来将面临的挑战以及需要开展的研究工作．

1 云存储模型

云存储模型采用谷歌文件系统(Google file system，GFS)的星形拓扑结构．GFS中包含主节点(master)和多个子节点(chunk nodes)，主结点保存了整个文件系统的名字空间、客户端对文件的访问及数据块到子节点的映射等，具体的数据存储工作由子结点负责［15］．主节点和子节点之间通过心跳包来通信，同时，还把客户端的操作指令发送给子结点，如图1所示．当客户端向文件系统读取数据时，首先，跟主节点通信，获得具体保存数据块的子节点信息，然后，客户端再和子节点建立数据传输连接，直接从子节点下载数据．将数据分割成大小为64 MB的数据块存储在子节点上，每个数据块初始化3个副本存放在子结点上．主节点先随机挑选某个副本为主副本．在系统运行的时候，主结点开始收集每个子节点和数据块的信息，包括数据的分布信息、子节点的当前负载量信息和客户端访问数据的信息等等．最后，主节点就可根据本文的策略动态调整副本的分布情况．

图1 云存储系统拓扑结构Fig．1 Cloud storage system topology structure

2 基于竞标模式的副本管理方法

在有底价竞标过程中，存在卖家、买家、竞标时间、竞标底价和竞标价格等几个重要的组合部分．卖家会根据买家出的竞标价格和自己的底价来决定竞标物品的最终归属权．在云存储环境中，副本的放置是一个棘手的问题，如果副本的位置与用户相距太远，则失去了数据副本的优势，如果把所有数据副本放置在数据请求者周围，则会提高查询请求的响应时间和负载均衡．将副本放置过程和竞标模式结合起来，通过卖家和买家的互动，使副本放置在最合适的地方．在副本放置完毕之后，主节点实时监测各数据的可访问率情况，动态管理副本的分布情况．

在竞标模式中，有卖方和买方两种角色，将云存储系统中的主节点定义为卖方，将参与竞标的子节点定义为买方．在副本放置的竞标过程中，卖家即主节点发起竞标活动，出售副本的放置权，符合竞标底价的买家即子节点参与竞标，取得副本的放置权．在节点获得副本的放置权之后，开始副本的管理过程．

2．1 竞标开始时间

在云计算中，用户都会与提供商签订一份服务等级协议(service layer agreement，SLA)，里面规定了用户对云提供商的一些基本要求，其中就有云服务商保证给用户的最低数据访问可用率aval．假设数据对象i有n个数据副本，即S=(R1，R2，R3，…，Rn)，每个副本存放在不同的服务器上，每个副本的失效率为Fj，这些事件彼此可能是相互独立或相关的，不失一般性，假设事件F1，…，Fk是独立的，而事件Fk+1，…，是具有相关性的．数据对象i不能被访问的概率为:

为了简化问题，假设每个副本的可访问率都为RAi，j(j∈n)，每个副本失效事件的概率是独立的，则数据对象i的n个副本提供的综合可访问率RAi可以由下式得到:

所以，当n个副本提供的综合访问率不能满足提供商保证给用户的可用率时，即RAi＜aval，master节点就开始准备生成数据i的新的副本，以提高数据i的访问率．这就是副本放置的竞标活动的开始．

2．2 竞标底价

在有底价的竞标活动中，底价是卖家对物品所愿意接受的最低价格．这个价格表示着卖家对买家的要求．在副本放置的竞标过程中，也有相类似的定义．

副本的分布情况与用户访问数据的响应时间、维护副本一致性操作的代价有着密切的关系，如果某个数据的副本集存放得过于集中，那么远程用户的数据访问响应时间势必会增加;相反，如果副本集的分布过于分散，在维护副本数据一致性时代价会非常昂贵．所以，为了给用户一个良好的用户体验，系统要严格控制副本集的分布情况．副本集的分布情况主要由副本的实际地理分布和副本之间的网络带宽决定．用副本分布程度RD(replication distribution)来描述副本的放置情况是分散还是集中．

副本之间的地理距离可以用distance来表示，distancej，k表示数据对象i的第j个副本和第k个副本之间的距离．副本之间的距离可以用副本所在的子结点之间的地理距离表示，子节点的地理位置按照文献［16］中副本位置的表示方法，定义为:

NLOC=(国家编号，地区编号，数据中心编号，机架编号，物理机编号)

式中:国家和地区编号采用电话区号表示;数据中心编号采用数据中心名称缩写进行区分;机架编号与物理机编号均为数据中心内部统一编号．用15位二进制表示两个节点之间的距离，如果两个节点之间的国家编号不同，则节点距离的第1到第5位(从左到右)置为1，后面都为0，否则就把1到5位置为0;如果两个节点之间的地区编号不同，则节点距离的第6到第9位置为1，后面都为0，否则就把6到9位都置为0;其余以此类推．

表1为节点i与节点j的距离．在表1中，节点i为中国福建省福州市超级计算机数据中心的第01号机架上的03号物理机，节点j为中国福建省厦门市厦门大学数据中心的第02号机架上的02号物理机，两点间的物理距离定义为distancei，j=00000111100000(二进制)=960(十进制)．

表示M×N的数据和服务器关系的放置矩阵，如果一个数据对象i的副本存放在服务器j上，则Lij=1;若没有，则Lij=0．因此副本集S=(R1，R2，…，Rn)的副本之间所有带宽的总和可以由下式得到:其中:是一个N×N的上三角矩阵，矩阵中的元素代表任意两个服务器之间的网络带宽;sum函数为矩阵所有元素的求和．

表1 节点i与节点j的距离Tab．1 Distance of node i and node j

所以，数据对象i的副本集合S=(R1，R2，…，Rn)的副本分布程度可由下式得到:

图2 副本分布与可用性和成本的关系Fig．2 Availability and cost varies with replica distance

式中:RDi是原先副本集的分布程度;RD'i是假设某个节点放置副本Rn+1后，副本集更新之后的副本分布程度．要让副本集的副本分布程度接近标准副本分布程度RDstandard的节点才有资格参与竞标．

2．3 竞标价格

在有资格参与竞标的节点中，要提供竞标价格BP(bidding price)给卖家，对于参与竞标的子结点来说，其影响副本性能的主要属性包括:节点的请求率，节点的平均服务时间，可靠性，网络带宽和磁盘空间负载，用五元组N=(λ，τ，f，bw，load)表示．将竞标价格和这五个属性结合起来，则有公式:其中:∂1、∂2、∂3、∂4和∂5分别为节点的请求率、节点的平均服务时间、失效率、网络带宽和磁盘空间负载在竞标价格中所占的权值．在本研究中，利用层次分析法(AHP)的核心思想［17］对这些指标进行量化处理，以确定这些权重的值．根据副本节点的性能属性偏好，结合1～9比率标度法(具体含义见表2)，对这五个属性先构造判断矩阵．构造完的判断矩阵如下所示:

表2 1～9比率标度法含义Tab．2 1 ～9 ratio scale method

2．4 竞标管理过程

在竞标的结束阶段，主节点需要查看系统中每个数据的可访问率，如果某个数据i的可访问率没达到用户的要求，则开始新一轮的竞标活动．若数据i的可用性得到用户的满足，则主节点就要开始管理和优化本系统的副本分布情况，以降低副本集的成本．

在数据对象i的副本集提供的访问率高于用户期望的数据可用率时，主节点找出访问率最低的副本，如果删除这个副本后，数据对象i的可用性依旧得到满足，则删除该副本．如果删除该副本后，数据对象i的访问率不能达到用户的要求，则不能删除该对象的某个副本，此时要考虑降低访问率的副本j，在选取准备迁移的副本j之后，寻找新的节点存放副本，此时又回到了副本放置的竞标过程．整个流程如图3所示．

图3 副本管理流程图Fig．3 Replica management flowchart

3 实验与性能分析

3．1 实验环境

用CloudSim［18］作为实验平台，进行仿真实验．模拟出10个数据中心，每个数据中心随机分布着10到100个物理机，每个物理机为2．8 GHz的Intel Pentium4核CPU，1 GB或2 GB的内存，80 GB或160 GB的硬盘．虚拟机部署在物理机上，虚拟机的操作系统是Ubuntu 12．04以及java版本是1．6．0．每个数据被分割为64 MB的数据对象，初始情况为每个对象没有副本随机分布在子节点上．各对象访问概率服从参数为λ的Poisson分布，访问量和访问类型服从Pareto(1，50)．由于仿真实验中网络的通信情况良好，所以将副本可用性aval设置为0．8．同时，在CloudSim平台上运行副本的传统静态策略和文献［13］的CDRM策略，以用作对比．

3．2 实验结果与分析

1)负载均衡．通过计算每个节点的负载方差来衡量系统的负载均衡．图4描述了本文策略在用户访问过程中的负载方差．可以看到，负载方差的变化相对平稳且基本保持在12%以下．图5展示了本文副本策略与传统静态副本策略和CDRM副本策略的比较结果．可以看到，在副本数量不是很多的时候，三者并没有很大的差距，有一点的随机性;在副本数量为60时，其他的两个副本策略的负载方差低于本文的策略，因为本文副本策略在竞标过程中需要耗费网络带宽;随着副本数量的急剧上升，本文策略在负载方面低于其他两种副本策略的负载方差．

图4 负载方差随时间间隔的变化Fig．4 Load variance varies with time interval

图5 负载方差随副本数量的变化Fig．5 Load variance varies with replica number

2)响应时间．为研究本文的副本策略的性能，在仿真云数据环境中安排了数量变化的负载来查看三种策略的不同响应时间．图6显示了三种不同策略的响应时间，可以看到，随着工作负载的数量增加，与其他两种策略相比，本文策略的响应时间明显减少，这说明了本文策略在负载数量多时的有效性．因为本文策略可以控制副本的分布范围，能有效地减少用户的远程文件访问数．

图6 负载数量变化的响应时间Fig．6 Response time varies with load

图7 时间间隔下的网络带宽负载Fig．7 Network bandwidth load varies with time interval

3)网络带宽．在本文副本策略与传统静态策略运行过程中的某一段时间，在Δt时间间隔下监测系统中的网络带宽负载．图7为不同时间间隔下的网络带宽负载，从图中可以看到，传统静态策略的网络带宽负载波动相对平缓，但本文副本策略在某些时刻突然占用了极大的网络带宽，因为这些时刻是竞标活动周期，在这周期内，竞标过程的通信要耗费比较多的网络带宽．在某些时刻牺牲一点网络带宽来提升整个系统的性能是值得的．

上述实验结果表明，在消耗一点网络带宽的代价下，本文副本管理策略可以有效提高用户访问数据的响应时间和负载平衡．

4 结语

对云存储环境下的副本问题提出了基于竞标模式的动态副本管理策略．该策略引入竞标机制中的竞标时间、竞标底价和竞标价格等，将主节点和子节点作为卖家和买家．本文策略考虑了系统的负载均衡和可用性和一致性的均衡问题．实验结果表明，与传统静态副本策略和CDRM副本策略相比，本文策略有着比较好的系统性能．

在未来的工作中，将深入研究针对用户访问模式的变化来进行副本分布以及通过灰色预测用户未来的数据访问热度来优化副本分布．