google.com 首页代码分析

Posted by 冰河 at 18:56 No Responses » 5,268 Views
262010

机缘巧合,对 google.com 的首页代码产生了浓厚兴趣。一点“分析”,杂记如下:

不同浏览器推送不同代码
google_src_diff.png

上图是在不同浏览器下,保存的 google 首页代码。

注意:文件大小是经过 IntelliJ IDEA 格式化处理后的大小,请查看:lab/2009/google.

其中 Chrome 和 Safari 的代码是一样的,Opera 仅仅一个 js 函数的写法与 Chrome 不同。差异最大的是 Firefox 和 IE。

我的想法:大部分应用场景下,针对不同浏览器实现不同版本,会增加开发和维护成本。google 首页采取这种差异化方案,很可能是考虑到要最大限度降低网页流量。毕竟对于日访问量上千万的网站来说,减少一个字符都能节约可观的流量。精简节约,在 google 首页上体现得淋漓尽致,下面会继续提及。

doctype 的写法

只有 Firefox 用了《!doctype html》来激活标准模式。其它浏览器下,都是简单粗暴的 Quirks 模式。

我的想法:Firefox 下也可以直接用 Quirks 模式,视觉差异上极小。不清楚 google 为何仅针对 Firefox 开启了标准模式。

值得注意的是,在 google 搜索结果页,所有浏览器下都使用了《!doctype html》。 毕竟结果页复杂些,依旧用 Quirks 模式的话,会增加开发成本。首页因为简单,Quirks 和 Standards 相比,没什么显著差别,因此能省就省。

关于 doctype, 强烈推荐阅读:Activating Browser Modes with Doctype

对浏览器来说,doctype 实际上仅影响浏览模式,因此能从简就从简。W3C 校验,我觉得没必要,很少关注。

精简,还是精简

以 Firefox 下 google 首页的源码为例:

html, body 缺胳膊少腿

html 元素的很多属性没有用双引号括起来

class, id 等命名很短

script 和 style 元素没 type 等属性

没有 keywords 和 description 等 meta 值,我是搜索老大,哈哈

balabala 等等

想起一句话:遵守规范的一个重要标准,就是知道何时打破它,并大胆地打破。从这层意义上讲,google 首页是非常遵守规范的。

没有完美

细心点,还可以发现:

引号去得不彻底,比如《img alt=“Google” 。..

还有padding-left: 0px, px 可以去掉

js 上,也有进一步精简的余地。比如下面两行完全一样的代码,很?:

if(google.y) google.y.first = [];

if(google.y) google.y.first = [];

还有一段代码,div 提前到 script 前面能省去判断:

《script》

function wgjp() {

var xjs = document.createElement(‘script’);

xjs.src = ‘/extern_chrome/1mZ_-PL2Zjc.js’;

(document.getElementById(‘xjsd’) || document.body).appendChild(xjs)

};

《/script》

《div id=xjsd》《/div》

也许吹毛求疵了,笑过。

预加载

看代码:

《body onload=“sf();if(document.images){new Image().src=‘/images/nav_logo4.png’}” 。..

这就是 YSlow 34条性能法则中的 Preload Components. google 首页提前加载了搜索结果页的 css sprite. 另外赞一下这个 sprite 图的组织,很 cute.

延迟加载

看代码:

window.setTimeout(function() {

var a = document.createElement(“script”);

a.src = “/extern_js/f/。../XRt_2Y4Z5sM.js”;

(document.getElementById(“xjsd”) || document.body).appendChild(a)

}, 0);

上面这个 js 挺大的,包含了 google 的 js 库和输入框的提示补全组件。这个 setTimeout 起到了将下载进程延迟到 window.onload 后。很小的代码调整,却提升了不少用户体验,实在划算。

另提一下,这个 js 在不同浏览器下也有不同版本,大小差异比较明显。为了尽可能减少流量,google 还真费心。

奇淫技巧

代码虽少,淫荡之处却摇曳生姿:

1. 遍历数组

for (var i = 0,c; c = [“ad”,“p”,“pa”,“zd”,“ac”,“pc”,“pah”,“ph”,“zc”][i++];) {

// doing something, such as console.log(c)

}

