你好,游客 登录
背景:
阅读新闻

漫谈Hadoop的思想之源:Google

[日期:2017-11-23] 来源:网络大数据  作者: [字体: ]

  ( )Google介绍

  谷歌公司(Google Inc.)成立于1998年9月4日,由拉里·佩奇和谢尔盖·布林共同创建,被公认为 较大的搜索引擎。

  谷歌是 家位于美国的跨国科技企业,业务包括互联网搜索、云计算、广告技术等,同时开发并提供大量基于互联网的产品与服务,其主要利润来自于AdWords等广告服务。

  1999年下半年,谷歌网站“Google”正式启用。 2010年3月23日,宣布关闭在中国大陆市场搜索服务。2015年8月10日,宣布对企业架构进行调整,并创办了 家名为Alphabet的“伞形公司”(Umbrella Company),成为Alphabet旗下子公司。2015年,在2015年度“ 品牌500强”排行中重返榜,苹果和亚马逊分别位居和第三名。2016年6月8日,《2016年BrandZ 较具价值品牌百强榜》公布,以2291.98亿美元的品牌价值重新超越苹果成为百强第 。2017年2月,Brand Finance发布2017年度 500强品牌榜单,排名第 。 2017年6月,《2017年BrandZ较具价值 品牌100强》公布,谷歌公司名列第 位。

  (二)hadoop的思想之源:Google

  Hadoop的思想之源是什么呢,就是我们非常熟悉的 个东西,就是Google,Google是 个搜索引擎,我相信在过去的几年里,不管你是做IT的,还是不是做IT的,或多或少多会接触过Google。如果你没接触过Google,在今天,可能你的生活质量会受到影响。

  Google搜索引擎,Gmail,安卓(我们手机上用的操作系统,android也是google的产品),Google Map,Google学术(在学术界的人,经常就用Google学术),Google earth,Google 翻译,Google +(社交产品),说了这么多,Google的服务也在不断的扩展中,我们也无法预料Google下 阶段会出什么产品。

  (三)Google的低成本之道

  不使用超 计算机,不使用存储(淘宝的去I,去o,去e之路)

  大量使用普通的PC服务(去掉机箱,外设,硬盘),提供有冗余的集群

  全 多个数据,有些附带发电厂

  运营商向Google倒付费。

  (四)集装箱数据

  提及数据,除传统意义机房、冷却的大型“落地”部署数据,Sun较早提出集装箱数据的概念,并于06年推出了 集装箱数据产品Blackbox,但在Sun被Oracle收购后并没有真正推广应用。

  但是集装箱数据市场的发展并没有因此停滞不前。相反,越来越多的IT厂商开始涉足这 领域,Google、微软等厂商在集装箱数据市场展开了比拼。

  集装箱数据充分发挥了模块化设计的优势,可以实现系统的快速、灵活部署,这不仅可以大幅降低建设成本,而且能够大幅缩短数据的建设周期。集装箱数据是 个预配置的完整解决方案,可以随时移动到任何地点,只要有电和网络就能工作,从而省去了用于土地审批和厂房建设的大量资金,节约了成本。

大数据

  就搜索巨头谷歌来说,为了满足应用的需求习惯自己设计和开发服务器、存储系统等。从2005年开始,Google就在数据里采用了集装箱式设计,每个集装箱能容纳1160台服务器。Google集装箱数据有许多特别之处,其中主要是自用并不具备通用性。

  Google集装箱数据的设计着重于“电源在上,水在下”,机架从集装箱的天花板悬挂下来,冷却设备在机架下面,让冷空气通过机架。冷却风扇速度可变,并可以精确管理,保证风扇在能够冷却机架的前提下运行在较低速度。

\

  (五)Google面对的数据和计算难题

  大量的网页怎么存储

  搜索算法

  Page-Rank计算问题

  (六)倒排索引:

  google如何快速的搜索网页,能够在0.0000000几秒就能够将数据搜索出来呢,这里面主要使用了 个倒排索引的技术。

  先假设有 篇文章,将这篇文章分词,(我爱北京天安门),假如有 种分词(我,爱,北京,天安门)索引怎么做呢,先单词ID是 个编号,唯 标识号,后面的倒排列表是什么意思呢,(1;1)表示这个单词出现在标识号为1的那个网页里面,它的偏移量是第 个位置,我们在查找的时候,Google会查找这张表,查到我这个单词,在右边会得到 系列的倒排列表,通过倒排列表我们可以把文章找出来,通过偏移量我们可以定位该词的位置。对于西文,由于单词之间有空格,相对来说比较容易分词,对于中文,日文,由于词汇之间没有明显的分界,所以相对来说分词会比较难,其中有 种方法就是使用字典。(讲解我爱北京天安门得劲分词)。当然中文的分词还有很多,百度今天之所以这么成功,是因为它对中文的分词能力是比较强的。关于研究这个语言的分词是 个很大的学术领域,在今天有很多的数据科学家在这里面工作。

