• 国乒男女队出征第54届世乒赛“盼天晴” 2018-04-24
  • 崔世安会见吴政隆 双方就推进苏澳合作深入交谈 2018-04-24
  • 音乐剧《朝暮有情人》演绎港穗两地三代情 2018-04-24
  • 3月70城房价环比涨幅扩大 2018-04-24
  • 国际油价4月19日涨跌互现 2018-04-23
  • 南平市人民防空办公室成立武夷新区人防办事处 2018-04-23
  • 劳动者合法权利也不可“任性”滥用 2018-04-22
  • SKT招募绝地求生队员 网友迫切看到faker与韦神对枪! 2018-04-22
  • 送别余光中:诗人虽远行,乡愁永流传 2018-04-22
  • 连超模肯豆都“爱不释脚”的穆勒鞋 你不了解一下?|穆勒鞋|肯豆|超模 2018-04-22
  • 国家国际发展合作署举行揭牌仪式 2018-04-21
  • 春潮涌动,千余青少年相约科技馆 2018-04-21
  • 英俄用“关闭电视台”互相威胁 双边关系雪上加霜 2018-04-21
  • 拔不拔赖清德?蔡英文何去何从 2018-04-21
  • 我国阅读指数首次发布 人均纸书阅读量为4.66本 2018-04-20
  • 理解MapReduce

    栏目: 杂谈 发布于: 2014-04-25 09:10:43

    理解MapReduce

    所谓大数据时代,大数据带来了巨大的好处,也带来了巨大的挑战,其中之一就是大数据的存储和计算。如新浪微博的巨大用户群,若想用矩阵存储用户之间的关系,矩阵的大小是惊人的,不仅传统的存储方式不再适用,在进行一些矩阵运算(如乘法)时更是无能为力了,这时候就需要我们的 MapReduce 上场啦。


    MapReduce 是 Google 提出的概念,由于论文中木有提到实现细节,大家只能根据论文所述理论自己实现了。其中最火的是当年雅虎牵头做的开源项目 Hadoop,目前已经得到了非常广泛的应用(如亚马逊、百度)。尽管有这么多顶尖人才在不断优化,但据说 Hadoop 的性能目前还不及 Google 的十分之一。Whatever,大家现在能用的只有 Hadoop 了,而且一般也够用了。


    MapReduce 本质是上很简单,就是把原始问题分解成易解的小问题,分发给不同的节点(computer)进行处理,再收集处理后的结果,汇总运算一下,得到最终结果。像极了人工智能中的 And/Or。原理虽简单,MapReduce 的最大贡献还是在于 Scalability,Fault-tolerance 以及对并发和分布式的管理。


    在 MapReduce 中,data(可以存储在文件系统,也可数据库) 被主节点计算机(master node) 分配给不同的子节点计算机(worker nodes)进行并行处理,这些 worker nodes 被称为 cluster 或 grid。下面结合一个矩阵乘法的例子进行说明。



    大矩阵直接存储在文件中不够灵活,而且大矩阵中一般都很稀疏(0元素很多),这样比较浪费。一般的做法是用一个三元组来存储每一个元素。



    表示第 i 行第 j 列的元素为 A。有如下两个矩阵,我们想求矩阵的乘积:


    则用上述方法表示两个矩阵:



    矩阵乘法的计算过程很简单,只需要把对应的行列求内积,最后得到一个4行2列的矩阵C。通过计算过程可以看出,C 中各元素的计算是独立的互不干扰的。这样,我们在Map阶段,就可以把 Cij计算所需要的元素都集中到同一个key(i,j)中,然后,在Reduce阶段就可以从中解析出各个元素来计算。


    同时注意到,Aij 会被C 中多个元素的计算用到,所以在 Map 阶段,也要把一个 Aij存储成多个键值对,以备稍后根据不同的键值划分给不同的 reducer 来处理。处理流程如下:



    其中 shuffle 阶段是 Hadoop 自动完成的;Map 和 Reduce 需要用户自己写代码。上图所示很明晰,不再解释了。在wiki 中有更加正式的流程定义,同时有另外几个例子,等我理解后再发文分享吧?;队行巳ふ咭黄鸾涣?!


    文章来源Zippera's blog


    如果您觉得此文不错,不妨转载或分享到自己的朋友圈!和更多的朋友一起感触吧!


    【欢迎关注“程序员之家",微信号:programmer_club

    1.欢迎关注程序员之家微信号:programmer_club,与你探讨码农人生路上遇到的各类一手&二手话题,定期与你分享码农心得、思考、感悟。

    2.点击右上角 -> 查看官方公众账号 -> 点击:关注

    3.搜索号:programmer_club(可复制并粘贴到搜索框) -> 点击:关注

    本文转载自:微信公众账号 - 程序员之家,版权归原作者所有!

    本站文章除注明转载外,均为本站原创或编译?;队魏涡问降淖?,但请务必注明出处。
    转载请注明:文章转载自 七星彩票平台
    本文标题:理解MapReduce
    IT技术书籍推荐:
    Python学习手册(第4版)
    Python学习手册(第4版)
    鲁特兹 (Mark Lutz) (作者), 李军 (译者), 刘红伟 (译者), 等 (译者)
    《Python学习手册(第4版)》内容简介:学习Python的主要内建对象类型:数字、列表和字典。使用Python语句创建和处理对象,并且学习Python的通用语法模型。使用函数构造和重用代码,函数是Python的基本过程工具。学习Python??椋悍庾坝锞?、函数以及其他工具,以便构建较大的组件。学习Python的面向对象编程工具,用于组织程序代码。学习异常处理模型,以及用于编写较大程序的开发工具。了解高级Python工具,如装饰器、描述器、元类和Unicode处理等。