详解Redis缓存击穿以及解决方案

假设，根据误判率，我们生成一个10位的bit数组，，以及2个hash函数((f_1,f_2))，如下图所示(生成的数组的位数和hash函数的数量，我们不用去关心是如何生成的，有数学论文进行过专业的证明)。

假设输入集合为((N_1,N_2)),经过计算(f_1(N_1))得到的数值得为2，(f_2(N_1))得到的数值为5，则将数组下标为2和下表为5的位置置为1，如下图所示：

同理，经过计算(f_1(N_2))得到的数值得为3，(f_2(N_2))得到的数值为6，则将数组下标为3和下表为6的位置置为1，如下图所示：

这个时候，我们有第三个数(N_3)，我们判断(N_3)在不在集合((N_1,N_2))中，就进行(f_1(N_3)，f_2(N_3))的计算

• 若值恰巧都位于上图的红色位置中，我们则认为，(N_3)在集合((N_1,N_2))中
• 若值有一个不位于上图的红色位置中，我们则认为，(N_3)不在集合((N_1,N_2))中

以上就是布隆过滤器的计算原理，下面我们进行性能测试，

(2) 性能测试

代码如下：

a. 新建一个maven工程，引入guava包

<dependencies> 
<dependency> 
<groupId>com.google.guava</groupId> 
<artifactId>guava</artifactId> 
<version>22.0</version> 
</dependency> 
</dependencies> 

b. 测试一个元素是否属于一个百万元素集合所需耗时

package bloomfilter; 
import com.google.common.hash.BloomFilter; 
import com.google.common.hash.Funnels; 
import java.nio.charset.Charset; 
public class Test { 
private static int size = 1000000; 
private static BloomFilter<Integer> bloomFilter =BloomFilter.create(Funnels.integerFunnel(), size); 
public static void main(String[] args) { 
for (int i = 0; i < size; i++) { 
bloomFilter.put(i); 
} 
long startTime = System.nanoTime(); // 获取开始时间 
//判断这一百万个数中是否包含29999这个数 
if (bloomFilter.mightContain(29999)) { 
System.out.println("命中了"); 
} 
long endTime = System.nanoTime(); // 获取结束时间 
System.out.println("程序运行时间： " + (endTime - startTime) + "纳秒"); 
} 
} 

输出如下所示：

命中了 
程序运行时间： 219386纳秒 

也就是说，判断一个数是否属于一个百万级别的集合，只要0.219ms就可以完成，性能极佳。

c. 误判率的一些概念

首先，我们先不对误判率做显示的设置，进行一个测试，代码如下所示：

package bloomfilter; 
import java.util.ArrayList; 
import java.util.List; 
import com.google.common.hash.BloomFilter; 
import com.google.common.hash.Funnels; 
public class Test { 
private static int size = 1000000; 
private static BloomFilter<Integer> bloomFilter =BloomFilter.create(Funnels.integerFunnel(), size); 
public static void main(String[] args) { 
for (int i = 0; i < size; i++) { 
bloomFilter.put(i); 
} 
List<Integer> list = new ArrayList<Integer>(1000); 
//故意取10000个不在过滤器里的值，看看有多少个会被认为在过滤器里 
for (int i = size + 10000; i < size + 20000; i++) { 
if (bloomFilter.mightContain(i)) { 
list.add(i); 
} 
} 
System.out.println("误判的数量：" + list.size()); 
} 
} 

输出结果如下：

误判对数量：330 

如果上述代码所示，我们故意取10000个不在过滤器里的值，却还有330个被认为在过滤器里，这说明了误判率为0.03.即，在不做任何设置的情况下，默认的误判率为0.03。

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!