从Bitmap与HBase看布隆过滤器

一、前言

在编程的世界中我们很有可能会面对处理的数据量在逐渐增大，并且到一个非常大的数据量的问题，我们这时候还需要判断一个数据是否存在“数据池子”中（可以简单的想象为判断要执行去重操作），然后在进行下一步的操作。对此我们通常的解决办法是维护一个数据结构来保存池子中的数据，在池子中找被检测数据是否存在。类似黑白名单功能一样。

但是在数据量非常大时存在着一系列问题，例如存储数据会消耗很多系统资源，检索性能低下等等。这时我们就会想到用布隆过滤器和Bitmap。以数据类型为int举例，如果采用HashSet或者HashMap存储，占4字节，即32bit。而前二者只要1bit存储（理论上16G的内存数据只要512M内存）。

二、位图（Bitmap）

bitmap数据结构是内存中连续的二进制位，适用于大量整型数据存储。实际业务中最主要应用于用户画像存储、大数据排序去重等业务场景。

Bitmap基础入门

https://mp.weixin.qq.com/s/xxauNrJY9HlVNvLrL5j2hg

关于Bitmap入门推荐去看这篇博客的图文讲解。

Bitmap的优势

• 实际上，java jdk1.0就已经提供了bitmap的实现BitSet类（不推荐，Guava的EWAHCompressedBitmap优化的更好，并且注意的是BitSet的某些方法需要是jdk1.4之后才有的）。
• bitmap就是用一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身,我们知道8个bit才组成一个Byte，所以bitmap本身会极大的节省储存空间
• 非常适合做数据的一系列并集差集运算，而不仅仅是去重操作，适用于更广的业务需求（例如查询用户在线状态，只需要一个key，然后用户ID为offset，如果在线就设置为1，不在线就设置为0，5000W用户只需要6MB的空间）。
• 由于bitmap数据结构的特性，存储后的数据是有序。

redis对Bitmap的不一样实现

其实bitmap在大数据领域更是广泛使用，比如hive（Hive 0.8.0版本中增加了bitmap索引）、redis等，而在redis中实现了bitmap数据结构，但redis的实现与我们的理论中的比特数组有些不一样，redis中的bitmap实质是一个字符串类型，不过我们还是可以通过字符串的下标偏移量offset来对字符串的bit位进行操作。

getbit key offset   //用于获取Redis中指定key对应的值中 对应offset的bit

//注意：如果offset过大，则会在中间填充0，offset最大到2^32-1，因为redis中的字符串限制最大为512M
setbit key offset value  //设置offset对应二进制上的值，返回该位上的旧值

//opecation可以是AND（与） OR（或） NOT（非） XOR（异或）
bitop operation rs key1 [key2..]     //对key1 key2做opecation并将结果保存在rs上    

bitcount key [start end]  //用于统计字符串被设置为1的bit数

使用spring data redis的redisTemplate代码实现

    public boolean getBit(String key, Long offset) {
        return redisTemplate.opsForValue().getBit(key,offset);
    }

    public void setBit(String key, Long offset) {
        redisTemplate.opsForValue().setBit(key,offset,true);
    }
    //其他不常用的 略

三、布隆过滤器（Bloom filter）

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的(假阳性)，而不是确切的。

与bitmap一样它也是一个bit数组（学术上定义是bit向量），但不同的是如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值（hashcode），并对每个生成的哈希值指向的 对应bit位进行置1操作。

检查元素时，会先经过各Hash函数计算被检测值，生成一组正整数的HashCode值。在比特数组中查询各HashCode值对应的位置是否为1。如果各位置均为1，说明被检测值可能在集合中。如果有一个位置为0，说明被检测值肯定不在集合中。

根据上面的定义我们很容易使用java自定义实现一个简单的布隆过滤器

package com.gxuwz.bean;

import java.util.BitSet;

/**
 * {@link BitSet}
 * @description: 自定义一个简单的布隆过滤器 
 * @auther: <a href="mailto:xiaozuo1221@gmail.com">Albert</a>
 * @date: 2020/3/19 23:18
 * @version 1.0
 */
public class BloomFilter {
    //相当于2的一次方 左移24，得 2的25次方
    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    // 内部类SimpleHash
    //Hash算法采用了最简单的基于seed和ascii码的Hash算法。八个种子均采用质数，减少HASH碰撞的概率。

    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }

}

