getspool.com的重要統計資料是實時計算的。Redis的bitmap讓我們可以實時的進行類似的統計,并且極其節省空間。在模拟1億2千8百萬使用者的模拟環境下,在一台MacBookPro上,典型的統計如“日使用者數”(dailyunique users)
的時間消耗小于50ms, 占用16MB記憶體。Spool現在還沒有1億2千8百萬使用者,但是我們的方案可以應對這樣的規模。我們想分享這是如何做到的,也許能幫到其它創業公司。
Bitmap以及Redis Bitmaps快速入門(Crash Course on Bitmap and Redis Bitmaps)
Bitmap(即Bitset)
Bitmap是一串連續的2進制數字(0或1),每一位所在的位置為偏移(offset),在bitmap上可執行AND,OR,XOR以及其它位操作。
位圖計數(Population Count)
位圖計數統計的是bitmap中值為1的位的個數。位圖計數的效率很高,例如,一個bitmap包含10億個位,90%的位都置為1,在一台MacBook Pro上對其做位圖計數需要21.1ms。SSE4甚至有對×××(integer)做位圖計數的硬體指令。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQ3chVEa0V3bT9CX5RXa2Fmcn9CXwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVMwJjW1x2VlZnRyoldRhlW1VTaitmTzkVdjJjYzpkMMZ3bENGMShUYvwFd4VGdvwlMvw1ayFWbyVGdhd3P2QDM4MTMygTMxMzNwMTMwIzLcRXZu5ibkN3Yuc2bsJmLn1Wavw1LcpDc0RHaiojIsJye.jpg)
Redis Bitmaps
Redis允許使用二進制資料的Key(binary keys) 和二進制資料的Value(binary
values)。Bitmap就是二進制資料的value。Redis的 setbit(key, offset,
value)操作對指定的key的value的指定偏移(offset)的位置1或0,時間複雜度是O(1)。
一個簡單的例子:日活躍使用者
為了統計今日登入的使用者數,我們建立了一個bitmap,每一位辨別一個使用者ID。當某個使用者通路我們的網頁或執行了某個操作,就在bitmap中把辨別此使用者的位置為1。在Redis中擷取此bitmap的key值是通過使用者執行操作的類型和時間戳獲得的。
這個簡單的例子中,每次使用者登入時會執行一次redis.setbit(daily_active_users, user_id,
1)。将bitmap中對應位置的位置為1,時間複雜度是O(1)。統計bitmap結果顯示有今天有9個使用者登入。Bitmap的key是daily_active_users,它的值是1011110100100101。
因為日活躍使用者每天都變化,是以需要每天建立一個新的bitmap。我們簡單地把日期添加到key後面,實作了這個功能。例如,要統計某一天有多少個使用者至少聽了一個音樂app中的一首歌曲,可以把這個bitmap的redis
key設計為play:yyyy-mm-dd-hh。當使用者聽了一首歌曲,我們隻是簡單地在bitmap中把辨別這個使用者的位置為1,時間複雜度是O(1)。
[java]
- Redis.setbit(play:yyyy-mm-dd, user_id, 1)
Redis.setbit(play:yyyy-mm-dd, user_id, 1)
今天聽過歌曲的使用者就是key是play:yyyy-mm-dd的bitmap的位圖計數。如果要按周或月統計,隻要對這周或這個月的所有bitmap求并集,得出新的bitmap,在對它做位圖計數。
利用這些bitmap做其它複雜的統計也非常容易。例如,統計11月聽過歌曲的進階使用者(premium user):
(play:2011-11-01∪ play:2011-11-02∪ … ∪ play:2011-11-30)∩premium:2011-11
1億2千8百萬使用者的性能比較(Performance comparison using 128 million users)
下面的表格顯示了在1億2千8百萬使用者上完成的時間粒度為1天,一周,一個月的使用者統計的時間消耗比較。
Period | Time(ms) |
Daily | 50.2 |
Weekly | 392.0 |
Monthly | 1624.8 |
優化(Optimizations)
前面的例子中,我們把日統計,周統計,月統計緩存到Redis,以加快統計速度。
這是一種非常靈活的方法。這樣進行緩存的額外紅利是可以進行更多的統計,如每周活躍的手機使用者—求手機使用者的bitmap與周活躍使用者的交集。或者,如果要統計過去n天的活躍使用者數,緩存的日活躍使用者使這樣的統計變得簡單——從cache中擷取過去n-1天的日活躍使用者bitmap和今天的bitmap,對它們做并集(Union),時間消耗是50ms。
示例代碼(SampleCode)
下面的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 date) { String key = action +
":" + date; BitSet users =
BitSet.valueOf(redis.get(key.getBytes())); return
users.cardinality(); }
下面的Java代碼用來統計某個使用者操作在一個指定多個日期的活躍使用者。
- 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();
- }
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(); }
References:
[1] Redis setbit command