基于遗传算法的多中心海量数据布局研究

1、 基于遗传算法的多中心海量数据布局研究 孙国强Summary：数据布局策略作为数据管理的重要方面，对研究多数据中心环境下的数据布局有着重要意义。针对多数据中心的数据检索、更新和全局负载均衡3个目标对数据布局方案进行求解和优化。提出一种改进的多目标遗传算法，该算法以降低多数据中心的数据检索和更新代价作为优化目标，并结合负载均衡作为约束条件。实验显示该算法不仅在数据布局方面有良好性能，而且能够获得较高的资源利用率。Key：海量数据；多中心；遗传算法；多目标优化；数据布局DOIDOI：10.11907/rjdk.143666：TP311.5：A ：16727800（2015）0010059020 引

2、言从海量数据中挖掘有效信息，为规划建设和生产提供辅助决策已成为一种趋势。然而如何在多数据中心环境下实现对海量数据的有效存储、访问和管理变得至关重要，具体表现为：一方面提高数据检索应用的可靠性，减少由于数据检索和更新不同步而造成的“脏数据”或“过时数据”，降低跨数据中心执行事务数据传输所导致的时间开销，进而提升执行效率；另一方面合理的数据布局方案，应在对应用执行效率进行优化的前提下，兼顾多数据中心之间工作负载的均衡性，尽量提高并行处理能力。目前，多种数据布局方法被相继提出，但由于数据分配问题本身的复杂性，大部分都存在不足之处。为更好地解决数据布局问题， 作者在查阅大量相关文献和论文资料的基础上，

3、提出了基于多目标遗传算法来解决多中心海量数据布局的目标优化问题。该算法以降低多数据中心的数据检索和更新代价作为优化目标，并结合负载均衡作为约束条件。模拟仿真结果表明了该算法的有效性。1 多数据中心数据布局模型1.1 多数据中心系统多数据中心系统，是由地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）使用计算机网络联接起来，共同组成的一个统一的数据库系统。对于多数据中心的数据分配问题，可以描述为设有一个由站点集S=（S1，S2.Sm）组成的网络，其上运行一个事务集T=（T1，T2.Tq），存储着一个片段集F=（F1，F2.FN），按照某个原则将每个片段Fi的不同副

4、本分配到不同的站点Sk上的分配方案，表示为A（F，S，T），使其分配代价最优1。数据分配问题对整个数据中心应用系统的可靠性、可用性和数据中心的效率有很大影响。数据分配方法优劣的度量标准通常是最小代价和性能，在优劣的度量问题上，国内外学者均偏向于代价优化，提出的优化函数也大多基于代价函数。但在分配数据时，均衡系统的负载也是需要慎重考虑的因素之一。1.2 数据布局数学模型适应度是个体优劣的评价标准，在遗传过程中适应度低的个体将被淘汰2。本文使用Reference1中的代价公式作为适应度评价的标准。其中，适应度函数为Min（Tota1Cost）。TotalCost=TQ+TU（1）其中， TQ 表示

5、所有事务的检索数据量，TU表示所有事务的更新数据量。对于所有站点上发生的所有事务，其总的检索数据量TQ和总的更新数据量TU分别为：TQ=STFVtran（Sk，Sf）FRE_Q（Ti，Sk）SEL_Q（Ti，Fj）Size（Fj）（2）TU=STFVtran（Sk，Sf）FRE_U（Ti，Sk）SEL_U（Ti，Fj）Size（Fj）（3）其中，Ti为事务，Fj为数据片段，Sf为站点，Sk为在站点Sk上的事务Ti所访问的数据片段Fj的副本所在的站点，若站点Sk本地有数据片段Fj的副本，则Sf等于Sk，否则为Sf使Vtran（Sk，Sf）达到最小值的站点；Vtran（Sk，Sf）为站点Sk与站点

6、Sf间的通信代价系数，FRE_Q（Ti，Sk）为由站点Sk发出的事务Ti执行检索操作的频率，SEL_Q（Ti，Fj）为事务Ti对数据片段Fj的检索访问百分比，Size（Fj）为数据片段Fj的大小；Sf为在站点Sk上的事务Ti所访问的数据片段Fj的任一副本所在站点，即所有拥有数据片段Fj副本的站点，FRE_U（Ti，Sk）为由站点Sk发出的事务Ti执行更新操作的频率，SEL_U（Ti，Fj）为事务Ti对数据片段Fj的更新访问百分比。交叉概率和变异概率是遗传算法中影响算法收敛性的重要参数，是控制算法搜索速度和求解质量的关键2。本文采用自适应调节策略，其中自适应交叉算子和自适应变异算子，分别如式（4

