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 (上)》的开篇,我们举的那个例子吗?

le0poZ6DHQ.webp!large

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

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

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

你又补充道:我儿子今年 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.combbb@163.com 两个垃圾邮箱需要添加到黑名单中,然后我们分别判断 aaa@163.combbb@163.comccc@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 协议》,转载必须注明作者和本文链接
你应该了解真相,真相会让你自由。
本帖由 MArtian 于 1年前 加精
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 10

都是干货呀

1年前 评论
快乐的皮拉夫 (楼主) 1年前
1年前 评论
快乐的皮拉夫 (楼主) 1年前
荭尘宝宝 (作者) 1年前

支持,非常实用。

1年前 评论

:grin: :see_no_evil:

1年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
文章
38
粉丝
110
喜欢
653
收藏
719
排名:273
访问:3.5 万
私信
所有博文
社区赞助商