Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948
May 18, 2012

昨天在微博上面看到吵A8和A9性能比较,架构中年宅心中又燃起了激情,这里稍微比较一下,数据都是来自ARM官网,在下凭着多年的知识稍微吐槽一二。

官网数据链接:

http://www.arm.com/products/processors/cortex-a/cortex-a8.php

http://www.arm.com/products/processors/cortex-a/cortex-a9.php

比性能,基本上就是比处理速度和能耗。如果把CPU比作麦当劳,里面有几万民工翻汉堡,那么谁翻的快,翻的省电,谁就赢了。当然这里有个架构问题,如果把麦当劳跟牛肉面比,麦当劳肯定完败。好在A8和A9的架构没有显著差别,都是v-7 A,还是麦当劳比麦当劳。

主频:A8 600M到1G,A9 800M到2G 主频高性能一般高,但是能耗也上去了。能耗函数的电容模型是W=fV^2C,和主频成正比。

电压和能耗,两个页面给出的标准不同,A8是0.9V到1.08V,A9给出的是能耗。能耗公式里面的那个C是跟芯片工艺有关的芯片电容常数,不知道台积电的参数,不好说。

工艺:A8没有给出工艺,估计是代工工厂比较多。A9页面显示是台积电代工,65纳米和40纳米两种工艺。

性能测试参数:A8单核开满1G推算值是两千DMIPS,A9单核1G推算是两千五百DMIPS,25%左右的性能提升,A9完胜。

那么为神马A9这么快?因为A9开了俩外挂:多核,乱序执行。A9可以有单核或者4核心,另外首次引入了乱序执行。当然开外挂是要付出代价的,A9的4核心能耗就比单核高很多,虽然没有高到4倍,这个跟多核之间的片内连接省电有关。

乱序执行也是一个大家伙,ARM架构以前一直不用乱序,因为乱序耗电,对性能提升有限。我以前读书时候做的研究表明,不用乱序,10%的性能损失可以换取30%的能耗节约,后来intel的ATOM架构用了类似的思想来省电。这次A9引入乱序,居然还能这么省电,台积电的工艺的确不错。

基本上就是这些了,新一代的CPU比前一代好是正常的,A9的性能提升,主要是多核+乱序,然后新工艺来保证能耗下降。

March 13, 2011

http://www.cas.ac.cn/ky/kyjz/201103/t20110307_3079982.shtml

软硬件协同的X86二进制翻译

December 31, 2010

嗯,马上要新年了,顺着解剖 Facebook 【6】云计算云存储的那些事儿 写点关于amazon dynamo的段子。

《最近比較煩》是周華健、品冠、李宗盛这三个在人生不同阶段的男人对男人辛苦的调侃,那么如果映射到云存储提供公司里面的不同职位的人,是否对云存储也有不同的感触呢?

硬件工程师:最近比较烦比较烦比较烦,amazon的机器已经有几十万,平时沉稳淡定的硬盘,每天趴窝也成了家常便饭。

软件架构师:最近比较烦比较烦比较烦,他们硬件麻烦要我们软件来管,机器趴窝还不算完,一个破路由器把网络分两半。

CTO:我比你烦也比你烦也比你烦,贝索斯说了技术细节他不管,用户选了东西你就给我存好,将来读不出来小心你的饭碗!

合唱:每天总有远的近的麻烦,现成的软件都有点脚软。文件系统搞得东西太乱,数据库总是弄得太慢。干脆,咱们卷起袖子自己干!

硬件工程师:机器趴窝不是那么普遍,每天也就几十个节点

软件架构师:数据丢了可是不能算完,我写它一万遍啊一万遍

硬件工程师:路由器的事情老板不肯出钱,买的都是自家网站卖的低端

软件架构师:低端的路由,把网断开,把数据版本分两段…

硬件工程师:你跑调了,那个是《城里的月光》

软件架构师和硬件工程师望着CTO:老板,怎么办?

嗯,歌唱好了,说说唱的都是是啥吧。其实都是云存储里面的常见问题。首先是硬件稳定性,因为云的计算和存储都是海量的PC机完成的,如果一台机器每天可能失效的几率是万分之一,那么基本上每天都有机器失效,特别是数据中心这种地方,一不小心就过热。对付硬件失效的方法就是复制数据和计算,带来的副作用就是有多个copy需要更新。

