【原】【Redis07】Redis基礎(chǔ)：Bitmap 與 HyperLogLog 相關(guān)操作

硬核項目經(jīng)理 2023-03-27 發(fā)布于湖南

展開全文

Redis基礎(chǔ)學(xué)習(xí)：Bitmap 與 HyperLogLog 相關(guān)操作

繼續(xù)進(jìn)行 Redis 基礎(chǔ)部分的學(xué)習(xí)，今天我們學(xué)習(xí)的是兩種另外的數(shù)據(jù)類型。說是數(shù)據(jù)類型，但其實它們實際上使用的都是 String 類型做為底層基礎(chǔ)，只不過是在存儲的時候進(jìn)行了一些特殊的操作。換句話說，這兩種類型并不是真正意義上的“數(shù)據(jù)類型”，換成“數(shù)據(jù)操作”可能更合適一些。

Bitmap

先來看看 Bitmap ，這是個啥玩意？其實呀，這個就是位圖，Bit 就是比特的意思嘛。一提到比特是不是又得來二進(jìn)制了？這個真沒辦法，學(xué)計算機的，任何工具都逃不掉的就是二進(jìn)制相關(guān)的操作。不過在 Redis 中的操作還是比較簡單的，畢竟我們主要的操作還是在程序業(yè)務(wù)端進(jìn)行，Redis 只是一個數(shù)據(jù)庫而已。

Bitmap 在 Redis 中可以存儲大約 40 多億條數(shù)據(jù)，或者說是40多億個 0 和 1 位。估計不少小伙伴馬上就能想到它的應(yīng)用場景了，我們在最后再說。先來看看它的操作。

Bitmap 操作命令

設(shè)置和獲取指定位置的位信息，直接使用 SETBIT 和 GETBIT。

127.0.0.1:6379> setbit a 8 1
(integer) 0
127.0.0.1:6379> setbit a 4 1
(integer) 0
127.0.0.1:6379> get a
"\b\x80"
127.0.0.1:6379> getbit a 4
(integer) 1
127.0.0.1:6379> getbit a 5
(integer) 0

注意到上面的例子，我們直接使用 GET 命令也可以獲取到內(nèi)容，前面就說過了，它本身就是使用 String 類型存儲的。只不過使用位操作的話，我們要理解 8 位代表 1 個字節(jié)的問題。因此，設(shè)置一個 8 位的二進(jìn)制代碼才能表示出一個我們能看懂的字符。

127.0.0.1:6379> setbit b 1 1
(integer) 0
127.0.0.1:6379> setbit b 4 1
(integer) 0
127.0.0.1:6379> setbit b 5 1
(integer) 0
127.0.0.1:6379> setbit b 6 1
(integer) 0
127.0.0.1:6379> setbit b 7 1
(integer) 0
127.0.0.1:6379> get b
"O"
127.0.0.1:6379> setbit c 1 1
(integer) 0
127.0.0.1:6379> setbit c 2 1
(integer) 0
127.0.0.1:6379> setbit c 4 1
(integer) 0
127.0.0.1:6379> setbit c 6 1
(integer) 0
127.0.0.1:6379> setbit c 7 1
(integer) 0
127.0.0.1:6379> get c
"k"

看出上面的例子是什么意思了嗎？第一個 b ，設(shè)置的其實是 01001111 ，轉(zhuǎn)換成十進(jìn)制是 79 ，對應(yīng)的 ASC2 碼就是大寫英文 O 。另一個 c 也是一樣的意思，01101011 的十進(jìn)制是 107 ，表示的英文是 107 。如果要表示 Ok 這兩個字母的話，就需要兩個 8 位，也就是兩個字節(jié) 01001111 01101011 。

127.0.0.1:6379> setbit d 1 1
(integer) 0
127.0.0.1:6379> setbit d 4 1
(integer) 0
127.0.0.1:6379> setbit d 5 1
(integer) 0
127.0.0.1:6379> setbit d 6 1
(integer) 0
127.0.0.1:6379> setbit d 7 1
(integer) 0
127.0.0.1:6379> get d
"O"
127.0.0.1:6379> setbit d 9 1
(integer) 0
127.0.0.1:6379> setbit d 10 1
(integer) 0
127.0.0.1:6379> setbit d 12 1
(integer) 0
127.0.0.1:6379> setbit d 14 1
(integer) 0
127.0.0.1:6379> setbit d 15 1
(integer) 0
127.0.0.1:6379> get d
"Ok"

好玩吧？中文也是一樣的，只是三個字節(jié)的 UTF8 編碼，需要三個 8 位的數(shù)據(jù)才能表示一個中文字，大家可以試試哦。

127.0.0.1:6379> set s 中
OK
127.0.0.1:6379> get s
"\xe4\xb8\xad"
127.0.0.1:6379> getbit s 0
(integer) 1
127.0.0.1:6379> getbit s 1
(integer) 1
127.0.0.1:6379> getbit s 2
(integer) 1
127.0.0.1:6379> getbit s 3
(integer) 0

