五千年(敝帚自珍)

主题:【原创】闲话Google集群 [6] 同步的苦恼 -- 邓侃

共:💬33 🌺52
全看树展主题 · 分页首页 上页
/ 3
下页 末页
家园 【原创】闲话Google集群 [6] 同步的苦恼

[1] 引子

[2] 存在的理由

[3] 布局

[4] 数据流和控制流的分离

[5] 同步的诀窍

[6] 同步的苦恼

前些时间,有人拿了本国内被禁的“晚年周恩来”,问我要不要读,我回绝了。周公的传记我通常不读,原因是周公太完美了,他是神。神可以被崇拜,但是不可以用来怡情。关于小林元帅的文章,我几乎从不放过,即便在很忙的时候,熬夜也读。小林从大雄走向大奸,不仅褒贬参半,而且争论颇热闹。

做学问也类似。教科书适合催眠,只有俯首帖耳消化吸收的被动,没有激扬文字指点江山的豪情,不打瞌睡不符合人性。读论文有趣得多,趣味在于多数论文只是一家之言。他可以宣扬他的观点,你可以指指点点评头论足,甚至可以另立山头同台打擂。

有关Google集群的论文比较有趣,原因有三,1. Google集群是当今世界规模最大,实际运行效果最好的集群;2. Google的同志们年轻朴实,行文朴实,有啥说啥,不拿一大堆数学公式或者半文不古的术语来忽悠人;3. Google集群并不十全十美,我们大快朵颐消化吸收的时候,不必俯首帖耳,吃饱喝足了,抹抹嘴,说,姜还可以多放些,葱最好打结,这样汤的味道会更厚实。

前一节讲到,当client向某个Chunk-server备份小组存放文件时,GFS规定的工序分7步。看似复杂,其实可以概括为三件事,1. Client向Master打听chunk-server小组中每个机器的地址,以及谁是小组长,2. Client把数据推送给地理距离最近的机器,然后逐步线性扩散到小组中所有机器,3. 小组长决定写入硬盘的顺序后,依次把内存中的数据写入硬盘。

这个工序好不好?好!但是我们今天偏来抬抬杠。抬杠这个词听起来有点情绪化,更贴切的说法是质疑,目的是探究有没有可能进一步改善同步的工序。

1. Client的权力是否过大?

a. Client(如Crawler)知道chunk-server中所有机器的地址,以及当前小组长是谁。这样chunk-server小组的隐私就暴露在client面前。

有人或许会说,反正client是集群内部自己人,不会有恶意攻击的情况发生,所以隐私暴露就暴露吧。这个想法过于乐观了,Google的集群有多达上百万台机器,林子大了什么鸟都有。万一某一台机器被恶意挟持了,或者万一有某个应用程序出了bug,无防范的众多chunk-server就倒霉了。

譬如client方面一个循环语句的中止条件写错,导致client不停地给chunk-server重复地发送相同数据,就像BBS里无聊的人刷屏一样,很快chunk-server的内存将会被灌满。这个时候chunk-server能做什么?要么内存被灌满以后,拒绝随后到达的新数据。如果这样,其它无辜正直的clients就不能顺利地向chunk-server传送数据了。要么,另外一种可能是,chunk-server循环使用内存,新来的数据将覆盖以往的数据。如果发飙的client传送数据的速度很快,那么可能的后果是chunk-server的大部分内存空间,被来自发飙client 的垃圾数据充斥。两种后果都很糟糕。

b. 在关键的第三步,client自主决定先给小组中那一台机器传送数据。Client想什么时候传送数据,就什么时候传送,它不考虑chunk-server的内存是否即将被占满,它也不考虑chunk-server网络带宽是否已经严重堵塞。

在第四步,又是client给小组长下令,把内存里的数据写入硬盘。当小组中各个chunk-server都已经接受到了数据,存放在内存中以后,理应尽快写入硬盘。但是什么时候开始写,决定权又是在这个我行我素的client手中。如果client正在忙着处理其它事情,它就顾不得下令写入硬盘,尽管下这个指令不费吹灰之力。造成的后果是,chunk-server内存中的数据不能及时写入硬盘。内存一旦被占满,后续的数据就不能被顺利发送到 chunk-server,或者先前到达的数据被覆盖。

所以,client掌握了太多的主动权,隐患很多。

c. Client缓存chunk-server中所有机器的地址,以及当前小组长是谁。万一这些信息发生改变,而client没有及时更新,会造成什么后果?

