woodpenker's blog

while(life!=0){study++;}

0%

RoaringBitMap小试牛刀

Posted on Edited on In Views: Valine:
Symbols count in article: 3.5k Reading time ≈ 3 mins.
RoaringBitmap数据结构理解和使用实战

RoaringBitmap小试牛刀

什么是RoaringBitmap

RoaringBitmap的官方github代码库: 中提供了各种语言的实现.
论文地址: http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA.pdf

roaringbitmap属于bitset中的一种, 他是bitmap的升级优化版. 对于大量数据的去重, 大量数据中是否存在的查询, 合并多个数据集合取交并集等场景比较适用. 类似的还有EWAHCompressedBitmap.

RoaringBitmap的存储数据结构主要有以下三种:

1
2
3
keys []int16
values []Container
size int(int32)

它的原理是: 对于32位的整数, 分开成两个部分, 即高16位和低16位(int16类型), 高16位存储到 keys []uint16中, 低16位被存储到values中, size表示当前包含的key-value对的个数. keys的数组永远保持有序的, 通过二分查找进行数据的搜索.

低16的Container根据数据量情况有三种存储形式.

  • ArrayContainer: 对于数据个数小于DEFAULT_MAX_SIZE(4096)的, 存储在ArrayContainer中, 其实际就是一个[]int16的数组, 数据直接按照顺序存在其中, 通过二分查找进行搜索. 适合这个高16的id区间下只有少量数据的场景. 每个数据2B, 容器大小最大为8kb, 这个大小刚好适合存入cache, 以通过cache命中来加速读取效率.
  • BitmapContainer: 对于数据个数大于DEFAULT_MAX_SIZE的, 则将存储容器转换为BitmapContainer, 其是一个由int64组成的位图数组bitmap []int64. 因为是低16位,要表示这些数据就需要2^16(65536)个比特位, 每个int64存储64个, 总共就需要1024个int64来存储这些比特位. 不管其中真的存储了一个还是全部65536个数据的标记, 都会初始化占用这1024个int64, 即固定的8kb内存空间.
  • RunContainer: 对于只存一个1的bitmapcontainer来说实在是太浪费空间了, 那就就可以通过行程长度压缩算法对连续的数据进行压缩. 对于连续出现的数字，只记录初始数字和后续数量:
    1. 对于数列11，它会压缩为11,0；
    2. 对于数列11,12,13,14,15，它会压缩为11,4；
    3. 对于数列11,12,13,14,15,21,22，它会压缩为11,4,21,1；
      数据存储在[]int16中, 他的性能最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储2个int16，占用4字节. 最坏情况，0~65535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个int16，128kb. 这里是只对于比特位为1的数据进行记录或者只对于0的数据进行记录.

只有BitmapContainer可以通过下标在O(1)时间查询, array容器是通过二分查找来查询O(logn), run容器通过顺序查找进行搜索.

在使用时, 对于如何生成存储的容器, 使用哪种容器, 以及怎么做容器转换都进行了优化:

  • 创建单个值时使用arraycontainer
  • 创建连续的值时比较array和run的空间代价选择较少的
  • 对于array容器, 数据量超过4096后自动转为bitmap容器, 通过调用优化方法比较转为run容器和bitmap的容器空间大小来决定是否转换为runcontainer
  • 对于bitmap容器,当数据量低于4096后转为array容器, 调用优化方法根据空间来决定是否转为run容器.
  • 对于run容器,在调用优化方法后会对比三种容器的空间来决定是否转化为对应的容器存储.

go版本实际使用体验

go版本的roaringbitmap地址为:https://github.com/RoaringBitmap/roaring
其中提供了对于64位数据进行支持的API(存储keys的切片数组从[]uint16换成了[]uint32).

roaringbitmap中在进行二分查找的时候,如果找不到会返回当前index的负数, 这样可以方便知道位置信息, 这种优化细节可以很好的加速下次临近数据的查找.

