前言
如果要統(tǒng)計一篇文章的閱讀量,可以直接使用 Redis 的 incr 指令來完成。如果要求閱讀量必須按用戶去重,那就可以使用 set 來記錄閱讀了這篇文章的所有用戶 id,獲取 set 集合的長度就是去重閱讀量。但是如果爆款文章閱讀量太大,set 會浪費太多存儲空間。這時候我們就要使用 Redis 提供的 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)來代替 set,它只會占用最多 12k 的存儲空間就可以完成海量的去重統(tǒng)計。但是它犧牲了準(zhǔn)確度,它是模糊計數(shù),誤差率約為 0.81%。
那么有沒有一種不怎么浪費空間的精確計數(shù)方法呢?我們首先想到的就是位圖,可以使用位圖的一個位來表示一個用戶id。如果一個用戶id是32字節(jié),那么使用位圖就只需要占用 1/256 的空間就可以完成精確計數(shù)。但是如何將用戶id映射到位圖的位置呢?如果用戶id是連續(xù)的整數(shù)這很好辦,但是通常用戶系統(tǒng)的用戶id并不是整數(shù),而是字符串或者是有一定隨機性的大整數(shù)。
我們可以強行給每個用戶id賦予一個整數(shù)序列,然后將用戶id和整數(shù)的對應(yīng)關(guān)系存在redis中。
$next_user_id = incr user_id_seq
set user_id_xxx $next_user_id
$next_user_id = incr user_id_seq
set user_id_yyy $next_user_id
$next_user_id = incr user_id_seq
set user_id_zzz $next_user_id
這里你也許會提出疑問,你說是為了節(jié)省空間,這里存儲用戶id和整數(shù)的映射關(guān)系就不浪費空間了么?這個問題提的很好,但是同時我們也要看到這個映射關(guān)系是可以復(fù)用的,它可以統(tǒng)計所有文章的閱讀量,還可以統(tǒng)計簽到用戶的日活、月活,還可以用在很多其它的需要用戶去重的統(tǒng)計場合中。所謂「功在當(dāng)代,利在千秋」就是這個意思。
有了這個映射關(guān)系,我們就很容易構(gòu)造出每一篇文章的閱讀打點位圖,來一個用戶,就將相應(yīng)位圖中相應(yīng)的位置為一。如果位從0變成1,那么就可以給閱讀數(shù)加1。這樣就可以很方便的獲得文章的閱讀數(shù)。
而且我們還可以動態(tài)計算閱讀了兩篇文章的公共用戶量有多少?將兩個位圖做一下 AND 計算,然后統(tǒng)計位圖中位 1 的個數(shù)。同樣,還可以有 OR 計算、XOR 計算等等都是可行的。
問題又來了!Redis 的位圖是密集位圖,什么意思呢?如果有一個很大的位圖,它只有最后一個位是 1,其它都是零,這個位圖還是會占用全部的內(nèi)存空間,這就不是一般的浪費了。你可以想象大部分文章的閱讀量都不大,但是它們的占用空間卻是很接近的,和哪些爆款文章占據(jù)的內(nèi)存差不多。
看來這個方案行不通,我們需要想想其它方案!這時咆哮位圖(RoaringBitmap)來了。
它將整個大位圖進行了分塊,如果整個塊都是零,那么這整個塊就不用存了。但是如果位1比較分散,每個塊里面都有1,雖然單個塊里的1很少,這樣只進行分塊還是不夠的,那該怎么辦呢?我們再想想,對于單個塊,是不是可以繼續(xù)優(yōu)化?如果單個塊內(nèi)部位 1 個數(shù)量很少,我們可以只存儲所有位1的塊內(nèi)偏移量(整數(shù)),也就是存一個整數(shù)列表,那么塊內(nèi)的存儲也可以降下來。這就是單個塊位圖的稀疏存儲形式 —— 存儲偏移量整數(shù)列表。只有單塊內(nèi)的位1超過了一個閾值,才會一次性將稀疏存儲轉(zhuǎn)換為密集存儲。
咆哮位圖除了可以大幅節(jié)約空間之外,還會降低 AND、OR 等位運算的計算效率。以前需要計算整個位圖,現(xiàn)在只需要計算部分塊。如果塊內(nèi)非常稀疏,那么只需要對這些小整數(shù)列表進行集合的 AND、OR 運算,如是計算量還能繼續(xù)減輕。
這里既不是用空間換時間,也沒有用時間換空間,而是用邏輯的復(fù)雜度同時換取了空間和時間。
咆哮位圖的位長最大為 2^32,對應(yīng)的空間為 512M(普通位圖),位偏移被分割成高 16 位和低 16 位,高 16 位表示塊偏移,低16位表示塊內(nèi)位置,單個塊可以表達 64k 的位長,也就是 8K 字節(jié)。最多會有64k個塊?,F(xiàn)代處理器的 L1 緩存普遍要大于 8K,這樣可以保證單個塊都可以全部放入 L1 Cache,可以顯著提升性能。
如果單個塊所有的位全是零,那么它就不需要存儲。具體某個塊是否存在也可以是用位圖來表達,當(dāng)塊很少時,用整數(shù)列表表示,當(dāng)塊多了就可以轉(zhuǎn)換成普通位圖。整數(shù)列表占用的空間少,它還有類似于 ArrayList 的動態(tài)擴容機制避免反復(fù)擴容復(fù)制數(shù)組內(nèi)容。當(dāng)列表中的數(shù)字超出4096個時,會立即轉(zhuǎn)變成普通位圖。
用來表達塊是否存在的數(shù)據(jù)結(jié)構(gòu)和表達單個塊數(shù)據(jù)的結(jié)構(gòu)可以是同一個,因為塊是否存在本質(zhì)上也是 0 和 1,就是普通的位標(biāo)志。
但是 Redis 并沒有原生支持咆哮位圖這個數(shù)據(jù)結(jié)構(gòu)???我們該如何使用呢?
Redis 確實沒有原生的,但是咆哮位圖的 Redis Module 有。
github.com/aviggiano/r…
這個項目的 star 數(shù)量并不是很多,我們來看看它的官方性能對比
OP |
TIME/OP (us) |
ST.DEV. (us) |
R.SETBIT |
31.89 |
28.49 |
SETBIT |
29.98 |
29.23 |
R.GETBIT |
29.90 |
14.60 |
GETBIT |
28.63 |
14.58 |
R.BITCOUNT |
32.13 |
0.10 |
BITCOUNT |
192.38 |
0.96 |
R.BITPOS |
70.27 |
0.14 |
BITPOS |
87.70 |
0.62 |
R.BITOP NOT |
156.66 |
3.15 |
BITOP NOT |
364.46 |
5.62 |
R.BITOP AND |
81.56 |
0.48 |
BITOP AND |
492.97 |
8.32 |
R.BITOP OR |
107.03 |
2.44 |
BITOP OR |
461.68 |
8.42 |
R.BITOP XOR |
69.07 |
2.82 |
BITOP XOR |
440.75 |
7.90 |
很明顯這里對比的是稀疏位圖,只有稀疏位圖才可以呈現(xiàn)出這樣好看的數(shù)字。如果是密集位圖,咆哮位圖的性能肯定要稍弱于普通位圖,但是通常也不會弱太多。
下面我們來觀察一下源代碼看看它的內(nèi)部結(jié)構(gòu)是怎樣的
// 單個塊
typedef struct roaring_array_s {
int32_t size;
int32_t allocation_size;
void **containers; // 指向整數(shù)數(shù)組或者普通位圖
uint16_t *keys;
uint8_t *typecodes;
uint8_t flags;
} roaring_array_t;
// 所有塊
typedef struct roaring_bitmap_s {
roaring_array_t high_low_container;
} roaring_bitmap_t;
很明顯可以看到塊存在與否和塊內(nèi)數(shù)據(jù)都是使用同樣的數(shù)據(jù)結(jié)構(gòu)表達的,它們都是 roaring_bitmap_t。這個結(jié)構(gòu)里面有多種編碼形式,類型使用 typecodes 字段來表示。
#define BITSET_CONTAINER_TYPE_CODE 1
#define ARRAY_CONTAINER_TYPE_CODE 2
#define RUN_CONTAINER_TYPE_CODE 3
#define SHARED_CONTAINER_TYPE_CODE 4
看到這里的類型定義,我們發(fā)現(xiàn)它不止前面提到的普通位圖和數(shù)組列表兩種形式,還有 RUN 和 SHARED 這兩種類型。RUN 形式是位圖的壓縮形式,比如連續(xù)的幾個位 101,102,103,104,105,106,107,108,109 表示成 RUN 后就是 101,8(1 后面是 8 個自增的整數(shù)),這樣在空間上就可以明顯壓縮不少。在正常情況下咆哮位圖內(nèi)部沒有 RUN 類型的塊。只有顯示調(diào)用了咆哮位圖的優(yōu)化 API 才會轉(zhuǎn)換成 RUN 格式,這個 API 是 roaring_bitmap_run_optimize。
而 SHARED 類型用于在多個咆哮位圖之間共享塊,它還提供了寫復(fù)制功能。當(dāng)這個塊被修改時將會復(fù)制出新的一份。
咆哮位圖的計算邏輯還有更多的細節(jié),我們后面有空再繼續(xù)介紹。
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,謝謝大家對腳本之家的支持。
您可能感興趣的文章:- 基于Redis位圖實現(xiàn)系統(tǒng)用戶登錄統(tǒng)計
- PHP使用redis位圖bitMap 實現(xiàn)簽到功能
- redis通過位圖法記錄在線用戶的狀態(tài)詳解
- java redis 實現(xiàn)簡單的用戶簽到功能
- 基于Redis位圖實現(xiàn)用戶簽到功能