布隆過濾器在實時指標計算中的應用

02-27

在實時指標計算中，經常需要進行去重判斷和處理，比如實時統計UV（按用戶去重訪問量），同時為了追求指標計算的性能，一般都是在內存中完成計算邏輯，中間數據也需要放在內存中，這就帶來了內存消耗過多的問題，尤其當去重的明細數據達到上億甚至更多的時候。

那麼如何更好的適應實時指標計算中的去重處理呢：

1、精確去重：這種情況下明細數據需要保存，同時可以通過數據傾斜的方式，對去重值進行分桶Hash，把一個節點的內存壓力分到多個節點上，再把每個桶裡面的值進行加和。關於Hash的介紹可以看這篇文章：Hash介紹

2、模糊去重：如果業務統計的精度要求不高，可以使用相關的去重演算法，可以大大降低內存的使用量。常用的模糊去重演算法有布隆過濾器和基數估計。

本文主要介紹一下布隆過濾器：

布隆過濾器（Bloom Filter）是由Howard Bloom在1970年提出的二進位向量數據結構，它具有很好的空間和時間效率，尤其是空間效率極高，BF常常被用來檢測某個元素是否是巨量數據集合中的成員。
BF可以高效地表徵集合數據，其使用長度為m的位數組來存儲集合信息，同時使用k個相互獨立的哈希函數將數據映射到位數組空間。其基本思想如下：首先，將長度為m的位數組元素全部置為0。對於集合S中的某個成員a，分別使用k個哈希函數對其計算，如果hi(a)=x(1≤i≤k,1≤x≤m)，則將位數組的第x位置為1，對於成員a來說，經過k個哈希函數計算後，可能會將位數組中的w位（w≤k）設置為1。對於集合中的其他成員也如此處理，這樣即可完成位數組空間的集合表示。
查詢的時候：使用相同的k個哈希函數計算，如果其對應位數組中的w位（w≤k）都為1，則判斷成員屬於集合；只要有任意一位為0，則判斷成員不屬於集合。BF可能會出現誤判：即判斷為屬於集合但實際不屬於集合，但BF不會出現漏判：即判斷為不屬於集合那一定不屬於集合。
BF的誤判率是可以控制的，計算出來的去重值比真實值小，採用布隆過濾器演算法存儲1億條數據只需要存儲100多MB的空間。