[譯]使用Redis Bitamp簡單快速實時計算指標

傳統上，度量指標一般由批處理作業執行（每小時執行，每天執行等）。Redis 中的 Bitmap 可以允許我們實時計算指標，並且非常節省空間。在1.28億使用者場景中，經典度量指標（如’日活’）在 MacBook Pro上只需不到50毫秒，而且只需要16 MB記憶體。

1. Bitmap

又可以稱之為 Bitset。

Bitmap 或 Bitset 是一個由 0 和 1 構成的陣列。在 Bitmap 中每一個 bit 被設定為 0 或 1，陣列中的每個位置被稱為 offset。AND，OR，XOR等操作符，以及其他位操作都是 Bitmaps 的常用操作。

2. 基數

Bitmap 中 1 的個數稱之為基數。我們有一種有效演算法來計算基數，例如，在 MacBook Pro 上，在包含10億位填充90％的 Bitmap 上計算基數耗時 21.1 ms。

3. Redis中的Bitmap

Redis 允許二進位制鍵和二進位制值。Bitmap 也是二進位制值。將鍵指定 offset 設定為 0 或 1， setbit（key，offset，value） 操作需要用  O(1) 時間複雜度。

4. 一個簡單的例子：每日活躍使用者

為了統計今天登入的不同使用者，我們建立了一個 Bitmap，其中每個使用者都由一個 offset 標識。當用戶訪問頁面或執行操作時，會將表示使用者ID的 offset 設定為 1。

在這個簡單的例子中，每次使用者登入時，我們都會執行：

redis.setbit(daily_active_users，user_id，1)

這會將 daily_active_users Bitmap 鍵對應 offset 設定為1。這是一個 O(1) 時間複雜度操作。對此 Bitmap 進行基數統計會統計出今天一共登入了 9 個使用者。鍵是 daily_active_users，值為 1011110100100101。

當然，由於每天活躍使用者每天都會在改變，我們需要一種方法每天建立一個新的 Bitmap。我們只需在 Bitmap 鍵後面追加一個日期即可。例如，如果我們想要計算某天在音樂應用中播放至少1首歌曲的不同使用者，我們可以將鍵名稱設定為 play:yyyy-mm-dd 。如果我們想要計算每小時播放至少一首歌曲的使用者數量，我們可以將鍵名稱設定為 play:yyyy-mm-dd-hh 。為了計算每日指標，只要使用者播放歌曲，我們就會在 play：yyyy-mm-dd 鍵中將使用者對應的 bit 設定為1。

redis.setbit(play:yyyy-mm-dd, user_id, 1)

今天播放歌曲的不同使用者是儲存以 play:yyyy-mm-dd 為鍵的值。要計算每週或每月度量指標，我們可以簡單地計算一週或一個月中所有每日 Bitmap 的並集，然後計算結果 Bitmap 的總體基數。

你還可以非常輕鬆地提取更復雜的指標。例如，11月播放歌曲的會員使用者為：

5. 使用1.28億使用者進行效能比較

下表顯示了針對1.28億使用者在1天，7天和30天計算的比較。通過組合每日 Bitmap 計算7日和30日指標：

6. 優化

在上面的示例中，我們可以通過在 Redis 中快取計算的每日，每週，每月計數來優化每週和每月計算。

這是一種非常靈活的方法。快取的另一個好處是它允許快速群組分析，例如使用手機的每週唯一使用者 - 手機使用者 Bitmap 與每週活躍使用者 Bitmap 的交集。或者，如果我們想要滾動計算過去n天內的唯一使用者，那麼快取每日唯一使用者的計數會使這變得簡單 - 只需從快取中獲取前n-1天並將其與實時每日計數結合起來即可，而這隻需要50ms。

7. 示例程式碼

下面的Java程式碼片段指定使用者操作和日期來計算唯一使用者：

import redis.clients.jedis.Jedis;
import java.util.BitSet;
...
Jedis redis = new Jedis("localhost");
...
public int uniqueCount(String action, String date) {
String key = action + ":" + date;
BitSet users = BitSet.valueOf(redis.get(key.getBytes()));
return users.cardinality();
}

下面的程式碼片段計算指定使用者操作和日期列表的唯一使用者：

import redis.clients.jedis.Jedis;
import java.util.BitSet;
...
Jedis redis = new Jedis("localhost");
...
public int uniqueCount(String action, String... dates){
BitSet all = new BitSet();
for (String date : dates) {
String key = action + ":" + date;
BitSet users = BitSet.valueOf(redis.get(key.getBytes()));
all.or(users);
}
return all.cardinality();
}

英譯對照

• 基數: Population Count

歡迎關注我的公眾號和部落格：