共计 5803 个字符，预计需要花费 15 分钟才能阅读完成。
背景
目前，在商品圈选投场景，每个标签 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
@得物技术公众号
