陶昕　计春雷

摘 要：针对传统装箱算法在处理海量数据时所存在的的运行效率与空间利用率低的问题，在深入研究已有装箱算法的基础上，在分布式系统中定义一种可变大小的箱子，结合动态和静态算法的优势，提出基于MapReduce的动态装箱算法。实验结果表明，针对海量动态数据，运用基于MapReduce的动态装箱算法，结果接近最优解，同时具有很高的处理效率。

关键词：装箱算法；海量数据；分布式系统； MapReduce

DOIDOI：10.11907/rjdk.151567

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2015）007-0066-05

0 引言

随着云计算和物联网技术的快速发展，数据量呈爆炸性增长。据WinterCorp统计显示，互联网产生的数据量每两年增长3倍[1]。在互联网技术极速发展的背景下，大数据应运而生，人们生活正在逐渐被巨大的数据量所包围。企业经营信息、电子商务商品物流信息、社交网络交互信息、位置信息等数据量远远超越现有企业IT架构和基础设施的承载能力，实时性要求也大大超越现有的计算能力。大数据正在逐渐影响人们的生活方式。同时，大数据的产生给传统的数据管理带来了巨大的挑战。针对海量数据的处理将成为大数据时代必须面对的问题。

Hadoop是一个开源的、具有高可靠性和良好可伸缩性的分布式计算框架，可以对海量数据进行分布式处理，其分布式计算模型MapReduce可以将数据集分割成若干小数据单元，这些小数据单元可以被放置在任何一个节点上进行处理[2]。Hadoop分布式文件系统（HDFS）专门为存储和管理海量数据而设计，其默认存储单元值为64M，但实际应用中所产生的数据大多小于64M，直接处理这些数据将造成内存浪费，降低整个系统性能。……