Google MapReduce, Skeletons

http://linux.tcpip.com.cn/news/shownews.php?id=10067&cat=5

引用

Google 披露自己的成功技术秘诀

　　Google 成功的搜索引擎幕后的技术英雄非常简单：解决 PC 崩溃问题。 　　

　　美国加利福尼亚州伯林格姆当地时间本周三，Google 负责技术和运营的副总裁 Urs Hoelzle 在 EclipseCon 会议上透露了 Google 数据中心运行的一些秘密。许多人都认为， Google 在运行数据中心方面的经验比其搜索算法更宝贵。 　　

　　Google 能够以数以百万美元计，而不是数以千万美元计的资金构筑其计算基础设施的秘密是：购买相对廉价的计算机。通过研究硬件成本，Google 的技术人员发现，购买一些高端服务器的成本要远高于数十台更简单的“大众化”服务器。这种策略的难题就在于使这些硬件协调地运行，确保一台计算机的故障不会影响任务的执行，例如返回搜索结果或显示广告。 　　

　　Hoelzle 说，我们考虑到了家用 PC。家用 PC 因软件和硬件缺陷而造成的崩溃每 3 年才会发生一次。他说，如果拥有数千台 PC，每天有一台 PC 崩溃是很正常的。因此，最好是能够以自动的方式解决这一问题，否则服务肯定会出现问题。 　　

　　Google 已经开发了大量的软件工具，来完成计算设备的安装。它开发了被称为“Google文件系统”的文件系统，能够处理 64MB 大小的数据块。更为重要的是，它能够应付随时可能发生的磁盘或网络故障。Hoelzle 说，我们开发了容错软件。如果有应付故障的措施，PC 就完全可以担负提供互联网服务的重任。Google 数以千计的 PC 服务器运行一种基于 Red Hat 版本的简化版 Linux，该版本只是针对 Google 专门修改的操作系统内核。　　

　　Google 还设计了一种能够处理海量数据、迅速响应查询的系统，它将整个 Web 划分为数以百万计的 Google 的技术人员称之为 shard 的小块儿。Google 创建了一个出现在 Web 上的词汇的索引，但它还有大量的文档服务器存储收集的网页。 　　

　　据 Hoelzle 称，Google 另一个重要的技术创新是，使在数以千计的服务器上运行的软件的开发非常简单。通常情况下，开发在并行服务器上运行的应用软件需要专门的编程工具和技能。名为 MapReduce 的这款编程工具对于 Google 降低成本是非常重要的。Hoelzle 说，成本是购买设备的成本和编写软件的编程时间之和。从去年开始，Google 已经开始大面积使用 MapReduce 编程工具。

　　Google 还开发了批量任务调度软件。名为 Global Work Queue 的这款软件能够将计算工作分解成许多更小的任务，并将它们分配给各台计算机完成。 　　

　　Hoelzle 表示，尽管考虑了故障问题，但这还不能解决所有问题。在演讲中，它展示了用于应对 Google 数据中心发生的紧急事件的6辆救火车的照片。 　　

　　在接受 CNET News.com 采访时，Hoelzle 表示，电力成本是 Google 的数据中心设计中的另一个重要因素。他说，不包括人力成本在内的运行成本直接与电力成本相关。电力是降低数据中心运行成本的一个因素，我们不但要降低设备采购费用，还需要降低运行成本。

http://www.cnblogs.com/tianchunfeng/archive/2005/03/17/120722.html

引用

MapReduce:Google的人间大炮

网络上关于MapReduce的介绍，最权威的就是　Jeffrey Dean
和 Sanjay Ghemawat　的那篇：MapReduce: Simpli ed Data Processing on Large Clusters
您可以到　labs.google.com 上下载。

    对goole这样需要分析处理海量数据的公司来说，普通的编程方法已经不够用了。于是 google开发了MapReduce。简单来说，语法上MapReduce就像Lisp,使用MapReduce模型你可以指定一个Map方法来处理诸如key/value这样的数据，并生成中间形式的　key/value 对，然后再使用 Reduce方法合并所有相同key的中间　key/value　对生成最终结果。google的MapReduce是运行在数千台机器上的处理TB数据的编程工具。

    据说在MapReduce这样的编程模型下，程序可以自动的集群机器中在按照并行方式分布执行。就如同java程序员可以不考虑内存泄露一样， MapReduce程序员也不许要关心海量数据如何被分配到多台机器上，不需要考虑如果参加计算的机器出现故障应该怎么办，不需要考虑这些机器间如何协作共同完成工作的。

    举个例子吧：最近我在做贝叶斯论坛垃圾帖屏蔽演示系统 Beta 1 的时候，就需要计算样本数据中每个词语出现的频率。我的计算步骤就是先分词，然后用hash表处理。要是碰到TB的数据，我的赛扬CPU可是吃不消。那么放在MapReduce下面会是什么样子呢？

    下面是一个伪实现：
第一步：
    map(String key, String value):
    // key: 文档名称
    // value: 文档内容
    for each word w in value:
        EmitIntermediate(w, "1");
第二步：
    reduce(String key, Iterator values):
    // key: 一个词
    // values: 关于这个词的频率数据
    int result = 0;
        for each v in values:
            result += ParseInt(v);
        Emit(AsString(result));


    如果你看过向量空间模型就知道，这就是计算　TF 和　IDF 的语义实现。

    Google的WebReduce　包是用C++实现的，在MapReduce: Simpli ed Data Processing on Large Clusters　一文中还包含了一段真实的WebReduce的代码，可以看看，饱饱眼福。

引用

MapReduce所用的思想叫做Skeletal Parallelism，在1989年以前就出现了，当时叫Algorithmic Skeletons
在近十多年欧洲的并行计算程序设计语言的研究中，它从来就没中断过，即便是在初期所取得的成果也远远超出MapReduce这个技术里需要用到的内容。见
http://homepages.inf.ed.ac.uk/mic/Skeletons/

Google的MapReduce从理论上讲实际只是一个最简单skeleton，其难度决不在于语言和并行技术设计上，而在于它是一个大规模的real world application，因此鲁棒性和容错比较重要，但它的文章里却对此谈之甚少，不知道为什么。

写文章的人不是科学研究者，而是工程师，OSDI发了这篇文章的主要原因还是因为它来自Google，主要是作为一个real world的demonstration.