• Reciprocity key to denuclearization process 2018-10-24
  • 拥有7.2亿美元比特币大金主突然苏醒 数字货币“吓跌” 2018-10-24
  • ::紫光阁::中共中央国家机关工作委员会 2018-10-23
  • 3名中国游客在瑞典遭粗暴对待 外交部敦促瑞方重视中方关切 2018-10-21
  • 国足20-0大胜!女梅西6球,女C罗轰5球,男足才赢19-0 2018-10-21
  • 消协提醒:春节预订酒店有技巧 预付卡消费需谨慎 2018-10-20
  • 陈敏尔唐良智会见传化集团董事长徐冠巨 2018-10-20
  • 扫黑除恶利剑高悬 前8月榕查处违法采砂案件93起 2018-10-20
  • 不能让所谓的收视率愚弄观众 2018-10-18
  • 新希望!中超19岁新星半年增重十斤 曾戏耍恒大两国脚 2018-10-17
  • 迎丰收 晒丰收 庆丰收 2018-10-15
  • “捂脸表情”被注册成商标?申请人不认为商标侵权 2018-10-15
  • 战巡南海、绕岛巡航…空军有“飞出去”的主心骨 2018-10-14
  • 幼儿园要求家长写一万字读后感:不能这样玩家长|幼儿园|家长-教育时讯 2018-10-13
  • 中国故宫文物展在希腊举行 2018-10-13
  • 理解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处理等。