写点什么

深入浅出时序数据库之压缩篇

  • 2017-06-04
  • 本文字数:2757 字

    阅读完需:约 9 分钟

物联网邻域近期如火如荼,互联网和传统公司争相布局物联网。作为物联网邻域数据存储的首选时序数据库也越来越多进入人们的视野,而早在 2016 年 7 月,百度云在其天工物联网平台上发布了国内首个多租户的分布式时序数据库产品 TSDB,成为支持其发展制造,交通,能源,智慧城市等产业领域的核心产品,同时也成为百度战略发展产业物联网的标志性事件。

前面我们有讲过时序数据库的存储篇(点击可查看):百度无人车和天工物联网都使用了时序数据库,但是你有多了解时序数据库?

和时序数据库的预处理篇(点击可查看):时序数据库如何支持秒级上亿数据的查询分组和聚合运算

压缩对于时序数据库是至关重要的。因为时序数据库面对的物联网场景每天都会产生上亿条数据。众所周知,在大数据时代的今天数据的重要性是不言而喻的,数据就是公司的未来。但如果无法对这些时序数据进行很好的管理和压缩,那将给客户带来非常高的成本压力。

如前文提到的,工业物联网环境监控方向的客户,一年产生 1P 的数据,如果每台服务器 10T 的硬盘,那么总共需要 100 多台。按照每台服务器 3 万来算,一年就需要 300 万的支出,这还不包括维护人员的成本。

压缩是个非常大的话题,本文希望能够先从大的宏观角度给出一个轮廓,讲述压缩的本质,压缩的可计算性问题。再从时序数据压缩这一个垂直领域,给出无损压缩和有损压缩各一个例子进行说明,希望能够抛砖引玉。

压缩的故事

先来讲个有关压缩的故事,外星人拜访地球,看中了大英百科全书,想要把这套书带回去。但这套书太大,飞船放不下。于是外星人根据飞船的长度,在飞船上画了一个点。这样外星人心满意足的返回了自己的星球,因为这个点就存储了整个大英百科全书。

这个并不是很严谨的故事,却道出了压缩的本质:用计算时间换取存储空间。外星人在飞船上画的点非常有技术含量,可以说是黑科技,代表一个位数非常长的不循环小数。而这串数字正代表了整个大英百科全书的内容。

压缩的两个问题

再来回答两个宏观的问题,帮助我们认识在压缩这件事上哪些是我们能做的,哪些是不能做的。

第一个问题:是否存在一个通用的压缩算法(Universal Compression),也就是说某个压缩算法能够压缩任意的数据。答案是否定的,并不存在这样的通用压缩算法。

用反证法可以做个快速的证明。假设存在通用的压缩算法,也就是说有个压缩算法,对于长度为 n 的字符串,总能压缩到长度小于 n 的字符串。总共有 2^n 个长度为 n 的不同字符串;但却只有 2^n-1 个长度小于 n 的字符串。那么必定存在两个长度为 n 的字符串 A,B,经过压缩得到同一个字符串。这样解压缩算法没有办法正确的解压。所以假设错误,并不存在通用的压缩算法。

第二个问题:是否能写出一个函数,输入字符串,可以得到这个字符串最短表示的长度。答案也是否定的,也就是说我们无法证明某个算法是最好的算法。柯尔莫哥洛夫复杂性的不可计算性解释的就是这个问题。用的也是反证法,有兴趣的朋友可以自行百度了解(注 1)。

这两个问题的答案,告诉我们三件事情,

  1. 压缩算法的选择需要具体情况具体分析,不可压缩的字符串总是存在。
  2. 不要妄图获得最好的压缩算法,它是不可计算的。因为总有你想不到的压缩算法存在。举个例子,[一百万个 0 的字符串,以“foo”作为 key,经过 AES 加密算法的 CBC 模式得到的字符串]。这串字符串看起来完全是随机的,不可压缩的。但我却用 43 个中文(中括号之间的内容)就表示了出来。
  3. 压缩是件很难很有技术含量的事情,需要不断的挖掘,才能将他做到更好。