其次是网络稳定性,这个和硬件稳定性是相关的,通常是因为路由器的关系,让网络分割(partition)为不连通的两个或者多个部分,导致数据不能流通。网络一旦分割,更新copy的事情就会出问题,在一个网络分割的copy被更新了,另外一些在其他网络分割的就不能被更新。将来网络恢复了,就会发现有多个版本。

如何解决这些问题呢?不同的应用有不同的要求。在amazon的这个应用里面,CEO有两个需求:

  1. 用户存的东西(主要是购物车的内容)要立刻能存,不能丢
  2. 用户取数据的时候要给一个完整的购物车

另外,amazon需要的不是普通的文件系统,也不是关系型数据库,他们需要的是一个能快速存取的key / value store,就是用一个key能够快速的取得相应的数据对象,这决定了他们:

  1. 不需要多层的文件系统,因为这个是给程序用的
  2. 不需要关系型数据库,他们主要是拿了key就能立刻取得value,关系型数据库带来很多冗余和不必要的限制
  3. 需要在各种困难情况下迅速的取得数据

具体的实现细节,在这里:

http://s3.amazonaws.com/AllThingsDistributed/sosp/amazon-dynamo-sosp2007.pdf

更多的段子,请关注ifanr的sunny_kan

December 17, 2010

最近有机会看了google bigquery的演示,在Tera byte级别的数据上面进行实时的查询,还是很厉害的。研究了一下,发现后面的软件项目是Dremel,这里是文章:

http://sergey.melnix.com/pub/melnik_VLDB10.pdf

我这次就不翻译了,因为科技论文最重要的是里面的概念和实施细节,语法和用词这些翻译上面很花时间的东西,在科技论文里面其实是次要的,我花了时间大家又不看,这种赔本买卖上次翻译bigtable一次就够了,这次不干了,这次只说说读论文的一些收获,希望能帮助大家读那篇原文。

Dremel的基本概念是按列来分割数据,能把树形结构的数据按列分割,而不是只能处理简单的二维表。文章里面用了不少篇幅来描述他们怎么把树形结构的数据变成数据列。这个按列处理数据是他们性能提高的关键。对比bigtable,都是分而治之的方式,把一台机器存不下的表分割为子表,不过bigtable是按行分,Dremel是按列分。

按列分割数据以后,做查询就方便很多,因为查询表达式基本上是对列里面数据的计算,把数据列分别存储,就实现了数据和计算在计算节点级别的局部性 - 就是说单个节点上面CPU和数据离的近了,计算起来快;整体来说可以把计算并行的分布到多个节点去,他们提到用了4000个节点并行计算。当然把数据分割也是有代价的,因为最后经常要把这些列再组合成记录。他们也承认,组合数据比较耗时。我当时看演示的时候,也发现如果最后的查询结果是scalar数据,比如count(*)这种,就飞快;如果是返回某些记录,就比较慢。

按列存储还有一个好处就是对稀疏矩阵的压缩,压缩的好处是把龟速的读盘,变成了飞速的计算。

文章里面也提到了,少数子表处理时间会很长,如果用户不在意非常精确的数据(比如,比尔盖茨和苹果教主这种超级富翁不必知道硬币是什么),那么处理速度会更高。

另外一些对海量数据的处理,比如备份,冗余等等,都是套路了,相信系统里面也有针对读硬盘的优化,比如按道来存储数据,减少磁头的寻道次数等等。

Google的人也说了,这个东西查只读数据很快,往里面写就比较慢了。我相信他们对数据肯定做了很多索引,但是文章里面没说,演示的人也不说。这么重要的查询优化居然不说,可疑啊可疑。

就说这么多,细节还是要看原文。

December 9, 2010

//更新:彼岸翻译了第5章的后面部分

6.优化
前面一章描述了BT的实现,我们还需要很多优化工作来获得用户需要的高性能,高可用性和高可靠性.本章描述实现的一些部分,以强调这些优化.

局部性群组

客户可以将多个列族组合成局部性群族.对每个子表中的每个局部性群组都会生成一个单独的SSTable.将通常不会一起访问的列族分割成不同的局部 性群组,将会提高读取效率.例如,Webtable中的网页元数据(语言和校验和之类的)可以在一个局部性群组,网页内容可以在另外一个群组:如果一个应 用要读取元数据,它就没有必要去访问页面内容.