2. 短路语句

function _gjp() {

!(window._gjwl.hash && window._gjuc()) && setTimeout(_gjp, 500)

}

短路表达式很常用,但用短路单独做语句,还真精简。

语义化

从语义上讲,google 的 html 代码是比较糟糕的。但考虑到各种浏览终端,或许 google 目前的写法非常优化。没有接触过跨n 》 20的浏览器开发经验,对此不多说。

小结

从首页代码中,能看出 google 推崇的是:简单 + 实用 + 性能。我越来越认同这种观点。

1/12/2010 03:00:00 PM

Like many other well-known organizations, we face cyber attacks of varying degrees on a regular basis. In mid-December, we detected a highly sophisticated and targeted attack on our corporate infrastructure originating from China that resulted in the theft of intellectual property from Google. However, it soon became clear that what at first appeared to be solely a security incident–albeit a significant one–was something quite different.

First, this attack was not just on Google. As part of our investigation we have discovered that at least twenty other large companies from a wide range of businesses–including the Internet, finance, technology, media and chemical sectors–have been similarly targeted. We are currently in the process of notifying those companies, and we are also working with the relevant U.S. authorities.

Second, we have evidence to suggest that a primary goal of the attackers was accessing the Gmail accounts of Chinese human rights activists. Based on our investigation to date we believe their attack did not achieve that objective. Only two Gmail accounts appear to have been accessed, and that activity was limited to account information (such as the date the account was created) and subject line, rather than the content of emails themselves.

Third, as part of this investigation but independent of the attack on Google, we have discovered that the accounts of dozens of U.S.-, China- and Europe-based Gmail users who are advocates of human rights in China appear to have been routinely accessed by third parties. These accounts have not been accessed through any security breach at Google, but most likely via phishing scams or malware placed on the users’ computers.

We have already used information gained from this attack to make infrastructure and architectural improvements that enhance security for Google and for our users. In terms of individual users, we would advise people to deploy reputable anti-virus and anti-spyware programs on their computers, to install patches for their operating systems and to update their web browsers. Always be cautious when clicking on links appearing in instant messages and emails, or when asked to share personal information like passwords online. You can read more here about our cyber-security recommendations. People wanting to learn more about these kinds of attacks can read this U.S. government report (PDF), Nart Villeneuve’s blog and this presentation on the GhostNet spying incident.

We have taken the unusual step of sharing information about these attacks with a broad audience not just because of the security and human rights implications of what we have unearthed, but also because this information goes to the heart of a much bigger global debate about freedom of speech. In the last two decades, China’s economic reform programs and its citizens’ entrepreneurial flair have lifted hundreds of millions of Chinese people out of poverty. Indeed, this great nation is at the heart of much economic progress and development in the world today.

We launched Google.cn in January 2006 in the belief that the benefits of increased access to information for people in China and a more open Internet outweighed our discomfort in agreeing to censor some results. At the time we made clear that “we will carefully monitor conditions in China, including new laws and other restrictions on our services. If we determine that we are unable to achieve the objectives outlined we will not hesitate to reconsider our approach to China.”

These attacks and the surveillance they have uncovered–combined with the attempts over the past year to further limit free speech on the web–have led us to conclude that we should review the feasibility of our business operations in China. We have decided we are no longer willing to continue censoring our results on Google.cn, and so over the next few weeks we will be discussing with the Chinese government the basis on which we could operate an unfiltered search engine within the law, if at all. We recognize that this may well mean having to shut down Google.cn, and potentially our offices in China.

The decision to review our business operations in China has been incredibly hard, and we know that it will have potentially far-reaching consequences. We want to make clear that this move was driven by our executives in the United States, without the knowledge or involvement of our employees in China who have worked incredibly hard to make Google.cn the success it is today. We are committed to working responsibly to resolve the very difficult issues raised.

Posted by David Drummond, SVP, Corporate Development and Chief Legal Officer

附录:读者Jason Liu翻译的Google官方博客文章:A new approach to China