HBase对于布隆过滤器实战

在HBase中底层数据是存储在HFile中的（加载到内存中的数据存储在MemStore中，当MemStore中的数据达到一定数量时，它会将数据存入HFile中），而每个HFile中存储的是有序的kv键值对，HFile文件内部由连续的块组成，每个块中存储的第一行数据的行键组成了这个文件的块索引，这些块索引信息存储在文件尾部。当HBase打开一个HFile时，块索引信息会优先加载到内存；HBase首先在内存的块索引中进行二分查找，确定可能包含给定键的块，然后读取磁盘块找到实际想要的键。

块索引能帮助我们更快地在一个文件中找到想要的数据，但是我们可能依然扫描了很多文件，因此引用了布隆过滤器，用户可以立即判断一个文件是否包含特定的行键，从而帮我们过滤掉一些不需要扫描的文件。

布隆过滤器是hbase中的高级功能，它能够减少特定访问模式（get/scan）下的查询时间(简单来说就是提高随机读的效率)。不过由于这种模式增加了内存和存储的负担，所以被默认为关闭状态。

hbase支持如下类型的布隆过滤器：

1、NONE 不使用布隆过滤器,默认

2、ROW 行键使用布隆过滤器

3、ROWCOL 列键使用布隆过滤器

其中ROWCOL是粒度更细的模式，值得注意的是基于row的scan指令是没办法走Bloom Filter的。因为布隆过滤器是需要事先知道过滤项的。对于顺序scan指令是没有事先办法知道rowkey的。而get指令是指明了rowkey所以可以用布隆过滤器，scan指明column同理。。。

对于HBase而言，当我们选择采用布隆过滤器之后，HBase会在生成HFile时包含一份布隆过滤器结构的数据，称其为MetaBlock；MetaBlock与DataBlock（真实的KeyValue数据）一起由LRUBlockCache维护。所以，开启bloomfilter会有一定的存储及内存cache开销。但是在大多数情况下，这些负担相对于布隆过滤器带来的好处是可以接受的.

四、总结

值得注意的是我在对数据结构的应用举例子时，不代表这些应用只使用了一种数据结构，比如 redis 也可以用布隆过滤器来解决缓存穿透的问题。事实上很多爬虫程序就是在使用布隆过滤器时也都是基于 redis 来做布隆过滤器的。

推荐去看看一篇博客 https://www.jianshu.com/p/c2defe549b40

结合上面的 bitmap 和 Bloom filter 的介绍时我们很容易看到了这两种数据结构有一些相似之处，也有一些不同之处，在实际开发中的选择时需要在两者之间仔细的斟酌。

由于我们主要谈论的是布隆过滤器，那么我们应该如何去选择使用它呢？

我们知道 bitmap 在内存中是连续的二进制位，它会直接通过一个bit位来表示某个元素对应的值或者状态，因此它适用于数字之间差值比较小的情况（最好可以是无限趋近于连续数据），若数字之间差值比较大会造成很大的资源浪费。例如在爬虫时为了避免重复下载，我们会存储网站URL，由于网站URL很长，这时通常用一个64位，甚至是128位的整数来标识URL。将该整数与bit数组下标值对应的位置置1后会发现开辟了大量没意义的空间，这就是由于数据量太离散造成存储数据中有大量无用且置为0的空间被浪费，造成了空间利用率的低下。

因此我们得出一个结论：bitmap的占用空间是随着当前最大元素的值而发生变化的，因此在处理数据量大且高度离散的数据时，我们会采用布隆过滤器。

而布隆过滤器就是在bitmap的基础上 有效的优化了空间利用率，采用了多个哈希函数，使得在存储时，某一个比特可以被多次利用，使得数据不仅可以是高度离散的，还可以更有效的利用空间。而对于布隆过滤器的假阳性，我认为可以根据业务实际的需要，通过以适当的提前设置白名单的方式来进行一部分的解决。

因此我们发现： 布隆过滤器适合数据量大，数据无规则且离散的日志使用（值得注意的是，这里的日志指的并不是传统意义上的日志，为了帮助不了解日志这个词意思的同学，我在这里推荐大家看 Kreps 的一篇博文，这篇博文被称为 程序员史诗般必读文章：日志：每个软件工程师都应该知道的有关实时数据的统一抽象 ）

end~