前言

如果要統(tǒng)計(jì)一篇文章的閱讀量，可以直接使用 Redis 的 incr 指令來完成。如果要求閱讀量必須按用戶去重，那就可以使用 set 來記錄閱讀了這篇文章的所有用戶 id，獲取 set 集合的長度就是去重閱讀量。但是如果爆款文章閱讀量太大，set 會(huì)浪費(fèi)太多存儲(chǔ)空間。這時(shí)候我們就要使用 Redis 提供的 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)來代替 set，它只會(huì)占用最多 12k 的存儲(chǔ)空間就可以完成海量的去重統(tǒng)計(jì)。但是它犧牲了準(zhǔn)確度，它是模糊計(jì)數(shù)，誤差率約為 0.81%。

那么有沒有一種不怎么浪費(fèi)空間的精確計(jì)數(shù)方法呢？我們首先想到的就是位圖，可以使用位圖的一個(gè)位來表示一個(gè)用戶id。如果一個(gè)用戶id是32字節(jié)，那么使用位圖就只需要占用 1/256 的空間就可以完成精確計(jì)數(shù)。但是如何將用戶id映射到位圖的位置呢？如果用戶id是連續(xù)的整數(shù)這很好辦，但是通常用戶系統(tǒng)的用戶id并不是整數(shù)，而是字符串或者是有一定隨機(jī)性的大整數(shù)。

我們可以強(qiáng)行給每個(gè)用戶id賦予一個(gè)整數(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

這里你也許會(huì)提出疑問，你說是為了節(jié)省空間，這里存儲(chǔ)用戶id和整數(shù)的映射關(guān)系就不浪費(fèi)空間了么？這個(gè)問題提的很好，但是同時(shí)我們也要看到這個(gè)映射關(guān)系是可以復(fù)用的，它可以統(tǒng)計(jì)所有文章的閱讀量，還可以統(tǒng)計(jì)簽到用戶的日活、月活，還可以用在很多其它的需要用戶去重的統(tǒng)計(jì)場合中。所謂「功在當(dāng)代，利在千秋」就是這個(gè)意思。

有了這個(gè)映射關(guān)系，我們就很容易構(gòu)造出每一篇文章的閱讀打點(diǎn)位圖，來一個(gè)用戶，就將相應(yīng)位圖中相應(yīng)的位置為一。如果位從0變成1，那么就可以給閱讀數(shù)加1。這樣就可以很方便的獲得文章的閱讀數(shù)。

而且我們還可以動(dòng)態(tài)計(jì)算閱讀了兩篇文章的公共用戶量有多少？將兩個(gè)位圖做一下 AND 計(jì)算，然后統(tǒng)計(jì)位圖中位 1 的個(gè)數(shù)。同樣，還可以有 OR 計(jì)算、XOR 計(jì)算等等都是可行的。

問題又來了！Redis 的位圖是密集位圖，什么意思呢？如果有一個(gè)很大的位圖，它只有最后一個(gè)位是 1，其它都是零，這個(gè)位圖還是會(huì)占用全部的內(nèi)存空間，這就不是一般的浪費(fèi)了。你可以想象大部分文章的閱讀量都不大，但是它們的占用空間卻是很接近的，和哪些爆款文章占據(jù)的內(nèi)存差不多。

看來這個(gè)方案行不通，我們需要想想其它方案！這時(shí)咆哮位圖（RoaringBitmap）來了。

它將整個(gè)大位圖進(jìn)行了分塊，如果整個(gè)塊都是零，那么這整個(gè)塊就不用存了。但是如果位1比較分散，每個(gè)塊里面都有1，雖然單個(gè)塊里的1很少，這樣只進(jìn)行分塊還是不夠的，那該怎么辦呢？我們再想想，對于單個(gè)塊，是不是可以繼續(xù)優(yōu)化？如果單個(gè)塊內(nèi)部位 1 個(gè)數(shù)量很少，我們可以只存儲(chǔ)所有位1的塊內(nèi)偏移量（整數(shù)），也就是存一個(gè)整數(shù)列表，那么塊內(nèi)的存儲(chǔ)也可以降下來。這就是單個(gè)塊位圖的稀疏存儲(chǔ)形式 —— 存儲(chǔ)偏移量整數(shù)列表。只有單塊內(nèi)的位1超過了一個(gè)閾值，才會(huì)一次性將稀疏存儲(chǔ)轉(zhuǎn)換為密集存儲(chǔ)。

咆哮位圖除了可以大幅節(jié)約空間之外，還會(huì)降低 AND、OR 等位運(yùn)算的計(jì)算效率。以前需要計(jì)算整個(gè)位圖，現(xiàn)在只需要計(jì)算部分塊。如果塊內(nèi)非常稀疏，那么只需要對這些小整數(shù)列表進(jìn)行集合的 AND、OR 運(yùn)算，如是計(jì)算量還能繼續(xù)減輕。

這里既不是用空間換時(shí)間，也沒有用時(shí)間換空間，而是用邏輯的復(fù)雜度同時(shí)換取了空間和時(shí)間。

咆哮位圖的位長最大為 2^32，對應(yīng)的空間為 512M（普通位圖），位偏移被分割成高 16 位和低 16 位，高 16 位表示塊偏移，低16位表示塊內(nèi)位置，單個(gè)塊可以表達(dá) 64k 的位長，也就是 8K 字節(jié)。最多會(huì)有64k個(gè)塊?，F(xiàn)代處理器的 L1 緩存普遍要大于 8K，這樣可以保證單個(gè)塊都可以全部放入 L1 Cache，可以顯著提升性能。

如果單個(gè)塊所有的位全是零，那么它就不需要存儲(chǔ)。具體某個(gè)塊是否存在也可以是用位圖來表達(dá)，當(dāng)塊很少時(shí)，用整數(shù)列表表示，當(dāng)塊多了就可以轉(zhuǎn)換成普通位圖。整數(shù)列表占用的空間少，它還有類似于 ArrayList 的動(dòng)態(tài)擴(kuò)容機(jī)制避免反復(fù)擴(kuò)容復(fù)制數(shù)組內(nèi)容。當(dāng)列表中的數(shù)字超出4096個(gè)時(shí)，會(huì)立即轉(zhuǎn)變成普通位圖。

用來表達(dá)塊是否存在的數(shù)據(jù)結(jié)構(gòu)和表達(dá)單個(gè)塊數(shù)據(jù)的結(jié)構(gòu)可以是同一個(gè)，因?yàn)閴K是否存在本質(zhì)上也是 0 和 1，就是普通的位標(biāo)志。