此外,每个群组可以设定不同的调试参数.例如,一个局部性群组可以被设定在内存中.内存中的局部性群组的SSTable在被子表服务器装载进内存的时候,使用的装载策略是懒惰型的.一旦属于该局部性群组的列族被装载进内存,再访问它们就不必通过硬盘了{读不懂?知道机器翻译有多难了吧?人翻译都不行}.这个特性对于需要频繁访问的小块数据特别有用:在BT内部,我们用这个特性来访问元数据表中的地址列族.

压缩

客户可以控制是否压缩一个局部性群组的SSTable.每个SSTable块(块的大小由局部性群组的调试参数确定),都会使用用户指定的压缩格式.尽管这样分块压缩{比全表压缩}浪费了少量空间,但是在读取SSTable的一小部分数据的时候,就不必解压整个文件了{那是,你们文件巨大,硬盘又便宜}. 很多客户使用两遍的订制压缩方式.第一遍是Bentley and McIlroy’s方式[6],该方式在一个大的扫描窗口中将常见的长串进行压缩.第二遍是一种快速压缩算法,在一个16KB的小扫描窗口中寻找重复数 据.两个算法都很快,现有机器上压缩速率为100到200MB/s,解压速率是400到1000MB/s.

尽管我们选择压缩算法的重点是速率,而非空间效率,这种两遍的压缩方式空间效率也令人惊叹{老大,别吹了,您老是在压字符串哪!你去压压运行代码看看?}. 例如,在Webtable,我们用这种压缩方式来存储网页内容.针对实验的目的,我们对每个文档只存储一个版本,而非存储所有能访问的版本.该模式获得了 10比1的压缩率.这比一般的Gzip的3比1或者4比1的HTML页面压缩率好很多,因为Webtable的行是这样安排的:从一个主机获取的页面都存 在临近的地方,这种特性让Bentley-McIlroy算法可以从一个主机那里来的页面里找到大量的重复内容.不仅是Webtable,其他很多应用也 通过选择行名来将类似内容聚集在一起,因此压缩效果非常的好{针对数据和程序特性选择的压缩算法}.当在BT中存储同一数据的多个版本的时候,压缩效率更高.

使用缓存来提高读取性能

为了提高读操作性能,子表服务机构使用两层缓存.扫描缓存是高层,它缓存子表服务器代码从SSTable获取的关键字-值对.块缓存是底层,缓存的 是从GFS读取的SSTable块.对于经常要重复读取同一部分数据的应用程序来说,扫描缓存很有用.对于经常要读取前面刚读过的数据附近的其他数据(例 如,顺序读{性能提升老花招:预取},或者在一个热门的行中的同一局部性群组中,随机读取不同的列)的应用程序来说,块缓存很有用{后面这句比较拗口,是说一个局部性群组里的列都在缓存里,可以随机读取}.

Bloom过滤器{需要读参考文献才知道是什么意思.从标题看,bloom是一种杂凑函数,有相对低的不命中率,所以可以用它来猜测一个关键字对应的存储数据在哪里,从而减少访问硬盘的次数,以提高性能}

如5.3节所述,一个读操作要知道一个子表的所有状态,必须从所有SSTable中读取数据.如果这些SSTable不在内存,那么就需要多次访问 硬盘.我们通过允许客户对特定局部性群组的SSTable指定bloom过滤器[7],来降低访问硬盘的次数.使用bloom过滤器,我们就可以猜测一个 SSTable是否可能包含特定行和列的数据.对于某些特定应用程序,使用少量内存来存储bloom过滤器换来的,是显著减少的访问磁盘次数.我们使用 bloom过滤器也使当应用程序要求访问不存在的行或列时,我们不会访问硬盘.

修改日志{commit-log}的实现

如果我们把对每个子表的修改日志都另存一个文件的话,就会产生非常多的文件,这些文件会并行的写入GFS.根据每个GFS底层实现的细节,这些写操 作在最终写入实际日志文件的时候,可能造成大量的硬盘寻道动作.此外,由于群组不大,为每个子表建立一个新的日志文件也降低了群组修改的优化程度.为了避 免这些问题,我们将对每个子表服务器的修改动作添加到一个修改日志中,将多个子表的修改混合到一个实际日志文件中[18,20].

使用单个日志显著提高了正常使用中的性能,但是将恢复的工作复杂化了.当一个子表服务器死掉时,它以前服务的子表们将会被移动到很多其他的子表服务 器上:它们每个都装载很少的几个子表.要恢复子表的状态,新的子表服务器要按照原来的服务器写的修改日志来重新进行修改.但是,这些修改记录是混合在一个 实际日志文件中的.一种方法是把日志文件都读出来,然后只重复需要进行的修改项.但是,用这种方法,假如有100台机器都装载了要恢复的子表,那么这个日 志文件要读取100次(每个服务器一次).

