海量数据OLAP分析实践—-TD Atom Cube

演讲嘉宾：徐岷峰

速记整理：马瑶

大家好，我是徐岷峰，来自于Talking Data，今天很高兴能够跟大家分享一下我们公司在海量数据OLAP上的经验，说到技术呢，首先当然要满足我们的业务需求，所以我们先简单介绍一下Talking Data的业务，Talking Data主要是做什么的呢，它主要做两块，一个是做开发者服务，什么意思呢，比如在座各位手机上的APP，里面可能就有我们公司的SDK，它的作用是什么呢，我们是和这些开发者合作，他们可能从自己的APP当中的一个使用情况，比如说应用今天被谁打开了，然后它的流程是多少，有多少人，比如说有多少人充值了，这些数据对于移动开发者来说都是非常有用的，是提供他进一步提高应用的依据，而我们就是说可以通过SDK，这些数据过来以后，我们可以更新报表，我们现在覆盖的，活跃的设备数量累计已经超过30亿了，每天上来的数据大概有十几个T左右，每天用户访问的Session数差不多也有十几B,所以面对这么大量的数据，应该说是真正海量数据的，那么我们怎么来做OLAP的分析呢，今天我就跟大家分享一下它的技术。

这是目前在业界比较流行的一些开源的OLAP的系统，在左边是MOLAP，右边是ROLAP，MOLAP简单说就是应用于交叉计算，ROLAP顾名思义就是交叉式查询，现在比较流行的，比如像MOLAP中有druid,pinot,还有人之前提到的lylin，然后对于ROLAP，有presto,Spark sql,impala，这些都是比较流行的，这些开源的架构和技术，我们都已经有研究，但是我要说明一点，我们公司是2011年成立的，在我们成立的时候，这些开源的架构和系统当时还都没有，所以当时我们自己设计实现了一套OLAP系统，从现在看起来，这套系统现在正在线上运行，而且从设计思想来看的话，基本上还是大同小异.

这幅图就是2011年的时候，公司当时的技术人员一块讨论，设计出来的一个架构图，这幅图一直沿用到现在，那么我们可以看出来，当数据上来以后，在下面我们是把数据分成实时的和批式的数据，因为对于我们的业务场景来说的话，很多的应用开发者，会实时的查询他们应用的使用情况，比如说过去一小时用户的数量有多少，所以呢，为了满足这种实时的查询，我们把数据分成流式的和批式的，流式的数据会走下面这个分支，有一个流式处理的一个流程，然后处理完一般是当天的数据会存RDBMS或者是Nosql的数据库里面，后面会把这些数据放在海量的数据仓库，然后会有批的任务再跑，再去做进一步的数据分析，这里我们用到的大量MOLAP的技术就是说最小粒度去聚合，然后去预建索引，这幅图是刚才讲的druid，druid它的体系架构，可以看出它是分成了实时节点和历史节点，类似的，你的流式数据也是先进到实时节点，然后它会在内存当中形成一个关系型的表格，实时查询，那么它在一定的时间粒度以后，它会把这些实时数据形成新的文档，会把它存到DEEPSTORE,然后相应的历史节点，会把Segment load起来，这样的话，当你通过Broker查询的时候，它会同时查询实时节点和历史节点那么这个思想和我们当初的设想基本是一致的。

这个是pinot的架构，那么它跟druid的思想基本是一样的，只不过这个图是倒过来画的。

