基于多目标优化的云存储副本分布策略的研究

发布时间：2019-09-15 22:53

【摘要】：针对现有云存储副本分布策略优化目标比较单一的不足,提出了局部最佳分布策略(Local Optimum Distribution,LODS)。LODS策略通过给出一系列新定义并利用一致性哈希函数来缩小副本分布的节点选择范围,进一步结合层次分析法,将一定决策半径内的节点作为方案层中的候选对象,通过更深入地研究云存储多目标优化准则对其优化从而最终选择出当前候选方案中的最佳目标节点。实验结果表明,通过优化的最优决策半径取值相对稳定,不随云存储系统规模的扩展和数据的增多而剧烈变化,并且当取值最佳决策半径时,LODS策略的存储负载平衡、热度负载平衡、等待时间性能高于HDFS、Amazon S3等系统中所采用的副本分布策略。
【图文】：

总体分布,决策中心,哈希,结构定义

略（Ｌｏ－ｃａｌＯｐｔｉｍｕｍＤｉｓｔｒｉｂｕｔｉｏｎＳｔｒａｔｅｇｙ，ＬＯＤＳ）。一致性哈希可以使副本总体分布相对均匀，再借助层次分析法对副本局部范围内的节点选择进行多目标优化，从而使其在局部节点选择时达到最优，较好地克服了上述目标优化方案的不足。在此基础上，进一步提出了副本分布策略综合性评价方法和评价指标，很好地弥补了当前的评价方法、评价标准不适用于局部优化过程评价的不足。２云存储局部最佳分布策略２．１ＬＯＤＳ的基本思想为了表达方便，在此首先给出如下新定义，如图１所示。图１决策表结构定义１（决策中心）从数据对象映射到环形哈希数值空间中的数值点出发，以顺时针寻找到的第一个由存储节点映射到的数值作为决策中心，用符号ｏ表示。为了方便叙述，数值ｏ对应的存储节点也用ｏ表示。定义２（决策半径）从决策中心出发顺时针和逆时针寻找相同个数的由存储节点映射到环形哈希数值空间中的数值，沿一个方向需要寻找的个数称为决策半径，符号表示为ｒ。如果数值ｋｅｙ为从决策中心出发顺时针或者逆时针寻找到的第ｉ个由存储节点映射到的数值，则称ｋｅｙ与决策中心ｏ的距离为ｉ，顺时针与决策中心ｏ距离ｉ的数值记为Ｐｒｅ（ｏ）ｉ，同样逆时针与决策中心ｏ距离ｉ的数值记为Ｐｒｏ（ｏ）ｉ，与它们对应的存储节点分别记为Ｐｒｅ＿Ｈ（ｏ）ｉ和Ｐｒｏ＿Ｈ（ｏ）ｉ。定义３（决策域）定义Ｐｒｅ＿Ｈ（ｏ）＝｛Ｐｒｅ＿Ｈ（ｏ）１，Ｐｒｅ＿Ｈ（ｏ）２，…，Ｐｒｅ＿Ｈ（ｏ）ｒ

副本,决策域,节点,因素分析

决策集的一次扩展）若Ｐ＿Ｕ（ｏ）＝錘，即当前决策域内没有适合存储当前副本的存储节点时，需要从Ｐｒｅ＿Ｈ（Ｐｒｅ（ｏ）ｒ）∪Ｐｒｏ＿Ｈ（Ｐｒｏ（ｏ）ｒ）中选择满足Λ条件的存储节点加入有效决策集，，同时Ｐ＿Ｈ（ｏ）＝Ｐ＿Ｈ（ｏ）∪Ｐｒｅ＿Ｈ（Ｐｒｅ（ｏ）ｒ）∪Ｐｒｏ＿Ｈ（Ｐｒｏ（ｏ）ｒ），这一过程称为有效决策集的一次扩展。图２同时展示了不同定义之间的关系或关联。图２ＬＯＤＳ决策域定义２．２影响存储节点选择的因素分析影响副本存储节点选择的因素主要包括：存储载后负载率、相对热度负载、预计等待时间。详细介绍如下：（１）存储载后负载率载后负载率主要为了衡量相同的副本数据块对于异构存储节点所造成的压力不同，即计算当前副本Ｒｅｐｌｉｊ加载到节点Ｎｉ后Ｎｉ的负载率，如式（１）所示：Ｌｏａｄ＿ｒ（Ｎｉ）＝Ｌｏａｄ（Ｎｉ）＋Ｂｕｒｄｅｎ（Ｒｅｐｌｉｊ）Ｓｔｏｒａｇｅ（Ｎｉ）（１）其中，Ｌｏａｄ（Ｎｉ）表示Ｎｉ的当前负载，Ｂｕｒｄｅｎ（Ｒｅｐｌｉｊ）表示存储副本Ｒｅｐｌｉｊ所需要的存储空间，Ｓｔｏｒａｇｅ（Ｎｉ）表示Ｎｉ的存储能力，则Ｌｏａｄ＿ｒ（Ｎｉ）表示Ｎｉ的载后负载率。（２）相对热度负载用节点相对热度来表示节点接收到的副本读写请求的总·４５·
【作者单位】：江南大学物联网应用技术教育部工程研究中心;江南大学物联网工程学院轻工过程先进控制教育部重点实验室;
【基金】：江苏省科技厅产学研前瞻项目(BY2013015-23) 中央高校科研专项(JUSRP211A41)资助
【分类号】：TP333;O221.6

【参考文献】