7、）和式（5）3。Pm=Pm1-（Pm1-Pm2）（Fmax-Fm）Fmax-Favg FcFavg Pm1 FcPc=Pc1-（Pc1-Pc2）（Fc-Favg）Fmax-Favg FmFavg Pc1 Fm其中，Pc1 =0.9，Pc2=0.6， Fc是参与交叉操作的两个个体中较大的适应度；Pm1 =0.1，Pm2=0.001，Fmax和Favg是上一代群体中最大适应度和平均适应度，Fm是变异个体的适应度。1.3 分配策略流程图遗传算法具有高度的并行性和鲁棒性等优良性能。算法的思想简单，运行方式和实现步骤规范，能够在深度优先搜索和广度优先搜索之间维持很好的平衡4。因此，本文的分配策略有较高的

8、执行效率和较强的求全局最优解的能力，且易于实现。求解流程如图1所示。图1 分配策略基本流程2 基于遗传算法的数据布局2.1 染色体编码二进制编码方案具有编码、解码操作简单易行，选择、交叉和变异等遗传操作便于实现，符合最小符号集编码原则，便于利用模式定理对算法进行理论分析的优点5。因此，对每个个体采用二进制编码，编码长度等于数据中心的个数n，编码顺序与其顺序相对应，1表示将该数据片段分配给相应位置的数据中心，0则相反。以6个站点为例说明，编码为001100的个体表示将数据片段分配给中间两个数据中心，这样，每个数据片段的分配方案就可以用一个二进制编码的个体表示。 2.2 适应度函数设计适应度是反映

9、个体所代表的分配方案优劣的标准6。在本文中更新检索总代价越大的分配方案中的个体适应度就越高。其中，检索代价公式如式（6），更新代价计算公式如式（7）。TQ=STVtran（Sk，Sf）FRE_Q（Ti，Sk）SEL_Q（Ti，Fj）Size（Fj）（6）TU=STVtran（Sk，Sf）FRE_U（Ti，Sk）SEL_U（Ti，Fj）Size（Fj）（7）TQ+TU代表了个体的更新检索总代价，显然，总代价越小表示其适应度越高。个体的适应度为：Fi=1TQ+TU（8）2.3 遗传操作为维持算法收敛性和群体中个体多样性二者之间的平衡，采用上文提及的交叉概率为Pc的自适应交叉算子和变异概率为Pm的自

10、适应变异算子对个体进行操作。为保证子代群体中适应度最高的个体优于父代群体中适应度最高的个体，采用适应度比例和最优保存策略相结合的选择机制，最优保存策略是算法收敛性的基本保障。最优保存策略7将当代群体中适应度最佳的个体记录下来，保留到下一代。这不仅能防止其被遗传操作破坏，还能提高群体平均适应度值和最优个体适应度值。对进行交叉和变异操作产生的新个体，计算每个个体的适应度，选出适应度最小的个体，用前面所记录的最优个体代替，这样就产生了进入下一代的群体。2.4 约束/终止条件为保证数据中心的正常运转，算法将负载失衡值作为个体的约束条件。本文设计的负载均衡值为各数据中心使用率的标准差，该值越小，负载越均

11、衡。Load=mi=1（Numi-nm）2（9）通过预先设立的阈值，在进化过程中，个体的负载失衡值必须小于该阈值，才能保留到下一代。如果数据中心的使用率超过该阈值，则认为该数据中心处于超负荷状态。若初始数据布局方案和子代数据布局方案使至少一个数据中心在事务开始执行前已处于超负荷状态，则视为无效解。遗传算法的终止条件一般是适应度达到了要求的值，或是进化到了一定的代数。算法一旦终止，便选择当前种群中的最优个体为最终结果8。3 结语在多种环境下的测试中，用本文算法进行求解，得到的解大多等于或者接近于最优解。通过采用自适应的交叉算子和变异算子，算法的全局搜索能力得到很好的体现。通过把数据中心的负载失衡值作为算法执行的约束条件，明显提高了数据中心的利用率。本文提出的一种基于双适应度的遗传算法的数据布局