避免这个问题的方法是先把日志按照关键字排序.在排序以后,所有的修改项都是连续的了,只要一次寻道操作,然后顺序读取.为了并行的排序,我们将日 志分割成64MB的段,并在不同的子表服务器上并行的排序.这个排序工作是由主服务器来协同的,当一个子表服务器表示需要从某些日志文件中开始恢复修改, 这个过程就开始了.

有时,向GFS中写修改日志文件会导致性能不稳定,原因很多(例如,正在写的时候,一个GFS服务器不行了,或者访问某三个GFS服务器的网络路由 断了或者拥塞).为了在GFS延迟的高峰时还能保证修改顺利进行,每个子表服务器实际上有两个线程:各自写不同的日志文件;两个线程里只有一个活跃.如果 一个线程的写操作性能不好,就切换到另外一个线程,修改的记录就写入新的活跃线程的日志文件.每个日志项都有序列号,在恢复的时候,由于线程切换而导致的 重复的序列号将被忽略.

加速子表的恢复

如果主服务器将一个子表从一个子表服务器移动到另外一个服务器,第一个子表服务器对子表进行轻度压缩.该压缩减少了子表服务器的日志文件中没有被紧 缩的状态,从而减少了恢复时间.压缩完成以后,该服务器就停止服务该子表.然后,在卸载该子表前,该服务器再次进行一次(通常很快)轻度压缩,以消除在前 面一次压缩时遗留下来的未紧缩的状态.第二次压缩做完以后,子表就可以被装载到另外一个服务器上,而不必请求从日志中恢复了.

利用不变性{immutability,不可写,可以并行读取}

除了SSTable缓存以外,由于所有生成的SSTable都是不变的,所以BT的很多其他部分都变的简单了.例如,当从SSTable读的时候, 就不必进行同步.这样一来,对行的并行操作就可以非常有效的实现了.内存表是唯一一个被读和写操作同时访问的可变数据结构.为了减少在读操作中对内存表的 竞争,内存表是写复制的,这样一来就可以并行进行读写操作.

因为SSTable是不变的,因此永久消除被删除的数据的问题,就转换成对过时的SSTable进行垃圾收集的问题了.每个子表的SSTable们 都在元数据表进行注册.主服务器对SSTable集合进行标记-扫除的垃圾收集工作[25],元数据表保存了根SSTable集合。

最后,SSTable的不变性使分裂子表的操作更加快速。我们不必为每个分裂出来的子表建立新的SSTable集合,而是让分裂的子表集合共享原来子表的SSTable集合。

5.实现
BT 的实现有三个主要组件:客户程序库,一个主服务器和多个子表服务器.针对负载的变化,可以动态的从服务器群中添加(或者去除)子表服务器.主服务器的任务 是:给子表服务器指定子表,检测加入或者失效的子表服务器,子表服务器负载均衡,以及对google文件系统的文件进行垃圾收集.除此之外,它还处理诸如 建立表和列族之类的表模式改变工作.

每个子表服务器管理一个子表集合(通常每个服务器处理数十乃至上千个子表).子表服务器负责处理对它管理的子表进行的读写操作,当子表变的太大时, 服务器会将子表分割.和很多单个主服务器分布式系统[17.21]一样,客户数据不经过主服务器.客户的读写操作是通过直接和子表服务器通信完成的.由于 BT的客户不必通过主服务器获取子表位置信息,大多数客户完全不和主服务器通信.因此,实际使用中主服务器的负载很轻.

一个BT集群存储多个表.每个表由一些子表组成,每个子表包含一个行域内的所有数据.在起始状态下,一个表只有一个子表.当一个表长大以后,它自动的分割成多个子表,每个子表的缺省大小是100到200MB.

5.1 子表的地址

子表地址信息是存储在一个三层类似B+树[10]的结构中的(图4).

fig4.JPG

图4:子表地址结构

第一层是Chubby中的一个文件,它存储根子表的地址.根子表里存储一个特殊的表里的所有子表的地址,地址这个特殊的表是元数据表.每个元数据子 表里存储一组用户子表的地址.根子表其实是元数据表里的第一个子表,但是对它的处理比较特殊:根子表永远不会被分割,这样一来保证了子表地址结构不会超过 三层.