像 很多知名的公 司一样,我们每天都在遭受着或多或少不同程度的网络攻击.在12月中旬,我们监测到了一个从中国来的对google网络基础架构的高智能的目标明确的攻 击,其目的是为了盗取google的技术资源.这个一开始被我们仅仅当成是一个重大安全事故的独立事件其实是另有来头的.

第一,这次攻击不仅仅针对google.我们的调查显示至少有20家大的公司,行业领域包括互联网,金融,科技,传媒,化工,都遭受了相似的攻击。我们正在通知这些公司,而且我们正在与美国相关领域的专家进行合作.

第 二.我们有证据显示这些黑客的主要目标是获取中国人权活动家(Chinese human rigths activists)们的gmail账号信息.调查显示这些黑客并没有达到他们的目的。只有两个账户似乎被侵入,但是仅得到了账户的一般信息(比如说账户 是何时建立的)和邮件的标题,并没有得到邮件的内容。

第三,作为这次调查的另一部分,我们发现很多个在中国,美国,欧 洲致力于中国人权发展的用户的gmail账户经常被第三方人士查阅.这些第三方人士并不是通过google的安全漏洞来获取gmail信息的,而是通过网 络钓鱼和在用户的计算机上运行恶意软件的方法来获取用户的gmail邮件信息.

我们已经通过这次攻击所收集到的信息对 我们的架构做出了修正以提升google和我们用户的安全。对于个人用户来说,我们推荐用户安装知名的杀毒软件和反间谍程序,为自己的操作系统打上最新的 补丁,升级自己的浏览器,始终小心处理im和email中的链接,在网络上被要求告知个人信息比如密码时保持警惕。你可以通过这里获取我们关于网络安全的 建议。希望了解关于这些网络攻击的种类的人可以阅读这份美国政府报告(pdf), Nart Villeneuve 的blog 还有这份这份关于ghostnet间谍事件的介绍(wiki上有介绍,跟咱中国又有关系).

我 们已经采取了非常规的手段–与广大的相关人士交流这次攻击的信息,这样做不仅仅是因为这次事件中我们发掘出来的安全和人权问题,更重要的是这件事的 核心其实是全世界关于言论自由的讨论.在过去的20年中,中国的经济改革和人民的商业头脑使中国数以亿计的中国人脱离了贫困.在当今世界,这个巨大的国家 是整个世界经济发展的中心。

我们在2006年的1月成立了google中国。我们相信与我们必须忍受中国政府的某些内容审查而遭受到的不快相比,无疑让中国人接触到更多的信息和创造一个更加开放的互联网络是更为重要的事情。在当时我们确定了“我们将一直小心关注中国的情况,包括新出台的法律和其他政策制度对我们服务的限制。如果我们认为我们没有能力达到我们提出的目标(指创建一个更加开放的互联网络),我们将会毫不犹豫的考虑是否撤出中国市场”。

这 些攻击和审查,同时考虑到这些年对网络上子自由言论的限制,让我们觉得我们应该重新审视我们在中国业务的可行性.我们不愿意再继续忍受对我们 google.cn上内容的审查,接下来的几个星期内我们将会与中国政府讨论有关我们是否能够在法律允许的范围内运行一个没有审查和过滤的搜索引擎的可能 性。如果失败的话,这久可能意味着我们将要关闭google.cn,以及google中国。

做出这样一个决定是非常困难的一件事,而且我们明白这将会造成深远的后果。有一点要说清楚,这样的决策是由在美国的主管人员们所做出的,并没有到目前为止辛勤工作使google中国如此成功的中国部分员工的参与。我们将会负责任的解决这个棘手的问题。

David Drummond, 企业发展部高级副总裁 首席法务官

计算Google PageRank的php代码

Posted by 冰河 at 21:52 No Responses » 13,491 Views
十二 182009

可以方便调用。这段代码在windows和linux下都能用。

