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