如何更高效地壓縮時序數(shù)據(jù)？基于深度強化學習的探索

隨著移動互聯(lián)網(wǎng)、IoT、5G 等的應用和普及，一步一步地我們走進了數(shù)字經(jīng)濟時代。隨之而來的海量數(shù)據(jù)將是一種客觀的存在，并發(fā)揮出越來越重要的作用。時序數(shù)據(jù)是海量數(shù)據(jù)中的一個重要組成部分，除了挖掘分析預測等，如何高效的壓縮存儲是一個基礎且重要的課題。同時，我們也正處在人工智能時代，深度學習已經(jīng)有了很多很好的應用，如何在更多更廣的層面發(fā)揮作用？本文總結了當前學術界和工業(yè)界數(shù)據(jù)壓縮的方法，分析了大型商用時序數(shù)據(jù)壓縮的特性，提出了一種新的算法，分享用深度強化學習進行數(shù)據(jù)壓縮的研究探索及取得的成果。

深度學習的本質(zhì)是做決策，用它解決具體的問題時很重要的是找到契合點，合理建模，然后整理數(shù)據(jù)優(yōu)化 loss 等最終較好地解決問題。在過去的一段時間，我們在用深度強化學習進行數(shù)據(jù)壓縮上做了一些研究探索并取得了一些成績，已經(jīng)在 ICDE 2020 research track 發(fā)表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口頭匯報。在這里做一個整體粗略介紹，希望對其它的場景，至少是其它數(shù)據(jù)的壓縮等，帶來一點借鑒作用。

背景描述

1 時序數(shù)據(jù)

時序數(shù)據(jù)顧名思義指的是和時間序列相關的數(shù)據(jù)，是日常隨處可見的一種數(shù)據(jù)形式。下圖羅列了三個示例：a）心電圖，b）股票指數(shù)，c）具體股票交易數(shù)據(jù)。

關于時序數(shù)據(jù)庫的工作內(nèi)容，簡略地，在用戶的使用層面它需要響應海量的查詢，分析，預測等；而在底層它則需要處理海量的讀寫，壓縮解壓縮，采用聚合等操作，而這些的基本操作單元就是時序數(shù)據(jù) <timestamp, value>，一般（也可以簡化）用兩個 8 byte 的值進行統(tǒng)一描述。

可以想象，任何電子設備每天都在產(chǎn)生各種各樣海量的時序數(shù)據(jù)，需要海量的存儲空間等，對它進行壓縮存儲及處理是一個自然而然的方法。而這里的著重點就是如何進行更高效的壓縮。

2  強化學習

機器學習按照樣本是否有 groundTruth 可分為有監(jiān)督學習，無監(jiān)督學習，以及強化學習等。強化學習顧名思義是不停地努力地去學習，不需要 groundTruth，真實世界很多時候也沒有 groundTruth，譬如人的認知很多時候就是不斷迭代學習的過程。從這個意義上來說，強化學習是更符合或更全面普遍的一種處理現(xiàn)實世界問題的過程和方法，所以有個說法是：如果深度學習慢慢地會像 C/Python/Java 那樣成為解決具體問題的一個基礎工具的話，那么強化學習是深度學習的一個基礎工具。

強化學習的經(jīng)典示意圖如下，基本要素為 State，Action，和 Environment�；�本過程為：Environment 給出 State，Agent 根據(jù) state 做 Action 決策，Action 作用在 Environment 上產(chǎn)生新的 State 及 reward，其中 reward 用來指導 Agent 做出更好的 Action 決策，循環(huán)往復….

而常見的有監(jiān)督學習則簡單很多，可以認為是強化學習的一種特殊情況，目標很清晰就是 groudTruth，因此對應的 reward 也比較清晰。

強化學習按照個人理解可以歸納為以下三大類：

1）DQN

Deep Q network，比較符合人的直觀感受邏輯的一種類型，它會訓練一個評估 Q-value 的網(wǎng)絡，對任一 state 能給出各個 Action 的 reward，然后最終選擇 reward 最大的那個 action 進行操作即可。訓練過程通過評估 “估計的 Q-value” 和 “真正得到的 Q-value” 的結果進行反向傳遞，最終讓網(wǎng)絡估計 Q-value 越來越準。

2）Policy Gradient

是更加端到端的一種類型，訓練一個網(wǎng)絡，對任一 state 直接給出最終的 action。DQN 的適用范圍需要連續(xù) state 的 Q-value 也比較連續(xù)（下圍棋等不適用這種情況），而 Policy Gradient 由于忽略內(nèi)部過程直接給出 action，具有更大的普適性。但它的缺點是更難以評價及收斂。一般的訓練過程是：對某一 state，同時隨機的采取多種 action，評價各種 action 的結果進行反向傳遞，最終讓網(wǎng)絡輸出效果更好的 action。

3）Actor-Critic

試著糅合前面兩種網(wǎng)絡，取長補短，一方面用 policy Gradient 網(wǎng)絡進行任一 state 的 action 輸出，另外一方面用 DQN 網(wǎng)絡對 policy gradient 的 action 輸出進行較好的量化評價并以之來指導 policy gradient 的更新。如名字所示，就像表演者和評論家的關系。訓練過程需要同時訓練 actor（policy Graident）和 critic（QN）網(wǎng)絡，但 actor 的訓練只需要 follow critic 的指引就好。它有很多的變種，也是當前 DRL 理論研究上不停發(fā)展的主要方向。

時序數(shù)據(jù)的壓縮

對海量的時序數(shù)據(jù)進行壓縮是顯而易見的一個事情，因此在學術界和工業(yè)界也有很多的研究和探索，一些方法有：

Snappy：對整數(shù)或字符串進行壓縮，主要用了長距離預測和游程編碼（RLE），廣泛的應用包括 Infuxdb。

Simple8b：先對數(shù)據(jù)進行前后 delta 處理，如果相同用RLE編碼；否則根據(jù)一張有 16 個 entry 的碼表把 1 到 240 個數(shù)（每個數(shù)的 bits 根據(jù)碼表）pack 到 8B 為單位的數(shù)據(jù)中，有廣泛的應用包括 Infuxdb。

Compression planner：引入了一些 general 的壓縮 tool 如 scale, delta, dictionary, huffman, run length 和 patched constant 等，然后提出了用靜態(tài)的或動態(tài)辦法組合嘗試這些工具來進行壓縮；想法挺新穎但實際性能會是個問題。

ModelarDB：側重在有損壓縮，基于用戶給定的可容忍損失進行壓縮�；�本思想是把維護一個小 buff，探測單前數(shù)據(jù)是否符合某種模式（斜率的直線擬合），如果不成功，切換模式重新開始buff等；對支持有損的 IoT 領域比較合適。

Sprintz：也是在 IoT 領域效果會比較好，側重在 8/16 bit 的整數(shù)處理；主要用了 scale 進行預測然后用 RLC 進行差值編碼并做 bit-level 的 packing。

Gorilla：應用在 Facebook 高吞吐實時系統(tǒng)中的當時 sofa 的壓縮算法，進行無損壓縮，廣泛適用于 IoT 和云端服務等各個領域。它引入 delta-of-delta 對時間戳進行處理，用 xor 對數(shù)據(jù)進行變換然后用 Huffman 編碼及 bit-packing。示例圖如下所示。

MO：類似 Gorilla，但去掉了 bit-packing，所有的數(shù)據(jù)操作基本都是字節(jié)對齊，降低了壓縮率但提供了處理性能。