目錄
位圖法簡述
對于我們大數(shù)據(jù)工作者來說，海量數(shù)據(jù)的判重和基數(shù)統(tǒng)計是兩個繞不開的基礎問題。之前我已經(jīng)講了兩種應用廣泛的方法，即布隆過濾器和HyperLogLog。雖然它們節(jié)省空間并且效率高，但也付出了一定的代價，即：
- 只能插入元素，不能刪除元素；
- 不保證100%準確，總是存在誤差。
這兩個缺點可以說是所有概率性數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure）做出的trade-off，畢竟魚與熊掌不可兼得嘛。
話說回來，有什么相對高效的能夠保證絕對精確的方法呢？最樸素的思路是利用布隆過濾器和HyperLogLog的基礎——位數(shù)組，也叫位圖（bitmap）。不妨來看一道老生常談的面試題：
給定含有40億個不重復的位于[0, 232 - 1]區(qū)間內(nèi)的整數(shù)的集合，如何快速判定某個數(shù)是否在該集合內(nèi)？
顯然，如果我們將這40億個數(shù)原樣存儲下來，需要耗費高達14.9GB的內(nèi)存，不可接受。所以我們可以用位圖來存儲，即第0個比特表示數(shù)字0，第1個比特表示數(shù)字1，以此類推。如果某個數(shù)位于原集合內(nèi)，就將它對應的位圖內(nèi)的比特置為1，否則保持為0。這樣就能很方便地查詢得出結(jié)果了，僅僅需要占用512MB的內(nèi)存，只有原來的不到3.4%。
由于位圖的這個特性，它經(jīng)常被作為索引用在數(shù)據(jù)庫、查詢引擎和搜索引擎中，并且位操作（如and求交集、or求并集）之間可以并行，效率更好。但是，位圖也不是完美無缺的：不管業(yè)務中實際的元素基數(shù)有多少，它占用的內(nèi)存空間都恒定不變。舉個例子，如果上文題目中的集合只存儲了0這一個元素，那么該位圖只有最低位是1，其他位全為0，但仍然占用了512MB內(nèi)存。數(shù)據(jù)越稀疏，空間浪費越嚴重。
為了解決位圖不適應稀疏存儲的問題，大佬們提出了多種算法對稀疏位圖進行壓縮，減少內(nèi)存占用并提高效率。比較有代表性的有WAH、EWAH、Concise，以及RoaringBitmap。前三種算法都是基于行程長度編碼（Run-length encoding, RLE）做壓縮的，而RoaringBitmap算是它們的改進版，更加優(yōu)秀，因此本文重點探討它。
RoaringBitmap的思路
為了不用打那么多字，下文將RoaringBitmap簡稱為RBM。
RBM的歷史并不長，它于2016年由S. Chambi、D. Lemire、O. Kaser等人在論文《Better bitmap performance with Roaring bitmaps》與《Consistently faster and smaller compressed bitmaps with Roaring》中提出，官網(wǎng)在這里。
RBM的主要思路是：將32位無符號整數(shù)按照高16位分桶，即最多可能有216=65536個桶，論文內(nèi)稱為container。存儲數(shù)據(jù)時，按照數(shù)據(jù)的高16位找到container（找不到就會新建一個），再將低16位放入container中。也就是說，一個RBM就是很多container的集合。
為了方便理解，照搬論文中的示例圖，如下所示。
圖中示出了三個container：
- 高16位為0000H的container，存儲有前1000個62的倍數(shù)。
- 高16位為0001H的container，存儲有[216, 216+100)區(qū)間內(nèi)的100個數(shù)。
- 高16位為0002H的container，存儲有[2×216, 3×216)區(qū)間內(nèi)的所有偶數(shù)，共215個。
container是RBM新創(chuàng)造的概念，自然也是提高效率的核心。為了更高效地存儲和查詢數(shù)據(jù)，不同情況下會采用不同類型的container，下面深入講解一下container的細節(jié)。
Container原理
一共有3種。
ArrayContainer
當桶內(nèi)數(shù)據(jù)的基數(shù)不大于4096時，會采用它來存儲，其本質(zhì)上是一個unsigned short類型的有序數(shù)組。數(shù)組初始長度為4，隨著數(shù)據(jù)的增多會自動擴容（但最大長度就是4096）。另外還維護有一個計數(shù)器，用來實時記錄基數(shù)。
上圖中的前兩個container基數(shù)都沒超過4096，所以均為ArrayContainer。
BitmapContainer
當桶內(nèi)數(shù)據(jù)的基數(shù)大于4096時，會采用它來存儲，其本質(zhì)就是上一節(jié)講過的普通位圖，用長度固定為1024的unsigned long型數(shù)組表示，亦即位圖的大小固定為216位（8KB）。它同樣有一個計數(shù)器。
上圖中的第三個container基數(shù)遠遠大于4096，所以要用BitmapContainer存儲。
RunContainer
RunContainer在圖中并未示出，初始的RBM實現(xiàn)中也沒有它，而是在本節(jié)開頭的第二篇論文中新加入的。它使用可變長度的unsigned short數(shù)組存儲用行程長度編碼（RLE）壓縮后的數(shù)據(jù)。舉個例子，連續(xù)的整數(shù)序列11, 12, 13, 14, 15, 27, 28, 29會被RLE壓縮為兩個二元組11, 4, 27, 2，表示11后面緊跟著4個連續(xù)遞增的值，27后面跟著2個連續(xù)遞增的值。
由此可見，RunContainer的壓縮效果可好可壞?？紤]極端情況：如果所有數(shù)據(jù)都是連續(xù)的，那么最終只需要4字節(jié)；如果所有數(shù)據(jù)都不連續(xù)（比如全是奇數(shù)或全是偶數(shù)），那么不僅不會壓縮，還會膨脹成原來的兩倍大。所以，RBM引入RunContainer是作為其他兩種container的折衷方案。
下面來簡要看看它們的復雜度和轉(zhuǎn)換方法。
時空分析
增刪改查的時間復雜度方面，BitmapContainer只涉及到位運算，顯然為O(1)。而ArrayContainer和RunContainer都需要用二分查找在有序數(shù)組中定位元素，故為O(logN)。
空間占用（即序列化時寫出的字節(jié)流長度）方面，BitmapContainer是恒定為8192B的。ArrayContainer的空間占用與基數(shù)（c）有關，為(2 + 2c)B；RunContainer的則與它存儲的連續(xù)序列數(shù)（r）有關，為(2 + 4r)B。以上節(jié)圖中的RBM為例，它一共存儲了33868個unsigned int，只占用了10396個字節(jié)的空間，可以說是非常高效了。
Container的創(chuàng)建與轉(zhuǎn)換
在創(chuàng)建一個新container時，如果只插入一個元素，RBM默認會用ArrayContainer來存儲。如果插入的是元素序列的話，則會先根據(jù)上面的方法計算ArrayContainer和RunContainer的空間占用大小，并選擇較小的那一種進行存儲。
當ArrayContainer的容量超過4096后，會自動轉(zhuǎn)成BitmapContainer存儲。4096這個閾值很聰明，低于它時ArrayContainer比較省空間，高于它時BitmapContainer比較省空間。也就是說ArrayContainer存儲稀疏數(shù)據(jù)，BitmapContainer存儲稠密數(shù)據(jù)，可以最大限度地避免內(nèi)存浪費。
RBM還可以通過調(diào)用特定的API（名為optimize）比較ArrayContainer/BitmapContainer與等價的RunContainer的內(nèi)存占用情況，一旦RunContainer占用較小，就轉(zhuǎn)換之。也就是說，上圖例子中的第二個ArrayContainer可以轉(zhuǎn)化為只有一個二元組0, 100的RunContainer，占用空間進一步下降到10200字節(jié)。
RBM的應用
官方提供了RBM的多種語言實現(xiàn)，Java、C/C++、Python、Go、C#等等一應俱全。Java版本的GitHub repo見這里。代碼比較多，但思路很清晰，看官如果對位運算比較熟悉的話讀起來不難，故本文就不再長篇大論地講源碼了。值得注意的幾點如下：
- 兩個RBM做集合操作時，不同種類container之間位運算的處理方式，如ArrayContainer AND BitmapContainer，BitmapContainer OR RunContainer等；
- 對64位整數(shù)的支持（32位有時會不夠用哈）；
- 能夠?qū)BM數(shù)據(jù)寫到堆外，即內(nèi)存映射；
- 支持Kryo序列化方式。
RBM的應用范圍極廣，下面只簡單列舉幾個有代表性的應用，并給出reference。
Lucene
為了加速搜索，Lucene會將常用的查詢過濾條件產(chǎn)生的結(jié)果集緩存到內(nèi)存中，方便復用，稱為filter cache。結(jié)果集其實就是文檔ID（整形數(shù)）的集合。從Lucene 5開始，使用了RBM優(yōu)化過的文檔ID集合RoaringDocIdSet作為filter cache，詳情可以參見《Frame of Reference and Roaring Bitmaps》。該文除了介紹RBM外，還介紹了壓縮倒排索引的Frame of Reference（FOR）編碼，值得一讀。
Spark
在Spark Core的MapStatus組件（用來跟蹤ShuffleMapTask的輸出結(jié)果塊）中，利用了RBM來存儲塊是否非空的狀態(tài)。今后會在Spark連載里講到它，所以現(xiàn)在看看該類的源碼就可以了，不難理解。
Greenplum
我司是Greenplum大戶，雖然本鶸現(xiàn)在不負責數(shù)倉相關的事情了，但是偶爾還是要向GP提供一些數(shù)據(jù)。GP配合RoaringBitmap非常適合做海量用戶的近實時畫像，每個RBM代表一維標簽即可，根據(jù)標簽圈選用戶也很方便。GP原生并未支持RBM類型數(shù)據(jù)，需要安裝一個擴展插件，見這里。關于GP與RBM的整合與使用，有兩篇不錯的參考文章：
Redis
我們在Redis里經(jīng)常使用位圖存儲數(shù)據(jù)（Redis原生以字符串的形式支持位圖），當然也就會遇到稀疏位圖浪費存儲空間的問題。但要讓Redis支持RBM，需要引入專門的module，項目地址見這里。它的設計思想與Java版RBM幾乎相同，不再廢話了。
The End
晚安咯。
