Redis中的BloomFilter簡(jiǎn)介及使用方法

本篇內(nèi)容主要講解“Redis中的BloomFilter簡(jiǎn)介及使用方法”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Redis中的BloomFilter簡(jiǎn)介及使用方法”吧!

介紹以及場(chǎng)景使用

BloomFilter 中文名就是 布隆過(guò)濾器，作為過(guò)濾器，有沒(méi)有感覺(jué)很像 LOL 中布隆的 E技能(堅(jiān)不可摧) ?

布隆過(guò)濾器是一個(gè)叫 布隆 的人提出來(lái)的，它是通過(guò)一個(gè) 大型位數(shù)組和幾個(gè)不同的hash函數(shù) 來(lái)實(shí)現(xiàn)的，我們可以把布隆過(guò)濾器理解為一個(gè) 不精確的set  。我們都知道 set 可以去重，使用 set 可以幫我們判斷集合中是否已經(jīng)存在某些元素并且或者幫我們實(shí)現(xiàn)去重功能。

但是，set 提供精確的去重功能的同時(shí)也給我們帶來(lái)了一個(gè)更大的問(wèn)題——空間消耗。

比如這個(gè)時(shí)候我們進(jìn)行網(wǎng)頁(yè)爬蟲(chóng)，需要對(duì)爬過(guò)的 url 進(jìn)行去重以避免爬到已經(jīng)爬過(guò)的網(wǎng)站，如果我們使用 set 那么也就意味著我們需要將所有爬過(guò)的 url  放入集合中，假設(shè)一個(gè) url 64字節(jié)，那么一億個(gè) url 意味著我們需要占用 6GB，十億就是 60GB 左右。

• 請(qǐng)注意，是內(nèi)存。

比如這個(gè)時(shí)候我們要進(jìn)行垃圾郵件或者垃圾短信的過(guò)濾，我們需要從數(shù)十億個(gè)垃圾郵件列表或者垃圾電話列表中進(jìn)行判斷此時(shí)的郵件或者短信是否是垃圾的。如果我們此時(shí)使用  set 那么占用空間不用我多說(shuō)了，也是 百GB級(jí)別 的。

上面的面試中我提到了 緩存穿透 ，用戶故意請(qǐng)求數(shù)據(jù)庫(kù)本來(lái)就不存在的(比如ID =  -1)，這個(gè)時(shí)候如果不做處理那么肯定會(huì)穿透緩存去查詢數(shù)據(jù)庫(kù)，一個(gè)查詢還好，如果幾千，幾萬(wàn)個(gè)同時(shí)進(jìn)來(lái)呢?你的數(shù)據(jù)庫(kù)頂?shù)米?那么此時(shí)我們使用 set  進(jìn)行處理，占用那么多內(nèi)存空間，你覺(jué)得值得嗎???或者說(shuō)，還有沒(méi)有更好的方法了?

上面所講的三個(gè)典型場(chǎng)景，網(wǎng)站去重，垃圾郵件過(guò)濾，緩存穿透 ，這三個(gè)只要使用 BloomFilter 就能完美解決。

你有沒(méi)有發(fā)現(xiàn)，上面三個(gè)場(chǎng)景其實(shí)對(duì)精度要求都不是很高，尤其是垃圾郵件過(guò)濾，其實(shí)偶爾收到幾個(gè)垃圾郵件也無(wú)所謂的。像緩存穿透，也正好符合了  BloomFilter 的一個(gè)特性 他說(shuō)有的不一定有，他說(shuō)沒(méi)有的肯定沒(méi)有，我說(shuō)你這個(gè) ID  在數(shù)據(jù)庫(kù)不存在那就真的不存在，老子把你過(guò)濾了就是這么自信，怎么，你打我???

原理探究

聊了這么久的概念和應(yīng)用場(chǎng)景，是不是還對(duì) BloomFilter 怎么能進(jìn)行去重的還是一臉懵逼? 下面我們就聊一聊 BloomFilter  的實(shí)現(xiàn)原理。首先給大家放一張結(jié)構(gòu)圖。

