網路hash過濾

❶ Redis使用bitmap、zset、hash、list等結構完成騷操作

當同時滿足以下條件時，使用ziplist編碼：

SpringBoot—實現n秒內出現x個異常報警

思路：
藉助Redis的zSet集合，score存儲的是異常時的時間戳，獲取一定時間范圍內的set集合。判斷set個數是否滿足條件，若滿足條件則觸發報指清警；

注意點：

相關API：

Redis實現延遲隊列方法介紹
基於Redis實現DelayQueue延遲隊列設計方案

相關API：

SpringBoot2.x—使用Redis的bitmap實現布隆過濾器（Guava中BF演算法）

布隆過濾器： 是專門用來檢測集合中是否存在特定元素的數據結構。
存在誤差率： 即將不在集合的元素誤判在集合中。

所以布隆過濾器適合查詢准確度要求沒這么苛刻，但是對時間、空間效率比較高的場景。

實現方式：Redis實現布隆過濾器——借鑒Guava的BF演算法：

SpringBoot2.x中使用Redis的bitmap結構（工具類）

注意：bitmap使用存在風險，若僅僅計算hash值，會導致bitmap佔用空間過大。一般需要對簡空hash值進行取余處理。

根據Redis是否存在key，判斷鎖是否被獲取；

鎖應該是一個對象，記錄持有鎖的線程信息、當前重入次數。所以應該使用Redis的Hash結構來存儲鎖對象。

3.1 網路波動造成釋放鎖失敗怎麼解決？

需要為鎖加上超時時間；

3.2 任務未執行完畢時，鎖由於超時時間被釋放？

線程一旦加鎖成功，可以啟動一個後台線程，每隔多少秒檢查一次，如果線程還持有鎖，可以不斷延長鎖的生存時間。

主從切換時，從伺服器上沒有加鎖信息，導致多個客戶端同時加鎖。

list結構底層是ziplist/quicklist（可看著一個雙端隊列）。常用命令：

使用list作為對象的緩存池。通過rpush放入對象，通過lpop取出對象。

若是阻塞取，可以使用blpop命令實現。

Redis和Lua腳本(實現令牌桶限流)

數據結構選擇hash。
hash裡面維護：最後放入令牌時間、當前桶內令牌量、桶內最大數量、令牌放置速度（元數據）。

被動式維護：

命令：incr原子累加；

對一段固定時間窗口內的請求進行計數，如果請求數超過了閾值，則舍棄該請求；如果沒有達到設定的閾值，則接受該請求，且計數加1。當窗口時間結束，重置計數器為0。

優點：實現簡單，容易理解；
缺點：流量曲線可能不夠平滑，有「突刺現象」。

1. 一段時間內（不超過時間窗口）系統服務不可用。 比如窗口大小1s，限流為100，恰好某個窗口第1ms來了100個請求，然後2ms-999ms請求都會被拒絕。這段時間用戶會感覺系統服務不可用（即不夠平滑）。

2. 窗口切換時可能會出現兩倍於閾值流量的請求。 比如窗口大小1s，限流大小100，攔逗瞎然後在某個窗口的第999ms有100個請求，窗口前期沒有請求。所以這100個請求都會通過。然後下一個窗口的第1ms又來100個請求，然後全部通過。其實也是1ms內通過的200個請求。

命令：Redis的incr命令

是對固定窗口計數器的優化，解決的是切換窗口兩倍閾值流量的場景。

具體解決方案是：將限流窗口分為多個小的限流窗口，各個限流窗口分別計數。當前時間大於窗口最大時間時，將頭部的小窗口數據舍棄，尾部新增小窗口來處理新請求。

優點：本質上是對固定窗口的優化

❷ 布隆過濾器

[TOC]

通過解決方案：

Java中如將數據存儲在內存中，最簡單的演算法結構是HashMap。通過HashMap判斷key是否存在，來判斷數據是否存在。通過hash演算法查找元素，時間復雜度基本是 O(1) （可能存在hash沖突後轉換成鏈表或紅黑樹的情況，時間復雜度的影響可以忽略）。

使用HashMap速度很快，存儲簡單，絕大部分場景可以使用。但是HashMap 佔用的空間比較大 ：

為什麼出現布隆過濾器：

舉例：

如1000萬個Integer存儲在內存中，佔用空間為：4x32x10000000位，即1220兆。如布隆過濾器通過4位元組存儲（布隆過濾器通過多次hash對數據計算後-->幾次hash根據數據量指定，得到多個數據， 佔用多個位 ），則佔用空間為610M。比原有空間少一半。