“中”這個字直接 GET 返回的是16進(jìn)制數(shù)據(jù)，將 e4b8ad 轉(zhuǎn)換成二進(jìn)制是 11100100 10111000 10101101 ，然后我們就可以使用 GETBIT 來驗證是不是和我們手動轉(zhuǎn)換出來的是一樣的結(jié)果。

大家有興趣的可以再多了解一下字符編碼相關(guān)的知識，比如在 Redis 中使用的 UTF8 ，為什么單個字節(jié)第一位只能是 0 ，必須是 0xxxxxxx 這樣的，中文也都是固定的 1110xxxx 10xxxxxx 10xxxxxx 這種格式，很有意思哦。

位操作

既然是位操作，那么與、或、異或、非操作肯定要有啦。

127.0.0.1:6379> bitop or dd b c
(integer) 1
127.0.0.1:6379> get dd
"o"
127.0.0.1:6379> bitop and dd b c
(integer) 1
127.0.0.1:6379> get dd
"K"
127.0.0.1:6379> bitop xor dd b c
(integer) 1
127.0.0.1:6379> get dd
"$"
127.0.0.1:6379> bitop not dd b
(integer) 1
127.0.0.1:6379> get dd
"\xb0"

查詢第一個bit位位置

通過 BITPOS 命令，可以查詢到指定的 key 中，第一個出現(xiàn)的位數(shù)據(jù)的位置。

127.0.0.1:6379> BITPOS a 1
(integer) 4
127.0.0.1:6379> BITPOS a 0
(integer) 0

第一條命令是查詢第一個 1 出現(xiàn)的位置，第二條命令是查詢第一個 0 出現(xiàn)的位置。它還有第二個參數(shù)，這個參數(shù)是一個偏移量，不過需要注意的是，它指的是字節(jié)的偏移量，不是位的偏移量。

127.0.0.1:6379> BITPOS d 1 0
(integer) 1
127.0.0.1:6379> BITPOS d 1 1
(integer) 9
127.0.0.1:6379> BITPOS d 1 2
(integer) -1

統(tǒng)計數(shù)量

BITCOUNT 可以統(tǒng)計指定 key 中 1 出現(xiàn)的次數(shù)。

127.0.0.1:6379> BITCOUNT d
(integer) 10
127.0.0.1:6379> BITCOUNT d 1 0 2
(error) ERR syntax error
127.0.0.1:6379> BITCOUNT d 1 0 1
(error) ERR syntax error
127.0.0.1:6379> BITCOUNT d 1 2
(integer) 5
127.0.0.1:6379> BITCOUNT d 0 2
(integer) 10
127.0.0.1:6379> BITCOUNT d 2 3
(integer) 0

它還有兩個參數(shù)，同樣也是字節(jié)偏移量和長度。

位域操作

位域這個東西我就不太懂了，只是給個例子，這一塊深入學(xué)過 C 的同學(xué)應(yīng)該會比較了解。

127.0.0.1:6379> setbit e 1 1
(integer) 0
127.0.0.1:6379> get e
"@"
127.0.0.1:6379> BITFIELD e incrby i5 100 1 get u4 0
1) (integer) 1
2) (integer) 4
127.0.0.1:6379> get e
"@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80"

Bitmap 經(jīng)典例子

好了，Bitmap 的基本操作就是上面那些，介紹的比較簡單，不過也確實都不復(fù)雜。但前提是要對二進(jìn)制和進(jìn)制之間的轉(zhuǎn)換以及字符編碼要有一定的了解。如果我們只是為了去顯示字符串的位，那就有點大材小用了，其實 Bitmap 有個非常強悍的能力，也就是運用 BITCOUNT 去進(jìn)行數(shù)據(jù)統(tǒng)計。

包括官網(wǎng)上給出的也是類似這樣的例子，統(tǒng)計登錄用戶數(shù)。

最開始我們已經(jīng)知道，一個 key 可以保存40多億個位，那么我們可以把用戶id當(dāng)作位索引，然后某個用戶今天登錄了，就給它的位設(shè)置為 1 ，然后就可以 BITCOUNT 快速統(tǒng)計出今天有多少用戶登錄了系統(tǒng)，速度相當(dāng)快哦。

127.0.0.1:6379> setbit user_login_20220509 100010 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 25525 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 8782 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 9846526547 1
(error) ERR bit offset is not an integer or out of range
127.0.0.1:6379> setbit user_login_20220509 98465265 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 399999999 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 3999999999 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 4294967295 1
(integer) 0
127.0.0.1:6379> setbit user_login_20220509 4294967296 1
(error) ERR bit offset is not an integer or out of range
127.0.0.1:6379> BITCOUNT user_login_20220509
(integer) 7

HyperLogLog

