背景

目前，在商品圈选投场景，每个标签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)。

标签商品集底层贮存是Hbase，对于已存在数据的插入，只有rowkey(标签id+spuId)不变， Hbase就会进行笼罩，保留最新工夫戳的数据，能够了解为老Y曾经被新Y笼罩(老Y数据=新Y数据,只是工夫戳会不一样)，所以老全增全删的计划， 删除量级是X，而不是X+Y。

如上图所示，每次刷新后，其实只须要对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，能够显著晋升性能。

程序逻辑上的优化

RoaingBitmap保护了排好序的一级索引，以及有序的ArrayContainer当进行交加操作的时候，只须要依据一级索引中对应的值来获取须要合并的容器，而不须要合并的容器则不须要对其进行操作间接过滤掉。

当进行合并的ArrayContainer中数据个数相差过大的时候采纳基于二分查找的办法对ArrayContainer求交加，防止不必要的线性合并破费的工夫开销。

RoaingBitmap在做并集的时候同样依据一级索引只对雷同的索引的容器进行合并操作，而索引不同的间接增加到新的RoaingBitmap上即可，不须要遍历容器。

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
@得物技术公众号