文｜Creed 得物技術(shù)

背景

目前鸦泳，在商品圈選投場(chǎng)景，每個(gè)標(biāo)簽id都會(huì)根據(jù)規(guī)則/指標(biāo)綁定一定數(shù)據(jù)量的商品集席赂，在圈選規(guī)則條件變動(dòng)或者定時(shí)任務(wù)觸發(fā)時(shí)會(huì)進(jìn)行商品集的刷新等缀，新增符合規(guī)則的商品，刪除不符合規(guī)則的商品臣嚣。

但是由于商品集下的spu數(shù)量大部分都在數(shù)十萬净刮，多的能達(dá)到上百萬，如果直接將刷新前后各十萬甚至百萬的spu全量放到內(nèi)存中互相做diff硅则，再對(duì)diff得到的差集做增刪淹父，當(dāng)同一時(shí)間刷新的標(biāo)簽數(shù)量過多時(shí)，內(nèi)存就很容易溢出怎虫，造成整個(gè)服務(wù)宕機(jī)暑认。

同時(shí)目前底層存儲(chǔ)商品集的數(shù)據(jù)庫(kù)為Hbase，因此在標(biāo)簽側(cè)對(duì)于商品集的刷新場(chǎng)景目前都是采取全增全刪的策略大审，即把刷新后的商品集先全量保存一次(利用Hbase 保存的冪等性蘸际，同一個(gè)rowkey的數(shù)據(jù)重復(fù)保存會(huì)進(jìn)行覆蓋，而不用在保存前做額外的數(shù)據(jù)是否存在的判斷)徒扶，并更新數(shù)據(jù)的modity_time=now()粮彤，然后再?gòu)腍base中分批scan遍歷商品集，找到modity_time<now的再進(jìn)行刪除，以此完成一次標(biāo)簽的刷新任務(wù)导坟。

往往一個(gè)商品集在刷新前后真正變化的spu量并不大屿良，通過取數(shù)分析得知變化的不會(huì)超過商品集數(shù)量的10%。而我們目前采用的這種全增全刪的策略惫周，每次刷新后都會(huì)有大量已有數(shù)據(jù)的重復(fù)插入尘惧，不僅延長(zhǎng)了刷新的速度，也增加底層儲(chǔ)存的壓力闯两，同時(shí)由于選投平臺(tái)里有標(biāo)簽的指標(biāo)褥伴，標(biāo)簽的變動(dòng)需要推送變化的spu給選投平臺(tái)進(jìn)行重新圈品，同時(shí)spu es 中也存有標(biāo)簽的數(shù)據(jù)用于后臺(tái)展示漾狼，所以當(dāng)前全增全刪的策略重慢，尤其是大量已有數(shù)據(jù)的重復(fù)插入，都會(huì)同步到選投平臺(tái)和spu es側(cè)逊躁，對(duì)他們?cè)斐纱罅康男阅芾速M(fèi)和處理成本似踱，改造迫在眉睫。

優(yōu)化方案

前面提到稽煤，由于傳統(tǒng)的java Set結(jié)構(gòu)在數(shù)據(jù)量較大的情況核芽，占用內(nèi)存較多，導(dǎo)致無法將前后海量商品集的數(shù)據(jù)全部存到內(nèi)存中去做運(yùn)算酵熙。

那么有沒有一個(gè)數(shù)據(jù)結(jié)構(gòu)可以在存海量數(shù)據(jù)時(shí)還能保持較低的內(nèi)存占用轧简，支持去重，還支持交集匾二，差集等各種運(yùn)算呢?

Bitmap完美滿足要求哮独。

Bitmap是通過bit數(shù)組來存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，是一串連續(xù)的二進(jìn)制數(shù)組（0和1）察藐，可以通過偏移量（offset）定位元素皮璧。Bitmap通過最小的單位bit來進(jìn)行0|1的設(shè)置，表示某個(gè)元素的值或者狀態(tài)分飞，時(shí)間復(fù)雜度為O(1)铲敛。

同時(shí)由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)叮叹，因此在存儲(chǔ)空間方面，可以大大節(jié)省绷旗。例如儲(chǔ)存500W數(shù)據(jù)僅需5000000/8/1024/1024=0.5M內(nèi)存掸读。

因此準(zhǔn)備使用Bitmap結(jié)構(gòu)來存儲(chǔ)刷新前后的商品集咆疗，然后分別對(duì)新老Bitmap互相求差集得到舟误，最終對(duì)差集進(jìn)行add和delete操作即可颠毙。

