源码位置：core\bloom\bloom.go

核心原理

布隆过滤器Bloom Filter（下面简称BF）是一种经典的海量数据处理算法，用于判断一个元素是否在一个超大集合中。BF是一种空间效率极高的概率算法，底层采用二进制位图存储数据。算法的大致流程是，对元素产生k个Hash值，将每一个Hash值都设置到底层位图数组中（Hash值对应位图下标的位设置为1）。判断元素是否存在时，先计算k个Hash值，再校验所有对应下标的位的值是否都是1，如果都是1返回数据存在，否则返回不存在。

存在假阳性误判

当元素存在时，判断结果一定是存在，不存在误判。因为数据在写入BF时，产生了k个Hash值，算法已经将k个Hash值对应的所有位都设置为了1。在我们查询该元素时，算法会产生完全相同的k个Hash值，所有这些Hash值对应的位必然都是1，因此必然返回数据存在（除非底层Redis位图被人为破坏性的修改了）。

当元素不存在时，判断结果极大的概率是不存在，但是存在极小的概率会返回元素存在，即假阳性判断（False Positive）。由于BF算法对每一个元素都会产生k个Hash值，不可避免的会产生Hash冲突，比如元素1的第三个Hash和元素10000的第5个Hash相同，那么该Hash值对应的位图上的一个位，就同时对应了两个元素的某个Hash值。即一个位图上的一个位，可能同时对应了多个元素的某个相同Hash值。现在，我们确定有一个元素不存在，那么这个不存在的元素也对应了k个Hash值，巧合的是，随着BF中数据量的增加，这k个Hash对应的位同时被其他元素都设置为了1，那么此时查询存在性时，就产生了假阳性，即不存在的元素误判为了存在。

假阳性的误判率是很低的，通常在万分之一以下，与构造BF的参数有关。其简化公式为：

p ≈ (1 - e^(-k * n / m))^k

参数解释：

k为Hash函数个数，go-zero的实现中固定为14；

n为预期数据量，通常较大，如100万；

m为位图位数，通常是n的20倍以上。

我们以go-zero中的实现为例（k固定为14），降低n/m的比例，将有效降低误判率p。当m=20n时，误判率为：0.0067%；m=22n时，误判率为：0.0021%；m=30n时，误判率为：0.00014%。

使用场景

BF的经典使用场景有很多：

1.避免缓存击穿

将已存在的主键信息加入到BF，在查找一个元素的详细信息时，先在BF中快速查询一次存在性，如果判断元素不存在时，那么可以立即返回不存在。如果判断元素存在，那么有极小的概率是误判的（即元素实际上是不存在的），此时再去底层的数据系统中查询该元素的详细信息。

这些极少量的误判元素，最终在DB中查询的结果是元素不存在，由于误判率很低，比如0.0067%，完全不会对我们的数据系统造成任何压力，是可接受的。

为什么不把这些已存在的元素主键加入到诸如Hash或者Set这类Redis数据结构中呢（100%没有误判）？而是使用存在一定误判率的BF算法？答案在空间效率上，当你有1千万，1亿个这样的元素需要判断存在性时，Hash或者Set这种结构占据的空间就完全不可接受，只有BF可以做到占用很少的空间（底层是二进制位图）。

2.区块链系统

区块链是一个典型的读多写少的系统，用户真正发起交易的次数很少，但是却经常会去查询区块，特别是交易的详细信息。在通常的区块链系统的实现中，总是将区块Hash和交易Hash（区块和交易的主键id）加入到BF中，从而拦截绝大部分不存在的Hash查询到达底层，直接返回不存在。

3.垃圾邮件识别

比如将几亿个垃圾邮件加入到BF后，就可以通过查询BF快速判断一个邮件是否是垃圾邮件了。

4.网络爬虫对URL去重

将已经爬取到的URL地址加入到BF后，就可以快速的避免重复爬取了。

使用示例

const BitsPerElement = 20 //  bits / elements 比值

func main() {
	// 1. 创建bloom过滤器，预期存储100万数据
	existDatas := [10]string{}
	bl := CreateBloom("localhost:6379", "bltest", 1000000, &existDatas) // 预期100万数据

	// 2. 测试已存在的数据 的存在性
	for i := 0; i < 3; i++ { // 测试前3个数据的存在性
		exist, err := bl.ExistsCtx(context.Background(), []byte(existDatas[i])) // 测试存在性
		if err != nil {
			fmt.Printf("ExistsCtx:%s err:%v\n", existDatas[i], err) // 打印后忽略错误
			break
		}
		if !exist { // 出现了不可能的情况（数据实际存在，却报告了不存在，不可能）
			fmt.Printf("ExistsCtx:%s report unexist, impossible!!!\n", existDatas[i], err)
			break
		}
	}

	// 3. 继续插入1000个数据，模拟软件运行过程中的增量数据
	for i := 0; i < 1000; i++ {
		bl.AddCtx(context.Background(), []byte(GenerateUuidV4()))
	}

	// 4. 再测试一次已存在数据 的存在性
	for i := 3; i < 6; i++ { // 测试第二页
		exist, err := bl.ExistsCtx(context.Background(), []byte(existDatas[i]))
		if err != nil {
			fmt.Printf("ExistsCtx:%s err:%v\n", existDatas[i], err)
			break
		}
		if !exist { // 出现了不可能的情况
			fmt.Printf("ExistsCtx:%s report unexist, impossible!!!\n", existDatas[i], err)
			break
		}
	}

	// 5. 测试不存在数据 的存在性（可能误判为存在，概率为0.000067）
	unexistCount := 2000000
	totalWrong := 0
	for i := 0; i < unexistCount; i++ { // 测试200万次，统计误判率
		uuid := GenerateUuidV4()
		exist, err := bl.ExistsCtx(context.Background(), []byte(uuid))
		if err != nil {
			fmt.Printf("ExistsCtx:%s err:%v\n", uuid, err)
			break
		}
		if exist { // 出现了误判
			totalWrong++
			fmt.Printf("ExistsCtx:%s wrong report exist!!!\n", uuid)
			break
		}
	}

	// 6. 打印误判率
	fmt.Printf("False Positive Ratio: %d / %d.\n", totalWrong, unexistCount)
}

