快捷導(dǎo)航

Redis精確去重計(jì)數(shù)方法（咆哮位圖）

更新時(shí)間：2019年06月04日 10:34:06 作者：老錢

這篇文章主要給大家介紹了關(guān)于Redis精確去重計(jì)數(shù)方法（咆哮位圖）的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用Redis具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

前言

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

那么有沒(méi)有一種不怎么浪費(fèi)空間的精確計(jì)數(shù)方法呢？我們首先想到的就是位圖，可以使用位圖的一個(gè)位來(lái)表示一個(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ù)的對(duì)應(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ì)提出疑問(wèn)，你說(shuō)是為了節(jié)省空間，這里存儲(chǔ)用戶id和整數(shù)的映射關(guān)系就不浪費(fèi)空間了么？這個(gè)問(wèn)題提的很好，但是同時(shí)我們也要看到這個(gè)映射關(guān)系是可以復(fù)用的，它可以統(tǒng)計(jì)所有文章的閱讀量，還可以統(tǒng)計(jì)簽到用戶的日活、月活，還可以用在很多其它的需要用戶去重的統(tǒng)計(jì)場(chǎng)合中。所謂「功在當(dāng)代，利在千秋」就是這個(gè)意思。

有了這個(gè)映射關(guān)系，我們就很容易構(gòu)造出每一篇文章的閱讀打點(diǎn)位圖，來(lái)一個(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ì)算等等都是可行的。

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

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

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

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

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

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

如果單個(gè)塊所有的位全是零，那么它就不需要存儲(chǔ)。具體某個(gè)塊是否存在也可以是用位圖來(lái)表達(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)變成普通位圖。

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

但是 Redis 并沒(méi)有原生支持咆哮位圖這個(gè)數(shù)據(jù)結(jié)構(gòu)??？我們?cè)撊绾问褂媚兀?br />

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

github.com/aviggiano/r…

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

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

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

下面我們來(lái)觀察一下源代碼看看它的內(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 字段來(lái)表示。

#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)部沒(méi)有 RUN 類型的塊。只有顯示調(diào)用了咆哮位圖的優(yōu)化 API 才會(huì)轉(zhuǎn)換成 RUN 格式，這個(gè) API 是 roaring_bitmap_run_optimize。

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

總結(jié)

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

您可能感興趣的文章: