面向海量数据的分布式信息管理平台研究

肖 祥

(福建水利电力职业技术学院 信息工程系，福建 永安 366000)

随着分布式数据的爆炸式增长，蕴藏在其中的巨大价值正在等待我们探索.例如，Facebook等社交网站可以通过分析网站历史记录(例如点击记录，活动记录等)来获得用户的使用模式和隐藏的相关性，以检测社交热点事件以及有利于进行营销决策(例如，广告推荐).但由于数据量大、高复杂度、分散性以及网络资源的匮乏等特性，集中式的数据处理是低效率甚至是不可行的[1].MapReduce是一个用于并行处理大规模数据集的分布式编程模型，在现有的应用程序中已经显示出其卓越的有效性[2-4].由于原始的MapReduce模型并未针对分布式信息处理进行优化[5]，因此将分布式信息聚合到单个数据中心进行集中处理是一种常用的方法.然而，由于网络链路的异构性以及带宽的有限性，集中式的信息处理会有较大的延迟.在优化信息处理所需的成本时，可以考虑链路带宽的异质性、数据生成的动态性和资源的价格.因此，本文将多源信息分布到多个数据中心，使用分布式MapReduce进行处理.分布式计算的多个阶段(例如Map阶段和MapReduce程序的Reduce阶段之间的相互作用)之间的相互依赖进一步增加了分布式信息处理中数据迁移、资源分配和Reducer选择的复杂性.本文通过在多个分布式计算中心之间平衡MapReduce两个阶段的成本来解决高效调度的问题，以实现高性能、高可用性和成本最小化的最终目的.

1 系统模型

图1 系统的体系结构

在MapReduce模型中，Mapper处理输入数据集并输出中间数据，中间数据表示为一组键值对，Reducer接收来自Mapper的所有中间数据，并根据特定的key来合并相应的value以在Reduce阶段生成更小的value集.Mapper和Reducer均可以部署在不同的节点.在分布式信息管理的环境下，分布式信息的执行路径尤为重要.Chamikara等人[6]定义了3种使用MapReduce进行信息管理的执行路径：COPY，MULTI和GEO.COPY是一种策略，是在进行MapReduce之前，将所有子数据集复制到一个数据中心.但是，当MapReduce生成的输出数据远小于输入时，COPY的效率并不高.MULTI是一种在每个子数据集上分别执行MapReduce的策略，然后将各个结果汇总.这种策略的缺点在于，只有在MapReduce作业的顺序对最终结果没有影响的情况下，才能获得预期的结果.GEO在不同数据中心执行Map操作，然后将中间数据复制到单个数据中心进行Reduce操作.这适用于Reduce阶段中作业相关的应用程序.例如，确定Web缓存中页面的中值大小，或者中间数据小于输入的应用程序.文献[7]通过测量来自Facebook的大约16 000个作业的Hadoop痕迹，大约70%的作业的输入数据大于相应的中间数据.因此，GEO在每个数据中心执行映射操作，然后将中间数据汇总到单个数据中心，从而降低跨区域带宽成本.基于以上考虑，我们考虑GEO在问题建模中的执行路径.

本文考虑数据服务提供商(DSP)管理多个信息源并将所有信息数据传输到云中，并利用MapReduce进行处理的场景.该系统的体系结构如图1所示.数据源分布在多个位置，并不断地产生海量数据；分析处理数据的应用程序部署在云中，数据源与分布在多个位置的数据中心相连接.

在这个模型中，数据一旦生成就被迁移到数据中心，并以增量方式处理，即只计算新到达的数据，过去的中间数据可以重复使用.Mappers和Reducer都能在每个数据中心上运行.由于本文采用了GEO执行路径，数据迁移有两个阶段：第一阶段，将数据迁移到任意的数据中心进行Map操作；第二阶段，迁移Mappers产生的中间数据时，必须考虑到数据相关性，相关的数据需要被迁移到同一个数据中心.该过程如图1所示，粗线是执行路径的一个例子，来自数据源1和数据源2的原始数据被迁移到多个数据中心进行Map操作，然后Mapper的输出数据被聚合到数据中心1中的Reducer进行Reduce操作.

设D是数据中心的集合，其大小为|D|，K是大小为|K|的虚拟机类型集合，每个虚拟机类型具有特定的容量vk，即CPU和内存.数据是从|R|个不同的数据源动态、持续产生的，R是数据源的集合.来自任意位置数据源的数据可以迁移到任意的数据中心进行Map操作，然后将中间数据聚合到数据中心.假设从数据源r到数据中心d的带宽为Balloc.在系统运行的每一个时间间隙中，数据服务提供商需要决定要从数据源r向数据中心d迁移的数据量，并计算需要使用多少资源来进行数据处理，并选择数据中心作为Reducer.最终的目标是最大限度地降低海量数据分析的总体成本，同时具有较低的延迟时延.

