从缓存穿透聊到布隆过滤器

已下线的个人博客 / 1 / 3 / 创建于 5年前 / 更新于 5年前 / 1 个改进

缓存现在在web领域应用广泛，相信大部分开发人员都会用到，然而你遇见过缓存穿透吗？

什么是缓存穿透？

缓存穿透是指查询一个根本不存在的数据，缓存层和存储层都不会命中，但是出于容错的考虑，如果从存储层查不到数据则不写入缓存层。
简单说，就查询一个不存在的key，因为没有缓存，就会去数据库查询，从而达到穿透缓存。增大数据库压力的险恶目的。
一般来说，不是恶意操作，正常来说，不会遇到这样的问题，然而，怕的就是一些险恶用心的攻击者。那么，我们如何有效处理这种问题呢？
简单想一下，如果我们把有效的key集合起来，查询之前我们先判断一下查询的key是否在集合中，如果不在，直接打回去，让你调皮。这个问题不就解决了吗？
但是，如果真的先把所有key组成集合，那这个存储占用的内存太大了，当有1亿个key，那存储空间也是相当可观的，有点太过浪费了。
为了不浪费，我跟你说，有一个小玩意叫“布隆过滤器”，它能帮你节省空间，节省钱。

布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
按上面的问题，我们可以把所有的key通过特定的算法，存储到这种二进制向量中，我们来看网上的一张图。

从缓存穿透聊到布隆过滤器

我们可以通过三个哈希算法将w存储到二进制向量，当查询w是否存在时，我们可以再通过这三个算法，如果算法算出来所在的位置均为1，则表示w可能存在（注意是可能存在），否则一定不存在。（这个很好理解，我就不做说明了）

说了这么多，我们来尝试下代码：

<?php
/**
 * Author: sai
 * Date: 2019/5/17
 * Time: 14:10
 * 代码来自网络，有改动
 */
class BloomFilterHash
{
    /**
     * 由Justin Sobel编写的按位散列函数
     */
    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));
        }
//        var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 该哈希算法基于AT＆T贝尔实验室的Peter J. Weinberger的工作。
     * Aho Sethi和Ulman编写的“编译器（原理，技术和工具）”一书建议使用采用此特定算法中的散列方法的散列函数。
     */
    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;
        $test = 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));
    }
//    var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 类似于PJW Hash功能，但针对32位处理器进行了调整。它是基于UNIX的系统上的widley使用哈希函数。
     */
    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;
        }
//        var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
     * 它是一个简单的哈希函数，使用一组奇怪的可能种子，它们都构成了31 .... 31 ... 31等模式，它似乎与DJB哈希函数非常相似。
     */
    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]));
        }
//        var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这是在开源SDBM项目中使用的首选算法。
     * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况。
     */
    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);
        }
//        var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 由Daniel J. Bernstein教授制作的算法，首先在usenet新闻组comp.lang.c上向世界展示。
     * 它是有史以来发布的最有效的哈希函数之一。
     */
    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]);
        }
        var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法，主题是排序和搜索第6.4章。
     */
    public function DEKHash($string, $len = null)
    {
        $len || $len = strlen($string);
        $hash = $len;
        for ($i=0; $i<$len; $i++) {
            $hash = (int) (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
        }
//        var_dump((int)($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
     */
    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]);
        }
//        var_dump(($hash % 0xFFFFFFFF) & 0xFFFFFFFF);die;
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }
}

/**
 * 使用redis实现的布隆过滤器
 */
abstract class BloomFilterRedis
{
    /**
     * 需要使用一个方法来定义bucket的名字
     */
    protected $bucket;

    protected $hashFunction;

    public function __construct()
    {
        if (!$this->bucket || !$this->hashFunction) {
            throw new Exception("需要定义bucket和hashFunction", 1);
        }
        $this->Hash = new BloomFilterHash;
        $this->Redis = self::getRedis(); //假设这里你已经连接好了
    }

    public static function getRedis()
    {
        $redis = new Redis();
        $redis->connect('127.0.0.1', 6379);
//        $redis->auth('13sai666.');
//        var_dump($redis->info('SERVER'));die;
        $redis->select(7);
        return $redis;
    }

    /**
     * 添加到集合中
     */
    public function add($string)
    {
        foreach ($this->hashFunction as $key=>$function) {
            $hash = $this->Hash->$function($string);
            $this->Redis->setBit($this->bucket.$key, $hash, 1);
        }
        return true;
    }

    /**
     * 查询是否存在, 不存在的一定不存在, 存在有一定几率会误判（hash冲突）
     */
    public function exists($string)
    {
        $pipe = $this->Redis->multi();
        $len = strlen($string);
        foreach ($this->hashFunction as $key=>$function) {
            $hash = $this->Hash->$function($string, $len);
            $pipe = $pipe->getBit($this->bucket.$key, $hash);
        }

        $res = $pipe->exec();
//        var_dump($res);
        foreach ($res as $bit) {
            if ($bit == 0) {
                return false;
            }
        }
        return true;
    }
}

/**
 * 重复内容过滤器
 * 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数)
 *
 * 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空.
 */
class FilteRepeatedComments extends BloomFilterRedis
{
    /**
     * 表示判断重复内容的过滤器
     * @var string
     */
    protected $bucket = 'bulong';

    protected $hashFunction = ['FNVHash', 'JSHash', 'ELFHash'];
}

可以调用测试下，

var_dump((new FilteRepeatedComments())->add('abc')); //true
var_dump((new FilteRepeatedComments())->add('bcd'));//true
var_dump((new FilteRepeatedComments())->add('dfg'));//true
var_dump((new FilteRepeatedComments())->exists('dfg'));//true
var_dump((new FilteRepeatedComments())->exists('dgg'));//false

简单的测试通过！
当然，应用时需要进行更多的测试。
那么这个叫“布隆过滤器”的东东真有那么好用？
我相信，你应该可以看出来，这是有误判率的，另外删除也是困难的。

具体误判推导过程，可以参考：
布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法
 布隆过滤器简介 - Jack47 - 博客园

应用场景：

垃圾邮件过滤
爬虫的url过滤
防止缓存击穿

好了，就介绍到这里啦！如有兴趣，还有布谷鸟过滤器。

博客地址：http://blog.13sai.com/essay/188

缓存布隆过滤器 redis

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

本帖由系统于 4年前自动加精

已下线

Laravel 8.x 译者 601 声望

CTO @ yunji

暂无个人描述~

6 人点赞

讨论数量: 3

nihao123

0 声望

为什么第4条，我打印出来是false？
1、var_dump((new FilteRepeatedComments())->add('abc')); //true
2、var_dump((new FilteRepeatedComments())->add('bcd'));//true
3、var_dump((new FilteRepeatedComments())->add('dfg'));//true
4、var_dump((new FilteRepeatedComments())->exists('dfg'));//true
5、var_dump((new FilteRepeatedComments())->exists('dgg'));//false

5年前评论

已下线（楼主）

可以尝试把hash出来的值和插入结果打印一下，猜测是某一个setBit失败了

tubaibai

大概是因为 hash 生成的值超出了2^32的大小所以 setBit 失败了，我也是卡这儿不知道怎么办了 = =

nihao123

0 声望

同样的代码，和你打印出来结果不一样

5年前评论

tubaibai

0 声望

大概是因为 hash 生成的值超出了2^32的大小所以 setBit 失败了，我也是卡这儿不知道怎么办了哈哈哈

3年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

从缓存穿透聊到布隆过滤器

什么是缓存穿透？

布隆过滤器

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

从缓存穿透聊到布隆过滤器

什么是缓存穿透？

布隆过滤器

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录