分布式图形验：机器学习框架以及云技术中的数据挖掘.doc

分布式图形实验：机器学习框架以及云技术中的数据挖掘 摘要： 像MapReduce这类高级数据并行处理框架在对大规模数据处理系统的设计与实现进行简化的同时，并不能天然地或者高效的支持许多重要的数据挖掘和机器学习算法，在此基础上构建的机器学习系统往往是低效的。为填补这一空白，我们引入Graphlab，它实现了异步、动态的并行图计算模式，同时保证数据一致性，且在共享内存基础上具有很好的计算并行度。在本论文中，我们从Graphlab框架本身拓展到更具实际意义、更有挑战性的具有健壮数据一致性的分布式计算。 我们在图计算基础上扩展开发了流水线锁定和数据版本技术来减少网络拥塞和降低网络传输开销。同时，我们介绍了使用经典Chandy-Lamport快照算法实现的容错机制，并论证了可以在Graphlab框架基础上方便的实现。最后，我们评价了我们的分布式实现方案在亚马逊虚拟计算平台上的性能，并展示了相对于Hadoop的实现方案，亚马逊虚拟机群部署Graphlab系统会有1到2个数量级的性能提升。 1.介绍 伴随着机器学习和数据挖掘任务的规模增长、复杂度提升，急需一个能够在大规模集群上快速并行执行数据挖掘和机器学习任务的系统。同时，像亚马逊弹性计算云这样的云集算服务提供了在不具备实体集群情况下进行大规模节点计算的可能。不幸的是，设计、实现并且调试分布式机器学习和数据挖掘算法需要能够对云集群非常熟练的使用，这些对机器学习和数据挖掘专家们构成极其艰巨的挑战，因为这需要他们在实现复杂数据算法模型的同时能够处理并行竞争条件、死锁、分布式状态和通信协议等难题。 尽管如此，对大规模计算和数据存储的需求，已经驱使很多人就某些独立的算法模型，开发出新的并行分布式机器学习和数据挖掘系统（如引文2，14，15，30，35）。由于不同的研究团体重复性地解决相同的并行或者分布式计算问题，这些消耗时间和重复劳动的努力仅仅缓慢推动了这个领域的发展。因此，研究机器学习和数据挖掘的群体及组织需要一个高水平的面向很多机器学习和数据挖掘应用中都会遇到的异步、动态、图并行计算模式的，并且隐藏并行和分布式系统复杂设计逻辑的分布式系统模型。不幸的是，已经存在的高水平并行计算模式例如mapreduce，Dryad和Pregel都不能很好的支持满足这些苛刻的特制要求。为了帮助填补这一空白，我们介绍Graphlab计算模式，它在共享内存环境下，直接面向异步、动态和图并行计算。 在这篇文论中，我们将多核的Graphlab概念拓展到分布式环境下，并对分布式执行模型进行乐形式化的描述。我们在保证严格的一致性要求的基础上，探索出多种分布式执行模型的实现方式。为了实现这个目标，融入数据版本控制技术来间情网络拥堵，引入流水线分布式锁机制来降低网络传输开销。为了处理数据局部性和入口带来的挑战，我们引入原子图机制，以实现在分布式环境下的快速构建图数据结构。我们还通过经典的Chandy-Lamport快照算法为Graphlab框架增加容错机制，并证明了此机制在Graphlab概念中可以很容易被实现。 我们对我们在亚马逊弹性计算服务基础上使用C++优化实现的Graphlab系统进行乐综合性能分析。我们展示出在Graphlab框架上开发的应用程序性能相当于在Hadoop/mapreduce框架同等实现下的20-60倍，且能和使用MPI精心设计的实现相匹敌。我们的主要贡献如下： 一个机器学习和数据挖掘算法共性综述以及现有大数据框架的局限性。 一个修改过的可以部署在分布式环境下的Graphlab概念版本和执行模型。 两种可实现的新的分布式执行模型实施方案。 彩色引擎：使用图着色算法实现静态调度的高效、渐进、一致的执行。 加锁引擎：采用分布式流水线锁机制和延迟消除方法实现对动态、优先执行的支持。 通过两个快照方案实现容错。 在分布式Graphlab框架下实现三种高水准的机器学习算法。 对部署在拥有64个节点512个CPU的亚马逊弹性计算服务集群上的Graphlab系统进行大量评测，并和Hadoop、Pregel和MPI进行对比。 2.MLDM的算法性能： 在论文的这一部分，我们将详细叙述Graphlab概念下的大规模分布式机器学习-数据挖掘系统所独有的关键特性，并解释其他的分布式框架为何不具备这些特性。这些特性和分布式框架列在表格1中。 图结构计算：很多机器学习-数据挖掘方面的研究进展将焦点聚集在对数据相关性的建模上。通过对数据相关性进行建模，我们能够从包含噪音的数据中抽取出更多有价值的信息。例如，与仅仅孤立的处理购物者数据相比，对相似购物者的相关性建模能够做出更好的推荐。不幸的是，类似于Mapreduce的分布式数据处理模型并不能通用性的适应相关性计算需求，而这又是很多更高级机器学习-数据挖掘算法所需要的。尽管，很多