石頭智能洗地機A10 Plus體驗：雙向自清潔治好了我的懶癌
一、前言和介紹專為家庭請假懶人而生的石頭科技在近日又帶來了自己的全新旗艦新品，石頭智能洗地機A10 Plus。從這個產品名上就不難看出，這次石頭推出的并不是常見的掃地機器
在進行大數據開發時，我們可以使用布隆過濾器和Redis中的HyperLogLog來進行大數據的判重和數量統計，雖然這兩種方法節省內存空間并且效率很高，但是也存在一些誤差。如果需要100%準確的話，我們可以使用BitMap來存儲數據。
BitMap 位圖索引數據結構被廣泛地應用于數據存儲和數據搜索中，但是對于存儲較為分散的數據時，BitMap會占用比較大的內存空間，因此我們更偏向于使用 Roaring BitMap稀疏位圖索引進行存儲。同時，Roaring BitMap廣泛應用于數據庫存儲和大數據引擎中，例如Hive，Spark，Doris，Kylin等。
下文將分別介紹 BitMap 和 Roaring BitMap 的原理及其相關應用。
BitMap的基本思想就是用bit位來標記某個元素對應的value，而key就是這個元素。
例如，在下圖中，是一個字節代表的8位，下標為1,2,4,6的bit位的值為1，則該字節表示{1,2,4,6}這幾個數。
在Java中，1個int占用4個字節，如果用int來存儲這四個數字的話，那么將需要4 * 4 = 16字節。
BitMap可以用于快速排序，查找，及去重等操作。優點是占用內存少（相較于數組）和運算效率高，但是缺點也非常明顯，無法存儲重復的數據，并且在存儲較為稀疏的數據時，浪費存儲空間較多。
為了解決BitMap存儲較為稀疏數據時，浪費存儲空間較多的問題，我們引入了稀疏位圖索引Roaring BitMap。Roaring BitMap 有較高的計算性能及壓縮效率。下面簡單介紹一下Roaring BitMap的基本原理。
Roaring BitMap處理int型整數，將32位的int型整數分為高16位和低16位分別進行處理，高16位作為索引分片，而低16位用于存儲實際數據。其中每個索引對應一個數據桶（bucket），那么一共可以包含2^16 = 65536個數據塊。每個數據桶使用container容器來存儲低16位的部分，每個數據桶最多存儲2^16 = 65536個數據。
如上圖所示，高16位作為索引查找具體的數據塊，當前索引值為0，低16位作為value進行存儲。
Roaring BitMap在進行數據存儲時，會先根據高16位找到對應的索引key（二分查找），低16位作為key對應的value，先通過key檢查對應的container容器，如果發現container不存在的話，就先創建一個key和對應的container，否則直接將低16位存儲到對應的container中。
Roaring BitMap的精妙之處在于使用不同類型的container，接下來將對其進行介紹。
1.ArrayContainer
顧名思義，ArrayContainer直接采用數組來存儲低16位數據，沒有采用任何數據壓縮算法，適合存儲比較稀疏的數據，在Java中，使用short數組來存儲，并且占用的內存空間大小和數據量成線性關系。由于short為2字節，因此n個數據為2n字節。ArrayContainer采用二分查找定位有序數組中的元素，因此時間復雜度為O(logN)。ArrayContainer的最大數據量為4096, 4096 * 2b = 8kb。
2.BitMapContainer
BitMapContainer采用BitMap的原理，就是一個沒有經過壓縮處理的普通BitMap，適合存儲比較稠密的數據，在Java中使用Long數組存儲低16位數據，每一個bit位表示一個數字。由于每個container需要存儲2^16 = 65536個數據，如果通過BitMap進行存儲的話，需要使用2^16個bit進行存儲，即8kb的數據空間。
可以從下圖中看出ArrayContainer和BitMapContainer的內存空間使用關系，當數據量小于4096時，使用ArrayContainer比較合適，當數據量大于等于4096時，使用BitMapContainer更佳。
因為BitMap直接使用位運算，所以BitMapContainer的時間復雜度為O(1)。
3.RunContainer
RunContainer采用Run-Length Encoding 行程長度編碼進行壓縮，適合存儲大量連續數據。Java中使用short數組進行存儲。連續bit位程度越高的話越節省存儲空間，最佳場景下（65536個數據全為1）只需要存儲4字節。最差場景為所有數據都不連續，所有存儲數據位置為奇數或者偶數，這種場景需要存儲128kb。由于采用二分查找算法定位元素，因此時間復雜度為O(logN)。
行程長度編碼即的原理是對連續出現的數字進行壓縮，只記錄初始數字和后續連續數量。
例如：[1,2,3,4,5,8,9,10]使用編碼后的數據為[1,4,8,2]。
Java 里可以使用runOptinize()方法來對比RunContainer和其他兩個Container存儲空間大小，如果使用RunContainer存儲空間更佳則會進行轉化。
根據上面三個Container類型我們可以得知如何進行選擇：
介紹完Roaring BitMap的三種container類型以后，讓我們了解一下，Roaring BitMap的相關源碼。這里介紹一下Java中增加元素的源碼實現。
public void add(final int x) { final short hb = Util.highbits(x); final int i = highLowContainer.getIndex(hb); if (i >= 0) { highLowContainer.setContainerAtIndex(i, highLowContainer.getContainerAtIndex(i).add(Util.lowbits(x))); } else { final ArrayContainer newac = new ArrayContainer(); highLowContainer.insertNewKeyValueAt(-i - 1, hb, newac.add(Util.lowbits(x))); } }Roaring BitMap首先獲取添加元素的高16位，然后再調用getIndex獲取高16位對應的索引，如果索引大于0，表示已經創建該索引對應的container，故直接添加相應的元素低16位即可；否則的話，說明該索引對應的container還沒有被創建，先創建對應的ArrayContainer，再進行元素添加。值得一提的是，在getIndex方法中，使用了二分查找來獲取索引值，所以時間復雜度為O(logn)。
// 包含一個二分查找protected int getIndex(short x) { // 在二分查找之前，我們先對常見情況優化。 if ((size == 0) || (keys[size - 1] == x)) { return size - 1; } // 沒有碰到常見情況，我們只能遍歷這個列表。 return this.binarySearch(0, size, x);}對于元素添加，三種Container提供了不同的實現方式，下面將分別介紹。
1. ArrayContainer
if (cardinality == 0 || (cardinality > 0 && toIntUnsigned(x) > toIntUnsigned(content[cardinality - 1]))) { if (cardinality >= DEFAULT_MAX_SIZE) { return toBitMapContainer().add(x); } if (cardinality >= this.content.length) { increaseCapacity(); } content[cardinality++] = x; } else { int loc = Util.unsignedBinarySearch(content, 0, cardinality, x); if (loc < 0) { // 當標簽中元素數量等于默認最大值時，把ArrayContainer轉換為BitMapContainer if (cardinality >= DEFAULT_MAX_SIZE) { return toBitMapContainer().add(x); } if (cardinality >= this.content.length) { increaseCapacity(); } System.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1); content[-loc - 1] = x; ++cardinality; } } return this;}ArrayContainer把添加元素分成兩種場景，一種走二分查找，另外一種不走二分查找。
第一種場景：不走二分查找。
當基數為0或者值大于container中的最大值，可以直接添加，因為content數組是有序的，最后一個是最大值。
當基數大于等于默認最大值4096時，ArrayContainer將轉換為BitMapContainer。如果基數大于content的數組長度的話，需要將content進行擴容。最后進行賦值即可。
第二種場景：走二分查找。
先通過二分查找找到對應的插入位置，如果返回loc大于等于0，說明存在，直接返回即可，如果小于0才進行后續插入。后續操作同上，當基數大于等于默認最大值4096時，ArrayContainer將轉換為BitMapContainer。如果基數大于content的數組長度的話，需要將content進行擴容。最后通過拷貝數組將元素插入到content數組中。
2. BitMapContainer
public Container add(final short i) { final int x = Util.toIntUnsigned(i); final long previous = BitMap[x / 64]; long newval = previous | (1L << x); BitMap[x / 64] = newval; if (USE_BRANCHLESS) { cardinality += (previous ^ newval) >>> x; } else if (previous != newval) { ++cardinality; } return this;}BitMap數組為BitMapContainer的存儲容器存放數據的內容，數據類型為long，在這里我們只需要找到x在BitMap中的位置，并且把相應的bit位置1即可。x/64就是找到對應long的舊值，1L<<x 就是把對應的bit位置為1，再跟舊值進行或操作，就可以得到新值，再將這個新值存回到bitmap數組即可。<="" span="">
3. RunContainer
public Container add(short k) { int index = unsignedInterleavedBinarySearch(valueslength, 0, nbrruns, k); if (index >= 0) { return this;// already there } index = -index - 2; if (index >= 0) { int offset = toIntUnsigned(k) - toIntUnsigned(getValue(index)); int le = toIntUnsigned(getLength(index)); if (offset <= le) { return this; } if (offset == le + 1) { // we may need to fuse if (index + 1 < nbrruns) { if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) { // indeed fusion is needed setLength(index, (short) (getValue(index + 1) + getLength(index + 1) - getValue(index))); recoverRoomAtIndex(index + 1); return this; } } incrementLength(index); return this; } if (index + 1 < nbrruns) { // we may need to fuse if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) { // indeed fusion is needed setValue(index + 1, k); setLength(index + 1, (short) (getLength(index + 1) + 1)); return this; } } } if (index == -1) { // we may need to extend the first run if (0 < nbrruns) { if (getValue(0) == k + 1) { incrementLength(0); decrementValue(0); return this; } } } makeRoomAtIndex(index + 1); setValue(index + 1, k); setLength(index + 1, (short) 0); return this;}RunContainer中的兩個數據結構，nbrruns表示有多少段行程，數據類型為int，valueslength數組表示所有的行程，數據類型為short。
public static void count(Integer inputSize) { RoaringBitMap BitMap = new RoaringBitMap(); BitMap.add(0L, inputSize); //獲取BitMap個數 int cardinality = BitMap.getCardinality(); //獲取BitMap壓縮大小 int compressSizeIntBytes = BitMap.getSizeInBytes(); //刪除壓縮（移除行程編碼，將container退化為BitMapContainer 或 ArrayContainer） BitMap.removeRunCompression(); //獲取BitMap不壓縮大小 int uncompressSizeIntBytes = BitMap.getSizeInBytes(); System.out.println("Roaring BitMap個數：" + cardinality); System.out.println("最好情況，BitMap壓縮大小：" + compressSizeIntBytes / 1024 + "KB"); System.out.println("最壞情況，BitMap不壓縮大小：" + uncompressSizeIntBytes / 1024 / 1024 + "MB"); BitSet bitSet = new BitSet(); for (int i = 0; i < inputSize; i++) { bitSet.set(i); } //獲取BitMap大小 int size = bitSet.size(); System.out.println("BitMap個數：" + bitSet.length()); System.out.println("BitMap大小：" + size / 8 / 1024 / 1024 + "MB"); }上述代碼使用了Java內置的BitMap(BitSet) 和 Roaring BitMap進行存儲大小對比，輸出結果如下所示。
可以發現，Roaring BitMap的壓縮性能效果非常好，同等情況下，是BitMap占用內存的近一千分之一。在退化成BitMapContainer/arrayContainer之后也仍然比使用基本的BitMap存儲效果好一些。
在Java中，Roaring BitMap提供了交并補差集等操作，如下代碼所示，列舉了Java中roaing BitMap的相關API使用方式。
//添加單個數字public void add(final int x)//添加范圍數字public void add(final long rangeStart, final long rangeEnd)//移除數字public void remove(final int x)//遍歷RBMpublic void forEach(IntConsumer ic)//檢測是否包含public boolean contains(final int x)//獲取基數public int getCardinality()//位與，取兩個RBM的交集，當前RBM會被修改public void and(final RoaringBitMap x2)//同上，但是會返回一個新的RBM，不會修改原始的RBM，線程安全public static RoaringBitMap and(final RoaringBitMap x1, final RoaringBitMap x2)//位或，取兩個RBM的并集，當前RBM會被修改public void or(final RoaringBitMap x2)//同上，但是會返回一個新的RBM，不會修改原始的RBM，線程安全public static RoaringBitMap or(final RoaringBitMap x1, final RoaringBitMap x2)//異或，取兩個RBM的對稱差，當前RBM會被修改public void xor(final RoaringBitMap x2)//同上，但是會返回一個新的RBM，不會修改原始的RBM，線程安全public static RoaringBitMap xor(final RoaringBitMap x1, final RoaringBitMap x2)//取原始值和x2的差集，當前RBM會被修改public void andNot(final RoaringBitMap x2)//同上，但是會返回一個新的RBM，不會修改原始的RBM，線程安全public static RoaringBitMap andNot(final RoaringBitMap x1, final RoaringBitMap x2)//序列化public void serialize(DataOutput out) throws IOExceptionpublic void serialize(ByteBuffer buffer)//反序列化public void deserialize(DataInput in) throws IOExceptionpublic void deserialize(ByteBuffer bbf) throws IOException對于序列化來說，Roaring BitMap官方定義了一套序列化規則，用來保證不同語言實現的兼容性。
Java中可以使用serialize方法進行序列化，deserialize方法進行反序列化。
Roaring BitMap可以用來構建大數據標簽，針對類型特征來創建對應的標簽。
在我們的業務場景中，有很多需要基于人群標簽進行交并補集運算的場景，下面以一個場景為例，我們需要計算每天某個設備接口 在設備標簽A上的查詢成功率，因為設備標簽A中的設備不是所有都活躍在網的，所以我們需要將設備標簽A與每日日活人群標簽取交集，得到的交集大小才能用作成功率計算的分母，另外拿查詢成功的標簽人群做分子來進行計算即可，查詢時長耗時為1s。
假如沒有使用標簽保存集合之前，我們需要在hive表中查詢出同時滿足當天在網的活躍用戶和設備A的用戶數量，查詢時長耗時在幾分鐘以上。兩種方式相比之下，使用Roaring BitMap查詢的效率更高。
本文結合個人理解梳理了BitMap及Roaring BitMap的原理及使用，分別主要介紹了Roaring BitMap的存儲方式及三種container類型及Java中Roaring BitMap相關API使用，如有不足和優化建議，也歡迎大家批評指正。
參考資料：
本文鏈接：http://www.tebozhan.com/showinfo-26-95169-0.html海量數據處理利器 Roaring BitMap 原理介紹
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 實現一個完美的高并發訂單減庫存方案
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號