引言

在大数据年代,想要不断提高根据海量数据获取的决议计划、洞悉发现和流程优化等才干,就需求不断考虑,怎么在利用有限的资源完成高效稳定地产出可信且丰厚的数据,从而进步赋能下流产品的效率以及效果。在货拉拉数仓构建过程中,咱们不断探究各种方法来完成降本提效。例如在一些场景下,利用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的简略完成

关于 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);
}

输出成果如下:

货拉拉大数据对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);
}

输出成果如下:

货拉拉大数据对BitMap的探索与实践上

BitSet源码了解

前面简略了解了一下BitMap,下面就经过源码来看看java是怎么完成BitSet的。

补白信息

翻开源码,首要映入眼帘的是下面这一段长长的补白,简略翻译一下,便于英语欠好的小伙伴了解

货拉拉大数据对BitMap的探索与实践上

源码补白翻译如下

  1. 这个类完成了一个根据需求增加的位向量。位集的每个组件都有一个布尔值。BitSet的位由非负整数索引。能够检查、设置或铲除单个索引位。一个位集可用于经过逻辑AND、逻辑inclusive OR和逻辑exclusive OR操作修正另一个位集的内容。
  2. 默许状况下,调会集的一切位最初的值都为false。
  3. 每个BitSet都有一个当时巨细,即BitSet当时运用的空间位数。请注意,巨细与BitSet的完成有关,因此它或许会跟着完成而改变。BitSet的长度与BitSet的逻辑长度有关,而且与完成无关。
  4. 除非另有说明,否则将null参数传递给位会集的任何方法都将导致NullPointerException。
  5. 假如没有外部同步,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的几个首要原因:

  1. 针对海量数据的存储,能够极大的节约存储成本!当需求存储一些很大,且无序,不重复的整数调集,那运用Bitmap的存储成本是十分低的。
  2. 因为其天然去重的特色,关于需求去重存储的数据很友爱!因为bitmap每个值都只对应仅有的一个方位,不能存储两个值,所以Bitmap结构天然合适做去重操作。
  3. 同样因为其下标的存在,能够快速定位数据!比方想判别数字 99999是否存在于该bitmap中,若是运用传统的调集型存储,那就要逐一遍历每个元素进行判别,时刻复杂度为O(N)。而因为选用Bitmap存储,只需检查对应的下标数的值是0还是1即可,时刻复杂度为O(1)。所以运用bitmap能够十分便利快速的查询某个数据是否在bitmap中。
  4. 还有因为其类调集的特性,关于一些调集的交并集等操作也能够支撑!比方想查询[1,2,3]与[3,4,5] 两个调集的交集,用传统方法取交集就要两层循环遍历。而Bitmap完成的底层原理,便是把01110000和00011100进行与操作就行了。而核算机做与、或、非、异或等等操作是十分快的。

尽管bitmap有诸多好处,可是正所谓人无完人,它也存在许多缺陷。

  1. 只能存储正整数而不能是其他的类型;
  2. 不合适存储稀少的调集,简略了解,一个调集寄存了两个数[1,99999999],那用bitmap存储的话就很不划算,这也与它本来节约存储的优点也背离了;
  3. 不适用于存储重复的数据

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。

如下图所示

货拉拉大数据对BitMap的探索与实践上

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个时,占用4096×2 = 8196byte 也便是8kb,而id数最大是65536,占用 65536×2 =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的选择:

货拉拉大数据对BitMap的探索与实践上

如图所示,能够看到ArrayContainer 更合适寄存稀少的数据,BitmapContainer 合适寄存稠密的数据。在RoaringBitmap中,若一个 Container 里边的元素数量小于 4096,会运用 ArrayContainer 来存储。当 Array Container 超越最大容量 4096 时,会转换为 BitmapContainer,这样能够最大化的优化存储。

how

bitmap就像一柄双刃剑,用的好能够协助咱们破除瓶颈,处理痛点。用的欠好不只会丢失它一切的优点,还要搭上过多的存储,甚至会丧失掉最重要的准确性,所以要针对不同事务场景灵敏运用咱们的武器,才干事半功倍!

下面举例bitmap的一些运用场景,来看看实践开发中,究竟怎么正确运用bitmap:

BitMap在用户分群的运用

假设有用户的标签宽表,对应字段及值如下

user_id(用户id) city_id(城市id) is_user_start(是否发动) is_evl(是否评价) is_order(是否下单)
1 1001 1 1 1
2 1001 1 1 0
3 1002 1 1 1
4 1002 1 0 0
5 1003 0 0 0

假如想根据标签区分人群,比方:1001城市 + 下单。

传统处理方案

一般是对列值进行遍历筛选,假如优化也便是列上建立索引,可是当这张表有许多标签列时,假如要索引收效并不是每列有索引就行,要每种查询组合建一个索引才干收效,索引数量相当于标签列排列组合的个数,当标签列有1、2 k 的时分,这根本便是不或许的。一般的做法是在数仓提前将热点的组合聚合过滤成新字段,或许只对热点组合加索引,但这样都很不灵敏。

运用BitMap的方案

经过选用bitmap的方法,按字段重组成Bitmap。

标签 标签值 bitmap字段底层二进制结构
city_id(城市id) 1001 00000110
city_id(城市id) 1002 00011000
city_id(城市id) 1003 00100000
is_user_start(是否发动) 1 00011110
is_user_start(是否发动) 0 00100000
is_evl(是否评价) 1 00001110
is_evl(是否评价) 0 00110000
is_order(是否下单) 1 00001010
is_order(是否下单) 0 00110100

把数据调整成这样的结构,再进行条件组合,那就简略了。比方: 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的常见运用场景。期望我们读后都能有所收成。

笔者介绍:黄雪超|高级数据仓库工程师。现任职于货拉拉数据财物组,首要负责用户、营销以及AB域的数仓构建,对数仓架构设计、落地、调优以及管理有丰厚实战经历。