0
0

slimarray: gzip的压缩率, 即时访问

张炎泼(xp) 发表于 2020年11月15日 08:00 | Hits: 450
Tag: algo | array | 数组 | compress | succinct


slimarray

场景和问题

在时序数据库, 或列存储为基础的系统中, 很常见的形式就是存储一个整数数组, 例如slim这个项目按天统计的 star 数:

Stargazers over time

这类数据有有很明显的统一的变化趋势, 对这类数据的存储, 我们可以利用数据分布的特点, 将整体数据的大小压缩到几分之一 . 这就是slimarray要做的事情.

使用slimarray, 可以将数据容量减小到gzip差不多的大小, 同时还能允许直接访问这些数据! 测试中我们选择了2组随机数, 以及现实中的2份数据, 一个ipv4的数据库, 一个slim的star变化数据, 服用slimarray后效果如下:

Data size Data Set gzip size slimarry size avg size ratio
1,000 rand u32: [0, 1000] x 824 byte 6 bit/elt 18%
1,000,000 rand u32: [0, 1000,000] x 702 KB 5 bit/elt 15%
1,000,000 IPv4 DB 2 MB 2 MB 16 bit/elt 50%
600 slimstar count 602 byte 832 byte 10 bit/elt 26%

在达到gzip同等压缩率的前提下, 构建 slimarray 和 访问的性能也非常高:

  • 构建 slimarray 时, 平均每秒可压缩 6百万 个数组元素;
  • 读取一个数组元素平均花费 7 ns/op.

本文手把手的介绍slimarray的原理, 实现:

初步想法: 前缀压缩

假设我们有一个包含4个元素的uint32的整数数组:

nums = [1006, 1005, 1007, 1010]

前缀压缩的思路就是把每个元素的公共部分提取出来单独存储, 这样每个单独元素就只需要存储它跟公共部分差异的部分, 从而大大降低存储空间. (因为公共部分在大多数情况中都在前面(例如现实中大部分被存储的数据都是排序的, 或近似于排序的), 所以一般提取公共部分的压缩都是前缀压缩)

在这个例子中, 我们看到最小的数是1005, 那么就把它作为公共部分提取出来, 再单独存储每个数字剩余的部分(和prefix的差异), 最后存储的内容如下:

{
  Prefix: 1005
  deltas: [
    1,
    0,
    2,
    5
  ]
}

可以看到这种表示方法中, 固定的部分Prefix大小不变, 影响整个存储效率的是deltas, 而它只需要记录每个原始值跟前缀之间的差, 最大是5, 也就是说每个delta 只需要3 bit 就够了.

当数据较多时, 均摊空间开销将近似于3 bit/elt.

现在我们换一个视角, 我们可以把要存储的数值看做是一个坐标系中的4个点: 横轴表示数组下标, 纵轴表示数字的值.

于是前缀压缩就可以看成是: 记录一条水平直线(y = 1005), 再记录数组中实际数值跟这条直线之间的y轴方向距离:

y = 1005
num[0] = y(0) + 1 = 1006
num[1] = y(1) + 0 = 1005
num[2] = y(2) + 2 = 1007
num[3] = y(3) + 5 = 1010
                                                (3, 1010)







                                    (2, 1007)

            (0, 1006)

........................(1, 1005)...........................

原文链接: https://blog.openacid.com/algo/slimarray/

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)