亿级数据判断 bitmap-布隆过滤器

缓存穿透

假设我们使用redis缓存了商品信息,当我们请求进来时,首先经过的是redis,当redis不存在时,才会去查找mysql.然后将mysql的数据缓存到redis.

整个流程看上去是没有任何问题的,但当前端在同一时间发生了大量请求,同时去请求一个redis,数据库都不存在的商品id,会发生什么情况呢?

1: 先去访问redis,发现redis不存在缓存

2: 查询mysql.mysql不存在缓存,则无法进行redis缓存

3: 下一次请求继续循环.....

这个情况,由于redis无法缓存数据,导致每次请求都会直接到数据库,数据库压力剧增,导致宕机.

短网址判断

短网址服务大家都应该比较熟悉,

如果有个短网址服务,现在存储了1亿条短网址.

当你访问 1.cn/arhwqwqwe  这串字符时

同缓存穿透,短网址服务器会先去请求redis缓存,当redis缓存不存在时,请求mysql数据库.....

bitmap

布隆过滤器基于  大数据存储处理-bitmap的艺术

通过 目标数据的 标识hash为位的下标,目标数据存在则为1,不存在则为0

例如:

1,3,5,6,7    5个值,在bitmap中表示为:

二进制表示为:(从右往左)

0b11101010

如果我们需要判断id 2是否存在,只需要根据2所在的位置去判断即可:

$bitmap = 0b11101010;
$goodsId = 3;
$bitToNum = 1 << $goodsId;//算出这个数字的二进制位数
echo "goodsId 2的二进制:" . decbin($bitToNum), PHP_EOL;
$tempNum = $bitmap & $bitToNum;
echo "位运算结果:" . decbin($tempNum), PHP_EOL;

if ($tempNum != $bitToNum) {
    echo "商品id:{$goodsId}不存在\n";
}else{
    echo "商品id:{$goodsId}存在\n";
}

看到这里,是不是发现有点熟悉?没错,这个是我从大数据存储处理-bitmap的艺术 复制过来的代码,可以看出,如果是商品id这种id类型的,可以直接使用bitmap判断存在或者不存在,那布隆过滤器呢?

布隆过滤器

布隆过滤器是一个非常长的bitmap组成,通过随机散列函数,将数据随机映射到bitmap的位置中.

它的存储步骤为:

1: 创建一个足够大的bitmap,例如10亿

2: 将需要判断的key,通过hash 映射函数,例如(md5(key)%10亿),将其指定到bitmap的一个位置中

3: 将bitmap该位置置为1

它的判断步骤为:

1: 将需要判断的key,通过hash映射函数,例如(md5(key)%10亿),获取其指定位置.

2: 找到bitmap的该位置,如果为0,则代码该key一定不存在,如果为1,则可能存在

php实现代码:(本文的hash函数用的是php自带的crc32算法)

<?php
/**
 * Created by PhpStorm.
 * User: xdd
 * Date: 2020/9/21
 * Time: 10:23
 */

/**
 * Created by PhpStorm.
 * User: apple
 * Date: 2020-04-30
 * Time: 14:25
 */
class BloomFilter
{
    //由于php的int为64位,如果要存储10亿,或者更大的数据,需要通过多个int数组实现
    protected $bitmap = [];
    //一个int,只能表示0-64的数字
    //10亿的数字
    protected $maxNum = 1 << 30;

    function add($key)
    {
        $hash = $this->hash($key);
        $bitmapKey = $this->getBitmapKey($hash);

        if (isset($this->bitmap[$bitmapKey])) {
            //如果已经添加了这个数组,则直接与运算将数据加上
            $this->bitmap[$bitmapKey] = $this->bitmap[$bitmapKey] | (1 << ($hash % 64));
        } else {
            $this->bitmap[$bitmapKey] = 1 << ($hash % 64);
        }
        return $hash;
    }

    function get($key)
    {
        $hash = $this->hash($key);
        $bitmapKey = $this->getBitmapKey($hash);

        if (isset($this->bitmap[$bitmapKey])) {
            $bitToNum = 1 << ($hash % 64);//算出这个数字的二进制位数
            $tempNum = $this->bitmap[$bitmapKey] & $bitToNum;
            if ($tempNum != $bitToNum) {
                return false;
            }
            return true;
        } else {
            return false;
        }
    }

    function hash($key)
    {
        $hash = crc32($key);
        //time33返回的数据是0-2^31,目前我们的设想是只存储2^30,所以取余
        $hash = $hash % $this->maxNum;
        return $hash;
    }

    function getBitmapKey($data)
    {
        $key = intval($data / 64);
        return $key;
    }
}


$bloomFilter = new BloomFilter();
$str = "测试1234";
$hash = $bloomFilter->add($str);

var_dump($bloomFilter->get($str));
var_dump($bloomFilter->get('213312'));

注意事项

需要注意的是,

布隆过滤器  重复率依靠的是hash算法,所以越完善的hash算法,分配的数据越均匀,冲突率越低

同时,布隆过滤器只能验证一个值 一定不存在或可能存在

应用场景

1:url短网址生成判断,如果不存在,则代表该url一定没有生成过,可以直接返回404

2:恶意url判断,如果存在,则表示该url可能有问题,可以进一步过滤判断

3:解决上面说的缓存穿透问题