一、背景介绍

CDP 系统中目前存在大量由用户 ID 集合组成的标签和群体，截止当前已有几千 + 标签，群体 2W+。

大量的标签都是亿级别数据量以上，例如性别、职业、学历等均，甚至有群体中的 ID 数量达到了数十亿 +。

并且随着用户 ID 池的不断增加，标签和群体本身包含的 ID 数量也随之增加，如何存储如此多的数据，标签与群体之间的组合计算，是我们面临的挑战。

二、问题描述

如此大量的用户 ID 集合，虽然标签和群体的 ID 集合本质类似，但是都需要存储亿级别的 ID 数据，这就对存储结构提出较高的要求。

这里拿群体举例，如果某群体包含 1000W 个用户 ID，通过文本文件存储，大概需要 150M，40 亿的群体就达到了惊人的 150*40*10=60000M，大约 60G，而我们的群体数量已经达到了几 W+，再加上标签数据，所需要的存储空间将不可接受。

并且，数据的存储只是其中一个方面，后续针对标签和群体的组合计算，创建出更细粒度的 ID 包也是一个挑战。

三、解决方案

面对以上问题，CDP 采用了 Bitmap 的思路来解决，不但解决了存储空间问题，而且 Bitmap 本身的交并差运算，能够很好的支持用户对不同标签和群体的组合计算，详细方案如下。

1）Bitmap 简介

为了便于理解，首先介绍一下什么是 bitmap。

它的基本思想是用 bit 位来唯一标记某个数值，这样可以用它来记录一个数值没有重复的数据元组。并且每一条数据只使用一个 bit 来标识，能够大大的节省存储空间。

比如，我想存储一个数值数组 [2,4,6,8]。

Java 中如果用 byte 类型来存储，不考虑其他开销，需要 4 个字节的空间，一个字节 8 位，也就是 4*8=32bit。

倘若使用更大的数据类型，存储空间也会相应增大，如使用 Integer（4 字节），则需要 4*4*8=128bit。

而如果采用 bitmap 的思想，只需要构建一个 8bit 空间，也就是一个字节的空间来存储，如下图。

2）用户 ID 池编码

通过上文的例子，可以看到，使用 Bitmap 思想来存储，实际上每一个数据是一个 bit，而且不能重复，这一点用户 ID 是符合的，没有重复的用户 ID。

由于 bitmap 里只能存 0 或者 1 来标识当前位是否有值，而用户 ID 确是一个字符串，这就需要将数十亿的用户 ID 进行唯一性编码，这个编码也就是我们常说的 offset 偏移量。

每一个用户 ID 对应一个唯一的 offset，目前已到数十亿，也就是说当前最大的偏移量是数十亿 +，这部分由数据同学帮我们加工一张 ID 池表，其中包含了 ID 和 offset 的对应关系。这样，新注册的 id，只要顺序增加 offset 值即可。

下边是一个简单示意图，假设我有 8 个 id，id1~id8，对应的 offset 编号为 1~8。

我要建一个只包含双数 id 的标签或群体，则我只需要将 offset 为 2，4，6，8 的位设为 1 即可。

3）遇到问题

有了存储的数据结构，还有 id 池，接下来就是具体实现了。

提到 Bitmap，首先想到的是Java 中的一种实现方案 BitSet，不过它存在两个问题。

一是我们的 id 池已经到达几十亿 +，已经超出了 BitSet 所能处理的范围，当前超出了 2^{32=4294967296}。

另一个问题是，倘若我建一个包含两个 id 的群体，第一个 offset 是 1，第二个 offset 是 10000000，这种情况还是要创建一个 1000wbit 的空间来存储，并且只有两个 bit 位是 1，其他的全为 0，这显然造成了很大的空间浪费。

也就是说，数据越稀疏，空间浪费越严重

下方位 BitSet 扩容时的代码，由代码中也可以看到，默认扩容 2 倍，当需要的大小超过 2 倍时，则按照需要扩容。

public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();
}

private void expandTo(int wordIndex) {
    int wordsRequired = wordIndex+1;
    if (wordsInUse < wordsRequired) {
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;
    }
}

private void ensureCapacity(int wordsRequired) {
    if (words.length < wordsRequired) {
        // Allocate larger of doubled size or required size
        int request = Math.max(2 * words.length, wordsRequired);
        words = Arrays.copyOf(words, request);
        sizeIsSticky = false;
    }
}

当用户圈的群体特别稀疏时，有可能会造成很大的空间浪费，所以，我们需要使用一种能够压缩的高效的位图实现。

4）RoaringBitmap 压缩

我们最终使用的是 RoaringBitmap，一种高效的压缩位图实现，简称 RBM。于 2016 年由 S. Chambi、D. Lemire、O. Kaser 等人在论文《Better bitmap performance with Roaring bitmaps》 《Consistently faster and smaller compressed bitmaps with Roaring》中提出。

基本实现思路如下：

以整型 int（32 位）为例，将数据分成高 16 位和低 16 位两部分，低 16 位不变，作为数据位 Container，高 16 位作为桶的编号 Container，可以理解为高位的 Container 中，存放了很多个低位 Container。

高低位计算示例：

protected static char highbits(int x) {
  return (char) (x >>> 16);
}

protected static char lowbits(int x) {
  return (char) x;
}

比如，我要存放 65538 这个值，则高位为 65538>>>16=1，低位为 65538-65536*1=2，即存储在 1 号桶的 2 号位置，存储位置如下图：

我们当前使用的 RoaringBitmap 版本为 0.8.13，Container 包含了三种实现：ArrayContainer(数组容器)，BitmapContainer(位图容器)，RunContainer(行程步长容器)

不过，上文中提到当前 id 池已经超过了整型所能标识的最大范围（2^{32=4294967296），所以需要一个能够处理 64 位的实现，我们使用了 RoaringBitmap 包中支持 64 位的 Roaring64NavigableMap。}

它的实现思路和 32 位的基本一致，分成了高 32 位和低 32 位两部分

jar 包引入方式：

<dependency>
     <groupId>org.roaringbitmap</groupId>
     <artifactId>RoaringBitmap</artifactId>
     <version>0.8.13</version>
</dependency>

public void add(long... dat) {
    for (long oneLong : dat) {
      addLong(oneLong);
    }
 }

public void addLong(long x) {
  int high = high(x);
  int low = low(x);
  …………
}

public static int high(long id) {
  return (int) (id >> 32);
}

public static int low(long id) {
  return (int) id;
}

bitmap 位图操作方法：

四、现状及展望

目前，CDP 画像的标签和群体均采用了 RoaringBitmap 的存储方式。人群和标签的交并差计算，生成更加精细化的人群就可以通过 bitmap 的操作来实现。

有了良好的存储方式，下一步就是如何将存储在数据仓库的明细数据，加工成原始的标签或者群体，具体实现方案会在下一篇分享。

作者：京东科技 黎宇飞

来源：京东云开发者社区 转载请注明来源