原創 Creed 得物技術

背景

目前，在商品圈選投場景，每個標籤id都會根據規則/指標繫結一定資料量的商品集，在圈選規則條件變動或者定時任務觸發時會進行商品集的重新整理，新增符合規則的商品，刪除不符合規則的商品。

但是由於商品集下的spu數量大部分都在數十萬，多的能達到上百萬，如果直接將重新整理前後各十萬甚至百萬的spu全量放到記憶體中互相做diff，再對diff得到的差集做增刪，當同一時間重新整理的標籤數量過多時，記憶體就很容易溢位，造成整個服務宕機。

同時目前底層儲存商品集的資料庫為Hbase，因此在標籤側對於商品集的重新整理場景目前都是採取全增全刪的策略，即把重新整理後的商品集先全量儲存一次(利用Hbase 儲存的冪等性，同一個rowkey的資料重複儲存會進行覆蓋，而不用在儲存前做額外的資料是否存在的判斷)，並更新資料的modity_time=now()，然後再從Hbase中分批scan遍歷商品集，找到modity_time<now的再進行刪除，以此完成一次標籤的重新整理任務。

往往一個商品集在重新整理前後真正變化的spu量並不大，通過取數分析得知變化的不會超過商品集數量的10%。而我們目前採用的這種全增全刪的策略，每次重新整理後都會有大量已有資料的重複插入，不僅延長了重新整理的速度，也增加底層儲存的壓力，同時由於選投平臺裡有標籤的指標，標籤的變動需要推送變化的spu給選投平臺進行重新圈品，同時spu es 中也存有標籤的資料用於後臺展示，所以當前全增全刪的策略，尤其是大量已有資料的重複插入，都會同步到選投平臺和spu es側，對他們造成大量的效能浪費和處理成本，改造迫在眉睫。

優化方案

前面提到，由於傳統的java Set結構在資料量較大的情況，佔用記憶體較多，導致無法將前後海量商品集的資料全部存到記憶體中去做運算。

那麼有沒有一個數據結構可以在存海量資料時還能保持較低的記憶體佔用，支援去重，還支援交集，差集等各種運算呢?

Bitmap完美滿足要求。

Bitmap是通過bit陣列來儲存資料的資料結構，是一串連續的二進位制陣列（0和1），可以通過偏移量（offset）定位元素。Bitmap通過最小的單位bit來進行0|1的設定，表示某個元素的值或者狀態，時間複雜度為O(1)。

同時由於採用了Bit為單位來儲存資料，因此在儲存空間方面，可以大大節省。例如儲存500W資料僅需5000000/8/1024/1024=0.5M記憶體。

因此準備使用Bitmap結構來儲存重新整理前後的商品集，然後分別對新老Bitmap互相求差集得到，最終對差集進行add和delete操作即可。

方案可行性分析

以標籤場景為例。

標籤可以繫結選投平臺，標籤系統會把選投平臺圈選的所有商品集都打上標，此刻標籤下的商品集記為oldSset(X+Y)。

選投平臺重新整理後，會重新圈選出一批滿足選投平臺指標的商品集，此時選投平臺下的商品集記為newSet(Y+Z) 。

此時標籤系統需要給newSet(Y+Z)打標，同時從oldSet(X+Y)刪除不在本次圈選範圍內的商品(X)。

如上圖所示，每次重新整理後，其實只需要對X進行刪除和對Z進行新增。

相比於老全增全刪邏輯，Bitmap diff新方案查詢和刪除量級不變，新增量級和對選投平臺，spu es 的通知量級，都減少了Y。

同時由於Bitmap本身儲存資料的方式，儲存500W的spu資料集對記憶體的佔用也才在0.5M,完成不用擔心記憶體溢位風險。

因此採用Bitmap來儲存重新整理前後的全量商品資料，並在記憶體中做diff是一個理論可行的方案。

技術選型

既然我們選定了使用Bitmap作為新方案的儲存，那麼應該選取哪種Bitmap實現呢?

眾所周知，Bitmap的實現有很多，例如java原生的BitSet，guava的EWAHCompressedBitmap，第三方的RoaingBitmap，redis Bitmap等等，由於redis的Bitmap主要做遠端儲存不適合當前記憶體diff場景，因此排除。

本次主要對比BitSet、EWAHCompressedBitmap、RoaingBitmap三種實現在各種資料稀疏度下的記憶體佔用和cpu佔用，以選出最滿足當前場景的實現。

記憶體佔用測試

通過往Bitmap中新增1、N+1、2N+1.....5000000資料，其中N為資料的步長(稀疏度) 來計算各個Bitmap在不同稀疏度下(N)的記憶體佔用情況。

