工作中有用到Redis濾重隊(duì)列。

原來(lái)的方法如下:

方法一

• 為了保證操作原子性，使用Redis執(zhí)行Lua腳本。
• 在腳本中的邏輯是，如果隊(duì)列不超過(guò)某個(gè)數(shù)值，進(jìn)行一次lrem操作（隊(duì)列使用list結(jié)構(gòu)），然后將新元素入列。

優(yōu)點(diǎn)：
簡(jiǎn)單，直觀。

缺陷：

lrem的時(shí)間復(fù)雜度為O(N)，N為隊(duì)列中的元素個(gè)數(shù)；所以，性能一般。

因?yàn)榉乐龟?duì)列內(nèi)容過(guò)多，防止發(fā)生N級(jí)別的刪除操作，限制了一個(gè)濾重的閥值，如果超過(guò)這個(gè)閥值就不能使用濾重功能。

方法二
為了解決以上痛點(diǎn)，新玩法為：

• 為了保證操作原子性，使用Redis執(zhí)行Lua腳本。
• 同樣使用Lua腳本，排重分為兩步，使用了Redis自帶的二進(jìn)制數(shù)組進(jìn)行維護(hù)是否存在重復(fù)的狀態(tài)：
• 在入隊(duì)之前，先從二進(jìn)制數(shù)組中查詢下這個(gè)key是否存在，即getbit key offset。如果存在說(shuō)明隊(duì)列中存在一個(gè)這個(gè)offset的值，就不需要進(jìn)行入隊(duì)操作，直接中斷執(zhí)行就好。
• 在出隊(duì)的時(shí)候，將出隊(duì)的元素在二進(jìn)制數(shù)組中設(shè)置為不存在，即，setbit key offset 0。

優(yōu)點(diǎn)：

因?yàn)槭莃itmap算法，在查詢是否存在執(zhí)行的offset的時(shí)候，時(shí)間復(fù)雜度是O(1)，并且與隊(duì)列中元素個(gè)數(shù)無(wú)關(guān)。

優(yōu)雅，如果算是優(yōu)點(diǎn)的話，哈哈。

缺點(diǎn)：

最重要的一點(diǎn)是redis bitmap的offset必須是int，比如，long范圍的offset是不存在的，這是一個(gè)很重要的點(diǎn)，一定要注意（都是血淚史）。

因?yàn)槿腙?duì)和出隊(duì)都進(jìn)行了bitmap的數(shù)據(jù)維護(hù)，所以需要確保在編碼的時(shí)候一定謹(jǐn)慎，足夠健壯。

總結(jié)
從上面的分析來(lái)看，感覺(jué)方法二完勝方法一。其實(shí)不盡然，只能說(shuō)各有不同的場(chǎng)景。
方法一比較通用，不論入隊(duì)的內(nèi)容是什么，都可能濾重，方法二依賴與Bitmap算法，意味key只能是數(shù)值型的元素。
在實(shí)際應(yīng)用中，以上兩種濾重方式一般是可以聯(lián)合使用的。如果key是數(shù)值類(lèi)型，沒(méi)有超出int的取值范圍，那么就直接使用方法二，如果超出了int的取值范圍的數(shù)值就使用方法一。

擴(kuò)展
還有一種濾重的算法叫：布隆過(guò)濾器，感興趣的同學(xué)可以了解下：Bloom filter。如果不需要?jiǎng)h除，不在乎誤判率的話那應(yīng)該是很合適的一個(gè)算法，空間和時(shí)間都很高效。

---

另外如果有人遇到過(guò)其他的一些坑或者有更好的建議，歡迎指點(diǎn)。

轉(zhuǎn)載于:https://www.cnblogs.com/liushijie/p/5450859.html

總結(jié)

以上是生活随笔為你收集整理的BitMap算法应用：Redis队列滤重优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。