生活随笔
收集整理的這篇文章主要介紹了
高并发下的缓存问题及布隆过滤器
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
一. 高并發下緩存的三大問題
1. 概述
背景 在高并發場景下，如果系統直連數據庫，數據庫會出現性能問題，甚至造成數據庫宕機，服務不可用。 為了降低數據庫的壓力，我們通常會設計一個緩存系統，在訪問數據庫之前，攔截一部分流量，保證系統的穩定和數據庫的可用。 高并發場景下緩存最常見的三大問題
2. 緩存雪崩
2.1 緩存雪崩的含義
緩存雪崩：當某一個時刻出現大規模的緩存失效的情況，那么就會導致大量的請求直接打在數據庫上面，導致數據庫壓力巨大，如果在高并發的情況下，可能瞬間就會導致數據庫宕機。
2.2 分析
造成緩存雪崩的關鍵：在同一時間大規模的key失效。 出現緩存雪崩的原因 第一種：可能是Redis宕機 第二種：可能是采用了相同的過期時間。
2.3 緩存雪崩的解決方案
法1：搭建Redis集群，防止Redis宕機導致緩存雪崩的問題，提高Redis的容災性。 法2：在原有的失效時間上加一個隨機值（比如1-5分鐘隨機），避免采用相同過期時間的key同時失效。 法3：提高數據庫的容災能力，可以使用分庫分表，讀寫分離的策略。 法4：增加兜底措施（熔斷機制或服務降級），防止過多請求打到數據庫。
3. 緩存擊穿
3.1 緩存擊穿的含義
緩存擊穿：一個熱點Key（數據庫存在該數據），有大并發集中對其進行訪問，突然間這個Key失效了，導致大并發全部打在數據庫上，導致數據庫壓力劇增，這種現象就叫做緩存擊穿。
緩存雪崩 && 緩存擊穿
緩存雪崩：大規模key同時失效； 緩存擊穿：一個熱點key。
3.2 分析
關鍵：某個熱點的key失效，導致大并發集中打在數據庫上。 解決方案的考慮 第一種：熱點key不設置過期時間； 第二種：降低打在數據庫的請求數量。
3.3 緩存擊穿的解決方案
法1：如果業務允許，將熱點key設置為永不過期； 法2：使用互斥鎖，針對同一個key只允許一個線程到數據庫查詢。 說明：如果緩存失效的情況，只有拿到鎖才可以查詢數據庫，降低了在同一時刻打在數據庫上的請求，防止數據庫打死。 問題：導致系統的性能變差。
4. 緩存穿透
4.1 緩存穿透的含義
緩存穿透：緩存和數據庫都沒有的數據，被大量請求，這些請求像“穿透”了緩存一樣直接打在數據庫上，這種現象就叫做緩存穿透。
4.2 分析
關鍵：傳進來的key在緩存和數據庫均不存在。 說明：假如有黑客傳進大量的不存在的key，則大量的請求打在數據庫上是很致命的，因此在日常開發中要對參數做好校驗，一些非法的參數，不可能存在的key就直接返回錯誤提示，要對調用方保持這種“不信任”的心態。
4.3 緩存穿透的解決方案
法1：緩存空值/默認值，即把無效的Key存入緩存。 詳解：如果Redis查不到數據，數據庫也查不到，我們把這個Key存入緩存，設置其value=null，當下次再通過這個Key查詢時就不需要再查詢數據庫。 缺點：如果傳進來的這個不存在的Key值每次都是隨機的，那存進Redis也沒有意義。 法2：使用布隆過濾器。 概述：布隆過濾器是一種概率性數據結構，它可以告訴我們數據一定不存在或可能存在。 詳解：我們可以在緩存之前再加一層布隆過濾器，在查詢的時候先去布隆過濾器查詢key是否存在，如果不存在就直接返回。
二. 布隆過濾器及其變體的介紹與應用
1. 布隆過濾器介紹
1.1 概述
布隆過濾器（Bloom Filter）是一種比較巧妙的、空間高效的、概率型數據結構，該數據結構于1970年由布隆（Burton Howard Bloom）提出。 其特點是高效插入和查詢，主要用于快速檢測一個元素是否在集合中，即告訴我們數據一定不存在或可能存在。
1.2 基本思想
數據結構：它由固定大小的二進制向量/位數組，以及一系列隨機映射函數（哈希函數）兩部分組成。 思想：其核心思想就是利用多個不同的Hash函數來解決沖突。 Hash碰撞：兩個不同元素映射到同一個哈希函數后得到的值可能相同。 基本思想：它引入多個哈希函數來減少沖突。如果某一個哈希函數得出元素不在集合中，則該元素肯定不在集合中；只有所有哈希函數都判定該元素在集合中，才能確定該元素存在于集合中。
1.3 原理
位數組：布隆過濾器使用一個m比特的數組來保存信息。在初始狀態時，對于長度為m的位數組，它的所有位都被置為0。
Hash函數：為了表達S={x1, x2,…,xn}這樣一個n個元素的集合，它使用k個相互獨立的哈希函數，分別將集合中的每個元素映射到{1,…,m}的范圍中。 添加元素到集合：當有變量被加入集合時，使用k個哈希函數得到k個哈希值，然后將數組中對應的比特位設置為1（假定有2個元素，3個映射函數） 注意：如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。
判斷元素是否存在：如判斷y是否屬于這個集合，只需要對y使用k個哈希函數得到k個哈希值，如果所有hash(y)的位置都是1，則布隆過濾器會認為y是集合中的元素，否則不在集合中。
1.4 誤判率和特性
思考：判斷兩個元素y1和y2。
y1：y1通過三個哈希函數的映射有一個位置為0，因此布隆過濾器會判斷y1不在集合中。 y2：y2通過三個哈希函數的映射所有位置均為1，因此布隆過濾器會判斷y2在集合中。但實際上，y2可能屬于這個集合，也可能不屬于，因為每個位置都可能與其他元素共用（即發生Hash沖突）。 誤判率 布隆過濾器的誤判：指多個輸入經過哈希之后在相同的bit位置都為1，這樣就無法判斷究竟是哪個輸入產生的。 誤判的概率：取決于Hash函數的個數、Hash函數沖撞的概率、位數組的大小。 通常在工程里Hash函數用3~5個，實際值視需求而定。 假陽性：把本來不存在布隆過濾器中的元素誤判為存在的情況叫做假陽性。 特性 從容器的角度 如果布隆過濾器判斷元素在集合中存在，則不一定存在； 如果布隆過濾器判斷不存在，則一定不存在。 從元素的角度 如果元素實際存在，則布隆過濾器一定判斷存在； 如果元素實際不存在，則布隆過濾器可能判斷存在。
1.5 優缺點
優點：它的空間效率和查詢時間都遠遠超過一般的數據結構（如傳統的List、Set、Map等數據結構）。 缺點 存在一定的誤判率； 存放在布隆過濾器的數據不能刪除。
1.6 適用場景和典型應用
適用場景：用于判定給定數據是否存在，但不嚴格要求100%正確的場合。 典型應用 數據庫防止穿庫。Bigtable、HBase、Cassandra以及Postgresql使用布隆過濾器來減少不存在的行或列的磁盤查找，大幅度提高數據庫查詢的性能。 判斷用戶是否閱讀過某視頻/文章。當然會導致一定的誤判，但不會讓用戶看到重復的內容。 緩存穿透場景。如果有一波冷數據，在緩存前先通過布隆過濾器。如果布隆過濾器返回不存在，則直接返回；只有布隆過濾器返回存在，才去查詢緩存，如果沒查詢到，則到數據庫查詢。 WEB攔截器，如果相同請求則攔截，防止重復被攻擊。用戶第一次請求，將請求參數放入布隆過濾器中，當第二次請求時，先判斷請求參數是否被布隆過濾器命中，可以提高緩存命中率。Google Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務。 布隆過濾器使用場景示意圖
2. 布隆過濾器的實現
2.1 布隆過濾器在Guava中的實現
概述 谷歌的Guava中提供了一個現成的布隆過濾器。 占用內存很小：如存儲100萬元素只占用0.87M的內存，生成了5個哈希函數。 說明 布隆過濾器提供的存放元素的方法是put() 布隆過濾器提供的判斷元素是否存在的方法是migjtContain() 布隆過濾器的誤判率默認設置為0.03，也可以在創建時自行指定。 位圖的容量是基于元素個數和誤判率計算出來的。 根據位數組的大小，可以進一步計算出哈希函數的個數。 實現示例 引入依賴
< dependency> < groupId> </ groupId> < artifactId> </ artifactId> < version> </ version> </ dependency> 實現示例
public class bloomFilterTest { public static void main ( String [ ] args) { BloomFilter < String > = BloomFilter . create ( Funnels . integerFunnel ( ) , 1500 , 0.01 ) ; String data = "data01" ; bloomFilter. put ( data) ; System . out. println ( filter. mightContain ( data) ) ; }
}
說明 當mightContain()方法返回true時，我們可以99％確定該元素在過濾器中；當過濾器返回false時，我們可以100％確定該元素不存在于過濾器中。 Guava提供的布隆過濾器實現算法比較權威，但只能在單機使用，而現在系統通常都是分布式場景。
2.2 基于Tair的布隆過濾器
概述：為了解決分布式場景的問題，集團的分布式緩存中間件Tair(Tair 2.0 RDB)也實現了BloomFilter。
實現示例
引入依賴< dependency> < groupId> </ groupId> < artifactId> </ artifactId> < version> </ version> </ dependency> 實現代碼RdbSmartApi rdbSmartApi = RdbSmartFactory . getClientManager ( "xxx" ) ;
rdbSmartApi. setPassWord ( "xxx" ) ;
rdbSmartApi. init ( ) ;
String filterName = "myBloomFilter" ;
Long size = 10000000L ;
double errorRate = 0.00001 ;
String result = rdbSmartApi. sync ( ) . bfreserve ( filterName. getBytes ( ) , size, errorRate) ;
if ( "OK" . equals ( result) ) { String data = "data01" ; boolean success = rdbSmartApi. sync ( ) . bfadd ( filterName. getBytes ( ) , data. getBytes ( ) ) ; if ( success) { boolean exist = rdbSmartApi. sync ( ) . bfexists ( filterName. getBytes ( ) , data. getBytes ( ) ) ; }
}
2.3 基于Redis的布隆過濾器
概述：Redis v4.0之后有了Module（模塊/插件）功能，Redis Modules讓Redis可以使用外部模塊擴展其功能，布隆過濾器就是其中的Module，官網推薦RedisBloom作為Redis布隆過濾器的Module。
Redis Modules的介紹：https://redis.io/modules RedisBloom的介紹：https://github.com/RedisBloom/RedisBloom 安裝RedisBloom 法1：直接編輯進行安裝git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make #編譯 會生成一個rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so #運行redis時加載布隆過濾器模塊
redis-cli # 啟動連接容器中的 redis 客戶端驗證
法2：使用Docker進行安裝docker pull redislabs/rebloom:latest # 拉取鏡像
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest #運行容器
docker exec -it redis-redisbloom bash
redis-cli
使用 基本指令bf.add：添加元素到布隆過濾器
bf.exists：判斷元素是否在布隆過濾器
bf.madd：添加多個元素到布隆過濾器
bf.mexists：判斷多個元素是否在布隆過濾器
127.0.0.1:6379> bf.add user Tom
(integer) 1
127.0.0.1:6379> bf.exists user Tom
(integer) 1
127.0.0.1:6379> bf.exists user John
(integer) 0
127.0.0.1:6379> bf.madd user Barry Jerry Mars
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists user Barry Linda
1) (integer) 1
2) (integer) 0
Redis的客戶端Redisson和lettuce基于布隆過濾器做了封裝。示例：Redisson< dependency> < groupId> </ groupId> < artifactId> </ artifactId> < version> </ version> </ dependency> public class RedissonBloomFilterDemo { public static void main ( String [ ] args) { Config config = new Config ( ) ; config. useSingleServer ( ) . setAddress ( "redis://127.0.0.1:6379" ) ; RedissonClient redisson = Redisson . create ( config) ; RBloomFilter < String > = redisson. getBloomFilter ( "user" ) ; bloomFilter. tryInit ( 55000000L , 0.03 ) ; bloomFilter. add ( "Tom" ) ; bloomFilter. add ( "Jack" ) ; System . out. println ( bloomFilter. count ( ) ) ; System . out. println ( bloomFilter. contains ( "Tom" ) ) ; System . out. println ( bloomFilter. contains ( "Linda" ) ) ; }
}
3. 布隆過濾器的變體
3.1 CountingBloomFilter（計數布隆過濾器）
背景：標準的布隆過濾器只支持插入和查找兩種操作，在集合是靜態集合時，它可以很好地工作。但是如果集合經常變動，其弊端就顯現出來了，因為它不支持刪除操作。 概述：CountingBloomFilter是BloomFilter的一個變種，它擴展標準布隆過濾器的數據結構，將底層數組的每一位擴展為一個4位大小的計數器Counter，用來存儲某個下標映射成功的頻次。它以占用更多的空間來換取支持刪除操作。 插入元素時，通過k個哈希函數映射到k個計數器，這些命中的計數器值增加1； 刪除元素時，刪除元素的時候，通過k個散列函數映射到k個計數器，這些計數器值減少1。 使用CBF判斷元素是否在集合的規則 某個元素通過k個散列函數映射到k個計數器，如果某個計數器的值為0，那么元素必定不在集合中； 某個元素通過k個散列函數映射到k個計數器，如果所有計數器的值都大于0，那么元素可能在集合中。
單機CountingBloomFilter的實現示例 引入依賴< dependency> < groupId> </ groupId> < artifactId> </ artifactId> < version> </ version> </ dependency> 實現代碼public class CountingBloomFilterDemo { public static void main ( String [ ] args) { int dataSize = 100000000 ; int hashCount = 3 ; int hashType = 1 ; CountingBloomFilter filter = new CountingBloomFilter ( dataSize, hashCount, hashType) ; String data = "data01" ; Key key = new Key ( data. getBytes ( ) ) ; filter. add ( key) ; boolean exist = filter. membershipTest ( key) ; filter. delete ( key) ; filter. membershipTest ( key) ; }
}
3.2 CuckooFilter(布谷鳥過濾器)
概述 解決標準BloomFilter無法刪除元素的問題；有更高的查詢效率；相比其他支持刪除的Filter更容易實現。 它源于布谷鳥哈希算法。
（1）布谷鳥哈希算法
數據結構：布谷鳥哈希表，它由一個桶數組組成，每個桶由一個數據項組成。 原理 每個插入項都有由哈希函數h1(x)和h2(x)確定的兩個候選桶，查找過程會檢查兩個桶是否任意一個桶包含此項。 如果x的兩個桶中任何一個是空的，則算法將x插入到該空桶中，插入完成； 如果兩個桶都沒有空間，項會選擇一個候選桶，踢出去現有的項，并將此被踢出項重新插入到它的備用位置。這個過程可能會重復，直到找到一個空桶或達到最大位移次數。如果沒有找到空桶，則認為此哈希表太滿，則進行擴容和ReHash后，再次插入。 雖然布谷鳥哈希可能執行一系列重置，但其均攤插入時間為O(1)。
說明
圖(a)：將新項x插入到8個桶的哈希表中的示例，其中x可以放置在桶2或6中。 圖(b)：表示待插入x的兩個桶都沒有空間，隨機選擇了候選桶6，踢出現有項a，重新放置“a”觸發了另一個重置，將現有的項“c”從桶4踢到桶1。 （2）布谷鳥過濾器
布谷鳥過濾器對布谷鳥哈希的改變
為了提高桶的利用率，使用多路哈希桶。 為了減少內存的使用，只存儲元素的指紋信息。 布谷鳥過濾器的數據結構：由一個哈希表組成，哈希表由一個桶數組組成，其中一個桶可以有多個條目，每個條目存儲一個指紋。
哈希計算兩個候選桶索引的方案
問題：布谷鳥過濾器只存儲指紋，因此無法恢復和重新哈希原始鍵以找到它們的替代位置； 解決：利用一種稱為部分鍵布谷鳥哈希的技術，來根據其指紋導出一個項的備用位置。 插入
Algorithm
1 : Insert
( x
)
f
= fingerprint
( x
) ;
i1
= hash ( x
) ;
i2
= i1 ⊕
hash ( f
) ;
if bucket
[ i1
] or bucket
[ i2
] has an empty entry thenadd f to that bucket
; return Done
;
// must relocate existing items
;
i
= randomly pick i1
or i2
;
for n
= 0 ; n
< MaxNumKicks
; n
+ + dorandomly select an entry e
from bucket
[ i
] ; swap f
and the fingerprint stored
in entry e
; i
= i ⊕
hash ( f
) ; if bucket
[ i
] has an empty entry thenadd f to bucket
[ i
] ; return Done
;
// Hashtable
is considered full
;
return Failure
;
查找：給定一個項x，算法首先根據公式 (1)計算x的指紋和兩個候選桶。然后讀取這兩個桶：如果兩個桶中的任何現有指紋匹配，則布谷鳥過濾器返回true，否則過濾器返回false。
Algorithm
2 : Lookup
( x
)
f
= fingerprint
( x
) ;
i1
= hash ( x
) ;
i2
= i1 ⊕
hash ( f
) ;
if bucket
[ i1
] or bucket
[ i2
] has f then
return True ;
return False ;
刪除：它檢查給定項的兩個候選桶。如果任何桶中的指紋匹配，則從該桶中刪除匹配指紋的一份副本。 注意：要安全地刪除項x，必須事先插入它，否則刪除非插入項可能會無意中刪除碰巧共享相同指紋的不同項。這一要求也適用于所有其他支持刪除的過濾器。
Algorithm
3 : Delete
( x
)
f
= fingerprint
( x
) ;
i1
= hash ( x
) ;
i2
= i1 ⊕
hash ( f
) ;
if bucket
[ i1
] or bucket
[ i2
] has f thenremove a copy of f
from this bucket
; return True ;
return False ;
說明：CuckooFilter不能擴容。因為我們已經丟失了原值 x，則無法計算擴容后新的位置 hash(x)
（3）布谷鳥過濾器的實現
CockooFilter的Java單機版實現
引入依賴< dependency> < groupId> </ groupId> < artifactId> </ artifactId> < version> </ version> </ dependency> 代碼實現public class CockooFilterDemo { public static void main ( String [ ] args) { String data = "data01" ; long dataSize = 100000000L ; CuckooFilter < String > = new CuckooFilter. Builder < String > ( Funnels . stringFunnel ( Charset . defaultCharset ( ) ) , dataSize) . build ( ) ; filter. put ( data) ; boolean exist = filter. mightContain ( data) ; filter. delete ( data) ; }
}
基于Redis的CockooFilter：Redis的module的形式同樣支持CuckooFilter。和BloomFilter一樣，Jedis也沒有CuckooFilter的客戶端api調用實現。下面是redis官網對支持CuckooFilter的操作說明。
基于Tair的CockooFilter：集團Tair RDB2.0支持高級數據結構中，同樣包含CockooFilter。
引入依賴< dependency> < groupId> </ groupId> < artifactId> </ artifactId> < version> </ version> </ dependency> 代碼實現public class CockooFilterTairDemo { public static void main ( String [ ] args) { RdbSmartApi rdbSmartApi = RdbSmartFactory . getClientManager ( "xxx" ) ; rdbSmartApi. setPassWord ( "xxx" ) ; rdbSmartApi. init ( ) ; String filterName = "myBloomFilter" ; Long size = 10000000L ; String result = rdbSmartApi. sync ( ) . cfreserve ( filterName. getBytes ( ) , size) ; if ( "OK" . equals ( result) ) { String data = "permission" ; boolean success = rdbSmartApi. sync ( ) . bfadd ( filterName. getBytes ( ) , data. getBytes ( ) ) ; if ( success) { boolean exist = rdbSmartApi. sync ( ) . bfexists ( filterName. getBytes ( ) , data. getBytes ( ) ) ; rdbSmartApi. sync ( ) . cfdel ( filterName. getBytes ( ) , data. getBytes ( ) ) ; } } }
}
3.3 ScalableBloomFilter（可動態擴容的布隆過濾器）
概述
TairBloom是云redis企業版（Tair3.0）上自帶的一個擴展數據結構，其采用redis module方式實現了一個可動態擴容的布隆過濾器(ScalableBloomFilter)。 TairBloom內部本質上是多層布隆過濾器(ScalableBloomFilter)的鏈式組合，只能執行插入、查詢操作，無法執行刪除操作。 它解決了標準布隆過濾器容量受限、無法動態擴容的問題；具有動態擴容的能力，可在容量不足或者false positive無法保證時進行自動動態擴容，業務無需擔心容量問題；非常適合需要對大量數據進行高效去重的場景。 ScalableBloomFilter的思想：新建一個布隆過濾器，將多個布隆過濾器“組裝”成一個布隆過濾器使用。
ScalableBloomFilter的原理
如圖展示的就是一個ScalableBloomFilter模型（下文簡稱SBF），該SBF一共包含BF0和BF1兩層。 插入過程：只會向最后一層插入數據 最開始時，SBF只包含BF0這一層，插入了a、b、c三個元素。 這時，假設BF0已經無法保證用戶設定的誤判率，此時就需要進行擴容，因此新的一層BF1被創建并加入進來。后來的d、e、f元素都會被插入到BF1中。 同理，當BF1也無法滿足該層事先設定的誤判率時，新的一層BF2也將被加入進來，如此進行下去。 查詢過程：由后向前 查詢g這個元素是否在SBF中 先在BF1中進行查詢。如果查詢顯示存在，則直接響應客戶端； 如果查詢顯示不存在，則繼續查詢BF0。如果BF0中顯示存在g，則響應客戶端g存在。否則，因為BF0已經是最后一層了，則響應客戶端g不存在。 說明：SBF的插入和查詢過程比較簡單。但是注意，首先，BF1在直觀上要比BF0長很多（m比特位數高）；其次，BF1上的散列函數k（哈希函數個數）也要比BF0上的大。
應用場景：非常適合推薦系統場景。文章閱讀功能，如果想留住用戶，就要盡可能給用戶推薦他喜歡類型的文章，但是又不能推薦重復的文章（特別是用戶最近剛讀過的文章）。為此，將用戶讀過的文章加入到TairBloom中，并在推薦給用戶之前，先去TairBloom中查詢一下該用戶是否讀過該文章，如果讀過就不推薦，否則就可以加入推薦列表。
參考資料
詳解布隆過濾器的原理，使用場景和注意事項 布谷鳥過濾器：實際上優于布隆過濾器 布谷鳥哈希和布谷鳥過濾器 冷飯新炒：理解布隆過濾器算法的實現原理 緩存穿透、緩存擊穿、緩存雪崩，看這篇就夠了 總結
以上是生活随笔 為你收集整理的高并发下的缓存问题及布隆过滤器 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
