Redis 实用小技巧—— bitmap 应用之「布隆过滤器」

简介

在《Redis 实用小技巧——神奇的 bitmap （上）》和《Redis 实用小技巧——神奇的 bitmap （下）》教程中，我们已经了解到了 bitmap 的相关原理和 Redis 中 bitmap 相关的操作命令，在接下来的系列文章中，我们将结合这些理论知识，来看几个比较典型的应用场景，从而加深对 bitmap 的了解。

这篇文章我们就从「布隆过滤器」开始，带大家走进 bitmap 的实战应用。

布隆过滤器

也许有些小伙伴会问，为什么要把「布隆过滤器」放到第一位来讲呢？

其实在这几个场景中，布隆过滤器算是相对复杂的一个场景了，但同时也是相对经典的一个场景。一开始我本来是打算放到最后来讲的，但是后来改变了主意：如果把布隆过滤器的思想掌握了以后，再学习其他的应用场景，会感觉相对容易一些。

那就让我们一起从了解「布隆过滤器」开始吧～

基本概念

首先，我们需要了解的是：什么是「布隆过滤器」呢？

其实，「布隆过滤器」这个概念早在 1970 就被提出来了。为什么叫「布隆」呢？无他，只因提出的人就叫「布隆」。

「布隆过滤器」是为了解决在海量的数据元素中，判断某些元素是否存在的问题而提出的。其核心是由二进制向量（ bit ）和一系列哈希算法（ map ）组成。

使用二进制向量是因为二进制向量本身的存储和操作优势，在 Redis 中，512 MB （实际分配空间比这个值要多一些）的存储空间就可以存储 2^32 -1 个数据，而设置或者取消 bit 位的值只要通过 SETBIT 操作即可完成。

而一系列的哈希算法，则是为了让 bit 位更具「表达力」。哈希算法本身是为了将序列化串映射到 bit 位的某一个偏移量上，那为何还需要一系列的哈希算法呢？

这还要从「哈希冲突」说起。「哈希冲突」又是个啥？

别急，听我娓娓道来。

还记得在《Redis 实用小技巧——神奇的 bitmap （上）》的开篇，我们举的那个例子吗？

现在让我们来考虑一个问题：怎么才能证明这个位置属于你家「在写作业」的那位呢？

如果你是这位「当事人」的话，或许你会说：我儿子叫「猪小明」，我写上他的名字可以了吧？

这时后边的「正义大哥」发话了：我儿子还叫「猪小明」呢，你怎么能证明你写的「猪小明」就是你儿子呢？

你又补充道：我儿子今年 10 岁。

大哥又接上了：好巧不巧，我儿子也 10 岁。

你继续道：我儿子身高一米二。

大哥坏坏地说：哎呀，我儿子也一米二呢，有什么办法呢。

这时，站在一旁的「吃瓜大哥」看不下去了，站出来替你支了一招：你直接把你儿子的身份证号写上不就完了么，看他还怎么接。

在这番对话中，姓名 + 年龄 + 身高，最终抵不过一个身份证管用。够绝。

除了够绝，没其他的了么？其实，站在「当事人」的角度想一下，当你在罗列姓名、年龄、身高这些时，你最终的诉求是什么呢？不就是为了证明这个位置属于你儿子么，而身份证号因为它的「唯一性」，貌似更具说服力。

但此时，身为「杠精」的我表示不服了：谁说来做核酸的一定是中国人呢，鄙人就是从毛里求斯火急火燎赶过来的，好巧不巧，我在我们国家的身份证号就和你儿子的一模一样了，你说气不气？

太累了，让我们先来暂停一波。插播一条广告先～

其实啰里八嗦讲了半天，上述这个「好巧不巧」的过程，就是一个「哈希冲突」的过程。

想象一下，不管倒霉的「当事人」怎么举证她儿子的「唯一性」，都能「好巧不巧」地被「撞衫」，哪怕是拿出了足够唯一的「身份证号」，都能被从毛里求斯远道而来的「大神」给撞一块。说明了什么？世界之大，「撞衫」无处不在。