元数据表里面,每个子表的地址都对应一个行关键字,这个关键字是由子表所在的表的标识符,和子表的最后一行编码而成的.每个元数据行在内存里存储大 约1kb的数据.元数据子表的大小限制是128MB,限制看似不大,不过已经可以让这个三层的地址树足够表示2^34个子表了(如果每个子表存储 128MB数据,一共是2^61字节数据).

客户程序库缓存了子表地址.如果客户没有一个子表的地址,或者它发现地址不正确,客户就递归的查询子表地址树.如果缓存是空的,那么寻址算法需要三 次网络来回通信来寻址,其中包括一次Chubby读操作.如果缓存数据过期,那么寻址算法可能最多需要6次网络来回通信才能更新数据,因为只有在缓存不命 中的时候才能发现数据过期{三次通信发现过期,另外三次更新数据}(这里的假定是,元数据子表没有频繁的移动).子表的地址是放在内存里的,所以不必访问google文件系统GFS,我们通过预取子表地址来进一步的减少了访问开销{体系结构里的老花招:缓存,预取}:每次读取子表的元数据的时候,都读取几个子表的元数据{为什么不说预取几个子表地址?俩?四个?这里就是有价值的东西了,需要时间去积累经验}.

在元数据表中还存储了次要信息,包括每个子表的事件日志(例如,什么时候一个服务器开始服务该子表).这些信息有助于排错和性能分析{一笔代过重要信息,比如都存了什么事件,事件属性是什么等}.

5.2子表分配

在任一时刻,一个子表只会分配给一个子表服务器.主服务器知道当前有哪些活跃的子表服务器,还知道哪些子表分配到哪些子表服务器,哪些以及哪些子表 没有被分配.当一个子表没有被分配到服务器,同时又有一个服务器的空闲空间足够装载该子表,主服务器就给这个子表服务器材发送一个装载请求,把子表分配给 这个服务器.

{这里是协议描述}BT使用Chubby来追踪子表服务器.当一个子表服务器启动时,它在一个特定的Chubby目录里建立一个有唯一名字的文件,并获取该文件的独占的锁.主服务器监视这个目录{服务器目录},就可以发现新的子表服务器.一个子表服务器如果丧失了对文件的锁,就停止对它的子表们的服务.服务器可能丧失锁的原因很多,例如:网络断开导致服务器丢失了Chubby会话(Chubby提供一种有效的服务,使子表服务器不必通过网络就能查询它是否还拥有文件锁{这个比较神,难道是tablet server自己只查本地文件,chubby server来帮它在本地建立文件?要认真看看chubby的协议才知道}). 如果文件依然存在,子表服务器会试图重新获得对文件的独占锁.如果文件不存在了,那么子表服务器就不能服务了,它就退出.当子表服务器终止时(例如,集群 管理系统将子表服务器的机器从集群中移除),它会试图释放文件锁,这样一来主服务器就能更快的把子表分配给其他服务器.

当一个子表服务器不再服务它的子表的时候,主服务器有责任发现问题,并把子表尽快重新分配.主服务器发现问题的方法是定期询问子表服务器的文件锁状 态.如果一个子表服务器报告丢失了文件锁,或者过去几次询问都没有反应,主服务器就会试图获取子表服务器的文件锁.如果主服务器能够获取锁,说明 Chubby是好的,子表服务器或者是死了,或者不能和Chubby通信,主服务器就删除子表服务器的文件,以确保子表服务器不再服务子表.一旦一个服务 器的文件被删除,主服务器就可以把它的子表都放入未分配的子表集合中.为了保证在主服务器和Chubby之间有网络故障的时候BT仍然可以使用,主服务器 的Chubby会话一旦过期,主服务器就退出.但是,如前所述,主服务器故障不影响子表到子表服务器的分配.

当一个集群管理系统启动一个主服务器时,它需要发现当前的子表分配状态,然后才能修改分配状态{设计思想:永远考虑失效+恢复}.主服务器执行以下启动步骤:(1)主服务器在Chubby中获取唯一的主文件锁,来阻止其他主服务器实例{singlton}.(2)主服务器材扫描Chubby服务器目录,获取当前活跃服务器列表.(3)主服务器和活跃子表服务器通信,获取子表分配状态{注意子表分配不是主服务器存储的,保证了失效时主服务器不会成为性能瓶颈}.(4)主服务器扫描元数据表,每次遇到一个没有分配的子表,就加入未分配子表集合,这个子表就可以被分配了.

