如果产品中需要压缩功能,我们应该如何选择压缩算法?

看过很多压缩相关的技术文章,大家都在讲各种压缩算法的技术实现原理及各压缩算法之间的压缩率的对比,哪个压缩算法好等等。这些技术文章非常好,可以指引我们在技术上不断钻研。本文将从另外一个大家讲的还比较少的角度,和大家一起探讨下如何在产品中使用好压缩算法。

一、认识压缩算法

1 压缩算法的历史

压缩算法的历史,如同压缩算法一样,闪耀着神奇奥妙的光芒。

最早使用压缩概念的是 19 世纪中期的摩尔斯码,在当时还是使用电报进行信息传输的,电报传输信号速度非常慢,摩尔斯意外发现大部分英文单词中使用某些字母的频率特别高,所以就想到用短的脉冲信号去代替出现频率高的字母,这样就能在更短的时间内发送出去更多的信息,这个想法也就是最早出现的压缩算法的概念了。

过了 100 多年后,香农(Claude Elwood Shannon)发表了著名的“通信的数学原理”论文,最早提出了信息熵的概念,建立了信息度量与压缩的理论基础。

香农是信息论的创始人,数学家,同时也是爱迪生的远房亲戚(这一家族肯定是祖坟上冒青烟了)。

为什么压缩和他有关呢,因为信息量的度量公式就是由他推导出来的。大家知道物体的重量是可以通过称重准确得到的,对于看不见摸不到的信息量如何度量呢?香农就是带着这个问题在不断探索和钻研,在参考了当时把热量成功度量出来的热力学第二定律的理论基础上,创建了信息熵计算公式,成功的让看不见的信息量也能够像物体的重量一样可以准确的称出来了。

同时他也是我们现在最常见的比特位的创建者,使用 0 和 1 两种状态来表示最短的信息量(如同世界上的有和无一样),也就是信息的最小单位。咱们现在使用的 byte,也是在其基础上的一个扩展应用。同时他的公式也是第一次用数学语言阐明了概率与信息冗余度的关系,简单来说,就是你一句话的意思用不同方式重复说了三遍,实际还是一句话的信息量,重复不带来信息量。

几年之后,哈夫曼(David A. Huffman)在 1952 年提出了 Huffman 编码,这个发明在压缩算法界里算是里程碑式的,它让前面的理论可以实实在在的落地。Huffman 编码并不是新理论,而是对早在 100 多年前就提出的摩尔斯码理论的一个非常巧妙的应用。

Huffman 编码仍然使用最初由摩尔斯提出的核心压缩理论,即频率高的用短码表示,频率低的用长码表示。但短码如何编码、长码如何编码及如何最小化信息量传输,这些问题在之前一直困扰着人们,而哈夫曼设计的 Huffman 树,让这些问题都得到了完美解决。

后来像 UNIX 上的 compact、DOS 中的 SQ,都是基于 Huffman 编码实现的,再后来出现的 WinRAR 和 GZIP 中也能看到 Huffman 编码的身影。

同时,在那几年还出现了费诺编码。费诺编码是在香农编码的基础上改进的,目的是减小编码长度。它按概率对信号源进行排序,然后对信号源进行切分,预期是切分后的两部分内信息源概率之和最接近为最佳。用这种方式编码后的码长会小于香农编码。它是一种概率匹配编码,并不是最佳编码方式。

字典编码大约是在 1997 年出现的,Abraham Lempel、Jacob Ziv 发表了他们开创性的 LZ77 算法,这是第一个使用字典数据的算法。LZ77 使用了一种叫滑动窗口的动态字典。1978 年,同样是这两个人又发布了他们的 LZ78 算法,该算法也使用了字典,与 LZ77 不同的是,该算法会解析输入数据并生成静态字典,而不是随时生成的动态字典。

多媒体出现后,压缩算法又出现了有损压缩技术,有损压缩是通过牺牲图像质量获得流畅的体验,解决了多媒体文件普遍过大导致播放时卡、慢等现象。

2 常用的压缩软件

