Redis

首页 -  Redis  -  布隆过滤器实现 解决缓存穿透

布隆过滤器实现 解决缓存穿透

布隆过滤器实现,解决缓存穿透

其实,我们可以在访问mysql之前,先访问一下布隆过滤器。布隆过滤器能够判断某个值的存在情况, 如果布隆过滤 器说-1这个值不存在, 那么这个肯定就不存在,这时候, 我们就没必要访问mysql了。 这样就成功把这些对mysql的恶意攻击进行过滤。

布隆过滤器场景

1.Google著名的分布式数据库Bigtable以及Hbase使用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的IO 次数。 

2.检查垃圾邮件地址 假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向 量,然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X,我们用八个不同的随机数产生器(F1,F2, ...,F8) 产生八个信息指纹(f1, f2, ..., f8)。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个 自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处 理后。一个针对这些 email 地址的布隆过滤器就建成了。 

3.Google chrome 浏览器使用bloom fifilter识别恶意链接(能够用较少的存储空间表示较大的数据集合,简单的想就 是把每一个URL都可以映射成为一个bit) 

4.文档存储检索系统也采用布隆过滤器来检测先前存储的数据 

5.爬虫URL地址去重 A,B 两个文件,各存放 50 亿条 URL,每条 URL 占用 64 字节,内存限制是 4G,让你找出 A,B 文件共同的 URL。如果是三个乃至 n 个文件呢? 分析 :如果允许有一定的错误率,可以使用 Bloom fifilter4G 内存 大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom fifilter 映射为这 340 亿 bit,然后挨个读取另外一个 文件的 url,检查是否与 Bloom fifilter,如果是,那么该 url 应该是共同的 url(注意会有一定的错误率)。 

6.解决缓存穿透问题 缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时被动写的,并且出于容错考虑, 如果从存储层查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到存储层去查询,失去了缓存的意 义。在流量大时,可能DB就挂掉了,要是有人利用不存在的key频繁攻击我们的应用,这就是漏洞。

其它: 在比特币中用来判断是不是属于钱包 敏感词判断,在布隆过滤器中查找敏感词 如果用hash1个亿的邮箱->8G内存 几个亿敏感词,可能几十G内存。 基于bit最小存储单元 + hash函数 + 牺牲一定准确性(能接受) 布隆过滤器说这个词不是个敏感词,那么这个词就肯定不是个敏感词。

布隆过滤器原理

布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的 个数为k假设集合里面有3个元素{x, y, z},哈希函数的个数为3。首先将位数组进行初始化, 将里面每个位都设置位0。对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一 个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时 候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不 存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。注意:此处不能判断该元素是否一定存在集合中, 可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4563个点。虽然这3个点都 1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都 1,这是误判率存在的原因

php+Redis实现的布隆过滤器

由于Redis实现了setbitgetbit操作,天然适合实现布隆过滤器,redis也有布隆过滤器插件。这里使用php+redis现布隆过滤器。 首先定义一个hash函数集合类,这些hash函数不一定都用到,实际上32hash值的用3个就可以了,具体的数量可 以根据你的位序列总量和你需要存入的量决定,上面已经给出最佳值。

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));
        }
        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)); }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; }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]));
        }
        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);
        }
        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]);
        }
        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 = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
        }
        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]); 
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; 
    } 
}

接着就是连接redis来进行操作

abstract class BloomFilterRedis
{
    /*** 需要使用一个方法来定义bucket的名字 */
    protected $bucket;
    protected $hashFunction;

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

    /*** 添加到集合中 */
    public function add($string)
    {
        $pipe = $this->Redis->multi();
        foreach ($this->hashFunction as $function) {
            $hash = $this->Hash->$function($string);
            #redis是支持位向量数据结构的
            $pipe->setBit($this->bucket, $hash, 1);
        }
        return $pipe->exec();
    }
    /*** 查询是否存在, 如果曾经写入过,必定回true,如果没写入过,有一定几率会误判为存在 */
    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();
        foreach ($res as $bit) {
            if ($bit == 0) {
                return false;
            }
        }
        return true;
    }
}

上面定义的是一个抽象类,如果要使用,可以根据具体的业务来使用。比如下面是一个过滤重复内容的过滤器。

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

利用插件实现:centos中安装redis插件

nux上安装redis就不说了,主要说redis安装插件布隆过滤器。 

步骤: 

1.下载redisbloom插件(redis官网下载即可) https://github.com/RedisLabsModules/redisbloom/