既然說到統(tǒng)計了，那么 HyperLogLog 這個操作類型就不得不提了。它是一種概率數(shù)據(jù)結(jié)構(gòu)，用于計算唯一事物的集合數(shù)量。同時，它是以內(nèi)存換精度的，也就是說，它能極大的節(jié)約內(nèi)存，但是會有精度丟失的問題。最壞情況下，也就是內(nèi)存占用最大的情況下，它也只需要 12K 的內(nèi)存容量就可以存儲非常巨大的數(shù)據(jù)量，精度的丟失會在 1% 以內(nèi)。它也可以實現(xiàn)上面 Bitmap 中統(tǒng)計的例子，我們先來看看相關(guān)的操作命令。

127.0.0.1:6379> pfadd hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7
127.0.0.1:6379> pfadd hll a b c d e f g h i j k
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 11

PFADD 添加數(shù)據(jù)，PFCOUNT 獲取數(shù)量。基本的操作命令就這兩個，是不是無敵了。除了這兩個外，還有一個合并的命令，類似于集合的并集操作。

127.0.0.1:6379> PFADD pfa a b c d e f
(integer) 1
127.0.0.1:6379> PFADD pfb d c a e g i
(integer) 1
127.0.0.1:6379> pfadd pfc b d f i l m n o
(integer) 1
127.0.0.1:6379> PFMERGE pfmerge pfa pfb pfc
OK
127.0.0.1:6379> pfcount pfmerge
(integer) 12

另外，它也是以 String 為基本存儲類型的，所以用 GET 也能看到內(nèi)容。

127.0.0.1:6379> get hll
"HYLL\x01\x00\x00\x00\x0b\x00\x00\x00\x00\x00\x00\x00Fm\x80I\xe8\x80L\"\x80D<\x848\x80B=\x80K\x83\x80B\xed\x84A\xfc\x8cG\x8e\x80Bm\x80BZ"

好了，接下來說下 HyperLogLog 和其它方式統(tǒng)計的對比，以下是網(wǎng)上找到的相關(guān)文章獲取到的資料。

如果我們使用 SET 來進(jìn)行基數(shù)統(tǒng)計，那么假設(shè)每一個元素的 32Bit(2^24 ≈ 1600萬; 2^32 ≈ 42億) ，假設(shè)存儲1億個不重復(fù)的元素那么我們需要 100 000 000 * 32 /8/1024/1024 ≈ 381MB。

如果我們用 Bitmap 來進(jìn)行基數(shù)統(tǒng)計，每個元素對應(yīng)一位(bit)，假設(shè)我們存儲1億個不重復(fù)的元素那么我們需要 100 000 000 /8/1024/1024 ≈ 12MB。

然而我們使用 HyperLogLog ，一個鍵占用的內(nèi)容空間是12KB，并且這個鍵可以處理海量數(shù)據(jù)。

它們?nèi)齻€都可以應(yīng)用在統(tǒng)計不重復(fù)元素的場景：

HyperLogLog：海量數(shù)據(jù)，可以忍受 0.81% 誤差的場景，其實大數(shù)據(jù)處理的時候都會有誤差。
Bitmap：數(shù)據(jù)量不大，不能忍受誤差，元素連續(xù)的（自增的用戶主鍵id）。
SET：數(shù)據(jù)量不大，不能忍受誤差，元素沒有規(guī)律，并且需要返回實際的單個元素。

總結(jié)

今天的內(nèi)容挺好玩吧，Bitmap 和 HyperLogLog 最常用的其實都是一個不重復(fù)數(shù)據(jù)統(tǒng)計的場景，但是又各有優(yōu)勢。在日常的工作中如果有類似的應(yīng)用場景，完全就可以使用這兩種數(shù)據(jù)操作來試試了。

擴展知識：布隆過濾器

布隆過濾器（Bloom Filter），聽說過沒？面試有沒有被坑過？跟你說，布隆過濾器的基礎(chǔ)知識就是 Bitmap ，HyperLogLog 也是它的類似實現(xiàn)之一。啥叫布隆過濾器？就是能夠快速地查找某一個元素是否存在于指定的集合中，最典型的做法就是使用二進(jìn)制位來進(jìn)行操作，這不就是 Bitmap 嘛。

當(dāng)然，完整的布隆過濾器的實現(xiàn)還是要更復(fù)雜一些，它一般會有三個 Hash 函數(shù)，生成三個不同位置，只有當(dāng)三個位置全部命中時，才會認(rèn)為指定的數(shù)據(jù)已經(jīng)存在。從這一點上來說，其實就是在有限的空間內(nèi)可以存放更多的數(shù)據(jù)。但它也會出現(xiàn)不同的數(shù)據(jù)三個 Hash 函數(shù)計算結(jié)果一致的概率，但我們可以增加更多的 Hash 函數(shù)，不過相應(yīng)地性能也會降低。同樣，它也會有精度問題，反正大概原理就是這樣。布隆過濾器有一個非常經(jīng)典的名言，那就是“我說你不在，那你一定不在；我說你存在，你有可能存在（也可能不存在）！”。在 packgist 上也能搜到純 PHP 實現(xiàn)布隆過濾器的 Composer 包，大家可以自己下載源碼學(xué)習(xí)一下哦！