如何使用bloomfilter構(gòu)建大型java緩存系統(tǒng)-java開發(fā)java經(jīng)驗技巧

《如何使用bloomfilter構(gòu)建大型java緩存系統(tǒng)-java開發(fā)java經(jīng)驗技巧》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、如何使用bloomfiltcr構(gòu)建大型Java緩存系統(tǒng)-Java開發(fā)Java經(jīng)驗技巧如何使用bloomfilter構(gòu)建大型Java緩存系統(tǒng)本文illImportNew-劉家財翻譯口javacodegeekso歡迎加入翻譯小組。轉(zhuǎn)載詰見文末要求。冃樂在如今的軟件當(dāng)中，緩存是解決很多問題的一個關(guān)鍵概念。你的應(yīng)用叮能會進(jìn)行CPU密集型運(yùn)算。你當(dāng)然不想讓這些運(yùn)算一邊又一邊的重復(fù)執(zhí)行，相反，你可以只執(zhí)行一次，把這個結(jié)果放在內(nèi)存屮作為緩存。有時系統(tǒng)的瓶頸在I/O操作上,比如你不想重復(fù)的查詢數(shù)據(jù)庫，你想把結(jié)果緩存起來，只在數(shù)據(jù)發(fā)

2、生變化時才去數(shù)據(jù)查詢來更新緩存。與上面的情況類似，冇些場合下我們需要進(jìn)行快速的查找來決定如何處理新來的請求。例如，考慮卜?面這種情況，你需要確認(rèn)一個URL是否指向一個惡意網(wǎng)站，這種需求可能會冇很多。如果我們把所冇惡意網(wǎng)站的URL緩存起來，那么會山用很大的空間。或者另一種情況，需要確認(rèn)用戶輸入的字符串是包含了美國的地名。像“華盛頓的博物館”一一在這個字符串屮，華盛頓是美國的一個地名。我們應(yīng)該把美國所冇的地名保存在內(nèi)存中然后再查詢嗎？那樣的話緩存會冇多大？是否能在不使用數(shù)據(jù)庫的前提卜?來高效地完成？這就是為什么我們要跨

3、越基本的數(shù)據(jù)結(jié)構(gòu)map,在更高級的數(shù)據(jù)結(jié)構(gòu)像布隆過濾器(bloomfilter)中來尋找答案。你可以把布隆過濾器看做Java中的集合(collection),你可以往它里面添加元素，查詢某個元素是否存在(就像一個HashSet)。如果布隆過濾器說沒有這個元索，那么口J以肯定不含有這個元索，但是如果布隆過濾器說有某個元素，那么這個結(jié)果可能是錯謀的。如果我們在設(shè)計布隆過濾器時足夠細(xì)心，我們可以把這種出錯的概率控制在可接受范圍內(nèi)。解釋布隆過濾器被設(shè)計為一個具有N的元素的位數(shù)組A(bitarray),初始時所有的位都置為0

4、.添加元素要添加一個元索，我們需要提供k個哈希函數(shù)。每個函數(shù)都能返回一個值，這個值必須能夠作為位數(shù)組的索引(可以通過對數(shù)組長度進(jìn)行取模得到)。然后，我們把位數(shù)組在這個索引處的值設(shè)為1。例如，第一個哈希函數(shù)作用于元素1上，返冋X。類似的，笫二個笫三個哈希函數(shù)返冋y與Z,那么：A[x]=A[y]=A[z]=1查找元素查找的過程與上面的過程類似，元素將會被會被不同的哈希函數(shù)處理三次，每個哈希函數(shù)都返回一個作為位數(shù)組索引值的整數(shù)，然后我們檢測位數(shù)組在X、y與7處的值是否為1。如果有一處不為1,那么就說明這個元索沒有被添加到

5、這個布隆過濾器中。如杲都為1,就說明這個元素在布隆過濾器里面。當(dāng)然，會有一定誤判的概率。算法優(yōu)化通過上面的解釋我們口J以知道，如果想設(shè)計出一個好的布隆過濾器，我們必須遵循以下準(zhǔn)則：?好的哈希函數(shù)能夠盡可能的返回寬范圍的哈希值。?位數(shù)組的大小(用m表示)非常重?zé)崛绻。敲此械奈缓芸炀投紩毁x值為1,這樣就增加了誤判的幾率。?哈希兩數(shù)的個數(shù)(川k表示)對索引值的均勻分配也很重要。計算m的公式如下：m=-nlogp/(log2)2;這里p為可接受的誤判率。計算k的公式如下：k=m/nlog(2)這里k二哈希函數(shù)個數(shù)

6、，呼位數(shù)組個數(shù)，n二待檢測元素的個數(shù)(后而會用到這幾個字母)。哈希算法哈希算法是影響布隆過濾器性能的地方。我們需耍選擇一個效率高但不耗時的哈希函數(shù)，在論文《更少的哈希函數(shù)，相同的性能指標(biāo)：構(gòu)造一個更好的布隆過濾器》中，討論了如何選用2個哈希函數(shù)來模擬k個哈希函數(shù)。首先，我們需要計算兩個哈希函數(shù)hl(x)與h2(x)。然后，我們可以用這兩個哈希函數(shù)來模仿產(chǎn)生k個哈希函數(shù)的效果：gi(x)=hl(x)+ih2(x);這里i的取值范圍是1到k的整數(shù)。Googleguava類庫使用這個技巧實現(xiàn)了-?個布隆過濾器，哈希算法的

7、主要邏輯如下：longhash64=…；//calculatea64bithashfunction//splititintwohalvesof32bithashvaluesinthashl二(int)hash64;inthash2二(int)(hash64>>>32);//Generatekdifferenthashfunctionswithasimpleloopfor(inti=1;i<=numHashFunctions;i++){intnextHash=hashl+i*hash2;應(yīng)用從數(shù)學(xué)公式屮，我們可以很明

8、顯的知道使用布隆過濾器來解決問題。但是，我們需要很好地理解布隆過濾器所能解決問題的領(lǐng)域。像我們可以使用布隆過濾器來存放美國的所有城市，因為城市的數(shù)量是可以大概確定的，所以我們可以確定n（待檢測元素的個數(shù)）的值。根據(jù)需求來修改P（誤判概率）的值，在這種情況下，我們能夠設(shè)計出一個查詢耗時少，內(nèi)存使用率高的緩存機(jī)制。實現(xiàn)GoogleGuava類庫有—?個實現(xiàn)，查看