<?php
class PageRank
{
//settings – host and user agent
var $googlehost='www.google.com';
var $googleua='Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.6) Gecko/20060728 Firefox/1.5';
//convert a string to a 32-bit integer
function StrToNum($Str, $Check, $Magic) {
    $Int32Unit = 4294967296;  // 2^32
    $length = strlen($Str);
    for ($i = 0; $i < $length; $i++) {
        $Check *= $Magic;    
        //If the float is beyond the boundaries of integer (usually +/- 2.15e+9 = 2^31),
        //  the result of converting to integer is undefined
        //  refer to http://www.php.net/manual/en/language.types.integer.php
        if ($Check >= $Int32Unit) {
            $Check = ($Check – $Int32Unit * (int) ($Check / $Int32Unit));
            //if the check less than -2^31
            $Check = ($Check < -2147483648) ? ($Check + $Int32Unit) : $Check;
        }
        $Check += ord($Str{$i});
    }
    return $Check;
}
//genearate a hash for a url
function HashURL($String) {
    $Check1 = $this->StrToNum($String, 0×1505, 0×21);
    $Check2 = $this->StrToNum($String, 0, 0x1003F);
    $Check1 >>= 2;    
    $Check1 = (($Check1 >> 4) & 0x3FFFFC0 ) | ($Check1 & 0x3F);
    $Check1 = (($Check1 >> 4) & 0x3FFC00 ) | ($Check1 & 0x3FF);
    $Check1 = (($Check1 >> 4) & 0x3C000 ) | ($Check1 & 0x3FFF);   
    $T1 = (((($Check1 & 0x3C0) << 4) | ($Check1 & 0x3C)) <<2 ) | ($Check2 & 0xF0F );
    $T2 = (((($Check1 & 0xFFFFC000) << 4) | ($Check1 & 0x3C00)) << 0xA) | ($Check2 & 0xF0F0000 );
    return ($T1 | $T2);
}
//genearate a checksum for the hash string
function CheckHash($Hashnum) {
    $CheckByte = 0;
    $Flag = 0;
    $HashStr = sprintf('%u', $Hashnum) ;
    $length = strlen($HashStr);
    for ($i = $length – 1;  $i >= 0;  $i –) {
        $Re = $HashStr{$i};
        if (1 === ($Flag % 2)) {             
            $Re += $Re;    
            $Re = (int)($Re / 10) + ($Re % 10);
        }
        $CheckByte += $Re;
        $Flag ++;   
    }
    $CheckByte %= 10;
    if (0 !== $CheckByte) {
        $CheckByte = 10 – $CheckByte;
        if (1 === ($Flag % 2) ) {
            if (1 === ($CheckByte % 2)) {
                $CheckByte += 9;
            }
            $CheckByte >>= 1;
        }
    }
    return '7'.$CheckByte.$HashStr;
}
//return the pagerank checksum hash
function getch($url) { return $this->CheckHash($this->HashURL($url)); }
//return the pagerank figure
function getrank($url)
{
    $urlinfo=parse_url($url);
    $start=$urlinfo["scheme"]<>""?strlen($urlinfo["scheme"]."://"):0;
    $url=substr($url,$start);
    $pr = -1;    // default return
    $ch = $this->getch($url);
    $fp = fsockopen("www.google.com", 80, $errno, $errstr, 30);
    if ($fp) {
       $out = "GET /search?client=navclient-auto&ch=$ch&features=Rank&q=info:$url HTTP/1.1
";
       //echo "<pre>$out</pre>"; //debug only
       $out .= "User-Agent: {$this->googleua}
";
       $out .= "Host: www.google.com
";
       $out .= "Connection: Close

";
       fwrite($fp, $out); 
       //$pagerank = substr(fgets($fp, 128), 4); //debug only
       //echo $pagerank; //debug only
       while (!feof($fp)) {
            $data = fgets($fp, 128);
            //echo $data;
            $pos = strpos($data, "Rank_");
            if($pos === false){} else{
                $pr=substr($data, $pos + 9);
                $pr=trim($pr);
                $pr=str_replace("",'',$pr);
                return $pr;
            }
       }
       //else { echo "$errstr ($errno)<br />"; } //debug only
       fclose($fp);
    }
    return $pr;
    }
}
//$gpr = new PageRank();
//echo $gpr->printrank("http://www.baidu.com/");
?>

Goolge DNS vs. OpenDNS

