Redis 如何使用 Bitmap

  1. Bitmap 是什麼

Bitmap(也稱爲位數組或者位向量等) 是一種實現對位的操作的'數據結構'，在數據結構加引號主要因爲：

  1. 佔用存儲空間

如上我們知道 Bitmap 本身不是一種數據結構，底層實際上使用字符串來存儲。由於 Redis 中字符串的最大長度是 512 MB 字節，所以 BitMap 的偏移量 offset 值也是有上限的，其最大值是：8 * 1024 * 1024 * 512 = 2^32。由於 C 語言中字符串的末尾都要存儲一位分隔符，所以實際上 BitMap 的偏移量 offset 值上限是：2^32-1。Bitmap 實際佔用存儲空間取決於 BitMap 偏移量 offset 的最大值，佔用字節數可以用 (max_offset / 8) + 1 公式來計算或者直接藉助底層字符串函數 strlen 來計算：

127.0.0.1:6379> setbit login:20220515 0 1
(integer) 0
# (0 / 8) + 1 = 1
127.0.0.1:6379> strlen login:20220515
(integer) 1
127.0.0.1:6379> setbit login:20220515 8 1
(integer) 0
# (8 / 8) + 1 = 2
127.0.0.1:6379> strlen login:20220515
(integer) 2

需要注意的是，在第一次初始化 Bitmap 時，假如偏移量 offset 非常大，由於需要分配所需要的內存，整個初始化過程執行會比較慢，可能會造成 Redis 的阻塞。在 2010 款 MacBook Pro 上，設置第 2^32-1 位，由於需要分配 512MB 內存，所以大約需要 300 毫秒；設置第 2^30-1 位（128 MB）大約需要 80 毫秒；設置第 2^28 -1 位（32MB）需要約 30 毫秒；設置第 2^26 -1（8MB）需要約 8 毫秒。一旦完成第一次分配，隨後對同一 key 再設置將不會產生分配開銷。

  1. 命令

下面示例中我們將登錄 App 的用戶存放在 Bitmap 中，登錄的用戶記做 1，沒有登錄的用戶記做 0，用偏移量作爲用戶的 id。

3.1 SETBIT

最早可用版本：2.2.0。時間複雜度：O(1)。

語法格式：

SETBIT key offset value

SETBIT 用來設置 key 對應第 offset 位的值（offset 從 0 開始算），可以設置爲 0 或者 1。當指定的 KEY 不存在時，會自動生成一個新的字符串值。字符串會進行擴展以確保可以將 value 保存在指定的偏移量 offset 上。當字符串值進行擴展時，空白位置用 0 來填充。需要注意的是 offset 需要大於或等於 0，小於 2 的 32 次方。

假設現在有 10 個用戶，用戶 id 爲 0、1、5、9 的 4 個用戶在 20220514 進行了登錄，那麼當前 Bitmap 初始化結果如下圖所示：

具體操作過程如下，login:20220514 代表 20220514 這天所有登錄用戶的 Bitmap：

127.0.0.1:6379> setbit login:20220514 0 1
(integer) 0
127.0.0.1:6379> setbit login:20220514 1 1
(integer) 0
127.0.0.1:6379> setbit login:20220514 5 1
(integer) 0
127.0.0.1:6379> setbit login:20220514 9 1
(integer) 0

假設用戶 uid 爲 15 的用戶也登錄了 App，那麼 Bitmap 的結構變成了如下圖所示，第 10 位到第 14 位都用 0 填充，第 15 位被置爲 1：

很多應用的用戶 id 以一個指定數字（例如 150000000000）開頭，直接將用戶 id 和 Bitmap 的偏移量對應勢必會造成一定的浪費，通常的做法是每次做 setbit 操作時將用戶 id 減去這個指定數字。在第一次初始化 Bitmap 時，假如偏移量非常大，那麼整個初始化過程執行會比較慢，可能會造成 Redis 的阻塞。

3.2 GETBIT

最早可用版本：2.2.0。時間複雜度：O(1)。

語法格式：

GETBIT key offset

獲取 key 對應第 offset 位的值（offset 從 0 開始算）。當 offset 超過字符串長度時，字符串假定爲一個 0 位的連續空間。當指定的 key 不存在時，假定爲一個空字符串，offset 肯定是超出字符串長度範圍，因此該值也被假定爲 0 位的連續空間，都會返回 0。