它自说自话地把数据发送给最邻近的chunk-server,进而扩散到小组中其它chunk-servers。然后和自己心目中的小组长联系,说,“所有数据都到位了,您老可以下令让各个chunk-server写进硬盘了”。没想到,小组长回信说,“俺已经卸任了”。得,client只好再找 master,问,“新任小组长是谁啊?”,等等。

如果只是换了一任小组长,那么后果还不算太严重,浪费一点时间而已。如果小组成员中,更换了机器。问题就大了。譬如,client的缓存里说,这个小组有 S1,S2和S3三台chunk-servers,S1和S2都已经回信说传送的数据已经存放在各自的内存中了,可是S3一直没有回音。Client就 re-try,一遍又一遍,无异于灌水。

关于Client缓存过期信息,GFS论文里很坦诚地承认了,这种可能性的确存在,参见第2.7.1节倒数第二段。但是论文辩解说,缓存的时间是有限的,所以这个可能性虽然存在,但是频率不会很高。如果真得束手无策,只能祈求错误出现的频率不高,但是有没有彻底杜绝错误的办法呢?

2. 小组长的权力是否过小?

干部的任命从来就不是一件小事,委任chunk-server小组长也同理。Master在决定谁最适合被任命为小组长时,需要考察小组中所有成员的工作负荷,健康情况等等。虽说这个工作的成本不大,但毕竟是有成本的。更麻烦的在于,委任状是有有效期的,有效期一过,需要注销,或者续约。

审查通过,又续了约,总算稳住了名号,圈里圈外总算有了点人望,却发现却是一个闲职。好生无趣。小组长的职责是什么?无非是第四步时,client递过来个条子,说,“时候差不多了,该把内存里的数据写进硬盘里去了”。小组长便列了个先后次序的单子,让各个chunk-server分头去写。说来说去,稍微有点技术含量的活儿,无非是决定优先顺序。其实也没什么技术含量,多半是重复先来先服务的老把戏。

前面说了,client的权力太大,能不能让闲置的小组长分点权力?皇帝要稳固皇位,无非是在外臣和内戚之间搞平衡。太祖为什么要启用江青和毛远新?无非是外臣势力过大,需要启用内戚来制约而已。

小组长可以做哪些事情?如果GFS让我出主意,我可能会这么建议,

1. 小组长决定哪一个chunk-server去client那里取数据,什么时候去取,而不是由client来决定。

Client没必要,也不应该知道小组中所有chunk-server的地址。由chunk-server主动向client索取要存放的数据,而不允许client随意灌水。

2. 小组长决定chunk-server们什么时候把内存里的数据写进硬盘,而不由clent来决定。

自家内部的事情,岂容外人干涉。

明摆着是夺权。

Client接触的应当是Master和小组长。就像是顾客来到银行,接待他的是大堂经理。顾客对大堂经理说,“我这里有一笔钱想存入贵行”。经理把顾客引到某个柜台,说,“这位服务生负责接待您”。顾客把钱交给服务生,服务生完成所有的储蓄手续。

如果大堂经理递给顾客一张名单,说,“你看,这是我行所有与储蓄业务有关的部门和工作人员,您自主决定怎么存”。估计大多数顾客脸色不会好看。如果某位顾客开怀地笑了,保不定银行将来会失窃。

夺权有理,这个理,并不在于容不下小组长游手好闲,而是在于强调内外有别。

待续

关键词(Tags): #Google#cluster#集群
家园 反对小组长干涉

这里,小组长是单机无备份,随时会死掉。

小组长权限绝对不能大,数据写入时机和顺序还是又client完成比较安全~~~

这里千万别把小组长想象成领导,它其实就是一个伙计,死不死的无所谓~~~

家园 一看标题可乐了

平时都跟着几位写家在英雄那边潜水

今天一看邓兄这个标题就笑了

GFS的东西之前确有接触 为什么捏 因为几年前遇见个比它更BT的案

一个横跨亚欧大陆(从东边的日本一直到西边的意大利)四个国家N个点的数据同步问题

抑郁的问题是涉及到协同工作,即这N个点里可能都在做同样的案子,一个地方更改了同时要反馈到其他的点去.按说如果有一个协同平台的应用级系统可以解决这个问题吧,可惜总的数据量都是TB级别.应用层面来解决的难度不是一般的大.从硬件层面来看(服务器和存储)而各个点之间的设备异构太大,厂商大谔们没一个敢接招的.

更为关键的是预算又敏感,推倒原有架构重起炉灶的事情BOSS不批,且各点之间的专线带宽因为涉及到多个国家提升也确实存在问题.

