公眾號怎么做微網(wǎng)站百度站長工具驗證
場景描述
小程序用戶的openid作為最主要的業(yè)務(wù)查詢字段,在做了緩存設(shè)計之后仍有非常高頻的查詢,通過埋點簡單統(tǒng)計約在每日1000w次。
其中:由于有新增用戶原因,導(dǎo)致請求的openid根本不存在MySQL數(shù)據(jù)庫中,這部分統(tǒng)計約占30%左右,也就是約300w次查詢是浪費的。假設(shè)openid的總量可能達到10億級別
解決思路:基于redis使用布隆過濾器?
方案介紹
1. 布隆過濾器
布隆過濾器(Bloom Filter)
是一種數(shù)據(jù)結(jié)構(gòu),其主要功能是判斷某個元素是否出現(xiàn)在集合中。
它通過使用多個哈希函數(shù)將元素映射到一個位數(shù)組中,并將對應(yīng)位標(biāo)記為1,來實現(xiàn)對元素的判重。
如果一個元素在位數(shù)組中對應(yīng)的位置上有一位為0,那么該元素一定不存在于集合中,
如果所有對應(yīng)位都為1,那么該元素可能存在于集合中。具體來說:
當(dāng)要加入一個元素時,使用多個不同的哈希函數(shù)對該元素進行哈希,得到多個哈希值,然后將這些哈希值對應(yīng)的位數(shù)組上的位置置為1。
當(dāng)查找一個元素時,同樣使用多個哈希函數(shù)進行哈希,然后查看對應(yīng)位置上的位,
如果存在任意一位為0,那么該元素不存在于集合中;
如果所有位都為1,那么該元素可能存在于集合中,需要進一步確認(rèn)。但是,布隆過濾器存在一定的誤判率。
對于一個元素,如果多個哈希函數(shù)將其映射到的位都已被標(biāo)記為1,則它可能被誤判為存在于集合中,即有一定的假陽性率 。
誤判率取決于哈希函數(shù)的數(shù)量和位向量的長度。
2. 10億數(shù)據(jù)如何做布隆過濾?
·?redis的bitmap
Bitmap:是一種Bit數(shù)組數(shù)據(jù)結(jié)構(gòu),它的主要作用是儲存0和1兩個狀態(tài)。
在Redis中,Bitmap通過字符串來實現(xiàn),一個字符串可以存儲超過2^32個元素,所以一個bloom能存儲的最大上限就是2^32個,約42.9億。占用的內(nèi)存是512M
雖然單個bitmap最大可達到42億,但是算上誤差率其實是不夠的,而且在redis中我們也應(yīng)該盡量避免這種大key的使用
· 分片
- 范圍劃分:將 32-bit 的范圍 ([0, n)) 劃分為 2^10 個桶,每一個桶有一個 Container 來存放一個數(shù)值的低26位;
- 存儲:在存儲和查詢數(shù)值的時候,將一個數(shù)值 k 劃分為高 10 位(k % 2^10)和低 26 位(k mod 2^26),取高 10 位找到對應(yīng)的桶,然后在低 26 位存放在相應(yīng)的 Container 中;
- 查詢判斷:當(dāng)查詢一個數(shù)值 k 是否存在時,我們只需要判斷 k mod 2^26 是否存在于對應(yīng)的 Container 中即可。
· 實現(xiàn)取高位和低位代碼?
取高位作桶,就是通過位運算向右移10位
將一個數(shù)的二進制位向左或向右移動特定的位數(shù)。向左移動相當(dāng)于在該數(shù)的二進制表示中加上多個0,向右移動相當(dāng)于去掉多余的二進制位$container = $hash >> 10;
取低位作數(shù)據(jù)字段,就是通過&位運算取26位
它對兩個數(shù)的每一個二進制位進行比較,只有當(dāng)兩個數(shù)的對應(yīng)二進制位都為1時,結(jié)果才會將該位置設(shè)置為1,否則設(shè)置為0
0x3FFFFFF是26位全1的二進制數(shù)的16進制表示方式
可以簡單理解為就是截取了一個數(shù)的低26位$index ? ? = $hash & 0x3FFFFFF;?
· go-zero的bloom介紹(core/bloom/bloom.go)
// New create a Filter, store is the backed redis, key is the key for the bloom filter, // bits is how many bits will be used, maps is how many hashes for each addition. // best practices: // elements - means how many actual elements // when maps = 14, formula: 0.7*(bits/maps), bits = 20*elements, the error rate is 0.000067 < 1e-4 // for detailed error rate table, see http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html func New(store *redis.Redis, key string, bits uint) *Filter {return &Filter{bits: bits,bitSet: newRedisBitSet(store, key, bits),} }
go-zero內(nèi)置的bloom默認(rèn)采用的hash次數(shù)是14,元素預(yù)估需要使用的bitmap位數(shù)是20倍多元素數(shù)量,錯誤率在0.000067左右
· Hash函數(shù)規(guī)劃
已知元素總量為10億,分片數(shù)為2^10=1024,那么每個分片元素數(shù)量為976562,需要的bitmap長度是 20*976562 = 19531240,也就是小于2^25=33554432(redis官網(wǎng)上介紹,bitmap長度達到2^26-1大約需要8M內(nèi)存),那么總內(nèi)存預(yù)估使用8G左右,分散在集群的各個節(jié)點上
所以保留一定的彈性范圍,在使用go-zero自帶的bloom時,key根據(jù)2^10進行分片,單個bloom的bits=30000000