通過下圖可以看出，除了在稀疏度為1時，EWAHCompressedBitmap記憶體佔用最低以外，其餘稀疏度下的記憶體佔用：RoaingBitmap<EWAHCompressedBitmap<BitSet。

cpu耗時測試

往各個Bitmap中新增1、N+1、2N+1.....5000000資料，其中N為資料的步長(稀疏度)，然後與有5000000滿資料的Bitmap分別求2000次差集並取2000次中的最大耗時，得到在每個稀疏度下每種Bitmap的耗時情況。

通過下圖可以看出，各個稀疏度下的cpu耗時：RoaingBitmap≈EWAHCompressedBitmap<BitSet.

選型最終結論

從記憶體佔用，cpu耗時測試，實際場景下資料稀疏度綜合考慮，RoaingBitmap效果最優，因此選用RoaingBitmap作為新方案的Bitmap實現。

RoaingBitmap介紹及原理

RoaingBitmap儲存原理

RoaingBitmap會將32 bit unsigned int 型別資料 劃分為 2^16 個大Container（即使用資料的前16位二進位制作為Container的編號），每個大Container有一個小Container 來存放一個數值的低16位。

在儲存和查詢數值時，將數值 k 劃分為高 16 位和低 16 位，取高 16 位值找到對應的Container，然後在將低 16 位值存放在相應的 Container 中。

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

比如我們要將31這個數放進RoarigBitmap中，它的16進製為：0000 001F，前16位為0000，後16為001F。所以我們先需要根據前16位的值：0，找到它對應的的Container編號為0，然後根據後16位的值：31，確定這個值應該放到Container中的哪一個位置，如下圖所示。

需要注意大Container裡面的各個小Container是在需要的時候才會申請開闢的，並不是一開始就全部申請的，而且大Container中小Container都是按序號有序排列在大Container裡面的。

四種container介紹

為了在各種場景和稀疏度下都始終保持有良好的記憶體佔用和效能表現，RoaingBitmap 特意設計了4種小Container，分別為ArrayContainer(陣列容器)，BitmapContainer(點陣圖容器)，Runcontainer(行程步長容器)，Sharedcontainer(共享容器)，下面我會對每個ArrayContainer的使用場景和原理進行介紹。

• Arraycontiner

在建立一個新container時，如果只插入一個元素，RBM（RoaingBitmap）預設會用ArrayContainer來儲存。當ArrayContainer（其中每一個元素的型別為 short 佔兩個位元組，且裡面的元素都是按從小到大的順序排列的）的容量超過4096（這裡是指4096個short 即8k）後，會自動轉成BitmapContainer(這個所佔空間始終都是8k)儲存。4096這個閾值很聰明，低於它時ArrayContainer比較省空間，高於它時BitmapContainer比較省空間。也就是說ArrayContainer儲存稀疏資料，BitmapContainer儲存稠密資料，可以最大限度地避免記憶體浪費，如下圖所示。

• BitmapContainer

這個容器其實就是我們所說的點陣圖，只不過這裡點陣圖的位數為65536個，也就是2^16個bit，計算下來起所佔記憶體就是8kb。然後每一位用0，1表示這個數不存在或者存在，如下圖所示：

• Runcontainer

這是一種利用步長來壓縮空間的方法

我們舉個例子：比如連續的整數序列 11， 12， 13， 14， 15， 27， 28， 29 會被 壓縮為兩個二元組 11， 4， 27， 2 表示：11後面緊跟著4個連續遞增的值，27後面跟著2個連續遞增的值，那麼原先16個位元組的空間，現在只需要8個位元組，是不是節省了很多空間呢。不過這種容器不常用，所以在使用的時候需要我們自行呼叫相關的轉換函式來判斷是不是需要將arraycontiner，或BitmapContainer轉換為Runcontainer。

• Sharedcontainer

這種容器它本身是不儲存資料的，只是用它來指向ArrayContainer，BitmapContainer或Runcontainer，就好比指標的作用一樣，這個指標可以被多個物件擁有，但是指標所指標的實質東西是被這多個物件所共享的。在我們進行RoaingBitmap之間的拷貝的時候，有時並不需要將一個container拷貝多份，那麼我們就可以使用Sharedcontainer來指向實際的container，然後把Sharedcontainer賦給多個RoaingBitmap物件持有，這個RoaingBitmap物件就可以根據Sharedcontainer找到真正儲存資料的container，這可以省去不必要的空間浪費。

這些container之間的關係可以用下面這幅圖來表示：

