Google显然要和Wikipedia拼一下。似乎选择了一个比较独特的角度，而不是和Wikipedia正面交锋？与维基百科按话题区分不同，Knol的重点是个人用户或用户群。Knol不编辑信息。只要作者不批准，用户不能修改信息，也不能写新信息，用户可以通知Google内容是否客观。这使得Knol看起来像一个WordPress MU，一个大博客，你可以在上面写任何东西…只不过分类只有一个——Knowledge。
此外，Knol首页的Slogan狠狠地雷了本人一下——”Who needs a search engine? Ctrl+F”。Google啊Google，太幽默。
[singlepic=15420,700,618]
[singlepic=14479,,,left]
Google Analytics（分析）是一款免费的 Web 分析产品，根据它提供的丰富详尽的图表式报告，网站管理员与营销人员可以更好地了解并影响访问者的行为，从而提高营销活动的投资回报率。
Google Analytics（分析）给网站管理员提供了这样一个途径：了解目前网站的状态，知道可以改进的方向。下面要做的事情就是每次只对网站作一次改动，并且给 Google Analytics（分析）一段时间，它会告诉您这次改动带来的改变是否符合预期。
就像 Google Analytics（分析）的高级经理 Brett Crosby 在 Analytics blog 里提到的：“不论您如何使用 Google Analytics（分析），最重要的是您已经在使用它。”您已经在试图通过对访问者行为的分析来理解您的访问者，并且朝着优化的方向努力。当您越了解访问者并且愿意朝着提升他们访问体验的方向努力时，也意味着您正走在一条通往拥有更多忠实访问者和提高您的投资回报率的康庄大道上。
1. Web分析产品之争
不可否认，JavaScript的登峰造极之作就是Web分析产品了。市面上有很多这样的产品可以选择，国内国外的都有，比如中国站长站，51.la都提供这样的分析产品，DreamHost之类的托管商也提供基于Apache日志的分析产品。我认为，Web分析工具是网站的核心工具之一，不应该随意的选择。
Google目前来看还是一个很负责任的公司，其产品值得信赖，关键的是Google Analytics确实也不错，尤其是其JavaScript控件库强大和完善，更是让我们这些JavaScript程序员无比崇拜。
[singlepic=14481,500,,center]
在这篇文章中，我想结合实际中的一个网站的数据信息，说明一下Google Analytics有什么用以及怎么用的问题。
2. Google Analytics原理及如何启用Google Analytics
Google Analytics是基于JavaScript的，只要把类似这样一段代码插入你的页面源代码中，就可以使用Google Analytics了。其中，UA-XXXXXXX-X是每创立一个分析帐户时生成的，你的帐户当然和我的不一样。
[code=’html’]
[/code]
或者使用新版本：
[code=’html’]
[/code]
主要原理是，将一个外链JavaScript脚本包含到本页中，然后设置一个参数，指定这是哪个站（即访问报告给哪个帐户），然后调用一个JavaScript函数，由里面的函数来收集当前用户的信息（IP，浏览器版本，当前页等等等等）。记录下信息之后，再用Google Analytics的网页来使用这些数据进行数据分析和数据挖掘。
3. 多元化分析的基础
注意一点，Google Analytics是一个网站分析工具，其数据基于对于网站浏览者的长期采样。一个刚刚使用Google Analytics的用户的数据是杂乱无章且没有多少意义的，长期使用，至少一个月，才能够看出趋势。
下图展示了一个较大的站最近两个月的数据。
[singlepic=14480,500,113,center]
可以观察到网站流量稳定在25000左右，但是在6月3日出现了一个奇点，这时候可以去网站搜索了一下这一天发生了什么事情，导致了这样的数据出现。原来，网站中包含一篇文章，是同济大学6月3日一场地震分析的报告会，被搜索引擎错误地当作6月3日地震预测的文章（是谣言！）排到了前面，这是应该主动去删除这样的不实信息（即便可能不是我们的错，而是搜索引擎的错误）。浏览量固然重要，但道德更重要，不要用谣言等手段骗取用户浏览。
下图是另外一个时间段的情况。明显观察到4月18日到4月20日数据出现了一个低谷。
[singlepic=14482,500,113,center]
这是因为，网站在这段时间由于内容审核被机房屏蔽了一段时间，不能够访问，网站管理员虽采取了转向到临时网站的策略，但仍旧因为内容不如原来丰富，导致流量大幅减少。
从上面可以看出，单纯看数据是没有意义的，应该数据结合网站的状况做多元化分析。
4. 浏览量数据
Google Analytics对数据进行区分，包括访问次数、绝对唯一访问者人数、综合浏览量、平均综合浏览量、网站停留时间、跳出率和新访问率。
[singlepic=14483,,,right]
5. 用户信息
Google Analytics还可以记录下用户使用机器的一些特征，比如浏览器及其版本、Java版本、Flash版本、操作系统语言等等信息。这些信息可以为网站设计者提供重要参考，可以根据比例来选择重点测试平台和采用那个版本的技术等等。
比如，作为专业Web开发人员的我可能会觉得FireFox很好很强大，并且在自己的机器上使用FireFox来浏览各种网站，那么能否就以FireFox上的显示效果为准来编写我的网页？当然不能。
[singlepic=14484,,,center]
上图可以看出，虽然FireFox很热，但是IE仍然是最重要的客户端浏览器，这意味着如果你编写了一段只能在FireFox上运行正常的页面，仍然将会在91.40%的用户浏览器里变成一团乱麻。
6. 来源分析
Google Analytics可以通过用户访问的HTTP refer信息整理分析用户是从哪里进入了你的网站。
[singlepic=14485,,,center]
从图上可以看出，用户来源基本四分天下，直接通过地址访问、通过Google、通过Baidu和通过其他方式数量基本差不多。进一步也可以看出，Baidu在中国还是很有市场份额的。
[singlepic=14477]
今天早上在Google上搜timezone的时候发现，Lab项目Google Code Search已经被集成进了搜索结果页面。如图：
[singlepic=14476,500,,center]
同济大学 计算机软件与理论 0720080247 李征
1. 矩阵乘法最优算法
1.1 矩阵与计算机科学
数学的重要性显而易见。数学是各种科学的基础，计算机也不例外。对于计算机学科起着关键性作用的数学分支主要是离散数学，因为计算机处理的数据还是二进制的离散量，对于连续量的处理还处在模拟的阶段。
此外，计算机科学中大量分支涉比如系统结构和计算机网络等等，都需要一定的逻辑学和图论作为其研究的支撑。作为离散数学的核心，矩阵的重要性不言而喻。众多的复杂计算机模型都可以用简单的矩阵来表示，而矩阵的运算也经常代表着重要的计算机物理含义。本文研究的搜索引擎排名评价体系就是其中之一。
1.2 矩阵乘法的理论下界
设A是一个m行n列矩阵
[singlepic=14397,,center]
B是另一个n行q列矩阵
[singlepic=14400,,center]
矩阵A和B的乘积是一个m行q列矩阵
[singlepic=14401,,center]
其中
[singlepic=14402,,center]
从定义出发计算矩阵的乘积，需要n次乘法运算和n-1次加减运算，得到的是计算矩阵乘法的计算复杂度的上界。当m、n和q被认为是同阶的数的时候，算法复杂度是O(n^3)。
两个矩阵相乘的任何可能的算法，运算次数至少不低于矩阵与向量相乘（当q=1时退化的情况）。此时，需要mn次乘法运算和m(m-1)次加减运算，当m和n同阶时，算法复杂度是O(n^2)。
由此可以得出结论，正确的矩阵相乘算法，其复杂度介于O(n^3)与O(n^2)。
1.3 几个典型的矩阵乘法算法
1.3.1 Winograd矩阵乘法算法
S. Winograd于1967年提出了一个矩阵乘法算法，其核心思想是修改向量内积计算方法，对重复计算部分进行预处理，然后将计算结果多次使用，从而达到简化计算的目的。
Winograd矩阵乘法算法实质是增加约50%的加减法代价以换取减少约50%乘法运算，但是其算法复杂度仍然是O(n^3)，并没有降低算法复杂性的阶。
1.3.2 Strassen矩阵乘法算法
Strassen算法是另外一个矩阵乘法算法，这个算法突破了O(n^3)的计算复杂度阶，由V. Strassen在1969年提出。
Strassen算法主要用于方阵的计算。Strassen观察了简单2阶方阵乘法的计算特点，使用7次乘法计算就能算出结果，而不是平常的8次，从而降低了整个算法计算复杂度阶。
Strassen算法的计算复杂度是O(n^(log2 7) )=O(n^2.31 )。
1.4 一个最优矩阵乘法算法
1989年，我的研究生导师蒋昌俊教授提出了一个新的矩阵乘法算法，称为凝聚算法。凝聚算法把矩阵相乘的计算复杂度降到了理论下界O(n^2)。
凝聚算法从非负整数矩阵出发，即当A和B的元素都是非负整数时，可以通过设置足够大的x和y，分别通过求x的m-1次多项式和y的q-1次多项式的值，把矩阵A的各列的元素和矩阵B的各行的元素凝聚在一起，分别得到n维向量[a1,a2,…,an]和[b1,b2,…,bn]，其中ak和bk分别是矩阵A的第k列元素和矩阵B的第k行元素的“凝聚”结果。通过向量的内积运算，又可以将上述两个向量的各个分量进一步凝聚成一个整数c。最后，以y为除数作q-1次整数求余运算，就把整数c散列成q个整数c1,c2,…,cq，再把ck对x作m-1次整除求余运算，又将ck散列成m个数，就得到了积矩阵C的第k列元素c1k,c2k,…,cmk。算法的关键之处在于设置x和y为足够大的整数，以便使整除求余的散列能够正确地反映前面通过多项式求值和向量内积运算的凝聚效果。
第一步：对x和y的取值是算法的关键，如果x和y的取值不合理，将得不到正确的反散列。
[singlepic=14403,,center]
第二步：对从1到n的k，用Horner方法计算：
[singlepic=14404,,center]
第三步：c=a1b1+a2b2+⋯+anbn
第四步：作除法，依次求商d1,d2,…,d(q-2)，rq和余数r1,r2,…,r(q-1)，使得：
[singlepic=14405,,center]
第五步：
对从1到q的j作除法，依次求商kj1,kj2,…,k(j(m-2))，rjm和余数rj1,rj2,…,r(j(m-1))，使得
[singlepic=14406,,center]
for i=1 to m do
for j=1 to q do
cij=r(j(m-i1+))
repeat
repeat
整个计算过程中各种操作的数量是
当m、n和q被认为同阶时，凝聚算法计算过程中有2n^2-2次比较运算，3n^2次乘法运算，n^2-1次除法运算和3n^2-n次加减运算，计算复杂度为O(n^2)。
2. 矩阵乘法最优算法在搜索引擎排名中的应用
2.1 一种互联网结构建模
万维网（World Wide Web，WWW）是指在因特网上以超文本为基础形成的信息网。万维网为用户提供了一个可以浏览的图形化界面，用户通过它可以查阅Internet上的信息资源。WWW是通过互联网获取信息的一种应用，我们所浏览的网站就是WWW的具体表现形式，但其本身并不就是互联网，万维网只是互联网的组成部分之一。互联网常用的服务包括：WWW、Email、FTP、Usenet、IM等。
在“谁发明了浏览器” 文中介绍了蒂姆-伯纳斯－李（Tim Berners-Lee）于1990年发明了首个网页浏览器－－World Wide Web。在1991年蒂姆-伯纳斯-李建立世界上第一个网站，它于1991年8月6日上网，它解释了万维网是什么，如何使用网页浏览器和如何建立一个网页服务器等等。综合各种资料，1991年8月6日被认为是是万维网诞生的日子。
WWW的基础是超文本和链接，链接也使得一个一个网站被相互链接起来，成为了全球规模的巨大网络。链接分为两种，一种称为内部链接，指从一个网站某个网页，链接到同一网站的另一个网页的链接；另一种称为外部链接，指从一个网站某个网页，链接到另一个网站的某个网页的链接。实际当中考虑的链接是外部链接，因为外部链接反映了整个互联网的拓扑关系。
搜索引擎是一种互联网应用，搜索引擎是自动从Internet搜集信息，经过一定整理以后，提供给用户进行查询的系统。英特网上的信息浩瀚万千，而且毫无秩序，所有的信息像汪洋上的一个个小岛，链接是这些小岛之间纵横交错的桥梁，而搜索引擎，则为你绘制一幅一目了然的信息地图，供你随时查阅。
对于搜索引擎来说，网站及其链接关系可以用图来描述。
[singlepic=14407,,center]
图1 八个网站相互链接的例子
通过邻接矩阵A可以描述整个网络的拓扑结构。邻接矩阵A定义为
[singlepic=14398,,center]
我们认为，一个网站本身是存在指向本身的链接的，因此aii=1。
图1中的示例的邻接矩阵为
[singlepic=14399,,center]
2.2 互联网站价值评价标准
用户通过搜索引擎找到他们所需要的网站和页面，而搜索引擎也被用户寄予厚望，希望能够在排在最前面的搜索结果中得到他们觉得最有价值的目标页面。
互联网络是一个开放的系统，如何去衡量信息的可靠性呢？当然，CNN或者人民日报谈论一个问题，和一个普通博客谈论一个问题，当然是不一样的。即，信息是有权值的。
为每一个网站人工去赋一个权值明显是不现实的。互联网站数目超过了1亿个，而且每个网站不停地在更新，一个固定的权值也是不合适的。
Google设计了PageRank算法。PageRank是一个动态的评价体系，能够动态地对网站和网页提供的信息的重要程度进行评估，并据此作为一项标准，排序用户搜索结果。
一般人们认为，可靠的信息来自于新闻网站、大公司和百科全书。这些网站被人工选出，赋予最高的PageRank权值。然后根据这些网站的外部链接，将自己的PageRank递减地传递下去，被这些网站链接的网站获得了第二级的PageRank，如此传递下去，就可以链接到每一个网站（除了那些没有意义的信息孤岛网站）。
如果我们得到了整个互联网的邻接矩阵A，那么我们可以通过计算A^k，得到经过k次链接后，哪些网站得到了传递过来的PageRank。
2.3 矩阵乘法最优算法在搜索引擎排名中的应用
互联网邻接矩阵是一个超级规模的矩阵，超过1亿维。在这里，我们探讨一下做一次相乘，凝聚算法能够带来的性能提升。
假设：互联网站数目n=1×10^8个，超级计算机（例如2008年6月9日IBM公司的“走鹃”）每秒进行运算1×10^15次。
由此可见，如果能够将凝聚算法应用在搜索引擎领域，会带来巨大的性能提升。
3. 参考资料
[1]. 矩阵乘法的一个最佳算法. 蒋昌俊, 吴哲辉, 1989, 科学通报第4期, 251-254
[2]. “矩阵乘法的一个最佳算法”一文的进一步研究. 蒋昌俊, 吴哲辉, 1994, Vol. 11, No. 2, 149-153
查看本文PDF版本：凝聚算法在搜索引擎应用设想
Google文件系统研究
同济大学 计算机软件与理论 0720080247 李征
1 简介
为了适应Google日益增长的数据处理需求，Google设计并实现了Google文件系统（Google File System, GFS）。GFS在很多方面上与之前出现过的分布式文件系统有着相似的特性，比如性能、可扩展性、可靠性和可用性。但是，它的设计更多地基于我们对于我们的应用的特性的观察和技术环境，包括现在的和将来可能出现的，因此也与之前的文件系统设计有着显著的不同。Google仔细地考察过传统的取舍，并且在设计空间中对各种不同方案做了深入的研究。
首先，组件失败比出现异常更加常见。文件系统通常包含几百甚至几千台存储节点，每个节点由经济的部件组成，访问文件系统的客户端的数目通常也在差不多的量级上。这种组件的数量和质量几乎决定了要想在任意给定时刻访问任意组件是不可能的，并且有些组件不能自行从错误中恢复。我们经历过各种错误，包括应用程序的bug、操作系统的bug、人为错误、磁盘错误、内存错误、连接头错误、网络错误和电源错误等等。因此，常规性的系统监测、错误检测、容错和自动恢复必须集成在系统中。
其次，文件常常非常大。几个GB的文件很常见。每个文件往往包含很多应用对象，例如web文档。当我们经常处理那些快速增加的数据集的时候，每个数据集都有几个TB大小，并且包含几十亿的对象，管理几十亿个KB级别的文件是很笨拙的选择，即便有时候文件系统可以支持这样做。于是，例如I/O操作和块大小这样的设计假设和参数要重新考察。
第三，绝大部分的文件更多地是被扩展新的数据，而不是改写旧的数据。随机对文件内部进行写操作，更是在应用中不会出现的情况。一旦创建，文件即变成只读的，并且经常是顺序读。很多种数据都有这样的特点。有些是数据分析软件扫描用的大型数据集合，有些是运行着的应用程序创建的流数据，有些是存档的数据，有些是一台机器产生的即时数据，即将或者立即由另一台机器进行处理。结合这样的访问模式和大文件的特点，扩展文件就变成了性能优化和原子性保证的关键，而客户端缓冲数据块则失去了初衷。
第四，对于应用程序和文件系统API的合作设计，对于增加全系统的灵活性是有益的。例如，我们在不强制对应用增加负载的情况下，将GFS的一致性模型扩展到更加简化的文件系统上。我们同时引入了一个扩展文件的原子操作，这样就可以使得多个客户端可以同时扩展同一个文件，不至于带来同步和互斥问题。这些问题将在下面的内容中做详细介绍。
很多种GFS集群已经部署，并且被用于不同的目的。最大的一个集群包含超过1000台存储节点、超过300TB磁盘空间，并且被几百台客户端服务器连续高密度地访问。
2 设计概览
2.1 假定
为了设计符合我们需求的文件系统，我们首先必须确定一些包含挑战和机会的假定。我们之前已经提到过一些关键技术，下面将详细阐述一下各项假定。
2.2 接口
GFS提供了一个熟悉的文件系统接口，虽然它并不是实现一个类似于POSIX那样的标准API接口。文件使用文件夹分层组织，并且由路径名识别。支持常见的创建、删除、打开、关闭、读取和写文件操作。
进一步地，GFS支持快照和记录扩展操作。快照操作以低代价创建一个文件或一个目录树的副本。记录扩展运行多客户端对同一个文件进行扩展写操作的同时，保证每个独立客户端的操作的原子性。这一特性对于多路合并结果和生产者消费者队列尤其有用，多个客户端可以同时操作，而不需要单独进行加锁操作。我们发现，在大型分布式应用程序中，这样的文件是无价的。
2.3 体系结构
一个GFS集群包含一个主节点和若干个子节点，能够由多个客户端所访问，如图1所示。每台机器都是典型的Linux主机，运行着用户级别的服务器进程。很容易地可以在同一台机器上同时运行子结点服务器程序和客户程序，机器资源是允许的，并且由运行脆弱的应用程序所导致的不可靠性是可以接受的。
文件被分割成固定大小的块。每个文件块由不变的且全局唯一的64位块标识唯一确定，这个标识由主节点在块被创建的时候指派。子结点把文件块作为普通Linux文件存储在本地磁盘上，并且根据块标识以及字节范围读取或写入块数据。为了可靠性，同一个块会在多台子结点上进行冗余存储，默认情况下存储三个副本，用户可以为不同的文件名字空间指定不同的冗余级别。
主节点存储关于文件系统的所有元数据。包含名字空间、访问控制信息、文件与文件块的对应信息以及文件块的位置信息。它也控制一些系统级别的活动，比如文件块租约管理、无关联文件块的垃圾收集以及子结点间的文件块合并。主节点使用心跳信息，不时地与各个子节点进行联系，发出指令并且收集这些子节点的状态信息。
连接到各个应用程序的GFS客户端代码通过文件系统API与主节点和子结点进行通讯，代替应用程序读取和写入数据。客户端从主节点进行元数据操作，读取数据块操作则直接去子结点完成。GFS并不提供POSIX式API，因此不需要引入Linux的vnode这一层概念。
客户端和子结点都不进行数据的缓存。客户端缓存数据只带来少量的好处，因为绝大部分应用程序按照流的方式读取大型文件或者所使用的工作数据集对于缓存来说过于庞大。不使用缓存机制可以简化客户端设计，并且使得整个系统消除了缓存不一致问题。（虽然如此，客户端仍然会缓存元数据）子节点不需要缓存文件数据，因为文件块是存储在本地文件系统中，Linux的缓存机制已经可以保证常用数据被缓存在内存当中了。
2.4 单主节点结构
使用单主节点设计能够大幅简化系统设计，并且使得主节点能够根据全局信息做出最优的块分配和冗余操作。但是我们必须对它的读取和写入操作进行优化，使得主节点不会成为一个瓶颈。客户端从不从主节点上读写文件数据。客户端仅仅询问主节点应该去联系哪台子结点。客户端会在一定时间内缓存这个信息，并且在随后很多操作中直接与子结点联系。
下面结合图1对简单读操作进行详细解释。首先，利用固定的块大小信息，客户端将文件名和字节偏移量翻译成文件的块索引号。然后，它将这个索引号和文件名一起发送给主节点。主节点返回相应的块标识和副本的位置信息。客户端使用文件名和索引号作为索引缓存这个信息。
客户端向某一个副本所在的服务器发送请求，大部分情况是最近的那台。请求中指定了块标识和块内字节范围。接下来的对同一个块的读取将不再进行客户端与主节点的通讯，直到缓存到期或者文件被重新打开。实际上，客户端经常在同一个请求中要求多个块，主节点也可以同时返回这些信息。这些冗余信息可能会满足未来的需求，但又不在实际中带来多余的代价。
2.5 块大小
块的大小是一个系统设计中的关键参数。GFS选择了64MB，远远超过典型的文件系统中的块大小。每个块副本都作为普通Linux文件存储在各个子结点上，并且按照需要进行扩展。磁盘空间晚分配策略避免了内部碎片带来的空间浪费，空间浪费这一点可能是如此大的块大小所带来的最大的坏处。
较大的块大小带来了几个重要的优点。首先，它能够减少客户端与主节点的通信需求，因为对同一个块的读写只需要一次通讯来得到初始化的块位置信息。对于应用来说，这个通讯量减少相当有意义，因为应用程序经常读写大型文件。甚至对于少量的随机读取，客户端也可以顺利地缓存所有数TB级别大小的文件块位置信息。其次，使用较大的块大小时，客户端更可能会对给定的一个块进行很多操作，这可以减少网络开销，因为可以在一段时间内维持一个持久化的TCP连接。第三，可以减少主节点上存储的元数据数量。这可以使得主节点将元数据保存在内存中，带来我们将在2.6.1中讨论的诸多好处。
另外，较大的块大小，即便采取晚分配策略，仍然尤其缺点。一个小文件包含较少数量的块，也许只有一个块。存储这些块的子结点可能成为热点，因为很多客户端请求同一个文件。实际中，热点问题并未成为一个主要的问题，因为应用大部分读取的都是具有多个块的文件。
但是，热点问题在GFS刚刚应用于一个批队列系统的时候出现了：一个可执行文件被作为一个块写入GFS，然后几百台机器同时执行。这几个存储这个可执行文件的子结点因为并发请求而超过负载。我们通过在存储此类可执行文件的时候选用较大的副本数目，并且通过排队错开应用程序的执行时间解决了这个问题。一个可能的长期解决方案是，允许客户端从另一个客户端获取该文件。
2.6 元数据
主节点存储了三类元数据：文件和文件块名字空间、文件和文件块的对应关系和每个文件块副本的位置信息。所有的元数据保存在主节点的内存中。前两种元数据还作为日志保存在主节点磁盘上并且在远程机器上有一个备份。使用日志可以使得我们对于主节点的升级更加方便、可靠，并且不会担心由于主节点崩溃而导致数据不一致的风险。主节点并不持久化保存文件块位置信息。取而代之的是，每当一个子结点加入集群的时候，或者主节点启动的时候，主节点去询问该子结点上有哪些文件块。
2.6.1 内存内数据结构
因为元数据都保存在内存中，主节点的操作速度会很快。此外，主节点也可以很容易而且很有效率地定期在后台进行全局信息的扫描。这种定期扫描用于块垃圾回收、失败子结点上块的恢复以及为了平衡子结点负载或磁盘使用而进行的块的合并。
这种内存存储的方法的一个潜在问题是，整个系统所能包含的块的数目由主节点内存大小所限制。实际中这并不是一个严重的问题。主节点只为每64MB文件块数据保持不到64字节的元数据。大部分文件块是满的，因为大部分文件需要很多个文件块才能存储，只有最后一个才是不满的。类似地，文件名字空间数据往往对每个文件请求不到64字节的数据，因为使用了前缀压缩。
如果将来有支持更大的文件系统的需求，相对简洁性、可靠性、性能和可扩展性而言，为主节点添加内存所带来的代价是微乎其微的。
2.6.2 块位置分配
主节点并不存储一个给定的块在那台子结点上这种持久化信息。它只是在启动的时候简单地从子结点获取数据。主节点上的信息总是最新的，因为主节点可以控制所有的块位置信息，并且通过心跳信息监视各个子节点的状态。
我们一开始曾经尝试在主节点保持持久化的块位置信息，但是我们觉得启动的时候再从子结点获取信息更加简洁。主节点与子结点同步的问题主要是，如果子结点加入或者离开集群、改名、失败、重启之类的问题。在一个包含几百台服务器的集群中，这样的事件真的是太普遍了。
另一个理解这种设计方案的方式是认识到子结点自己对自己磁盘中包含或不包含哪些文件块有最终的发言权。在主节点上试图保持这样的信息是没有意义的，因为子结点上发生的错误会导致文件块丢失（例如磁盘可能坏掉或者不再可用），或者管理员可能重命名了子结点。
2.6.3 操作日志
操作日志记录了元数据的关键性改变。这是对GFS是很关键的。不仅仅因为它是元数据的唯一持久化记录，还因为它作为唯一的逻辑时间线，定义并记录了并发操作执行的顺序。文件和文件块，还有它们的版本都是在它创建的时候就在逻辑时间上永久且唯一确定了的。既然操作日志如此重要，我们必须可靠地保存它，并且在元数据更新到持久化存储之前，它的变化对客户端是不可见的。否则，即便文件块正常存储了，我们还是会丢失整个文件系统或者最近的客户端操作。因此，我们在远程机器上保留了备份，并且只在本地和远程都刷新日志到了磁盘，才发送客户端操作成功的相应。主节点将几个日志记录打包更新，从而降低了对系统吞吐量的影响。
主节点可以通过重新执行日志操作的方式恢复文件系统的状态。为了最小化启动时间，我们必须控制日志的大小在比较小的水平上。每当日志超过一定大小的时候，主节点设置一个检查点，这样主节点恢复状态的时候，就可以只执行最后一个检查点之后的有限条日志。检查点以紧凑B树格式存储在内存中，可以在名字空间查询是不带来多余的解析代价。这个特性更进一步地加速了恢复过程并且提升了可用性。
因为检查点的建立可能需要一定的时间，因此这样建立主节点的内部状态数据结构，可以使得检查点可以在变化发生前就建立起来。主节点切换到新的日志文件上继续记录，然后使用一个单独的线程创建新的检查点。新的检查点包含了所有切换前的变化。这可能需要一分钟或者更长的时间，因为一个集群可能会有几百万文件。一旦完成，将会立即写到本地和远程磁盘中。恢复操作只需要最近完成的检查点和之后的那部分日志。旧的检查点和日志可以删除，但是我们仍然会保持一些，防止大灾难的发生。创建检查点过程中发生的错误并不会影响正确性，因为恢复代码会监测并跳过不完整的检查点。
2.7 一致性模型
GFS放宽了一致性模型以便能够良好支持我们高度分布的应用程序，但是保持简单的关系和效率，以便可以方便地实现。下面讨论GFS能够保证的特性以及这些特性对于应用程序的意义。我们将重点放在GFS如何保持这些特性，具体细节将在其他部分去讨论。
2.7.1 GFS保证的特性
文件名字空间的变化（例如文件的创建）是原子操作。这些操作由主节点排他地处理：名字空间通过加锁保证原子性和正确性；主节点的操作日志定义了一个这些操作全局化的发生顺序。
一个数据变化发生后，文件区域是否受到影响，取决于变化的类型，而无论变化成功或者失败。表1概括了这个结果。如果所有客户端看到同样的数据，则文件区域是一致的，而不论它们分别读取的是哪个备份。如果一个文件的变化是一致的，则客户端可以看到全局上发生了怎样的变化，一个区域才因此而被定义。如果一个变化没有受到并行写入的影响而成功的时候，一个受影响区域因此定义（并且是一致的）：所有的客户端将总会看到变化的情况。成功的并行变化将只是一致的，而并不定义区域：所有的客户端将看到同样的数据，但是可能反映变化的情况。典型地，多重变化会导致碎片的产生。一次失败的变化可能会导致区域的不一致（也是未定义的）：不同的客户端可能会在不同的时候看到不同的数据。下面介绍一下应用程序是如何区别定义的和未定义的区域。应用程序不必进一步区分不同的未定义区域。
数据变化可能是以写入或者记录扩展的方式发生。一次写操作将使得数据在应用程序指定的文件偏移位置写入。一次记录扩展操作使得数据（即记录）自动被扩展至少一次，即便是在并行变化发生的过程中，但是发生在GFS指定的偏移位置上。（相比而言，正常的扩展操作是发生在客户端认为的文件结尾处）偏移将返回给客户端并且在包含这条记录的定义区域的开始做标记。更进一步地，GFS可能会在其中插入填充数据或者记录备份。它们占用了被认为是不一致的区域。在一系列变化成功完成之后，变化的文件区域被保证是已经定义的，并且包含了最后一次变化中写入的数据。GFS将记录这一变化，首先，在所有的文件块副本上应用这一变化，其次，使用文件块版本号确定某一个副本是陈旧的，可能由于子服务器down机而缺失了某次变化而导致。陈旧的副本不能参与任何新的变化，也不能在客户端请求块位置的时候作为结果返回给客户端。它们将会尽早地被作为垃圾清理掉。
因为客户端会缓存块位置信息，它们可能会在信息更新之前去读到一个陈旧的副本。这个窗口由缓存的生存期和下一次打开该文件的时间而决定，重新打开该文件会导致缓存全部更新。更进一步地，既然大部分的文件是只用来扩展的，陈旧的副本只会返回一个错误的文件尾位置，而不是过期的数据。当一个读文件的客户端重试的时候会联系主节点，然后会立即得到新的文件块位置。
一次变化成功很长时间之后，组件的故障依然会导致数据的破坏。GFS通过常规性的主节点与子结点之间握手以及检查校验和的方式识别故障的子结点。一旦发现一个问题，数据将尽快通过正确的副本恢复回来。一个文件块丢失的情况只会发生在当所有的文件块副本在GFS做出操作之前都丢失的情况，典型地是在几分钟之内。即便是这种情况，文件块只是不可用，而不是被毁坏：客户端将收到错误，而不是毁坏的数据。
2.7.2 对于应用程序的意义
GFS客户端可以适应这种宽松的一致性模型，这几种简单的技术已经用于其他的目的：依赖于扩展而不是复写、检查点、写自检、可自我检查的记录。实际中所有的应用程序修改文件的方式都是扩展而不是复写。在一种典型的应用中，一个写文件器从开始到结束完整地生成一个文件。在所有数据写完后，它会自动地重命名这个文件，或者周期性地生成检查点，控制多少数据已经成功地写入。检查点还可能会包含应用程序自己的校验和。写入器只处理和校验上次成功的检查点建立以来的文件区域，也即处于定义状态的部分。不考虑一致性和并发性的情况下，这种应用很好地处理了我们的需求。扩展写比起随机写更具效率和弹性。检查点可以使得写入器能够阶段性地重启下一操作，而不用再去处理已经成功写入的部分。
在另一种典型应用中，很多个写入器并发地扩展一个文件，合并结果或者排在生产者消费者队列中。记录被扩展的位置是语义学上最后一次写入的位置。读取器处理偶然的填充数据和冗余数据。每条记录都含有写入器生成的类似校验和的冗余数据，这样使得数据可以被校验。读取器可以根据校验和识别多余的填充和记录碎片。
3 参考资料
[1]. The Google File System, Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, Google.
从来没见过这样的agent。来自Google实验室？
2008-05-30 20:07:46 Google Labs Python-urllib/1.17
今天上Google Reader的时候发现Google的favicon变掉了。
[singlepic=13944]