布隆过滤器实现,解决缓存穿透
其实,我们可以在访问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 fifilter,4G 内存 大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom fifilter 映射为这 340 亿 bit,然后挨个读取另外一个 文件的 url,检查是否与 Bloom fifilter,如果是,那么该 url 应该是共同的 url(注意会有一定的错误率)。
6.解决缓存穿透问题 缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时被动写的,并且出于容错考虑, 如果从存储层查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到存储层去查询,失去了缓存的意 义。在流量大时,可能DB就挂掉了,要是有人利用不存在的key频繁攻击我们的应用,这就是漏洞。
其它: 在比特币中用来判断是不是属于钱包 敏感词判断,在布隆过滤器中查找敏感词 如果用hash,1个亿的邮箱->8G内存 几个亿敏感词,可能几十G内存。 基于bit最小存储单元 + hash函数 + 牺牲一定准确性(能接受) 布隆过滤器说这个词不是个敏感词,那么这个词就肯定不是个敏感词。
布隆过滤器原理
布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的 个数为k假设集合里面有3个元素{x, y, z},哈希函数的个数为3。首先将位数组进行初始化, 将里面每个位都设置位0。对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一 个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时 候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不 存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。注意:此处不能判断该元素是否一定存在集合中, 可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。虽然这3个点都 为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都 是1,这是误判率存在的原因
php+Redis实现的布隆过滤器
由于Redis实现了setbit和getbit操作,天然适合实现布隆过滤器,redis也有布隆过滤器插件。这里使用php+redis实 现布隆过滤器。 首先定义一个hash函数集合类,这些hash函数不一定都用到,实际上32位hash值的用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
本文由:xiasohu168.com 作者:xiaoshu发表,转载请注明来源!