找到最新的tag下载tar.gz格式即可;

 wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

2.解压并安装,生成.so文件

[root@101 ext]# tar -zxvf v1.1.1.tar.gz [
root@101 ext]# cd RedisBloom-1.1.1/ 
[root@101 RedisBloom-1.1.1]# make 
[root@101 RedisBloom-1.1.1]# ls 
contrib Dockerfile docs LICENSE Makefile mkdocs.yml ramp.yml README.md rebloom.so src tests

3.redis配置文件(redis.conf)中加入该模块即可

[root@yangwenjiong-centos etc]# cd /etc/redis/
[root@yangwenjiong-centos redis]# ls redis.conf

4.配置文件加入模块代码

[root@redis]# vim redis.conf
 #####################MODULES#################### 
 # Load modules at startup. If the server is not able to load modules 
 # it will abort. It is possible to use multiple 
 loadmodule directives. loadmodule /usr/local/redis/redisbloom-1.1.1/rebloom.so 
 #INITIAL_SIZE 800000 ERROR_RATE 0.1
 #位向量长度100M,误差率千分之一(百分之0.1)

5.启动redis即可

[root@redis]# redis-server redis.conf

6.测试是否安装成功

redis-cli shutdown
主要命令有 
bf.add 添加元素
bf.exists 查询元素是否存在 
bf.madd 一次添加多个元素 
在 redis 中有两个值决定布隆过滤器的准确率:
error_rate:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。 
initial_size:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。 
redis 中有一个命令可以来设置这两个值:示例: php-redis扩展中有个函数可以调用原始的redis指令: 添加:在向redis set值的之后,调用bf.add添加到过滤器。 检查:在穿过了redis去到Mysql之前,调用bf.exists检查 一下,如果不存在。 布隆过滤器可以用在查询和写入分开的业务模式下,一个业务会把key写入redis和BF,另一个业务来搜索查找这个 key。 如果get和set在同一个地方就不能用BF啦。 6 解决本节刚开始提出的缓存穿透问题 这里我们按着本节5.2的方式来实现,实现起来相对简单些 bf.reserve test 0.1 100000000 第一个值是过滤器的名字。 第二个值为 error_rate 的值。 第三个值为 initial_size 的值。 注意必须在add之前使用bf.reserve指令显式创建,如果对应的 key 已经存在,bf.reserve会报错。同时设置的错误率 越低,需要的空间越大。如果不使用 bf.reserve,默认的error_rate是 0.01,默认的initial_size是 100。

示例:

 #新建一个过滤器
 bf.reserve test 0.1 100000000 
 # test是布隆过滤器名称,0.1是误判率,100000000是位向量长度 
 #向过滤器中添加元素 
 127.0.0.1:6379> bf.add test abc123 #test是布隆过滤器名称,abc123是需要判断的元素 
 #判断元素是否在过滤器中 
 127.0.0.1:6379> bf.exists test abc123 #test是布隆过滤器名称,abc123是需要判断的元素 1

php-redis扩展中有个函数可以调用原始的redis指令:

$redis = new \Redis(); 
$redis->connect('127.0.0.1', 6379); 
$re = $redis->rawCommand('bf.exists', 'test', 'abc12345'); 
var_dump($re);

解决缓存穿透问题

$redis = new \Redis(); 
$redis->connect('127.0.0.1', 6379); 
//先看看布隆过滤器中验证数据是否存在, 如果布隆过滤器说没有,那就肯定没有 
$re = $redis->rawCommand('bf.exists', 'goods_sku_code', '商品编码123456abcdefg'); 
if($re == 0){ die("商品编码不存在"); }else{//这里写查询mysql代码 }

插入mysql时,同时同步到布隆过滤器

$redis = new \Redis(); 
$redis->connect('127.0.0.1', 6379); 
//先看看布隆过滤器中验证数据是否存在, 如果布隆过滤器说没有,那就肯定没有 
$redis->rawCommand('bf.add', 'goods_sku_code', '商品编码123456abcdefg'); 
//这里写插入mysql代码

附,redis位向量数据结构,是基于最小数据单元bit的,如下是redis位向量bit存储示例:

127.0.0.1:6379> setbit k 10 1 #设置1 
127.0.0.1:6379> getbit k 10 #得到1


(0)
分享:

本文由:xiasohu168.com 作者:xiaoshu发表,转载请注明来源!

相关阅读