Posted by 冰河 at 21:41 No Responses » 11,807 Views
十二 182009

1.Google推出免费DNS服务

谷歌发布了 Google Public DNS 服务,利用这个服务我们可以:

  1. 加快 DNS 解析速度从而加快网页载入速度;
  2. 谷歌承诺不会给你重定向,避免一般 DNS 服务一打开敏感网页就给你重定向不知道哪里去;
  3. 更安全。

使用的方法是:

网络连接 → 本地连接 → 属性 → Internet 协议 (TCP/IP) → 属性 → DNS 服务器填入 8.8.8.8 和 8.8.4.4。

编注:

以上方法仅适用于 Windows 平台,Linux 系统可将这组 IP 加入 /etc/resolv.conf 文件:

nameserver 8.8.8.8
nameserver 8.8.4.4

使用 NetworkManager 的同学,设置方法请参考这里

2.OpenDNS

OpenDNS 是一个免费的域名解析服务提供商(DNS)。将DNS服务选项设置成如下两个地址便可以开始使用OpenDNS的服务:

  • 208.67.222.222 (Resolver1.OpenDNS.com)
  • 208.67.220.220 (Resolver2.OpenDNS.com)

OpenDNS 在 2006年7月由 黑客/创业者 大卫·尤里维奇(David Ulevitch)创建。之后获得了由CNET的创始人Halsey Minor创建的Minor Ventures公司提供的风险投资。 2006年7月10号,这项OpenDNS开始为digg、slashdot和Wired News网站提供服务,这直接导致DNS请求数从7月9日的一百万猛增到30日的三千万。 2006年10月2日,OpenDNS建立了第一个反钓鱼数据库Phishtank.com,收集、整理和发布钓鱼攻击信息。 2006年,OpenDNS开始使用DynDNS的接口来处理动态IP用户的DNS更新。 从2007年1月开始,OpenDNS开始在以下地区设置服务器来提供服务:西雅图、帕洛阿尔托、纽约、华盛顿和伦敦,并计划扩展到芝加哥和香港。 2007年6月11日,OpenDNS开始启用高级网页过滤系统来为他们的免费账户过滤成人内容。

OpenDNS 在 2006年7月由 黑客/创业者大卫·尤里维奇(David Ulevitch)创建。之后获得了由CNET的创始人Halsey Minor创建的Minor Ventures公司提供的风险投资。

2006年7月10号,这项OpenDNS开始为digg、slashdot和Wired News网站提供服务,这直接导致DNS请求数从7月9日的一百万猛增到30日的三千万。

2006年10月2日,OpenDNS建立了第一个反钓鱼数据库Phishtank.com,收集、整理和发布钓鱼攻击信息。

2006年,OpenDNS开始使用DynDNS的接口来处理动态IP用户的DNS更新。

从2007年1月开始,OpenDNS开始在以下地区设置服务器来提供服务:西雅图、帕洛阿尔托、纽约、华盛顿和伦敦,并计划扩展到芝加哥和香港。

2007年6月11日,OpenDNS开始启用高级网页过滤系统来为他们的免费账户过滤成人内容。

3.Google DNS vs. OpenDNS

Google今天宣布了一项新服务Google Public DNS,让消费者使用Google作为他们的DNS服务提供商。该服务给用户带来的好处是,理论上更快速、更稳定的浏览体验,以及针对恶意网站的更多安全 防护;而Google可以通过该服务获得大量的用户数据,以及某些可能的收入。目前Google Public DNS服务尚处于试验阶段,用户如果想使用它,必须修改网络设置,这样他们的网站访问请求才会被转向Google服务而不是ISP商。Google已经建立了专门网页来指导用户如何设置使用该服务。

该服务将直接挑战风投公司Sequoia和Greylock支持的OpenDNS服务,OpenDNS至今已经推出4年,目前每天解析200亿次DNS查询,拥有150万最终用户。

2008年,OpenDNS的日均解析量仅有70亿条,但是已经实现日进2万美元收入。其营收方式是,当用户输入了一个无法解析的网址时,该服务将显示它 自己的定制页面,其中包含搜索结果和广告。另外,企业用户非常愿意付费使用这种DNS服务,以防止用户访问恶意网站或其它网站(诸如色情网站或社交网站 Facebook等)。

