亚洲全黄无码一级在线看_国产剧情久久久性色_无码av一区二区三区无码_亚洲成a×人片在线观看

當前位置: 首頁 > 科技新聞 >

內(nèi)存崩潰了?其實你只需要換一種方式

時間:2019-11-12 18:40來源:網(wǎng)絡(luò)整理 瀏覽:
在上一篇 Java 多線程爬蟲及分布式爬蟲架構(gòu)探索 中,我們使用了 JDK 自帶的 Set 集合來進行 URL 去重,看上去效果不錯,但是

在上一篇 Java 多線程爬蟲及分布式爬蟲架構(gòu)探索 中,我們使用了 JDK 自帶的 Set 集合來進行 URL 去重,看上去效果不錯,但是這種做法有一個致命了缺陷,就是隨著采集的 URL 增多,你需要的內(nèi)存越來越大,最終會導致你的內(nèi)存崩潰。那我們在不使用數(shù)據(jù)庫的情況下有沒有解決辦法呢?還記得我們在上一篇文章中提到的布隆過濾器嗎?它就可以完美解決這個問題,布隆過濾器有什么特殊的地方呢?接下來就一起來學習一下布隆過濾器。

內(nèi)存崩潰了?其實你只需要換一種方式

什么是布隆過濾器

布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu),比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu),它是在 1970 年由一個名叫布隆提出的,它實際上是由一個很長的二進制向量和一系列隨機映射函數(shù)組成,這點跟哈希表有些相同,但是相對哈希表來說布隆過濾器它更高效、占用空間更少,布隆過濾器有一個缺點那就是有一定的誤識別率和刪除困難。布隆過濾器只能告訴你某個元素一定不存在或者可能存在在集合中, 所以布隆過濾器經(jīng)常用來處理可以忍受判斷失誤的業(yè)務,比如爬蟲 URL 去重。

布隆過濾器原理

在說布隆過濾器原理之前,我們先來復習一下哈希表,在上一篇文章中,我們利用的是 Set 來進行 URL 去重,我們來看看 Set 的存儲模型

內(nèi)存崩潰了?其實你只需要換一種方式

Set url 去重

URL 經(jīng)過一個哈希函數(shù)后,將 URL 存入了數(shù)組里,這樣查詢時也是非常高效的,但是由于數(shù)組里存入的是 URL,隨著 URL 的增多,需要的數(shù)組越來越大,意味著你需要更多的內(nèi)存,比如我們采集了幾億的 URL,那么可能就需要上百G 的內(nèi)存,這是條件不允許的,因為內(nèi)存特別的昂貴,所以這個在 url 去重中是不可取的,占內(nèi)存更小的布隆過濾器就是一種不錯的選擇。

布隆過濾器實質(zhì)上由長度為 m 的位向量或位列表(僅包含 0 或 1 位值的列表)組成,最初所有值均設(shè)置為 0,如下所示。

內(nèi)存崩潰了?其實你只需要換一種方式

布隆過濾器

因為底層是 bit 數(shù)組,所以意味著數(shù)組只有 0、1 兩個值,跟哈希表一樣,我們將 URL 通過 K 個函數(shù)映射 bit 數(shù)組里,并且將指向的 Bit 數(shù)組對應的值改成 1 。我們以 /nba/2492297.html 為例,如下圖所示。

內(nèi)存崩潰了?其實你只需要換一種方式

布隆過濾器

/nba/2492297.html經(jīng)過三個哈希函數(shù)分別映射到了 1、4、9 的位置,這三個 bit 數(shù)組的值就變成了 1,我們再存入一個 /nba/2492298.html,此時 bit 數(shù)組就變成下面這樣:

內(nèi)存崩潰了?其實你只需要換一種方式

布隆過濾器

/nba/2492298.html被映射到了 0、4、11 的位置,所以此時 bit 數(shù)組上有 5 個位置的值為 1,本應該是有 6 個值為 1 的,但是因為在 4 這個位置重復了,所以會覆蓋。

