1 前言
在之前文章 《深刻了解高性能Redis的本質》 的時候就介紹過Redis的幾種基本資料結構,它是基于不同業務場景而設計的:
- 動态字元串(REDIS_STRING):整數(REDIS_ENCODING_INT)、字元串(REDIS_ENCODING_RAW)
- 雙端清單(REDIS_ENCODING_LINKEDLIST)
- 壓縮清單(REDIS_ENCODING_ZIPLIST)
- 跳躍表(REDIS_ENCODING_SKIPLIST)
- 哈希表(REDIS_HASH)
- 整數集合(REDIS_ENCODING_INTSET)
除了這常見資料類型,還有一些不常用的資料類型,如 BitMap、Geo、HyperLogLog 等等,他們在各自的領域為大資料量的統計,後面我們一一來介紹,學習下他們的實作原理和應用場景。
2 BitMap介紹
BitMap (位圖)的底層資料結構使用的是String類型的的 SDS 資料結構來儲存。因為一個位元組8個bit位,為了有效的将位元組的8個bit都利用到位,使用數組模式存儲。
并且每個bit都使用二值狀态表示,要麼0,要麼1。
是以,BitMap 是通過一個 bit 位來表示某個元素對應的值或者狀态, 它的結構如下,key 對應元素本身;offset即是偏移量,固定整型,一般存數組下表或者唯一值;value存儲的是二值(要麼0要麼1),一般用來表示狀态,如性别、是否登入、是否打卡等。
從上面可以看出這邊使用一個位元組表示1行,每1行存儲8個bit,就是可以存儲8個狀态位,極大的提高了空間利用。這也是BitMap的優勢,我們可以使用很少的位元組,存儲大量的線上狀态、打卡标記等狀态資訊,非常有效果。
我們可以使用 setbit, getbit, bitcount 等幾個相關指令來管理BitMap。文法如下:
SETBIT key offset value
上面說過了,key是元素名稱, offset 必須是數值類型,value 隻能是 0 或者 1,如果我們存儲一個使用者的線上狀态,使用者,代碼如下:
//設定線上狀态
// $redis->setBit('online', $uid, 1);
$redis->setBit('online', 5, 1);
$redis->setBit('online', 9, 1);
則具體展現為:
byte | bit0 | bit1 | bit2 | bit3 | bit4 | bit5 | bit6 | bit7 |
buf[0] | 1 | |||||||
buf[1] | 1 |
可以看出使用者ID為5和9被打上1的标志,代表線上狀态,其他未設定值預設為0,是離線狀态。
除了Set之外,還有getBit、bitCount等文法,如下:
// 擷取是否線上的狀态
$isOnline = $redis->getBit('online', $uid);
// 擷取線上人數 統計
$onlineNum = $redis->bitCount('online');
3 BitMap的主要應用場景
上面介紹了BitMap的原理和狀态存儲的優勢。那我們存儲了bit位,其實目的還是為了高效的計算,而不是簡單的狀态記錄。
而在實際的應用場景中,他主要解決如下幾個類型的需求:
3.1 狀态統計
上面其實我們已經示範過了,這種場景最常見,因為值隻能是1或者0,是以所有的二值狀态的,所有存在是否對照關系的場景都可以使用。如線上(1) 離線(0),打卡(1) 未打卡(0),登入(1) 未登入(0),群聊消息已閱(1) 未閱(0) 等等。
我們以使用者 離線/線上 為例子,看看如何使用 Bitmap 在海量的使用者資料之中判斷某個使用者是否是線上狀态。
假設我們使用一個 online_statu 來作為key,用來存儲 使用者登入後的狀态集合,而使用者的ID則為offset,online的狀态就用1表示,offline的狀态就用0表示。
- 如果1024使用者登入系統,那麼設定ID為1024的使用者為線上的代碼如下:
SETBIT online_statu 1024 1
- 如果想看1024的使用者是否是線上狀态(這邊注意,key可能不存在,代表沒有這個使用者,這時候預設傳回0),代碼如下:
GETBIT online_statu 1024
- 如果1024的使用者退出系統,則為他執行下線,代碼如下:
SETBIT online_statu 1024 0
- 空間上的有效利用,1億 人的狀态存儲隻需要 100000000/8/1024/1024 = 11.92 M,簡單的資料結構也保證了性能上的優勢。
基于上面的讨論,我們可以總結出一個預評估公式,根據實際的資料量擷取存儲空間:( offset / 8 / 1024 / 1024 ) M
3.2 固定周期的簽到情況統計(周/月/年)
固定周期可能是年/月/周,按照不同次元,可能有 365,31,7的bit位的統計周期。
假設這時候我們如果對于某個使用者(如1024)全年的簽到情況做統計,可以這麼設計:
-
設計key 為 {bus_type}{uid}{yyyy} ,及業務類型+使用者id+年份
比如 sign_1024_2022
-
簽到則執行對應代碼
舉例,1024使用者在2022 年的第1天和最後一天如果有簽到,那就是:
# 22年第一天
SETBIT sign_1024_2022 0 1
# 22年最後一天
SETBIT sign_1024_2022 364 1
- 判斷某使用者(1024)在某一天(150)是否有簽到
GETBIT sign_1024_2022 150
- 統計某使用者(1024) 全面的簽到次數,使用 BITCOUNT 指令,統計給定的 bit 數組中,值 = 1 的所有bit位數量。
BITCOUNT sign_1024_2022
-
那如果你想限定範圍了怎麼辦,比如原來設計的是一年的統計。但是你想獲得某個月第一次打卡的資料,這時候就要使用BITPOS了。
通過 BITPOS key value [start] [end] 指令,傳回資料表示 Bitmap 中第一個值為 給定value 的 offset 位置。
在預設情況下,指令會檢測整個位圖,但使用者也可以通過可選的start參數和end參數指定要檢測的範圍。
比如第2個月的第3天是2月的第一次簽到日,則下面的傳回結果為30(第一個月31天)+ 3(二月第3天簽到) = 33 :
$index = BITPOS sign_1024_2022 30
offset也是從0開始的,是以傳回的值最好加個1,不會讓使用者看的暈頭轉向。
3.3 連續簽到使用者資訊
如果一個平台有千萬級别以上的大量使用者,而我們需要統計每個使用者連續簽到的資訊,那需要怎麼設計呢?
- 可以把每天的日期當成位圖(BitMap)的key,如 20221023
- 使用者的唯一鍵當成(UserId)當成offset,如編号 1024 的使用者
- 如果 1024 的使用者在 2022.10.23 有簽到,則位圖的value為1,否則為0。
如果這時候我們要判斷使用者是否整周都有簽到或者整個月都有簽到就可以使用 【與】運算
隻有指定周期内的所有值都是1(簽到)的時候,結果才是1,否則是我們整周或者整個月都拿起來【與】運算,得到的結果是不是1就能确是否滿勤。
# 與運算: 0&0=0;0&1=0;1&0=0;1&1=1
# 下面為僞代碼,類似:
(20221022 1024) & ( 20221023 1024) & ...
Redis 提供了 BITOP operation destkey key [key …]這個指令用于對一個或者多個 鍵 = key 的 Bitmap 進行 位元 操作。
operation 可以是 AND 、 OR 、 NOT 、 XOR 這四種操作中的任意一種:
- BITOP AND destkey key [key …] ,對一個或多個 key 求邏輯并,并将結果儲存到 destkey 。
- BITOP OR destkey key [key …] ,對一個或多個 key 求邏輯或,并将結果儲存到 destkey 。
- BITOP XOR destkey key [key …] ,對一個或多個 key 求邏輯異或,并将結果儲存到 destkey 。
- BITOP NOT destkey key ,對給定 key 求邏輯非,并将結果儲存到 destkey 。
除了 NOT 操作之外,其他操作都可以接受一個或多個 key 作為輸入。
# 統計一周的值(7個BitMap,10.17 ~ 10.23 号)并将結果存入到新的BitMap (sign-result) 中
redis> BITOP AND sign-result 20221017 20221018 20221019 20221020 20221021 20221022 20221023
(integer) 1
# 新的BitMap 中,擷取 1024的簽到結果,如果為1,則本周全部簽到
redis> GETBIT sign-result 1024
(integer) 1
可以了解下這張圖的運算過程:
這邊需要注意:當 BITOP 處理不同長度的字元串時,較短字元串所缺部分會被當作 0 對待。同樣的,空 key 也被看作是 0 的字元串序列看待。
同理,類似HeapDump性能社群的使用者簽到統計,也可以用位圖(BitMap)這種方式計算!
小結
1個byte等于8個bit,每個bit位隻使用0或者1來表示,這樣能夠有效的降低存儲空間,而Redis是存儲在高速緩存中的,是以實際上是大大減少了記憶體占用。
很多場景都可以使用位圖計算,比如我們上面說到的 是否登入、是否線上、是否簽到、使用者性别狀态、IP黑名單、是否VIP使用者統計 等等場景,但凡涉及到二值狀态識别、海量統計的資料都可以考慮使用。
為幫助開發者們提升面試技能、有機會入職BATJ等大廠公司,特别制作了這個專輯——這一次整體放出。
大緻内容包括了: Java 集合、JVM、多線程、并發程式設計、設計模式、Spring全家桶、Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Memcached、MongoDB、Redis、MySQL、RabbitMQ、Kafka、Linux、Netty、Tomcat等大廠面試題等、等技術棧!
歡迎大家關注公衆号【Java爛豬皮】,回複【666】,擷取以上最新Java後端架構VIP學習資料以及視訊學習教程,然後一起學習,一文在手,面試我有。
每一個專欄都是大家非常關心,和非常有價值的話題,如果我的文章對你有所幫助,還請幫忙點贊、好評、轉發一下,你的支援會激勵我輸出更高品質的文章,非常感謝!