0 前言

两周前和大家分享了有关于 geohash 算法的话题——GeoHash技术原理及应用实战，本周继续给大家带来另一款在设计思路上非常巧妙的数据结构工具——布隆过滤器 bloom filter.

1 布隆过滤器思路推演

1.1 致敬左神

我们先从一个实际的场景问题开始谈起.

实际上这个场景问题，包括布隆过滤器的概念，是在我自学编程阶段，在小破站观看左神算法课时首次接触到的，这里我专门引用这个例子加以说明，算是对左神进行一次小小的致敬，感恩成长路上每个对自己有过帮助的人 ^_^

1.2 场景问题

这个场景问题是这样的：

现在我们在参与组装一个爬虫程序的流程，我们手中已有一个存储了大量 url 的 list 作为输入源，我们需要让爬虫爬过每个 url，并以为基础呈网状扩张，扩展爬取网页内容中遇到的每个 url 链接.

在这个流程中，由于网络的网状性，同一个 url 可能会重复获取，因此我们需要建立一个合理的去重机制，避免爬虫遍历程序陷入重复的死循环当中.

现在假设我们总共有 10 亿条 url，要求通过单台机器的内存实现上述流程，试问要如何设计实现这个流程呢？

1.3 粗暴解法

解决这个问题最简单直观的方式，是通过维护一个存储遍历过了的 url 的集合，所有遍历到的 url 都先判断一下是否在集合中，如果是则直接忽略；如果不是则添加到集合中，并进行处理.

这样做是能够达到目标，但是需要考虑成本损耗问题. 现在总共有 10 亿个 url，假设每个 url 的大小是 16 byte，则总共需要的内存空间大小为 10亿 * 16byte= 16GB，这对于单机来说，是一个过于沉重的数字.

1.4 bitmap 解法

我们注意到这个场景中，在集合中只需要标识出对应 url 是否存在的信息即可，而无需记录下 url 的实际内容. 基于这一点出发，我们试想如果能够通过一个 bit 位对 url 的存在状态进行标识，如果为 0 则代表 url 不存在，如果为 1 则代表 url 存在，同样可以满足我们的使用诉求. 这样，我们就把存储一个 url 所需要花费的工作由 16 byte 降低到了 1 bit，所花费的空间仅为原方案的 1/128.

使用 bitmap 实现的想法固然很美好，然而我们如何建立一条 url 和一个 bit 位的映射关系呢？这里，我们自然而然想到的方案是哈希散列：

• • 首先明确 bitmap 的总长度，假设为 m

• • 接下来针对每个 url 取 hash 值

• • 每个 url 的 hash 值对 m 取模，得到其对应的 bit 位索引

通过上述流程，我们建立了由 url -> bit 位的映射关系，并且通过哈希函数的离散性，保证每个 url 对应的 bit 位尽可能均匀地分散在 bitmap 的各个位置.

然而，提到哈希函数，我们就绕不开其存在的一个问题——哈希碰撞. 由于哈希函数的输入域是无穷大的，对应的输出域是有限的，因此不过避免地存在多个不同的输入产生相同输出的问题，这个问题即称为哈希碰撞的现象.

更多有关哈希的内容，可以参见我之前发表的文章——Golang map 实现原理.

更何况，我们针对 url 取 hash 值后，还需要根据固有的 bitmap 长度 m 进行取模，这样多个不同 url 映射到相同 bit 位的概率就更高了.

最终我们还是无法建立一个 url 和一个 bit 位之间严格的一一映射关系，进而导致 bit 位对 url 是否存在的标识信息失去应有的准度.

1.5 布隆过滤器

在 bitmap 方案的基础之上，我们调整一下面对问题的思路.

由于哈希碰撞的存在，我们知道基于 bitmap 标识 url 的信息是会存在“误判”问题，那么这个“误判”问题究竟会发生在什么样的场景中，产生什么样的后果呢？

• • 假如一个 url 存在，bitmap 会将其误判为不存在么？

