时序数据的概念和特点
时序数据是指工夫序列数据，是按工夫程序记录的数据列。时序数据能够是期间数，也能够时点数。对于数据库而言，时序数据个别是一系列带有工夫戳和数据值的数据点，且各列数据值类型雷同、数值随工夫戳递增（减）或在无限区间内稳定。
时序数据罕用压缩编码方式
从时序数据的特点来看，通用的压缩算法和按行压缩并不能很好的压缩时序数据，因而时序数据库大多都针对不同类型的数据按列采纳不同压缩编码方式来缩小数据存储的空间占用，进步存储空间利用率。
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。