下面獲取用戶 id 爲 4 的用戶是否在 20220514 這天登錄過，返回 0 說明沒有訪問過：

127.0.0.1:6379> getbit login:20220514 4
(integer) 0

下面獲取用戶 id 爲 5 的用戶是否在 20220514 這天登錄過，返回 1 說明訪問過：

127.0.0.1:6379> getbit login:20220514 5
(integer) 1

下面獲取用戶 id 爲 20 的用戶是否在 20220514 這天登錄過，因爲 offset 20 根本就不存在，所以返回結果也是 0：

127.0.0.1:6379> getbit login:20220514 20
(integer) 1

3.3 BITCOUNT

最早可用版本：2.6.0。時間複雜度：O(N)。

語法格式：

BITCOUNT key [ start end [ BYTE | BIT]]

用來計算指定 key 對應字符串中，被設置爲 1 的 bit 位的數量。一般情況下，字符串中所有 bit 位都會參與計數，我們可以通過 start 或 end 參數來指定一定範圍內被設置爲 1 的 bit 位的數量。start 和 end 參數的設置和 GETRANGE 命令類似，都可以使用負數：比如 -1 表示最後一個位，而 -2 表示倒數第二個位等。

從 Redis 7.0.0 開始支持 BYTE 或者 BIT 選項

下面計算 20220514 這天所有登錄用戶數量：

127.0.0.1:6379> bitcount login:20220514
(integer) 5

3.4 BITOP

最早可用版本：2.6.0。時間複雜度：O(N)。

語法格式：

BITOP operation destkey key [key ...]

BITOP 是一個複合操作，支持在多個 key 之間執行按位運算並將結果存儲在 destkey 指定的 key 中。BITOP 命令支持四種按位運算：AND(交集)、OR(並集)、XOR(異或) 和 NOT(非)：

BITOP AND destkey srckey1 srckey2 srckey3 ... srckeyN
BITOP OR destkey srckey1 srckey2 srckey3 ... srckeyN
BITOP XOR destkey srckey1 srckey2 srckey3 ... srckeyN
BITOP NOT destkey srckey

如上所見，NOT 很特殊，因爲它只需要一個輸入 key，因爲它執行位反轉，因此它僅作爲一元運算符纔有意義。

假設 20220513 登錄 App 的用戶 id 爲 1、3、5、7，如下圖所示：

如果想算出 20220513 和 20220514 兩天都登錄過的用戶數量，如下圖所示：

可以使用 AND 求交集，具體命令如下：

127.0.0.1:6379> bitop and login:20220513:and:20220514 login:20220513 login:20220514
(integer) 2
127.0.0.1:6379> bitcount login:20220513:and:20220514
(integer) 2
127.0.0.1:6379> getbit login:20220513:and:20220514 1
(integer) 1
127.0.0.1:6379> getbit login:20220513:and:20220514 5
(integer) 1

如果想算出 20220513 和 20220514 任意一天登錄過 App 的用戶數量：

可以使用 OR 求並集，具體命令如下：

127.0.0.1:6379> bitop or login:20220513:or:20220514 login:20220513 login:20220514
(integer) 2
127.0.0.1:6379> bitcount login:20220513:or:20220514
(integer) 7
127.0.0.1:6379> getbit login:20220513:or:20220514 0
(integer) 1
127.0.0.1:6379> getbit login:20220513:or:20220514 1
(integer) 1

3.5 BITPOS

最早可用版本：2.8.7。時間複雜度：O(N)。

語法格式：

BITPOS key bit [ start [ end [ BYTE | BIT]]]

用來計算指定 key 對應字符串中，第一位爲 1 或者 0 的 offset 位置。除此之外，BITPOS 也有兩個選項 start 和 end，跟 BITCOUNT 一樣。

BYTE、BIT 這兩個選項從 7.0.0 版本開始才能使用。

下面計算 20220514 登錄 App 的最小用戶 id：

127.0.0.1:6379> bitpos login:20220513 1
(integer) 1
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vCtxcNQiB5vctanR1R7sIA

猜你喜歡