2023-06-11：redis中，如何在100個(gè)億URL中快速判斷某URL是否存在？

答案2023-06-11：

傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)的不足

當(dāng)然有人會(huì)想，我直接將網(wǎng)頁URL存入數(shù)據(jù)庫進(jìn)行查找不就好了，或者建立一個(gè)哈希表進(jìn)行查找不就OK了。

當(dāng)數(shù)據(jù)量小的時(shí)候，這么思考是對(duì)的，

確實(shí)，將值映射到 HashMap 的 Key，可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)返回結(jié)果，具有高效的優(yōu)點(diǎn)。但是 HashMap 的實(shí)現(xiàn)也存在一些不足，例如存儲(chǔ)容量占比較高。考慮到負(fù)載因子的存在，通常需要預(yù)留一定的空間，導(dǎo)致實(shí)際空間不能被完全利用。例如，如果有一個(gè)1000萬大小的 HashMap，以String類型為Key（長度不超過16個(gè)字符，且非常少重復(fù)），以Integer類型為Value，需要占據(jù)多少空間呢？實(shí)際上，它將占用1.2GB內(nèi)存。相比之下，存儲(chǔ)1000萬個(gè)int類型的數(shù)據(jù)只需要大約40MB空間，占比僅為3%；而存儲(chǔ)1000萬個(gè)Integer類型的數(shù)據(jù)則需要約161MB空間，占比高達(dá)13.3%。因此，一旦數(shù)據(jù)量增大到數(shù)億級(jí)別，HashMap 所占據(jù)的內(nèi)存大小將變得非?？捎^。

如果整個(gè)網(wǎng)頁黑名單系統(tǒng)包含100億個(gè)網(wǎng)頁URL，則簡單的數(shù)據(jù)庫查找操作將非常費(fèi)時(shí)，并且如果每個(gè)URL空間為64B，則整個(gè)系統(tǒng)需要的內(nèi)存空間將達(dá)到640GB，這對(duì)于一般的服務(wù)器來說是一個(gè)非常大的需求，難以實(shí)現(xiàn)。

布隆過濾器

布隆過濾器簡介

1970 年布隆提出了一種布隆過濾器的算法，用來判斷一個(gè)元素是否在一個(gè)集合中。 這種算法由一個(gè)二進(jìn)制數(shù)組和一個(gè) Hash 算法組成。

本質(zhì)上布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。

相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是確切的。

實(shí)際上，布隆過濾器被廣泛應(yīng)用于網(wǎng)頁黑名單系統(tǒng)、垃圾郵件過濾系統(tǒng)、爬蟲網(wǎng)址判重系統(tǒng)等領(lǐng)域。Google 著名的分布式數(shù)據(jù)庫 Bigtable 就使用了布隆過濾器來查找不存在的行或列，以減少磁盤查找的IO次數(shù)。此外，Google Chrome瀏覽器也使用布隆過濾器來加速安全瀏覽服務(wù)。

布隆過濾器的誤判問題

?通過哈希計(jì)算得到的在數(shù)組上的位置并不一定代表元素真正存在于集合中

?誤判問題的本質(zhì)是哈希沖突，即不同的元素可能哈希到相同的數(shù)組位置

?如果一個(gè)元素的哈希值不在數(shù)組中，則一定不存在于集合中，但是如果哈希值在數(shù)組中，則存在誤判的概率（誤判）

優(yōu)化方案

增大哈希數(shù)組的長度，使其能夠容納更多的元素。需要根據(jù)集合大小和誤判率等因素，預(yù)估合適的數(shù)組長度；

增加哈希函數(shù)的數(shù)量，以減少哈希沖突的概率。多個(gè)哈希函數(shù)可以讓元素哈希到多個(gè)位置上，從而降低誤判率。

布隆過濾器重要的三個(gè)公式

1.假設(shè)數(shù)據(jù)量為n，預(yù)期的失誤率為p（布隆過濾器大小和每個(gè)樣本的大小無關(guān)）。

2.根據(jù)n和p，算出BloomFilter一共需要多少個(gè)bit位，向上取整，記為m。

3.根據(jù)m和n，算出BloomFilter需要多少個(gè)哈希函數(shù)，向上取整，記為k。

4.根據(jù)修正公式，算出真實(shí)的失誤率p_true。

golang代碼如下：

package?main

import?(
????"fmt"
????"math"
)

func?main()?{
????p?:=?0.0001??????????//預(yù)期失誤率，萬分之一
????n?:=?100_0000_0000.0?//數(shù)據(jù)量100億
????m?:=?-n?*?math.Log(p)?/?(math.Ln2?*?math.Ln2)
????m?=?math.Ceil(m)
????k?:=?math.Ln2?*?m?/?n
????k?=?math.Ceil(k)
????ptrue?:=?math.Pow(1-math.Pow(math.E,?-n*k/m),?k)
????fmt.Println("比特位m：",?int(m))
????fmt.Println("哈希函數(shù)個(gè)數(shù)k：",?k)
????fmt.Printf("真實(shí)失誤率ptrue：%f%%\n",?ptrue*100)
????fmt.Printf("占用空間：%fG\n",?m/8/1024/1024/1024)
}