如何更高效地压缩时序数据？基于深度强化学习的探索

随着移动互联网、IoT、5G 等的应用和普及，一步一步地我们走进了数字经济时代。随之而来的海量数据将是一种客观的存在，并发挥出越来越重要的作用。时序数据是海量数据中的一个重要组成部分，除了挖掘分析预测等，如何高效的压缩存储是一个基础且重要的课题。同时，我们也正处在人工智能时代，深度学习已经有了很多很好的应用，如何在更多更广的层面发挥作用？本文总结了当前学术界和工业界数据压缩的方法，分析了大型商用时序数据压缩的特性，提出了一种新的算法，分享用深度强化学习进行数据压缩的研究探索及取得的成果。

深度学习的本质是做决策，用它解决具体的问题时很重要的是找到契合点，合理建模，然后整理数据优化 loss 等最终较好地解决问题。在过去的一段时间，我们在用深度强化学习进行数据压缩上做了一些研究探索并取得了一些成绩，已经在 ICDE 2020 research track 发表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口头汇报。在这里做一个整体粗略介绍，希望对其它的场景，至少是其它数据的压缩等，带来一点借鉴作用。

背景描述

1 时序数据

时序数据顾名思义指的是和时间序列相关的数据，是日常随处可见的一种数据形式。下图罗列了三个示例：a）心电图，b）股票指数，c）具体股票交易数据。

关于时序数据库的工作内容，简略地，在用户的使用层面它需要响应海量的查询，分析，预测等；而在底层它则需要处理海量的读写，压缩解压缩，采用聚合等操作，而这些的基本操作单元就是时序数据 <timestamp, value>，一般（也可以简化）用两个 8 byte 的值进行统一描述。

可以想象，任何电子设备每天都在产生各种各样海量的时序数据，需要海量的存储空间等，对它进行压缩存储及处理是一个自然而然的方法。而这里的着重点就是如何进行更高效的压缩。

2  强化学习

机器学习按照样本是否有 groundTruth 可分为有监督学习，无监督学习，以及强化学习等。强化学习顾名思义是不停地努力地去学习，不需要 groundTruth，真实世界很多时候也没有 groundTruth，譬如人的认知很多时候就是不断迭代学习的过程。从这个意义上来说，强化学习是更符合或更全面普遍的一种处理现实世界问题的过程和方法，所以有个说法是：如果深度学习慢慢地会像 C/Python/Java 那样成为解决具体问题的一个基础工具的话，那么强化学习是深度学习的一个基础工具。

强化学习的经典示意图如下，基本要素为 State，Action，和 Environment。基本过程为：Environment 给出 State，Agent 根据 state 做 Action 决策，Action 作用在 Environment 上产生新的 State 及 reward，其中 reward 用来指导 Agent 做出更好的 Action 决策，循环往复….

而常见的有监督学习则简单很多，可以认为是强化学习的一种特殊情况，目标很清晰就是 groudTruth，因此对应的 reward 也比较清晰。

强化学习按照个人理解可以归纳为以下三大类：

1）DQN

Deep Q network，比较符合人的直观感受逻辑的一种类型，它会训练一个评估 Q-value 的网络，对任一 state 能给出各个 Action 的 reward，然后最终选择 reward 最大的那个 action 进行操作即可。训练过程通过评估 “估计的 Q-value” 和 “真正得到的 Q-value” 的结果进行反向传递，最终让网络估计 Q-value 越来越准。

2）Policy Gradient

是更加端到端的一种类型，训练一个网络，对任一 state 直接给出最终的 action。DQN 的适用范围需要连续 state 的 Q-value 也比较连续（下围棋等不适用这种情况），而 Policy Gradient 由于忽略内部过程直接给出 action，具有更大的普适性。但它的缺点是更难以评价及收敛。一般的训练过程是：对某一 state，同时随机的采取多种 action，评价各种 action 的结果进行反向传递，最终让网络输出效果更好的 action。

3）Actor-Critic

试着糅合前面两种网络，取长补短，一方面用 policy Gradient 网络进行任一 state 的 action 输出，另外一方面用 DQN 网络对 policy gradient 的 action 输出进行较好的量化评价并以之来指导 policy gradient 的更新。如名字所示，就像表演者和评论家的关系。训练过程需要同时训练 actor（policy Graident）和 critic（QN）网络，但 actor 的训练只需要 follow critic 的指引就好。它有很多的变种，也是当前 DRL 理论研究上不停发展的主要方向。

时序数据的压缩

对海量的时序数据进行压缩是显而易见的一个事情，因此在学术界和工业界也有很多的研究和探索，一些方法有：

Snappy：对整数或字符串进行压缩，主要用了长距离预测和游程编码（RLE），广泛的应用包括 Infuxdb。

Simple8b：先对数据进行前后 delta 处理，如果相同用RLE编码；否则根据一张有 16 个 entry 的码表把 1 到 240 个数（每个数的 bits 根据码表）pack 到 8B 为单位的数据中，有广泛的应用包括 Infuxdb。

Compression planner：引入了一些 general 的压缩 tool 如 scale, delta, dictionary, huffman, run length 和 patched constant 等，然后提出了用静态的或动态办法组合尝试这些工具来进行压缩；想法挺新颖但实际性能会是个问题。

ModelarDB：侧重在有损压缩，基于用户给定的可容忍损失进行压缩。基本思想是把维护一个小 buff，探测单前数据是否符合某种模式（斜率的直线拟合），如果不成功，切换模式重新开始buff等；对支持有损的 IoT 领域比较合适。

Sprintz：也是在 IoT 领域效果会比较好，侧重在 8/16 bit 的整数处理；主要用了 scale 进行预测然后用 RLC 进行差值编码并做 bit-level 的 packing。

Gorilla：应用在 Facebook 高吞吐实时系统中的当时 sofa 的压缩算法，进行无损压缩，广泛适用于 IoT 和云端服务等各个领域。它引入 delta-of-delta 对时间戳进行处理，用 xor 对数据进行变换然后用 Huffman 编码及 bit-packing。示例图如下所示。

MO：类似 Gorilla，但去掉了 bit-packing，所有的数据操作基本都是字节对齐，降低了压缩率但提供了处理性能。