关于redis:Redis布隆过滤器分析与总结

问题引入

问题一: 本来有 10 亿个号码，当初又来了 10 万个号码，要疾速精确判断这 10 万个号码是否在 10 亿个号码库中？

问题二: 接触过爬虫的，应该有这么一个需要，须要爬虫的网站千千万万，对于一个新的网站 url，咱们如何判断这个 url 咱们是否曾经爬过了？

问题三: 一个邮件系统，有上亿的邮件数量，咱们要检测某一个邮箱是否正确发送了邮件信息？

问题四: 提到 Redis 做缓存查问，咱们须要思考几个问题，缓存穿透、缓存击穿和缓存雪崩。咱们该如何解决缓存这种缓存问题呢？

布隆过滤

布隆过滤器其实就是，一种数据结构，是由一串很长的二进制向量组成，能够将其看成一个二进制数组。既然是二进制，那么外面寄存的不是 0，就是 1，然而初始默认值都是 0。

大抵的数据结构如下图:

增加数据:

向布隆过滤器中增加 key 时，会应用多个 hash 函数对 key 进行 hash 算得一个整数索引值而后对位数组长度进行取模运算失去一个地位，每个 hash 函数都会算得一个不同的地位。再把位数组的这几个地位都置为 1 就实现了 add 操作。

获取数据时:

只须要将这个新的数据通过下面自定义的几个哈希函数，别离算出各个值，而后看其对应的中央是否都是 1，如果存在一个不是 1 的状况，那么咱们能够说，该新数据肯定不存在于这个布隆过滤器中。

Redis 配置

在 Redis 中要应用布隆过滤器，能够间接参照该文档, 文档地址

举荐应用 docker 应用形式，如果要编译成 so 动静库，则须要运行在 Linux 环境中。

// 装置
docker run -p 6377:6379 --name redis-redisbloom redislabs/rebloom:latest

装置完之后，查看 docker 容器。

进入 Redis 容器，并查看容器模块状态。

# 进入容器
docker exec -it 4a695ead6577 /bin/sh
# 登录到 Redis
redis-cli
# 查看 Redis 模块
127.0.0.1:6379> info Modules
# Modules
module:name=bf,ver=20205,api=1,filters=0,usedby=[],using=[],options=[]

操作演示

增加数据

// 单个增加
127.0.0.1:6379> bf.add blkey 1
(integer) 1
127.0.0.1:6379> bf.add blkey 2
(integer) 1
127.0.0.1:6379> bf.add blkey 2
(integer) 0
127.0.0.1:6379> bf.add blkey 3
(integer) 1
127.0.0.1:6379> bf.add blkey 4
(integer) 1

// 批量增加
127.0.0.1:6379> bf.madd blkey 5 6 7 8 4
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 0

通过增加会发现，如果元素曾经存在，则返回的是 0 值。

检测数据

// 检测单个值
127.0.0.1:6379> bf.exists blkey 1
(integer) 1
127.0.0.1:6379> bf.exists blkey 2
(integer) 1
127.0.0.1:6379> bf.exists blkey 3
(integer) 1

// 批量检测
127.0.0.1:6379> bf.mexists blkey 1 2 3 4 5 10
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
6) (integer) 0

通过演示会发现，如果元素不存在，则返回的是 0 值。

代码演示

这里用 composer 来对 Redis 布隆过滤器进行操作。官网也列举了几种编程语言的客户端。

文档地址

composer require palicao/php-rebloom

<?php
declare(strict_types=1);

namespace App\Http\Controllers\Redis;

use Illuminate\Http\Request;
use Palicao\PhpRebloom\BloomFilter;
use Palicao\PhpRebloom\RedisClient;
use Palicao\PhpRebloom\RedisConnectionParams;
use Redis;

/**
 * Redis 布隆过滤器
 * Class BloomFilterController
 * @package App\Http\Controllers\Redis
 */
class BloomFilterController
{
    private $request;

    private $host = '192.168.0.112';

    private $port = 6377;

    private $bloomFilter;

    public function __construct(Request $request)
    {$this->request     = $request->all();
        $this->bloomFilter = new BloomFilter(
            new RedisClient(new Redis(),
                new RedisConnectionParams($this->host, $this->port)
            )
        );
    }

