Redis系列8：Bitmap實現億萬級數據計算
Redis系列1：深刻理解高性能Redis的本質
Redis系列2：數據持久化提高可用性
Redis系列3：高可用之主從架構
Redis系列4：高可用之Sentinel(哨兵模式）
Redis系列5：深入分析Cluster 集群模式
追求性能極致：Redis6.0的多執行緒模型
追求性能極致：客戶端快取帶來的革命
1 前言
我們在第一篇 深刻理解高性能Redis的本質 的時候就介紹過Redis的幾種基本數據結構，它是基於不同業務場景而設計的：
- 動態字元串(REDIS_STRING)：整數(REDIS_ENCODING_INT)、字元串(REDIS_ENCODING_RAW)
- 雙端列表(REDIS_ENCODING_LINKEDLIST)
- 壓縮列表(REDIS_ENCODING_ZIPLIST)
- 跳躍表(REDIS_ENCODING_SKIPLIST)
- 哈希表(REDIS_HASH)
- 整數集合(REDIS_ENCODING_INTSET)
除了這常見數據類型，還有一些不常用的數據類型，如 BitMap、Geo、HyperLogLog 等等，他們在各自的領域為大數據量的統計，後面我們一一來介紹，學習下他們的實現原理和應用場景。
2 BitMap介紹
BitMap （點陣圖）的底層數據結構使用的是String類型的的 SDS 數據結構來保存。因為一個位元組8個bit位，為了有效的將位元組的8個bit都利用到位，使用數組模式存儲。
並且每個bit都使用二值狀態表示，要麼0，要麼1。
所以，BitMap 是通過一個 bit 位來表示某個元素對應的值或者狀態, 它的結構如下，key 對應元素本身；offset即是偏移量，固定整型，一般存數組下表或者唯一值；value存儲的是二值（要麼0要麼1），一般用來表示狀態，如性別、是否登錄、是否打卡等。
從上面可以看出這邊使用一個位元組表示1行，每1行存儲8個bit，就是可以存儲8個狀態位，極大的提高了空間利用。這也是BitMap的優勢，我們可以使用很少的位元組，存儲大量的在線狀態、打卡標記等狀態資訊，非常有效果。
我們可以使用 setbit, getbit, bitcount 等幾個相關命令來管理BitMap。語法如下：
SETBIT key offset value
上面說過了，key是元素名稱， offset 必須是數值類型，value 只能是 0 或者 1，如果我們存儲一個用戶的在線狀態，用戶，程式碼如下：
//設置在線狀態
// $redis->setBit('online', $uid, 1);
$redis->setBit('online', 5, 1);
$redis->setBit('online', 9, 1);
則具體體現為：
| byte | bit0 | bit1 | bit2 | bit3 | bit4 | bit5 | bit6 | bit7 |
|---|---|---|---|---|---|---|---|---|
| buf[0] | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| buf[1] | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
可以看出用戶ID為5和9被打上1的標誌，代表在線狀態，其他未設置值默認為0，是離線狀態。
除了Set之外，還有getBit、bitCount等語法，如下：
// 獲取是否在線的狀態
$isOnline = $redis->getBit('online', $uid);
// 獲取在線人數 統計
$onlineNum = $redis->bitCount('online');
3 BitMap的主要應用場景
上面介紹了BitMap的原理和狀態存儲的優勢。那我們存儲了bit位，其實目的還是為了高效的計算，而不是簡單的狀態記錄。
而在實際的應用場景中，他主要解決如下幾個類型的需求：
3.1 狀態統計
上面其實我們已經演示過了，這種場景最常見，因為值只能是1或者0，所以所有的二值狀態的，所有存在是否對照關係的場景都可以使用。如在線(1) 離線(0)，打卡(1) 未打卡(0)，登錄(1) 未登錄(0)，群聊消息已閱(1) 未閱(0) 等等。
我們以用戶 離線/在線 為例子，看看如何使用 Bitmap 在海量的用戶數據之中判斷某個用戶是否是在線狀態。
假設我們使用一個 online_statu 來作為key，用來存儲 用戶登錄後的狀態集合，而用戶的ID則為offset，online的狀態就用1表示，offline的狀態就用0表示。
- 如果1024用戶登錄系統，那麼設置ID為1024的用戶為在線的程式碼如下：
SETBIT online_statu 1024 1
- 如果想看1024的用戶是否是在線狀態（這邊注意，key可能不存在，代表沒有這個用戶，這時候默認返回0），程式碼如下：
GETBIT online_statu 1024
- 如果1024的用戶退出系統，則為他執行下線，程式碼如下：
SETBIT online_statu 1024 0
- 空間上的有效利用，1億 人的狀態存儲只需要 100000000/8/1024/1024 = 11.92 M，簡單的數據結構也保證了性能上的優勢。
基於上面的討論，我們可以總結出一個預評估公式，根據實際的數據量獲取存儲空間：( offset / 8 / 1024 / 1024 ) M
3.2 固定周期的簽到情況統計（周/月/年）
固定周期可能是年/月/周，按照不同維度，可能有 365，31，7的bit位的統計周期。
假設這時候我們如果對於某個用戶（如1024）全年的簽到情況做統計，可以這麼設計:
-
設計key 為 {bus_type}{uid}{yyyy} ，及業務類型+用戶id+年份
比如 sign_1024_2022 -
簽到則執行對應程式碼
舉例，1024用戶在2022 年的第1天和最後一天如果有簽到，那就是：
# 22年第一天
SETBIT sign_1024_2022 0 1
# 22年最後一天
SETBIT sign_1024_2022 364 1
- 判斷某用戶（1024）在某一天（150）是否有簽到
GETBIT sign_1024_2022 150
- 統計某用戶（1024） 全面的簽到次數，使用 BITCOUNT 指令，統計給定的 bit 數組中，值 = 1 的所有bit位數量。
BITCOUNT sign_1024_2022
- 那如果你想限定範圍了怎麼辦，比如原來設計的是一年的統計。但是你想獲得某個月第一次打卡的數據，這時候就要使用BITPOS了。
通過 BITPOS key value [start] [end] 指令，返回數據表示 Bitmap 中第一個值為 給定value 的 offset 位置。
在默認情況下，命令會檢測整個點陣圖，但用戶也可以通過可選的start參數和end參數指定要檢測的範圍。
比如第2個月的第3天是2月的第一次簽到日，則下面的返回結果為30（第一個月31天）+ 3（二月第3天簽到） = 33 ：
$index = BITPOS sign_1024_2022 30
offset也是從0開始的，所以返回的值最好加個1，不會讓用戶看的暈頭轉向。
3.3 連續簽到用戶資訊
如果一個平台有千萬級別以上的大量用戶，而我們需要統計每個用戶連續簽到的資訊，那需要怎麼設計呢？
- 可以把每天的日期當成點陣圖（BitMap）的key，如 20221023
- 用戶的唯一鍵當成（UserId）當成offset，如編號 1024 的用戶
- 如果 1024 的用戶在 2022.10.23 有簽到，則點陣圖的value為1，否則為0。
如果這時候我們要判斷用戶是否整周都有簽到或者整個月都有簽到就可以使用 【與】運算
只有指定周期內的所有值都是1（簽到）的時候，結果才是1，否則是我們整周或者整個月都拿起來【與】運算，得到的結果是不是1就能確是否滿勤。
# 與運算： 0&0=0；0&1=0；1&0=0；1&1=1
# 下面為偽程式碼，類似：
(20221022 1024) & ( 20221023 1024) & ...
Redis 提供了 BITOP operation destkey key [key …]這個指令用於對一個或者多個 鍵 = key 的 Bitmap 進行 位元 操作。
operation 可以是 AND 、 OR 、 NOT 、 XOR 這四種操作中的任意一種：
- BITOP AND destkey key [key …] ，對一個或多個 key 求邏輯並，並將結果保存到 destkey 。
- BITOP OR destkey key [key …] ，對一個或多個 key 求邏輯或，並將結果保存到 destkey 。
- BITOP XOR destkey key [key …] ，對一個或多個 key 求邏輯異或，並將結果保存到 destkey 。
- BITOP NOT destkey key ，對給定 key 求邏輯非，並將結果保存到 destkey 。
除了 NOT 操作之外，其他操作都可以接受一個或多個 key 作為輸入。
# 統計一周的值（7個BitMap，10.17 ~ 10.23 號）並將結果存入到新的BitMap （sign-result） 中
redis> BITOP AND sign-result 20221017 20221018 20221019 20221020 20221021 20221022 20221023
(integer) 1
# 新的BitMap 中，獲取 1024的簽到結果，如果為1，則本周全部簽到
redis> GETBIT sign-result 1024
(integer) 1
可以理解下這張圖的運算過程：
這邊需要注意：當 BITOP 處理不同長度的字元串時，較短字元串所缺部分會被當作 0 對待。同樣的，空 key 也被看作是 0 的字元串序列看待。
同理，類似HeapDump性能社區的用戶簽到統計，也可以用點陣圖（BitMap）這種方式計算！
小結
1個byte等於8個bit，每個bit位只使用0或者1來表示，這樣能夠有效的降低存儲空間，而Redis是存儲在高速快取中的，所以實際上是大大減少了記憶體佔用。
很多場景都可以使用點陣圖計算，比如我們上面說到的 是否登錄、是否在線、是否簽到、用戶性別狀態、IP黑名單、是否VIP用戶統計 等等場景，但凡涉及到二值狀態識別、海量統計的數據都可以考慮使用。
