一、背景

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

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

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

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

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

接下來我們隨機選取300個游戲的appId（[2945340, ....... , 2793501,3056389]）作為集合來分別實驗分析intset，bloom filter，RoaringBitMap對存儲效果的影響。

2.1 intset

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

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

2.2 bloom filter

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

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

2.3 RoaringBitMap

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

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

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

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

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

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

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

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

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

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

假設(shè)集合存儲范圍是Interger.MaxValue，現(xiàn)在要存儲數(shù)字集合是[ 2^3 - 1 , 2^9 - 1 , 2^15 -1 , 2^25 - 1 , 2^25 , 2^30 -1 ]這6個數(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。

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

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

更為極端的情下對于數(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ù)對齊，結(jié)構(gòu)體消耗，指針大小等開銷了。在特別稀疏的情況下，用RoaringBitMap效果可能還更差。

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

三、總結(jié)

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

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

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

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