最后的解决方法非常好玩 不是现在热吵的什么硬件级别的灾备分中心拉 什么软件级别的重复数据删除拉 什么系统级的协同平台拉 或者拉一根可以3秒下一部DVD影片的专线拉(当然最终的解决方法肯定会是从技术层面彻底、根本地解决问题,不过那已经不干偶地事情拉)

靠的是传统间谍最原始也最安全的办法--信使.

别说后来一实验,效果还不错.因为这个庞大的实体当空中飞人的还真多,而飞之前都要报HR备案(各个国家的补贴、汇率计算方法估计不会比那个铱星"A国人通过B国的卫星在C国给正在D国HIGH的购买电话于E国的居住地在F国的G国人"打过一个电话的费用计算简单)于是一个小小的程序就解决了问题,飞人们带着个SATA硬盘飞来飞去,意想着有多少个TB的数据翱翔在亚欧大陆的3万英尺之上呵,多么地行为艺术——那可是阳春白雪和下里巴人的最最完美结合呢!

家园 SneakerNet

你别说,大教授从来不反对行为艺术。

记得是Tanenbaum那本Commputer Network经典,或者是其它那本书里,就正儿八经地提过sneakernet的说法。意思是在某些环境下,不必过份迷信技术手段。

家园 挑起群众斗群众

与天斗其乐无穷,与地斗其乐无穷,与人斗其乐无穷。

这个“斗”,不是意气之争,不同意见的争论也是斗的一种。

共和党人肉猫反对小组长干涉,有哪位民主党人支持小组长?

家园 SNEAKERNET是最为彪悍的存在

也就是最早的网络。。

传说中人们要共享文件就把文件考在软盘上。

然后再把软盘送到需要的人的手里。

完成这次共享 由于是走着过去的 所以就叫所以SNEAKERNET叫鞋子网也就是人工网络 ...

家园 通俗易懂阿,呵呵,上花。
家园 KISS 原则也是一个很重要的原因

小组长作的傻,对于GFS来说绝对是follow KISS原则的典型例子!

越简单的,出错的概率越低~~~

家园 花一下,我以前孤陋寡闻的以为

只有俄们中国人才能想出这种招。,

家园 借问老兄一个问题:

Gmail的邮件标签在存储和检索上是怎么实现的?老兄可有研究?

家园 Gmail的邮件标签

不是非常明白老兄你的问题。Gmail的邮件标签,你是指什么?

家园 Gmail中的每个邮件都可以由用户分配任意多个标签

这些标签是用户自定义的。比如说,假如我有一个IBM开发者网络的帐号邮件,我可以给它两个标签,一个名为“IBM”,一个名为“帐号”,这样,我不论根据哪一个都可以很轻松地找到这封邮件。

这是基于属性的数据检索,这些标签其实对应了邮件的不同属性。不过,基于属性的数据检索的实例很少见,GMAIL的这个大概是最著名的一个。我很想了解一下google是怎样实现邮件标签这种属性的存储的,以及如何根据这些属性进行检索。老兄当有以教我,先行谢过。

家园 邮件标签

汗,要不是你说,我还没有注意到Gmail这个功能呢。

我先试试gmail的这个功能,否则胡言乱语,不负责任。

家园 倒排索引和动态索引

Gmail标签的实现,说难也不难,说容易也不容易。

Gmail邮件的检索,是依靠inverted index来实现的。不妨用Lucene来体验一下inverted index(倒排索引)的功能。

在Lucene里面,每个document,被分为很多fields。譬如email的To,Cc,Bcc,Topic,Body等等,都是fields。把每个document拆分为多个fields,然后把每个fields里的string取出,按terms建立inverted index。

如果增加一个field,“label”,那么建立inverted index的时候,也相应增加相关索引。

如果有些email没有label怎么办?如果没有label,那么按照label来检索就找不到。找不到不是坏事,就像有些email没有Cc一样。

听起来很容易,当然前提是对搜索引擎技术需要比较了解。如果我前面的文字读起来费解,不妨先玩玩Lucene。花一个下午熟悉一下Lucene,再回头看我写的东东,或许就明白了。

为什么说难?主要是动态建索引的问题。

建inverted index不是一件轻松的活儿,通常每天只更新一次。但是注意到使用gmail时,你刚刚收到的email,就能被查到,而不是明天才能被查到,这是为什么?这是因为gmail里面有动态索引的技术。

动态索引如何实现,说起来比较费事。以后再聊。

家园 花!期待“动态索引的实现”

真能吊胃口啊

全看树展主题 · 分页首页 上页
/ 3
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河