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