一、布隆过滤器
1.1 原理
1.1.1 布隆过滤器基础版
原理就是一个对一个key进行k个hash算法获取k个值，在比特数组中将这k个值散列后设定为1，然后查的时候如果特定的这几个位置都为1，那么布隆过滤器判断该key存在。
布隆过滤器可能会误判，如果它说不存在那肯定不存在，如果它说存在，那数据有可能实际不存在；
Redis的bitmap只支持2^32大小，对应到内存也就是512MB，误判率万分之一，可以放下2亿左右的数据，性能高，空间占用率及小，省去了大量无效的数据库连接。
image.png
存入过程： 通过三个hash函数计算出三个哈希值，然后将三个值映射到数组中将0改成1。
查询过程：通过三个hash函数计算出查询数据的哈希值，然后检查布隆过滤器对应位置上的值是否为1，如果有一个不为1表示该值不存在，如果都为1表示该值可能存在。（查询时间复杂度为O(k)，k为哈希函数个数）
删除过程：不能进行删除，因为会删除掉其他数据。
更新过程：也不能进行更新。
1.1.2 布隆过滤器增强版
为了解决上面布隆过滤器的问题,出现了一个增强版的布隆过滤器(Counting Bloom Filter),这个过滤器的思路是将布隆过滤器的bitmap更换成数组,当数组某位置被映射一次时就+1,当删除时就-1,这样就避免了普通布隆过滤器删除数据后需要重新计算其余数据包Hash的问题,但是依旧没法避免误判。
image.png
1.2 应用
image.png
-
redis缓存穿透（大量查询不存在于数据库中的数据）：使用布隆过滤器进行过滤，如果不存在直接跳过查询数据库，返回结果。
-
新闻客户端的推送去重功能，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。它在起到去重的同时，在空间上还能节省 90% 以上，只是稍微有那么点不精确，也就是有一定的误判概率。
-
黑白名单
-
块索引是HBase固有的一个特性，因为HBase的底层数据是存储在HFile中的，而每个HFile中存储的是有序的<key, value>键值对，HFile文件内部由连续的块组成，每个块中存储的第一行数据的行键组成了这个文件的块索引，这些块索引信息存储在文件尾部。当HBase打开一个HFile时，块索引信息会优先加载到内存；HBase首先在内存的块索引中进行二分查找，确定可能包含给定键的块，然后读取磁盘块找到实际想要的键。
但实际应用中，仅仅只有块索引满足不了需求，这是因为，块索引能帮助我们更快地在一个文件中找到想要的数据，但是我们可能依然需要扫描很多文件。而布隆过滤器就是为解决这个问题而生。因为布隆过滤器的作用是，用户可以立即判断一个文件是否包含特定的行键，从而帮我们过滤掉一些不需要扫描的文件。
1.3 代码实现
1.3.1 实现一(Guava)
调用谷歌的guava包的api就可以。
缺点：guava版实现主要问题在于无法支持集群环境. 为了支持集群环境主要考虑通过redis setbit来实现BloomFilter。
创建布隆过滤器对象：
// 参数Funnels.integerFunnel()是默认参数，size是预计存入的数据量，fpp是设置的误判率
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, int expectedInsertions, double fpp) {
return create(funnel, (long) expectedInsertions, fpp);
}
误判率越低，哈希函数个数和布隆过滤器数组长度越大，运算效率越低。
放入数据：
@CanIgnoreReturnValue
public boolean put(T object) {
return strategy.put(object, funnel, numHashFunctions, bits);
}
判断是否存在：
public boolean mightContain(T object) {
return strategy.mightContain(object, funnel, numHashFunctions, bits);
}
1.3.2 实现二(Redisson)
使用redis实现
依赖
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.6.5</version>
</dependency>
代码
public class RedissonBloomFilter {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://192.168.32.128:6379");
// config.useSingleServer().setPassword("");
// 构造Redisson
RedissonClient redissonClient = Redisson.create(config);
// 初始化布隆过滤器：预计元素为100000000L个，误差率为3%
RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter("phoneList");
bloomFilter.tryInit(100000000L, 0.03);
// 将号码插入到布隆过滤器中
bloomFilter.add("10086");
// 判断下面的号码是否在布隆过滤器中
System.out.println(bloomFilter.contains("10000"));
System.out.println(bloomFilter.contains("10086"));
}
}
1.4 布隆过滤器的缺点
- 不支持删除元素：一旦对位数组进行了赋值，无法将其删除。可以通过增加每个数组元素大小使用增强版过滤器实现删除功能。
- 查询性能弱：布隆过滤器使用多个hash函数计算位图多个不同位点，由于多个位点在内存中不连续，CPU寻址花销较大。
- 空间利用率低。
二、布谷鸟过滤器
2.1 原理
image.png
布谷鸟哈希结构：布谷鸟过滤器由一个数组组成，数组中元素大小为4个字节，可以存储4个指纹，每个指纹占一个字节(128种)。同一个数组元素 上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。
type bucket [4]byte // 一个桶，4个座位
type cuckoo_filter struct {
buckets [size]bucket // 一维数组
nums int // 容纳的元素个数
kick_max // 最大挤兑次数
}
插入：首先计算数据的指纹和哈希值，并通过指纹和哈希值计算另一个哈希值，两个哈希值映射到两个位置(因为计算得到两个位置，每个位置存储4个指纹，所以相同对象最多存储8个)。接下来进行插入，会尝试插入两个位置，如果都失败，随机挤走一个指纹，并重新为该指纹寻找新的位置(超过最大挤兑次数后扩容)。
扩容：如果数组过小，会发生循环挤兑的情况，就可以设置最大挤兑次数，如果超过该次数，进行扩容，重新计算每个指纹的位置。
查找：通过计算哈希值得到两个元素，对两个元素中的8个位置进行指纹对比，如果对比成功则表示数据存在。如果哈希值和指纹相同时会发生误判(小概率)。
删除：因为每个对象的指纹会存储到一个位置中，所以可以通过删除这个指纹来删除数据。删除功能无法使用的情况：如果相同对象存储超过8个，就无法使用删除功能；如果俩数据的哈希值和指纹相同时，会出现误删除情况。
更新：即删除后再添加新指纹。
2.2 应用
同布隆过滤器。
2.3 代码实现
貌似目前没有现成的java实现。
可以参考如下项目：
-
通过redis中强有力的第三方扩展module, 让redis支持sql及布谷鸟过滤器。
https://github.com/RedBeardLab/rediSQL
2.4 布谷鸟过滤器的优缺点
对比布隆过滤器：
布谷鸟过滤器在错误率小于3%的时候空间性能是优于布隆过滤器的，而这个条件在实际应用中常常满足，所以一般来说它的空间性能是要优于布隆过滤器的。布谷鸟过滤器按照普通设计，只有两个Hash表，在查找的时候可以确保两次访存就可以做完，相比于布隆过滤器的K个Hash函数K次访存，在数据量很大不能全部装载在内存中的情况下，多次访问内存性能较差。
当然，布谷过滤器也有其相应的缺点，当装填数据过多的时候，容易出现循环的问题，即插入失败的情况。另外，它还跟布隆过滤器共有的一个缺点，就是访问空间地址不连续，内存寻址消耗大。
优点：
- 访问内存次数低
- Hash函数计算简单
- 存在删除操作。如果相同数据个数不超过8个，那么删除操作可用；但是因为存储的是计算后的指纹信息，存在误删除的可能，所以不好用。
缺点：
- 内存空间不联系，CPU消耗大。
- 容易出现装填循环问题：Hash冲突踢出原数据，原数据还是存在冲突。
- 删除数据时，Hash冲突会引起误删：查询有误判，那么删除也会有误删。
网友评论