其中的roaring_array是RoaingBitmap物件，而途中的Sharedcontainer則表示被多個roaring_array裡面的小Container共享。

 

RoaingBitmap優勢

• 記憶體

Bitmap比較適用於資料分佈比較稠密的儲存場景中，對於原始的Bitmap來說，若要儲存一個uint32型別資料，這就需要2 ^ 32長度的bit陣列，通過計算可以發現(2 ^ 32 / 8 bytes = 512MB)，一個普通的Bitmap需要耗費512MB的儲存空間。如果我們只儲存幾個資料的話依然需要佔用512M的話，就有些浪費空間了，因此我們可以採用對點陣圖進行壓縮的RoaingBitmap，以此減少記憶體和提高效率。

• 效能

RoaingBitmap除了比Bitmap佔用記憶體少之外，其並集和交集操作的速度也要比Bitmap的快。原因歸結為以下幾點：

• 計算上的優化

對於RoaingBitmap本質上是將大塊的Bitmap分成各個小塊，其中每個小塊在需要儲存資料的時候才會存在。所以當進行交集或並集運算的時候，RoaingBitmap只需要去計算存在的一些塊而不需要像Bitmap那樣對整個大的塊進行計算。如果塊內非常稀疏，那麼只需要對這些小整數列表進行集合的 AND、OR 運算，這樣的話計算量還能繼續減輕。這裡既不是用空間換時間，也沒有用時間換空間，而是用邏輯的複雜度同時換取了空間和時間。

同時在RoaingBitmap中32位長的資料，被分割成高 16 位和低 16 位，高 16 位表示塊偏移，低16位表示塊內位置，單個塊可以表達 64k 的位長，也就是 8K 位元組。這樣可以保證單個塊都可以全部放入 L1 Cache，可以顯著提升效能。

• 程式邏輯上的優化

1. RoaingBitmap維護了排好序的一級索引，以及有序的ArrayContainer當進行交集操作的時候，只需要根據一級索引中對應的值來獲取需要合併的容器，而不需要合併的容器則不需要對其進行操作直接過濾掉。
2. 當進行合併的ArrayContainer中資料個數相差過大的時候採用基於二分查詢的方法對ArrayContainer求交集，避免不必要的線性合併花費的時間開銷。
3. RoaingBitmap在做並集的時候同樣根據一級索引只對相同的索引的容器進行合併操作，而索引不同的直接新增到新的RoaingBitmap上即可，不需要遍歷容器。
4. RoaingBitmap在合併容器的時候會先預測結果，生成對應的容器，避免不必要的容器轉換操作

show me the code

程式碼邏輯其實相對簡單，主要是構建新老Bitmap，互相求差集後對本次新增的spu進行新增，對本次需要刪除的spu進行刪除操作。

優化效果

重新整理速度

統計全量標籤在新老邏輯下的耗時,發現提升比例大部分都集中在40%-60%區間，去掉最高及最低值

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

寫入量級以及對其他場景影響

統計全量標籤在新老邏輯下的寫量級,發現提升比例大部分都集中在85%-99%區間，去掉最高及最低值

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

總結

由於java的Set結構在大資料量下的記憶體佔用很高，因此在圈選商品集的重新整理場景無法直接在記憶體中用set去全量儲存重新整理前後的商品集並做差集運算。

因此考慮到了使用Bitmap這樣一種通過bit陣列來儲存資料的資料結構，它採用了Bit為單位來儲存資料，因此在儲存空間方面，可以大大節省。

對比了業界了各種Bitmap實現，結合當前場景，最終採用了RoaingBitmap來作為最終的實現。

RoaingBitmap屬於是點陣圖的一個進化，即壓縮點陣圖，不過在RoaingBitmap中不只包含Bitmap這一種資料結構，而是包涵了多種儲存的方式(contianer)，同時通過計算及邏輯上的優化，保證了在各個稀疏度下相比於傳統的Bitmap都能保持較低的記憶體佔用和對比速度。

最終上線後優化效果也是比較不錯，重新整理速度提升在52%左右，寫入量級平均降低87%，有效的提升了重新整理速度，以及對儲存DB及其他場景域的壓力。

同時本方案也適用其他類似的場景，比如選投平臺側的重新整理，繫結選投平臺的主題集下的商品重新整理等。

參考文件：

1. RoaingBitmap 官方github地址
2. 使用Apache ECharts完成優化效果圖繪製

*文/Creed

關注得物技術，每週一三五晚18:30更新技術乾貨
要是覺得文章對你有幫助的話，歡迎評論轉發點贊～