那么我们看一下TD的业务场景结果，这是我们实际线上的数据，这是我们一个典型的事实表，我们可以看到这个TABLE中有time, deviceid, provice, mobile,app,duration, 下面这个也是一个典型的事实表，这里只是把duration换成了event，这里面可能会有充值啊，支付啊，如果是游戏会有冲关啊，如果对于软件会有安装啊，卸载啊，等等这些事件。那么在做这个OLAP过程当中的话呢，一般会有典型的几个计算，一种就是sum，实际上在OLAP里面就是一个切片计算，比如说像这个是统计什么呢，按照全面枪战，看看游戏的时间是多少对所有的人群来说，那么这样我们再去预建CUBE的时候，我们可以把这个deviceid去掉，因为我们要求的时间和deviceid是没有关系的，所以我们就可以把deviceid这个维度去掉，那么我们就可以保留下比如像时间这个维度，然后中间可以保留像地区啊，应用啊，app,像这个时长呢，就作为一个metric,那么通过这种预建CUBE以后的话呢，它的所占的存贮量就会很小了，所有至少减少掉5个数量级，那么另外一个计算呢，就是像count,跟前面是类似的，那么这里我们是做了针对事件的统计，当然我们这里可能会有一个字典表，然后把充值作为一个count,也一样是做这个提前聚合，生成CUBE,这是一个典型的OLAP计算，对于一般意义上的OLAP来说，像count,sum,像我们讲的一般的开源系统都能够非常轻松的实现，而且对于内存，占用率都不大，但是唯独下面有一个计算，是我们面临的一个非常艰巨的任务，就是distinct count,比如我想算在某一个时间段内，玩过所有全面枪战这个的所有设备，那么这个就是典型的要进行排重的计算，我们看到刚才的那几个维度都是有限的，比如说，如果我按照地区来做聚合的话，全国可能有三十多个省份，但是对于deviceid来说，它是无限增长的这么一个维度，这样就意味着如果我想排重的话，我就要保留所有的deviceid，这个对于存储，或者是计算量来说的话，都是不可想象的，那么怎么来解决这个问题呢，这实际上是一个基数计算的问题，那么这道片子讲的就是说目前在进行基数计算的时候，主流的几种技术，一个是用HASHset,我们知道一个SET里是不允许有重复的元素的，所以用HashSet来做这种排重是可以的。

下面这两种呢，像Linear, HyperLogLog呢，这是两种算法，它们都是一种估算的算法，这张表格的数据是我从互联网上拷贝过来的，这是用它来说明问题，那么我们从这里可以看到如果用HashSet来做的话，内存的使用量，是远远超过下面两种估算的使用量的，那么现在的问题是我们在做OLAP的时候，需不需要精准的计算，那么很不幸的是，我们公司的业务是需要这种很精准的计算的，因为我们有比如说这种业务，广告商和渠道之间，那么广告商投放了广告以后，他希望获得什么数据呢，他需要知道广告投放以后有多少人去点击了，能够来衡量广告的投放效果，按照以往的时候，他只能按照是渠道给它的数据，你投放的广告效果很好，有多少多少的点击量，那么它的转化率是多少呢，可以给你估算一个，但是其实这其中是缺乏一个信任的，因为从广告商来看的话，可能我的销量并没有出现大幅的增长，这时候Talking Data会有一个产品，就是做这种中间数据的监测，就是说渠道的数据可以汇聚到我这里来，然后同时我们有用户设备上的点击数据，我们可以做这个统计，然后把这个数据提供给渠道和广告商，就等于说我们三方去对比这个数据，涉及到钱的这方面比较敏感，需要做这种精准的技术计算，另外一个例子比如说游戏的APP，尤其是上线初期的时候，他非常关心日活量是多少，也真的是有客户因为个位数的误差来跟我们较真，因为我们是做这种服务的，所以肯定会有这种技术来满足公司的需求，所以我们无疑是要做这种精准的技术计算，但是我们刚才也看到了，如果使用HashSet那样内存消耗太大了，我们又是海量的数据，怎么办呢，这就是我们TD ATOM CUBE使用BitMap来进行处理，什么是BitMap呢，BitMap就是一个非常大的数组，数组中的每个元素就是一类，我们当时使用了counciseSet，下面是它的这个网址，感兴趣的同学可以上去看一看，我们在counciseSet上又做了一些改良和优化，封装成了我们现在使用的BitMap，同时一个BitMap我们可以认为它是一个数据集，所以对于集合里的所有操作它都是满足的，那么这些操作在做OLAP的时候都会用到，待会儿我会讲，那么我们就做了一些测试，就是使用BitMap计算基数的时候它跟HashSet还有估算HyperLogLog这些算法之间做了一个比较。

这个是我们的实验数据，首先我们是产生大量的不重复的离散度高的数字，这个就比较符合应用场景，因为设备已经达到好几十亿了，随之上来的数据肯定是比较离散的，然后同时我们会插入重复的数据，比例4%左右，分布也是相对均匀的，选择测试的数据我们选择了1万，100万，1000万，1亿，分别用这些方法做基数计算，最后我们统计内存占用量，数据的加载消耗的时间和精度。

一百万……

一千万……

