目录
- 关于Bitmap
- What
- BitMap的简单实现
- BitSet源码理解
- 备注信息
- 核心片段理解
- Why
- BitMap的特点
- BitMap的优化
- RoaringBitmap的核心原理
- how
- BitMap在用户分群的应用
- 传统解决方案
- 使用BitMap的方案
- BitMap在A/B实验平台业务的应用
- 结语
关于Bitmap
在大数据时代,想要不断提升基于海量数据获取的决策、洞察发现和流程优化等能力,就需要不停思考,如何在利用有限的资源实现高效稳定地产出可信且丰富的数据,从而提高赋能下游产品的效率以及效果。在货拉拉数仓构建过程中,我们不断探索各种方式来实现降本提效。例如在一些场景下,利用Bitmap去提升下游的数据使用体验,并达成我们想要的降本提效的目的。
为了更好的展示Bitmap在货拉拉实践应用中的探索与实践,我们分了两篇文章来介绍,本文主要介绍Bitmap的实现原理与应用优化,以及在一些常见业务场景中的实践应用,让大家在面对相应场景的时候,能够有一个区别于传统的解决方案的新思路。下一篇文章则是重点介绍Bitmap在货拉拉中的具体落地,以及使用时遇到的一些痛点和对应解决方案。
首先从Bitmap开始说起,这里采用经典的WWH结构,让不熟悉的小伙伴能够快速了解掌握。
What
BitMap,即位图,是比较常见的数据结构,简单来说就是按位存储,主要为了解决在去重场景里面大数据量存储的问题。本质其实就是哈希表的一种应用实现,使用每个位来表示某个数字。
举个例子
假设有个1,3,5,7的数字集合,如果常规的存储方法,要用4个Int的空间。其中一个Int就是32位的空间。3个就是4*32Bit,相当于16个字节。
如果用Bitmap存储呢,只用8Bit(1个字节)就够了。bitmap通过使用每一bit位代表一个数,位号就是数值,1标识有,0标识无。如下所示:
BitMap的简单实现
对于 BitMap 这种经典的数据结构,在 Java 语言里面,其实已经有对应实现的数据结构类 java.util.BitSet 了,而 BitSet 的底层原理,其实就是用 long 类型的数组来存储元素,因为使用的是long类型的数组,而 1 long = 64 bit,所以数据大小会是64的整数倍。这样看可能很难理解,下面参考bitmap源码写了一个例子,并写上了详细的备注,方便理解
import java.util.Arrays; public class BitMap { // 用 byte 数组存储数据 private byte[] bits; // 指定 bitMap的长度 private int bitSize; // bitmap构造器 public BitMap(int bitSize) { this.bitSize = (bitSize >> 3) + 1; //1byte 能存储8个数据,那么要存储 bitSize的长度需要多少个bit呢,bitSize/8+1,右移3位相当于除以8 bits = new byte[(bitSize >> 3) + 1]; } // 在bitmap中插入数字 public void add(int num) { // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。 bits[arrayIndex] |= 1 << position; } // 判断bitmap中是否包含某数字 public boolean contain(int num) { // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可 return (bits[arrayIndex] & (1 << position)) != 0; } // 清除bitmap中的某个数字 public void clear(int num) { // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后,那个位置自然就是1,然后对取反,再与当前值做&,即可清除当前的位置了. bits[arrayIndex] &= ~(1 << position); } // 打印底层bit存储 public static void printBit(BitMap bitMap) { int index=bitMap.bitSize & 0x07; for (int j = 0; j < index; j++) { System.out.print("byte["+j+"] 的底层存储:"); byte num = bitMap.bits[j]; for (int i = 7; i >= 0; i--) { System.out.print((num & (1 << i)) == 0 ? "0" : "1"); } System.out.println(); } } // 输出数组元素,也可以使用Arrays的toString方法 private static void printArray(int[] arr) { System.out.print("数组元素:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println(); } }
下面就来简单玩一玩这个自制的BitMap,先尝试插入一个3,并清理掉它,看看底层二进制结构是怎样变化的
public static void main(String[] args) { // 简单试验 BitMap bitmap = new BitMap(3); bitmap.add(3); System.out.println("插入3成功"); boolean isexsit = bitmap.contain(3); System.out.println("3是否存在:" + isexsit); printBit(bitmap); bitmap.clear(3); isexsit = bitmap.contain(3); System.out.println("3是否存在:" + isexsit); printBit(bitmap); }
输出结果如下:
再通过数组,插入多个元素看看效果
public static void main(String[] args) { // 数组试验 int[] arr = {8,3,3,4,9}; printArray(arr); int size = Arrays.stream(arr).max().getAsInt(); BitMap b = new BitMap(size); for (int i = 0; i < arr.length; i++) { b.add(arr[i]); } printBit(b); }
输出结果如下:
BitSet源码理解
前面简单了解了一下BitMap,下面就通过源码来看看java是如何实现BitSet的。
备注信息
打开源码,首先映入眼帘的是下面这一段长长的备注,简单翻译一下,便于英语不好的小伙伴理解
源码备注翻译如下
- 这个类实现了一个根据需要增长的位向量。位集的每个组件都有一个布尔值。BitSet的位由非负整数索引。可以检查、设置或清除单个索引位。一个位集可用于通过逻辑AND、逻辑inclusive OR和逻辑exclusive OR操作修改另一个位集的内容。
- 默认情况下,集合中的所有位最初的值都为false。
- 每个BitSet都有一个当前大小,即BitSet当前使用的空间位数。请注意,大小与BitSet的实现有关,因此它可能会随着实现而改变。BitSet的长度与BitSet的逻辑长度有关,并且与实现无关。
- 除非另有说明,否则将null参数传递给位集中的任何方法都将导致NullPointerException。
- 如果没有外部同步,BitSet对于多线程使用是不安全的。
核心片段理解
首先可以看到源码中,最核心的属性信息。在BitSet 中使用的是long[] 作为底层存储的数据结构,并通过一个 int 类型的变量,来记录当前已经使用数组元素的个数。
这种类型的属性结构很常见,比如StringBuilder、StringBuffer底层是一个char[] 作为存储,一个int 变量用来计数,相似的还有ArrayList,Vector等
/** * The internal field corresponding to the serialField "bits". */ private long[] words; /** * The number of words in the logical size of this BitSet. */ private transient int wordsInUse = 0;
再往下看,是一个很重要的方法,是用来获取某个数在数组中的下标,采用的算法是将这个数右移6位,这是因为 bitIndex >> 6 = bitIndex / (2^6) = bitIndex /64,而long就是64个字节
private final static int ADDRESS_BITS_PER_WORD = 6; /** * Given a bit index, return word index containing it. */ private static int wordIndex(int bitIndex) { return bitIndex >> ADDRESS_BITS_PER_WORD; }
接着比较有意思的就是它的空参构造器,BITS_PER_WORD默认是1<<6 也就是64,根据上面方法原理,wordIndex(64-1)+1 = 1 ,所以最终初始化的是长度为1的数组
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; /** * Creates a new bit set. All bits are initially { @code false}. */ public BitSet() { initWords(BITS_PER_WORD); sizeIsSticky = false; } private void initWords(int nbits) { words = new long[wordIndex(nbits-1) + 1]; }
最后看到这个很经典也很重要的方法,由于底层是数组,在初始化的时候,并不知道将来会需要存储多大的数据,所以对于这一类底层核心实现结构是数组的实体类,通常会使用动态扩容的方法,具体实现细节也都大同小异,这里实现的动态扩容是原本的两倍,和Vector类似。
/** * Ensures that the BitSet can hold enough words. * @param wordsRequired the minimum acceptable number of words. */ 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); // 创建新的数组,容量为request,然后将原本的数组拷贝到新的数组中 words = Arrays.copyOf(words, request); // 并设置数组大小不固定 sizeIsSticky = false; } }
至于其他的源码细节,因为篇幅有限,就暂且不表,感兴趣的可以自行阅读~
Why
BitMap的特点
根据bitmap的实现原理,其实可以总结出使用bitmap的几个主要原因:
- 针对海量数据的存储,可以极大的节约存储成本!当需要存储一些很大,且无序,不重复的整数集合,那使用Bitmap的存储成本是非常低的。
- 因为其天然去重的属性,对于需要去重存储的数据很友好!因为bitmap每个值都只对应唯一的一个位置,不能存储两个值,所以Bitmap结构天然适合做去重操作。
- 同样因为其下标的存在,可以快速定位数据!比如想判断数字 99999是否存在于该bitmap中,若是使用传统的集合型存储,那就要逐个遍历每个元素进行判断,时间复杂度为O(N)。而由于采用Bitmap存储,只要查看对应的下标数的值是0还是1即可,时间复杂度为O(1)。所以使用bitmap可以非常方便快速的查询某个数据是否在bitmap中。
- 还有因为其类集合的特性,对于一些集合的交并集等操作也可以支持!比如想查询[1,2,3]与[3,4,5] 两个集合的交集,用传统方式取交集就要两层循环遍历。而Bitmap实现的底层原理,就是把01110000和00011100进行与操作就行了。而计算机做与、或、非、异或等等操作是非常快的。
虽然bitmap有诸多好处,但是正所谓人无完人,它也存在很多缺陷。
- 只能存储正整数而不能是其他的类型;
- 不适合存储稀疏的集合,简单理解,一个集合存放了两个数[1,99999999],那用bitmap存储的话就很不划算,这也与它本来节约存储的优点也背离了;
- 不适用于存储重复的数据。
BitMap的优化
既然bitmap的优点如此突出,那应该如何去优化它存在的一些局限呢?
- 针对存储非正整数的类型,如字符串类型的,可以考虑将字符串类型的数据利用类似hash的方法,映射成整数的形式来使用bitmap,但是这个方法会有hash冲突的问题,解决这个可以优化hash方法,采用多重hash来解决,但是根据经验,这个效果都不太好,通常的做法就是针对字符串建立映射表的方式。
- 针对bitmap的优化最核心的还是对于其存储成本的优化,毕竟大数据领域里面,大多数时候数据都是稀疏数据,而我们又经常需要使用到bitmap的特长,比如去重等属性,所以存在一些进一步的优化,比较知名的有WAH、EWAH、RoaringBitmap等,其中性能最好并且应用最为广泛的当属RoaringBitmap
RoaringBitmap的核心原理
为了快速把这个原理说清楚,这里就不继续撸源码了,有兴趣的小伙伴可以自行搜索相关源码阅读,下面简单阐述一下它的核心原理:1个Int 类型相当于有32 bit 也就相当于2^32=2^16 x 2^16,这意味着任意一个Int 类型可以拆分成两个16bit的来存储,每一个拆出来的都不会大于2^16, 2^16就是65536,而Int的正整数实际最大值为 2147483647。而RoaringBitmap的压缩首先做的就是用原本的数去除65536,结果表示成(商,余数),其中商和余数是都不会超过65536。
如下图所示
RoaringBitmap的做法就是将131138 原本32bit的存储结构,拆分成连两个16bit的结构,而拆分出的两个16bit分别存储了131138除65536的商2以及余数66。
在RoaringBitmap中,把商所处的16bit 被称为高16位,除数所处的16bit 被称为低16位。并用key和Container去存储的这些拆分出来的数据,其中key是short[] ,存放的就是商,因为bitmap的特性,商和余数不会存在完全相同的情况。
通过商来作为key划分不同的Container,就类似划分不同的桶,key就是标识数据应该存在哪个桶,container用来存对应数据的低16位的数字。比如 1000和60666 除以65536后的结果分别是(0,1000)和(0,60666),所以这两个数据存储到RoaringBitmap中,就会都放到key位0那个container中,container中就是1000和60666。
由于container中存放的数字是0~65536的一些数据,可能稀疏可能稠密,所以RoaringBitmap依据不同的场景,提供了 3 种不同的 Container,分别是 ArrayContainer 、 BitmapContainer 、RunContainer。
关于三个Container的存储原理如下:
- ArrayContainer 存储的方式就是 shot类型的数组, 每个数字占16bit 也就是2Byte,当id 数达到4096个时,占用4096x2 = 8196byte 也就是8kb,而id数最大是65536,占用 65536x2 =131072 byte 也就是128kb。
- BitmapContainer存储的方式就是bitmap类型,bitmap的位数为 65536,能存储0~65535个数字,占用 65536/8/1024=8kb,也就是bitmap container占用空间恒定为8kb。
- RunContainer存储的必须是连续的数字,比如存储1,2,3...100w,RunContainer就只会存储[1,100w]也就是开头和结尾的一个数字,其压缩效率取决于连续的数字有多长。
关于ArrayContainer和BitmapContainer的选择:
如图所示,可以看到ArrayContainer 更适合存放稀疏的数据,BitmapContainer 适合存放稠密的数据。在RoaringBitmap中,若一个 Container 里面的元素数量小于 4096,会使用 ArrayContainer 来存储。当 Array Container 超过最大容量 4096 时,会转换为 BitmapContainer,这样能够最大化的优化存储。
how
bitmap就像一柄双刃剑,用的好可以帮助我们破除瓶颈,解决痛点。用的不好不仅会丢失它所有的优点,还要搭上过多的存储,甚至会丧失掉最重要的准确性,所以要针对不同业务场景灵活使用我们的武器,才能事半功倍!
下面举例bitmap的一些使用场景,来看看实际开发中,到底怎么正确使用bitmap:
BitMap在用户分群的应用
假设有用户的标签宽表,对应字段及值如下
如果想根据标签划分人群,比如:1001城市 + 下单。
传统解决方案
通常是对列值进行遍历筛选,如果优化也就是列上建立索引,但是当这张表有很多标签列时,如果要索引生效并不是每列有索引就行,要每种查询组合建一个索引才能生效,索引数量相当于标签列排列组合的个数,当标签列有1、2 k 的时候,这基本就是不可能的。通常的做法是在数仓提前将热点的组合聚合过滤成新字段,或者只对热点组合加索引,但这样都很不灵活。
使用BitMap的方案
通过采用bitmap的办法,按字段重组成Bitmap。
把数据调整成这样的结构,再进行条件组合,那就简单了。比如: 1001城市 + 下单 = Bitmap[00000110] & Bitmap[00001010]= 1 ,这个计算速度相比宽表条件筛选是快很多的,如果数据是比较稠密的,bitmap可以极大的节省底层存储,如果数据比较稀疏,可以采用RoaringBitmap来优化。
BitMap在A/B实验平台业务的应用
在支持货拉拉A/B实验平台业务的场景中,会有一个实验对应很多司机的情况,因为要在数仓处理成明细宽表,来支持OLAP引擎的使用,随着维度的增多,数据发散的情况变得很严重,数仓及OLAP的存储与计算资源都消耗巨大。为了解决这个痛点,在架构组同事建议下,引入了BitMap,将组装好的司机id数组转换成RoaringBitmap格式,再传入到OLAP引擎里面使用。
在数仓应用层,由于引入了BitMap,重构了原本的数据表结构及链路,并优化了数仓的分层。不仅让整个链路耗时缩短了2个多小时,还节省了后续往OLAP引擎导数的时间,再算上数仓层的计算与存储资源的节省,很完美的实现了降本增效!而在OLAP引擎层,由架构组的同事通过二次开发,支持了Bitmap的使用,也取得了很不错的效果。
具体的落地与应用则在下篇文章给大家详细分享。
结语
本文首先通过对于BitMap的简单实现以及对于Java中BitSet源码的分析,提升读者对于其底层原理的理解,然后分析了BitMap的特点,并针对其存储优化的方案,讲解了RoaringBitmap技术的原理,最后列举了对于BitMap的常见使用场景。希望大家读后都能有所收获。
更多关于货拉拉BitMap大数据的资料请关注自由互联其它相关文章!