不过,和OpenDNS不同的是,Google Public DNS并不重定向用户到广告页面。

针对Google推出DNS服务,OpenDNS创始人大卫·尤勒维什(David Ulevitch)在官方博客上发表了五点声明,他认为该服务与OpenDNS并不完全相同,而且Google推出DNS服务的举动也说明了DNS在互联 网架构中的关键作用,以及帮助用户安全、可靠地浏览互联网的战略重要性。另外尤勒维什还指出,Google是互联网上最大的广告和重定向公司。

Google Public DNS产品经理普瑞姆·拉玛斯瓦米(Prem Ramaswami)表示,该服务的目标是快速、安全和有效的DNS响应。他表示,Google将严格遵循DNS协议,即不阻挡、不劫持和不过滤用户查询。

Google还透露了该服务将收集的数据类型和保存时间。收集的数据包含IP地址(最长保存48小时,以检测针对该服务的恶意行为)、ISP信息和地理位置信息(最长保存2周)。这些数据将不会以任何方式关联用户的Google帐号。

据普瑞姆表示,普通用户每天大约进行1000次DNS查询。

十二 182009

微软著名的C++大师Herb Sutter在2005年初的时候曾经写过一篇重量级的文章:”The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software“,预言OO之后软件开发将要面临的又一次重大变革-并行计算。

摩尔定律统制下的软件开发时代有一个非常有意思的现象:”Andy giveth, and Bill taketh away.”。不管CPU的主频有多快,我们始终有办法来利用它,而我们也陶醉在机器升级带来的程序性能提高中。

我记着我大二的时候曾经做过一个五子棋的程序,当时的算法就是预先设计一些棋型(有优先级),然后扫描棋盘,对形势进行分析,看看当前走哪部对自己 最重要。当然下棋还要堵别人,这就需要互换双方的棋型再计算。如果只算一步,很可能被狡猾的对手欺骗,所以为了多想几步,还需要递归和回朔。在当时的机器 上,算3步就基本上需要3秒左右的时间了。后来大学毕业收拾东西的时候找到这个程序,试了一下,发现算10步需要的时间也基本上感觉不出来了。

不知道你是否有同样的经历,我们不知不觉的一直在享受着这样的免费午餐。可是,随着摩尔定律的提前终结,免费的午餐终究要还回去。虽然硬件设计师还 在努力:Hyper Threading CPU(多出一套寄存器,相当于一个逻辑CPU)使得Pipeline尽可能满负荷,使多个Thread的操作有可能并行,使得多线程程序的性能有 5%-15%的提升;增加Cache容量也使得包括Single-Thread和Multi-Thread程序都能受益。也许这些还能帮助你一段时间,但 问题是,我们必须做出改变,面对这个即将到来的变革,你准备好了么?

Concurrency Programming != Multi-Thread Programming。很多人都会说MultiThreading谁不会,问题是,你是为什么使用/如何使用多线程的?我从前做过一个类似AcdSee 一样的图像查看/处理程序,我通常用它来处理我的数码照片。我在里面用了大量的多线程,不过主要目的是在图像处理的时候不要Block住UI,所以将 CPU Intensive的计算部分用后台线程进行处理。而并没有把对图像矩阵的运算并行分开。

我觉得Concurrency Programming真正的挑战在于Programming Model的改变,在程序员的脑子里面要对自己的程序怎样并行化有很清楚的认识,更重要的是,如何去实现(包括架构、容错、实时监控等等)这种并行化,如何去调试,如何去测试。

在Google,每天有海量的数据需要在有限的时间内进行处理(其实每个互联网公司都会碰到这样的问题),每个程序员都需要进行分布式的程序开发, 这其中包括如何分布、调度、监控以及容错等等。Google的MapReduce正是把分布式的业务逻辑从这些复杂的细节中抽象出来,使得没有或者很少并 行开发经验的程序员也能进行并行应用程序的开发。

