巧用 Redis Hyperloglog，輕鬆統計 UV 資料
本文由 yanglbme 原創，首發於公眾號“Doocs開源社群”，歡迎轉載。
計數不同使用者行為的最快方法之一是寫一個類似 SELECT COUNT(DISTINCT user) 的 SQL。但是，如果實時資料的量達到了上百萬條，這可能會很昂貴。你可能會想到另一種方法，就是將使用者儲存在一個 Redis set 集合中，因為 set 天然具備去重的功能。
但是，這種解決方案也帶來了它固有的問題。如果一個統計不同使用者記錄的應用程式執行有多個例項，那麼我們需要具有巨大 RAM 大小的記憶體快取解決方案。如果要處理 1000 萬個不同的記錄，每個記錄分配 10 位元組，那麼僅在一個時間範圍內我們就至少需要 100MB 的記憶體。因此，這不是記憶體有效的解決方案。
在本文中，我想向你展示如何通過在 Redis Cache 伺服器中分配少於 2MB 的記憶體來處理一百萬個不同的使用者記錄。
我們都知道，Redis 有好幾種資料結構，比如：String、BitMap、Set、Sorted Set等。在這裡我想特別強調一下Hyperloglog，因為它最適合通過減少記憶體消耗來統計不同的使用者操作。
Hyper LogLog
Hyper LogLog 計數器的名稱是具有自描述性的。 你可以僅僅使用loglog(Nmax)+ O(1)位來估計基數為 Nmax 的集合的基數。
Redis Hyperloglog 操作
要進行 Redis Hyperloglog 的操作，我們可以使用以下三個命令：
PFADDPFCOUNTPFMERGE我們用一個實際的例子來解釋這些命令。比如，有這麼個場景，使用者登入到系統，我們需要在一小時內統計不同的使用者。 因此，我們需要一個 key，例如 USER:LOGIN:2019092818。 換句話說，我們要統計在 2019 年 09 月 28 日下午 18 點至 19 點之間發生使用者登入操作的非重複使用者數。對於將來的時間，我們也需要使用對應的 key 進行表示，比如 2019111100、2019111101、2019111102 等。
我們假設，使用者 A、B、C、D、E 和 F 在下午 18 點至 19 點之間登入了系統。
127.0.0.1:6379> pfadd USER:LOGIN:2019092818 A(integer) 1127.0.0.1:6379> pfadd USER:LOGIN:2019092818 B C D E F(integer) 1127.0.0.1:6379>複製程式碼當進行計數時，你會得到預期的 6。
127.0.0.1:6379> pfcount USER:LOGIN:2019092818(integer) 6複製程式碼如果 A 和 B 在這個時間內多次登入系統，你也將得到相同的結果，因為我們僅保留不同的使用者。
127.0.0.1:6379> pfadd USER:LOGIN:2019092818 A B(integer) 0127.0.0.1:6379> pfcount USER:LOGIN:2019092818(integer) 6複製程式碼如果使用者 A~F 和另外一個其他使用者 G 在下午 19 點至下午 20 點之間登入系統：
127.0.0.1:6379> pfadd USER:LOGIN:2019092819 A B C D E F G(integer) 1127.0.0.1:6379> pfcount USER:LOGIN:2019092819(integer) 7複製程式碼現在，我們有兩個鍵 USER:LOGIN:2019092818 和 USER:LOGIN:2019092819，如果我們想知道在 18 點到 20 點（2 小時）之間有多少不同的使用者登入到系統中，我們可以直接使用pfcount命令對兩個鍵進行合併計數：
127.0.0.1:6379> pfcount USER:LOGIN:2019092818 USER:LOGIN:2019092819(integer) 7複製程式碼如果我們需要保留鍵值而避免一遍又一遍地計數，那麼我們可以將鍵合併為一個鍵 USER:LOGIN:2019092818-19，然後直接對該鍵進行pfcount操作，如下所示。
127.0.0.1:6379> pfmerge USER:LOGIN:2019092818-19 USER:LOGIN:2019092818 USER:LOGIN:2019092819OK127.0.0.1:6379> pfcount USER:LOGIN:2019092818-19(integer) 7複製程式碼接下來，我們寫個程式，比較使用 SET、Hyperloglog 兩種方式儲存不同使用者登入行為的記憶體佔用。
import redis.clients.jedis.Jedis;public class RedisTest { private static final int NUM = 1000000; // 100萬用戶 private static final String SET_KEY = "SET:USER:LOGIN:2019082811"; private static final String PF_KEY = "PF:USER:LOGIN:2019082811"; public static void main(String[] args) { Jedis client = new Jedis(); for (int i = 0; i < NUM; ++i) { System.out.println(i); client.sadd(SET_KEY, "USER" + i); client.pfadd(PF_KEY, "USER" + i); } }}複製程式碼我們看一下結果，對於 100 萬用戶，Set 可以精確儲存，而 Hyperloglog 則稍有偏差，多出了 7336，誤差率大概是在 0.7%。而在記憶體佔用上，Set 消耗了 10888895B≈10MB，Hyperloglog 只消耗了 10481B≈10KB 的記憶體，幾乎是 Set 的 1/1000。
127.0.0.1:6379> scard SET:USER:LOGIN:2019082811(integer) 1000000127.0.0.1:6379> pfcount PF:USER:LOGIN:2019082811(integer) 1007336127.0.0.1:6379> debug object SET:USER:LOGIN:2019082811Value at:00007FD74F841940 refcount:1 encoding:hashtable serializedlength:10888895 lru:9308508 lru_seconds_idle:53127.0.0.1:6379> debug object PF:USER:LOGIN:2019082811Value at:00007FD74F7A5940 refcount:1 encoding:raw serializedlength:10481 lru:9308523 lru_seconds_idle:50複製程式碼serializedlength 引數表示該 key 儲存的內容所佔用的記憶體位元組數。
滑動視窗的不同計數
要在滑動視窗中計算不同的使用者，我們需要指定一個較小的粒度，在這種情況下，分鐘級的就足夠了，我們將使用者行為儲存在格式為 yyyyMMddHHmm 的鍵中，例如 USER:LOGIN:201909281820。
當我們要統計最後 5 分鐘的不同使用者操作時，只需要將 5 個鍵進行合併計算即可：
127.0.0.1:6379> pfcount 201909281821 201909281822 201909281823 201909281824 201909281825(integer) 6複製程式碼由此看來，統計最近一小時我們需要 60 個鍵，統計最近一天需要 1440 個鍵，最近 7 天則需要 10080 個鍵。 我們擁有的鍵越多，合併它們時就需要耗費更多的時間進行計算。 因此，我們應該減少鍵的數量，不僅要保留具有 yyyyMMddHHmm 格式的鍵，還應保留小時、日和月的時間間隔，並使用 yyyyMM，yyyyMMdd，yyyyMMddHH。
使用這些新鍵，pfcount 操作可以花費更少的時間，例如：
如果你要計算使用者最近一天的操作並且僅使用分鐘鍵，你需要合併所有 1440 個鍵。但是，如果你在分鐘鍵之外還使用小時鍵，則只需要 60 個分鐘鍵和 24 個小時鍵，因此我們只需要 84 個鍵。
package utils;import org.apache.commons.lang3.time.DateUtils;import java.text.SimpleDateFormat;import java.util.*;import java.util.stream.Collectors;public class HLLUtils { private static String TIME_FORMAT_MONTH_DAY = "MMdd"; private static String TIME_FORMAT_DAY_MINUTES = "MMddHHmm"; private static String TIME_FORMAT_DAY_HOURS = "MMddHH"; private static SimpleDateFormat FORMAT_MONTH_DAY = new SimpleDateFormat(TIME_FORMAT_MONTH_DAY); private static SimpleDateFormat FORMAT_DAY_HOURS = new SimpleDateFormat(TIME_FORMAT_DAY_HOURS); private static SimpleDateFormat FORMAT_DAY_MINUTES = new SimpleDateFormat(TIME_FORMAT_DAY_MINUTES); /** * 獲取兩個日期之間的鍵 * * @param d1 日期1 * @param d2 日期2 * @return 鍵列表 */ public static List<String> parse(Date d1, Date d2) { List<String> list = new ArrayList<>(); if (d1.compareTo(d2) == 0) { return list; } long delta = d2.getTime() - d1.getTime(); if (delta == 0) { return list; } if (delta < DateUtils.MILLIS_PER_HOUR) { // 若時間差小於 1 小時 int minutesDiff = (int) (delta / DateUtils.MILLIS_PER_MINUTE); Date date1Increment = d1; while (d2.compareTo(date1Increment) > 0 && minutesDiff > 0) { list.add(FORMAT_DAY_MINUTES.format(date1Increment)); date1Increment = DateUtils.addMinutes(date1Increment, 1); } } else if (delta < DateUtils.MILLIS_PER_DAY) { // 若時間差小於 1 天 Date dateLastPortionHour = DateUtils.truncate(d2, Calendar.HOUR_OF_DAY); list.addAll(parse(dateLastPortionHour, d2)); long delta2 = dateLastPortionHour.getTime() - d1.getTime(); int hoursDiff = (int) (delta2 / DateUtils.MILLIS_PER_HOUR); Date date1Increment = DateUtils.addHours(dateLastPortionHour, -1 * hoursDiff); while (dateLastPortionHour.compareTo(date1Increment) > 0 && hoursDiff > 0) { list.add(FORMAT_DAY_HOURS.format(date1Increment)); date1Increment = DateUtils.addHours(date1Increment, 1); } list.addAll(parse(d1, DateUtils.addHours(dateLastPortionHour, -1 * hoursDiff))); } else { Date dateLastPortionDay = DateUtils.truncate(d2, Calendar.DAY_OF_MONTH); list.addAll(parse(dateLastPortionDay, d2)); long delta2 = dateLastPortionDay.getTime() - d1.getTime(); int daysDiff = (int) (delta2 / DateUtils.MILLIS_PER_DAY); // 若時間差小於 1 個月 Date date1Increment = DateUtils.addDays(dateLastPortionDay, -1 * daysDiff); while (dateLastPortionDay.compareTo(date1Increment) > 0 && daysDiff > 0) { list.add(FORMAT_MONTH_DAY.format(date1Increment)); date1Increment = DateUtils.addDays(date1Increment, 1); } list.addAll(parse(d1, DateUtils.addDays(dateLastPortionDay, -1 * daysDiff))); } return list; } /** * 獲取從 date 往前推 minutes 分鐘的鍵列表 * * @param date 特定日期 * @param minutes 分鐘數 * @return 鍵列表 */ public static List<String> getLastMinutes(Date date, int minutes) { return parse(DateUtils.addMinutes(date, -1 * minutes), date); } /** * 獲取從 date 往前推 hours 個小時的鍵列表 * * @param date 特定日期 * @param hours 小時數 * @return 鍵列表 */ public static List<String> getLastHours(Date date, int hours) { return parse(DateUtils.addHours(date, -1 * hours), date); } /** * 獲取從 date 開始往前推 days 天的鍵列表 * * @param date 特定日期 * @param days 天數 * @return 鍵列表 */ public static List<String> getLastDays(Date date, int days) { return parse(DateUtils.addDays(date, -1 * days), date); } /** * 為keys列表新增字首 * * @param keys 鍵列表 * @param prefix 字首符號 * @return 添加了字首的鍵列表 */ public static List<String> addPrefix(List<String> keys, String prefix) { return keys.stream().map(key -> prefix + key).collect(Collectors.toList()); }}複製程式碼我們來看一下兩個日期之間計算出的樣本鍵列表。 你可能已經意識到了，鍵的數量應該儘可能少，這樣合併鍵進行統計時代價將會比較小。 因此，我們不僅要將時間範圍劃分為分鐘，而且還要劃分為小時、天、月等。
BEGIN=201909281800&END=201909281920[USER:LOGIN:09281900, USER:LOGIN:09281901, USER:LOGIN:09281902, USER:LOGIN:09281903, USER:LOGIN:09281904, USER:LOGIN:09281905, USER:LOGIN:09281906, USER:LOGIN:09281907, USER:LOGIN:09281908, USER:LOGIN:09281909, USER:LOGIN:09281910, USER:LOGIN:09281911, USER:LOGIN:09281912, USER:LOGIN:09281913, USER:LOGIN:09281914, USER:LOGIN:09281915, USER:LOGIN:09281916, USER:LOGIN:09281917, USER:LOGIN:09281918, USER:LOGIN:09281919, USER:LOGIN:092818]複製程式碼BEGIN=20190928191100&END=20190930163800[USER:LOGIN:09301600, USER:LOGIN:09301601, USER:LOGIN:09301602, USER:LOGIN:09301603, USER:LOGIN:09301604, USER:LOGIN:09301605, USER:LOGIN:09301606, USER:LOGIN:09301607, USER:LOGIN:09301608, USER:LOGIN:09301609, USER:LOGIN:09301610, USER:LOGIN:09301611, USER:LOGIN:09301612, USER:LOGIN:09301613, USER:LOGIN:09301614, USER:LOGIN:09301615, USER:LOGIN:09301616, USER:LOGIN:09301617, USER:LOGIN:09301618, USER:LOGIN:09301619, USER:LOGIN:09301620, USER:LOGIN:09301621, USER:LOGIN:09301622, USER:LOGIN:09301623, USER:LOGIN:09301624, USER:LOGIN:09301625, USER:LOGIN:09301626, USER:LOGIN:09301627, USER:LOGIN:09301628, USER:LOGIN:09301629, USER:LOGIN:09301630, USER:LOGIN:09301631, USER:LOGIN:09301632, USER:LOGIN:09301633, USER:LOGIN:09301634, USER:LOGIN:09301635, USER:LOGIN:09301636, USER:LOGIN:09301637, USER:LOGIN:093000, USER:LOGIN:093001, USER:LOGIN:093002, USER:LOGIN:093003, USER:LOGIN:093004, USER:LOGIN:093005, USER:LOGIN:093006, USER:LOGIN:093007, USER:LOGIN:093008, USER:LOGIN:093009, USER:LOGIN:093010, USER:LOGIN:093011, USER:LOGIN:093012, USER:LOGIN:093013, USER:LOGIN:093014, USER:LOGIN:093015, USER:LOGIN:0929, USER:LOGIN:092820, USER:LOGIN:092821, USER:LOGIN:092822, USER:LOGIN:092823, USER:LOGIN:09281911, USER:LOGIN:09281912, USER:LOGIN:09281913, USER:LOGIN:09281914, USER:LOGIN:09281915, USER:LOGIN:09281916, USER:LOGIN:09281917, USER:LOGIN:09281918, USER:LOGIN:09281919, USER:LOGIN:09281920, USER:LOGIN:09281921, USER:LOGIN:09281922, USER:LOGIN:09281923, USER:LOGIN:09281924, USER:LOGIN:09281925, USER:LOGIN:09281926, USER:LOGIN:09281927, USER:LOGIN:09281928, USER:LOGIN:09281929, USER:LOGIN:09281930, USER:LOGIN:09281931, USER:LOGIN:09281932, USER:LOGIN:09281933, USER:LOGIN:09281934, USER:LOGIN:09281935, USER:LOGIN:09281936, USER:LOGIN:09281937, USER:LOGIN:09281938, USER:LOGIN:09281939, USER:LOGIN:09281940, USER:LOGIN:09281941, USER:LOGIN:09281942, USER:LOGIN:09281943, USER:LOGIN:09281944, USER:LOGIN:09281945, USER:LOGIN:09281946, USER:LOGIN:09281947, USER:LOGIN:09281948, USER:LOGIN:09281949, USER:LOGIN:09281950, USER:LOGIN:09281951, USER:LOGIN:09281952, USER:LOGIN:09281953, USER:LOGIN:09281954, USER:LOGIN:09281955, USER:LOGIN:09281956, USER:LOGIN:09281957, USER:LOGIN:09281958, USER:LOGIN:09281959]複製程式碼例項
其實，有了上面生成 key 的方法，我們便可以很輕鬆地在實際場景中應用 Redis 的 HyperLoglog 進行資料統計，比如我們要統計從此刻開始往前推一小時、一天、一週的 UV。
程式碼實現如下：
import redis.clients.jedis.Jedis;import utils.JedisUtils;import java.util.Date;import java.util.List;import static utils.HLLUtils.addPrefix;import static utils.HLLUtils.getLastDays;import static utils.HLLUtils.getLastHours;public class UVCounter { private Jedis client = JedisUtils.getClient(); private static final String PREFIX = "USER:LOGIN:"; public UVCounter() { } /** * 獲取周UV * * @return UV數 */ public long getWeeklyUV() { List<String> suffixKeys = getLastDays(new Date(), 7); List<String> keys = addPrefix(suffixKeys, PREFIX); return client.pfcount(keys.toArray(new String[0])); } /** * 獲取日UV * * @return UV數 */ public long getDailyUV() { List<String> suffixKeys = getLastHours(new Date(), 24); List<String> keys = addPrefix(suffixKeys, PREFIX); return client.pfcount(keys.toArray(new String[0])); } /** * 獲取小時UV * * @return UV數 */ public long getHourlyUV() { List<String> suffixKeys = getLastHours(new Date(), 1); List<String> keys = addPrefix(suffixKeys, PREFIX); return client.pfcount(keys.toArray(new String[0])); }}複製程式碼怎麼樣，你學會了嗎？
最新評論