云风的 BLOG: 读了 google 的几篇论文

周末在家赖床，把玩我的 treo 手机，从 google reader 上看到 myan 大大新近介绍 google 的三篇论文的中译版。

（插一句，google reader 的手机版做的相当不错，很烂的手机都可以方便的使用，界面简洁，节省 GPRS 流量，强烈推荐）

这三篇论文我都有所耳闻，GFS 的论文应该出来最早，前几年就有同事发过英文版的给我看过。MapReduce 耳边经常有人跟我提起。BigTable 听的比较少一点，但也知道大概是咋回事。

三篇论文中译本都没读过（更别说英文版我会仔细学习了）。我便躺在床上，捧着手机，细细品读。

这三篇其实都是解决大数据量，分布式处理的问题。说穿了，都没什么技术难点，也无啥革命性的技术创新，但系统实现起来绝对不简单。这个难度，体现在工程实现上的困难。

健壮的系统总是结构简单规则简单的，用冗余的数据提高效率，增加健壮度。

GFS 是另两个系统的基础，它最底层利用本地文件系统提供原子操作，而不是自己解决。这可以简化系统复杂度，我们在设计系统时就应该尽量简化每个层次上代码完成的工作。与之类似的，我在设计我们的游戏服务器架构的时候，数据储存一块没有使用标准数据库，而是依赖于内存与本地文件系统，也是基于这种考虑。

GFS 采用了单点的 master 调控全局，这样可以做出非常简单的设计。但是需要极度减轻加在其上的工作，最终让 client 在真正获取数据的时候不必直接和它通讯。我非常认同这一点，有时候设计一个单点总控的单元并非不合理。我们已经实现的登陆服务器就是这样的，用户只有一个登陆认证点，但认证完毕后不再需要保持连接。

整个系统中，其实可以有许多单元是单点的。只需要减轻其上任务的复杂度，往往都是可堪负荷的。至于单点故障的问题，在底层设计上可以允许发生错误并重试，而系统能够快速重启就够了。当然，并非系统所有的部分都适用，有些地方，相互备份的模块是必须的。

BigTable 满有意思的。我认为当初做出设计的最难点是合理的提出需求，把需求简化到最小的单位，然后就最基本的需求来实现和优化，得到一个高性能的分布式结构化数据存储方案。

比如完全的关系数据模型就是不必要的，但是版本控制就有必要。复杂的数据类型是没有必要的，只需要储存字符串就够了。合理的需求自然需要大量的实践经验来总结，而需求的合理则可以做出极大的性能优化。实现者最清楚怎样的需求能最大限度的优化；实践者最清楚哪些需求是合理的，必须的，哪些则是不重要的，可放弃的。我们对系统设计者的要求就是即有丰富的实践经验，又有足够的能力自己做实现。这样才能做出优秀的系统来。

最后说说 MapReduce ，原理不复杂。就是把大部分可分布式任务完成的要点提取出来：即数据分割、分布式叠代处理、去掉冗余的计算结果、结果合并。效率的提高在于冗余处理，用廉价的机器计算能力来减轻系统设计的复杂度。系统则专注于解决数据传输、分割、合并这些简单逻辑的高效实现上。并实现数据定位和数据运算的正交化。

以上我也就是简单评论几句，行家不必较真。目前我的工作范围内尚没有需求去设计实现类似的系统，所以暂时也没太多精力研究细节。我相信若真的做起实现来，困难会很多，工作量会很大，会碰到相当多初期没想到的难题。

随便再写几句最近的一些工作。

新同事报道，安排的工作是完成我前段做了一半的资源管理模块。几个月前，我那段代码几经修改后算是收工了，提交代码仓库后就没有修改过。但是我只完成了从本地文件系统中加载资源，这次打算把数据打包以及数据包读写的加上。

大约花了好几天的时间讲解代码和设计，也算新同事天资聪慧，硬是把我近千行毫无注释的代码给理解了一遍。想起有些地方很不规则的内部函数命名，以及偶尔几行自己都差点想不起的原始设计用意，真是汗颜。

最后，总算让人弄懂了，自己也输理了一遍当初的思路。值得庆幸的是，设计大体还算合理，这次新添加东西没有动任何老的接口，也没有新增加接口。该隐藏的信息都隐藏好了，该暴露的东西都用上了。新添加的代码跟老代码的正交性也还好，不大需要重复做一些工作。

表面上看起来应该很简单的东西，实际做出来还是满复杂的，我想这就是工程实现的难度吧。

Comments

一如既往的支撑。

Posted by: 福利工口姬 | (16) April 16, 2014 04:33 PM

那近千行代码讲了几天，是因为当初写就写了好几天。中间为了整理思路，还写了篇 blog 。

Posted by: Cloud | (15) August 31, 2007 12:00 AM

突然发现一处有意思的地方。 “大约花了好几天的时间讲解代码和设计，也算新同事天资聪慧，硬是把我近千行毫无注释的代码给理解了一遍。” 纵使你能1年写10万行代码，讲解1000行代码也需要花好几天啊，挖哈哈哈。

