深入简出的掌握BitMap

爱被打了一巴掌 2022-05-08 09:04 216阅读 0赞

Bitmap作为被各种框架广泛引用的一门技术，它的原理其实很简单。bit即比特，而Bitmap则是通过bit位来标识某个元素对应的值（支持 0、1 两种状态），简单而言，Bitmap 本身就是一个 bit 数组。

**目录**

1.特性

高性能

存储空间小

2.适用场景

3.局限性

4.实现一个吧

开源利器组件-RoaringBitmap

5.发展需要

6.相关开源应用

Redis

HBase

RocksDB

PalDB

美图团队-Naix

总结

--------------------

# 1.特性 #

## 高性能 ##

Bitmap在其主战场的**计算性能**相当惊人。  
以某 APP 数据为基准进行了简单的留存计算（即统计新增用户在次日依然活跃的用户数量），通过 Hive（基于4节点的 Hadoop 集群，采用 left out join）耗时139秒左右)，而Bitmap（交集计算）仅需226毫秒。

## 存储空间小 ##

由于Bitmap是通过bit位来标识状态，数据**高度压缩**故占用存储空间极小。  
假设有10 亿活跃设备 ID（数值类型），若使用常规的 Int 数组存储大概需 3.72G，而 Bitmap 仅需 110M 左右。  
当然，若要进行去重、排序等操作，存储空间的节省带来的性能红利（如内存消耗等）也非常可观。

# 2.适用场景 #

*  海量数据下Top n问题，比如从10亿个数中找出最大的10000个数
 *  海量数据下是否存在问题，比如查看会员体系下某用户当天是否登录系统或统计登录情况

# 3.局限性 #

*  数据标识列识合法性，它最好是个int/long数字（string也不是不可以，多一次hash风险也存在），带小数点及负数就不太好处理了
 *  数据标识列范围确定性，初始化最好是给定一个合理范围值（最大值），如果数据识列比较稀疏，要考虑是否存在浪费存储空间
 *  java中最小的存储单位是byte，没有bit类型，需要拓展及大量bit处理逻辑

# 4.实现一个吧 #

/**
     * 这里，先实现一个位数组的数据结构
     */
    public static class BitArr {
        private int bitLength = 0;
        private byte[] bytes;
        public byte[] getBytes() {
            return bytes;
        }
        /**
         * 构建多少位的位数组
         * @param bitLength 位长
         */
        public BitArr(int bitLength) {
            this.bitLength = bitLength;
            bytes = new byte[(int) Math.ceil((double) bitLength/7)];
        }
        /**
         * 标记某一个位
         * 设置为1
         * @param position 位
         */
        public void mark(int position) {
            if (position>bitLength)
                return;
            int arrIndex = position/7;
            int bitIndex = position%7;
            bytes[arrIndex] |= (1 << (6-bitIndex));
        }
        public void cleanMark(int position) {
            if (position>bitLength)
                return;
            int arrIndex = position/7;
            int bitIndex = position%7;
            bytes[arrIndex] &= ~(1 << (6-bitIndex));
        }
        public void printAllBit() {
            for (byte aByte : bytes) {
                System.out.print(BitArr.Byte2String(aByte));
            }
            System.out.println();
        }
        /**
         * 打印除符号位的bit
         * @param nByte
         * @return
         */
        private static String Byte2String(byte nByte){
            StringBuilder nStr=new StringBuilder();
            for(int i=6;i>=0;i--) {
                int j=(int)nByte & (int)(Math.pow(2, (double)i));
                if(j>0){
                    nStr.append("1");
                }else {
                    nStr.append("0");
                }
            }
            return nStr.toString();
        }
    }
    public static int[] bitmapSort(int[] arr, int theMax) {
        if (arr==null || arr.length==0)
            return null;
        BitArr bitArr = new BitArr(theMax+1);
        for (int anArr : arr) {
            bitArr.mark(anArr);
        }
        int[] result = new int[arr.length];
        byte[] bytes = bitArr.getBytes();
        int index = 0;
        for (int i = 0; i < bytes.length; i++) {
            //java里面没有无符号的类型，所以我们只能用byte的前7位
            for (int j = 0; j < 7; j++) {
                byte temp = (byte) (1<<6-j);
                byte b = (byte) (bytes[i] & temp);
                if ( b == temp) {
                    result[index++] = i*7 + j;
                }
            }
        }
        return result;
    }
    //验证
    public static void main(String[] args) {
        int[] a = {4,7,2,5,14,3,8,12};
        int[] end = bitmapSort(a, 14);
        for (int x : end) {
            System.out.print(x+",");
        }
    }
    //输出：2,3,4,5,7,8,12,14,