从专业一点的角度讲，能否出现「哈希冲突」，主要有两点限制原因：

一是哈希函数的优良性，即哈希以后的值是否能够足够「唯一」，或者说在空间内「离散分布」。在上述例子中，就是怎么证明「你儿子就是你儿子」的问题。

二是分布空间的大小和空间内元素的多少。假设世界上只有两个「杠精」，那这哥俩相遇的概率还是很小的。但是当满大街都是「杠精」的时候，相遇就是眨一眨眼，擦一擦肩。

「只要有缘，总能遇见。」

回到先前的话题，布隆过滤器的第二大组成部分：一系列的哈希算法，想必看完这个形象的比方后，你已经猜到意图何在了吧。其实就是为了增加元素分布的随机性和降低「哈希冲突」的可能性。

我们来借用一张图看一下：

这里，我们将 X ，Y，和 Z 三个元素通过三个哈希函数分别映射到不同的 bit 位上（每一支箭头表示一种哈希算法）。现在，我们需要判断 W 这个元素是否存在于集合中。

我们需要对 W 通过三个哈希函数求散列值，并判断在 bit 位中是否已存在。这里有两种情况：

• 当存在至少一个 bit 位没有被设置时，则集合中肯定不存在 W （同一个值经过三个哈希函数计算得到的散列值必然相同）
• 当三个 bit 位都被设置时，则集合中可能存在 W (注意这里是可能，而不是一定)

或许，这里你会有个疑问，如果 W 经过哈希函数计算后，映射到的是以下位置呢（图中被圈出来的位置）：

没错，这就是「冲突」了，虽然 W 并不存在于集合中，却被「误判」为存在于集合中。

如此看来，这不很容易就「冲突」了吗？也没啥优势啊？

别忘了，我们的离散空间有 2^32 - 1 之大，假设哈希算法在空间内计算的散列值是均匀的，则两个元素发生碰撞的几率为 (2^32 - 1)^3。这已经足够大了。

但是当集合中的元素越来越多时，比如超过了一半以上，这时候发生「冲突」的概率就需要引起我们的重视了。

优点

相比于其他数据结构，布隆过滤器存储空间更占优势。当然，这种优势是相对于「海量数据」而言。比如当仅存储 2^32 -1 这一个数据时，在 32 位操作系统中，普通存储用一个无符号的 int 类型只需要 4 个字节，而 bitmap 需要 512 MB。但是反过来讲，当需要存储 2^32 - 1 个数据时，bitmap 则不用再额外分配空间，这点是普通存储无法比拟的。

另外，布隆过滤器的插入和查询的效率也是非常高的，时间复杂度均为 O(1) 。

从集合的角度讲，布隆过滤器可以表示全集，其它任何数据结构都不能。

缺点

当然，布隆过滤器的缺点也是十分明显的。

首先，因为布隆过滤器使用多个哈希函数来计算散列值，这就会导致同一个 bit 位的偏移量可能是不同值的散列值。这样麻烦就来了，当我将一个元素加入到 bitmap 中以后，我无法再进行删除操作了，因为如果删除的话，可能会把其他值的散列值也删除掉。

另外一个缺点就是「误判率」了。即当我们集合中的元素越来越多时，会导致误判的概率越来越大。不过，就算拿 2^32 - 1的一半来讲的话，也有 21 亿多的数据量呢，这对于一般的场景来说已经够用了。如果数据量确实很大的话，则可以考虑拆分成多张 bitmap 表，然后再通过固定的哈希算法进行映射，这样也能解决一部分问题。

代码实现

讲了这么多理论，肯定感觉到枯燥了吧。接下来，我们就以 Laravel 为例，看看如何在代码中实现吧。

哈希算法库

首先，我们需要准备几个哈希算法。

