高可用服務設計之如何應對快取穿透

2020 年 4 月 13 日
筆記
JAVA, 分散式, 高並發&高可用

背景

用戶中心是授權邏輯與用戶資訊相關邏輯構建的應用。分散式系統中，大多數業務都需要和用戶中心打交道，為了保證用戶中心服務的高可用，避免不了做快取、導入搜索引擎從而降低資料庫的壓力。然而有些不經過用戶中心授權的業務場景查詢用戶中心的數據，可能引發大量無效的查詢，發生快取穿透，直接對搜索引擎和資料庫造成壓力。如何解決用戶中心快取穿透的問題呢？接下來就著重說一下布隆過濾器是怎麼「隔檔」這些無效查詢的。

快取穿透

快取穿透是指用戶查詢數據，在資料庫沒有，自然在快取中也不會有。這樣就導致用戶查詢的時候，在快取中找不到對應key的value，每次都要去資料庫再查詢一遍，然後返回空（相當於進行了兩次無用的查詢）。這樣請求就繞過快取直接查資料庫。

布隆過濾器

基本概念

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進位向量(點陣圖)和一系列隨機映射函數（哈希函數）。
布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的演算法，缺點是有一定的誤識別率和刪除困難。

特點

空間效率高和查詢效率高的概率型數據結構。
對於一個元素檢測是否存在的調用，BloomFilter會告訴調用者兩個結果之一：可能存在或者一定不存在。
一個很長的二進位向量（位數組）。
一系列隨機函數（哈希）。
有一定的誤判率（哈希表是精確匹配）。

原理

布隆過濾器（Bloom Filter）的核心實現是一個超大的位數組和幾個哈希函數。假設位數組的長度為m，哈希函數的個數為k。

(1) 添加元素過程

將要添加的元素給k個哈希函數。
得到對應於位數組上的k個位置。
將這k個位置設為1。

(2) 查詢元素過程

將要查詢的元素給k個哈希函數。
得到對應於位數組上的k個位置。
如果k個位置有一個為0，則肯定不在集合中。
如果k個位置全部為1，則可能在集合中。

演示

(1)參考地址

//www.jasondavies.com/bloomfilter

(2)可能存在

(3)一定不存在

Guava Bloom Filter

Guava中，布隆過濾器的實現主要涉及到2個類， BloomFilter和 BloomFilterStrategies。首先來看一下 BloomFilter的成員變數。需要注意的是不同Guava版本的 BloomFilter實現不同。

BitArrays 是定義在BloomFilterStrategies中的內部類，封裝了布隆過濾器底層bit數組的操作。
numHashFunctions表示哈希函數的個數，即上文公式提到的k。
Funnel主要是把任意類型的數據轉化成Java基本數據類型（primitive value，如char，byte，int……），默認用java.nio.ByteBuffer實現，最終均轉化為byte數組。
Strategy是定義在BloomFilter類內部的介面，程式碼如下，有3個方法，put（插入元素），mightContain（判定元素是否存在）和ordinal方法（可以理解為枚舉類中那個默認方法）。

BloomFilterStrategies類，首先它是實現了BloomFilter.Strategy 介面的一個枚舉類，其次它有兩個2枚舉值，MURMUR128_MITZ_32和MURMUR128_MITZ_64，分別對應了32位哈希映射函數和64位哈希映射函數，後者使用了murmur3 hash可生成128位哈希值，具有更大的空間，不過原理是相通的。

MURMUR128_MITZ_64實現原理可以參考（//rrd.me/gDkD5）。

BitArray是guava bloom filter底層bit數組的一個實現類。Guava使用的是一個long型數組實現了類似BitSet的數據結構。第一個構造函數傳入了一個bit位的位數bits，然後bits除以64並向上取整得到long型數組的大小。get和set操作根據bit位的索引index，找到對應的操作對象data[index >>> 6]（等價於data[index / 64]），分別跟（1L << index）與操作和或操作相應的結果。

Redis Bloom Filter

分散式系統直接使用guava bloom filter在某些業務場景下不是很方便，既然是分散式環境，最好還是通過分散式快取封裝一版布隆過濾器。