MapReduce中最重要的两个词就是Map(映射)和Reduce(规约)。初看Map/Reduce这两个词,熟悉Function Language的人一定感觉很熟悉。FP把这样的函数称为”higher order function”(”High order function”被成为Function Programming的利器之一哦),也就是说,这些函数是编写来被与其它函数相结合(或者说被其它函数调用的)。如果说硬要比的化,可以把它想象成C 里面的CallBack函数,或者STL里面的Functor。比如你要对一个STL的容器进行查找,需要制定每两个元素相比较的 Functor(Comparator),这个Comparator在遍历容器的时候就会被调用。

拿前面说过图像处理程序来举例,其实大多数的图像处理操作都是对图像矩阵进行某种运算。这里的运算通常有两种,一种是映射,一种是规约。拿两种效果 来说,”老照片”效果通常是强化照片的G/B值,然后对每个象素加一些随机的偏移,这些操作在二维矩阵上的每一个元素都是独立的,是Map操作。而”雕 刻”效果需要提取图像边缘,就需要元素之间的运算了,是一种Reduce操作。再举个简单的例子,一个一维矩阵(数组)[0,1,2,3,4]可以映射为 [0,2,3,6,8](乘2),也可以映射为[1,2,3,4,5](加1)。它可以规约为0(元素求积)也可以规约为10(元素求和)。

面对复杂问题,古人教导我们要“分而治之”,英文中对应的词是”Divide and Conquer“。Map/Reduce其实就是Divide/Conquer的过程,通过把问题Divide,使这些Divide后的Map运算高度并 行,再将Map后的结果Reduce(根据某一个Key),得到最终的结果。

Googler发现这是问题的核心,其它都是共性问题。因此,他们把MapReduce抽象分离出来。这样,Google的程序员可以只关心应用逻 辑,关心根据哪些Key把问题进行分解,哪些操作是Map操作,哪些操作是Reduce操作。其它并行计算中的复杂问题诸如分布、工作调度、容错、机器间 通信都交给Map/Reduce Framework去做,很大程度上简化了整个编程模型。

MapReduce的另一个特点是,Map和Reduce的输入和输出都是中间临时文件(MapReduce利用Google文件系统来管理和访问这些文件),而不是不同进程间或者不同机器间的其它通信方式。我觉得,这是Google一贯的风格,化繁为简,返璞归真。

接下来就放下其它,研究一下Map/Reduce操作。(其它比如容错、备份任务也有很经典的经验和实现,论文里面都有详述)

Map的定义:

Map, written by the user, takes an input pair and produces a set of intermediate key/value pairs. The MapReduce library groups together all intermediate values associated with the same intermediate key I and passes them to the Reduce function.

Reduce的定义:

The Reduce function, also written by the user, accepts an intermediate key I and a set of values for that key. It merges together these values to form a possibly smaller set of values. Typically just zero or one output value is produced per Reduce invocation. The intermediate values are supplied to the user’s reduce function via an iterator. This allows us to handle lists of values that are too large to fit in memory.

MapReduce论文中给出了这样一个例子:在一个文档集合中统计每个单词出现的次数。

Map操作的输入是每一篇文档,将输入文档中每一个单词的出现输出到中间文件中去。

map(String key, String value):
    // key: document name
    // value: document contents
    for each word w in value:
        EmitIntermediate(w, “1″);

比如我们有两篇文档,内容分别是

A - “I love programming”

B - “I am a blogger, you are also a blogger”。

B文档经过Map运算后输出的中间文件将会是:

	I,1
	am,1
	a,1
	blogger,1
	you,1
	are,1
	a,1
	blogger,1

Reduce操作的输入是单词和出现次数的序列。用上面的例子来说,就是 (”I”, [1, 1]), (”love”, [1]), (”programming”, [1]), (”am”, [1]), (”a”, [1,1]) 等。然后根据每个单词,算出总的出现次数。

reduce(String key, Iterator values):
    // key: a word
    // values: a list of counts
    int result = 0;
    for each v in values:
        result += ParseInt(v);
    Emit(AsString(result));

最后输出的最终结果就会是:(”I”, 2″), (”a”, 2″)……

