1. Bitmap 是什么

Bitmap(也稱為位數(shù)組或者位向量等)是一種實(shí)現(xiàn)對(duì)位的操作的'數(shù)據(jù)結(jié)構(gòu)'，在數(shù)據(jù)結(jié)構(gòu)加引號(hào)主要因?yàn)椋?/p>

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

2. 占用存儲(chǔ)空間

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

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 時(shí)，假如偏移量 offset 非常大，由于需要分配所需要的內(nèi)存，整個(gè)初始化過程執(zhí)行會(huì)比較慢，可能會(huì)造成 Redis 的阻塞。在 2010 款 MacBook Pro 上，設(shè)置第 2^32-1 位，由于需要分配 512MB 內(nèi)存，所以大約需要 300 毫秒；設(shè)置第 2^30-1 位（128 MB）大約需要 80 毫秒；設(shè)置第 2^28 -1 位（32MB）需要約 30 毫秒；設(shè)置第 2^26 -1（8MB）需要約 8 毫秒。一旦完成第一次分配，隨后對(duì)同一 key 再設(shè)置將不會(huì)產(chǎn)生分配開銷。

3. 命令

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

3.1 SETBIT

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

語(yǔ)法格式：

SETBIT key offset value

SETBIT 用來設(shè)置 key 對(duì)應(yīng)第 offset 位的值（offset 從 0 開始算），可以設(shè)置為 0 或者 1。當(dāng)指定的 KEY 不存在時(shí)，會(huì)自動(dòng)生成一個(gè)新的字符串值。字符串會(huì)進(jìn)行擴(kuò)展以確?？梢詫?value 保存在指定的偏移量 offset 上。當(dāng)字符串值進(jìn)行擴(kuò)展時(shí)，空白位置用 0 來填充。需要注意的是 offset 需要大于或等于 0，小于 2 的 32 次方。

假設(shè)現(xiàn)在有 10 個(gè)用戶，用戶id為 0、1、5、9 的 4 個(gè)用戶在 20220514 進(jìn)行了登錄，那么當(dāng)前 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

假設(shè)用戶 uid 為 15 的用戶也登錄了 App，那么 Bitmap 的結(jié)構(gòu)變成了如下圖所示，第 10 位到第 14 位都用 0 填充，第 15 位被置為 1：

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

3.2 GETBIT

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

語(yǔ)法格式：

GETBIT key offset

獲取 key 對(duì)應(yīng)第 offset 位的值（offset 從 0 開始算）。當(dāng) offset 超過字符串長(zhǎng)度時(shí)，字符串假定為一個(gè) 0 位的連續(xù)空間。當(dāng)指定的 key 不存在時(shí)，假定為一個(gè)空字符串，offset 肯定是超出字符串長(zhǎng)度范圍，因此該值也被假定為 0 位的連續(xù)空間，都會(huì)返回 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 這天登錄過，因?yàn)?offset 20 根本就不存在，所以返回結(jié)果也是 0：

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

3.3 BITCOUNT

最早可用版本：2.6.0。時(shí)間復(fù)雜度：O(N)。

語(yǔ)法格式：

BITCOUNT key [ start end [ BYTE | BIT]]

用來計(jì)算指定 key 對(duì)應(yīng)字符串中，被設(shè)置為 1 的 bit 位的數(shù)量。一般情況下，字符串中所有 bit 位都會(huì)參與計(jì)數(shù)，我們可以通過 start 或 end 參數(shù)來指定一定范圍內(nèi)被設(shè)置為 1 的 bit 位的數(shù)量。start 和 end 參數(shù)的設(shè)置和 GETRANGE 命令類似，都可以使用負(fù)數(shù)：比如 -1 表示最后一個(gè)位，而 -2 表示倒數(shù)第二個(gè)位等。

從 Redis 7.0.0 開始支持 BYTE 或者 BIT 選項(xiàng)

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

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

3.4 BITOP

最早可用版本：2.6.0。時(shí)間復(fù)雜度：O(N)。

語(yǔ)法格式：

BITOP operation destkey key [key ...]

BITOP 是一個(gè)復(fù)合操作，支持在多個(gè) key 之間執(zhí)行按位運(yùn)算并將結(jié)果存儲(chǔ)在 destkey 指定的 key 中。BITOP 命令支持四種按位運(yùn)算：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 很特殊，因?yàn)樗恍枰粋€(gè)輸入 key，因?yàn)樗鼒?zhí)行位反轉(zhuǎn)，因此它僅作為一元運(yùn)算符才有意義。

假設(shè) 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。時(shí)間復(fù)雜度：O(N)。

語(yǔ)法格式：

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

用來計(jì)算指定 key 對(duì)應(yīng)字符串中，第一位為 1 或者 0 的 offset 位置。除此之外，BITPOS 也有兩個(gè)選項(xiàng) start 和 end，跟 BITCOUNT 一樣。

BYTE、BIT 這兩個(gè)選項(xiàng)從 7.0.0 版本開始才能使用。

下面計(jì)算 20220514 登錄 App 的最小用戶id：

127.0.0.1:6379> bitpos login:20220513 1
(integer) 1

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

最新評(píng)論