一、背景

用戶在瀏覽游戲中心/應(yīng)用商店的某些模塊內(nèi)容時(shí)，會(huì)進(jìn)行一系列滑屏操作并多次請(qǐng)求游戲推薦業(yè)務(wù)來進(jìn)行游戲推薦展示，這段時(shí)間我們稱之為一個(gè)用戶session。

一個(gè)session內(nèi)用戶一般會(huì)進(jìn)行十幾次滑屏操作，每次滑屏操作都會(huì)請(qǐng)求推薦業(yè)務(wù)，所以在這個(gè)session內(nèi)游戲推薦需要對(duì)推薦過的游戲進(jìn)行去重，避免出現(xiàn)重復(fù)推薦同一款游戲影響用戶體驗(yàn)。

精簡(jiǎn)后的業(yè)務(wù)流程如下所示：用戶進(jìn)行滑屏操作時(shí)會(huì)觸發(fā)一次推薦請(qǐng)求，此時(shí)客戶端會(huì)將上一頁的黑名單游戲通過游戲中心服務(wù)端透?jìng)鹘o推薦系統(tǒng)，推薦系統(tǒng)將一個(gè)session內(nèi)每次請(qǐng)求的黑名單信息都累加存儲(chǔ)到Redis中作為一個(gè)總的過濾集合，在召回打分時(shí)就會(huì)過濾掉這些黑名單游戲。

以實(shí)際業(yè)務(wù)場(chǎng)景為例，用戶瀏覽某模塊的session時(shí)長一般不會(huì)超過10分鐘，模塊每頁顯示的游戲?yàn)?0個(gè)左右，假設(shè)每個(gè)用戶session內(nèi)會(huì)進(jìn)行15次的滑屏操作，那么一個(gè)session就需要存儲(chǔ)300 個(gè)黑名單游戲的appId（整數(shù)型Id）。因此該業(yè)務(wù)場(chǎng)景就不適合持久化存儲(chǔ)，業(yè)務(wù)問題就可以歸結(jié)為如何使用一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)來緩存一系列整數(shù)集合以達(dá)到節(jié)省內(nèi)存開銷的目的。

二、技術(shù)選型分析

接下來我們隨機(jī)選取300個(gè)游戲的appId（[2945340, ....... , 2793501,3056389]）作為集合來分別實(shí)驗(yàn)分析intset，bloom filter，RoaringBitMap對(duì)存儲(chǔ)效果的影響。

2.1 intset

實(shí)驗(yàn)結(jié)果表明用 intset保存300個(gè)游戲集合，得到占用的空間大小為1.23KB。這是因?yàn)閷?duì)于300個(gè)整數(shù)型appId游戲，每個(gè)appId用4Byte的int32就能表示。根據(jù)intset的數(shù)據(jù)結(jié)構(gòu)，其開銷僅為encoding + length + 400 個(gè)int所占的空間。

typedef struct intset{
    unit32_t encoding;          // 編碼類型
    unit32_t length;            // 元素個(gè)數(shù)
    int8_t contents[];          // 元素存儲(chǔ)
} intset;

2.2 bloom filter

布隆過濾器底層使用的是bitmap，bitmap本身就是一個(gè)數(shù)組可以存儲(chǔ)整形數(shù)字，arr[N] = 1 表示數(shù)組里存儲(chǔ)了N這個(gè)數(shù)字。

bloom filter會(huì)先用hash函數(shù)對(duì)數(shù)據(jù)進(jìn)行計(jì)算，映射到bitmap相應(yīng)的位置，為減少碰撞（不同的數(shù)據(jù)可能會(huì)有相同的hash值），會(huì)使用多個(gè)hash算子對(duì)同一份數(shù)據(jù)進(jìn)行多次映射。在業(yè)務(wù)中我們假設(shè)線上有一萬個(gè)游戲，同時(shí)業(yè)務(wù)場(chǎng)景不允許出現(xiàn)誤判，那么誤差就必須控制在10^-5，通過bloom filter的計(jì)算工具h(yuǎn)ttps://hur.st/bloomfilter/?n=10000&p=1.0E-5&m=&k=得出，需要17個(gè)hash算子，且bitmap空間要達(dá)到29KB才能滿足業(yè)務(wù)需求，顯然這樣巨大的開銷并不是我們想要的結(jié)果。