通過對guava bloom filter的分析，由單機版改造成分散式版，只需要重新實現三個guava bloom filter的三個類（BloomFilter，BloomFilterStrategies，BitArray）。

RedisBitArray改造不是很麻煩，只需要引入操作分散式快取的JedisCluster對象就好了。get和set操作對應JedisCluster對象的getbit和setbit操作（針對String類型的值，Redis通過位操作實現了BitMap數據結構）。

BloomFilter和BloomFilterStrategies的改造相對比較簡單，這裡就不詳細說明了。

Routing Bloom Filter

為什麼要有路由布隆過濾器？通過上面的公式可以知道，當要插入的樣本數量n越大，那麼需要分配的記憶體容量m也會越大。也就是布隆過濾器的不當使用極易產生大 Value，增加記憶體溢出或者阻塞風險，因此生成環境中建議對體積龐大的布隆過濾器進行拆分，拆分的規則我們定義為按照一定的路由規則對應到不同的布隆過濾器。

(1) 設計方案

(2) 路由策略

routing方法根據樣本計算出路由key值。
exceptedInsertions方法根據樣本獲取到路由key值，然後計算期望插入的樣本數量。

(3) 成員變數

ROUTE_MAP是本地快取，存儲RoutingStrategy對象routing方法計算出的路由key值以及對應的RedisBloomFilter實例。
routingStrategy是路由策略RoutingStrategy實例。
bfRedisKeyPrefix是Redis布隆過濾器bit數組在redis中對應的key值前綴。
bfKeysMappingRedisKey存儲了所有Redis布隆過濾器bit數組在redis中對應的key（即bfRedisKeyPrefix + 路由key）的集合。

(4) put操作

獲取當前樣本對象的routeKey，ROUTE_MAP的computeIfAbsent方法根據routeKey獲取對應的Redis Bloom Filter，如果不存在則創建一個新的Redis Bloom Filter對象實例並保存到ROUTE_MAP中。變數bloomFilterRedisKey = bfRedisKeyPrefix + routeKey，也就是Redis Bloom Filter bit數組在redis中存儲的key值，最後保存在分散式快取的集合中（即bfKeysMappingRedisKey對應的集合）。

(5) mightContain操作

和put操作的流程基本一致，在獲取routeKey對應的Redis Bloom Filter實例的時候，如果不存在需要判斷分散式快取bfKeysMappingRedisKey對應的集合中是否存在bloomFilterRedisKey，如果不存在說明put操作沒有創建對應的Redis Bloom Filter實例，直接返回null。

(6) 監控資訊

approximateElementCount，布隆過濾器中可能存在的元素個數。
bitSize，布隆過濾器bit數組大小。
bitCount，布隆過濾器bit數組中bit位是1的數量。
keyLength，布隆過濾器bit數組通過strlen統計的長度。

註：布隆過濾器的bit數組在redis中對應的數據類型是String哦！

應用場景

網頁爬蟲對URL的去重。
黑名單，垃圾郵件過濾。
解決資料庫快取擊穿。

實際應用

消息中心給用戶推送消息的時候，是按照先微信小程式用戶，否則公眾號用戶串列邏輯來執行的（大多數消息都是按照用戶手機號推送的）。小程式的用戶體系相對公眾號的用戶體系是較少的，而且小程式用戶訂閱消息的量級增長的緩慢。這就出現了很多不是小程式用戶的查詢請求，也就是出現了上面提到 快取穿透 現象，無形之中會增加搜索引擎和資料庫壓力。

小程式用戶查詢服務集成了布隆過濾器，很優雅的解決了快取穿透的問題。業務上線初期，每天大約有200W到300W的請求，可以過濾掉90%以上的無效用戶查詢請求。看著這鮮明的效果，欣喜若狂，心想著這方案集成的太完美了，真香！

源碼參考

請關注微信訂閱號（演算法和技術SHARING），回復：bloomfilter，便可查看。

參考資料

//www.jianshu.com/p/2104d11ee0a2

//zhuanlan.zhihu.com/p/43263751

//blog.csdn.net/u012422440/article/details/94088166

//www.jianshu.com/p/44b4b42931d4

Tags: JAVA 分散式高並發&高可用