Redis 實戰篇：巧用 Bitmap 實現億級海量數據統計
在移動應用的業務場景中，我們需要保存這樣的信息：一個 key 關聯了一個數據集合。
常見的場景如下：
- 給一個 userId ，判斷用戶登陸狀態;
- 顯示用戶某個月的簽到次數和首次簽到時間;
- 兩億用戶最近 7 天的簽到情況，統計 7 天內連續簽到的用戶總數;
通常情況下，我們面臨的用戶數量以及訪問量都是巨大的，比如百萬、千萬級別的用戶數量，或者千萬級別、甚至億級別的訪問信息。
所以，我們必須要選擇能夠非常高效地統計大量數據(例如億級)的集合類型。
如何選擇合適的數據集合，我們首先要了解常用的統計模式，并運用合理的數據類型來解決實際問題。
四種統計類型：
- 二值狀態統計;
- 聚合統計;
- 排序統計;
- 基數統計。
本文將由二值狀態統計類型作為實戰篇系列的開篇，文中將用到 String、Set、Zset、List、hash 以外的拓展數據類型 Bitmap 來實現。
文章涉及到的指令可以通過在線 Redis 客戶端運行調試，地址：https://try.redis.io/，超方便的說。
寄語
多分享多付出，前期多給別人創造價值并且不計回報，從長遠來看，這些付出都會成倍的回報你。
特別是剛開始跟別人合作的時候，不要去計較短期的回報，沒有太大意義，更多的是鍛煉自己的視野、視角以及解決問題的能力。
二值狀態統計
碼哥，什么是二值狀態統計呀?
也就是集合中的元素的值只有 0 和 1 兩種，在簽到打卡和用戶是否登陸的場景中，只需記錄簽到(1)或 未簽到(0)，已登錄(1)或未登陸(0)。
假如我們在判斷用戶是否登陸的場景中使用 Redis 的 String 類型實現(key -> userId，value -> 0 表示下線，1 - 登陸)，假如存儲 100 萬個用戶的登陸狀態，如果以字符串的形式存儲，就需要存儲 100 萬個字符串了，內存開銷太大。
碼哥，為什么 String 類型內存開銷大?
String 類型除了記錄實際數據以外，還需要額外的內存記錄數據長度、空間使用等信息。
當保存的數據包含字符串，String 類型就使用簡單動態字符串(SDS)結構體來保存，如下圖所示：
SDS
len：占 4 個字節，表示 buf 的已用長度。
alloc：占 4 個字節，表示 buf 實際分配的長度，通常 > len。
buf：字節數組，保存實際的數據，Redis 自動在數組最后加上一個 “\0”，額外占用一個字節的開銷。
所以，在 SDS 中除了 buf 保存實際的數據， len 與 alloc 就是額外的開銷。
另外，還有一個 RedisObject 結構的開銷，因為 Redis 的數據類型有很多，而且，不同數據類型都有些相同的元數據要記錄(比如最后一次訪問的時間、被引用的次數等)。
所以，Redis 會用一個 RedisObject 結構體來統一記錄這些元數據，同時指向實際數據。
對于二值狀態場景，我們就可以利用 Bitmap 來實現。比如登陸狀態我們用一個 bit 位表示，一億個用戶也只占用 一億 個 bit 位內存 ≈ (100000000 / 8/ 1024/1024)12 MB。
- 大概的空間占用計算公式是：($offset/8/1024/1024) MB
什么是 Bitmap 呢?
Bitmap 的底層數據結構用的是 String 類型的 SDS 數據結構來保存位數組，Redis 把每個字節數組的 8 個 bit 位利用起來，每個 bit 位 表示一個元素的二值狀態(不是 0 就是 1)。
可以將 Bitmap 看成是一個 bit 為單位的數組，數組的每個單元只能存儲 0 或者 1，數組的下標在 Bitmap 中叫做 offset 偏移量。
為了直觀展示，我們可以理解成 buf 數組的每個字節用一行表示，每一行有 8 個 bit 位，8 個格子分別表示這個字節中的 8 個 bit 位，如下圖所示：
Bitmap
8 個 bit 組成一個 Byte，所以 Bitmap 會極大地節省存儲空間。 這就是 Bitmap 的優勢。
判斷用戶登陸態
怎么用 Bitmap 來判斷海量用戶中某個用戶是否在線呢?
Bitmap 提供了 GETBIT、SETBIT 操作，通過一個偏移值 offset 對 bit 數組的 offset 位置的 bit 位進行讀寫操作，需要注意的是 offset 從 0 開始。
只需要一個 key = login_status 表示存儲用戶登陸狀態集合數據， 將用戶 ID 作為 offset，在線就設置為 1，下線設置 0。通過 GETBIT判斷對應的用戶是否在線。50000 萬 用戶只需要 6 MB 的空間。
SETBIT 命令
- SETBIT <key> <offset> <value>
設置或者清空 key 的 value 在 offset 處的 bit 值(只能是 0 或者 1)。
GETBIT 命令
- GETBIT <key> <offset>
獲取 key 的 value 在 offset 處的 bit 位的值，當 key 不存在時，返回 0。
假如我們要判斷 ID = 10086 的用戶的登陸情況：
第一步，執行以下指令，表示用戶已登錄。
- SETBIT login_status 10086 1
第二步，檢查該用戶是否登陸，返回值 1 表示已登錄。
- GETBIT login_status 10086
第三步，登出，將 offset 對應的 value 設置成 0。
- SETBIT login_status 10086 0
用戶每個月的簽到情況在簽到統計中，每個用戶每天的簽到用 1 個 bit 位表示，一年的簽到只需要 365 個 bit 位。一個月最多只有 31 天，只需要 31 個 bit 位即可。
比如統計編號 89757 的用戶在 2021 年 5 月份的打卡情況要如何進行?
key 可以設計成 uid:sign:{userId}:{yyyyMM}，月份的每一天的值 - 1 可以作為 offset(因為 offset 從 0 開始，所以 offset = 日期 - 1)。
第一步，執行下面指令表示記錄用戶在 2021 年 5 月 16 號打卡。
- SETBIT uid:sign:89757:202105 15 1
第二步，判斷編號 89757 用戶在 2021 年 5 月 16 號是否打卡。
- GETBIT uid:sign:89757:202105 15
第三步，統計該用戶在 5 月份的打卡次數，使用 BITCOUNT 指令。該指令用于統計給定的 bit 數組中，值 = 1 的 bit 位的數量。
- BITCOUNT uid:sign:89757:202105
這樣我們就可以實現用戶每個月的打卡情況了，是不是很贊。
如何統計這個月首次打卡時間呢?
Redis 提供了 BITPOS key bitValue [start] [end]指令，返回數據表示 Bitmap 中第一個值為 bitValue 的 offset 位置。
在默認情況下， 命令將檢測整個位圖， 用戶可以通過可選的 start 參數和 end參數指定要檢測的范圍。
所以我們可以通過執行以下指令來獲取 userID = 89757 在 2021 年 5 月份首次打卡日期：
- BITPOS uid:sign:89757:202105 1
需要注意的是，我們需要將返回的 value + 1 ，因為 offset 從 0 開始。
連續簽到用戶總數
在記錄了一個億的用戶連續 7 天的打卡數據，如何統計出這連續 7 天連續打卡用戶總數呢?
我們把每天的日期作為 Bitmap 的 key，userId 作為 offset，若是打卡則將 offset 位置的 bit 設置成 1。
key 對應的集合的每個 bit 位的數據則是一個用戶在該日期的打卡記錄。
一共有 7 個這樣的 Bitmap，如果我們能對這 7 個 Bitmap 的對應的 bit 位做 『與』運算。
同樣的 UserID offset 都是一樣的，當一個 userID 在 7 個 Bitmap 對應對應的 offset 位置的 bit = 1 就說明該用戶 7 天連續打卡。
結果保存到一個新 Bitmap 中，我們再通過 BITCOUNT 統計 bit = 1 的個數便得到了連續打卡 7 天的用戶總數了。
Redis 提供了 BITOP operation destkey key [key ...]這個指令用于對一個或者多個 鍵 = key 的 Bitmap 進行位元操作。
opration 可以是 and、OR、NOT、XOR。當 BITOP 處理不同長度的字符串時，較短的那個字符串所缺少的部分會被看作 0 。空的 key 也被看作是包含 0的字符串序列。
便于理解，如下圖所示：
BITOP
3 個 Bitmap，對應的 bit 位做「與」操作，結果保存到新的 Bitmap 中。
操作指令表示將 三個 bitmap 進行 AND 操作，并將結果保存到 destmap 中。接著對 destmap 執行 BITCOUNT 統計。
- // 與操作
- BITOP AND destmap bitmap:01 bitmap:02 bitmap:03
- // 統計 bit 位 = 1 的個數
- BITCOUNT destmap
簡單計算下 一個一億個位的 Bitmap占用的內存開銷，大約占 12 MB 的內存(10^8/8/1024/1024)，7 天的 Bitmap 的內存開銷約為 84 MB。同時我們最好給 Bitmap 設置過期時間，讓 Redis 刪除過期的打卡數據，節省內存。
小結
思路才是最重要，當我們遇到的統計場景只需要統計數據的二值狀態，比如用戶是否存在、 ip 是否是黑名單、以及簽到打卡統計等場景就可以考慮使用 Bitmap。
只需要一個 bit 位就能表示 0 和 1。在統計海量數據的時候將大大減少內存占用。
