OLAP实践(一) CrushJoin系统介绍

一、系统背景

      最近一段时间,我与同事liangjun(http://blog.csdn.net/hit_hlj_sgy)一直在对OLAP系统进行一些调研、开发以及将相应的系统在Sina weibo数据中的使用进行推广。在这一过程中,我们有一些经验,开发了一些实用的组件或系统,近期会进行一些分享。

      这篇blog主要介绍我们上个月完成的CrushJoin系统,工程名称揭示了它产生的意义,就是尽量减少join操作对集群数据,尤其是某些表进行反复、重复的扫描。它的背景如下:对于weibo中用户数据,每个用户由一个uid对应,同时用户有很多属性,包括他的年龄、省份、注册时间、性别、兴趣、用户活跃度、用户质量等等,经过整理以后发现总共有多达100+的属性,这些属性分布在10几张hive表中。非常重要的一种场景是数据分析师需要对用户的属性进行ad-hoc查询,比如我们想要知道在北京的用户中他的年龄构成如何,或者说我们要分析上海用户中年龄是40-50岁的用户是长期登陆的用户占上海用户中的总量多少。目前为止,现有的做法是根据需要的属性将多个表进行join,join的键为刚才提到的uid。这种方法的问题非常多,首先是ad-hoc查询需要尽快的查询时间,而通过hive转化为mr查询的方式在时间上根本无法做到实时,用户从提交查询到最后获得结果一般都需要十几甚至几十分钟,join的较多时候甚至是以小时为单位才能够查询出来。第二,这种查询都会join用户基础表,每次查询都需要扫描用户基础表将会十分浪费。

      为此,我们希望设计一套系统,能够提供给用户秒级的查询速度,满足用户对任意维度的属性进行join和in操作。这套系统准确的说不能算严格意义上的OLAP系统,因为传统意义上的OLAP分为维度(dimensions)+度量(metrics),要对多种维度进行join,groupby操作,获得相应的度量。这套系统借鉴了OLAP系统中的一些结构,更准确的叫法应该是多维filter系统。


二、相关知识

      下面我们来看一下用于这套系统的基本知识:

      1、bitmap

      bitmap也可称作bitset,是由0或者1构成的bit数组,如下图:

         Crush1

 

      其中每一位都是一个位移(offset),对bitmap的操作有AND,OR,XOR等等,因为所有操作都是按位运算,所以运算速度异常迅速。

 

      如果我们将用户的uid映射为bitmap中的一位,这样我们的count计数就转换为bitmap对应位为1的个数。就比如上图,我们可以计算出具有某种属性的用户为4。如果我们需要获得具有两个及以上的属性和,那么就将对应的bitmap进行按位与(AND)操作即可,如下图

        Crush2

      两个对应属性AND后,可以计算出满足这两个属性的用户数为2,以此类推。

      2、全排序

      我们知道,mapreduce的特性是在reduce端按key排序,但是,这种排序不是全局性的,而使用bitmap需要对全局uid进行排序,所以我们需要进行一次全排序。为此我们估算总共的用户,以及每个reduce需要的用户。这需要两步,首先是分析阶段,需要根据reduce个数,将总共的用户进行采样,确定每个reduce需要处理的uid下限和上限。第二步就是根据第一步的结果,使用TotalOrderPartitioner以及提供采样文件,就可以做到reducer之间有序,reducer内部也是有序的全排序。具体细节可以查询TotalOrderPartitioner,当然这步我们是做了一些修改。


三、系统设计与流程

      我们将所有的bitmap存储在Hbase中,Hbase表的设计为,在全排序获得的UID范围为key, columnFamily为1,column是排序好的属性,其中属性名称与int做了一个映射,所以column是1、2、3….等,value对应了该UID范围reduce计算好的各个属性的bitmap进行序列化的结果。

      Hbase建表的时候我们就根据reduce计算生成的文件设置好region数,这里的region数设置为200个,主要是方便我们查询时候使用Coprocessor,提升查询的并发性和速度。同时,这里需要特别说的是,bitmap的实现有多种,比如java原生的实现,但是如果数据量过大,即使是按位运算数据量也不能忽视,尤其是我每个reduce根据属性个数大概是150+的属性,每个属性生成一个bitmap,并存储在hbase中,数据量非常大。这里我们使用了Roaringbitmap,他的地址是https://github.com/lemire/RoaringBitmap,目前很多开源的OLAP项目都使用它,比如Druid。我们目前测试的效果,根据你的bitmap稀疏程度,RoaringBitmap基本上都能压缩几百甚至上千倍,并且计算更快,非常方便。

系统的流程如下:

                   Crush3

      1、系统每天更新一次,首先使用mr任务,将所有表对应的属性按照全排序,分布到对应的reduce端,reduce端根据属性值对每个属性生成一个bitmap,同时写入HFile中。

      2、HFile生成完成后,将HFile distcp到我们的Hbase集群中,通过bulkload将数据导入

      3、后端是个Jetty Server,用户查询通过Jetty Server,转换为对Hbase的查询,查询使用Coprocessor

      4、Hbase将Coprocessor结果返回给Jetty,Jetty立即将用户数量返回给用户,同时异步的将对应的UIDs写入到一个文件,方便用户查询

 

     经过我们的测试,查询10个属性总共需要600ms,将原先离线的join,转化为实时查询,完成了我们的目的。

Print Friendly

jiang yu

Leave a Reply