布隆過濾器是如何判斷某個值一定不存在或者可能存在呢?通過判斷哈希函數(shù)映射到對應數(shù)組的值,如果都為 1,說明可能存在,如果有一個不為 1,說明一定不存在。對于一定不存在好理解,但是都為 1 時,為什么說可能存在呢?這跟哈希表一樣,哈希函數(shù)會產(chǎn)生哈希沖突,也就是說兩個不同的值經(jīng)過哈希函數(shù)都會得到同一個數(shù)組下標,布隆過濾器也是一樣的。我們以判斷 /nba/2492299.html 是否已經(jīng)采集過為例,經(jīng)過哈希函數(shù)映射的 bit 數(shù)組上的位置如下圖所示:

內(nèi)存崩潰了?其實你只需要換一種方式

布隆過濾器

/nba/2492299.html 被哈希函數(shù)映射到了 4、9、11 的位置,而這幾個位置的值都為 1 ,所以布隆過濾器就認為 /nba/2492299.html 被采集過了,實際上是沒有采集過的,這就說明了布隆過濾器存在誤判,這也是我們業(yè)務允許的。布隆過濾器的誤判率跟 bit 數(shù)組的大小和哈希函數(shù)的個數(shù)有關(guān)系,如果 bit 數(shù)組過小,哈希函數(shù)過多,那么 bit 數(shù)組的值很快都會變成 1,這樣誤判率就會越來越高,bit 數(shù)組過大,就會浪費更多的內(nèi)存,所以就要平衡好 bit 數(shù)組的大小和哈希函數(shù)的個數(shù),關(guān)于如何平衡這兩個的關(guān)系,不是我們這篇文章的重點。

布隆過濾器的原理我們已經(jīng)了解了,為了加深對布隆過濾器的理解,我們用 Java 來實現(xiàn)一個簡易版的布隆過濾器,代碼如下:

 

把上面這段代碼理解好對我們理解布隆過濾器非常有幫助,實際上在工作中并不需要我們自己實現(xiàn)布隆過濾器,谷歌已經(jīng)幫我們實現(xiàn)了布隆過濾器,在 Guava 包中提供了 BloomFilter,這個布隆過濾器實現(xiàn)的非常棒,下面就看看谷歌辦的布隆過濾器。

布隆過濾器 Guava 版

要使用 Guava 包下提供的 BloomFilter ,就需要引入 Guava 包,我們在 pom.xml 中引入下面依賴:

 

Guava 中的布隆過濾器實現(xiàn)的非常復雜,關(guān)于細節(jié)我們就不去探究了,我們就來看看 Guava 中布隆過濾器的構(gòu)造函數(shù)吧,Guava 中并沒有提供構(gòu)造函數(shù),而且提供了 create 方法來構(gòu)造布隆過濾器:

 

funnel:你要過濾數(shù)據(jù)的類型

expectedInsertions:你要存放的數(shù)據(jù)量

fpp:誤判率

你只需要傳入這三個參數(shù)你就可以使用 Guava 包中的布隆過濾器了,下面這我寫的一段 Guava 布隆過濾器測試程序,可以改動 fpp 多運行幾次,體驗 Guava 的布隆過濾器。

 

布隆過濾器的應用

緩存擊穿

緩存擊穿是查詢數(shù)據(jù)庫中不存在的數(shù)據(jù),如果有用戶惡意模擬請求很多緩存中不存在的數(shù)據(jù),由于緩存中都沒有,導致這些請求短時間內(nèi)直接落在了DB上,對DB產(chǎn)生壓力,導致數(shù)據(jù)庫異常。

最常見的解決辦法就是采用布隆過濾器,將所有可能存在的數(shù)據(jù)哈希到一個足夠大的bitmap中,一個一定不存在的數(shù)據(jù)會被這個bitmap攔截掉,從而避免了對底層存儲系統(tǒng)的查詢壓力。下面是一段偽代碼:

 

爬蟲 URL 去重

爬蟲是對 url 的去重,防止 url 重復采集,這也是我們這篇文章重點講解的內(nèi)容

垃圾郵件識別

從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱,將垃圾郵箱添加到布隆過濾器中,然后判斷某個郵件是否是存在在布隆過濾器中,存在說明就是垃圾郵箱。

【責任編輯:華軒 TEL:(010)68476606】
推薦內(nèi)容