google大数据分析之dremel

本来关于dremel在半个月前就大概看了看论文(也就是fake post之前的一周左右吧),不过由于一直对搜索的query execution tree不了解,加上最近有点小忙,也就一直没有更新。

今天下午去买了一套金鱼装备,安装,洗沙折腾了几个小时,不过很好玩,看着金鱼,读个paper,挺惬意的。顺便,也把之前漏过的tech blog补上,赶紧写完,跑步去。

不说废话了,开始正题。本文结构如下:

1. dremel的背景;

2. dremel的几个关键思路;

3. dremel对应的开源产品,以及目前的进展;

第一节:dremel的背景

google一直是互联网技术的探路者,每公布一个产品,都会引起业界的轰动和效仿。比如03 gfs,04 mapreduce,06 chubby,06 bigtable,以及后来的tenzing,megastore,percolator,pregel,dremel,几乎每个产品,如今都能在开源界找到对应的产品或功能。但是这里有三点需要清楚认识到:

1)google只公开了部分产品,实际上,google内部大量使用的其他产品,如borg,colossus, etc.,并没有如上般公布出来;

2)google公布的产品,大多数是在内部使用了很成熟了才公布,比如dremel是06年已经在google内部上千台机器上广泛使用,10年才公布,业界广泛对其的效仿,目前也还没有一个成型的系统,可以看到这样的认识差距,或者说google的对于大数据量的分布式需求,明显超过业界其他公司至少5年;

3)google的工程师都是顶尖的工程缔造者,据说,业界目前对其很多产品的copy,性能跟g内部实现版本的差距非常大,玩架构牛,玩细节也牛,levelDB炫目的性能可见一斑。

所以说,。。。。好像没什么好说的,好好学习人家的思想,和思考怎么想到这些思想的。吧。

关于dremel,生于大数据时代,论文的标题为《Dremel: Interactive Analysis of Web-Scale Datasets》,就是大数据的交互(即时)分析,说白了它的目的就是让用户,使用海量数据(PB级别)分析,就像使用单机mysql一样,方便,快速。

我们知道tenzing & hive都是架在hadoop上面,通过将用户的query请求转化为mr job来完成查询,一般的响应时间都至少是分钟级以上,或者说就是mr job的时间级别。而dremel是架在gfs上的,跟hadoop没有半毛钱关系,即便说有关系的话,也是hadoop处理后的数据,放到gfs上,然后利用dremel去查。

另外还有一点,storm & apache s4等流式计算是不同于hadoop & dremel的一类,dremel跟storm的定位也是完全岔开的,他们三者的定位区别在于(参考techcrush的一篇文章,忘记标签了。。。):

1)hadoop是对离线数据的积累,然后batch计算;

2)streaming计算式在数据产生的时候,就流进来,立马计算;

3)dremel是以上二者的下一个流水的事情,对已知数据的交互分析;

所以说,dremel是与上面的所有是互补的,并不能谁取代谁,dremel需要以上两种提供整理后的数据集。好吧,铺垫扯淡的不少了,开始讲dremel的细节了。

 

第二节:dremel的几个关键思路

dremel的思路很清晰,简洁,就是用恰当的数据存储格式,并结合搜索引擎的query execution tree的思路来加速。所以,关键点是两个:

1. 如何描述数据,相应的对进来的数据进行描述,并且在需要的时候,反过来根据描述来完整的构造数据;

2. 基于以上的数据格式,定制化的做了一套具体执行查询的流程;

首先我们看第一个技术点。

我们先看看目前业界大数据的结构化存储描述,基本上都是nested(嵌套数据),比如json, xml, protocol buffer, thrift等,在集群中实际存储的细节格式的典型无疑是bigtable:

这是典型的行式存储,行有schema,并且带version。这样来看,当我们按此格式,存储1p的数据,现在只查询contents 这个field时候,需要扫描整个系统(虽然底层是按照列存储的,但是基本上要扫描所有机器)。dremel中表述这种结构一个简图就是:

