« 人民币升值? | 返回首页 | 欧拉数 e »

读了 google 的几篇论文

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

Comments

一如既往的支撑。

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

突然发现一处有意思的地方。

“大约花了好几天的时间讲解代码和设计,也算新同事天资聪慧,硬是把我近千行毫无注释的代码给理解了一遍。”

纵使你能1年写10万行代码,讲解1000行代码也需要花好几天啊,挖哈哈哈。

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

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

就我现在而言,我比较赞同用二进制协议,甚至是RPC来做通讯。

但若用RPC必须是非常简单的,大多数情况下应该是立即返回的单向消息。

用二进制或者RPC的原因在于,
把二进制信息要格式化成文本,以及把文本解析成二进制这两件事情相比,前者更容易。所以,使用二进制的协议,并输出足量的日志,要比收发两端都进行文本的解析/序列化来得容易,而且并未增加调试难度。

TAOUP 中提到文本更安全,不容易产生漏洞,我觉得是错的,许多使用文本协议或者文本配置文件的程序,解析器都远不够严谨,很容易崩在特殊字符上。

在一些情况下,文本协议也并不具有更好的移植性。比如文件路径中的特殊字符,cygwin 的大量不兼容问题都出在这上面。很多 GNU 程序根本就没有考虑过文件名中的空格、中文之类的东西。而最广泛的有问题的字符,就是 '\0' ,我估计在文本里面加个 '\0' ,一半以上的用 C 写的程序都会出问题。

实现一个文本协议很容易,但是想要做到真正可靠就会使复杂度急剧升高。

HTTP 协议就是这样一个例子,HTTP 1.1 的 RFC 文档有 176 页,虽然大部分规范都能用 BNF 来描述,但是 BNF 里面仍然夹杂着许多放到尖括号里面用人类语言来描述的其他限制。

如果 HTTP 协议用的是二进制协议,可以极大的减少实现一个 HTTP 1.1 客户端的代码量。当然,对应的 RFC 文档的页数也会少得多。

人类可读字符串来表示数据,即使在在"步骤多,数据表示复杂"的情况下还不至于导致过大的效率损失。IMHO

因为数据转换成机器理解的格式,算法时间复杂度应该是线性的,空间复杂度是相当的,其引起的效率损失可以通过线性的增加机器来解决。但是带来的好处却很大。

另外,按 google 论文的说法,数据格式是允许被改变的,但一般人不会选择这么做。

ps. 我们的项目开发历程里,经历了二进制数据格式到文本数据格式的转化。最终发现,还是文本的好啊 :D

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

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

有没有考虑过Erlang?

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

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

那些方面比opera不专业呢?

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

还不如用UCWEB来上网,偶就用

treo 上访问google reader? 用的什么么浏览器? 不会是blazer吧?每次后退都会重新载入页面,慢死了。
我在用opera mini留言哦。
另外reader手机版还是太差了,尤其是mark page as read

Post a comment

非这个主题相关的留言请到:留言本