作者：vivo網際網路技術-Ke Jiachen

一、背景

使用者在瀏覽遊戲中心/應用商店的某些模組內容時，會進行一系列滑屏操作並多次請求遊戲推薦業務來進行遊戲推薦展示，這段時間我們稱之為一個使用者session。

一個session內使用者一般會進行十幾次滑屏操作，每次滑屏操作都會請求推薦業務，所以在這個session內遊戲推薦需要對推薦過的遊戲進行去重，避免出現重複推薦同一款遊戲影響使用者體驗。

精簡後的業務流程如下所示：使用者進行滑屏操作時會觸發一次推薦請求，此時客戶端會將上一頁的黑名單遊戲通過遊戲中心服務端透傳給推薦系統，推薦系統將一個session內每次請求的黑名單資訊都累加儲存到Redis中作為一個總的過濾集合，在召回打分時就會過濾掉這些黑名單遊戲。

以實際業務場景為例，使用者瀏覽某模組的session時長一般不會超過10分鐘，模組每頁顯示的遊戲為20個左右，假設每個使用者session內會進行15次的滑屏操作，那麼一個session就需要儲存300 個黑名單遊戲的appId（整數型Id）。因此該業務場景就不適合持久化儲存，業務問題就可以歸結為如何使用一個合適的資料結構來快取一系列整數集合以達到節省記憶體開銷的目的。

二、技術選型分析

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

2.1 intset

實驗結果表明用 intset儲存300個遊戲集合，得到佔用的空間大小為1.23KB。這是因為對於300個整數型appId遊戲，每個appId用4Byte的int32就能表示。根據intset的資料結構，其開銷僅為encoding + length + 400 個int所佔的空間。

typedef struct intset{
    unit32_t encoding;          // 編碼型別
    unit32_t length;            // 元素個數
    int8_t contents[];          // 元素儲存
} intset;

2.2 bloom filter

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

bloom filter會先用hash函式對資料進行計算，對映到bitmap相應的位置，為減少碰撞（不同的資料可能會有相同的hash值），會使用多個hash運算元對同一份資料進行多次對映。在業務中我們假設線上有一萬個遊戲，同時業務場景不允許出現誤判，那麼誤差就必須控制在10^-5，通過bloom filter的計算工具http://hur.st/bloomfilter/?n=10000&p=1.0E-5&m=&k=得出，需要17個hash運算元，且bitmap空間要達到29KB才能滿足業務需求，顯然這樣巨大的開銷並不是我們想要的結果。

2.3 RoaringBitMap

RoaringBitMap和bloom filter本質上都是使用bitmap進行儲存。但bloom filter 使用的是多個hash函式對儲存資料進行對映儲存，如果兩個遊戲appId經過hash對映後得出的資料一致，則判定兩者重複，這中間有一定的誤判率，所以為滿足在該業務場景其空間開銷會非常的大。而RoaringBitMap是直接將元資料進行儲存壓縮，其準確率是100%的。

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

2.3.1 資料結構

每個RoaringBitMap中都包含一個RoaringArray，儲存了全部的資料，其結構如下:

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

它的思路是將32位無符號整數按照高16位分桶（container），並做為key儲存到short[] keys中，最多能儲存2^16 = 65536 個桶（container）。儲存資料時按照資料的高16位找到container，再將低16位放入container中，也就是Container[] values。size則表示了當前keys和values中有效資料的數量。

為了方便理解，下圖展示了三個container：

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

• 高16位為0000H的container，儲存有前1000個62的倍數。

• 高16位為0001H的container，儲存有[2^16, 2^16+100)區間內的100個數。

• 高16位為0002H的container，儲存有[2×2^16, 3×2^16)區間內的所有偶數，共215個。

當然該資料結構的細節不是我們關注的重點，有興趣的同學可以去查閱相關資料學習。現在我們來分析一下在推薦業務中RoaringBitMap是如何幫助我們節省開銷的。RoaringBitMap中的container分為ArrayContainer，BitmapContainer 和 RunContainer 但其壓縮方式主要分為兩種，姑且就稱為可變長度壓縮和固定長度壓縮, 這兩種方式在不同的場景下有不同的應用。

2.3.2 壓縮方式與思考

假設兩串數字集合 [112,113,114,115,116,117,118 ], [112, 115, 116, 117, 120, 121]

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

• 112,1,1,1,1,1,1 使用的位元組大小為 7bit + 6bit = 13bit, 壓縮率為 (7 * 32 bit) / 13 bit = 17.23

• 112,3,1,1,3,1 使用的位元組大小為 7bit + 2bit + 1bit + 1bit + 2bit + 1bit = 14bit, 壓縮率為（6 * 32bit）/ 14 = 13.7

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

• 112, 6，使用的位元組大小為 7bit + 3bit = 10bit , 壓縮率為（7 * 32bit）/ 10bit = 22.4

• 112, 115, 3, 120,2 使用的位元組大小為 7bit + 7bit + 2bit + 7bit + 2bit = 25bit，壓縮率為（6 * 32bit）/ 25 = 7.68

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

假設集合儲存範圍是Interger.MaxValue，現在要儲存數字集合是[2^3 - 1, 2^9 - 1, 2^15 -1, 2^25 - 1, 2^25 , 2^30 -1]這6個數。使用可變長壓縮方式表示為：2^3 -1, 2^9 - 2^3, 2^15 - 2^9, 2^25 - 2^15, 1, 2^30 - 2^ 15 使用位元組大小 3bit + 9bit +15bit + 25bit + 1bit + 30bit = 83bit, 壓縮率為 6 * 32 bit / 83 = 2.3。

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

2.3.3 業務分析

更為極端的情下對於資料集合[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 就更別說加上元件資料結構，位數對齊，結構體消耗，指標大小等開銷了。在特別稀疏的情況下，用RoaringBitMap效果可能還更差。

但對於遊戲業務來說遊戲總量就10000多款，其標識appId一般都是自增主鍵，隨機性很小，分佈不會特別稀疏，理論上是可以對資料有個很好的壓縮。同時使用RoaringBitMap儲存Redis本身採用的bit，不太受Redis本身資料結構的影響，能省下不少額外的空間。

三、總結

在文章中我們探討了在過濾去重的業務中，使用Redis儲存的情況下，利用intset，bloom filter 和 RoaringBitMap這三種資料結構儲存整數型集合的開銷。

其中傳統的bloom filter 方式由於對準確率的要求以及短id對映空間節省有限的不足，使得該結構在遊戲推薦場景中反而增加了儲存開銷，不適合在該業務場景下儲存資料。而intset結構雖然能滿足業務需求，但其使用的空間複雜度並不是最優的，還有優化的空間。

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

對於Redis這種基於記憶體的資料庫來說，使用適當的資料結構提升儲存效率其收益是巨大的：不僅大大節約了硬體成本，同時減少了fork阻塞執行緒與單次呼叫的時延，對系統性能的提升是十分顯著的，因此在該場景下使用RoaringBitMap是十分合適的。