其中 F、G、H 是幾種 無(wú)偏 Hash 函數(shù)，底下是一個(gè) 大型的位數(shù)組，當(dāng)我們向 BloomFilter  添加數(shù)據(jù)的時(shí)候，它首先會(huì)將我們的數(shù)據(jù)(key)做幾次hash運(yùn)算(這里就是FGH)，每個(gè)hash運(yùn)算都會(huì)得到一個(gè)不用的位數(shù)組索引下標(biāo)，此時(shí)我們就將算出的幾個(gè)下標(biāo)的位置的值改成1就行。如果判斷元素是否存在，只要  判斷所在的所有索引下標(biāo)的值都是1 就行了。

其實(shí)你也發(fā)現(xiàn)了，在 BloomFilter 中會(huì)出現(xiàn)不同key所算出的下標(biāo)重復(fù)了，如上圖所示，這就是誤差的來(lái)源( 你可以配置初始大小和錯(cuò)誤率來(lái)控制誤差  )也是他說(shuō)有的不一定有，他說(shuō)沒(méi)有的肯定沒(méi)有 這一特性的根本原因，因?yàn)槿绻?或者存在0那么肯定不存在，如果全是1也有可能是別的幾個(gè)key給放進(jìn)去的1。

基本使用

因?yàn)?BloomFilter 是 Redis 的擴(kuò)展模塊，所以需要額外下載，你可以使用 Docker  進(jìn)行拉取。安裝步驟我不做詳細(xì)解釋，你可以到它的github上學(xué)習(xí)怎么安裝

安裝完之后我們就可以愉快的使用啦。

• bf.add key element 添加

• bf.exists key element 判斷是否存在

• bf.madd key element1 element2 ... 批量添加

• bf.mexists key element1 element2 ... 批量判斷

命令很簡(jiǎn)單，你可以自己去嘗試。

HyperLogLog

介紹以及場(chǎng)景使用

在 Redis 中還有一個(gè)會(huì)存在誤差的數(shù)據(jù)結(jié)構(gòu) HyperLogLog。

我們首先思考一個(gè)場(chǎng)景，當(dāng)老板讓我們計(jì)算頁(yè)面的 UV 我們?cè)撛趺崔k?

如果訪問(wèn)量不大使用 set 進(jìn)行用戶去重完全可以，但是訪問(wèn)量如果有幾百萬(wàn)，幾千萬(wàn)，那么就會(huì)又遇到上面提到的 浪費(fèi)空間 的問(wèn)題。如果我們這個(gè)時(shí)候有一個(gè)能  進(jìn)行去重且能進(jìn)行計(jì)數(shù)的數(shù)據(jù)結(jié)構(gòu)就好了。

這個(gè)時(shí)候 HyperLogLog 就閃亮登場(chǎng)了!它能提供不精確的去重計(jì)數(shù)方案(誤差值在 0.81% 左右)，不精確就不精確哇，UV  要你多精確?0.81%我們也能接受。最重要的是 HyperLogLog 只占用 12KB 的內(nèi)存。

使用方法和場(chǎng)景實(shí)踐

• pfadd key element 添加

• pfcount key 計(jì)算

• pfmerge destkey sourcekey1 sourcekey2 ... 合并

命令都是 pf 開(kāi)頭是因?yàn)檫@是一個(gè)名叫 Philippe Flajolet 的教授發(fā)明的。

可以看到就這三個(gè)基本命令，很簡(jiǎn)單很容易掌握。那我們來(lái)動(dòng)手實(shí)踐一下吧。

BitMap

介紹和使用場(chǎng)景

首先我們?cè)賮?lái)思考一個(gè)比較有意思的場(chǎng)景，老板想讓你統(tǒng)計(jì)一年內(nèi)多個(gè)用戶之間他們同時(shí)在線的天數(shù)，這個(gè)時(shí)候你怎么辦?

你可能會(huì)想到使用 hash 存儲(chǔ)，這太浪費(fèi)空間了，有沒(méi)有更好的辦法呢?答案是有的，Redis 中使用了 bitmap位圖。

