Hadoop Day 1

Hadoop起源:

Google的低成本之道:

1. 不使用超算，不使用存储（淘宝的去i，去e，去o之路）
2. 大量使用普通的pc服务器，提供有冗余的集群服务
3. 全世界多个数据中心，有些附带发电厂
4. 运营商（中国联通 电信） 向Google倒付费

可以把Hadoop理解成是一个山寨版的Google，它是基于Google的三篇论文（解决上图中的问题）提出，具体如下：

1. GFS(Google File System)
2. PageRank
3. Bigtable

其中GFS 是HDFS的雏形；Bigtable是HBase的雏形

而PageRank主要是解决如何量化一个网页的价值问题，google通过建立数学模型来量化网页的价值进而在搜索结果中排序(后面会讲),但是由于该数学模型涉及到百万数量级的矩阵乘法运算，这在世界范围内都找不到能够在秒级单位的Response Time，因此对模型的求解引发了Map-Reduce分布式处理的思想，也就有了Hadoop中Map-Reduced的由来。

倒排索引：

Google 搜索的数据量相当大，按照常人的思维，google搜索应该是全数据库检索，但是这就不符合Google 毫秒级的响应时间。 这里google借助了倒排索引，顾名思义，所谓倒排索引就是于正常相反，不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。
举个简单的例子以英文为例，下面是被索引的数据：

• T₀: “it is what it is”
• T₁: “what is it”
• T₂: “it is a banana”

通过分词我们可以得到如下的反向索引

“a”: {2}
“banana”: {2}
“is”: {0, 1, 2}
“it”: {0, 1, 2}
“what”: {0, 1}

搜索 “what is it” 就变成求关键字的交集 即
$${ 0,1 } \cap { 0,1,2 } \cap {0,1,2} = {0,1}$$

PageRank:

PageRank 是用来量化不同网页的价值的，它主要采用不同网页外连接到本网页的多少来量化，其实和期刊的影响因子计算类似，如果其他网页外链到本网页的数目也多，也就是本网页被其他网页引用次数越多，那么本网页的PageRank则高。

PageRank的具体算法如下

最后图中 q为所求的pagerank的解 q是矩阵G特征值为1的特征向量，求解可以通过随机初始化q^cur 不断迭代最后收敛。