作者：王福胜
“营销云”(TalkingData MarketingCloud) 是TalkingData发布的新一代广告营销数据管理平台，利用超过40亿移动终端数据的覆盖优势，实现了从人群构建、多维洞察到同步投放、客观监测的一体化解决方案。
TalkingData积累了40多亿移动设备的数据， 并且基于这些数据建立了自己的标签体系。 现有12大类超过800个受众定向标签，包括人口属性，设备属性，位置属性，兴趣，消费特征，安装的应用App等。这些标签关联的设备累加起来超过700亿。 如何利用这些标签为用户提供快速的标签人群构建，对人群进行多维度的快速画像是一个挑战。
标签人群构建是利用TalkingData的标签数据来选择人群， 比如选择男性标签和有车标签计算出有车男性的人群。
人群画像是从不同的维度来描述这个人群，比如某个人群，男性占比为70%，女性为30%， 年龄在19-25岁的比例为75%，使用华为手机的占50%，使用苹果手机的占30%等等。具体的计算就是人群数据和TalkingData各个维度的数据做And运算得出数量的百分比。
用来画像的维度，除了人口属性，设备属性这些标签，还有操作系统，运行商，联网方式，活跃应用App等维度，这些维度的数据量也很巨大。
具体到实现，TalkingData是把收集到的移动设备数据进行了BitMap化处理，利用BitMap的快速And, Or运算能力来做标签人群构建和人群画像。 Bitmap对数据有很好的压缩能力，但是因为TalkingData积累的移动设备数量庞大，生成的Bitmap很多都是几百兆， 用来构建、画像的的Bitmap数据总共大小有几百G。 最开始的实现方案是把生成的Bitmap存在HDFS上，使用Spark集群来做这些运算，但是运算速递，特别是画像速递并不理想。 一个一千万人群的画像，常常需要1个多小时才完成。
RocksDB是一个高性能的KV存储系统，读写性能很优越，使用磁盘做存储。比较适合我们这种Bitmap数量比较多，总数据量大，又需要快速读写的场景。 于是我们开始调研RocksDB, 尝试使用RocksDB来解决人群构建和画像的性能问题。
下面是我们对RockDB的一些调研以及RockDB在我们业务中的使用。
RocksDB
介绍
RocksDB是facebook开源的NOSQL存储系统，其设计是基于Google开源的LevelDB，优化了LevelDB中存在的一些问题，其性能要比LevelDB强，设计与LevelDB极其类似。
LevelDB的开源发起者：Jeff Dean和Sanjay Ghemawat，这两位是Google公司重量级的工程师。
Jeff Dean是Google大规模分布式平台Bigtable和MapReduce主要设计和实现者。
Sanjay Ghemawat是Google大规模分布式平台GFS，Bigtable和MapReduce主要设计和实现工程师。
如果了解Bigtable的话，应该知道在这个影响深远的分布式存储系统中有两个核心的部分：Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作，实际的分布式数据存储以及读写操作是由Tablet Server完成的，而LevelDB则可以理解为一个简化版的Tablet Server。
RocksDB相对传统的关系数据库的一大改进是采用LSM树存储引擎。LSM树是非常有创意的一种数据结构，它和传统的B+树不太一样，下面先说说B+树。
上图是B+树的一个例子。 B+树根节点和枝节点分别记录每个叶子节点的最小值，并用一个指针指向叶子节点。叶子节点里每个键值都指向真正的数据块，每个叶子节点都有前指针和后指针，这是为了做范围查询时，叶子节点间可以直接跳转，从而避免再去回溯至枝和跟节点。
B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。
对于大量的随机写也一样，举一个插入key跨度很大的例子，如7->1000->3->2000 … 新插入的数据存储在磁盘上相隔很远，会产生大量的随机写IO，低下的磁盘寻道速度严重影响性能。
-
LSM
树（Log-Structured Merge Tree）
LSM树而且通过批量存储技术规避磁盘随机写入问题。 LSM树的设计思想非常朴素, 它的原理是把一颗大树拆分成N棵小树， 它首先写入到内存中（内存没有寻道速度的问题，随机写的性能得到大幅提升），在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
1） LevelDB是一个持久化存储的KV系统，和Redis这种内存型的KV系统不同，LevelDB不会像Redis一样狂吃内存，而是将大部分数据存储到磁盘上。
2） LevleDb在存储数据时，是根据记录的key值有序存储的，就是说相邻的key值在存储文件中是依次顺序存储的，而应用可以自定义key大小比较函数。
3） LevelDB支持数据快照（snapshot）功能，使得读取操作不受写操作影响，可以在读操作过程中始终看到一致的数据。
4） LevelDB还支持数据压缩等操作，这对于减小存储空间以及增快IO效率都有直接的帮助。
1) 增加了column family，这样有利于多个不相关的数据集存储在同一个db中，因为不同column family的数据是存储在不同的sst和memtable中，所以一定程度上起到了隔离的作用。
2) 采用了多线程同时进行compaction的方法，优化了compact的速度。
3) 增加了merge operator，优化了modify的效率。
4) 将flush和compaction分开不同的线程池，能有效的加快flush，防止stall。
5) 增加了对write ahead log(WAL)的特殊管理机制，这样就能方便管理WAL文件，因为WAL是binlog文件。
RocksDB的整体结构：
rocksdb从3.0开始支持ColumnFamily的概念。每个columnfamilyl的meltable与sstable都是分开的，所以每一个column family都可以单独配置，所有column family共用同一个WA文件，可以保证跨column family写入时的原子性。
写操作包含两个具体步骤：
1) 首先是将这条KV记录以顺序写的方式追加到log文件末尾，因为尽管这是一个磁盘读写操作，但是文件的顺序追加写入效率是很高的，所以并不会导致写入速度的降低。
2) 第二个步骤是:如果写入log文件成功，那么将这条KV记录插入内存中的Memtable中，Memtable只是一层封装，其内部其实是一个Key有序的SkipList列表，插入一条新记录的过程也很简单，即先查找合适的插入位置，然后修改相应的链接指针将新记录插入即可。完成这一步，写入记录就算完成了，所以一个插入记录操作涉及一次磁盘文件追加写和内存SkipList插入操作，这是为何RocksDB写入速度如此高效的根本原因
删除操作与插入操作相同，区别是，插入操作插入的是Key:Value值，而删除操作插入的是“Key:删除标记”，并不真正去删除记录，而是后台Compaction的时候才去做真正的删除操作。
RocksDB首先会去查看内存中的Memtable，如果Memtable中包含key及其对应的value，则返回value值即可；如果在Memtable没有读到key，则接下来到同样处于内存中的Immutable Memtable中去读取，类似地，如果读到就返回，若是没有读到,那么会从磁盘中的SSTable文件中查找。
总的读取原则是这样的：首先从属于level 0的文件中查找，如果找到则返回对应的value值，如果没有找到那么到level 1中的文件中去找，如此循环往复，直到在某层SSTable文件中找到这个key对应的value为止（或者查到最高level，查找失败，说明整个系统中不存在这个Key)。
相对写操作，读操作处理起来要复杂很多。RocksDB为了提高读取速递，增加了读cache和Bloomfilter。
RocksDB
在营销云中的使用
RocksDB是C++实现的， 但是以JNI的方式提供了Java接口。TalkingData使用的服务基本以Java为主，而且Bitmap也是用的Java实现，使用Java序列化的方式保存在HDFS上的，所以我们编译了Java版的RocksDB, 用它实现了我们的Bitmap服务，以常用的RestFull的方式提供标签人群构建，以及画像服务。
下图是Bitmap Server的结构图:
Bitmap的计算请求通过Bitmap proxy以随机的方式发给Bitmap Rest Service。每台Bitmap server都是对等的，保存一样的数据，提供一样的服务。
如果调用某台Rest Service时失败了， proxy会做标记，并把请求发到另外一台Rest Service上， 等待一定时间(默认30秒)后会把失败的Rest Service标记清除，恢复向它发送请求。 只有所有的Rest Service都不可用了，Bitmap计算请求才会失败。
Bitmap Rest Service可以通过修改配置文件来方便的部署多台，不只是像图中描述的只有两台。
Bitmap Rest Service 层提供多个Bitmap的and, or, xor等操作， 并且把操作结果保存在RocksDB里，用来提供标签构建人群服务。 同时也提供多个Bitmap的and, or, xor的count计算，用来提供画像服务。 RocksDB server的数量也可以通过配置文件来修改。
Rest Service会调用Bitmap server, Bitmap server层调用底层的RocksDB服务，读取Bitmap做计算，并且把计算结果返回。
RocksDB服务实例和Bitmap Server在一台机器上，Bitmap的读取和计算都在一个Java进程内，而且返回的是Bitmap计算的结果，不需要把Bitmap读到client端做计算，减少了网络传输的开销，提高了速递。
对数据的预处理
TalkingData的设备数据虽然已经Bitmap化了，但是数据还是比较大（像应用安装的Bitmap月数据近120G)。 在把这些数据存入RocksDB之前，还是想尽量缩小这些数据的大小。我们对Bitmap数据进行了分析，并且进行了以下的一些处理：
我们分析了某一天的机型数据，大概有1亿2000万个设备， 共有13621个原始机型，但是其中只有一个设备的机型达到4978个，有两个设备的机型1420个。 也就是说只有一两个设备的机型占了总机型的一半，但是数量极少。 而且很多机型是一些像”马蜂窝里面抢的手机”, “雷军刚刚送我的小米NOTE” 等这样的一些值，这些机型基本可以判定为刷机刷出来的， 或者是模拟器。这些数据我们在处理过程中直接丢弃了，不再做后续的处理，大大减少了要处理的Bitmap数量。
另外在分析运营商的Bitmap数据中也发现了类似的现象。我们也把这种设备数量极少但是类别很多的数据丢弃，减少数据的处理量。
TalkingData对收集到的设备做Bitmap化处理时，是对收集到的原始数据直接处理的，像设备机型，原始的机型有1万多个。其实很多原始机型对应的其实是一个机型，标准化之后机型只有2600多个。
移动应用App也是同样的情况，原始的应用App有10万多个，标准化之后只有8000多个。
用户在使用标签构建人群，或者做画像时关心的都是标准的机型。所以在把Bitamp存入RocksDB之前，我们对原始的Bitmap做了标准化处理，这样Bitmap的数量减少了很多，相应的在RocksDB中的key数量也减少了很多，有利于更快的查找读取这些Bitmap，同时在画像时做Bitmap运算的数量也会减少，可以提高画像的速递。
因为在画像时，最终结果取的是相对值，比如人群男性占60%，女性占40%。 只要保持一定的精度，可以对画像使用的Bitmap做抽样。
我们尝试对Bitmap按offset均匀抽取了十分之一的数据, 确保抽样后的Bitmap和原始Bitmap的bit位分布一致。 对各个维度的Bitmap做了抽样之后，我们做了对比测试，测试结果表明使用抽样的Bitmap和使用全量Bitmap做画像的结果非常接近，误差基本在0.1%以下，可以保证画像的准确度。 抽样使Bitmap的大小减少了7倍。
而且画像时，我们通常只关心排名靠前的结果，画像结果展现的条数也有限，所以对设备的系统，运营商，应用APP, 操作系统等用于画像的Bitmap我们按数量做了排序，取数量前300的Bitmap做十分之一抽样。网络，城市和省份的Bitmap数量本来就比较少，我们全保留做十分之一抽样。最终我们建了两个的Bitmap service库，一个是全量的标签库用来做标签构建人群。一个是抽样的标签，机型，运行商和联网方式的库，用来做画像。
因为用来做标签构建和画像的Bitmap都很大，很多都是几百兆，这么巨大的Bitmap在进行and, or等Bitmap运算时会很慢。 所以在存储时，我们把Bitmap按bit位每2亿位分块，对每块做标记，分成0,1,2,..18,19等块，再对这些块的标记按4(或者别的数)取模， 模相同的合成一个Bitmap, 这样就把大的Bitmap拆分成多个相互独立的小Bitmap, 这样在进行and, or等运算时，多个小的Bitmap可以独立进行and,or运算，然后把小Bitmap的运算结果进行合并， 这样增加了Bitmap运算的并行度，加快了运算速度。
Bitmap数据经过预处理，导入到RocksDB，现在通过RocksDB的Bitmap服务选择标签构建人群时，人群的预估数量可以实时算出，构建出人群过程也在几秒钟内完成； 对一千万的人群进行全维度的画像，可以1分钟完成，比之前使用spark集群速递提高了几十倍。
|