但是 Redis 并沒有原生支持咆哮位圖這個(gè)數(shù)據(jù)結(jié)構(gòu)?。课覀冊撊绾问褂媚?？

Redis 確實(shí)沒有原生的，但是咆哮位圖的 Redis Module 有。

github.com/aviggiano/r…

這個(gè)項(xiàng)目的 star 數(shù)量并不是很多，我們來看看它的官方性能對比

很明顯這里對比的是稀疏位圖，只有稀疏位圖才可以呈現(xiàn)出這樣好看的數(shù)字。如果是密集位圖，咆哮位圖的性能肯定要稍弱于普通位圖，但是通常也不會(huì)弱太多。

下面我們來觀察一下源代碼看看它的內(nèi)部結(jié)構(gòu)是怎樣的

// 單個(gè)塊
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)表達(dá)的，它們都是 roaring_bitmap_t。這個(gè)結(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ù)的幾個(gè)位 101,102,103,104,105,106,107,108,109 表示成 RUN 后就是 101,8（1 后面是 8 個(gè)自增的整數(shù)），這樣在空間上就可以明顯壓縮不少。在正常情況下咆哮位圖內(nèi)部沒有 RUN 類型的塊。只有顯示調(diào)用了咆哮位圖的優(yōu)化 API 才會(huì)轉(zhuǎn)換成 RUN 格式，這個(gè) API 是 roaring_bitmap_run_optimize。

而 SHARED 類型用于在多個(gè)咆哮位圖之間共享塊，它還提供了寫復(fù)制功能。當(dāng)這個(gè)塊被修改時(shí)將會(huì)復(fù)制出新的一份。
咆哮位圖的計(jì)算邏輯還有更多的細(xì)節(jié)，我們后面有空再繼續(xù)介紹。

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對腳本之家的支持。

最新評論