Redis學習之深入瞭解Bitmaps
Redis版本：6.2.6
一、簡單介紹 Bitmaps
點陣圖不是實際的資料型別，而是在 String 型別上定義的一組面向位的操作。由於字串是二進位制安全的 blob，並且它們的最大長度為 512 MB，因此它們適合設定多達 2^32 個不同的位。【相關推薦：Redis視訊教學】
上述是Redis官網對 Bitmaps 的介紹，簡單理解 Bitmaps 就是 Redis 提供的一系列直接操作 String 的位的指令，比如我們現在有一個字串 ：「a」
127.0.0.1:6379> set k1 a OK 127.0.0.1:6379> get k1 "a"
a 的二進位制是：0110 0001，我們可以利用 [ GETBIT key offset ]指令，獲取這個字串對應 位 的數值：
127.0.0.1:6379> getbit k1 0 (integer) 0 127.0.0.1:6379> getbit k1 1 (integer) 1 127.0.0.1:6379> getbit k1 2 (integer) 1 127.0.0.1:6379> getbit k1 3 (integer) 0 127.0.0.1:6379> getbit k1 4 (integer) 0 127.0.0.1:6379> getbit k1 5 (integer) 0 127.0.0.1:6379> getbit k1 6 (integer) 0 127.0.0.1:6379> getbit k1 7 (integer) 1
這個指令中的 offset 表示偏移量，如上面展示可以看到，偏移 1 位，2 位，7 位的數值是 1，其他位是 0，對應的二進位制就是：0110 0001，這是字元 a 的 ASCII 值。
接下來我們可以利用 [SETBIT key offset value ] 指令，去改變某一位的值，比如：
127.0.0.1:6379> setbit k1 6 1 //偏移6位，置為1 (integer) 0 127.0.0.1:6379> get k1 "c"
如上，我們設定偏移量為 6 的位置數值為 1，這樣這個二進位制物件就變成了: 0110 0011，對應的就是字元 」c「 ，我們通過 直接操作字串的位 改變了字串的值。
Bitmaps 在redis中是按位元操作字串的工具，根據這個工具，我們可以將字串當作一組二進位制陣列來使用，我們舉一個簡單的例子：
如何記錄十億使用者的線上狀態？
這裡我們 用一串二進位制來記錄這十億使用者的登入狀態，二進位制的每一位都代表一個使用者，0 代表未登入，1 代表已登入，每次登入或登出都利用 Bitmaps 去更新對應位的數值，最終形成的結果看起來就是這樣的：
我們用上面的一串二進位制記錄了這十億使用者的登入狀態，為什麼要這麼做？ 主要就是節省空間，讀取或更新速度快
我們來算一下這種儲存方式所需要的儲存空間大小：
十億使用者，每一個使用者佔 1 bit 所需空間 = 1000000000 bit = 1000000000 / 8 / 1024 / 1024 = 119 MB
以 MySQL 為例，儲存需要的空間大小：
假設僅有兩個欄位：使用者id，線上狀態 使用者id為BIGINT型別，大小為：8 Bytes 線上狀態使用TINYINT型別，大小為：1 Bytes 所需空間 = 1000000000 * (8 + 1) Bytes = 9000000000 Bytes = 8583 MB
差距顯而易見，這也很好理解，使用 MySQL 或者Redis 的 Hash 儲存，最小單元都是 位元組，和直接操作 位 自然無法比較。
以上是對 Redis 的 Bitmaps 的簡單介紹，接下來會介紹一下關於 Bitmaps 的基礎命令以及應用。
二、Bitmaps的操作
SETBIT
時間複雜度： O(1)
SETBIT key offset value
更新指定 key 的 offset 位置處的值，value 只可以是 0 或 1
需要注意：
1、offset 表示偏移量，最大為 2 32-1（(因為最大是512MB，符號佔1位)。
2、分配記憶體，一次分配之後，後續相同的key不會再有分配開銷，官網描述：在 2010 款 MacBook Pro 上，設定位數 2 32-1（512MB 分配）大約需要 300 毫秒。
3、返回值，返回對應 offset 操作之前的值。
GETBIT
時間複雜度： O(1)
GETBIT key offset
返回儲存在key的字串值中offset處的位值。
需要注意：
當 key 不存在，或者 offset 超出範圍時，返回整數 0
BITCOUNT
時間複雜度： O(n)
BITCOUNT key [start end [BYTE|BIT]]
計算字串中 1 的數量
範例： 127.0.0.1:6379> set k1 a OK 127.0.0.1:6379> BITCOUNT k1 (integer) 3 127.0.0.1:6379> set k1 aa OK 127.0.0.1:6379> BITCOUNT k1 (integer) 6 127.0.0.1:6379> BITCOUNT k1 0 0 (integer) 3 127.0.0.1:6379> BITCOUNT k1 0 1 (integer) 6 127.0.0.1:6379> BITCOUNT k1 0 -1 (integer) 6
需要注意：
1、start 和 end 引數指的是Byte，不是bit，官網介紹在7.0版本之後才可以指定 Byte或bit。
2、如果key 不存在，統計出來是0
3、時間複雜度是 O(n)，這個n是指start 和 end 引數之間的資料量，所以資料量過大時善用start 和 end，或者多建幾個key。
BITOP
時間複雜度： O(n)
BITOP operation destkey key [key ...]
在多個鍵（包含字串值）之間執行按位元運算並將結果儲存在目標鍵中
其中 operation有 ：AND，OR，XOR 和 NOT
destkey是指目標key，將後面的多個 key 進行按位元操作後，儲存在 destkey 中
// AND，按位元與 127.0.0.1:6379> set k1 a OK 127.0.0.1:6379> set k2 aa OK 127.0.0.1:6379> set k3 aaa OK 127.0.0.1:6379> bitop and dk1 k1 k2 k3 (integer) 3 127.0.0.1:6379> get dk1 "a\x00\x00"
如上面範例，將 k1 ，k2，k3，進行按位元與之後結果儲存在 dk1 中，dk1 後面的 \x00 是十六進位制， a\x00\x00 轉換成二進位制就是： 0110 0001 0000 0000 0000 0000。
// OR，按位元或 127.0.0.1:6379> bitop or dk2 k1 k2 k3 (integer) 3 127.0.0.1:6379> get dk2 "aaa" --------------------- //XOR ，按位元互斥或 127.0.0.1:6379> bitop xor dk3 k1 k2 k3 (integer) 3 127.0.0.1:6379> get dk3 "a\x00a" --------------------- //NOT，取反 0110 0001 取反 -> 1001 1110 -> 十六進位制 \x9e 127.0.0.1:6379> bitop not dk4 k1 (integer) 1 127.0.0.1:6379> get dk4 "\x9e"
BITPOS
時間複雜度： O(N)
BITPOS key bit [start [end [BYTE|BIT]]]
返回字串中設定為 1 或 0 的第一位的位置。
範例 127.0.0.1:6379> setbit k1 4 1 (integer) 0 127.0.0.1:6379> setbit k1 13 1 (integer) 0 127.0.0.1:6379> bitpos k1 1 (integer) 4 127.0.0.1:6379> bitpos k1 1 0 0 (integer) 4 127.0.0.1:6379> bitpos k1 1 1 1 (integer) 13
需要注意：
1、這裡的 start 、end 引數指的是 Byte，在7.0版本後可以指定 Byte或bit。
2、bitpos 、 setbit 、 getbit 遵循相同的位位置約定。
3、查詢 1 時，不存在的 key 或者 對應範圍的字串全是 0 ，返回 -1。
4、查詢 0 時，有三種特殊情況：
k2 = 1111 1111 , k3 不存在 --------------------------- // 不指定範圍或僅指定 start，且值全是1，這時候會查出來最右側的1的位置 + 1，可以視為右側填充了0 127.0.0.1:6379> BITPOS k2 0 (integer) 8 --------------------------- // 不指定範圍或僅指定 start，且key不存在，返回0 127.0.0.1:6379> BITPOS k3 0 (integer) 0 --------------------------- // 指定範圍，且範圍內沒有0，返回 -1 127.0.0.1:6379> BITPOS k2 1 1 (integer) -1
BITFIFLD
BITFIELD key [GET encoding offset] [SET encoding offset value] [INCRBY encoding offset increment] [OVERFLOW WRAP|SAT|FAIL]
該命令將 Redis 字串視為位陣列，並且能夠處理不同位寬和任意非（必要）對齊偏移量的特定整數位段，該命令有get、set、incrby操作
就是說可以利用這個命令，按位元分段的處理字串，舉個例子：
127.0.0.1:6379> set k1 aaa OK
| a | a | a |
|---|---|---|
| 0110 0001 | 0110 0001 | 0110 0001 |
k1的二進位制如上表格所示，接下來我們使用BITFIFLD命令來操作 k1
GET：
// u8 = 無符號 + 8 位 ； 0 = 從第0位開始 // 獲取到的結果就是 : 0110 0001 ，無符號轉換成十進位制就是 97 127.0.0.1:6379> BITFIELD k1 get u8 0 1) (integer) 97
// i8 = 有符號 + 8 位 ； 1 = 從第一位開始 // 結果 = 1100 0010 ，帶符號轉換成十進位制就是 -62 （不理解為啥是-62可以看一下二補數） 127.0.0.1:6379> BITFIELD k1 get i8 1 1) (integer) -62
SET：
// 將0-7位，變成98，也就是: 0110 0010 ，這對應的就是b,所以第一個字元變成了 b 127.0.0.1:6379> BITFIELD k1 set u8 0 98 1) (integer) 97 127.0.0.1:6379> get k1 "baa" ------------------------------------------ 127.0.0.1:6379> BITFIELD k1 set u8 #1 98 // #1的意思是 從第二個 8 位開始 1) (integer) 97 127.0.0.1:6379> get k1 "bba"
INCRBY：遞增或者遞減
// -1 表示遞增或遞減的數值，k1 的0-7位 減1，結果是97，k1就變成了 "aba" 127.0.0.1:6379> get k1 "bba" 127.0.0.1:6379> BITFIELD k1 incrby u8 0 -1 1) (integer) 97 127.0.0.1:6379> get k1 "aba" 127.0.0.1:6379> BITFIELD k1 incrby u8 #1 -1 1) (integer) 97 127.0.0.1:6379> get k1 "aaa"
在使用 INCRBY 進行遞增或遞減操作時，有 溢位控制 ，而且 Redis 提供了三種行為來控制溢位：
WRAP ：環繞，在無符號整數的情況下，換行就像對整數可以包含的最大值進行模運算
// 以 u8 為例，無符號，8位元，那麼最大值是 256 127.0.0.1:6379> BITFIELD k1 get u8 0 1) (integer) 97 127.0.0.1:6379> BITFIELD k1 overflow WRAP incrby u8 0 256 1) (integer) 97 127.0.0.1:6379> BITFIELD k1 overflow WRAP incrby u8 0 257 // 97 + 257 = 97+257-256 = 98 1) (integer) 98 127.0.0.1:6379> BITFIELD k1 overflow WRAP incrby u8 0 200 // 98 + 200 = 298 - 256 = 42 1) (integer) 42
在有符號的情況下，向上溢位到負值，向下溢位到正值，以 i8 為例 127 + 1 到 -128
127.0.0.1:6379> set k1 aaa OK 127.0.0.1:6379> BITFIELD k1 get u8 0 1) (integer) 97 127.0.0.1:6379> BITFIELD k1 incrby i8 0 30 1) (integer) 127 127.0.0.1:6379> BITFIELD k1 incrby i8 0 1 1) (integer) -128 127.0.0.1:6379> BITFIELD k1 incrby i8 0 -1 1) (integer) 127
SAT： 使用飽和演演算法，即下溢時設定為最小整數值，溢位時設定為最大整數值。
// u8時，最大255 最小 0 127.0.0.1:6379> set k1 aaa OK 127.0.0.1:6379> BITFIELD k1 get u8 0 1) (integer) 97 127.0.0.1:6379> BITFIELD k1 overflow SAT incrby u8 0 20000 1) (integer) 255 127.0.0.1:6379> BITFIELD k1 overflow SAT incrby u8 0 -213123 1) (integer) 0
FAIL：在此模式下，不會對檢測到的上溢或下溢執行任何操作。相應的返回值設定為 NULL 以向呼叫者發出條件訊號。就是說，溢位就返回 NUll。
127.0.0.1:6379> set k1 aaa OK 127.0.0.1:6379> BITFIELD k1 get u8 0 1) (integer) 97 127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 200 1) (nil) 127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 -98 1) (nil)
另外，以上的 BITFIELD 命令可以多個一起使用：
127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 -98 get u8 0 1) (nil) 2) (integer) 97
BITFIELD_RO
BITFIELD命令的唯讀變體。它就像原始的BITFIELD一樣，但只接受GET子命令並且可以安全地用於唯讀副本。
Bitmaps 的應用
在上面的描述中，介紹了 Bitmaps 可以記錄使用者的線上狀態，除此之外還可以用他做那些功能呢？
首先我們來總結一下Bitmaps的特點：
- 只有 0 和 1 兩種狀態(描述的資訊比較侷限)
- 佔用的記憶體非常少
- 存取速度極快 (set，get操作時間複雜度都是O(1))
基於這些特點，我們可以用 Bitmaps 來判斷資料是否存在於某個集合中、也可以用於記錄使用者的一些行為比如登入或者某個頁面的檢視，關閉，簽到等等，接下來我們舉幾個比較常見的例子。
日活統計
如何統計當前系統每天登入的使用者數量？
使用Redis的Bitmaps，將 系統名+日期設定為key 如 zcy20211215，value中使用使用者的Id做offset，用 0 和 1 記錄使用者在當天是否登入過，登入將對應的位設定為1。
這樣做之後，每天可以得到一個Bitmaps，如果想獲取某天登入過的使用者數量，直接使用 BITCOUNT 操作即可。
如果想統計過去 30 天都登入過的使用者，可以使用 BITOP AND 操作，將那 30 天的Bitmaps進行 按位元與 操作。
布隆過濾器
布隆過濾器的本質是 Hash對映演演算法 + Bitmaps。
如圖，一個 value 進入布隆過濾器，經過多個Hash演演算法，獲取其對映在Bitmap上的位置，當所有的位置都為1時，則認為這個 value 在過濾器中，否則就認為不存在。
行銷資料統計
Bitmaps 在行銷系統中可以用到的場景很多：
人物誌資訊的使用，一個使用者有很多中標籤並且無限擴充套件，比如 性別，是否是程式設計師，單身，租房，是否養寵物，我們都可以考慮用Bitmap儲存和使用。
使用者的行為，是否點選了廣告，是否瀏覽到底部，是否領取優惠券等行為分別用一個Bitmap儲存，用法和上面的人物誌類似。
這裡舉一個小例子，看一下Bitmaps在行銷系統中的使用：
假設我們有一個一億使用者的電商應用，產品提了這樣一個需求：
所有的男性使用者在進入應用首頁時，彈出一個 防脫髮保健品 的廣告彈窗
需求很簡單，一個介面搞定，使用者進入時呼叫 獲取廣告 的介面，介面中查詢資料庫判斷是否為男性，是返回廣告內容，否返回空。
這時候產品覺得這種推播不夠精準，也未必男性都會掉頭髮，所以增加了條件： 程式設計師，我們的需求就變成了：
所有的 男性 且職業為 程式設計師 的使用者在進入應用首頁時，彈出一個 防脫髮保健品 的廣告彈窗
加了一個條件之後依然很簡單，使用者的 性別 和 職業 資訊極有可能存在一張表，也是一次查詢即可。
然而，男性程式設計師脫髮的概率很高，但是未必都買得起防脫髮保健品，這時候需要推播的更精準一點，所以再新增一個條件：在平臺上月均消費超過五百 ，這個條件和上述的 男性、程式設計師 這兩個條件大概率不在同一個表中，如果用上面的方案，那就是再增加一次DB查詢，速度慢且對資料庫開銷大，這個時候 Bitmaps 的效果就很明顯了。
現有的條件是：男性、程式設計師、在平臺上月均消費超過五百
在這個場景中，如果要使用 Bitmaps，首先要把資料載入到Redis裡，可以用一種簡單粗暴的方法，直接遍歷資料庫，把需要用的標籤資訊載入到Redis中：
// 使用者標籤載入虛擬碼
public Boolean loadUserLabel() {
// 使用者性別 bitmap 資料載入
String key = "user_label_sex_male";
List<User> users = userDao.queryUser();
users.forEach(
t->{
if (Objects.equals(t.getSex(),"male")) {
jedis.setbit(key,t.getId(),"1");
}
}
);
return true;
}經過上述程式碼，將使用者的性別載入到了 redis 的 bitmap中，其他的標籤如 職業、消費大於五百，與此類似。
在Redis中有了我們所需的使用者標籤資訊後，就可以開始使用了，像我們上述的需求，可以用 BITOP 命令的 AND操作，將男性、程式設計師、月均消費大於五百這三個Bitmap 生成一個 同時滿足這三個條件的 Bitmap，標籤過多的時候可以這樣做。在這裡我們就三個條件，可以簡單一點直接在程式碼裡查三次：
// 使用者首頁廣告獲取虛擬碼
public Response getHomepageAds(User user) {
// 這裡寫死，實際使用中是動態設定
String maleKey = "user_label_sex_male";
String programmerKey = "user_label_occupation_programmer";
String spendMonth500Key = "user_label_spend_month_500";
//去bitmap判斷，該位為1，則滿足條件
if (jedis.getbit(maleKey,user.getId()) && jedis.getbit(programmerKey,user.getId())
&& jedis.getbit(spendMonth500Key,user.getId())) {
return "內容";
}
return "沒有廣告";
}上面就是一個Bitmap在行銷系統中應用的小例子，可以在這基礎上進行很多擴充套件，比如每個標籤的實時的增量載入，每個廣告和標籤的繫結關係的動態設定，標籤的自動生成等等等等。。。。
我們接下來可以看一下 Bitmaps 在使用者行為記錄中的應用，現在產品提了一個新的需求：
我想知道有多少使用者點進了我們的彈窗廣告
點選彈窗廣告之後，前端傳送請求，後端記錄使用者的點選狀態：
// 使用者點選廣告行為記錄虛擬碼
public Response getHomepageAds(User user) {
String adActionKey = "homepage_ad_action_open";
jedis.setbit(adActionKey,user.getId(),"1");
}後面如果想統計數量，可以直接用 BITCOUNT 命令。其他行為的記錄和這個相似，如是否拖動到底部，停留時間是否大於n秒等等，這裡就不做贅述啦。
協同製圖
這個例子來源於Redis官網，是 Reddit 在 2017 年愚人節的一個遊戲 r/place，這是一個非常有趣的 Bitmaps 的應用。
遊戲介紹：
一個畫板，上面有1000 * 1000 個畫素點，每個玩家每五分鐘可以編輯一個畫素點(有十六種顏色提供選擇)，參與的玩家數量不限，72 小時後截止。
遊戲很簡單，每個人只要編輯畫素點的顏色即可，17 年的活動最終形成了這個畫（這裡是一部分）：
這裡面有一百萬個畫素點，據統計至少十萬人蔘與了這個遊戲，並行量很高，如何保證可用性呢？Reddit 在這裡就使用了 Redis 的 Bitmap：
先定義畫板中的畫素的位置，用 x 表示橫座標，y 表示縱座標，每一個畫素點的位置都對應 Bitmap 的一個offset。
使用者編輯畫素點時，將 位置資訊(x,y) 和 顏色資訊 用 Bitmap 儲存，讀取畫板資料也是直接利用 Bitmap。
思路很簡單，主要是解決下面兩個問題：
1、座標和Bitmap之間的對映關係？ 座標如何轉換成 Bitmap的 offset，offset如何轉換成畫板中的 x,y 座標。
2、如何直接利用 Bitmaps 儲存一個座標點的資訊？ 這裡就存顏色。
這個專案是這麼做的：
1、由於總計畫素點是 100 萬個，所以設計了公式： x + 1000y = offset
儲存時，將 (x,y) 轉換成 offset ，比如 (1,2) 位置，那麼 offset = 1 + 2000 = 2001
讀取時，將 offset 轉換成(x,y)，比如 offset = 9008，那麼 x = 9008 % 1000 = 8，y = 9008 / 1000 = 9
2、利用 Bitmaps 的 BITFIELD 命令，進行分段操作：
玩家可選擇的顏色共 16 種，那麼每個點至少需要 4 位，所以使用 BITFIELD 時，操作的位數位段應該是 u4
看起來就是這樣的：
上面是這個遊戲對於 Bitmaps 應用的簡單介紹，具體實現及原始碼見文末Reddit 團隊的部落格。
利用 BITFIELD 命令，還可以判斷資料是否重複，比如有 10 億個整數，如何找出其中重複的資料？ 每個數可以給 2 位，01表示出現一次，10表示有重複。
四、小擴充套件
當使用者 Id 不是自增 Id，該如何使用 Bitmaps？
在實際開發中，使用者的Id有可能不是自增的，比如使用雪花演演算法，或UUID工具生成的Id，這種情況直接使用 Bitmaps 是不行的，偏移量過大。這時候可以參考 布隆過濾器 ，設計一個Id的對映演演算法，將使用者Id對映在一定範圍內。
Bitmaps 進行持久化儲存時，如何節省空間？
使用壓縮演演算法，如 RLE演演算法
在使用Bitmaps時，會有大量連續的位置資料重複，這些重複就有壓縮的空間，比如前 1000 位都是 0，那隻用存一句 1000個0即可，而不是 00000...這樣存一千個。
更多程式設計相關知識，請存取：！！
以上就是Redis學習之深入瞭解Bitmaps的詳細內容，更多請關注TW511.COM其它相關文章！