答案是不会. 由于哈希函数具有单向稳定映射的性质，因此一个相同的 url 不管输入多少次，都会产生相同的 hash 值，最终映射到相同的 bit 位. 倘若其之前输入过，对应的 bit 位一定为置为 1，后续一定会被判定为存在.

• • 假如一个 url 不存在，bitmap 会将其误判为存在么？

答案是可能会. 由于哈希碰撞问题的存在，导致多个 url 可能映射到相同的 bit 位. 假设 url1 和 url2 都映射到 bit1，输入 url1 后 bit1 就会被置为 1，这样哪怕 url2 未曾输入过，其首次输入时，对应的 bit1 位置也为 1，因此会被误判为已存在.

针对于 url 不存在被误判为存在的现象，首先我们需要明确这是只有少量发生了哈希碰撞的 url 才会产生的问题，其次在我们的爬虫程序主要应用在大数据场景中，更注重的是宏观的数学模型和数据量级，因此是可以接受少量数据的遗漏问题的.

因此，基于 bitmap 的实现方案已经在我们能够接受的范畴之内，下面要考虑的就是，如何通过合理的流程设计，来尽可能降低这部分误判问题的发生概率.

在这里，我们采用的方式是增加哈希函数的个数，比如我们将哈希函数的个数由 1 个增加为 k 个，那么对应于一个 url 的 bit 位就是 k 个，于是发生误判的前提就是，这 k 个 bit 位都因为哈希碰撞而被置为 1，相比于 1 个 bit 位，发生误判的概率大大降低，并且可以基于数学推导获取到准确的误判概率.

至此，布隆过滤器的实现思路就向大家展示完毕. 下面我们再回过头来对其下一个定义：

布隆过滤由一个 bitmap 和一系列随机映射函数组成，它不存放数据的明细内容，仅仅标识一则数据是否存在的信息，其最大的优点是拥有很良好的空间利用率和查询效率.

1.6 布隆过滤器优缺点

下面我们对布隆过滤器的优缺点进行总结：

优点：

• • 节省空间：一个 bit 位标识一则数据的存在信息，且利用了 k 个散列函数进行映射后，bitmap 的长度 m 可以进一步降低

• • 查询高效：使用 k 个散列函数进行映射，由于 k 为常数，因此实际的时间复杂度为 O(1)

缺点：

• • 存在假阳性误判问题：

对于不存在的数据可能会被误判为存在，对于已存在的数据不可能发生误判.

• • 数据存在删除困难的问题：

由于哈希碰撞问题的存在，一个 bit 位可能被多个输入数据使用，因此无法删除. 最终 bitmap 使用越久，被置为 1 的 bit 位越多，发生误判的概率就越高.

极端场景下，所有 bit 位都被置为 1，则针对所有不存在数据的误判概率为 100%.

针对于布隆过滤器数据删除困难的问题，下面提出两个方向的解决方案：

方案一：数据归档

这种方案适用于我们在数据库中仍然存有全量数据的明细记录，使用布隆过滤器仅仅作为缓存层起到保护关系型数据库的用途. 此时我们可以定期地对一部分数据库中的老数据进行归档，然后定期使用指定时间范围内的新数据构建出一个新的 bitmap，对老的 bitmap 进行覆盖，以此延长布隆过滤器的生命力.

方案二：布谷鸟过滤器

布谷鸟过滤器是另一类另辟蹊径的算法工具，能够在一定程度上支持 bitmap 中的数据删除操作. 这是个很有信息量的话题，我们后续单开一篇文章加以描述.

2 布隆过滤器误判率推演

这部分数学推演流程是我当前在滴滴出行营销技术工作过程中，借鉴了组内石老师的技术分享后形成的思路，这里需要特别致敬一下石老师.

2.1 误判率推演

首先，我们设置好布隆过滤器的三个基本参数：

• • bitmap 的长度设置为 m；

• • hash 函数的个数设置为 k；

• • bitmap 中已输入的元素个数为 n；（注意是输入的元素而非被置为 1 的 bit 位）

下面我们开始概率推演：

• • 在输入 1 个元素，并通过 hash 函数进行 1 次映射时，1 个 bit 位因为这次操作被置为 1 的概率为 1/m；