这个就是针对1万条数据，我们可以看到HashSet和BitMap基本上是在同一个数量级的，HashSet从时间上来看还优于BitMap，对于估算算法来说的话，比如HyperLogLog，它的计算精度呢，里面有一个参数，叫bucket，就是桶子数量，基本上它的桶子数量越大，精度就越高，但是它内存的占用量也会相应的大一点，从1万条数据来看的话呢，也是远远小于HashSet和BitMap的，那么我们把这个数据提升到100万，我们可以看到HashSet使用的内存数量已经超过一个数量级了，对于HyperLogLog来说，它的内存占用率基本是不变的，而且它的时间相对于BitMap来说也是很小的，这是到了1000万，下面是到了1亿条数据的时候呢，这里我就没有再列出HashSet，因为HashSet已经溢出了，那么可以看到从运行的速度和内存的使用量来看的话呢，估算的算法还是远远的优于BitMap的，它唯一的缺点就是它不是精准的，所以从这一点来说的话呢，它没有办法满足我们的业务需求，所以我们总结一下，用HyperLogLog对同等计算资源所消耗的内存都是优于HashMap和BitMap的方法，HyperLogLog的精度是与桶子数量成正比的，如果对于百万的数据需要高精度的话，BitMap完全可以满足需求，而且也是可接受的，所以在我们的OLAP的场景当中呢，还是大量的用BitMap，因为对于某一款应用来说，它上来某一天产生的deviceid超过百万的应该是不多的,那么怎么来使用BitMap呢?

我们看一个案例，上面是刚才讲的一个事实表，我们把deviceid分出来，分出来以后我们把它做了一个字典表，我们可以看到第一个deviceid对应到0，第二个对应到1，第三个对应到2，那么这个0，1，2我们就可以对应到BitMap的下标，BitMap[0]就是排在第一个的device,BitMap[1]就是第二个device，依次类推，然后我们针对每一个维度都把它形成一个粒度最小的cube,那么我们可以看出，比如针对某一天的app,比如说12月22号，玩全面枪战的device包含的BitMap就只有0和1，使用滴滴打车的是2，我们把所有的维度比如像地区，设备，应用，还有事件，我们都把它形成一个最小粒度的cube,现在我们继续算distinct count的话，现在的这种情况下，我们就把它转换成了BitMap1和BitMap15，做一个and操作，结果就会出来了，所以可以看出用BitMap来做这种聚合的运算呢，计算快，存储少，因为是位运算，同时呢，我们可以看到它可以支持join，这个特性是druid和pinot,包括现在市面上有的一些OLAP的框架都不具备的，我们之前和druid founder做过一些交流，为什么不提供这种join或者说像精准的计算，他给我的回答就是说代价太大了，时间复杂度也比较高，当然他们是做一个开源的框架，他们有他们的考虑，但我们主要是来满足我们的业务需求，所以我们使用BitMap能够对流性数据进行分析，就是今天的数据，昨天的数据，一个月前的数据做聚合的情况，做join的查询，用这个BitMap是非常方便的，druid是你要把它存到数据库里头，原来是用Mysql数据库，存的时候BitMap在内存里头是一个java对象，存在数据库里就存在序列化和反序列化的问题，我们通过实践发现在做序列化的时候，它所耗费的时间还是比较长的，我们就深入的看了consizeSet的实现，我们发现它里面是把BitMap按照word的形式存储的，同时它提供了一些压缩算法，比如说你连续中间出现n个1，n个0，那么它就会用n0，n1来表示，这样的话，它的压缩性能还是比较好的，因为当我们存储海量的数据的时候呢，就算是使用BitMap来存储它的内存消耗也是比较大的，所以必须要有压缩，发现这些特点以后呢，我们就把中间的这些word抽取出来，然后把它存到Mysql数据库中，然后压缩的数据呢，可以在内存中做一个还原，我们通过使用这些特性呢，将性能提高到一个数量级，原来我们采用Mysql数据库，后来我们是用rocksdb，这是facebok开源的一个数据库，对于我们存贮BitMap这种数据呢，也能够提高性能。

