一些数据压缩手段

我们知道,外存(硬盘)的性能远远低于内存,即使是同样复杂度的运算(CPU 计算量相同),如果能减少外存的访问量,也会大大提高整体性能。甚至有时我们需要用 CPU 换硬盘,即宁可多消耗些 CPU 时也要减少硬盘访问量,一方面 CPU 性能更好,另一方面是 CPU 比硬盘更容易并行,现代计算机的 CPU 核数常常远远超过硬盘的并发访问能力,数据密集型的任务应当更多地使用 CPU 的能力。

如果能物理地减少数据存储量,也就自然而然地减少了外存访问量。


列存是常见的减少外存访问量的手段,不过,仅仅是简单地采用列式存储,并不会真正地减少数据存储量。但是,使用列存之后,数据的可压缩性将大大提高。同一列的数据一般具体有相同的数据类型甚至近似的取值,大多数压缩算法在这种情况的工作效果要比针对杂乱类型数据时好很多,这样就能大幅度地减少数据存储量了。所以,列存不仅是在访问量上占便宜,即使访问表中所有列,列存的硬盘读取量要也比行存更少。在表的列数不多时,列存仍然有优势。

通用的压缩算法不能假定数据有某种特征,只能是将数据当作随意的字节流去编码,有时并不能获得最好的压缩率。而且,高压缩率的算法常常会消耗过多的 CPU,甚至于会到了拿 CPU 换硬盘都不划算的地步。所以,我们不能完全指望压缩算法,还要自己先对数据做一些手脚,人为地制造某些数据特征来利用,就可以采用较低压缩率同时低 CPU 消耗的压缩算法,也获得较好的压缩效果。


一个常用的办法是排序。

数据表的列中常常有许多是维度,比如地区、日期等。这些维度的取值基本都在一个小集合范围内,在大数据量时会有很多重复取值。如果数据是按这些列排序的,则相邻记录之间取值相同的情况就很常见,而这时使用很轻量级的压缩算法也能获得很好的压缩率,简单来讲,直接记录列值及其重复次数都能起到不错的压缩效果。

排序时的次序也有讲究。要尽量把取值较长的列放在前面排序。比如有地区和性别两个列,地区的取值长度要大于性别,则先地区后性别排序的效果就要好于反过来的情况。

先地区排序:

北京 赵大
北京 钱二
北京 孙三
上海 李四
上海 周五

先性别排序:

北京 赵大
北京 钱二
上海 李四
北京 孙三
上海 周五

前者存储:北京(3 个),上海(2 个);男(2 个),女(1 个),男(1 个),女(1 个);总字符数为 8(只数字符个数,括号中的次数不记)。

后者存储:北京(2 个),上海(1 个),北京(1 个),上海(1 个);男(3 个),女(2 个);总字符为 10。

地区的字符数比性别要长,把长的排到前面的存储量会更小。


上面的例子中,我们还可以把”北京”、”上海”这些字符串事先转换成数字编码,而不要直接使用原始字符串,这样也能减少存储量。”北京”是个 2 个字符的串,如果用数字 1 代替就变成 1 个字符了。有些枚举形字符串列的取值很长,转换成数字编码会有很好的效果。做了编码转换后,在使用的时候会有些麻烦,需要再转换回来。不过,和获得的性能提升相比,这些麻烦还是值得的。

整数(从字符串编码而来或本身就是整数)的存储也有些技巧。现代计算机的整数一般是 32 位的,要占 4 个字节。但很多整数很小,比如从省份转换过来的整数不会超过 100,这 4 个字节的高 3 字节全是 0,有些浪费;性别转换过来的只有 1 和 2 两种,而 4 个字节的整数甚至长于 1 或 2 个字节的“男”,”女“值本身了,这个转换反而不划算了。

这时候就要设计合理的编码方式,不要让所有整数都占用同样长度的空间,让小正整数只用 1-2 个字节就能表示,大正整数以及负整数(负数很罕见)才要占满 4 个字节,甚至 5 个字节(否则信息空间是不够的),因为小正整数更常见,整体存储空间还是会变少。

类似的技巧还可以用于日期存储上,一般来讲与某个确定日期距离较近的且过去的日期会更多一些,这时可采用某种编码方式让这些值变短,而距离远的以及将来的日期可以使用长编码。

这些编码方案看起来很不起眼,一次只能减少一两个字节,但当数据量很大时效果就相当可观。


对于应用程序员来讲,一般不会直接控制到这种细节层面了。不过,了解所选用的数据库(或别的有数据存储功能的产品)采用的压缩手段还是有必要的,这样才能更准确地预估运算性能。