• • 反之，这个 bit 位不会因为这次操作被置为 1 的概率为 1-1/m；

• • 进一步得到，这个 bit 位在经过 k 次 hash 映射后，仍然不被置为 1 的概率为 (1-1/m)^k；

• • 进一步得到，这个 bit 位在输入 n 个元素后，仍然不被置为 1 的概率为 (1-1/m)^(k·n)；

• • 反之，在输入 n 个元素后，1 个 bit 位被置为 1 的概率为 1-(1-1/m)^(k·n)；

有了以上的结论后，我们知道我们每次输入一个元素时，发生误判的前提是，经过 hash 映射后，对应的 k 个 bit 位都在此前恰好被置为 1 了，因此我们可以得到误判发生的概率为——

[1-(1-1/m)^(k·n)]^k

下面我们基于高等数学中等价无穷小的规则，对这个误判概率表达式进行简化.

在高等数学中，我们知道当 x->0 时，有 (1+x)^(1/x)~e，其中 e 为自然常数，值约为 2.7182818.

于是我们有，当 m->∞ 时，1/m -> 0，于是有 (1-1/m)^(-m)~e.

于是有 (1-1/m)^(k·n)=(1-1/m)^[(-m)·(-k·n/m)]~e^(-k·n/m)

最终我们得到，当 m->∞ 时，误判概率可以简化表示为——[1-e^(-k·n/m)]^k.

2.2 参数调优思路

通过 2.1 小节，我们知道一个布隆过滤器发生误判的概率是同时与 bimap 的长度 m、hash 函数的个数 k 以及 bitmap 中已输入元素的个数 n 有关的.

下面我们的问题是，我们如何通过合理的参数选取，来降低布隆过滤器发生误判的概率呢？

在面对这个问题时，我们采用的视角是，在已知 m 和 n 的前提下，如何通过 k 的取值，来使得误判概率趋于最低，因此 m 和 n 对于我们而言是常量，k 为求取的变量.

为进一步简化误判概率表达式，我们将常量表达式 e^(n/m) 记为常数 t，于是误判概率表达式为——f(k)=[1-t^(-k)]^k

我们对 f(k) 进行求导，通过求取 f(k) 的极小值（f'(k)=0，f''(k)>0），最终得到当 k·n/m=ln2 时，误判概率 f(k) 取到极小值.

因此我们在设计布隆过滤的参数时，应该遵循如下思路：

• • 首先初步设定 bitmap 长度 m 为一个足够大的值

• • 其次，我们预估这个布隆过滤器中可能存放的元素数量 n

• • 接下来我们根据 k·n/m=ln2，计算出合适的 hash 函数个数

• • 最后，我们通过误判概率表达式 [1-e^(-k·n/m)]^k，推算出可能发生误判的概率，看是否能够满足要求

针对于布隆过滤器的参数选取，这里有一个现成的参数调优模拟器，可供使用：

https://hur.st/bloomfilter/?n=9000000&p=&m=65000000&k=6

2.3 哈希算法选型

在针对布隆过滤器中的 hash 函数进行选型时，我们主要以计算性能为优先考虑项，相较之下，hash 函数无需具备加密属性（不强要求两个不同输入源一定产生不同的结构）.

基于此，我们不考虑使用类似于 sha1、md5 这样的加密 hash 算法，而是在非加密性 hash 算法中进行选择. 其中， murmur3 算法在性能上有着比较良好的表现，后续在 4 5 章的布隆过滤器实现代码中，我们选择采用 murmur3 作为 hash 函数.

murmur3 github 开源地址：https://github.com/spaolacci/murmur3

3 本地布隆过滤器实现

下面展示一下，基于本地 bitmap 实现布隆过滤器的具体代码：

3.1 哈希编码

下面是通过 murmur3 实现的 hash 编码模块，将输入的字符串转为 int32 类型的 hash 值：

import (
    "math"


    "github.com/spaolacci/murmur3"
)


type Encryptor struct {
}


func NewEncryptor() *Encryptor {
    return &Encryptor{}
}