左边是bigtable的格式,右边是dremel的格式。可以明显看到,dremel把各个field都拆出来,单独存储到一起,那么这样的一个典型好处是当我们只需要查询某几个field的时候,field间就自然隔离,数据集也要小很多,自然计算速度也要高很多,当然这只是粗略但显而易见的想法。

优点是看出来了,但是问题是怎么把数据拆出来呢? 而且必要的是,要能够准确的复原数据,换句话说,是要能split,能assemble。关于这点,google非常巧妙的做了两个定义:repeatition level & definition level。这个主要是结合protocol buffer来做的,所以使用过protocol buffer的读者对下面这个message定义就不能再熟悉了(不熟悉的自己refer一下pb的文档吧):

在这个结构下,结合dremel,如何表示出r1 & r2两个实际的数据呢?

现在可以说repeatition level & definetion level的含义了,简单说,针对的就是pb中repeated & optional这两项。

1.repeatition level:表示数据的重复情况,针对的就是pb中的repeated这一项,稍微不同的是,比如Name.Language.Code,这个在哪一级repeat了,就对应的写[012];

2.definition level:表示数据是否为空,对应pb中optional项,其实一般来讲,如果为空,一个bool就可以表示了,但是dremel论文提到,google还是选择用整数来表示,这是因为恢复数据的考虑,具体可以参见论文,细节不表。

是个时候給个example来说明repeatition & definition了,但是给图之前,先介绍个简单方法来使读者更容易根据r1 & r2写出对应的r & d结果。先把r1 & r2中,对message中require数据都标上,如果不存在的话,就写为null,然后再统一数repeatition leve & definition level。好吧,反正最终结果是:

数据格式大概就长这个样子了,split完后,恢复数据assemble是怎么样的呢?如下:

这个图很简单明了,就是一个状态机。

关于数据表示就到这了。下面看看利用搜索引擎的query exectution tree来运算,实时相应用户请求。(22:30了,跑步时间远远不足,还要写drill & open dremel,现在开始简写加速)。

一个思想就是跟sql的单机查询树差不多(细节不了解,猜的哈哈),看图就知道了:

好吧,简意就是将一个query,根据root server拆分,发到各个intermediate server上去查询,(可以有多层intermediate server),最后实际执行时各个leaf server(也就是存储数据的机器),各个intermediate server实际上是起了aggregrator的作用。这个一猜就猜到了,关键问题是如何做拆分? 这个才是执行时期的核心,以及dremel有专门的资源调度算法,和异常失败处理。这个太细节的也不清楚,不过执行拆分可以参考sql,失败可以参考hadoop,或者等drill开发完成了看看代码。

好吧,差不多就这样了,来个性能图,大概看看我们说的这个东东到底表现咋样。

看到了吧,大概是10s级别。不过能看明白MR-columns是什么东东吗? 哈哈,留给自己参看dremel的论文吧,一个小小trick, just for test。

 

进入第三部分,开源界dremel相关进展。

其实主要看这两篇文章就明白了。

drill的apache主页:http://wiki.apache.org/incubator/DrillProposal

open dremel页:http://bigdatacraft.com/archives/327

实际上,这两个都刚开始,文中可以看出,drill完成分析,定了要做哪些features,并且对于分拆的几个引擎做了框架部分,还没打通,主要主力是mapR的,感觉还没有看见超牛介入,所以说,可以看到大家的积极性不高,相比之下,pregel的公布时间差不多,业界的几个系统早就起来了。open dremel的情况也差不多。

不过从drill中一段话The Drill architecture consists of four key components/layers,还是可以预见到一些可能采用的东东的。

终于over了,我的金鱼还在欢快的游泳~ 丝毫没有歇着的迹象。

而我也要跑步去了。。。都快晚上11点了,出去溜达下意思下吧。

悲催,这么晚写博客,搞到这时候,不过完成一件之前就规划好的事,还是轻松多了的。

now not fake~

5 thoughts on “google大数据分析之dremel

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>