MapReduce启蒙文献

MapReduce是一个极其强大的算法,尤其当使用普通硬件构成的分布式系统处理海量数据时尤为如此。它让广大开发者能轻易在大型、分布式、容错的系统上处理数据。最近Cloudant产品线上众多灵感中的一个让其焕发新生。事实上,这个灵感也促进了这个公司本身的创立。MapReduce最近也被重新审视,它的实现方案众多,各有优势和弱点。它不是适合所有场景的万能工具,我也曾经直言过这个问题。但是,如果使用得当,它会是一个极其强大的工具。它也是一个极其简单的概念,是进入分布式计算世界的绝佳入口。我也因此很吃惊为何这么少人读过MapReduce启蒙文献。我提供下列我主观认为很有益的文章,并向大家介绍它们的核心概念。

MapReduce的发现和承诺

  • Google MapReduce.Jeff Dean和Sanjay Ghemawat 发表了Google的MapReduce实现的细节,此举为世界做出了巨大贡献,文章诠释了数据如何并行批处理,如何拥有最大的可伸缩性。他们方案的主要优势是为开发者提供了一个优雅简洁的API(“你想如何处理文件中的一行数据?”)并且隐藏了所有的工作流管理、任务调度、失败恢复。但是这个论文最精彩的部分是13页的一个示例应用,他们在一个顺序的C程序中嵌入了一个MapReduce工作流。这一个例子非常明显的突出了顺序化编程和并行处理之间的区别,而且令人兴奋的是几行代码就能轻易碾碎PB级别的数据。最后,这个论文还展现了真实的运作数据,这些数据巩固了MapReduce在Google的关键地位。
  • Google Sawzall。不深究细节,Sawzall是我找到的第一份演示声明式语言重要性的论文,文章介绍了声明式语言如何封装Google的MapReduce实现。它也第一次让我意识到,类SQL的语言比如 Pig 和Hive即将来临。这篇文章也预示着Google未来将启用的具有改革意义的大数据查询引擎产品。
  • Yahoo map-reduce-merge。这份论文提供了第一个证明多步式MapReduce工作流(尤其是map-reduce-merge)是关系上完备的。SQL关系代数能够在一种“负载均衡、可伸缩以及并行”的方式上表达。这份论文也对提到的算法提供了例子实现。这篇文章使得Pig、Hive以及其他类SQL语言在MapReduce(那时已经发展出Hadoop)上衍生、发展成为必然。

 

理解和量化MapReduce的限制

  • Graph Twiddling in a MapReduce World.这篇具有改革意义的(但是很少引用的)的文章发表自NSA的Jonathan Cohen,详细讨论了通用MapReduce算法处理图形数据的适用性和限制。它特别检查了一些常用的图形算法(例如计算所有节点的出度,枚举三角等等)。这篇文章实现了几个常用算法的示例以进行举证,而且提出MapReduce处理过程通常需要多层加工,因此在一些场景下整个图形需要在连续步骤中不断向后拷贝。虽然图形处理在mapreduce中是可以做到的,但是也可能很低效,取决于使用哪种算法。
  • Google Percolator.我曾在别处详细描述了这份论文,它建立了Google面向批处理的MapReduce框架(Hadoop)的延迟缺陷观点。特别是此文介绍了增量处理的Percolator框架,以及它如何增量处理添加到文档库中的新文件(比如新抓取的网页添加到搜索引擎时如何增量建立索引,译者注)。它讨论了一些特定实现(包括为Bigtable添加事务处理语义)并且提供了引人注目的可运行的证据,证明了增量方法是高效分析连续成长/变化数据集合的优秀方案。Google写到,“转化索引系统到增量系统……减少了100倍的平均文档处理延迟”
  • Google Dremel.如果你不读其他任何文档,读这篇吧。这份论文描述了一个惊人的替代方案的核心,此方案可以用难以置信的低延迟查询海量数据。它就是Dremel,作为新型BigQuery产品的核心,它承诺能在几千台服务器上秒级分析万亿行数据。这篇文章令人信服的证明了Google的MapReduce实现有两个致命弱点:(i)在他们面向批处理的实现中不可避免的严重处理延迟;(ii)缺少声明式查询语言。Dremel简直是个混蛋(可能指Dremel太强大、对传统MapReduce缺陷的剖析太直接,译者注)。面向列的存储、查询扩展和服务器树以及一个类SQL的查询语言组成了这个绝对革命性产品的核心。开源和企业阵营都妒忌该产品并不让人意外,我们拭目以待, 开源项目Apache Drill(基于Dremel)对比Cloudera的近期宣布的Impala项目(基于Hadoop)谁更胜一筹。

 

Cloudant的MapReduce

MapReduce极其强大。在Cloudant我们认为这是理所应当的,但是如果引入并行计算到数据库层面,可以极大简化应用层面的复杂度。我们的实现方案是非常不同于Google、Hadoop、Mongo和Riak。与Google和Hadoop类似,我们是完全并行的。执行过程发生在集群中每一个节点上,这些节点都持有输入数据集的一部分。但是不像上述所有产品,我们的实现是增量的。它的优化不是为了贯穿数据的首次处理,而是为新增或修改的文档提供高效的计算,Percolator论文中也提到了非增量方案的延迟问题。

下一步,我们的实现不是仅仅在文件系统存储上创建key/value行。Cloudant MapReduce的输出其实是一个持久化在磁盘上的b+树。通过Cloudant mapreduce引擎,我们允许用户高效处理数据并且为速度要求极高的查询创建二级索引。它逻辑上等价于SQL里的ALTER TABLE CREATE INDEX。

与Mongo和Riak中的数据库实现相比,Cloudant的MapReduce是可连接的。这首先意味着它是能够在大量的事务型数据上对某些类型的JOIN操作执行高效预计算。最后,不像Dremel,我们还没提供一个声明式查询语言。map-reduce-merge论文以及Pig和Hive的编译器都为如何将SQL查询编译为高效的MapReduce代码提供了一个清晰的方案。这是新Cloudant用户的普遍需求。如果你感兴趣这些反馈将如何影响我们的产品发展路线图,请在11月8号星期四收听Alan Hoffman的网络广播。

英文原文:MapReduce’s Founding Documents,编译:ImportNew - 储晓颖

译文链接:http://www.importnew.com/1706.html

【如需转载,请在正文中标注并保留原文链接、译文链接和译者等信息,谢谢合作!】

关于作者: 储晓颖

现任支付宝架构师,负责监控分析域的架构和产品设计。架构时严谨,编码时疯狂。新浪微博:@疯狂编码中的xiaoY

查看储晓颖的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部