Posted by: Atry | (14) August 30, 2007 11:22 PM

不过，为什么要把它搞得很复杂呢？虽然我觉得复杂的二进制协议要比复杂的文本协议好一点。不过，复杂的二进制协议和复杂的文本协议都不是好东西。

Posted by: Atry | (13) August 30, 2007 11:19 PM

的确。国内常见现象，如同能盖2层小楼的人觉得盖金茂也很简单只要往上堆就行了。却不知量变引起质变，当规模达到一定程度再简单的事情都会变得很复杂，如同小地摊之于连锁卖场，打群架之于大规模战争，独轮车之于F-22。每当规模上一个台阶，所需要的技术就要超出原有的范畴。

Posted by: d | (12) August 25, 2007 04:36 PM

就我现在而言，我比较赞同用二进制协议，甚至是RPC来做通讯。但若用RPC必须是非常简单的，大多数情况下应该是立即返回的单向消息。用二进制或者RPC的原因在于，把二进制信息要格式化成文本，以及把文本解析成二进制这两件事情相比，前者更容易。所以，使用二进制的协议，并输出足量的日志，要比收发两端都进行文本的解析/序列化来得容易，而且并未增加调试难度。 TAOUP 中提到文本更安全，不容易产生漏洞，我觉得是错的，许多使用文本协议或者文本配置文件的程序，解析器都远不够严谨，很容易崩在特殊字符上。在一些情况下，文本协议也并不具有更好的移植性。比如文件路径中的特殊字符，cygwin 的大量不兼容问题都出在这上面。很多 GNU 程序根本就没有考虑过文件名中的空格、中文之类的东西。而最广泛的有问题的字符，就是 '\0' ，我估计在文本里面加个 '\0' ，一半以上的用 C 写的程序都会出问题。实现一个文本协议很容易，但是想要做到真正可靠就会使复杂度急剧升高。 HTTP 协议就是这样一个例子，HTTP 1.1 的 RFC 文档有 176 页，虽然大部分规范都能用 BNF 来描述，但是 BNF 里面仍然夹杂着许多放到尖括号里面用人类语言来描述的其他限制。如果 HTTP 协议用的是二进制协议，可以极大的减少实现一个 HTTP 1.1 客户端的代码量。当然，对应的 RFC 文档的页数也会少得多。

Posted by: Atry | (11) August 22, 2007 01:28 AM

人类可读字符串来表示数据，即使在在"步骤多，数据表示复杂"的情况下还不至于导致过大的效率损失。IMHO 因为数据转换成机器理解的格式，算法时间复杂度应该是线性的，空间复杂度是相当的，其引起的效率损失可以通过线性的增加机器来解决。但是带来的好处却很大。另外，按 google 论文的说法，数据格式是允许被改变的，但一般人不会选择这么做。 ps. 我们的项目开发历程里，经历了二进制数据格式到文本数据格式的转化。最终发现，还是文本的好啊 :D

Posted by: Cloud | (10) August 14, 2007 01:19 PM

我比较关注MapReduce技术。一直十分疑惑，MapReduce明明就是网格技术的一个实现，为什么其论文里决口不提网格？是不是觉得传统网格技术比如globus计算效率太低？并行计算的一个主要困难是数据相关性，决大多数问题都表现为局部数据相关性。我很赞赏MapReduce能抽象出这么简单的模型，轻易了解决局部相关性。但一些问题中存在全局数据相关性或随机相关性，我担心MapReduce解决这些问题时有不小的困难。相比于传统网格技术的低效，我猜测MapReduce应该很不错。不过示例中输入/输出，中间步骤都用字符串表示数据，倒是足够KISS，但在步骤多，数据表示复杂的情况下，效率恐怕有不小的损失。

Posted by: dayn9 | (9) August 14, 2007 09:23 AM

云风今天翻看你以前写的文章时，发现在Archives里按每月浏览页面，页面头部多了" /> ”. :p

Posted by: Cofyc | (8) August 10, 2007 08:23 PM

有没有考虑过Erlang?

Posted by: Linker M Lin | (7) August 10, 2007 09:10 AM

回答我的看法：还不是很熟悉时，大概思路想好后就可以开始编程，边编程边完善并修改设计；已经可以完全把握时，可以完全全设计好了再编程。

Posted by: alioxp | (6) August 10, 2007 09:04 AM

在项目里是完完全全设计好了再编程，还是大概思路想好后就可以开始编程，边编程边完善并修改设计呢？上千行的代码在几天时间内理解还是没问题的，但自己设计就有点困难。

Posted by: longtrue | (5) August 7, 2007 07:56 PM

那些方面比opera不专业呢？

Posted by: ywchen2000 | (4) August 7, 2007 12:00 PM

基本上，ucfly是没有opera专业的，当然，ucfly专门针对国内的网站论坛优化，是他的优势