压缩软件大家并不陌生,Windows 下常用的压缩软件有 WinZip、WinRAR、cab 和 7z 这些, Linux 下常用的有 tar、zip、gzip 和 bzip2 等软件。这些软件为了提升压缩率,会使用多种压缩算法来实现。即便是相同的压缩算法,在不同软件中的实现可能也会有较大差别,进而有优劣之分,这也就是为什么使用相同压缩算法的压缩软件之间压缩率及性能差别很大的原因了。

3 压缩算法的分类

二、压缩算法特点与本质

压缩算法的特点如下:

1)新压缩算法总是在不断涌现

2)压缩率与压缩速度总成反比

3)不同数据源对压缩率影响很大

 

压缩的本质是对信息进行再编码,即相同信息使用另一种更简洁的方式重新表达。

人们在生活中到处可以看到一些压缩方法,同时也在不知不觉中使用着,如简称就是一种典型的压缩方法。“中华人民共和国”我们就简称为“中国”,“中国交通管理局”我们也习惯用“交管局”来表示,使用简称让我们提高了效率。这些压缩方法通常也需要带着一个固定的词典,在词典中把“中国”再翻译回原来的“中华人民共和国”,简称的词典都装在我们每个人的脑子里,所以可以相互交流。

三、压缩算法的使用

1 常见的使用不妥的地方

我观察到的大部分压缩算法使用不妥的地方是对自己的数据不了解,同时对所使用的压缩算法的原理也没有理解,只是看到评测文章说哪个压缩算法好,就花不少精力移植到自己的项目中,结果一跑和预期相差甚远。

为什么会出现这种现象呢?主要是你的数据和评测的数据不一样。抛开压缩对象说压缩算法如何牛,就是在耍流氓。有人可能要说了,我这压缩算法不管你是什么数据,我都能压缩得很好。那好,我给你的数据就是你压缩后的数据,看你还能不能再压下去。

所以,压缩算法一定是要和压缩对象紧密关联的,只有了解清楚自己的数据,才能压出好效果。

2 正确的使用方法(一核二平原则)

我认为正确地使用压缩算法,要抓好一个核心、做好两个平衡。

一个核心,就是紧紧抓住数据的特点,根据特点选择合适的压缩算法。两个平衡,一个是要做好压缩速度与压缩率的平衡,二是做好投入与收益的平衡。

 

下面我分别展开来详细描述下:

一个核心

如何抓好一个核心,关键是洞察及发现自己数据的特点,并有效利用好这些特点。这里我以 TDengine 中的压缩算法为例。

TDengine 是处理时序数据的数据库,时序数据的两个特点:

  1. 采集的数据都是时序的

  2. 采集的数据大多是在一定范围内波动的

根据以上这两个特点,我们在数据存储的时候采用了列式存储。列式存储可以让相同类型的数据尽可能地放在一起,这就为下一步的高效压缩创造了条件。

按列压缩的时候,我们会根据不同列的数据类型采用不同的压缩算法:

  • 时间序列类型:我们利用了时间序列数据的稳定增长且有固定差值的两个特点,选择使用 delta-of-delta 压缩算法,此压缩算法记录的是差值的差值,如果我们采集的频次是固定的且为 1 秒一次,用此算法编码后需要记录的值将全部是零,这样就可以极大减小要保存的实际信息量了。

  • 整数类型:设备采集的整数类型一般都是自然界产生的常量数据,如温度、湿度、电压、电量等。这些数的共同特点是绝对值都相对较小,并在一定范围内波动。针对这些特点,我们对整数类型的数据采用了小整数编码(ZIG-ZAG)技术配合前导零记录(simple8B)的压缩技术,实现信息量的压缩。ZIG-ZAG 把原来前置的符号位后移,把有值部分尽可能凑一起,让更多的 0 可以成片连接起来,方便压缩。

  • 字符串数据类型:时序数据库中存储的字符串类型的数据,一般都是设备编号或者设备名称等,这些名称大部分习惯使用英文字母+数字来表示,我们使用通用的字符串压缩算法,实现了这部分数据的压缩。

