建站
咨詢
售后
建站咨詢
新聞中心
一、背景
用戶在瀏覽游戲中心/應用商店的某些模塊內(nèi)容時，會進行一系列滑屏操作并多次請求游戲推薦業(yè)務來進行游戲推薦展示，這段時間我們稱之為一個用戶session。
創(chuàng)新互聯(lián)長期為上千家客戶提供的網(wǎng)站建設服務，團隊從業(yè)經(jīng)驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為響水企業(yè)提供專業(yè)的成都做網(wǎng)站、網(wǎng)站建設，響水網(wǎng)站改版等技術服務。擁有10多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。
一個session內(nèi)用戶一般會進行十幾次滑屏操作，每次滑屏操作都會請求推薦業(yè)務，所以在這個session內(nèi)游戲推薦需要對推薦過的游戲進行去重，避免出現(xiàn)重復推薦同一款游戲影響用戶體驗。
精簡后的業(yè)務流程如下所示：用戶進行滑屏操作時會觸發(fā)一次推薦請求，此時客戶端會將上一頁的黑名單游戲通過游戲中心服務端透傳給推薦系統(tǒng)，推薦系統(tǒng)將一個session內(nèi)每次請求的黑名單信息都累加存儲到Redis中作為一個總的過濾集合，在召回打分時就會過濾掉這些黑名單游戲。
以實際業(yè)務場景為例，用戶瀏覽某模塊的session時長一般不會超過10分鐘，模塊每頁顯示的游戲為20個左右，假設每個用戶session內(nèi)會進行15次的滑屏操作，那么一個session就需要存儲300 個黑名單游戲的appId（整數(shù)型Id）。因此該業(yè)務場景就不適合持久化存儲，業(yè)務問題就可以歸結為如何使用一個合適的數(shù)據(jù)結構來緩存一系列整數(shù)集合以達到節(jié)省內(nèi)存開銷的目的。
二、技術選型分析
接下來我們隨機選取300個游戲的appId（[2945340, ....... , 2793501,3056389]）作為集合來分別實驗分析intset，bloom filter，RoaringBitMap對存儲效果的影響。
2.1 intset
實驗結果表明用 intset保存300個游戲集合，得到占用的空間大小為1.23KB。這是因為對于300個整數(shù)型appId游戲，每個appId用4Byte的int32就能表示。根據(jù)intset的數(shù)據(jù)結構，其開銷僅為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相應的位置，為減少碰撞（不同的數(shù)據(jù)可能會有相同的hash值），會使用多個hash算子對同一份數(shù)據(jù)進行多次映射。在業(yè)務中我們假設線上有一萬個游戲，同時業(yè)務場景不允許出現(xiàn)誤判，那么誤差就必須控制在10^-5，通過bloom filter的計算工具https://hur.st/bloomfilter/?n=10000&p=1.0E-5&m=&k=得出，需要17個hash算子，且bitmap空間要達到29KB才能滿足業(yè)務需求，顯然這樣巨大的開銷并不是我們想要的結果。
2.3 RoaringBitMap
RoaringBitMap和bloom filter本質(zhì)上都是使用bitmap進行存儲。但bloom filter 使用的是多個hash函數(shù)對存儲數(shù)據(jù)進行映射存儲，如果兩個游戲appId經(jīng)過hash映射后得出的數(shù)據(jù)一致，則判定兩者重復，這中間有一定的誤判率，所以為滿足在該業(yè)務場景其空間開銷會非常的大。而RoaringBitMap是直接將元數(shù)據(jù)進行存儲壓縮，其準確率是100%的。
實驗結果表明：RoaringBitMap對300個游戲集合的開銷僅為0.5KB，比直接用intset（1.23KB）還小，是該業(yè)務場景下的首選。所以下文我們來著重分析下RoaringBitMap為什么為如此高效。
2.3.1 數(shù)據(jù)結構
每個RoaringBitMap中都包含一個RoaringArray，存儲了全部的數(shù)據(jù)，其結構如下:
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則表示了當前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個。
當然該數(shù)據(jù)結構的細節(jié)不是我們關注的重點，有興趣的同學可以去查閱相關資料學習。現(xiàn)在我們來分析一下在推薦業(yè)務中RoaringBitMap是如何幫助我們節(jié)省開銷的。RoaringBitMap中的container分為ArrayContainer，BitmapContainer 和 RunContainer 但其壓縮方式主要分為兩種，姑且就稱為可變長度壓縮和固定長度壓縮, 這兩種方式在不同的場景下有不同的應用。
2.3.2 壓縮方式與思考
假設兩串數(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ù)字集合。但在過于稀疏的情況下，即使是可變長度壓縮方式也不好使。
假設集合存儲范圍是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è)務分析
更為極端的情下對于數(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ù)結構，位數(shù)對齊，結構體消耗，指針大小等開銷了。在特別稀疏的情況下，用RoaringBitMap效果可能還更差。
但對于游戲業(yè)務來說游戲總量就10000多款，其標識appId一般都是自增主鍵，隨機性很小，分布不會特別稀疏，理論上是可以對數(shù)據(jù)有個很好的壓縮。同時使用RoaringBitMap存儲Redis本身采用的bit，不太受Redis本身數(shù)據(jù)結構的影響，能省下不少額外的空間。
三、總結
在文章中我們探討了在過濾去重的業(yè)務中，使用Redis存儲的情況下，利用intset，bloom filter 和 RoaringBitMap這三種數(shù)據(jù)結構保存整數(shù)型集合的開銷。
其中傳統(tǒng)的bloom filter 方式由于對準確率的要求以及短id映射空間節(jié)省有限的不足，使得該結構在游戲推薦場景中反而增加了存儲開銷，不適合在該業(yè)務場景下存儲數(shù)據(jù)。而intset結構雖然能滿足業(yè)務需求，但其使用的空間復雜度并不是最優(yōu)的，還有優(yōu)化的空間。
最終我們選擇了RoaringBitMap這個結構進行存儲，這是因為游戲推薦業(yè)務保存的過濾集合中，游戲id在大趨勢上是自增整數(shù)型的，且排列不是十分稀疏，利用RoaringBitMap的壓縮特性能很好的節(jié)省空間開銷。我們隨機抽選300個游戲的id集合進行測試，結合表格可以看到，相比于intset結構使用的1.23KB空間，RoaringBitMap僅使用0.5KB的大小，壓縮率為2.4。
對于Redis這種基于內(nèi)存的數(shù)據(jù)庫來說，使用適當?shù)臄?shù)據(jù)結構提升存儲效率其收益是巨大的：不僅大大節(jié)約了硬件成本，同時減少了fork阻塞線程與單次調(diào)用的時延，對系統(tǒng)性能的提升是十分顯著的，因此在該場景下使用RoaringBitMap是十分合適的。
網(wǎng)站名稱：高效壓縮位圖在推薦系統(tǒng)中的應用
鏈接URL：http://www.dlmjj.cn/article/cogcpgc.html