方案可行性分析

以標(biāo)簽場(chǎng)景為例。

標(biāo)簽可以綁定選投平臺(tái)肌索，標(biāo)簽系統(tǒng)會(huì)把選投平臺(tái)圈選的所有商品集都打上標(biāo)，此刻標(biāo)簽下的商品集記為oldSset(X+Y)。

選投平臺(tái)刷新后诚亚，會(huì)重新圈選出一批滿足選投平臺(tái)指標(biāo)的商品集晕换，此時(shí)選投平臺(tái)下的商品集記為newSet(Y+Z) 。

此時(shí)標(biāo)簽系統(tǒng)需要給newSet(Y+Z)打標(biāo)站宗，同時(shí)從oldSet(X+Y)刪除不在本次圈選范圍內(nèi)的商品(X)闸准。

image.png

image.png

標(biāo)簽商品集底層儲(chǔ)存是Hbase，對(duì)于已存在數(shù)據(jù)的插入梢灭，只要rowkey(標(biāo)簽id+spuId)不變夷家， Hbase就會(huì)進(jìn)行覆蓋，保存最新時(shí)間戳的數(shù)據(jù)敏释，可以理解為老Y已經(jīng)被新Y覆蓋(老Y數(shù)據(jù)=新Y數(shù)據(jù),只是時(shí)間戳?xí)灰粯?库快，所以老全增全刪的方案， 刪除量級(jí)是X钥顽，而不是X+Y义屏。

如上圖所示，每次刷新后蜂大，其實(shí)只需要對(duì)X進(jìn)行刪除和對(duì)Z進(jìn)行新增闽铐。

相比于老全增全刪邏輯，Bitmap diff新方案查詢和刪除量級(jí)不變奶浦，新增量級(jí)和對(duì)選投平臺(tái)兄墅，spu es 的通知量級(jí)，都減少了Y澳叉。

同時(shí)由于Bitmap本身儲(chǔ)存數(shù)據(jù)的方式隙咸，儲(chǔ)存500W的spu數(shù)據(jù)集對(duì)內(nèi)存的占用也才在0.5M,完成不用擔(dān)心內(nèi)存溢出風(fēng)險(xiǎn)。

因此采用Bitmap來儲(chǔ)存刷新前后的全量商品數(shù)據(jù)耳高，并在內(nèi)存中做diff是一個(gè)理論可行的方案扎瓶。

技術(shù)選型

既然我們選定了使用Bitmap作為新方案的儲(chǔ)存，那么應(yīng)該選取哪種Bitmap實(shí)現(xiàn)呢?

眾所周知泌枪，Bitmap的實(shí)現(xiàn)有很多概荷，例如java原生的BitSet，guava的EWAHCompressedBitmap碌燕，第三方的RoaingBitmap误证，redis Bitmap等等，由于redis的Bitmap主要做遠(yuǎn)程儲(chǔ)存不適合當(dāng)前內(nèi)存diff場(chǎng)景修壕，因此排除愈捅。

本次主要對(duì)比BitSet、EWAHCompressedBitmap慈鸠、RoaingBitmap三種實(shí)現(xiàn)在各種數(shù)據(jù)稀疏度下的內(nèi)存占用和cpu占用蓝谨，以選出最滿足當(dāng)前場(chǎng)景的實(shí)現(xiàn)。

內(nèi)存占用測(cè)試

通過往Bitmap中添加1、N+1譬巫、2N+1.....5000000數(shù)據(jù)咖楣，其中N為數(shù)據(jù)的步長(zhǎng)(稀疏度) 來計(jì)算各個(gè)Bitmap在不同稀疏度下(N)的內(nèi)存占用情況。

通過下圖可以看出芦昔，除了在稀疏度為1時(shí)诱贿，EWAHCompressedBitmap內(nèi)存占用最低以外，其余稀疏度下的內(nèi)存占用：RoaingBitmap<EWAHCompressedBitmap<BitSet咕缎。

image.png

cpu耗時(shí)測(cè)試

往各個(gè)Bitmap中添加1珠十、N+1、2N+1.....5000000數(shù)據(jù)凭豪，其中N為數(shù)據(jù)的步長(zhǎng)(稀疏度)焙蹭，然后與有5000000滿數(shù)據(jù)的Bitmap分別求2000次差集并取2000次中的最大耗時(shí)，得到在每個(gè)稀疏度下每種Bitmap的耗時(shí)情況墅诡。