实际的执行顺序是:

  1. MapReduce Library将Input分成M份。这里的Input Splitter也可以是多台机器并行Split。
  2. Master将M份Job分给Idle状态的M个worker来处理;
  3. 对于输入中的每一个<key, value> pair 进行Map操作,将中间结果Buffer在Memory里;
  4. 定期的(或者根据内存状态),将Buffer中的中间信息Dump到本地磁盘上,并且把文件信息传回给Master(Master需要 把这些信息发送给Reduce worker)。这里最重要的一点是,在写磁盘的时候,需要将中间文件做Partition(比如R个)。拿上面的例子来举例,如果把所有的信息存到一个 文件,Reduce worker又会变成瓶颈。我们只需要保证相同Key能出现在同一个Partition里面就可以把这个问题分解。
  5. R个Reduce worker开始工作,从不同的Map worker的Partition那里拿到数据(read the buffered data from the local disks of the map workers), 用key进行排序(如果内存中放不下需要用到外部排序 – external sort)。很显然,排序(或者说Group)是Reduce函数之前必须做的一步。 这里面很关键的是,每个Reduce worker会去从很多Map worker那里拿到X(0<X<R) Partition的中间结果,这样,所有属于这个Key的信息已经都在这个worker上了。
  6. Reduce worker遍历中间数据,对每一个唯一Key,执行Reduce函数(参数是这个key以及相对应的一系列Value)。
  7. 执行完毕后,唤醒用户程序,返回结果(最后应该有R份Output,每个Reduce Worker一个)。

可见,这里的分(Divide)体现在两步,分别是将输入分成M份,以及将Map的中间结果分成R份。将输入分开通常很简单,Map的中间结果通常 用”hash(key) mod R”这个结果作为标准,保证相同的Key出现在同一个Partition里面。当然,使用者也可以指定自己的Partition Function,比如,对于Url Key,如果希望同一个Host的URL出现在同一个Partition,可以用”hash(Hostname(urlkey)) mod R”作为Partition Function。

对于上面的例子来说,每个文档中都可能会出现成千上万的 (”the”, 1)这样的中间结果,琐碎的中间文件必然导致传输上的损失。因此,MapReduce还支持用户提供Combiner Function。这个函数通常与Reduce Function有相同的实现,不同点在于Reduce函数的输出是最终结果,而Combiner函数的输出是Reduce函数的某一个输入的中间文件。

Tom White给出了Nutch[2]中另一个很直观的例子,分布式Grep。我一直觉得,Pipe中的很多操作,比如More、Grep、Cat都类似于一种Map操作,而Sort、Uniq、wc等都相当于某种Reduce操作。

加上前两天Google刚刚发布的BigTable论文,现在Google有了自己的集群 – Googel Cluster,分布式文件系统 – GFS,分布式计算环境 – MapReduce,分布式结构化存储 – BigTable,再加上Lock Service。我真的能感觉的到Google著名的免费晚餐之外的对于程序员的另一种免费的晚餐,那个由大量的commodity PC组成的large clusters。我觉得这些才真正是Google的核心价值所在。

呵呵,就像微软老兵Joel Spolsky(你应该看过他的”Joel on Software”吧?)曾经说过,对于微软来说最可怕的是[1],微软还在苦苦追赶Google来完善Search功能的时候,Google已经在部署下一代的超级计算机了。

The very fact that Google invented MapReduce, and Microsoft didn’t, says something about why Microsoft is still playing catch up trying to get basic search features to work, while Google has moved on to the next problem: building Skynet^H^H^H^H^H^H the world’s largest massively parallel supercomputer. I don’t think Microsoft completely understands just how far behind they are on that wave.

注1:其实,微软也有自己的方案 – DryAd。问题是,大公司里,要想重新部署这样一个底层的InfraStructure,无论是技术的原因,还是政治的原因,将是如何的难。

注2:Lucene之父Doug Cutting的又一力作,Project Hadoop - 由Hadoop分布式文件系统和一个Map/Reduce的实现组成,Lucene/Nutch的成产线也够齐全的了。

© 2009 - 2024 冰河的博客