場景描述

小程序用戶的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的使用

· 分片

1. 范圍劃分：將 32-bit 的范圍 ([0, n)) 劃分為 2^10 個桶，每一個桶有一個 Container 來存放一個數(shù)值的低26位；
2. 存儲：在存儲和查詢數(shù)值的時候，將一個數(shù)值 k 劃分為高 10 位(k % 2^10)和低 26 位(k mod 2^26)，取高 10 位找到對應(yīng)的桶，然后在低 26 位存放在相應(yīng)的 Container 中；
3. 查詢判斷：當(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