通過下圖可以看出壳嚎，各個(gè)稀疏度下的cpu耗時(shí)：RoaingBitmap≈EWAHCompressedBitmap<BitSet.

image.png

選型最終結(jié)論

從內(nèi)存占用，cpu耗時(shí)測(cè)試末早，實(shí)際場(chǎng)景下數(shù)據(jù)稀疏度綜合考慮烟馅，RoaingBitmap效果最優(yōu)，因此選用RoaingBitmap作為新方案的Bitmap實(shí)現(xiàn)然磷。

RoaingBitmap介紹及原理

RoaingBitmap儲(chǔ)存原理

RoaingBitmap會(huì)將32 bit unsigned int 類型數(shù)據(jù) 劃分為 2^16 個(gè)大Container（即使用數(shù)據(jù)的前16位二進(jìn)制作為Container的編號(hào)）郑趁，每個(gè)大Container有一個(gè)小Container 來存放一個(gè)數(shù)值的低16位。

在存儲(chǔ)和查詢數(shù)值時(shí)姿搜，將數(shù)值 k 劃分為高 16 位和低 16 位寡润，取高 16 位值找到對(duì)應(yīng)的Container，然后在將低 16 位值存放在相應(yīng)的 Container 中舅柜。

這樣說可能比較抽象不易理解梭纹，下面我通過一個(gè)例子來說明。

比如我們要將31這個(gè)數(shù)放進(jìn)RoarigBitmap中致份，它的16進(jìn)制為：0000 001F变抽，前16位為0000，后16為001F氮块。所以我們先需要根據(jù)前16位的值：0绍载，找到它對(duì)應(yīng)的的Container編號(hào)為0，然后根據(jù)后16位的值：31滔蝉，確定這個(gè)值應(yīng)該放到Container中的哪一個(gè)位置击儡，如下圖所示。

image.png

需要注意大Container里面的各個(gè)小Container是在需要的時(shí)候才會(huì)申請(qǐng)開辟的蝠引，并不是一開始就全部申請(qǐng)的阳谍，而且大Container中小Container都是按序號(hào)有序排列在大Container里面的蛀柴。

四種container介紹

為了在各種場(chǎng)景和稀疏度下都始終保持有良好的內(nèi)存占用和性能表現(xiàn)，RoaingBitmap 特意設(shè)計(jì)了4種小Container边坤，分別為ArrayContainer(數(shù)組容器)名扛，BitmapContainer(位圖容器)，Runcontainer(行程步長(zhǎng)容器)茧痒，Sharedcontainer(共享容器)，下面我會(huì)對(duì)每個(gè)ArrayContainer的使用場(chǎng)景和原理進(jìn)行介紹融蹂。

• Arraycontiner

在創(chuàng)建一個(gè)新container時(shí)旺订，如果只插入一個(gè)元素，RBM（RoaingBitmap）默認(rèn)會(huì)用ArrayContainer來存儲(chǔ)超燃。當(dāng)ArrayContainer（其中每一個(gè)元素的類型為 short 占兩個(gè)字節(jié)区拳，且里面的元素都是按從小到大的順序排列的）的容量超過4096（這里是指4096個(gè)short 即8k）后，會(huì)自動(dòng)轉(zhuǎn)成BitmapContainer(這個(gè)所占空間始終都是8k)存儲(chǔ)意乓。4096這個(gè)閾值很聰明樱调，低于它時(shí)ArrayContainer比較省空間，高于它時(shí)BitmapContainer比較省空間届良。也就是說ArrayContainer存儲(chǔ)稀疏數(shù)據(jù)笆凌，BitmapContainer存儲(chǔ)稠密數(shù)據(jù)，可以最大限度地避免內(nèi)存浪費(fèi)士葫，如下圖所示乞而。

image.png

• BitmapContainer

這個(gè)容器其實(shí)就是我們所說的位圖，只不過這里位圖的位數(shù)為65536個(gè)慢显，也就是2^16個(gè)bit爪模，計(jì)算下來起所占內(nèi)存就是8kb。然后每一位用0荚藻，1表示這個(gè)數(shù)不存在或者存在屋灌，如下圖所示：

image.png

• Runcontainer

這是一種利用步長(zhǎng)來壓縮空間的方法

