背景
今年在公司内部主导了两个的行情数据系统的构建，两者均使用到了常见的时序数据压缩算法。这里简单总结一下过程中积累的一些经验。
让我们先来思考一个问题：压缩算法生效的前提是什么？
数据本身至少要符合以下两种特性其一：
数据存在冗余
数据符合特定的概率分布
在时序数据领域，数据冗余度与相似度较高，因此天生适合进行压缩。但对于不同类型的数据，其所适用的压缩算法也大相径庭。下面我们逐一介绍这些数据相应的压缩算法。
整数
整型数据是构建各种应用的基石，时序型应用也不例外。在行情数据中，存在大量的整型数据，例如：逐笔成交中的时间戳、成交量。
根据压缩算法的不同，可以将整型数据分为以下3类：
无符号整型——Varint
有符号整型——ZigZag
时间戳——Delta2+Simple8b
Varint
一个32位的无符号整型能表达0-之间的任意数字但这些数字在日常生活中出现的概率并不是均匀分布的，一个著名的例子是本福特定律，该定律常被用于辨别数据的真伪。
通常情况下，较小的数字出现的概率会高于极大的数据。以年龄为例，无论人口如何分布，大部分人的年龄都位于0~之间。
表示仅需要7bit足矣，如果使用32bit的无符号整型进行存储，意味着至少浪费了24bit。
幸运的是，我们能通过一种自适应编码方式来减少这种浪费——Varint。
publicclassVarIntCodec{staticintencodeInt(intv,byte[]bytes,intoffset){if(v0){thrownewIllegalStateException();}elseif(v){bytes[offset++]=(byte)v;}elseif(v){bytes[offset++]=(byte)(v
0x80);bytes[offset++]=(byte)((v7)0x7F);}elseif(v){bytes[offset++]=(byte)(v
0x80);bytes[offset++]=(byte)((v7)
0x80);bytes[offset++]=(byte)(v14);}elseif(v){bytes[offset++]=(byte)(v
0x80);bytes[offset++]=(byte)((v7)
0x80);bytes[offset++]=(byte)((v14)
0x80);bytes[offset++]=(byte)(v21);}else{bytes[offset++]=(byte)(v
0x80);bytes[offset++]=(byte)((v7)
0x80);bytes[offset++]=(byte)((v14)
0x80);bytes[offset++]=(byte)((v21)
0x80);bytes[offset++]=(byte)(v28);}returnoffset;}staticintdecodeInt(byte[]bytes,int[]offset){intval;intoff=offset[0];byteb0,b1,b2,b3;if((b0=bytes[off++])=0){val=b0;}elseif((b1=bytes[off++])=0){val=(b00x7F)+(b17);}elseif((b2=bytes[off++])=0){val=(b00x7F)+((b10x7F)7)+(b);}elseif((b3=bytes[off++])=0){val=(b00x7F)+((b10x7F)7)+((b20x7F)14)+(b);;}else{val=(b00x7F)+((b10x7F)7)+((b20x7F)14)+((b30x7F)21)+(bytes[off++]28);}offset[0]=off;returnval;}}
通过观察代码可以得知，Varint编码并不是没有代价的：每8bit需要需要牺牲1bit作为标记位。对于值较大的数据，Varint需要额外的空间进行编码，从而导致更大的空间消耗。因此使用Varint的前提有两个：
数据较小
没有负数
ZigZag
Varint编码负数的效率很低：对于big-endian数据来说，Varint是通过削减leading-zero来实现的压缩。而负数的首个bit永远非零，因此不但无法压缩数据，反而会引入不必要的空间开销。
ZigZag通过以下方式来弥补这一缺陷：
增加小负数的leading-zero数量，然后再进行Varint编码。
其原理很简单，增加一个ZigZag映射：
Varint编码前增加映射(n1)^(n31)
Varint解码后增加映射(n1)^-(n1)
当n=-1时，Varint编码前映射：
n=-1-a=n1-b=n31-a^b-
当n=-1时，Varint解码后映射：
m=a^b-a=m1-b=-(m1)-a^b-
ZigZag映射能够有效增加小负数的leading-zero数量，进而提高编码效率。
ZigZag本身也并不是完美的的：
占用了部分非负数的编码空间
对于大负数没有优化效果
Delta2
时间戳是时序数据中的一类特殊的数据，其值往往比较大，因此不适用于Varint编码。但是时间戳本身具有以下两个特性：
非负且单调递增
数据间隔较为固定
前面提到过：提高整型数据压缩率的一个重要手段是增加leading-zero数量。说人话就是：尽可能存储较小的数字。
因此，相较于存储时间戳，存储前后两条数据的时间间隔是一个更好的选择。
第一种方式是使用Delta编码：
第一个数据点，直接存储0t0
第n个数据点，则存储0tnt0
但是Delta编码的数据冗余仍然较多，因此可以改进为Delta2编码：
第一个数据点，直接存储0t0
第n个数据点，则存储1tntn1
编码后的int64的时间戳，可以用int32甚至更小的数据类型进行存储。
Simple8b
朋友，你觉得Varint与Delta2已经是整型压缩的极限了吗？
某些特殊的时序事件，可能以很高的频率出现，比如行情盘口报价。这类数据的时间戳进行Delta2编码后，可能会出现以下两种情况：
场景1：很多连续的0或1区间
场景2：大部分数据分布在0~63的范围内
对于场景1，游程编码（RLE）是个不错的选择，但普适性较差。
对于场景2，每个值仅需6bit存储即可，使用Varint编码仍有空间浪费。
Simple8b算法能较好的处理这一问题，其核心思想是：将尽可能多数字打包在一个64bit长整型中。
Simple8b将64位整数分为两部分：
selector(4bit)用于指定剩余60bit中存储的整数的个数与有效位长度
payload(60bit)则是用于存储多个定长的整数根据一个查找表，将数据模式匹配到最优的selector，然后将多个数据编码至payload
Simple8b维护了一个查找表，可以将数据模式匹配到最优的selector，然后将多个数据编码至payload。编码算法可以参考这个Go实现。
需要指出的是，这个开源实现使用回溯法进行编码，其复杂度为(2)O(n2)（n为输入数据长度）。该实现对于离线压缩来说已经足够，但对于实时压缩来说稍显不足。
我们在此代码的基础上，使用查表法维护了一个状态转移数组，将编码速度提升至()O(n)，使其能够应用于实时压缩。
浮点数
浮点数是一类较难压缩的数据，IEEE在编码上几乎没有浪费任何一个bit，因此无法使用类似Varint的方式进行压缩：
目前常用的压缩方式可以分为两类：
有损压缩——丢弃不必要的精度后，使用整数进行表示
无损压缩——XOR编码
有损压缩
有损压缩需要配合业务领域知识来使用，因为首先要确定需要保留的精度。当精度确定之后，就可以将浮点数转换为整数，然后使用Varint进行编码。
publicstaticScaledResultscaleDecimal(float[]floats,finalintscaleLimit)throwsCodecException{BigDecimal[]decimals=newBigDecimal[floats.length];for(inti=0;ifloats.length;i++){decimals=newBigDecimal(Float.toString(floats));}BigDecimalbase=null;intmaxScale=0;for(BigDecimaldecimal:decimals){Preconditions.checkState(decimal.signum()=0);intscale=decimal.scale();if(scale==1maxScale==0decimal.stripTrailingZeros().scale()=0){scale=0;}maxScale=Math.max(maxScale,scale);base=base==null
decimal.