func (e *Encryptor) Encrypt(origin string) int32 {
    hasher := murmur3.New32()
    _, _ = hasher.Write([]byte(origin))
    return int32(hasher.Sum32() % math.MaxInt32)
}

3.2 布隆过滤器服务

下面是基于本地 bitmap 构建的布隆过滤器服务：

• • m：bimap 的长度，由用户输入

• • k：hash 函数的个数，由用户输入

• • n：布隆过滤器中的元素个数，由布隆过滤器统计

• • bitmap：位图，类型为 []int，其中使用到每个 int 元素的 32 个 bit 位，因此有 []int 长度为 m/32. 构造时为避免除不尽的问题，切片长度额外增大 1

• • encryptor：散列函数编码模块

import (
    "context"


    "github.com/demdxx/gocast"
)


type LocalBloomService struct {
    m, k, n   int32
    bitmap    []int
    encryptor *Encryptor
}


func NewLocalBloomService(m, k int32, encryptor *Encryptor) *LocalBloomService {
    return &LocalBloomService{
        m:         m,
        k:         k,
        bitmap:    make([]int, m/32+1),
        encryptor: encryptor,
    }
}

3.3 查询流程

下面是判定一个元素 val 是否存在于布隆过滤器的查询流程：

• • 首先基于 LocalBloomService.getKEncrypted 方法，获取到 val 对应的 k 个 bit 位的偏移 offset

• • 由于 []int 中，每个 int 元素使用 32 个 bit 位，因此对于每个 offset，对应在 []int 中的 index 位置为 offset >> 5，即 offset/32

• • offset 在一个 int 元素中的位置对应为 offset & 31，即 offset % 32

• • 倘若有任意一个 bit 位标识为 0，都说明元素 val 在布隆过滤器中一定不存在

• • 倘若所有 bit 位标识都为 1，则说明元素 val 在布隆过滤器中很有可能存在

func (l *LocalBloomService) Exist(val string) bool {
    for _, offset := range l.getKEncrypted(val) {
        index := offset >> 5     // 等价于 / 32
        bitOffset := offset & 31 // 等价于 % 32


        if l.bitmap[index]&(1<<bitOffset) == 0 {
            return false
        }
    }


    return true
}

获取一个元素 val 对应 k 个 bit 位偏移量 offset 的实现如下：

• • 首次映射时，以元素 val 作为输入，获取 murmur3 映射得到的 hash 值

• • 接下来每次以上一轮的 hash 值作为输入，获取 murmur3 映射得到新一轮 hash 值

• • 凑齐 k 个 hash 值后返回结果

func (l *LocalBloomService) getKEncrypted(val string) []int32 {
    encrypteds := make([]int32, 0, l.k)
    origin := val
    for i := 0; int32(i) < l.k; i++ {
        encrypted := l.encryptor.Encrypt(origin)
        encrypteds = append(encrypteds, encrypted%l.m)
        if int32(i) == l.k-1 {
            break
        }
        origin = gocast.ToString(encrypted)
    }
    return encrypteds
}

3.4 添加流程

下面是追加元素进入布隆过滤器的流程：

• • 每有一个新元素到来，布隆过滤器中的 n 递增

• • 调用 LocalBloomService.getKEncrypted 方法，获取到元素 val 对应的 k 个 bit 位的偏移量 offset

• • 通过 offset >> 5 获取到 bit 位在 []int 中的索引，思路同 3.3 小节

• • 通过 offset & 31 获取到 bit 位在 int 中的 bit 位置，思路同 3.3 小节

• • 通过 | 操作，将对应的 bit 位置为 1

• • 重复上述流程，将 k 个 bit 位均置为 1

func (l *LocalBloomService) Set(val string) {
    l.n++
    for _, offset := range l.getKEncrypted(val) {
        index := offset >> 5     // 等价于 / 32
        bitOffset := offset & 31 // 等价于 % 32


        l.bitmap[index] |= (1 << bitOffset)
    }
}

4 基于 redis 实现布隆过滤器

下面展示一下，基于 redis bitmap 实现布隆过滤器的具体代码：

