時序數據的概念和特點
時序數據是指時間序列數據，是按時間順序記錄的數據列。時序數據可以是時期數，也可以時點數。對於數據庫而言，時序數據一般是一系列帶有時間戳和數據值的數據點，且各列數據值類型相同、數值隨時間戳遞增（減）或在有限區間內波動。
時序數據常用壓縮編碼方式
從時序數據的特點來看，通用的壓縮算法和按行壓縮並不能很好的壓縮時序數據，因此時序數據庫大多都針對不同類型的數據按列採用不同壓縮編碼方式來減少數據存儲的空間佔用，提高存儲空間利用率。
Delta
Delta差分編碼又稱增量編碼，編碼時，第一個數據不變，其他數據轉換為與上一個數據的Delta。該算法應用廣泛，如需要查看文件的歷史更改記錄（版本控制、Git等）。在時序數據庫中，很少單獨使用，一般搭配Simple8b或者Zig-Zag一起使用，壓縮效果更好，下面舉例説明Delta時間戳壓縮：
時間戳一般採用 int64 類型進行存儲，需要佔用 8byte(64bit) 存儲空間。最直接的優化就是存儲時間戳的差值，這裏需要起始時間戳和 Delta 的最大範圍閾值。有兩種常用的實現思路：
1.存儲相鄰兩個時間戳差值 Delta(n) = T(n) - T(n-1)
2.存儲與起始時間戳的差值 Delta(n) = T(n) - T(0)
假設起始時間戳為 1571889600000，Delta 的最大範圍閾值為 3600s，每個 Delta 的數值需要 13bit 可以存儲。因此以上時間戳數據共佔用空間為 64 + 13 * 4 = 116bit。思路 1 的優勢是不需要對塊內數據依次遍歷，但是相比思路 2 可能需要更為頻繁地更換起始時間，根據實際需求選擇合適的壓縮方案。
Delta of Delta
又名二階差分編碼，是在Delta編碼的基礎上再一次使用Delta編碼，比較適合編碼單調遞增或者遞減的序列數據。例如 2,4,4,6,8 , Delta編碼後為2,2,0,2,2 ，再Delta編碼後為2,0,-2,0,0。通常也會搭配Simple-8B或者Zig-Zag一起使用。
Facebook Gorilla 有詳細闡述 Delta-of-Delta 編碼的計算方式，針對不同時間跨度的數據給出了一種較為通用的處理方案（a+b=c, a表示存儲標識位佔用bit，b表示存儲data需要的bit）。
依然通過一組時間戳數據來直觀感受下 Delta-of-Delta 編碼的壓縮效果：
依然假設起始時間戳為 1571889600000，Delta 的最大範圍閾值為 3600s，佔用存儲空間對比如下：
Delta 算法： 64 + 13 * 7 = 155bit 。
Delta-of-delta 算法： 64 + 9 4 + 1 3 = 103bit 。可以看出 delta-of-delta 算法相比 delta 算法進一步獲得了更高的壓縮率。在實際應用場景中，海量時序數據的時間戳都是密集且連續的，絕大部分都滿足 delta-of-delta=0 的條件，這樣可以大幅度降低時間戳的存儲空間。
Zig-Zag
在一些情況下，我們使用到的整數，往往是比較小的。比如，我們會記錄一個用户的id、一本書的id、一個回覆的數量等等。在絕大多數系統裏面，他們都是一個小整數，就像1234、1024、100等。而我們在系統之間進行通訊的時候，往往又需要以整型（int）或長整型（int64）為基本的傳輸類型，為了傳輸一個整型（int）1，我們需要傳輸00000000_00000000_00000000_00000001 32個bits，除了一位是有價值的1，其他全是基本無價值的0。
對於正整數來講，如果在傳輸的時候，我們把多餘的0去掉（或者是儘可能去掉無意義的0），傳輸有意義的1開始的數據，那我們就可以做到數據的壓縮了，比如：00000000_00000000_00000000_00000001這個數字，我們如果能只發送一位1或者一個字節00000001，就將壓縮很多額外的數據。
zigzag給出了一個很巧的方法：補碼的第一位是符號位，他阻礙了我們對於前導0的壓縮，那麼，我們就把這個符號位放到補碼的最後，其他位整體前移一位：
但是即使這樣，也是很難壓縮的，因為數字絕對值越小，他所含的前導1越多。於是，這個算法就把負數的所有數據位按位求反，符號位保持不變，得到了這樣的整數：
而對於非負整數，同樣的將符號位移動到最後，其他位往前挪一位，數據保持不變。
正數、0、負數都有同樣的表示方法了，我們得到了有前導0的另外一個整數。不過他還是一個4字節的整數，我們接下來就要考慮怎麼樣將他們表示成儘可能少的字節數，並且還能還原。
比如：我們將1轉換成(00000000_00000000_00000000_00000010)zigzag這個以後，我們最好只需要發送2bits（10），或者發送8bits（00000010），把前面的0全部省掉。因為數據傳輸是以字節為單位，所以，我們最好保持8bits這樣的單位。zigzag引入了一個方法，就是用字節自己表示自己。舉個例來講：
我們先按照七位一組的方式將上面的數字劃開：
1.將它跟(~0x7f)做與操作的結果，高位還有信息，所以，我們把低7位取出來，並在倒數第八位上補一個1(0x80)：11001111
2.將這個數右移七位：(0000-0000000-0000000-0000000-0001111)zigzag
3.再取出最後的七位，跟(~0x7f)做與操作，發現高位已經沒有信息了（全是0），那麼我們就將最後8位完整的取出來：00001111，並且跳出循環，終止算法
4.最終，我們就得到了兩個字節的數據[11001111, 00001111]解壓過程：對於每一個字節，先看最高一位是否有1(0x80)。如果有，就説明不是最後一個數據字節包，那取這個字節的最後七位進行拼裝。否則，説明就是已經到了最後一個字節了，那直接拼裝後，跳出循環，算法結束。最終得到4字節的整數。
Simple-8B
Simple-8B編碼方式是2010年墨爾本大學一博士在論文中提出的，在 simple 8b 中，一組整數會被存在一系列固定大小的數據塊中。每個數據塊裏，每個整數都用固定字長來表示，這個固定字長由數據塊中最大的整數來表示。而每個數據塊的第一位用來標記這個數據塊字長。
使用這個技術可以讓我們只需要在每個數據塊中只記錄一次字長，而不是去記錄每個整數的字長。而且因為每個數據塊的字長是一樣的，我們也可能推算出來數據塊裏中存儲了多少個整數。
Bit-Packing
這種算法是把文本用需要的最少的位來進行壓縮編碼。
比如八個十六進制數：1，2，3，4，5，6，7，8。轉換為二進制為：00000001，00000010，00000011，00000100， 00000101，00000110，00000111，00001000。每個數只用到了低4位，而高4位沒有用到（全為0），因此對低4位進行壓縮編碼後得到：0001，0010，0011，0100，0101，0110，0111，1000。然後補充為字節得到：00010010， 00110100，01010110，01111000。所以原來的八個十六進制數縮短了一半，得到4個十六進制數：12，34，56，78。
對於bool類型，佔用一個字節（8bit），但其實際有效的只有最後1bit的0 或1，因此，在對bool類型進行壓縮時，使用bit-packing壓縮率很高：8個bool值，原先佔用8byte(64bit)，使用bit-packing壓縮後只需要1byte(8bit)，壓縮率高達12.5%。
XOR
XOR編碼方式是Gorilla內存數據庫一篇論文中提出的，其主要針對時序數據（時間戳+測量值的鍵值對），對時間戳和測量值分別編碼達到壓縮效果。
針對時間戳採用前述delta of delta處理，針對測量值採用如下方法進行壓縮：
1.第一個測量值不壓縮（64bit）。
2.對於後續的測量值，如果當前值跟前一個值的XOR結果為0，即值相等，僅存儲一位‘0’。
3.如果XOR結果不是0，計算XOR中前導零和尾隨零的個數，存儲位’1’後接a)或b):
a). 使用‘0’作為控制位，如果有意義位塊落在前一個有意義位塊中，即前導零和後導零的數量至少與前一個值相同，使用該信息作為塊位置，只存儲有意義的XOR值。
b). 使用‘1’作為控制位，將前導零數的長度存儲到下5位，然後將有意義的xor值的長度存儲到下6位。最後存儲XOR值的有意義的位。
(截圖自Gorilla: A Fast, Scalable, In-Memory Time Series Database)
在上述圖例中，塊頭後是第一條數據的時間戳跟塊頭基準時間戳的delta值，以及第一條數據的測量值（64bit），接下來是壓縮後的鍵值對序列，第二條數據時間戳的d&d值為-2，位於‘10’標記的區間，則存儲‘10’，後跟7位的‘-2’，第三條數據的時間戳d&d值為0，直接存儲一位‘0’。
第一個測量值存儲的是原值12（64bits），第二個測量值跟第一個測量值XOR結果為0，存儲的是一位‘0’，第三個測量值跟第二個測量值XOR結果0x0010000000000000，轉換為二進制有11個前導0（0x001==> 000000000001），因此使用‘11’（2bits）作為控制位，後跟5bit存儲前導零個數，接下來6bit存儲有意義的XOR結果值1（6bits），然後1bit存儲有意義值的位數（只有一位有意義），合計64+1+2+5+6+1=79bits，原值64*3=192bits，綜合考慮原值：64x2x3=384bits，壓縮後：103+64(head)=167bits，壓縮率0.435。