\
\

  (七)page Rank算法:

  这是Google较核心的算法,用于给每个网页价值评分,是google“在垃圾中找”的关键算法,这个算法成就了今天的Google。

\
\

  Google并没有公开发表过pageRank这个算法,这个算法是根据Google早期发表的 些论文大家推测出来的,具体现在google怎么计算呢,我也不知道,但是大体的思想还是这个思想,在 些具体的运算会有 些更加复杂的地方。我们这个模型尽管对大家来说已经很复杂了,但是对Google来说还是很简单的。Google今天不会这么简单来算的。

  自从Google有了PageRank之后,它可以把垃圾变为,他可以在 大堆垃圾数据,爬虫怕回来的数据里面找到用户所需要的东西,所以Google的用户体验要比其它的搜索引擎要好,所以用户都聚集在Google搜索平台上面,把其它的搜索引擎就都淘汰掉了,所以Google能称为今天的巨人不是偶然的,PageRank在这里面起到了非常非常重要的作用。

  Pagerank的想法是怎么样的呢,非常简单,我们怎么样判断 个页面的价值呢,根据页面的文字数来判断么,这个当然不可能,根据访问量,这个页面点击的越多,我们认为这个页面越有价值,这个听起来很有道理,但事实上是行不通的,因为google爬虫在爬取这个网页的时候,它不可能获取这个网页的点击数,点击数只有站长才知道,其它人是不知道的,所以也不能作为 个根据。google只能根据它从网页爬取的网页的信息来进行判断。Google的想法是怎么样的呢,根据页面的链接关系来判断 个页面的价值,如果有 个页面他被别人指向的越多,像四号页面,大家都指向它,就说明他是比较重要的,若有 个页面大家都不指向他,1号页面,说明1号页面就不是 个很重要的页面。可能有人认为这个太简单了,我把这个页面拿回来,数数里面的链接数就可以了,其实,也没有那么简单,还有 个问题就是这个网站的价值本身是不 样的,如果你的个人网站有另外 个个人网站指向你,这个好像没有什么稀奇,但如果中国国务院的网站指向你,就说明你比较重要了,这里有 个问题,就是中国国务院的网站的价值跟某位同学的网站的价值是完全不 样的,或者用Google的说法可以这么说,如果有 个pageRank比较高的网站指向你,跟 个PageRank比较低的网站指向你,这两个链接指向你的价值是不 样的,我么在计算的时候需要把这个因素考虑进去。

  下面我们看 下Google是怎么样建立数学模型,并且求解出PageRank的,我们先根据网页互相指向的信息,先做 个简单的情况,有1,2,3,4,四个网站,它们之间互相指来指去,先根据互相指向的信息,得到 个Google矩阵,这个矩阵的每 个列代表网页,第 列,代表是第 个网页,列,代表是个网页,以此类推,每 行也代表 个网页,第 行代表第 个网页,行,代表是个网页,以此类推。我们先看第 列,这里面有0,也有非0的值,0就代表没有连接,非0代表有连接,1没有链接指向自己,所以这里是0,1有连接指向2,所以这里是非零值,同样,1有连接指向3,所以这里页是非零值,四也 样,这里有 个问题,1/3是如何来的呢,原因很简单,每 列 共有1个权值,它有三个外链出去,所以每个链就分到1/3,所以这里就是1/3了,列就是个网页向外指出的情况,比如说,个网页有 个链接指向3,所以在列第三行有 个非零值,列这有 个链接指向4,所以在列第四行也有 个非零值,有两个外链共同来分权值1,所以每个能分为1/2,余下的两列也依此类推,google的矩阵就是这么来的。

  之后该如何计算呢,要对Google矩阵做 点点轻微的调整,使用公式 G=αS+(1-α)U/n

  其中S就是我们刚刚求出来的原始矩阵,α是0到1之间的 个数,这个数字会经常做调整,调整以后,可以影响PageRank的值,这个α是Google的工程师根据他们的经验来决定,这个α值具体取多少,才可以是pageRank的区分效果较好,这个是他们通过大量的实验摸索出来的,这个我们不需要管,现在也有可能使用机器学习来计算这个值。n是节点的数,这里就是4.U是 个全部元素都是1的矩阵,我们用这个(1-α)U/n矩阵加上αS矩阵,就形成了真正的google矩阵。pageRank是什么东西呢,是这个矩阵的特征值,以及特征向量,是这个矩阵的特征向量,特征向量是什么意思呢,我们把这个矩阵G乘以 个向量,加入这个矩阵是4乘以4的话,q应该是有四个元素的列向量,我们需要找 个q,使这个G乘以q,结果还是等于q,因此我们把求页面价值的问题,转为求 个很庞大的矩阵的特征值的问题。变成 个数学问题。这个特征值 般采用迭代的方法来算,我们给 个原始的向量q,q可以随意写,把这个元素不断地乘以G,Google在它的论文里面证明了,这样 直迭代下去,它 定是收敛的。所以我们可以预先设定 个阈值,当迭代到 定的次数后,q与上 次迭代出来的q的距离小于这个阈值,我们就停止迭代的过程。就把这个q拿出来作为 个近似解,这个就是pageRank,我就算出来了。

  数学上轻描淡写,非常简单,实际上我们用计算机上来算的时候是不是那么简单呢,这个肯定没有那么简单,为什么,大家想 想就知道了,这个矩阵有多大呢,不说多了,假设有 百万个网页,这个已经是很小的 个数字了,因为Google有上亿个网页。假设为1百万个网页的时候,矩阵的元素有多少呢, 百万乘以 百万, 万个亿,在任何 台服务器都是无法实现的,只能证明理论上是可行的,并且特征向量是符合我们要求的东西,编写程序的时候是无法实现的。所以产生了Map-reduce 思想。

  (八)Map-Reduce想法

  如果什么运算是 台计算机解决不了的,那么就是很多台计算机来解决。所以Google采用了不仅 台计算机来算,而是很多台计算机采用分布式的方式来以。如下图所示,每 个节点里面都会被分配这个矩阵里面的若干个列,在现实中我们可以理解,其实我们的网页在现实中分布在很多服务器节点上面。每个服务器都存放了若干个网页,但不会存放全部的网页,从网页上我们能分析出,它有哪些外链指向出来,因此Google矩阵的某个列在这个节点上是能够算出来的。如何算,我生成 个特征向量,有q1,q2,q3,q4,…,qn。假设第 个节点有2个列,我通过网络把q1,q2送过来,给第 个节点,假设个节点有两个列,我通过网络把q3,q4送过来,其它节点以此类推,在第 个节点我算q1乘以第 个列,q2乘以个列,算出这个列的结果,个节点依此类推。由于每个节点的网页数都不会很多,所以每个节点都可以很快的计算出结果出来。较后把所有算出来的结果发到 个共同的目标节点,在该节点把所有的列加起来,由于节点数有限,因此目标节点将所有的列都加起来也不是很困难的事情,因此我们在目标节点处得到 个向量,迭代第 步产生的特征向量。将该项不同的列的值量重新分配到各个节点上,在进行计算,计算后在汇总到该节点上,产生新的特征向量,不断的迭代,迭代到收敛值为止,知道产生符合的结果。通过这个方法,pageRank就可以进行计算了,这种用分散的节点来分负荷进行计算的思想,就是我们今天所说的map-reduce。我们将 个巨大的任务,我们认为不可能完成的任务,通过map映射到各个节点,来进行分布式计算。在每个节点算出这个值之后,较后汇总到 个节点上去,这个汇总的过程,我们把它叫Reduce,reduce之后,我们又把汇总的结果分散到各个节点上去,在map 次,又重新计算,在reduce 次。反复Map-reduce很多次以后,这个page-rank就被我们算出来了。

\

  (九)Google带给我们的思想

  GFS(Google file system)----Hadoop的HDFS

  Map-Reduce--Hadoop Map-Reduce

  Bigtable----Hbase





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款