另外，我们做BitMap的时候，还做了其他一些优化，比如说增加缓存，对于JAVA来说有堆栈的这种缓存，存储热数据，还对BitMap做了分片存储，根据地区，根据应用做分片的存储，对于单次的请求需求查询大量bitmap的情况，比如说刚才讲的游戏这种的话，中间的维度可能达到三十几个，如果是查一年的数据查一个指标，这时候可能会加载很多大量的OLAP进来，这时候如果是单机来做的话，难免会出现内存溢出啊，或者是从数据库取数据的过程，IO的消耗的时间也是比较长的，那么可以采用fork/join方式来做查询，刚才我们也说了，集合里的并，交，分配率，交换率都是满足的，所以有这种理论的支持我们就可以把它放在各个节点上去做，然后把它们做一下汇总。

最后我们再说一下原子的cube它也有自己的问题，如果大家有兴趣的话，我们把采集的kernel跟大家说一下，这个场景是我想求1月1号到1月2号北京地区充值的app version的情况，如果我简单粗暴的来做的话,我可能把Bitmap1、bitmap5、bitmap3做一下然后再与上Bitmap1 and bitmap5 and bitmap4，这时我们发现1这个用户他是会出现2次的，但是1这个用户在1，2的时候他已经去天津了，导致这个错误的原因在哪儿呢，其实还是在使用BitMap的时候方法不太对，那正确的应该怎么做呢，应该在最小的时间粒度内，做所有的BirMap的这种计算，就是分天做，也要把所有的都放在一起，比如1月1号我们做了上面这个计算以后，然后在1月2号的时候在北京这个人根本就没有，所以你就没有办法做这种与的操作，其实还有个问题，就是如果我按小时粒度来求这个问题的话，那它也解决不了，因为我们的这个cube是基于天来做的，所以如果你想做更小时间粒度的查询，一定要把cube的时间粒度放到小时，当然你如果你要再放小，放到分钟，放到秒，那就没有意义了，这个数据量就太大了，还有就是我们在11年的时候采用这个concize算法，它有一个限制，它基数上限为：1040187422，那么现在我们的设备数已经超过30亿了，那怎么办呢，我们采用了一种分段的算法，就是超过它的上线以后，我们重新再起一个BitMap来做，当然这个在无形当中就增加了计算的复杂量，最近我们又发现了RoaringBitmap，这个也是我们通过测试，准备把concize换成RoaringBitmap，它无论是从内存的空间，压缩还有它计算的时间，现在根据我们的测试来说，都是优于ConciseBitmap的，这是我们做的一个对比的测试，大家可以看到在10万一下的话，在内存的使用率上呢，ConciseBitmap还是要优于RoaringBitmap，但是像比较常用的比如像百万级别的计算，RoaringBitmap的优势就能够体现出来了，RoaringBitmap的上线要比ConciseBitmap大一倍多，它的上线就相当于java里面int的最大值，所以在超过大数据集超过100万的数据，Roaring比Concise更适合，Concise先比于Roaring在加载数据的时候有个弱点就是数据要求是排序的，比如你要成批的再里面加入100条数据，如果你不排序的话，它的速度就更慢了，这个我当时做过一个实验，就是每一百万条数据往ConciseBitmap里面去插，我连续的插入1000万条数据，可能有超过了半个小时，还没有给我返回，后来我们发现它是要排序的，排序以后它的速度就一下上去了，但RoaringBitmap没有这个要求。所以接下来我们要怎么优化OLAP平台呢？

一个是采用分布式的存储，我们现在是基于rocksdb,mysql,当然了，我们也采用了一些Nosql的DB,我们还在做进一步的优化，还有就是采用fork/join架构，我们现在只是把查询做了分解，但是里面还有更复杂的一些问题，比如说负载均衡的问题，我们现在也在做开源的技术解决，另外我们在结合计算方面的话，我们除了为开发者服务这块呢，可能会比较倾向于做这种精准的计算，当然还有些用户他可能只要求趋势的计算，这时候我们就没有必要去做这种精准的计算，所以我们也在考虑核心维度的基数计算采用TDatomcube；非核心维度的基数计算采用hyperloglog，在满足需求的情况下，它的精度也算是可以的，好，这就是我今天要讲的内容，谢谢大家！本文相关PPT和音视频下载请点击【查看】。

• 本文版权由CHINA HADOOP大数据资讯网与演讲者共同拥有，转载请保留原文来源链接及公众号信息，违者必究。

• China HADOOP Summit 2016 上海站将于7月29日30日在上海市召开，现向业界召集演讲。有兴趣的朋友请联系我们。