写点什么

CDP 技术系列(一):使用 bitmap 存储数十亿用户 ID 的标签或群体

  • 2024-01-24
    北京
  • 本文字数:2734 字

    阅读完需:约 9 分钟

一、背景介绍

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 的操作来实现。


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


作者:京东科技 黎宇飞


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

用户头像

拥抱技术,与开发者携手创造未来! 2018-11-20 加入

我们将持续为人工智能、大数据、云计算、物联网等相关领域的开发者,提供技术干货、行业技术内容、技术落地实践等文章内容。京东云开发者社区官方网站【https://developer.jdcloud.com/】,欢迎大家来玩

评论

发布
暂无评论
CDP技术系列(一):使用bitmap存储数十亿用户ID的标签或群体_京东科技开发者_InfoQ写作社区