2.3 RoaringBitMap

RoaringBitMap和bloom filter本質(zhì)上都是使用bitmap進(jìn)行存儲(chǔ)。但bloom filter 使用的是多個(gè)hash函數(shù)對(duì)存儲(chǔ)數(shù)據(jù)進(jìn)行映射存儲(chǔ)，如果兩個(gè)游戲appId經(jīng)過hash映射后得出的數(shù)據(jù)一致，則判定兩者重復(fù)，這中間有一定的誤判率，所以為滿足在該業(yè)務(wù)場(chǎng)景其空間開銷會(huì)非常的大。而RoaringBitMap是直接將元數(shù)據(jù)進(jìn)行存儲(chǔ)壓縮，其準(zhǔn)確率是100%的。

實(shí)驗(yàn)結(jié)果表明：RoaringBitMap對(duì)300個(gè)游戲集合的開銷僅為0.5KB，比直接用intset（1.23KB）還小，是該業(yè)務(wù)場(chǎng)景下的首選。所以下文我們來著重分析下RoaringBitMap為什么為如此高效。

2.3.1 數(shù)據(jù)結(jié)構(gòu)

每個(gè)RoaringBitMap中都包含一個(gè)RoaringArray，存儲(chǔ)了全部的數(shù)據(jù)，其結(jié)構(gòu)如下:

short[] keys;
Container[] values;
int sizer;

它的思路是將32位無符號(hào)整數(shù)按照高16位分桶（container），并做為key存儲(chǔ)到short[] keys中，最多能存儲(chǔ)2^16 = 65536 個(gè)桶（container）。存儲(chǔ)數(shù)據(jù)時(shí)按照數(shù)據(jù)的高16位找到container，再將低16位放入container中，也就是Container[] values。size則表示了當(dāng)前keys和values中有效數(shù)據(jù)的數(shù)量。為了方便理解，下圖展示了三個(gè)container：

圖片引用自： https://arxiv.org

• 高16位為0000H的container，存儲(chǔ)有前1000個(gè)62的倍數(shù)。
• 高16位為0001H的container，存儲(chǔ)有[2^16, 2^16+100)區(qū)間內(nèi)的100個(gè)數(shù)。
• 高16位為0002H的container，存儲(chǔ)有[2×2^16, 3×2^16)區(qū)間內(nèi)的所有偶數(shù)，共215個(gè)。

當(dāng)然該數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)不是我們關(guān)注的重點(diǎn)，有興趣的同學(xué)可以去查閱相關(guān)資料學(xué)習(xí)?，F(xiàn)在我們來分析一下在推薦業(yè)務(wù)中RoaringBitMap是如何幫助我們節(jié)省開銷的。RoaringBitMap中的container分為ArrayContainer，BitmapContainer 和 RunContainer 但其壓縮方式主要分為兩種，姑且就稱為可變長度壓縮和固定長度壓縮, 這兩種方式在不同的場(chǎng)景下有不同的應(yīng)用。

2.3.2 壓縮方式與思考

假設(shè)兩串?dāng)?shù)字集合 [112,113,114,115,116,117,118 ], [112, 115, 116, 117, 120, 121]使用可變長度壓縮可以記錄為：

• 112,1,1,1,1,1,1 使用的字節(jié)大小為 7bit + 6bit = 13bit, 壓縮率為 (7 * 32 bit) / 13 bit = 17.23
• 112,3,1,1,3,1 使用的字節(jié)大小為 7bit + 2bit + 1bit + 1bit + 2bit + 1bit = 14bit, 壓縮率為（6 * 32bit）/ 14 = 13.7

使用固定長度壓縮可以記錄為：

• 112, 6，使用的字節(jié)大小為 7bit + 3bit = 10bit , 壓縮率為（7 * 32bit）/ 10bit = 22.4
• 112, 115, 3, 120,2 使用的字節(jié)大小為 7bit + 7bit + 2bit + 7bit + 2bit = 25bit，壓縮率為（6 * 32bit）/ 25 = 7.68

