【VictoriaMetrics源码阅读】vm中仿照RoaringBitmap的实现：uint64s

2022-03-23 00:00:00 集合 元素 数组 查找 交集

作者:张富春(ahfuzhang)，转载时请注明作者和引用链接，谢谢！

  • cnblogs博客
  • zhihu
  • 公众号:一本正经的瞎扯

正文

VictoriaMetrics中使用uint64类型来表示一个MetricID，且MetricID是递增的。
因此有这些一些需求：

  1. 需要缓存某一类metricID的集合，例如某个MetricQL的查询结果对应很多个MetricID;
  2. 需要对多个metricID的集合取交集和并集等操作。

并且：

  • 占用的内存要尽可能的小
  • 要避免大量的小对象，否则会对GC造成很大压力
  • 插入、检查是否存在某个ID、并集计算、交集计算等要尽可能的快

VictoriaMetrics-1.72.0-cluster/lib/uint64set/uint64set.go 这里的代码很好的满足了上述需求。
下面我来分析它的实现原理。

1.结构

  • 整个uint64按位分成多个部分，每个部分分别采用各自的插入和查找策略。相当于分级存储。
  • 高32位先建一个桶
    • 桶的个数动态增加
    • metricID是递增的，因此在这样的业务场景下，高32位通常是0


  • 高16位再建一个存储桶，这里的策略与上面相似。
    • 桶的个数动态的增加
    • 通常桶内的值是顺序增加的，插入过程只能顺序查找
    • 在做集合计算的阶段，可以先对桶排序。


  • 低16位的处理稍稍复杂一些：
    • 当元素个数在56个以内时，直接在一个uint16的数组里顺序追加和顺序搜索
    • 当元素超过56个时，建立一个1024个元素的数组，数组的元素是uint64类型
    • uint64类型一共64个位，用每个位来代表0-63的某个值。相比用64个uint8来存储，空间节省了8倍。


2.插入过程

  • 先确定高32位的分桶（如果没有就新增这个分桶）
  • 在32位的分桶上，再确定高16位的分桶（如果没有就新增这个分桶）
  • 在16位的分桶上，检查是否在56个元素以内
    • 56个元素以内，直接在[]uint8数组上追加
    • 超过56个元素，创建1024个元素的uint64数组，并把56个元素添加进去


  • 16位的分桶上，通过前10位值作为下标，确定uint64数组的位置
  • 把低6位的值，转换为一个uint64上的mask(值为N就把第N位置1)，然后与上一步确定的uint64取bit or运算

3.查找过程

  • 先确定高32位的分桶
  • 再确定高16位的分桶
  • 如果不存在1024个元素的分桶，就在56个元素的数组里面顺序查找
  • 如果存在1024个元素的分桶，根据高10位获得下标
  • 根据低6位，看uint64中对应的位是否是1

4.交集运算过程

  • 先对a,b两个集合的32位分桶进行排序
  • 依次偏移a,b两个集合32位分桶的下标，直到分桶值对齐
    • 通过分桶的匹配，可以快速淘汰大量的值


  • 32位分桶的值相等后，继续比较高16位的分桶。比较方法与上面相同。
  • 低16位的值，比较1024个元素的数组。两个uint64做bit and运算，即可完成取交集。

5.总结

  1. uint64set类，首先考虑了业务场景。在绝大多数高32位都相同的大量数据的情况下，能够取得很好的效果。
  • 相反：如果是大量随机的uint64值，这里的方法不见得会更好
  1. 相比map而言，插入和查找做不到O(1)的性能，但是分段查找也不会太差
  2. 相比map而言，内存上的好处非常多：
  • 数据的扩容方便且快速，map可能需要多次扩容+rehash才行
  • 更加节约内存
  • 对GC的压力很小
  1. 对并集、交集等集合操作，分桶能够快速避开不合适的数据的比较，性能极高。

如果想看具体的源码的注释，请移步我上传的VM注释版的源码。

来源 https://zhuanlan.zhihu.com/p/468222528

相关文章