我們舉個(gè)例子：比如連續(xù)的整數(shù)序列 11， 12应狱， 13共郭， 14， 15侦香， 27落塑， 28， 29 會(huì)被 壓縮為兩個(gè)二元組 11罐韩， 4憾赁， 27， 2 表示：11后面緊跟著4個(gè)連續(xù)遞增的值散吵，27后面跟著2個(gè)連續(xù)遞增的值龙考，那么原先16個(gè)字節(jié)的空間蟆肆，現(xiàn)在只需要8個(gè)字節(jié)，是不是節(jié)省了很多空間呢晦款。不過這種容器不常用炎功，所以在使用的時(shí)候需要我們自行調(diào)用相關(guān)的轉(zhuǎn)換函數(shù)來判斷是不是需要將arraycontiner，或BitmapContainer轉(zhuǎn)換為Runcontainer缓溅。

• Sharedcontainer

這種容器它本身是不存儲(chǔ)數(shù)據(jù)的蛇损，只是用它來指向ArrayContainer，BitmapContainer或Runcontainer坛怪，就好比指針的作用一樣淤齐，這個(gè)指針可以被多個(gè)對(duì)象擁有，但是指針?biāo)羔樀膶?shí)質(zhì)東西是被這多個(gè)對(duì)象所共享的袜匿。在我們進(jìn)行RoaingBitmap之間的拷貝的時(shí)候更啄，有時(shí)并不需要將一個(gè)container拷貝多份，那么我們就可以使用Sharedcontainer來指向?qū)嶋H的container居灯，然后把Sharedcontainer賦給多個(gè)RoaingBitmap對(duì)象持有祭务，這個(gè)RoaingBitmap對(duì)象就可以根據(jù)Sharedcontainer找到真正存儲(chǔ)數(shù)據(jù)的container，這可以省去不必要的空間浪費(fèi)怪嫌。

這些container之間的關(guān)系可以用下面這幅圖來表示：

其中的roaring_array是RoaingBitmap對(duì)象义锥，而途中的Sharedcontainer則表示被多個(gè)roaring_array里面的小Container共享。

image.png

RoaingBitmap優(yōu)勢(shì)

• 內(nèi)存

Bitmap比較適用于數(shù)據(jù)分布比較稠密的存儲(chǔ)場(chǎng)景中喇勋，對(duì)于原始的Bitmap來說缨该，若要存儲(chǔ)一個(gè)uint32類型數(shù)據(jù)，這就需要2 ^ 32長(zhǎng)度的bit數(shù)組川背，通過計(jì)算可以發(fā)現(xiàn)(2 ^ 32 / 8 bytes = 512MB)贰拿，一個(gè)普通的Bitmap需要耗費(fèi)512MB的存儲(chǔ)空間。如果我們只存儲(chǔ)幾個(gè)數(shù)據(jù)的話依然需要占用512M的話熄云，就有些浪費(fèi)空間了膨更，因此我們可以采用對(duì)位圖進(jìn)行壓縮的RoaingBitmap，以此減少內(nèi)存和提高效率缴允。

• 性能

RoaingBitmap除了比Bitmap占用內(nèi)存少之外荚守，其并集和交集操作的速度也要比Bitmap的快。原因歸結(jié)為以下幾點(diǎn)：

• 計(jì)算上的優(yōu)化

對(duì)于RoaingBitmap本質(zhì)上是將大塊的Bitmap分成各個(gè)小塊练般，其中每個(gè)小塊在需要存儲(chǔ)數(shù)據(jù)的時(shí)候才會(huì)存在矗漾。所以當(dāng)進(jìn)行交集或并集運(yùn)算的時(shí)候，RoaingBitmap只需要去計(jì)算存在的一些塊而不需要像Bitmap那樣對(duì)整個(gè)大的塊進(jìn)行計(jì)算薄料。如果塊內(nèi)非常稀疏敞贡，那么只需要對(duì)這些小整數(shù)列表進(jìn)行集合的 AND、OR 運(yùn)算摄职，這樣的話計(jì)算量還能繼續(xù)減輕誊役。這里既不是用空間換時(shí)間获列，也沒有用時(shí)間換空間，而是用邏輯的復(fù)雜度同時(shí)換取了空間和時(shí)間蛔垢。

同時(shí)在RoaingBitmap中32位長(zhǎng)的數(shù)據(jù)击孩，被分割成高 16 位和低 16 位，高 16 位表示塊偏移鹏漆，低16位表示塊內(nèi)位置巩梢，單個(gè)塊可以表達(dá) 64k 的位長(zhǎng)，也就是 8K 字節(jié)艺玲。這樣可以保證單個(gè)塊都可以全部放入 L1 Cache且改，可以顯著提升性能。

• 程序邏輯上的優(yōu)化

