一、什么是布隆過濾器？
布隆過濾器可以用來判斷一個元素是否在一個集合中。它的優(yōu)勢是只需要占用很小的內(nèi)存空間以及有著高效的查詢效率。
對于布隆過濾器而言，它的本質(zhì)是一個位數(shù)組：位數(shù)組就是數(shù)組的每個元素都只占用1bit ，并且每個元素只能是0或者1
布隆過濾器除了一個位數(shù)組，還有 K 個哈希函數(shù)。當(dāng)一個元素加入布隆過濾器中的時候，會進(jìn)行如下操作：
- 使用K個哈希函數(shù)對元素值進(jìn)行K次計(jì)算，得到K個哈希值
- 根據(jù)得到的哈希值，在位數(shù)組中把對應(yīng)下標(biāo)的值置為1
下圖表示有三個hash函數(shù)，比如一個集合中有x、y、z三個元素，分別用三個hash函數(shù)映射到二進(jìn)制序列的某些位上，假設(shè)我們判斷w是否在集合中，同樣用三個hash函數(shù)來映射，結(jié)果發(fā)現(xiàn)取得的結(jié)果不全為1，則表示w不在集合里面。
數(shù)組的容量即使再大，也是有限的。那么隨著元素的增加，插入的元素就會越多，位數(shù)組中被置為1的位置因此也越多，這就會造成一種情況：當(dāng)一個不在布隆過濾器中的元素，經(jīng)過同樣規(guī)則的哈希計(jì)算之后，得到的值在位數(shù)組中查詢，有可能這些位置因?yàn)橹捌渌氐牟僮飨缺恢脼?了
所以，有可能一個不存在布隆過濾器中的會被誤判成在布隆過濾器中。這就是布隆過濾器的一個缺陷。但是，如果布隆過濾器判斷某個元素不在布隆過濾器中，那么這個值就一定不在布隆過濾器中?？偨Y(jié)就是：
- 布隆過濾器說某個元素在，可能會被誤判
- 布隆過濾器說某個元素不在，那么一定不在
二、Google布隆過濾器基本使用
- 引入依賴
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>21.0</version> </dependency>
- BloomFilterService
@Service
public class BloomFilterService {@Autowired private UserMapper userMapper; private BloomFilter<Integer> bf; /** * 創(chuàng)建布隆過濾器 * * @PostConstruct：程序啟動時候加載此方法 */ @PostConstruct public void initBloomFilter() { List<User> userList = userMapper.selectAllUser(); if (CollectionUtils.isEmpty(userList)) { return; } //創(chuàng)建布隆過濾器(默認(rèn)3%誤差) bf = BloomFilter.create(Funnels.integerFunnel(), userList.size()); for (User user : userList) { bf.put(user.getId()); } } /** * 判斷id可能存在于布隆過濾器里面 * * @param id * @return */ public boolean userIdExists(int id) { return bf.mightContain(id); }}
- BloomFilterController
@RestController
public class BloomFilterController {@Autowired private BloomFilterService bloomFilterService; @RequestMapping("/bloom/idExists") public boolean ifExists(int id) { return bloomFilterService.userIdExists(id); }}
三、Google布隆過濾器與Redis布隆過濾器對比
- Google布隆過濾器的缺點(diǎn)
基于JVM內(nèi)存的一種布隆過濾器
重啟即失效
本地內(nèi)存無法用在分布式場景
不支持大數(shù)據(jù)量存儲
- Redis布隆過濾器
可擴(kuò)展性Bloom過濾器：一旦Bloom過濾器達(dá)到容量，就會在其上創(chuàng)建一個新的過濾器
不存在重啟即失效或者定時任務(wù)維護(hù)的成本：基于Google實(shí)現(xiàn)的布隆過濾器需要啟動之后初始化布隆過濾器
缺點(diǎn)：需要網(wǎng)絡(luò)IO，性能比Google布隆過濾器低
四、Redis布隆過濾器安裝和基本使用
1）使用Docker安裝
[root@localhost ~]# docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
2）基本使用
[root@localhost ~]# docker exec -it bloomfilter /bin/bash
root@7a06a3528556:/data# redis-cli -p 6379
127.0.0.1:6379>
Redis布隆過濾器命令：
bf.add：添加元素到布隆過濾器中，只能添加一個元素，如果想要添加多個使用bf.madd命令
bf.exists：判斷某個元素是否在過濾器中，只能判斷一個元素，如果想要判斷多個使用bf.mexists
127.0.0.1:6379> bf.add urls www.taobao.com
(integer) 1
127.0.0.1:6379> bf.exists urls www.taobao.com
(integer) 1
127.0.0.1:6379> bf.madd urls www.baidu.com www.tianmao.com
- (integer) 1
- (integer) 1
127.0.0.1:6379> bf.mexists urls www.baidu.com www.tianmao.com- (integer) 1
- (integer) 1
上面使用的布隆過濾器只是默認(rèn)參數(shù)的布隆過濾器，它在我們第一次add的時候自動創(chuàng)建。Redis還提供了自定義參數(shù)的布隆過濾器，需要在add之前使用bf.reserve指令顯式創(chuàng)建。如果對應(yīng)的key已經(jīng)存在，bf.reserve會報錯(error) ERR item exists bf.reserve 過濾器名 error_rate initial_size
布隆過濾器存在誤判的情況，在Redis中有兩個值決定布隆過濾器的準(zhǔn)確率：
- error_rate：允許布隆過濾器的錯誤率，這個值越低過濾器的位數(shù)組的大小越大，占用空間也就越大
- initial_size：布隆過濾器可以儲存的元素個數(shù)，當(dāng)實(shí)際存儲的元素個數(shù)超過這個值之后，過濾器的準(zhǔn)確率會下降
127.0.0.1:6379> bf.reserve user 0.01 100
OK
五、會員轉(zhuǎn)盤抽獎
實(shí)現(xiàn)思路：在判斷用戶是否是會員的時候，第一步先通過布隆過濾器過濾掉99%的非會員（誤碼率為1%的情況下），由于布隆過濾器有可能將一個不存在布隆過濾器中的誤判成在布隆過濾器中，也就是有可能會把非會員判斷為會員，所以第二步查詢數(shù)據(jù)庫中用戶對應(yīng)的數(shù)據(jù)庫信息判斷該用戶是否是會員
關(guān)注我的公眾號，后臺回復(fù)【JAVAPDF】獲取200頁面試題！
5萬人關(guān)注的大數(shù)據(jù)成神之路，不來了解一下嗎？
5萬人關(guān)注的大數(shù)據(jù)成神之路，真的不來了解一下嗎？
5萬人關(guān)注的大數(shù)據(jù)成神之路，確定真的不來了解一下嗎？