时序数据压缩

针对不同的数据,会有不同的压缩,大致压缩的对象可以分为文档、音频、视频等。如果直接采用文档的压缩算法用于时序数据,效果并不理想。下图是一些常用的压缩算法的 benchmark,可以看到压缩率那一栏最高也只能够达到 3 左右的压缩率(压缩率 = 原始数据大小 / 压缩后的数据大小)。更多压缩算法可以查看注 2。

如果要得到更好的压缩率,我们需要采取更加适合时序数据的压缩算法。时序数据的压缩可以分为无损压缩和有损压缩。

无损压缩

无损压缩是说被压缩的数据和解压后的数据完全一样,不存在精度的损失。对数据的压缩说到底是对数据规律性的总结。时序数据的规律可以总结为两点:1、timestamp 稳定递增、2、数值有规律性,变化稳定。下面来举个例子。

上图是一组时序数据,如果我们一行一行的看感觉压缩有点困难,但如果我们一列一列的看,压缩方案就呼之欲出了。

先看 timestamp 那一列是等差递增数列,可以用 [1467627245000,1000,4] 来表示。1467627245000 代表了第一个时间,1000 代表后一个时间比前一个时间的大 1000,4 代表了这样的规律出现了 4 次。如果一共有 100 个这样规律的 timestamp,那就意味着,我们用 3 个 Long 型就可以表示出来。timestamp 压缩率高达 33。

再进一步观察看 value 那一列,如果取差值,可以得到(6,-5,2,-5),全部都加 5 得到(11,0,7,0),这些数值都可以用 4bit 来表示。也就是用 [23,5,4,0xb0700000] 来表示(23,22,24,25,24)。其中的 4 代表后续一共有 4 个数。如果这样的规律一直维持到 100 个 Int 的 value,就可以用 16 个 Int 来代表,压缩率高达 6.3。

具体的情景会复杂很多,在此只是简单举个例子。InfluxDB 无损压缩算法在其页面上有完整的阐述(注 3),可以配合开源源码进行更加深入的理解。针对于浮点数类型,Facebook 在 Gorilla 论文中(注 4)提到的非常高效的无损压缩算法,已经有很多文章进行分析。InfluxDB 对于浮点型也采用这个算法。

有损压缩

有损压缩的意思是说解压后的数据和被压缩的数据在精度上有损失,主要针对于浮点数。通常都会设置一个压缩精度,控制精度损失。时序数据的有损压缩的思路是拟合。也就是用一条线尽可能的匹配到这些点,可以是直线,也可以是曲线。

最有名的时序数据有损压缩是 SOIsoft 公司的 SDA 算法,中文称为旋转门压缩算法。

在上图中,红色的点是上一个记录的点,空心的点是被丢掉的点,绿色的点是当前的点,黑色的点是当前要记录的点。

可以看到图左边,当前点和上一个记录点以及压缩精度的偏差值形成的矩形可以包含中间的点,所以这些点都是可以丢掉的。

再看图右边,当前点和上一个记录点形成的矩形无法包含中间的点,所以把上一个点记录下来。如此进行下去,可以看到,大部分的数据点都会被丢掉。查询的时候需要根据记录的点把丢掉的点在插值找回来。

有损压缩除了可以大幅减少存储成本。如果结合设备端的能力,甚至可以减少数据的写入,降低网络带宽。

总结

虽然判断压缩算法最优是不可计算的,但是设计好的压缩算法仍然是可计算的问题。可以看到,前面提到的时序数据的无损压缩有损压缩算法都会基于时序数据的特征采取方案,达到更好的压缩率。现在 deep learning 非常的火,让人很好奇它是不是可以给数据压缩带来新的方案。

注 1:请点击

注 2:请点击

注 3:请点击

注 4:请点击

2017-06-04 17:369410

评论

