BitmapRoaringBitmap原理分析

　　作者：京东科技曹留界
　　在人群本地化实践中我们介绍了人群ID中所有的pin的偏移量可以通过Bitmap存储，而Bitmap所占用的空间大小只与偏移量的最大值有关系。假如现在要向Bitmap内存入两个pin对应的偏移量，一个偏移量为1，另一个偏移量为100w，那么Bitmap存储直接需要100wbit的空间吗？数据部将偏移量存入Bitmap时，又如何解决数据稀疏问题呢？本文将为大家解答这个问题。一、BitMap
　　Bitmap的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此可以大大节省存储空间。
　　如果想将数字2存入位图中，则只需要将位图数组中下标为2的数组值置为1。
　　但是，如果现在要存储两个人群ID对应的偏移量，一个偏移量为1，另一个偏移量为100w，如果将这两个值直接放到位图数组中，那么位图数组所需要的空间就是100wbit，会产生大量的空间浪费。那么有什么方法可以避免空间浪费吗？答案就是RoaringBitMap！二、RoaringBitMap
　　RoaringBitMap是一种高效压缩位图，简称RBM。RBM的概念于2016年由S。Chambi、D。Lemire、O。Kaser等人在论文《BetterbitmapperformancewithRoaringbitmaps》《ConsistentlyfasterandsmallercompressedbitmapswithRoaring》中提出。下面我们结合java中的实现对其进行介绍。2。1实现思路
　　RBM主要将32位的整型（int）分为高16位和低16位（两个short），其中高16位对应的数字使用16位整型有序数组存储，低16位根据不同的情况选择三种不同的container来存储，这三种container分别为：
　　ArrayContainer
　　底层数据结构为short类型的数组，直接将数字低16位的值存储到该数组中。short类型的数组始终保持有序，方便使用二分查找，且不会存储重复数值。因为这种Container存储数据没有任何压缩，因此只适合存储少量数据。其内部数组容量是动态变化的，当容量不够时会进行扩容，最大容量为4096。由于数组是有序的，存储和查询时都可以通过二分查找快速定位其在数组中的位置。
　　ArrayContainer占用的空间大小与存储的数据量为线性关系，每个short为2字节，因此存储了N个数据的ArrayContainer占用空间大致为2N字节。存储一个数据占用2字节，存储4096个数据占用8kb。
　　BitmapContainer
　　底层实现为位图。这种Container使用long〔〕存储位图数据。我们知道，每个Container处理16位整形的数据，也就是065535，因此根据位图的原理，需要65536个比特来存储数据，每个比特位用1来表示有，0来表示无。每个long有64位，因此需要1024个long来提供65536个比特。
　　因此，每个BitmapContainer在构建时就会初始化长度为1024的long〔〕。这就意味着，不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。
　　RunContainer
　　RunContainer中的Run指的是行程长度压缩算法（RunLengthEncoding），对连续数据有比较好的压缩效果。
　　它的原理是，对于连续出现的数字，只记录初始数字和后续数量。即：
　　对于数列11，它会压缩为11，0；
　　对于数列11，12，13，14，15，它会压缩为11，4；
　　对于数列11，12，13，14，15，21，22，它会压缩为11，4，21，1；
　　源码中的short〔〕valueslength中存储的就是压缩后的数据。
　　这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切，对于连续的100个short，它能从200字节压缩为4字节，但对于完全不连续的100个short，编码完之后反而会从200字节变为400字节。
　　如果要分析RunContainer的容量，我们可以做下面两种极端的假设：
　　最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储2个short，占用4字节
　　最坏情况，065535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个short，128kb
　　也就RBM在存入一个32位的整形数字时，会先按照该数字的高16位进行分桶，以确定该数字要存入到哪个桶中。确定好分桶位置后，再将该数字对应的低16位放入到当前桶所对应的container中。
　　举个栗子
　　以十进制数字131122为例，现在我们要将该数字放入到RBM中。第一步，先将该数字转换为16进制，131122对应的十六进制为0x00020032；其中，高十六位对应0x0002，首先我们找到0x0002所在的桶，再将131122的低16位存入到对应的container中，131122的低16位转换为10进制就是50，没有超过ArrayContainer的容量4096，所以将低16位直接放入到对应的ArrayContainer中。
　　如果要插入的数字低16位超过了4096，RBM会将ArrayContainer转换为BitMapContainer。反之，如果数据在删除之后，数组中的最大数据小于4096，RBM会将BitMapContainer转换回ArrayContainer。
　　RBM处理的是32位的数字，如果我们想处理Long类型的数字怎么办呢？这个时候可以使用Roaring64NavigableMap。Roaring64NavigableMap也是使用拆分模式，将一个long类型数据，拆分为高32位与低32位，高32位代表索引，低32位存储到对应RoaringBitmap中，其内部是一个TreeMap类型的结构，会按照signed或者unsigned进行排序，key代表高32位，value代表对应的RoaringBitmap。三、空间占用对比
　　1、连续数据
　　分别向位图中插入1w、10w、100w、1000w条连续数据，并且对比BitMap和RoaringBitMap占用空间的大小。比较结果如下表所示：
　　10w数据占用空间
　　100w数据占用空间
　　1000w数据占用空间
　　BitMap
　　97。7KB
　　976。6KB
　　9。5MB
　　RoaringBitMap
　　16KB
　　128KB
　　1。2MBTestpublicvoidtestSizeOfBitMap（）｛对比占用空间大小10w元素RoaringBitmaproaringBitmap3newRoaringBitmap（）；byte〔〕bits2newbyte〔100000〕；for（inti0；i100000；i）｛roaringBitmap3。add（i）；bits2〔i〕（byte）i；｝System。out。println（10w数据roaringbitmapbytesize：roaringBitmap3。getSizeInBytes（））；System。out。println（10w数据位图数组bytesize：bits2。length）；RoaringBitmaproaringBitmap4newRoaringBitmap（）；byte〔〕bits3newbyte〔1000000〕；for（inti0；i1000000；i）｛roaringBitmap4。add（i）；bits3〔i〕（byte）i；｝System。out。println（100w数据roaringbitmapbytesize：roaringBitmap4。getSizeInBytes（））；System。out。println（100w数据位图数组bytesize：bits3。length）；RoaringBitmaproaringBitmap5newRoaringBitmap（）；byte〔〕bits4newbyte〔10000000〕；for（inti0；i10000000；i）｛roaringBitmap5。add（i）；bits4〔i〕（byte）i；｝System。out。println（1000w数据roaringbitmapbytesize：roaringBitmap5。getSizeInBytes（））；System。out。println（1000w数据位图数组bytesize：bits4。length）；｝
　　运行截图：
　　2、稀疏数据
　　我们知道，位图所占用空间大小只和位图中索引的最大值有关系，现在我们向位图中插入1和999w两个偏移量位的元素，再次对比BitMap和RoaringBitMap所占用空间大小。
　　占用空间
　　BitMap
　　9。5MB
　　RoaringBitMap
　　24ByteTestpublicvoidtestSize（）｛RoaringBitmaproaringBitmap5newRoaringBitmap（）；byte〔〕bits4newbyte〔10000000〕；for（inti0；i10000000；i）｛if（i1i9999999）｛roaringBitmap5。add（i）；bits4〔i〕（byte）i；｝｝System。out。println（两个稀疏数据roaringbitmapbytesize：roaringBitmap5。getSizeInBytes（））；System。out。println（两个稀疏数据位图数组bytesize：bits4。length）；｝
　　运行截图：