彼节者有间，而刀刃者无厚；以无厚入有间，恢恢乎其于游刃必有余地矣 ----- 庖丁解牛

前言：随着挪动互联网、IoT、5G等的利用和遍及，一步一步地咱们走进了数字经济时代。随之而来的海量数据将是一种主观的存在，并施展出越来越重要的作用。时序数据是海量数据中的一个重要组成部分，除了开掘剖析预测等，如何高效的压缩存储是一个根底且重要的课题。同时，咱们也正处在人工智能时代，深度学习曾经有了很多很好的利用，如何在更多更广的层面发挥作用？深度学习的实质是做决策，用它解决具体的问题时很重要的是找到契合点，正当建模，而后整顿数据优化loss等最终较好地解决问题。在过来的一段时间，咱们在用深度强化学习进行数据压缩上做了一些钻研摸索并获得了一些问题，曾经在ICDE 2020 research track发表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口头汇报。在这里做一个整体粗略介绍，心愿对其它的场景，至多是其它数据的压缩等，带来一点借鉴作用。

  1. 背景形容

========

1.1 时序数据

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

对于时序数据库的工作内容，简略地，在用户的应用层面它须要响应海量的查问，剖析，预测等；而在底层它则须要解决海量的读写，压缩解压缩，采纳聚合等操作，而这些的基本操作单元就是时序数据，个别（也能够简化）用两个8 byte的值进行对立形容。
能够设想，任何电子设备每天都在产生各种各样海量的时序数据，须要海量的存储空间等，对它进行压缩存储及解决是一个自然而然的办法。而这里的着重点就是如何进行更高效的压缩。

1.2 强化学习

机器学习依照样本是否有groundTruth可分为有监督学习，无监督学习，以及强化学习等。强化学习顾名思义是不停得致力得去学习，不须要groundTruth，真实世界很多时候也没有groundTruth，譬如人的认知很多工夫就是一直迭代学习的过程。从这个意义上来说，强化学习是更合乎或更全面广泛的始终解决事实世界问题的过程和办法，所以有个说法是：如果深度学习缓缓地会像C/Python/Java那样成为解决具体问题的一个根底工具的话，那么强化学习是深度学习的一个根底工具。
强化学习的经典示意图如下，基本要素为State，Action，和Environment。根本过程为：Environment给出State，Agent依据state做Action决策，Action作用在Environment上产生新的State及reward，其中reward用来领导Agent做出更好的Action决策，周而复始….
而常见的有监督学习则简略很多，能够认为是强化学习的一种非凡状况，指标很清晰就是groudTruth，因而对应的reward也比拟清晰。

强化学习依照集体了解能够演绎为以下三大类：

  • DQN：Deep Q network，比拟合乎人的直观感触逻辑的一种类型，它会训练一个评估Q-value的网络，对任一state能给出各个Action的reward，而后最终抉择reward最大的那个action进行操作即可。训练过程通过评估"预计的Q-value“”和“真正失去的Q-value”的后果进行反向传递，最终让网络预计Q-value越来越准。
  • Policy Gradient：是更加端到端的一种类型，训练一个网络，对任一state间接给出最终的action。DQN的适用范围须要间断state的Q-value也比拟间断（下围棋等不实用这种状况），而Policy Gradient因为疏忽外部过程间接给出action，具备更大的普适性。但它的毛病是更难以评估及收敛。个别的训练过程是：对某一state，同时随机的采取多种action，评估各种action的后果进行反向传递，最终让网络输入成果更好的action。
  • Actor-Critic：试着糅合后面两种网络，舍短取长，一方面用policy Gradient网络进行任一state的action输入，另外一方面用DQN网络对policy gradient的action输入进行较好的量化评估并以之来领导policy gradient的更新。如名字所示，就像表演者和评论家的关系。训练过程须要同时训练actor（policy Graident）和critic(DQN)网络，但actor的训练只须要follow critic的指引就好。它有很多的变种，也是以后DRL实践钻研上不停倒退的次要方向。
  1. 时序数据的压缩

===========

对海量的时序数据进行压缩是不言而喻的一个事件，因而在学术界和工业界也有很多的钻研和摸索，一些办法有：

  • 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，所有的数据操作根本都是字节对齐，升高了压缩率但提供了解决性能；
  • …