    /**
     * 增加删除数据
     * @throws \RedisException
     * @author kert
     */
    public function index()
    {
        // 文章:https://www.cnblogs.com/ysocean/p/12594982.html

        /** @var string $cacheKey 缓存 key */
        $cacheKey = 'bloom';
        /** @var int $cacheValue 缓存 value */
        $cacheValue = mt_rand(0, 100);
        // 单个增加缓存
        var_dump('插入缓存', $this->bloomFilter->insert((string)$cacheKey, (string)$cacheValue));
        // 单个查问缓存
        var_dump('验证缓存', $this->bloomFilter->exists((string)$cacheKey, (string)$cacheValue));

        /** @var array $batchCacheValue 批量缓存 value */
        $batchCacheValue = [mt_rand(0, 100), mt_rand(0, 100), mt_rand(0, 100), mt_rand(0, 100), mt_rand(0, 100)];
        // 批量增加缓存
        var_dump('批量插入缓存', $this->bloomFilter->insertMany((string)$cacheKey, $batchCacheValue));
        // 批量获取缓存
        var_dump('批量验证缓存', $this->bloomFilter->manyExist((string)$cacheKey, $batchCacheValue));
    }
}

内存比照

这里咱们通过模仿邮件发送来比照布隆过滤器和汇合各自占用的内存比照。

布隆过滤器

public function email()
{
    /** @var string $cacheKey 缓存 key */
    $cacheKey = 'bloom:email';
    /** @var array $email 缓存邮箱数据 */
    $emailArray = [];
    for ($i = 0; $i < 1000; $i++) {array_push($emailArray, $i . 'wangyi@163.com');
    }
    /** @var array $insertResult 插入后果 */
    $insertResult = $this->bloomFilter->insertMany((string)$cacheKey, $emailArray);
    foreach ($insertResult as $value) {if ($value === false) {echo '插入失败' . PHP_EOL;}
    }
    /** @var array $queryResult 查问后果 */
    $queryResult = $this->bloomFilter->manyExist((string)$cacheKey, $emailArray);
    foreach ($queryResult as $value) {if ($value === false) {echo '查问失败' . PHP_EOL;}
    }
}

汇合

public function emailSet()
{
    /** @var string $cacheKey 缓存 key */
    $cacheKey = 'set:email';
    /** @var array $email 缓存邮箱数据 */
    $emailArray = [];
    for ($i = 0; $i < 1000; $i++) {array_push($emailArray, $i . 'wangyi@163.com');
    }
    $redis = new Redis();
    $redis->connect($this->host, $this->port);
    var_dump($redis->sAddArray($cacheKey, $emailArray));
}

内存比照

/**
 *  初始内存:854.40K
 *  布隆过滤器:857.50K ~3k
 *  汇合:912.52K ~55k
 */

通过比照发现，同样的邮箱数量，应用 set 的形式比应用过滤器的形式，内存至多多应用 18 倍多。

案例解决

在文章结尾，咱们引入了几个问题？首先咱们想到的第一个技术计划就是通过数据库查问。这样数据更加精确。然而咱们须要思考一个问题，如果数据量很大，没查问一次都走数据库，无疑是给数据库减少了累赘。

如果咱们通过布隆过滤器来实现，既能解决咱们理论的需要，也能解决数据库压力过重的状况。

上面演示代码实现逻辑。

/**
* 检测某一个手机号是否曾经发送短信内容
* @author kert
*/
public function filterMobile()
{
    /** @var string $cacheKey 缓存 key */
    $cacheKey = 'bloom:mobile';
    /** @var array $email 缓存手机号数据 (模仿发送过的手机号) */
    $mobileArray = [];
    for ($i = 0; $i < 1000; $i++) {array_push($mobileArray, substr(md5((string)$i), 0, 11));
    }
    // 插入布隆过滤器
    $this->bloomFilter->insertMany((string)$cacheKey, $mobileArray);
    // 检测某一个值是否存在
    var_dump($this->bloomFilter->exists((string)$cacheKey, (string)substr(md5((string)100), 0, 11)));
    // output bool(true)
}

通过下面的演示，咱们不难看出，布隆过滤在对数据检测是否存在的状况，要比走数据库好很多。

优缺点剖析

1. 通过下面内存比照的内容，以及对布隆过滤器实现原理、存储数据格式的理解，咱们能够得出布隆过滤器能够节俭内存，尤其是数据大的状况下。
2. 布隆过滤器是不反对删除数据的，如果须要删除数据则须要重建缓存信息。
3. 布隆过滤器应用屡次 hash 计算，也会存在 hash 抵触状况。这几会导致一个问题，当检测过滤器是否存在数据时，检测到存在，理论不肯定存在。同时检测到不存在，则缓存中肯定不存在。

总结

布隆过滤器节俭内存，然而也存在一种误差。对于开篇提到的几个案例场景是一种十分不错的抉择。