布隆过滤器

一、概述

1、概念

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,它是一种比较巧妙的概率型数据结构,特点是高效地插入和查询。

布隆过滤器用于判断一个元素一定不存在于这个空间,比如黑名单系统。

2、布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:

如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:

Ok,我们现在再存一个值 “tencent”,如果哈希函数返回 3、4、8 的话,图继续变为:

值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。

当我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。

而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

这是为什么呢?答案很简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

3、布隆过滤器处理流程

第一步:开辟空间

开辟一个长度为m的位数组(或者称二进制向量),这个不同的语言有不同的实现方式,甚至你可以用文件来实现。

第二步:寻找hash函数

获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了。

第三步:写入数据

将所需要判断的内容经过这些hash函数计算,得到几个值,比如用3个hash函数,得到值分别是1000,2000,3000。之后设置m位数组的第1000,2000,3000位的值位二进制1。

第四步:判断

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。可以对比上面的布隆过滤器数据结构,你可能会有更清晰的认识。

 

 

4、如何选择哈希函数个数和布隆过滤器长度

很显然,过小的布隆过滤器很快所有的 bit 位就会都被置为 1,那么查询任何值都会返回“可能存在”,也就起不到过滤的目的了。

布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置为 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

5、布隆过滤器的优缺点

优点:

使用更小的空间和更高的效率进行判断。

缺点:

存在一定的误判,并且不能删除元素。

注:想解决Bloom Filter 中不能删除元素的问题,可以使用 Counting Bloom Filter,它是网上提出来的 Bloom Filter 的改进版,Bloom Filter 本身只有0或1,而Bloom Filter 采用的是计数,比如0,4,9 等,删除元素,就将对应的bit位上值减1,这里不做过多介绍,实际生产中,采用这种方案的人也不多。

6、应用场景

(1)黑名单系统

(2)缓存穿透

二、代码实现

由于Redis实现了setbit和getbit操作,天然适合实现布隆过滤器,redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器。

1、BloomFilterHash.php (hash函数类)
<?php
declare(strict_types = 1);

/*
 * hash函数集合类,用于布隆过滤器使用
 */
class BloomFilterHash
{
    /**
     * 由Justin Sobel编写的按位散列函数
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function JSHash($string, $len = null)
    {
        $hash = 1315423911;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {
            $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 该哈希算法基于AT&T贝尔实验室的Peter J. Weinberger的工作。
     * Aho Sethi和Ulman编写的“编译器(原理,技术和工具)”一书建议使用采用此特定算法中的散列方法的散列函数。
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function PJWHash($string, $len = null)
    {
        $bitsInUnsignedInt = 4 * 8; //(unsigned int)(sizeof(unsigned int)* 8);
        $threeQuarters = ($bitsInUnsignedInt * 3) / 4;
        $oneEighth = $bitsInUnsignedInt / 8;
        $highBits = 0xFFFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth);
        $hash = 0;
        $len || $len = strlen($string);
        for($i=0; $i<$len; $i++) {
            $hash = ($hash << (int) ($oneEighth)) + ord($string[$i]);
        }
        $test = $hash & $highBits;
        if ($test != 0) {
            $hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 类似于PJW Hash功能,但针对32位处理器进行了调整。它是基于UNIX的系统上的widley使用哈希函数。
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function ELFHash($string, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {
            $hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xF0000000;
            if ($x != 0) {
                $hash ^= ($x >> 24);
            }
            $hash &= ~$x;
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
     * 它是一个简单的哈希函数,使用一组奇怪的可能种子,它们都构成了31 .... 31 ... 31等模式
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function BKDRHash($string, $len = null)
    {
        $seed = 131;  # 31 131 1313 13131 131313 etc..
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {
            $hash = (int) (($hash * $seed) + ord($string[$i]));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这是在开源SDBM项目中使用的首选算法。
     * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况。
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function SDBMHash($string, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {
            $hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 由Daniel J. Bernstein教授制作的算法,首先在usenet新闻组comp.lang.c上向世界展示。
     * 它是有史以来发布的最有效的哈希函数之一。
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function DJBHash($string, $len = null)
    {
        $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卷”中提出的算法,主题是排序和搜索第6.4章。
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function DEKHash($string, $len = null)
    {
        $len || $len = strlen($string);
        $hash = $len;
        for ($i=0; $i<$len; $i++) {
            $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
     *
     * @param $string
     * @param null $len
     * @return int
     */
    public function FNVHash($string, $len = null)
    {
        $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619
        $hash = 2166136261; //32位的offset
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {
            $hash = (int) ($hash * $prime) % 0xFFFFFFFF;
            $hash ^= ord($string[$i]);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }
}

2、BloomFilterRedis.php (redis 添加、查询元素到/从 布隆过滤器)
<?php
declare(strict_types = 1);

include_once 'BloomFilterHash.php'; // 项目中请用use替代

/**
 * 使用redis实现的布隆过滤器
 */
class BloomFilterRedis
{

    protected $bucket; // 定义bucket的名字
    protected $hashFunction; // 定义使用的hash方法
    protected $Hash;
    protected $Redis;

    /**
     * BloomFilterRedis constructor.
     * @param string $bucket
     * @param array $hashFunction
     */
    public function __construct(string $bucket, array $hashFunction)
    {
        $this->bucket = $bucket;
        $this->hashFunction = $hashFunction;
        $this->Hash = new BloomFilterHash;
        $this->Redis = $this->getRedis();
    }

    /**
     * 添加到集合中
     *
     * @param $string
     * @return array
     */
    public function add($string)
    {
        $pipe = $this->Redis->multi();
        foreach ($this->hashFunction as $function) {
            $hash = $this->Hash->$function($string);
            $pipe->setBit($this->bucket, $hash, true);
        }
        return $pipe->exec();
    }

    /**
     * 查询是否存在(存在的一定会返回true, 不存在有一定几率返回true,但如果返回false,则说明一定不存在)
     *
     * @param $string
     * @return bool
     */
    public function exists($string)
    {
        $pipe = $this->Redis->multi();
        $len = strlen($string);
        foreach ($this->hashFunction as $function) {
            $hash = $this->Hash->$function($string, $len);
            $pipe = $pipe->getBit($this->bucket, $hash);
        }
        $res = $pipe->exec();
        if (in_array(0, $res)) {
            return false;
        }
        return true;
    }

    /**
     * 设置redis连接
     *
     * @return Redis
     */
    private function getRedis()
    {
        $redis = new Redis();
        $redis->connect('127.0.0.1', 6379);
        $redis->auth('haveyb');
        $redis->select(8);
        return $redis;
    }

}
3、index.php (测试文件)
<?php
declare(strict_types = 1);

include_once 'BloomFilterRedis.php'; // 在项目中应该使用use自动加载

// 定义key,并自行从hash函数集中选取几个方法
$object = new BloomFilterRedis('test_bloom', ['JSHash', 'DJBHash', 'ELFHash']);
$object->add('老迟笔记');
$object->add('DockerHub');

// 添加元素到布隆过滤器
var_dump($object->exists('老迟笔记')); // true
echo '<br>';
var_dump($object->exists('DockerHub')); // true
echo '<br>';
var_dump($object->exists('SiNa')); // false

注:使用上面的方法可以存储 2^32 个元素