1. RoaingBitmap維護(hù)了排好序的一級(jí)索引板驳，以及有序的ArrayContainer當(dāng)進(jìn)行交集操作的時(shí)候，只需要根據(jù)一級(jí)索引中對(duì)應(yīng)的值來獲取需要合并的容器碍拆，而不需要合并的容器則不需要對(duì)其進(jìn)行操作直接過濾掉若治。
2. 當(dāng)進(jìn)行合并的ArrayContainer中數(shù)據(jù)個(gè)數(shù)相差過大的時(shí)候采用基于二分查找的方法對(duì)ArrayContainer求交集，避免不必要的線性合并花費(fèi)的時(shí)間開銷感混。
3. RoaingBitmap在做并集的時(shí)候同樣根據(jù)一級(jí)索引只對(duì)相同的索引的容器進(jìn)行合并操作端幼，而索引不同的直接添加到新的RoaingBitmap上即可，不需要遍歷容器弧满。
4. RoaingBitmap在合并容器的時(shí)候會(huì)先預(yù)測(cè)結(jié)果婆跑，生成對(duì)應(yīng)的容器，避免不必要的容器轉(zhuǎn)換操作

show me the code

代碼邏輯其實(shí)相對(duì)簡(jiǎn)單庭呜，主要是構(gòu)建新老Bitmap滑进，互相求差集后對(duì)本次新增的spu進(jìn)行新增，對(duì)本次需要?jiǎng)h除的spu進(jìn)行刪除操作募谎。

image.png

優(yōu)化效果

刷新速度

統(tǒng)計(jì)全量標(biāo)簽在新老邏輯下的耗時(shí),發(fā)現(xiàn)提升比例大部分都集中在40%-60%區(qū)間扶关，去掉最高及最低值

得出最終結(jié)論為平均提升比例在52.42%

image.png

image.png

寫入量級(jí)以及對(duì)其他場(chǎng)景影響

統(tǒng)計(jì)全量標(biāo)簽在新老邏輯下的寫量級(jí),發(fā)現(xiàn)提升比例大部分都集中在85%-99%區(qū)間，去掉最高及最低值

得出最終結(jié)論為平均提升比例在86.98%

image.png

image.png

總結(jié)

由于java的Set結(jié)構(gòu)在大數(shù)據(jù)量下的內(nèi)存占用很高数冬，因此在圈選商品集的刷新場(chǎng)景無法直接在內(nèi)存中用set去全量?jī)?chǔ)存刷新前后的商品集并做差集運(yùn)算节槐。

因此考慮到了使用Bitmap這樣一種通過bit數(shù)組來存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，它采用了Bit為單位來存儲(chǔ)數(shù)據(jù)拐纱，因此在存儲(chǔ)空間方面铜异，可以大大節(jié)省。

對(duì)比了業(yè)界了各種Bitmap實(shí)現(xiàn)秸架，結(jié)合當(dāng)前場(chǎng)景揍庄，最終采用了RoaingBitmap來作為最終的實(shí)現(xiàn)。

RoaingBitmap屬于是位圖的一個(gè)進(jìn)化咕宿，即壓縮位圖币绩，不過在RoaingBitmap中不只包含Bitmap這一種數(shù)據(jù)結(jié)構(gòu)蜡秽，而是包涵了多種存儲(chǔ)的方式(contianer)，同時(shí)通過計(jì)算及邏輯上的優(yōu)化缆镣，保證了在各個(gè)稀疏度下相比于傳統(tǒng)的Bitmap都能保持較低的內(nèi)存占用和對(duì)比速度芽突。

最終上線后優(yōu)化效果也是比較不錯(cuò)，刷新速度提升在52%左右董瞻，寫入量級(jí)平均降低87%寞蚌，有效的提升了刷新速度，以及對(duì)儲(chǔ)存DB及其他場(chǎng)景域的壓力钠糊。

同時(shí)本方案也適用其他類似的場(chǎng)景挟秤，比如選投平臺(tái)側(cè)的刷新，綁定選投平臺(tái)的主題集下的商品刷新等抄伍。

參考文檔：

1. RoaingBitmap 官方github地址
2. 使用Apache ECharts完成優(yōu)化效果圖繪制

*文/Creed

關(guān)注得物技術(shù)艘刚，每周一三五晚18:30更新技術(shù)干貨
要是覺得文章對(duì)你有幫助的話，歡迎評(píng)論轉(zhuǎn)發(fā)點(diǎn)贊～