我們知道，字符串中一個(gè)字符是使用8個(gè)比特來(lái)表示的(如上圖)，在 Redis 中 bitmap 底層就是 string，也可以說(shuō) string 底層就是  bitmap。

如果有了這個(gè)我們是不是可以用來(lái)計(jì)算一個(gè)用戶在指定時(shí)間內(nèi)簽到的次數(shù)?也就是一個(gè)位置代表一天，0代表未簽到，1代表簽到，在上圖中，該用戶在八天內(nèi)簽到了四次。

Redis 中的 bitmap 還提供了多個(gè) bitmap 進(jìn)行與，或，異或運(yùn)算的命令，當(dāng)然還有單個(gè) bitmap 的 非  運(yùn)算。這是不是給你提供了一點(diǎn)思路對(duì)于我們一開(kāi)始的需求呢?

基本命令使用

• setbit key index 0/1 設(shè)置某位的值

• getbit key index 獲取某位的值

• bitcount key start end 獲取指定范圍內(nèi)為1的數(shù)量

需要注意的是，這里的start 和 end是指的字符位置不是比特位置!!!包括下面的 bitpos 也是

• bitpos key bit start end 獲取第一個(gè)值為bit的從start到end字符索引范圍的位置

• bitop and/or/xor/not destkey key1 key2 對(duì)多個(gè) bitmap 進(jìn)行邏輯運(yùn)算。

對(duì)于bitmap還有一個(gè)好玩的指令就是 bitfield ，這里我不做過(guò)多介紹，感興趣的同學(xué)自己可以了解一下。

動(dòng)手實(shí)踐

我們首先來(lái)實(shí)現(xiàn)一下統(tǒng)計(jì)用戶簽到次數(shù)的功能。

還記得我們一開(kāi)始的問(wèn)題嗎?統(tǒng)計(jì)一年內(nèi)多個(gè)用戶之間他們同時(shí)在線的天數(shù)，我們有了 bitmap 還怕什么。

GeoHash

介紹和場(chǎng)景運(yùn)用

GeoHash 常用來(lái)計(jì)算 附近的人，附近的商店。

試想一下如果我們使用 關(guān)系數(shù)據(jù)庫(kù) 來(lái)存儲(chǔ)某個(gè)元素的地址 (id,經(jīng)度,緯度)  。這個(gè)時(shí)候我們?cè)撊绾斡?jì)算附近的人?難道我們要遍歷所有元素位置并做距離計(jì)算?這顯然不可能。

當(dāng)然你可以使用劃分區(qū)域并使用 SQL 語(yǔ)句圈出區(qū)域，然后建立 雙向復(fù)合索引 來(lái)提升性能，但是數(shù)據(jù)庫(kù)的并發(fā)能力畢竟有限，我們能不能使用 Redis  來(lái)做呢?

答案是可以的，Redis 中使用了 GeoHash  提供了很好的解決方案。具體原理是將地球看成一個(gè)平面，并把二維坐標(biāo)映射成一維(精度損失的原因)。如果對(duì)其中的算法感興趣你可以自己額外去了解，篇幅有限不做過(guò)多說(shuō)明。

基本命令和使用實(shí)戰(zhàn)

• geoadd key longitude latitude element(后面可配置多個(gè)三元組) 添加元素

• geodist key element1 element2 unit 計(jì)算兩個(gè)元素的距離

• geopos key element [element] 獲取元素的位置

• geohash key element 獲取元素hash

• georadiusbymember key element distanceValue unit count countValue ASC/DESC  [withdist] [withhash] [withcoord] 獲取元素附近的元素 可附加后面選項(xiàng)[距離][hash][坐標(biāo)]

• georadius key longitude latitude distanceValue unit count countValue ASC/DESC  [withdist] [withhash] [withcoord] 和上面一樣只是元素改成了指定坐標(biāo)值 

到此，相信大家對(duì)“Redis中的BloomFilter簡(jiǎn)介及使用方法”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！