还有很多相干的压缩算法，总的来说：

  1. 它们根本都是反对单模式，或者无限的偏static的模式进行数据的压缩；
  2. 很多为了进步压缩率，都用了bit-packing (甚至有损压缩），但对越来越宽泛应用的并行计算不太敌对；
  3. 两阶段的基于深度学习的压缩算法

===================

3.1 时序数据压缩的个性

时序数据来源于IoT、金融、互联网、业务管理监控等方方面面，状态个性相差很多，而后对数据精确度等的要求也不尽相同。如果只能有一种对立的压缩算法进行无差别看待地解决，那应该是基于无损的、用8B数据进行数据形容的算法。
下图是阿里云业务中一些时序数据的示例，无损是从宏观还是宏观层面，数据的pattern都是形形色色的，不仅仅是形态曲线，也包含数据精度等。所以压缩算法很有必要反对尽量多的一些压缩模式，而后又能够既无效又经济地抉择其中一种进行压缩。

对于一个大型的商用的时序数据压缩算法，须要重点关注三个重要的个性：

  • Time correlation：时序数据有很强的工夫相关性，而后对应的数据基本上是间断的。采样距离通常是1s，100ms等；
  • Pattern diversity：如上图，pattern及个性差距会很大；
  • Data massiveness：每天、每小时、每秒须要解决的数据量都是海量的，总体解决数据至多是在每天10P的level，对应的压缩算法须要高效且有高吞吐率。

3.2 新算法核心理念

寻根究底，数据压缩的实质可分为两阶段：首先Transform阶段把数据从一个空间转化到另外一个更规定的空间，而后在差值编码阶段用各种各样的方法较好的标识变换后的差值。
依据时序数据的特点，能够定义以下6个根本的transform primitives（可扩大）。

而后定义以下3中根本的differential coding primitives（可扩大）。

接下来把下面的两种tools排列组合进行压缩？这样可行但成果必定是不太好，因为模式抉择和相干参数的cost比重太高了，须要2B（primitive choice + primitive parameter）的管制信息，占了8B须要表白数据的25%。
更好的应该是对数据的个性进行抽象化分层表白，示意图如下。创立一个控制参数集较好的表白所有的状况，而后在全局(一个timeline)层面抉择适合的参数来确定一个搜寻空间（只蕴含大量的压缩模式，譬如4种）；而后在具体进行每个点的压缩时，遍历从中抉择出最好的那一种压缩模式进行压缩。管制信息的比重在~3%。

3.3 两阶段压缩框架AMMMO

AMMMO（adatpive multiple mode middle-out）整体过程分为两个阶段，第一阶段确定以后这条工夫线的总体个性（确定9个控制参数的具体值）；而后在第二阶段在大量的压缩模式中遍历并查找最初的一种进行压缩，具体框图如下。

第二阶段的模式抉择没有难度，逻辑简略适宜高效率执行；第一阶段确定各参数值（9个这里）失去适合的压缩空间有比拟大的挑战，须要从实践上的300K多个排列组合抉择里找出适合的那一个。

3.4 基于规定的模式空间抉择算法

能够设计一种算法，譬如创立各个压缩模式的成果记录牌(scoreboard），而后遍历一个timeline里的所有点并进行剖析记录，而后再通过统计分析比拟等抉择最好的模式。一些不言而喻的问题有：

  • 抉择的评估指标是否现实？
  • 须要人工去思考并编写程序，有较多的实现，debug和maintain的工作量；
  • 如果算法中的primitive，压缩模式等做了扭转，整个代码都须要重构，基于下面的抉择不是实践抉择，须要一种主动且较智能的办法撑持不停的演变等。
  1. 深度强化学习

==========

4.1 问题建模

简化下面的整个模式空间抉择算法如下图，咱们能够把这个问题等同于多指标的分类问题，每个参数就是一个指标，每个参数空间的取值范畴就是可抉择的类目数。深度学习在图像分类，语义了解等方面证实了它的高可用性。相似地，咱们也能够把这里的模式空间的抉择问题用深度学习来实现，把它当做一个multi-label的classification问题。

用什么样的网络？思考到辨认的次要关系是delta/xor, shift，bitmask等为主，cnn不失当，full-connect的mlp比拟适合。相应地，把一条工夫线上的所有点，如果1小时就是3600个共3600*8B，有些太多，思考到同一timeline外部一段一段的相似性，把32个点作为一个最根本的处理单元。
接下来，怎么去创立训练样本？怎么给样本寻找label呢？
在这里咱们引入了强化学习，而不是有监督的学习去训练，因为：

  • 去创立有label的样本很难：32个样本256B，实践上sample有256^256中可能性，对每个这种样本，须要遍历300K的可能性能力找出最好的那一个。创立及抉择sample，create label的工作量都十分大；
  • 这不是一般的one-class-label问题：给定一个样本，并不是有惟一的最好的一个后果，很有可能很多的抉择都能获得雷同的压缩成果；N class（N根本不可知）的训练又减少了很多难度；
  • 须要一种自动化的办法：压缩的tool等参数抉择很有可能是须要扩大的，如果产生整个训练样本的创立等都须要从新再来。须要一种自动化的方法。

用什么样的强化学习呢？DQN，policy gradient, 还是actor-critic? 如后面剖析，DQN是不太适宜reward/action不间断的的状况，这里的参数，譬如majorMode 0和1是齐全不同的两种后果，所以DQN不适合。此外，压缩问题一方面不容易评估另外网络也没有那么简单，不须要actor-critic。最终咱们抉择了policy gradient。
Policy gradient常见的loss是用一个缓缓进步的baseline作为衡量标准来反馈以后的action是否适合，但这里并不太适合（成果尝试了也不太好），因为这里sample的实践block(256^256) state太多了一些。为此，咱们专门设计了一个loss。

失去了每个block的参数后，思考到block的相关性等。能够用统计的方法，聚合失去整个timeline的最终参数设置。

4.2 深度强化学习网络框架

整体的网络框架示意图如下：

在训练端：随机抉择M个block，每个block复制N份，而后输出到有3个隐含层的全连贯网络中，用region softmax失去各参数各种choice的概率，而后依照概率去sample每个参数的值，失去参数后输出到底层的压缩算法进行理论压缩并失去压缩值。复制的N个block互相比拟计算loss而后做反向流传。loss的整体设计为：

_fn(copi)_形容了压缩成果，比N个block的均值高就正反馈，_Hcs(copi)_是穿插熵，心愿得分高的概率越大越确定越好；反之亦然。前面的_H（cop)_是穿插熵作为正则化因子来尽量避免网络固化且收敛到部分最优。
在推理端，能够把一个timeline的全副或部分block输出到网络中，失去参数，做统计聚合而后失去整个timeline的参数。

  1. 后果数据

========

5.1 实验设计

测试数据局部一方面随机选取了阿里云业务IoT和server两个大场景下共28个大的timeline；另外也选取了时序数据分析开掘畛域最通用的数据集UCR。根本信息如下：

比照算法选取了比拟有对比性的Gorilla，MO和Snappy。因为AMMMO是两阶段的压缩算法框架，第一阶段的参数抉择能够有各种各样的算法，这里选用了Lazy（简略粗犷的设置一些普世参数），rnd1000Avg（随机1000次取成果平均值），Analyze（用人工代码的算法)和 ML（深度强化学习的方法）等。

