大數據實時日活計算之Bloom Filter

04-21

需求背景

在做大數據統計時，需要實時統計APP各個時間段的用戶活躍數，以此觀察各個時段用戶的訪問情況，便於產品做更好運營策略，同時還能起到監控異常的作用。

實時統計框架

而實時統計通常採用的框架是kafka+storm+redis進行計算，如下圖所示：

首先，通過flume收集日誌，一份上傳到HDFS上，通過mapreducer或spark進行離線計算；同時也會上傳到Kafka，進行實時計算。
其次，storm接收kafka數據，實時進行業務分析和計算，將用戶和計算結果存儲在redis

最後，前端通過讀取redis的計算結果在報表或圖表中展示出來。而實時統計日活最重要的點是判斷用戶是否在該時間段內已經來過？

簡單方案

最簡單的方式使用imei(用imei作為用戶的惟一標示) + date(一般為一個小時或半個小時作為時間段) 作為key存儲到redis,以此來判斷用戶是否在該時間段已經訪問過APP。其流程圖如下：

方法雖然簡單可行，但存在的問題是，由於運營活動或其他原因造成用戶活躍非常大，就會需要大量redis內存存儲用戶集合，而redis內存是比較昂貴的。那能否用少量內存來存儲用戶集合？我們很容易想到使用bit數組來存儲用戶集合，即用一位或多位表示一個用戶，這就大大減少空間的使用。但因為imei是一串字元，如何把imei轉化成bit數組中一位或多位？

Bloom Filter

如何將imei轉化bit數組中一個或多個位置，其最有效就是使用hash函數進行映射，但我們知道存儲用戶越多，其他誤差率是非常大，很顯然不符合我們的需求。最後想了Bloom

Filter演算法 ,不僅能將imei映射到bit數組中，而且誤差還在接受範圍內。而Bloom

Filter演算法其核心就是使用多個hash函數來表示元素，從而降低衝突率，以此滿足用戶需求;Bloom

Filter會使用一個bit數組，多個獨立的hash函數來存儲元素和判斷元素是否存在。

下面簡單介紹一下Bloom Filter是如何存儲元素和判斷元素是否存在的。

1.初始狀態

假設Bloom Filter使用m大小bit數組來存儲元素以及3個hash函數來映射元素所存儲的位置。初始狀態，bit組中每個位置都設置為0。

2.存儲元素

例如在存儲元素X1,通過三個hash函數進行映射，h1(X1)=1,h2(X1)=4,h3(X2)=6。然後在bit數組中對應位置設置為1，以此表示元素X1。當然在存儲多個元素，無可避免會存在一個位置會被設置為1多次，設置多次過程中，只有第一次設置是起作用。例如圖中第6的位置被設置了兩次。

3.判斷元素元素

在判斷元素Y1是否集合中存在時，同樣使用這3個hash函數對元素Y1進行映射，所映射的位置在bit數組中只有一個位置為0，則Y1在集合不存在；否則Y1集合素中已存在。當然如果判斷元素Y1在集合存在，也無法100%保證元素Y1真正在集合中存在。

例如圖中Y1通過第2個hash函數所映射的位置為0，則Y1不存在；而Y2通過3個hash函數所映射的位置都為1，表示Y2在元素中存在。

4.誤差和hash函數個數設置

我們使用Bloom

Filter演算法，是會存在誤差。所以怎麼設定bit數組大小和hash函數個數，使得誤差最小？

假設bit數組大小為m,hash函數個數為k以及需要存儲的元素個為n,通過數學推導，可以得出最小誤差P(error)和hash函數個數k

Bloom Filter實現

1.舊版判斷用戶是否存在

該版本使用多個位置表示imei(即用戶)。

public boolean exist1(String key, String value, HahsType[] func) { for (HahsType f : func) { long offset = f.hash(value); try { Boolean bExist = RedisLimitHelper.setbit(jedisCluster, key, offset, true); if (!bExist) { return false; } } catch (Exception e) { } } return true;//之所以返回true,以確保出現異不會計數}

2.新版判斷用戶素是否存在

在上一個版本判斷用戶是否存在時，使用多個位置存儲元素，就會有多次需要訪問Redis；為了減少對Redis訪問；可以看到，Bloom

Filter使用的多個hash算出的每個位置，其實對應一個二進位數，所以我們只需把這個二進位數據轉化十進位，然後根據這數字所在位置是否為1來判斷用戶是否存在，這樣只需要訪問redis一次即可。

public boolean exist(String key, String value, HahsType[] func) { long index = 0; //不同的hash可能映射到相同的位置,相同位置記錄一個即可 Set<Long> numSet = new HashSet<Long>(); for (HahsType f : func) { numSet.add(f.hash(value)); } for (long num : numSet) { index += 2 << num; } try { return RedisLimitHelper.setbit(jedisCluster, key, index, true); } catch (Exception e) { } return true;//之所以返回true,以確保出現異不會計數}

3.hash函數

在使用多個hash函數時，為了方便，並沒有採用不同的hash演算法；而使用同一個hash演算法，只是其seed不同而已。其實現如下

public static class HahsType { private int size; private int seed; public HahsType(int size, int seed) { this.size = size; this.seed = seed; } public long hash(String value) { long result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } return (size - 1) & result; }}

4.統計流程

結果對比

1.內存對比

簡單方案

Bloom Filter方案

2.過期key對比

簡單方案

Bloom Filter方案

從結果可以看無論是在redis內存使用上和過期key數據量上，都有很大的優勢。

總結

通過結果可以看出，使用Bloom Filter來存儲用戶和判斷用戶元素是否存在，極大的節省了redis內存資源開銷；另外也可以用來進行實時留存計算。

但Bloom Filter也存在自己的缺點，因為其本質使用的是hash的原因，夫存在一定誤判斷，造成統計數據會存在一定誤差；所以對於需要精確的統計需求，Bloom Filter是不適合；另外Bloom Filter不能對元素進行刪除(雖然可以通過擴展的Bloom Filter是可以刪除元素)。

aHR0cDovL3dlaXhpbi5xcS5jb20vci9CamtjQkdURWhqbjVyU0JuOTJ3VQ== (二維碼自動識別)