個人覺得，此比較在字元等的比較中尤為有效。
一個字元串多個字元，根據編碼方式，一個字元兩個或三個位元組，如10個字元，字元串存儲佔用20個位元組，還有相關字元串相關的類信息的內存佔用。
位存儲，根據數據量的大小，hash的位數，靈活計算。如4個位元組，則是原hashMap佔用空間的五分之一。

（1）定義位元組向量

先定義一個指定長度的位元組數組（位元組數組，數組內每個元素的值）。

如長度為8（一個位元組大小），默認所有元素值均為0，如下：

（2）計算哈希值

將要寫入過濾器的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。

如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。

（3）更新位元組向量

將計算出的位元組向量的索引， 對應的位元組向量中的元素值更高為1 （無論之前為0或者為1，均更改為1）。如下：

（1）計算哈希值

將要判斷過濾器中是否存在的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。

如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。

注意：哈希函數的判斷方式和計算索引的方式，需和寫入數據時完全一致。

（2）判斷是否存在

如原位元組數組中，對應1，3，7中存在的元素的值都為1。則判定為此元素 可能存在 ，但凡有一個元素的值不為1，則判定此元素 一定不存在 。

布隆過濾器，主要需實現的目標是， 在指定的數據個數范圍內，滿足誤判率在設定的范圍內 ，誤判率太高的話，無法起到過濾數據的情況，誤判率不能為0。

因此需要計算兩個數據來滿足 存儲數據的個數 和 誤判率 ：

使用布隆過濾器的決定性因素之一，就是此演算法插入數據和查詢數據的速度必須非常快。因此在對數據進行哈希運算的時候， 需選擇計算快的哈希演算法 。

而且， 寫入數據以及查詢數據的哈希演算法，順序和演算法都需完全一致 。

待完善。。。。。

可以通過google的 guava ，在內存中輕松實現布隆過濾器。

無需手動計算滿足位元組數組的長度和哈希個數，只需要輸入 擬輸入數據的個數 和 期望誤判率 即可。

不輸入期望誤判率的情況下，誤判率為0.03，即100個非范圍內的數據進行校驗時，約三個數據會判定為存在。

多次執行，結果一致，根據結果判定：

內存的存儲存在局限性，可以使用redis中的bitMap來實現位元組數組的存儲。

使用redis實現布隆過濾器。需要根據公式，手動計算位元組數組的長度和哈希的個數。

實現過程，待完善。。。。。。

❸ 布隆過濾器詳解

布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用於判斷一個元素是否在一個集合中。

通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 ， ， 。

這個時候，布隆過濾器（Bloom Filter）就應運而生。

了解布隆過濾器原理之前，先回顧下 Hash 函數原理。

哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：

所有散列函數都有如下基本特性：

但是用 hash表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。

BloomFilter 是由一個固定大小的二進制向量或者點陣圖（bitmap）和一系列映射函數組成的。

在初始狀態時，對於長度為 m 的位數組，它的所有位都被置為0，如下圖所示：

當有變數被加入集合時，通過 K 個映射函數將這個變數映射成點陣圖中的 K 個點，把它們置為 1（假定有兩個變數都通過 3 個映射函數）。

查詢某個變數的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了

為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。

布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 並不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 ，另外，散列函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何數據結構都不能；

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加 1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。

如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。

布隆過濾器的典型應用有：

知道了布隆過濾去的原理和使用場景，我們可以自己實現一個簡單的布隆過濾器

分布式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現了布隆過濾器。

當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。

Redis 提供的 bitMap 可以實現布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥區別。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件載入到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。

在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式

直接編譯進行安裝

使用Docker進行安裝

使用

布隆過濾器基本指令：

我們只有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這里就不做這個實驗了。

上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。

Redis 還提供了自定義參數的布隆過濾器， bf.reserve 過濾器名 error_rate initial_size

但是這個操作需要在 add 之前顯式創建。如果對應的 key 已經存在，bf.reserve 會報錯

我是一名 Javaer，肯定還要用 Java 來實現的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson

為了解決布隆過濾器不能刪除元素的問題，布穀鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布穀鳥過濾器和布隆過濾器進行了深入的對比。相比布穀鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。

由於使用較少，暫不深入。

https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

❹ 布隆過濾器的優點

相比於其它的數抄據結襲構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外, Hash函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能；
k和m相同，使用同一組Hash函數的兩個布隆過濾器的交並差運算可以使用位操作進行。
布隆過濾器