顯然稀疏排列對(duì)于兩種壓縮方式都有影響，可變長度壓縮適合于稀疏分布的數(shù)字集合，固定長度壓縮合于連續(xù)分布的數(shù)字集合。但在過于稀疏的情況下，即使是可變長度壓縮方式也不好使。

假設(shè)集合存儲(chǔ)范圍是Interger.MaxValue，現(xiàn)在要存儲(chǔ)數(shù)字集合是[ 2^3 - 1 , 2^9 - 1 , 2^15 -1 , 2^25 - 1 , 2^25 , 2^30 -1 ]這6個(gè)數(shù)。使用可變長壓縮方式表示為： 2^3 -1 , 2^9 - 2^3 , 2^15 - 2^9 , 2^25 - 2^15 , 1 , 2^30 - 2^ 15 使用字節(jié)大小 3bit + 9bit +15bit + 25bit + 1bit + 30bit = 83bit, 壓縮率為 6 * 32 bit / 83 = 2.3。

這個(gè)壓縮率和固定長度壓縮方式無異，均為極限情況下對(duì)低位整數(shù)進(jìn)行壓縮，無法利用偏移量壓縮來提高壓縮效率。

2.3.3 業(yè)務(wù)分析

更為極端的情下對(duì)于數(shù)據(jù)集合[ 2^25 - 1 , 2^26 - 1 , 2^27 - 1 , 2^28 - 1 , 2^29 - 1 , 2^30 - 1 ], RoaringBitMap壓縮后只能做到 25 + 26 + 27 + 28 + 29 + 30 = 165bit, 壓縮率為 6 * 32 / 165 = 1.16 就更別說加上組件數(shù)據(jù)結(jié)構(gòu)，位數(shù)對(duì)齊，結(jié)構(gòu)體消耗，指針大小等開銷了。在特別稀疏的情況下，用RoaringBitMap效果可能還更差。

但對(duì)于游戲業(yè)務(wù)來說游戲總量就10000多款，其標(biāo)識(shí)appId一般都是自增主鍵，隨機(jī)性很小，分布不會(huì)特別稀疏，理論上是可以對(duì)數(shù)據(jù)有個(gè)很好的壓縮。同時(shí)使用RoaringBitMap存儲(chǔ)Redis本身采用的bit，不太受Redis本身數(shù)據(jù)結(jié)構(gòu)的影響，能省下不少額外的空間。

三、總結(jié)

在文章中我們探討了在過濾去重的業(yè)務(wù)中，使用Redis存儲(chǔ)的情況下，利用intset，bloom filter 和 RoaringBitMap這三種數(shù)據(jù)結(jié)構(gòu)保存整數(shù)型集合的開銷。

其中傳統(tǒng)的bloom filter 方式由于對(duì)準(zhǔn)確率的要求以及短id映射空間節(jié)省有限的不足，使得該結(jié)構(gòu)在游戲推薦場(chǎng)景中反而增加了存儲(chǔ)開銷，不適合在該業(yè)務(wù)場(chǎng)景下存儲(chǔ)數(shù)據(jù)。而intset結(jié)構(gòu)雖然能滿足業(yè)務(wù)需求，但其使用的空間復(fù)雜度并不是最優(yōu)的，還有優(yōu)化的空間。

最終我們選擇了RoaringBitMap這個(gè)結(jié)構(gòu)進(jìn)行存儲(chǔ)，這是因?yàn)橛螒蛲扑]業(yè)務(wù)保存的過濾集合中，游戲id在大趨勢(shì)上是自增整數(shù)型的，且排列不是十分稀疏，利用RoaringBitMap的壓縮特性能很好的節(jié)省空間開銷。我們隨機(jī)抽選300個(gè)游戲的id集合進(jìn)行測(cè)試，結(jié)合表格可以看到，相比于intset結(jié)構(gòu)使用的1.23KB空間，RoaringBitMap僅使用0.5KB的大小，壓縮率為2.4。

對(duì)于Redis這種基于內(nèi)存的數(shù)據(jù)庫來說，使用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)提升存儲(chǔ)效率其收益是巨大的：不僅大大節(jié)約了硬件成本，同時(shí)減少了fork阻塞線程與單次調(diào)用的時(shí)延，對(duì)系統(tǒng)性能的提升是十分顯著的，因此在該場(chǎng)景下使用RoaringBitMap是十分合適的。