// redisHost服务端地址，如localhost:6379；bloomKey布隆过滤器实例在redis中对应的位图键；elements预期的数据量；
// existDatas返回产生的10条数据（用于外部测试存在性）
func CreateBloom(redisHost, bloomKey string, elements int, existDatas *[10]string) *bloom.Filter { // 创建Bloom过滤器
	rd := redis.MustNewRedis(redis.RedisConf{Host: redisHost, Type: "node"}) // 创建redis
	bl := bloom.New(rd, bloomKey, uint(BitsPerElement*elements))             // 创建bloom过滤器
	initElements := elements >> 1                                            // 初始添加一半数据
	for i := 0; i < initElements; i++ {                                      // 向bloom过滤器添加数据
		uuid := GenerateUuidV4()
		if err := bl.AddCtx(context.Background(), []byte(uuid)); err != nil {
			fmt.Printf("AddCtx:%s err:%v\n", uuid, err) // 打印后忽略错误
			break
		}
		if i < len(*existDatas) { // 输出测试数据
			(*existDatas)[i] = uuid
		}
	}
	return bl
}

func GenerateUuidV4() string { // 产生32位uuid字符串
	u, err := uuid.NewV4()
	if err != nil {
		return ""
	}
	// xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
	return strings.ReplaceAll(u.String(), "-", "")
}

运行结果：

D:\go\src\test>go run bloom.go
ExistsCtx:6052fc4270884b1aa480870fa2c413f3 wrong report exist!!!
False Positive Ratio: 1 / 2000000.
D:\go\src\test>

运气太好了，对于不存在的元素，测试了200万次，才遇到一次误判，即假阳性。

核心流程

源码节选

// for detailed error rate table, see http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
// maps as k in the error rate table
const maps = 14 // 哈希函数的数量固定为14，即对每个key产生14个Hash值，设置位图中的14位

type (
	// A Filter is a bloom filter.
	Filter struct {
		bits   uint           // 位图总位数
		bitSet bitSetProvider // 存储接口
	}

	bitSetProvider interface { // 存储接口，测试和设置方法
		check(ctx context.Context, offsets []uint) (bool, error)
		set(ctx context.Context, offsets []uint) error
	}
)

// New create a Filter, store is the backed redis, key is the key for the bloom filter,
// bits is how many bits will be used, maps is how many hashes for each addition.
// best practices:    最佳实践
// elements - means how many actual elements    elements表示预期要存储的数据量，建议的位图位数bits等于20*elements
// when maps = 14, formula: 0.7*(bits/maps), bits = 20*elements, the error rate is 0.000067 < 1e-4
// 举例：预期存储100万数据，即elements=100万，位图位数bits=20*100万=2000万，误判率为0.000067（误判率固定为0.000067，与存储的数量量无关，看下面的公式）
// 误判率计算公式：p ≈ (1 - e^(-k * n / m))^k，参数说明：m位图位数，n预期数据量，k哈希函数个数（k固定为14的情况下，取决于n/m的比值，这里建议为1/20。提高m可有效降低误判率）
// for detailed error rate table, see http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
func New(store *redis.Redis, key string, bits uint) *Filter { // 创建一个bloom过滤器实例，采用redis作为存储介质，key是redis中的位图键名，bits是总位数
	return &Filter{
		bits:   bits,                             // 位图总位数
		bitSet: newRedisBitSet(store, key, bits), // redis位图读写实例，实现了bitSetProvider接口
	}
}

// Add adds data into f.
func (f *Filter) Add(data []byte) error {
	return f.AddCtx(context.Background(), data) // 转调用AddCtx
}

// AddCtx adds data into f with context.
func (f *Filter) AddCtx(ctx context.Context, data []byte) error { // 向bloom过滤器中添加数据
	locations := f.getLocations(data)   // 1.对输入数据一次性计算14个Hash，并计算和输出14个位图索引
	return f.bitSet.set(ctx, locations) // 2.调用redis位图的设置接口，即将所有位图下标全部设置为1
}

// Exists checks if data is in f.
func (f *Filter) Exists(data []byte) (bool, error) {
	return f.ExistsCtx(context.Background(), data) // 转调用ExistsCtx
}

// ExistsCtx checks if data is in f with context.
func (f *Filter) ExistsCtx(ctx context.Context, data []byte) (bool, error) { // 检查数据在bloom过滤器中的存在性
	locations := f.getLocations(data)            // 1.对输入数据一次性计算14个Hash，并计算和输出14个位图索引
	isSet, err := f.bitSet.check(ctx, locations) // 2.调用redis位图的测试接口，检查数据的存在性（所有14个位图索引都是1返回true，否者返回false）
	if err != nil {
		return false, err
	}

	return isSet, nil
}

func (f *Filter) getLocations(data []byte) []uint { // 对输入数据一次性计算14个Hash，并计算和输出14个位图索引
	locations := make([]uint, maps) // 一共生成14个Hash值，对应位图中的14个下标
	for i := uint(0); i < maps; i++ {
		hashValue := hash.Hash(append(data, byte(i)))   // 在输入数据后追加循环索引i，产生新的Hash值
		locations[i] = uint(hashValue % uint64(f.bits)) // 用取余的方式计算并输出 位图下标
	}

	return locations // 输出14个位图下标
}