如何使用bloomfilter構建大型java緩存系統-java開發(fā)java經驗技巧

《如何使用bloomfilter構建大型java緩存系統-java開發(fā)java經驗技巧》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

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

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

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

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

5、這個布隆過濾器中。如杲都為1,就說明這個元素在布隆過濾器里面。當然，會有一定誤判的概率。算法優(yōu)化通過上面的解釋我們口J以知道，如果想設計出一個好的布隆過濾器，我們必須遵循以下準則：?好的哈希函數能夠盡可能的返回寬范圍的哈希值。?位數組的大小(用m表示)非常重熱如果太小，那么所有的位很快就都會被賦值為1,這樣就增加了誤判的幾率。?哈希兩數的個數(川k表示)對索引值的均勻分配也很重要。計算m的公式如下：m=-nlogp/(log2)2;這里p為可接受的誤判率。計算k的公式如下：k=m/nlog(2)這里k二哈希函數個數

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

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

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