5.2 压缩成果比照

首先从整体压缩率来看，AMMMO两阶段自适应多模式的压缩比起Gorila/MO等有显著的成果晋升，均匀压缩率晋升在50%左右。

而后ML的成果怎么样呢？下图在ML的视线比照了测试集B上的压缩成果，总的来说，ML相比人工精心设计的算法略好，比随机均匀等显著好很多。

5.3 运行效率

AMMMO借鉴了MO的设计思维，移除了bit-packing，不仅仅在CPU上能高速运行，也特地适宜于并行计算平台如GPU。此外AMMMO分两阶段，其中第一阶段的性能会差一些，但很多时候，譬如对一个特定的设施过来2天的数据，全局压缩参数是能够复用的。下图形容了整体的性能比照，试验环境为“Intel CPU 8163 + Nvidia GPU P100"，其中AMMMO的代码应用了P100。

从上图中看出，AMMMO在压缩端和解压缩端都能达到GB/s的解决性能，性能指标还是很不错的。

5.4 算法学到的成果

深度强化学习训练的网络从最终成果上看着不错，那它是不是真的有学到有意义的内容呢？下标比照了3中算法在几个测试集上的体现，能够看出，ML版本的参数抉择和剖析算法/最优成果抉择是差不多的，特地是在byte offset和majorMode的抉择上。

这种压缩的全连贯网络参数表象会是怎么样的？对第一层进行了参数heatmap可视化（正的参数为红色，负的为蓝色，值越大色彩越亮），如下：

能够显著看到32个点在雷同的byte上有很多规定的操作，竖线（如果逾越byte则混同状况），能够认为是在对应的地位上做delta或xor运算等。而后数字变动最大的Byte0的参数也比拟沉闷。
综上，深度学习学到的货色还是挺有解释性的。

  1. 相干人员和致谢

===========

在整个过程中，Yanqing peng，飞刀，汪晟，乐予，麦君和Yue Xie等一起付出了很多的致力，特别感谢飞刀老师的方向指引和总体判断；
此外，特别感谢矽厉等在工作中给予的反对，感激德施等在业务上给予的帮忙和反对。

原文链接
本文为阿里云原创内容，未经容许不得转载。