如何在 30 分钟内完成数十亿条数据的分析？

1. 受众分析需求及难点

TalkingData 推出的数字化营销平台（Smart Marketing Cloud，以下简称 SMC），提供了一套从人群构建、客群洞察，再到同步投放、客观监测的一体化解决方案，帮助企业构建完整的数字化营销闭环。SMC 服务多个行业的广告主和广告代理，帮助他们对目标受众人群进行分析、洞察和触达。但是由于 SMC 汇集了包括一方企业数据、二方媒体数据和 TalkingData 自有数据在内的多源数据，数据量非常大；此外，为了对受众人群进行全面、深入的画像，TalkingData 基于人口属性、移动端行为偏好等建立了拥有六大类别、800 多个标签的标签体系，维度非常多。这对数据的处理分析提出了巨大的挑战。

在具体使用中，产品性能是企业非常重视的方面。为了提升 SMC 的性能，让用户能够快速、准确的实现目标受众洞察，我们从技术上对 SMC 的受众分析能力进行了三大方面的优化。

2. 使用技术原理及方案：

Bitmap 计算

在 SMC 中，由于数据量巨大，我们对所有广告主构建的受众人群均会使用 RoaringBitmap 进行存储。由于 RoaringBitmap 只能存储整型数据，而我们需要处理的数据量在大多数情况下高达数十亿条，故我们将 RoaringBitmap 进行扩展，使之支持长整型数据。

原生 RoaringBitmap 只支持 int 类型，最大数据存储量为2147483647，由于 TalkingData 设备数据量约 80 亿，已远远超过 RoaringBitmap 的存储范围，所以需要使用长整型来扩展 RoaringBitmap。

以 set(long) 方法为例，寻址方法大概如下代码所示：

**public** **void** **set**(**long** offset) {
**int** index = (**int**) (offset / max());
**int** value = (**int**) (offset % max());
bitmaps.get(index).set(value);
}

扩展之后的 RoaringBitmap，已经获得了比较好的存储和读取速度。但这还只是开始，随后还需要对这些人群数据进行多维度的分析和计算。

RocksDB 加速计算

SMC 的受众分析维度包含：人口属性维度、设备属性维度、商旅属性、App 行为分析等。基于以上维度对某个广告受众人群包进行分析时，需要进行约 10 万次 Bitmap 的交并运算，此时系统 CPU 和 I/O 就成了瓶颈。于是我们采用 RocksDB 进行 Bitmap 的缓存，以减少 I/O 耗时。

RocksDB 依靠大量灵活的配置，使之能针对不同的生产环境进行调优，包括直接使用内存、使用 Flash、使用硬盘或者 HDFS。支持使用不同的压缩算法，并且有一套完整的工具供生产和调试使用。

RocksDB 优势如下：

• 为需要存储 TB 级别数据到本地 FLASH 或者 RAM 的应用服务器设计
• 针对存储在高速设备的中小键值进行优化——支持存储在 flash 或者直接存储在内存
• 性能随 CPU 数量线性提升，对多核系统友好

RocksDB 支持 snappy、zlib、bzip2 lz4 和 lz4_hc 压缩算法。对不同层的数据可以配置不同的压缩算法。一般来说，90% 的数据保存在 Lmax 层。一个典型的安装可能是 L0-L2 层不配置压缩算法，中间层用 snappy 压缩算法，而 Lmax 层采用 zlib 压缩。使用 RocksDB 后，I/O 性能显著提升，原来需要 3 个小时以上才能计算完成的任务，现在缩短到 1.5 小时即可计算完毕。

但这个时间仍然太长，让人无法忍受，于是我们想到对系统数据进行抽样，以加快运算速度。

随机抽样算法

随机抽样是最为常用的算法之一，它最大的特点是能够通过抽取、计算较小的数据样本量，来尽可能客观的推断数据总体特征。

我们需要进行随机抽样且保持有序，当总设备量为 n，需要随机挑选出 m 个设备，其中 m < n。输出是 [0 , n-1] 范围内 m 个随机整数的有序列表，不允许重复。从概率的角度说，我们希望得到没有重复的有序选择，其中每个选择出现的概率相等。简单来说就是从 n 个数中， 随机抽取 m 个数据，并保持有序。

轮流判断 n 个数组成的列表中每个数的概率 (m/n)，每次判断后 n=n-1，若当前被判断的数被选择，则 m=m-1，否则 m 不变。

rac{m}{n} * rac{m-1}{n-1} + rac{n-m}{n} * rac{m}{n-1}= rac{m^2-m+mn-m^2}{n(n-1)}=rac{m}{n}nm​∗n−1m−1​+nn−m​∗n−1m​=n(n−1)m2−m+mn−m2​=nm​

实现方式：

**public** **static** Set<Long> **random**(**long** n,**int** m){
 
Set<Long> set = **new** TreeSet<Long>();
**long** remaining = n-1;
**for** (**long** i = 0; i<n ;i++){
 **if** (Math.random() * remaining < m){
 set.add(i);
 m -= 1;
 }
 remaining -= 1;
}
**return** set;
 
}

我们使用次方法从总设备量中随机抽取受众人群分析样本数据并加工成 Bitmap。我们假设另此 Bitmap 为 A，男性全量数据 M，则计算 X 人群中的男性占比 P 的公式为：

P = rac{A∩M∩X}{X}* 100%P=XA∩M∩X​∗100%

采用随机抽样方式获得的占比结果还是会有一定偏差。经对比 50 组随机构建的受众人群包，对性别占比进行分析，相对误差率均未超过 8%，在可接受范围之内。

经过随机抽样计算之后，Bitmap 数据占用 RocksDB 存储显著减小，Bitmap 计算效率显著提高，数十亿数据量的受众分析任务可在 30 分钟内计算完成。

基于以上这些优化，智能营销云可以快速完成对广告受众的分析，让广告主在整个广告投放过程中及时了解自己的目标受众特点以及分布情况，从而指导广告主及时对广告投放受众群体进行调整。

感谢您耐心看完了文章...

关注作者：JAVA高级程序员。

我会不定期在微头条发放：（Java工程化、分布式架构、高并发、高性能、深入浅出、微服务架构、Spring、MyBatis、Netty、源码分析）等技术学习资料，以及Java进阶学习路线图。

我们总是想得太多，做的太少！