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

答案2023-06-11：

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

當(dāng)然有人會(huì)想，我直接將網(wǎng)頁(yè)URL存入數(shù)據(jù)庫(kù)進(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萬(wàn)大小的 HashMap，以String類(lèi)型為Key（長(zhǎng)度不超過(guò)16個(gè)字符，且非常少重復(fù)），以Integer類(lèi)型為Value，需要占據(jù)多少空間呢？實(shí)際上，它將占用1.2GB內(nèi)存。相比之下，存儲(chǔ)1000萬(wàn)個(gè)int類(lèi)型的數(shù)據(jù)只需要大約40MB空間，占比僅為3%；而存儲(chǔ)1000萬(wàn)個(gè)Integer類(lèi)型的數(shù)據(jù)則需要約161MB空間，占比高達(dá)13.3%。因此，一旦數(shù)據(jù)量增大到數(shù)億級(jí)別，HashMap 所占據(jù)的內(nèi)存大小將變得非常可觀(guān)。

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

布隆過(guò)濾器

布隆過(guò)濾器簡(jiǎn)介

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

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

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

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

布隆過(guò)濾器的誤判問(wèn)題

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

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

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

優(yōu)化方案

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

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

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

1.假設(shè)數(shù)據(jù)量為n，預(yù)期的失誤率為p（布隆過(guò)濾器大小和每個(gè)樣本的大小無(wú)關(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ù)期失誤率，萬(wàn)分之一
	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)
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-479224.html

到了這里，關(guān)于2023-06-11：redis中，如何在100個(gè)億URL中快速判斷某URL是否存在？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！