使用示例可以直接参考官方的代码示例. 刚好我这里有个应用场景, 我这边业务有多张mysql数据表, 其中的数据总量在2000万左右, 而且数据还在不断的写入. 其中每个表的都有uid字段(64位整数), 并且这个字段不是唯一的,同时由一个自增的id键值. 现在需要实时的统计这多张数据表中所有的uid去重后的总数. 如果每次统计都通过sql去多张表进行distinct的计算, 每计算一次都需要花个几分钟. 实际上我只需要在第一次将全部去重数据计算好并存下来, 下一次计算就只把新增的数据和这个旧的数据集进行一个并集的操作, 那个新产生的数据集大小不就是我要的总数吗? 使用一个hashmap可以存储这个数据, hash的key值存储uid, value为一个最小数据类型. 这样这个hashmap的key会很庞大,并且数据散列度较大, 有没有更好的存储方式呢? 想到这里, 我就想到了使用roaringmap.

具体办法是: 第一次运行, 通过多个goroutine对每个表都通过id按照固定的步长分批查询uid数据, 把结果交给一个goroutine去写入roaringbitmap, 将这个bitmap存在文件中, 并保存下每个表当前查询到的最大id. 以后再次执行时就在上次查询的最大id基础上依旧多goroutine并发查询uid数据并写入一个新的bitmap, 最后对两个bitmap进行or操作, 就得到了当前的全量去重uid.

~这里goroutine的并发数量设置为cpu数量的2倍. id步长递增量拍脑袋设的10000. ~

这里跑个题, 由于go数据库连接使用的连接池, 不需要考虑每次请求都重新建立tcp连接. 而每个IP包能实际携带的tcp数量量在1460B以下, 实际可能就只有1400B, 每个uid都是8B, 这样一算一个IP包就最多能携带175个数据, 这还要不考虑其他协议的数据, 所以如果想让每个tcp都不分片, 都刚好被一个IP包承载, 就需要每次取数据量在175以下.真的这样可以最大优化吗? 实际上不是, 每批数据量很小, 每次都要经过操作系统的层层传递, 还不如一次性把大量的数据拿过来, 这样不用每个goroutine的请求都要经过两端操作系统的各种数据传递, 数据的解析执行, 数据库中各种数据读取操作. 反而性能会更好.

实际测试, 100多万的数据, 直接一次请求获取需要1.92s左右, 比我人工批量取100万个要好很多.

另外由于goroutine本身除了垃圾处理和内存占用外, 只要没被调度, 就没什么消耗, 可以尽量创建, 不需要人工设置一个太小的上限, 当然, 如果为了控制内存和性能, 还是要有个上限, 这个上限可以大很多. 就如Why goroutines instead of threads?: 中所说, 在同一个地址空间中创建数十万个goroutine是很实际的。在4 GB内存的计算机上，goroutine的最大数量限制大约为略少于100万的数字。每个goroutine大约占用4KB多的栈空间, goroutine的初始栈空间, 在1.2的时候扩到8K(2个操作系统page), 在1.4的时候又减到2K, 这些变化是由于分段堆栈在段之间快速来回切换时造成了性能问题(“热堆栈分割”), 当分段的堆栈被替换为连续的堆栈后就在1.4中减少到2k了.

所以可以尽可能的创建goroutine, 但是实际使用的时候就会遇到操作系统的limit瓶颈, 如果操作系统限制了open file的数量, 那么将在达到限制后无法创建更多的网络请求, 也就导致goroutine的执行数量被限制. 可参考这里

因此, 最后确定了设置并发上限为10000, 并且一次尽可能多的请求数据(1干万数据大约77MB,一次请求1千万).

最终在千兆带宽的内网服务器上执行效果是11.317s跑完首次数据写入, 其后如果间隔10分钟执行则只需0.682s.

去重后uid数据量为100多万

存储的bitmap文件大小: 2.6M. 如果使用map的数据结构存储, 每个key都是8B, 那么这100多万数据就要7.63M的空间了, 再加上value的空间就更大了. 可见roaringbitmap的威力.