2 问题建模

数据迁移和处理的成本最小化问题可以建模为：

minCtotal

subject to 0≤ar,d≤Br,d,∀r,d

(1)

在式(1)中，Ctotal是指总成本，其定义如式(2)所示：

(2)

总成本由3部分组成.第一部分，即式(2)中的第一项，是指带宽、存储以及时延成本.其中，sd是数据中心d的存储价格，br,d是数据源和数据中心之间带宽的价格，lr,d是数据源和数据中心之间时延的价格，ar,d是数据源r分配到数据中心d的数据量.第二部分是计算成本，md,k是Map操作所需类型k虚拟机的数量，rd,k是Reduce操作所需类型k虚拟机的数量，pk是类型k虚拟机的价格.第三部分是数据迁移的成本，其中，fz是数据中心产生的数据量.式(1)中的第一个约束条件是带宽约束，即数据源r分配到数据中心d的数据量不可以多于r到d的带宽，其中，Br,d是数据源r到数据中心d的最大带宽.在第二个约束条件中，ar是指数据源r产生的总数据量.第三个约束条件，是指在数据中心d中的Map和Reduce操作所使用的资源不能超过该虚拟机的总资源.第四个约束条件保证了只有一个数据中心在运行Reducer.

我们的目标是通过优化分配给每个数据中心的数据量、所需虚拟机资源数量以及合适的Reduce操作来最大限度地降低总成本.具体而言，考虑以下成本要素：带宽成本、存储成本、延迟成本、计算成本和迁移成本.

3 算法设计

可以等价地将优化问题(1)分解为3个子问题：数据分配、资源配置和Reducer的选择.上述3个子问题的求解过程如下所示.

1)数据分配

由于每个数据源生成数据的过程都是独立的，所以集中式优化可以在每个数据源独立地执行.数据源r的数据分配问题，应该解决以下问题：

(3)

求解问题(3)的算法如表1所示.

表1 数据分配算法

2)资源配置

由于每个数据中心中的资源供应都是独立的，与数据分配类似，资源配置问题可以在每个数据中心内独立地解决.考虑数据中心d的资源配置问题，利用线性规划的知识，可以推导出式(4).由式(4)可知，当数据中心的价格pk较低，或者虚拟机资源vk较多时，会倾向选择类型k的虚拟机.

(4)

3)Reducer的选择

Reducer的选择是一个min-weight问题.因此，能推导出以下的式(5)：

(5)

Reducer的选择算法如表2所示.

表2 Reducer选择算法

4 算法评估

我们将本文的算法与其他方案进行比较，其中，所对比的每个方案都具有数据分配、资源配置和reducer选择的组合.对于数据分配策略，考虑2种代表性策略：1)接近感知数据分配(PDA)，其中来自每个数据源的动态生成的数据总是被分配给地理位置上最近的数据中心；2)负载平衡数据分配(Load-Balance Data Allocation，LBDA)，每个数据源的数据总是被分配到最低的Map负载的数据中心.对于资源配置策略，考虑2种典型的策略：启发式虚拟机配置(HVP)以及稳定的虚拟器(SVP)配置.对于Reducer选择策略，我们考虑最小迁移成本的Reducer选择(MCRS).

图2给出了不同策略的平均时间成本的比较.从图2我们能观察到，在成本方面，除了PDA+SVP+MCRS的组合，本文的算法均有最小的平均时间成本.这是因为PDA+SVP+MCRS的组合仅将数据移动到位置最近的数据中心，使带宽成本和延迟成本最低.尽管如此，这种策略并不是真正有效的，因为它们的队列会随着时间的增加而增加(如图3所示).这意味该算法组合不能保持长期的稳定.因此，与PDA+SVP+MCRS策略组合相比，本文算法在数据局部性和系统稳定性之间做出了更好的折衷.从图3中可以看出，即使经过很长时间，本文算法能具有较好的稳定性，而其他策略的队列大小随时间的增加而增加，这必然导致系统的不稳定.

图2 各算法的平均成本

图3 各算法的平均队列长度

5 结语

针对分布信息源产生的海量数据，本文开发了一个有效的数据迁移、资源分配和Reducer选择以及成本最小化的框架.通过平衡数据中心MapReduce两个过程所产生的成本，即带宽成本、存储成本、计算成本、迁移成本和延迟成本，通过同时最小化5个成本，建立一个联合的随机整数非线性优化问题.通过采用数学分解技术，将原问题转化为3个独立的子问题，并提出相应的算法，从而使平均运行成本最小化.最后，通过与现有的典型方法进行比较，验证本文算法的有效性.