4.1 哈希编码

murmur3 哈希编码模块同本文 3.1 小节本地布隆过滤器模块中的实现，不再赘述：

import (
    "math"


    "github.com/spaolacci/murmur3"
)


type Encryptor struct {
}


func NewEncryptor() *Encryptor {
    return &Encryptor{}
}


func (e *Encryptor) Encrypt(origin string) int32 {
    hasher := murmur3.New32()
    _, _ = hasher.Write([]byte(origin))
    return int32(hasher.Sum32() % math.MaxInt32)
}

4.2 redis 客户端

redigo github 开源地址：https://github.com/gomodule/redigo

基于 redigo 搭建的 redis 客户端实现代码如下：

• • 基于 redis 连接池，进行连接的复用，每次操作需要先从连接池获取连接，使用完毕后需要手动将连接放回池子中

• • redis 客户端封装了一个 Eval 接口，用于执行 lua 脚本，完成复合指令的原子化组装

import (
    "context"
    "fmt"


    "github.com/demdxx/gocast"
    "github.com/gomodule/redigo/redis"
)


type RedisClient struct {
    pool *redis.Pool
}


func NewRedisClient(pool *redis.Pool) *RedisClient {
    return &RedisClient{
        pool: pool,
    }
}


// 执行 lua 脚本，保证复合操作的原子性
func (r *RedisClient) Eval(ctx context.Context, src string, keyCount int, keysAndArgs []interface{}) (interface{}, error) {
    args := make([]interface{}, 2+len(keysAndArgs))
    args[0] = src
    args[1] = keyCount
    copy(args[2:], keysAndArgs)


    // 获取连接
    conn, err := r.pool.GetContext(ctx)
    if err != nil {
        return -1, err
    }


    // 放回连接池
    defer conn.Close()


    // 执行 lua 脚本
    return conn.Do("EVAL", args...)
}

4.3 布隆过滤器服务

定义布隆过滤器服务模块：

• • m：bitmap 长度，由用户输入

• • k：hash 函数个数，由用户输入

• • client：连接 redis 的客户端

// 布隆过滤器服务
type BloomService struct {
    m, k      int32
    encryptor *Encryptor
    client    *RedisClient
}


// m -> bitmap 的长度；k -> hash 函数的个数；
// client -> redis 客户端；encryptor -> hash 映射器
func NewBloomService(m, k int32, client *RedisClient, encrytor *Encryptor) *BloomService {
    return &BloomService{
        m: m,
        k: k,
        client:    client,
        encryptor: encrytor,
    }
}

4.4 查询流程

查询输入内容是否存在于布隆过滤器当中：

• • key 对应的是布隆过滤器中 bitmap 的标识键 key，不同 key 对应的元素是相互隔离的

• • val 对应的是输入的元素，从属于某个 key 对应的 bitmap

• • 调用 BloomService.getKEncrypted 方法，获取到 k 个 bit 位对应的偏移量 offset

• • 调用 RedisClient.Eval 方法执行 lua 脚本，但凡 k 个 bit 位中有一位不为 1，则返回 false 不存在，否则返回 true 存在

// key -> 布隆过滤器 bitmap 对应的 key   val -> 基于 hash 映射到 bitmap 中的值
func (b *BloomService) Exist(ctx context.Context, key, val string) (bool, error) {
    // 映射对应的 bit 位
    keyAndArgs := make([]interface{}, 0, b.k+2)
    keyAndArgs = append(keyAndArgs, key, b.k)
    for _, encrypted := range b.getKEncrypted(val) {
        keyAndArgs = append(keyAndArgs, encrypted)
    }


    rawResp, err := b.client.Eval(ctx, LuaBloomBatchGetBits, 1, keyAndArgs)
    if err != nil {
        return false, err
    }


    resp := gocast.ToInt(rawResp)
    if resp == 1{
        return true,nil
    }
    return false, nil
}

根据输入元素映射到 k 个 bit 位偏移量 offset 的执行方法是 getKEncrypted，逻辑同 3.3 小节，不再赘述.