这里，我们列出三个比较经典的哈希算法：由Justin Sobel 编写的按位散列函数，由Daniel J. Bernstein教授制作的算法和 Donald E. Knuth在「计算机编程艺术第3卷」中提出的算法。

经典的哈希算法还有很多，这里我们仅取几个比较有代表性的进行使用。其效果都是将字符串转换为固定长度的散列串，然后转换成 0 - 2^32 - 1 之间的一个整数值。以下哈希算法节选自 《布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法》一文，文章写的不错，大家可以进行参考。

HashFunction.php

<?php

/*
 |--------------------------------------------------------------------------
 | 哈希方法类
 |--------------------------------------------------------------------------
*/

namespace App\Services\Common;


class HashFunction
{
    /**
     * 由 Justin Sobel 编写的按位散列函数
     *
     * @param string $string 字符串
     * @param int $len 运算长度
     * @return int
     */
    public static function JSHash(string $string, int $len = 0)
    {
        $hash = 1315423911;

        $len || $len = strlen($string);

        for ($i = 0; $i < $len; $i ++) {
            $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
        }

        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 由 Daniel J. Bernstein 教授制作的算法
     *
     * @param string $string 字符串
     * @param int $len 运算长度
     * @return int
     */
    public static function DJBHash(string $string, int $len = 0)
    {
        $hash = 5381;

        $len || $len = strlen($string);

        for ($i = 0; $i < $len; $i++) {
            $hash = (int)(($hash << 5) + $hash) + ord($string[$i]);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * Donald E. Knuth 在「计算机编程艺术第3卷」中提出的算法
     *
     * @param string $string 字符串
     * @param int $len 运算长度
     * @return int
     */
    public static function DEKHash(string $string, int $len = 0)
    {
        $len || $len = strlen($string);

        $hash = $len;

        for ($i = 0; $i < $len; $i++) {
            $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
        }

        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }
}

布隆过滤器类

接下来，我们需要封装一个布隆过滤器处理类。

该处理类主要包含了初始化（Redis 客户端、bitmap 存储键和哈希函数列表）工作，添加元素到 bitmap 和判断元素是否存在于 bitmap 功能。其核心代码如下：

BloomFilter.php

<?php

/*
 |--------------------------------------------------------------------------
 | 布隆过滤器
 |--------------------------------------------------------------------------
*/

namespace App\Services\Common;

use Illuminate\Support\Facades\Redis;

class BloomFilter
{
   /**
    * @var \Illuminate\Redis\Connections\Connection Redis客户端
    */
    protected $client;

    /**
     * @var string bitmap 存储键
     */
    protected $bucket;

    /**
     * @var array 哈希函数列表
     */
    protected $hashFunctions = [];

    /**
     * 构造方法
     *
     * @param string $connection redis 连接名称
     * @param string $bucket bitmap 存储键
     * @param array $hashFunctions 哈希函数列表
     */
    public function __construct(string $connection = 'default', string $bucket = '', array $hashFunctions = [])
    {
        $this->client = Redis::connection($connection);
        $this->bucket = $bucket;
        $this->hashFunctions = $hashFunctions;
    }

    /**
     * 添加元素到 bitmap
     *
     * @param string $item
     * @return mixed
     * @throws \Exception
     */
    public function add(string $item)
    {
        return $this->client->transaction(function ($redis) use ($item) {
            foreach ($this->getHashFunctions() as $hashFunction) {
                if(!is_callable([HashFunction::class, $hashFunction])){
                    throw new \Exception("哈希函数 [{$hashFunction}] 不可用。");
                }
                $offset = call_user_func_array([HashFunction::class, $hashFunction], [$item]);
                $redis->setbit($this->bucket, $offset, 1);
            }
        });
    }

    /**
     * 判断元素是否存在
     *
     * @param string $item 元素
     * @return bool
     * @throws \Exception
     */
    public function exist(string $item): bool
    {
        $ret = $this->client->transaction(function ($redis) use ($item) {
            foreach ($this->getHashFunctions() as $hashFunction) {
                if(!is_callable([HashFunction::class, $hashFunction])){
                    throw new \Exception("哈希函数 [{$hashFunction}] 不可调用。");
                }
                $offset = call_user_func_array([HashFunction::class, $hashFunction], [$item]);
                $redis->getbit($this->bucket, $offset);
            }
        });

        foreach ($ret as $bit) {
            if ($bit == 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 设置 bitmap 存储键
     *
     * @param string $bucket bitmap 键
     * @return $this
     */
    public function setBucket(string $bucket): BloomFilter
    {
        $this->bucket = $bucket;
        return $this;
    }

    /**
     * 获取 bitmap 存储键
     *
     * @throws \Exception
     * @return string
     */
    public function getBucket(): string
    {
        if(!$this->bucket){
            throw new \Exception('bitmap 存储键未设置');
        }
        return $this->bucket;
    }

    /**
     * 设置哈希函数列表
     *
     * @param array $hashFunctions 哈希函数列表
     * @return $this
     */
    public function setHashFunctions(array $hashFunctions = []): BloomFilter
    {
        $this->hashFunctions = $hashFunctions;
        return $this;
    }

    /**
     * 获取哈希函数列表
     *
     * @throws \Exception
     * @return array
     */
    public function getHashFunctions(): array
    {
        if(empty($this->hashFunctions)){
            throw new \Exception('哈希函数列表未设置');
        }
        return $this->hashFunctions;
    }

}

功能使用

接下来要做的就是将元素添加到 bitmap 中，并判断指定元素是否存在于 bitmap 中。布隆过滤器的应用场景有很多，比如：邮箱黑名单过滤、爬虫 url 判断重复、缓存穿透等。其实原理都差不多，这里我们拿「邮件黑名单过滤」来举例。

比如我们现在有 aaa@163.com 和 bbb@163.com 两个垃圾邮箱需要添加到黑名单中，然后我们分别判断 aaa@163.com ，bbb@163.com 和 ccc@163.com 这几个邮箱是否存在于黑名单中。代码逻辑如下：

// 1. 实例化处理类
$bloomFilter = new BloomFilter();

// 2. 设置 bitmap 存储键和哈希函数列表
$bloomFilter
    ->setBucket('BLOOM_FILTER:JUNK_MAILBOX')
    ->setHashFunctions(['JSHash', 'DJBHash', 'DEKHash']);

// 3. 添加元素到 bitmap
$bloomFilter->add('aaa@163.com');
$bloomFilter->add('bbb@163.com');

// 4. 判断元素是否存在于 bitmap 中
dd(
    $bloomFilter->exist('aaa@163.com'),
    $bloomFilter->exist('bbb@163.com'),
    $bloomFilter->exist('ccc@163.com'),
);

运行代码，结果输出如下：

true
true
false

和我们的预期效果一致。

这样，一个完整的布隆过滤器的功能就实现了，是不是并没有想象中的复杂。

实际上，现在还有很多优秀的布隆过滤器变种方案，这里我们就不在详细讨论了，感兴趣的小伙伴可以自行探索。另外，Redis 自 4.0 版本以后提供了一款 布隆过滤器插件，通过此插件，也可以很方便地使用布隆过滤器的功能，大家也可以研究下，这里我们就不介绍了。

总结

到这里，bitmap 应用之「布隆过滤器」部分我们就介绍完了，用一句话总结一下：

当你遇到需要在「海量」数据中，判断某个元素（可能是整数，也可能是序列化串）是否存在时，不妨考虑使用下「布隆过滤器」。

在下一篇文章《Redis 实用小技巧—— bitmap 应用之「缓存穿透」问题的处理》中，我们将带大家详细了解下「布隆过滤器」的应用之一——如何解决「缓存穿透」的问题。

感谢大家的持续关注～

本作品采用《CC 协议》，转载必须注明作者和本文链接