发布
暂无评论
发现更多内容

Mac教程:如何开启任何来源选项

魔仙苹果mac堡

Mac 苹果电脑 任何来源

K8S部署应用详解

tiandizhiguai

设备使用HTTPS协议接入IoT物联网平台——设备接入类

阿里云AIoT

跨平台开发成为移动应用程序开发趋势

没有用户名丶

企业不想走弯路,不如试试低代码开发

引迈信息

低代码 低代码开发 JNPF

Last Week in Milvus

Zilliz

Milvus Zilliz 向量数据库

业务架构那点事(2)如何通过高层访谈获取企业战略信息?

涛哥 数字产品和业务架构

业务架构 访谈

如何在 macOS 中互换 Control 和 Command 键

魔仙苹果mac堡

mac教程 Control键 Command 键

Acrobat Pro DC 2023发布,有哪些新的改进?

Rose

adobe pdf编辑器 Acrobat Pro DC 2023

直播教学!20 分钟开发可视化「智能门铃」丨RTE 开发实战课 • 第一期

声网

最佳实践 直播 RTC 声网

面面俱到!四面阿里拿offer后,才发现师哥给的面试笔记有多强大

做梦都在改BUG

Java java面试 Java八股文 Java面试题 Java面试八股文

如何在 macOS 中互换 Control 和 Command 键

春天的风暖暖的

国家中心城市手机银行发展洞察

易观分析

金融 经济 手机银行 城市

OPPO、京东云 loT 项目数据架构改造,数据处理痛点这样破解

TDengine

tdengine 数据架构 时序数据库 用户案例 loT

通过Flutter实现一个能在多端运行的扫雷游戏

编程的平行世界

flutter 前端 游戏 移动端 扫雷

订阅标识符与订阅选项--MQTT 5.0新特性

EMQ映云科技

物联网 IoT mqtt 订阅 企业号 3 月 PK 榜

亿级用户中心的设计与实践

做梦都在改BUG

Java 服务架构 亿级流量 用户中心

SpringBoot项目就连创建目录都让人抓狂

做梦都在改BUG

Java Spring Boot 框架

支付宝小程序-MQTT模拟器体验阿里云IoT开发——设备接入类

阿里云AIoT

物联网

ElasticSearch必知必会-Reindex重建索引

京东科技开发者

elasticsearch 索引 ES 集群 企业号 3 月 PK 榜

喜讯|百度入选“移动互联网APP产品安全漏洞治理”优秀案例

百度安全

中国流程挖掘迎来新“启点”,望繁信科技全面升级

ToB行业头条

React数字滚动组件 numbers-scroll

观纵科技

JavaScript 前端监控 React

使用抓包工具Wireshark分析IoT设备网络行为——设备管理运维类

阿里云AIoT

网络协议 物联网 网络性能优化

交易系统之数据库弱依赖解决方案

京东科技开发者

数据库 高并发 灾备 db 企业号 3 月 PK 榜

解决 Parallels Desktop 虚拟机不能连网的问题

魔仙苹果mac堡

Parallels Desktop 虚拟机 PD虚拟机不能联网 PD常见问题

真香!阿里最新出品Java面试核心讲(终极版),Github已星标50K

程序员小毕

Java 程序员 面试 后端 架构师

CleanMyMac4.20专业的mac清理软件

茶色酒

CleanMyMac4.20

VPN客户端Shimo mac版使用教程:如何创建新的 VPN 帐户?

Rose

vpn mac系统 Shimo下载 Shimo教程

AntDB数据库助力中国移动华南中心计费项目

亚信AntDB数据库

AntDB 国产数据库 aisware antdb AntDB数据库 企业号 3 月 PK 榜

金三突击面试,收获6个Offer,原来面试还能这么简单!

做梦都在改BUG

Java java面试 Java八股文 Java面试题 Java面试八股文

深入浅出时序数据库之压缩篇_数据库_百度云时序数据库资深工程师_InfoQ精选文章