func (b *BloomService) getKEncrypted(val string) []int32 {
    encrypteds := make([]int32, 0, b.k)
    origin := val
    for i := 0; int32(i) < b.k; i++ {
        encrypted := b.encryptor.Encrypt(origin)
        encrypteds = append(encrypteds, encrypted)
        if int32(i) == b.k-1 {
            break
        }
        origin = gocast.ToString(encrypted)
    }
    return encrypteds
}

下面是批量执行 bitmap 查询操作的 lua 脚本：会针对 k 个 bit 位进行查询，只要有一个 bit 位的标识为 0，则返回 0；如果所有 bit 位的标识都为 1，则返回 1.

const LuaBloomBatchGetBits = `
  local bloomKey = KEYS[1]
  local bitsCnt = ARGV[1]
  for i=1,bitsCnt,1 do
    local offset = ARGV[1+i]
    local reply = redis.call('getbit',bloomKey,offset)
    if (not reply) then
        error('FAIL')
        return 0
    end
    if (reply == 0) then
        return 0
    end
  end
  return 1
`

4.5 添加流程

将一个输入元素添加到布隆过滤器中的流程如下：

• • key 对应的是布隆过滤器中 bitmap 的标识键 key，不同 key 对应的元素是相互隔离的

• • val 对应的是输入的元素，从属于某个 key 对应的 bitmap

• • 调用 BloomService.getKEncrypted 方法，获取到 k 个 bit 位对应的偏移量 offset

• • 调用 RedisClient.Eval 方法执行 lua 脚本，将 k 个 bit 位统统置为 1

func (b *BloomService) Set(ctx context.Context, key, val string) error {
    // 映射对应的 bit 位
    keyAndArgs := make([]interface{}, 0, b.k+2)
    keyAndArgs = append(keyAndArgs, key, b.k)
    for _, encrypted := range b.getKEncrypted(val) {
        keyAndArgs = append(keyAndArgs, encrypted)
    }


    rawResp, err := b.client.Eval(ctx, LuaBloomBatchSetBits, 1, keyAndArgs)
    if err != nil {
        return err
    }
    
    resp := gocast.ToInt(rawResp)
    if resp != 1 {
        return fmt.Errorf("resp: %d", resp)
    }
    return nil
}

同样基于 lua 脚本实现复合指令的原子化组装，将 k 个 bit 位同时置为 1

const LuaBloomBatchSetBits = `
  local bloomKey = KEYS[1]
  local bitsCnt = ARGV[1]


  for i=1,bitsCnt,1 do
    local offset = ARGV[1+i]
    redis.call('setbit',bloomKey,offset,1)
  end
  return 1
`

5 工程案例介绍

在我之前实现的个人项目——分布式定时器 xtimer 中就使用到了布隆过滤器作为任务幂等性校验的辅助工具.

  该项目详细介绍见文章——基于协程池架构实现分布式定时器 XTimer

xtimer 开源地址如下：https://github.com/xiaoxuxiansheng/xtimer

xtimer 架构图如下：

在 xtimer 中，定时任务的实际执行聚焦在执行器 executor 模块，是由上游 trigger 模块异步启动的，只能通过一种类似于 ack 的分片过期时间延长操作，保证到定时任务满足 at least once 的语义，但无法做到 exactly once 的语义.

因此在 executor 模块实际执行任务前，需要查询数据库中的定时任务执行状态，完成幂等性校验. 在这个过程中,我使用到 bloomFilter，来明确标识出哪部分任务是一定没有执行过的，此时可以减少一次查库操作，直接步入后续的执行流程；针对于被 bloomFilter 标识为已执行的任务，则还需要二次查数据库完成兜底校验.

整个执行流程图如下：

6 总结

本期和大家分享了一个设计思路非常巧妙的数据结构——布隆过滤器.

布隆过滤由一个 bitmap 和一系列随机映射函数组成，它不存放数据的明细内容，仅仅标识一则数据是否存在的信息，其最大的优点是拥有很良好的空间利用率和查询效率，其存在的缺点则是数据删除困难，以及存在一定的假阳性误判概率.