1. Bitmap 是什么

Bitmap(也稱為位數(shù)組或者位向量等)是一種實現(xiàn)對位的操作的'數(shù)據(jù)結(jié)構(gòu)'，在數(shù)據(jù)結(jié)構(gòu)加引號主要因為：

• Bitmap 本身不是一種數(shù)據(jù)結(jié)構(gòu)，底層實際上是字符串，可以借助字符串進行位操作。
• Bitmap 單獨提供了一套命令，所以與使用字符串的方法不太相同?？梢园?Bitmaps 想象成一個以位為單位的數(shù)組，數(shù)組的每個單元只能存儲 0 和 1，數(shù)組的下標在 Bitmap 中叫做偏移量 offset。

2. 占用存儲空間

如上我們知道 Bitmap 本身不是一種數(shù)據(jù)結(jié)構(gòu)，底層實際上使用字符串來存儲。由于 Redis 中字符串的最大長度是 512 MB字節(jié)，所以 BitMap 的偏移量 offset 值也是有上限的，其最大值是：8 * 1024 * 1024 * 512 = 2^32。由于 C 語言中字符串的末尾都要存儲一位分隔符，所以實際上 BitMap 的偏移量 offset 值上限是：2^32-1。Bitmap 實際占用存儲空間取決于 BitMap 偏移量 offset 的最大值，占用字節(jié)數(shù)可以用 (max_offset / 8) + 1 公式來計算或者直接借助底層字符串函數(shù) 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 非常大，由于需要分配所需要的內(nèi)存，整個初始化過程執(zhí)行會比較慢，可能會造成 Redis 的阻塞。在 2010 款 MacBook Pro 上，設置第 2^32-1 位，由于需要分配 512MB 內(nèi)存，所以大約需要 300 毫秒；設置第 2^30-1 位（128 MB）大約需要 80 毫秒；設置第 2^28 -1 位（32MB）需要約 30 毫秒；設置第 2^26 -1（8MB）需要約 8 毫秒。一旦完成第一次分配，隨后對同一 key 再設置將不會產(chǎn)生分配開銷。

3. 命令

下面示例中我們將登錄 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 次方。

假設現(xiàn)在有 10 個用戶，用戶id為 0、1、5、9 的 4 個用戶在 20220514 進行了登錄，那么當前 Bitmap 初始化結(jié)果如下圖所示：

具體操作過程如下，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 的結(jié)構(gòu)變成了如下圖所示，第 10 位到第 14 位都用 0 填充，第 15 位被置為 1：

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

3.2 GETBIT

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

語法格式：

GETBIT key offset

獲取 key 對應第 offset 位的值（offset 從 0 開始算）。當 offset 超過字符串長度時，字符串假定為一個 0 位的連續(xù)空間。當指定的 key 不存在時，假定為一個空字符串，offset 肯定是超出字符串長度范圍，因此該值也被假定為 0 位的連續(xù)空間，都會返回 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 根本就不存在，所以返回結(jié)果也是 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 位的數(shù)量。一般情況下，字符串中所有 bit 位都會參與計數(shù)，我們可以通過 start 或 end 參數(shù)來指定一定范圍內(nèi)被設置為 1 的 bit 位的數(shù)量。start 和 end 參數(shù)的設置和 GETRANGE 命令類似，都可以使用負數(shù)：比如 -1 表示最后一個位，而 -2 表示倒數(shù)第二個位等。

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

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

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 之間執(zhí)行按位運算并將結(jié)果存儲在 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，因為它執(zhí)行位反轉(zhuǎn)，因此它僅作為一元運算符才有意義。

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

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

可以使用 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 的用戶數(shù)量：

可以使用 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

到此這篇關于Redis使用Bitmap的方法實現(xiàn)的文章就介紹到這了,更多相關Redis使用Bitmap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論