这里有一个复杂的情况:在元数据表没有被分配之前,是不能扫描元数据表的{鸡和蛋}.因此,在开始第四步的扫描之前,如果第三步的扫描没有发现根子表没分配,主服务器就把根子表加入未分配的子表集合.这一附加步骤保证了根子表肯定会被分配.由于根子表包括了所有元数据子表的名字,主服务器在扫描过根子表以后,就知道了所有的元数据子表.

现存子表集合仅在以下事件中才会改变:一个子表被建立或者删除,两个子表被合并,或者一个子表被分割成两个.主服务器可以监控所有这些事件,因为前 三个事件都是主服务器启动的.最后一个事件:分割子表,是由子表服务器启动的.这个事件是特别处理的.子表服务器在分割完毕时,在元数据表中记录新的子表 的信息.当分割完成时,子表服务器通知主服务器.如果分割的通知没有到达(两个服务器中间死了一个),主服务器在请求子表服务器装载已经分割的子表的时 候,就会发现这个没有通知的分割操作{设计的时候一定要考虑到错误和失败的恢复.古人云,未思进,先思退}.子表服务器就会重新通知主服务器,因为在元数据表中找到的子表入口只包含要求装载的子表的部分信息{细节,细节呢?}

//今天比较忙,只有这些了.抱歉.

//更新:彼岸翻译了第5章的剩余部分,贴在这里:

5.3 子表服务

Bigtable_Figure5.jpg
图5:子表表示

子表的状态存放在GFS里,如图5所示。更新内容提交到存放redo记录的提交日志里{比较绕,看原文可能清楚点}。在这些更新中,最近提交的那些存放在内存里一个叫memtable的有序缓冲里;老一点的更新则存放在一系列SSTable里。若要恢复一个子表,子表服务器从METADATA表中读取元数据。元数据包括了由一个子表和一系列redo点{redo怎么翻好?}组成的SSTable列表,这些是指向可能含有该子表数据的提交日志的指针{烦死定语从句了}。 该服务器把这些SSTable的索引读进内存,并通过重复redo点之后提交的更新来重建memtable。

当一个写操作到达子表服务器时,该服务器检查确信这个操作完整无误,而且发送方有权执行所描述的变换。授权是通过从一个Chubby文件里读取具有 写权限的操作者列表来进行的(几乎一定会存放在Chubby客户缓存里)。合法的变换会写到提交日志里。可以用成组提交来提高大量小变换的吞吐量 [13,16]。写操作提交后,写的内容就插入到memtable里。

当一个读操作到达子表服务器时,会作类似的完整性和授权检查。合法的读操作在一个由SSTable系列和memtable合并的视图里执行。由于SSTable和memtable是字典序的数据结构,合并视图可以很有效地形成。

进来方向的{incoming}读写操作在子表分拆和合并时仍能继续。

5.4 紧缩{compaction}

在执行写操作时,memtable的大小不断增加。当memtable大小达到一定阈值时,memtable就会被冻结,然后创建一个新的memtable,冻结住的memtable则被转换成SSTable并写到GFS里。这种次要紧缩过程有两个目的:缩小了子表服务器的内存用度,以及减少了在服务器当机后恢复过程中必须从提交日志里读取的数据量。 进来方向的读写操作在紧缩进行当中仍能继续。

每一个次要紧缩会创建一个新的SSTable。如果这种行为一直继续没有停止的迹象,读操作可能需要合并来自任意多SSTable的更新。相反,我们通过定期在后台执行合并紧缩来限定这类文件的数量。合并紧缩读取一些SSTable和memtable的内容,并写成一个新的SSTable。一旦紧缩完成,作为输入的这些个SSTable和memtable就可以扔掉了。

把所有SSTable重写成唯一一个SSTable的合并紧缩叫作主要紧缩。 由非主要紧缩产生的SSTable可以含有特殊的删除条目,它们使得老一点但仍活跃的SSTable中已删除的数据不再出现。而主要紧缩则产生不包含删除 信息或删除数据的SSTable。Bigtable在它所有的子表中循环,并且定期对它们执行主要紧缩。这些主要紧缩使得Bigtable可以回收已删除 数据占有的资源,并且还能保证已删除数据及时从系统里小时,这对存放敏感数据的服务很重要。