## 开源利器组件-RoaringBitmap ##

这个类库（更高效的压缩算法）被用到了spark、hive、kylin、druid。。。等大数据解决方案中。

[github][]

# 5.发展需要 #

什么样背景下产生的呢？当然还是业务发展的形态所致：海量数据和需求（单机怎么行啊），

*  **百 T 级 Bitmap 索引**。这是单个节点难以维护的量级，通常情况下需要借助外部存储或自研一套分布式数据存储来解决；
 *  **序列化和反序列化问题**。虽然 Bitmap 存储空间占用小、计算快，但使用外部存储时，对于大型 Bitmap 单个文件经压缩后仍可达几百兆甚至更多，存在非常大的优化空间。另外，存储及查询反序列化数据也是非常耗时的；
 *  **如何在分布式 Bitmap 存储上比较好的去做多维度的交叉计算**，以及如何在高并发的查询场景做到**快速的响应**

# 6.相关开源应用 #

## **Redis** ##

Redis 本身支持 bitset 操作，但其实现效果达不到期望。假设进行简单的 Bitmap 数据 kv 存储，以 200T 的数据容量为例，每台机器为 256G，保留一个副本备份，大概需要 160 台服务器，随着业务量的增长，成本也会逐步递增；

## **HBase** ##

在美图大数据，HBase 的使用场景非常多。若采用 HBase 存储 Bitmap 数据，在读写性能上优化空间不大，且对 HBase 的依赖过重，很难达到预期的效果；

## **RocksDB** ##

RocksDB 目前在业界的使用较为普遍。经测试，RocksDB 在开启压缩的场景下，CPU 和磁盘占用会由于压缩导致不稳定；

而在不开启压缩的场景下，RocksDB 在数据量上涨时性能衰减严重，同时多DB的使用上性能并没有提升；

## **PalDB** ##

PalDB 是 linkedin 开发的只读 kv 存储，在官方测试性能是 RocksDB 和 LevelDB 的 8 倍左右，当数据量达某个量级。PalDB 的性能甚至比 java 内置的 HashSet、HashMap 性能更优。

## **美图团队-Naix** ##

上面的解决方案都比较限性，看之前他们的分享专门开发过这个系统，但目前没有开源，

![70][]

**外部调用层**

外部调用层分为 generator 和 tcp client。generator 是负责生成 Bitmap 的工具，原始数据、常规数据通常存储在 HDFS 或者其他存储介质中，需要通过 generator 节点将对应的文本数据或其他数据转化成 Bitmap 相关的数据，然后再同步到系统中。tcp client 主要负责客户端应用与分布式系统的交互。

**核心节点层**

核心节点层主要包含三种：

*  Master 节点，即 Naix 的核心，主要是对集群进行相关的管理和维护，如添加 Bitmap、节点管理等操作；
 *  Transport 节点是查询操作的中间节点，在接收到查询相关的请求后，由 Transport 对其进行分发；
 *  Data Nodes（Naix中最核心的数据存储节点），我们采用 Paldb 作为 Bitmap 的基础数据存储。

**依赖的外部存储层**

Naix 对于外部存储有轻量级的、依赖，其中 mysql 主要用于对元数据进行管理，并维护调度中间状态、数据存储等，而 redis 更多的是作为计算过程中的缓存。

# 总结 #

位图算法，其需要一次遍历整个数据，假如有N个数据，就只是需要遍历N次，所以时间复杂度 是 `O(N)`。但是，其需要额外地开辟内存空间，有N个数据，就需要多开辟N bit位的数据， 额外需要：`N/8/1024/1024 MB` 的空间。假如是一亿个数据，那么大概要：`11.92MB`。

[github]: https://github.com/RoaringBitmap/RoaringBitmap
[70]: /images/20220508/7cd0adfb9a7d40cdaf7a3fbae17de5cd.png