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

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

什么是缓存穿透?

缓存穿透是指查询一个根本不存在的数据,缓存层和存储层都不会命中,但是出于容错的考虑,如果从存储层查不到数据则不写入缓存层。
简单说,就查询一个不存在的key,因为没有缓存,就会去数据库查询,从而达到穿透缓存。增大数据库压力的险恶目的。

一般来说,不是恶意操作,正常来说,不会遇到这样的问题,然而,怕的就是一些险恶用心的攻击者。那么,我们如何有效处理这种问题呢?

简单想一下,如果我们把有效的key集合起来,查询之前我们先判断一下查询的key是否在集合中,如果不在,直接打回去,让你调皮。这个问题不就解决了吗?

但是,如果真的先把所有key组成集合,那这个存储占用的内存太大了,当有1亿个key,那存储空间也是相当可观的,有点太过浪费了。

为了不浪费,我跟你说,有一个小玩意叫“布隆过滤器”,它能帮你节省空间,节省钱。

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

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

说了这么多,我们来尝试下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
<?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 $function) {
$hash = $this->Hash->$function($string);
$this->Redis->setBit($this->bucket, $hash, 1);
}
return 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();
// 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];
}

可以调用测试下,

1
2
3
4
5
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实现布隆过滤器实现方法

布隆过滤器简介

应用场景:

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

好了,就介绍到这里啦!