February 18, 2010

攒机器这个事情,也就是以前在国内才干,当时不仅自己攒,还带着我照顾的留学生攒。对,你没看错,我在国内照顾留学生来着。

留学生的故事咱们先放着,留着以后说。这个攒机器,就是去买一堆零件,回来自己配。以前在国内,跑到小店里面,买好CPU,主板,内存,硬盘,显卡声卡机箱还有显示器鼠标键盘,回来一拼就好了,然后再跑到光盘店里面去淘几张合集回来,或者干脆去同学那里抢,哦不,是借,我们读书人,怎么能干抢东西的事情呢?

现在攒机器其实也差不多,跑到本地的店里去买点CPU加主板的打折货,然后去网上买硬盘和内存机箱,回来装起来,再弄个Ubuntu就好了。一共也就400美元不到的样子,就拼出一台4核,4G,1TB的机器。这样算算,也就是100块钱+100瓦一个核,要是在家里弄一个16核的集群,需要1600美元,没准还有折扣。

唯一的问题就是,通过无线网做remote desktop还是太慢,还不能把集群全都扔到车库里面去。

December 15, 2009

昨天写了电波和列车,引来Song的专业评论。看来我这里虽然偏僻,但是还是有不少专业人士在看,这样好,我也不靠口水和美女去争取流量,有高质量的读者才重要。

那我今天再写一个物理量让人迷惑的事情:芯片的速度。

通常在通俗读物里面,芯片之所以快,都是因为它们是用电信号来计算的,这个电信号其实不准确:到底这个信号是不是电磁波的速度呢?比如:一个计算的结果,从芯片的一级流水线传递到下一级,是不是用光速传播的呢?

当然你可以说,这个速度不是每秒30万公里,因为芯片的导线是铝或者铜,不是真空,所以没有那么快。事实上,信号在芯片里面传播的速度,比电磁波的速度要小很多很多,否则intel的那群芯片设计师们,也不要努力缩小线宽了,把线路弄短是正经。

说到这里,再提一个问题:为什么线宽越小,芯片的速度越快呢?

答案是:在芯片里面,信号的传递速度,是受限于导线的充电速度的。当电流从一根导线的一段传递到另外一段的时候,这根导线实际上相当于一个电容,而高电平则是对电容充电,低电平则是放电,当充电/放电的过程结束的时候,导线两端的电压一致,信号就传递过去了。电容越大,充电和放电的时间越长,信号就传递的越慢。

导线的电容,正比于导线的面积,所以导线越短,线宽越窄,电容就越小,信号速度就越快。

December 12, 2009

昨天急着赶路,没时间详细说。为什么会有电波抓不住列车的事情呢?协和号高速列车一个小时也不过跑170到220公里(咦?搜狗怎么看见220,就认为gongli应该是“宫里”不是“公里”?你们的HMM是用辫子戏训练出来的?),电波可是一秒跑30万公里的。要是电波抓不住手机,那我们的列车就是银河铁道999,我们也不用去非洲挖矿了,直接移民人马座。

有点手机常识的人都知道,手机是和基站通信的,各个基站各管一片地方,很多基站管理的区域,组成类似蜂窝的系统覆盖地球表面。所以在美国,手机不叫handphone叫cellphone。在手机运动的时候,如果跨越基站管理区域的边界,那么在两个基站之间会有交接工作,把手机的通信从离开的那个区域的基站交给进入区域的基站。

当然实际的操作比这个复杂多了,比如一个地方三个基站覆盖怎么办?手机去问谁?你去问问丁磊关于魔兽,就知道有多复杂了。

扯远了,接着说基站和手机。手机运动的快了,在切换基站的时候,就会发生基站处理不过来的事情:这边基站还在跟另外一个基站商量谁管这个手机的时候,手机已经跑过去了。

不过,列车再快,和汽车的速度也差不了多少,那么既然高速公路上面开车打手机没问题,为什么高速列车上面打手机就有问题呢?

December 9, 2009

Intel刚刚宣布取消Larrabe项目。看起来intel进军图形处理器市场的努力再次遭到挫折。

以前intel成功的推出了i740,但是紧随其后的Timna,一款CPU+GPU+Mem controller的低端处理器就失败了。最近Apple又拒绝使用Arrandale,现在Larrabee也取消了。

但是随着游戏市场的继续增长,我相信intel对GPU的努力会继续。

Next Page »