还有其它各种类型的数据,如 float、bool 类型等,我们都采用了适合其数据特点的压缩算法,得到了较好的压缩效果。

TDengine 中的压缩算法,紧紧抓住不同类别数据的特点,使用最适合这类数据的压缩算法,达到了 TDengine 的超高压缩率和超高压缩性能,是一个核心理念的典型应用。如果大家对具体实现感兴趣,也可以参考 TDengine 的源代码(https://github.com/taosdata/TDengine)。

两个平衡

  1. 压缩速度与压缩率的平衡

压缩率越高越好,这个标准只存在于技术领域纯谈技术之时。

在实际生产生活中,必须要和它的另一个矛盾面——压缩速度——结合起来看。在不断提高压缩率的同时,压缩速度必然要跟着下降,使用者需要根据自己的实际应用情况,在两者间把握和拿捏出一个好的平衡点来,达到既不会太影响业务处理速度,也可以收获一个好的压缩率的效果,从而节约存储空间。

TDengine 在处理这个问题时,是优先要保证采集数据的流量峰到来时,压缩数据这一环节不会存在数据积压现象,并且还要留有 10%的处理空间。要保证采集数据实时入库的核心业务通畅是优先级最高的,其次才是尽可能把数据压缩下来,为用户节约磁盘空间。

也就是说,TDengine 拿捏这个平衡度,是按主要矛盾、次要矛盾的权衡观点来处理的。对于不同的业务,这个平衡点是不一样的,需要自己把握好。

  1. 投入与收益的平衡

另一个要把握好的平衡就是投入与收益。处理大型业务数据的压缩,通常我们会选择多种压缩算法和压缩策略来实现。对业务数据切分的越精细,选择的压缩算法及策略就越准确,压缩率和压缩性能也会越高。

优化压缩算法和压缩策略,是一条永无止境的道路:大模块层面优化不下去,可以优化小模块;小模块完了,还可以优化小模块里的每个函数;函数完了还有汇编层面的优化。

那我们要不要把压缩算法一直优化下去呢?

我觉得这个需要在投入与收益之间找到一个平衡点。压缩算法的优化有这样的规律,前期投入 10 分的人力,能优化出 20 分的成绩,后期投入 10 分的人力,有可能只能优化出 5 分的成绩。

我们需要评估在产品或项目中压缩所占据的位置、压缩对上下游环节的影响程度,做出一个合理的优化截止点出来。比如说有些产品或项目中的压缩功能,并不是很重要,只是一个辅助功能,比如说一些定期备份压缩存储的功能,用到的频率也不高,只有出问题时才会读取出来用一下,像这样的应用中没必要投入太大精力把压缩优化到极致,这个功能并非产品关键功能,快速地构建一个功能稳定的压缩方法应该就可以了。

TDengine 中的压缩环节对整个产品而言还是比较重要的:一是使用频繁,读写查询都在不断调用;二是压缩率的大小决定了能给用户节约多少硬盘,直接关系着用户的存储成本;三是压缩算法性能决定着用户数据写入及查询的速度,都是产品核心功能。

所以我们在这方面投入的资源是比较大的,不断优化压缩算法,不断提升压缩率和压缩性能。但我们也不会无限制地投入大量人力在这块儿,而是会根据公司的当前规模及人员情况,做到一个合理的截止点即可,后续仍然保留着需要投入更多资源去优化的空间。

四、总结

前面介绍了压缩算法的历史、分类及特点后,又重点介绍了压缩算法的使用,抛出了自己的观点,旨在引导大家在产品中正确地使用压缩算法。

如果实在记不住太多东西,读完这篇文章,我希望你能记住四个字——“一核二平”,这样就应该有所收获了。使用压缩算法时要抓住数据特点这一个核心,然后平衡好压缩率与压缩速度,平衡好投入及收益就好了。

 

作者简介:

段宽军,涛思数据高级架构师。主要负责流计算、数据存储、压缩算法等相关的工作。

本文文字及图片出自 InfoQ

本文文字及图片出自

你也许感兴趣的:

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注