CDP 技术系列(一):使用 bitmap 存储数十亿用户 ID 的标签或群体
一、背景介绍
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的操作来实现。
有了良好的存储方式,下一步就是如何将存储在数据仓库的明细数据,加工成原始的标签或者群体,具体实现方案会在下一篇分享。
作者:京东科技 黎宇飞
来源:京东云开发者社区 转载请注明来源

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
应用监控 eBPF 版:实现高效协议解析的技术探索
作者:彦鸿 引言 随着 Kuberentes 等云原生技术的飞速发展,带来了研发与运维模式的变革。企业软件架构由单体服务向分布式、微服务演进。随着业务发展,多语言、多框架、多协议的微服务在企业中越来越多,软件架构复杂度越来越高,如何快速通过可观测工具快速定位出问题对研发人员至关重要。为满足全场景、端到端的应用监控需求,应用实时监控服务 ARMS 推出应用监控 eBPF 版,通过 eBPF 技术完善整个应用监控体系。应用监控 eBPF 版提供无侵入、语言无关的可观测能力。 详细产品介绍: 多语言应用监控最优选,ARMS 应用监控 eBPF 版正式发布 使用 eBPF 来进行可观测性需要进行应用层协议解析,但云上微服务软件架构中的应用层协议往往比较复杂,这也给协议解析带来了不小的挑战。传统的协议解析方式存在 CPU、内存占用高,错误率高等问题,在应用监控 eBPF 版中,我们提出一种高效的协议解析方案,实现对应用层协议的高效解析。 eBPF 技术简介 eBPF(扩展的 Berkeley 包过滤器)是一种强大的技术,允许开发人员在 Linux 内核中安全地运行预编译的程序,而不改变内核源码或...
- 下一篇
CDP 技术系列(二):ClickHouse+Bitmap 实现海量数据标签及群体组合计算
一、背景介绍 上一篇文章介绍了CDP中,面对单个标签或群体数十亿的数据如何存储 我们都知道数据仓库的概念,它的里边存储了我们所有的数据,其中就包含了标签或群体所依赖的数据,但是这些数据并不能直接拿来使用,想要变成业务需要的标签或群体数据,还需要进行加工。 数据工程师将数仓里的原始数据,经过一些列的数据作业加工成业务用户需要的源表,比如性别表,学历表,年龄表,购买行为表等等。 有了这些相对规整的源表,接下来就是如何利用这些表,去组合成我们需要的群体,然后通过群体再去做营销,推广等。 本篇要讨论的主要就是使用什么方式快速圈选出人群。 二、问题描述 上文已经讲到有了标签的存储方式和源表,并且当前CDP平台已经有几千+标签,2W+群体,这其中涉及到的源表会非常多且大。 我们遇到的第一个问题,是如何将这么多张源表,加工成对应标签的bitmap? 第二个问题,加工好这些bitmap文件之后,存储在什么地方才能方便后续的使用? 第三个问题,存储好这些标签的bitmap之后,如何快速的进行组合计算,加工成用户需要的群体? 比如我有三个标签:学历,年龄和性别,如何圈出:具有本科学历的,年龄在20到...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Mario游戏-低调大师作品
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS8编译安装MySQL8.0.19
- SpringBoot2配置默认Tomcat设置,开启更多高级功能