随着移动互联网的普及，越来越多的传感器设备可以联网，越来越多的数据通过移动互联网上行到服务器进行后续的大数据挖掘、分析等数据应用。但是，在当下流量在大部分设备上还是按量收费的前提下，数据的传输成本还是非常高昂的。有没有一种专门针对传感器数据的极致编码算法及框架，在能耗运行、成本可控的情况下，上行规模更大、维度更多、密度更大的数据去实现更多的业务商业价值以及挖掘数据中隐藏的Boss。
解决方案之：一种基于列式及数据规律去定制的数字编码框架
以一组真实的GPS记录数据为例：
| time | lat(保留6位小数) | lon(保留6位小数) | speed | bearing | accuracy | ... |
|---|---|---|---|---|---|---|
| 1551940387 | 30.345653 | 121.342134 | 78.3 | 358.5 | 9.8 | |
| 1551940388 | 30.345678 | 121.342398 | 77.4 | 359.4 | 9.0 | |
| 1551940389 | 30.345692 | 121.3428 | 76.3 | 0.5 | 10.1 | |
| 1551940390 | 30.345892 | 121.342681 | 77.1 | 359.8 | 10 | |
| 1551940391 | 30.3457 | 121.342862 | 75.8 | 359 | 11.3 |
- 以不带Schema以,分割\n换行的CSV格式(非支持特殊文本的标准CSV)，数据大小：
实际字符串
//总大小：222字节
- 我们进一步思考，使用文本来传输数据是不是比较浪费，那我们使用基于Plain编码#link，继续不考虑Schema, 数据大小:
/ **
* row : time(4B)+lat(8B)+lon(8B)+speed(4B)+bearing(4B)+accuracy(4B)
*
*/
int totalSize = (4 + 8 + 8 + 4 + 4 + 4) * 5
//总大小：180字节
- 我们进一步考虑，使用Protobuffer的编码机制，数据整数化，使用变长编码#link，数据大小：
/**
* row : time(4B)+lat*1000000.toInt(4B)+lon*1000000.toInt(4B)
* +speed*10.toInt(2B)+bearing*10(2B) + accuracy*10(2B)
*/
int totalSize = (4 + 4 + 4 + 2 + 2+ 2) * 5
//总大小：90字节
到这里了，我们发现使用ProtoBuffer的变成编码机制后，数据大小为仅仅为csv的 40%。目前看来应该还是一个不错的结果，不过在接触过大数据列式存储的编码后，这个结果基本就不太领人满意了。
在介绍大数据列式编码前，先介绍下一些比较常见的数字和文本的编码
-
Plain Encoding
每种数据类型支持的普通编码。它以下列格式存储数据：
- BOOLEAN：1字节
- INT32：4字节
- INT64：8字节
- INT96：12字节（不建议使用）
- FLOAT：4字节
- DOUBLE：8字节
- BYTE_ARRAY：长度为4个字节的，后续跟数组中包含的字节
- FIXED_LEN_BYTE_ARRAY：数组中包含的字节数
-
VarNumber Encoding
该编码的核心思路是针对数字的长度在大部分场景下数据的数组比最大值要小很多，使用变长的思路去编码同类型数据，达到使用合适的长度去编码数据的目的。
编码过程是只支持正整数，再利用直接的高位表示编码未结束状态，0表示结束，1表示未结束。
例子： 我们对一个Int型数字为：525314编码的具体过程如下 普通二进制编码：00000000000| 0010000| 0001000| 0000010 变长二进制编码： ‘0’0010000|‘1’0001000|‘1’0000010 编码后只需要3个Byte。 注意： 如果数据的值都比较接近该类型的最大值，编码后数据的字节可能会比原数据大一个字节。 具体原因是因为每个字节的高位都用来做编码标示了。 -
Zigzag
该编码是将Singed带负数的整数全部正数化，目的很简单，数字正数化后，数字才能放弃高位，做到变成编码。该编码的过程是正数奇数化，偶数部分留给负数部分。
例子： 编码前： -4,-2,-1,0,1,3 编码后: 8,4,2,0,1,5 注意： 该编码是后续数字编码处理的核心，基本大部分数字编码都是基于正数的处理 -
BitPacking
该编码的核心思路是用最小单元Bit来编码数据，针对Int类型和Long类型中，大量数据都是小数据，可能1个字节都不到，我们使用Bit来编码数据后，数据大小远远小于实际数据的大小
例子： 对一组数字：1，3，2，6，7，10进行编码 Header: 最大bit宽度：4,数据长度：6 Body: 0001,0011,0010,0110,0111,1010 注意： 1.我们在选择编码的时候，如果一组数字中，存在一些特别大的数字，那么该编码的优势就不明显了。 2.如果一组数字的bit数，不够8的整数位，需要额外填充bit补全Byte。所以我们在选择数字组的时候，使用技巧是尽量让一组数据的长度为8的整数倍。 -
Run Length Encoding
该编码的核心思路是把一组连续的一样的数字只编码一个数字+对应数字的长度。
例子： 一组数字：7，7，7，7，1，1，1，1，1，1，3，3 编码后： 7,5|1,6|3,2 注意： 编码后，不管是原始数字还是长度都是数字，尤其是长度都是非常小的数字， 我们可针对这一的数字混合Bitpacking，进一步缩小编码的大小 -
Dictionary Encoding
该编码的核心是针对一些枚举类型的的文本进行数字化，然后再综合上述编码对文本进行压缩，因为这里的应用场景主要是数值，不做过多的展开。
-
Prefix Encoding
该编码的核心是解决文本中很多前缀和后缀相同的文本数据，提取相同的前缀和后缀，然后借助RLE编码，数据部分只存差值。 除了文本，有很多比如像GPS经纬度，这种数字前缀变化很小的也可以去使用这种编码机制。
例子： Gps经纬度小数位精度 赤道周长（米） 度数（度） 40076000 360 111322.2222 1 11132.22222 0.1 1113.222222 0.01 111.3222222 0.001 11.13222222 0.0001 1.113222222 0.00001 0.111322222 0.000001 0.011132222 0.0000001 我们的gps存储精度一般在6位，11CM的误差，基本能满足90%以上的场景。 按照车速100KM/H换算成27M/S，gps小数位前2位1113米的变化的频率比较小， 所以Gps的前缀基本提取出来，只需要存储后4位小数的变量。 以本文的最初GPS表格的一组GPS经度举例： 121.342134,121.342398,121.3428,121.342681,121.342862 使用该压缩方式 Header: Value|length 12134,5 Body: 2134,2398,2800,2681,2862 注意： 该编码一般需要配合其它编码混合使用 -
Delta Encoding
该编码的核心思路是数字编码只关注前后数组差值，比如在我们常见的ID，时间戳，这些数字的共同点是数字前后差值很小，我们利用这一特点，可以大大压缩数据的大小。
例子：
1，2，3，4，5，6，7，8
Header:
StartValue|length 1,8
Body
1,1,1,1,1,1,1
通过这样的压缩方式，配合BitPacking编码，Body只需要1个字节。
我们再看一组复杂的数字：
7，9，4，1，8，6，3，2
Header:
7,8
Body:
2,-5,-3,7,-2,-3,-1
这样一组数字的Body充斥这正数和负数，我们把Body进行Zigzag编码正数化，
然后使用Bitpacing存储，最大的Bit宽度为4，Body为4个字节
注意：
这样的编码优缺点非常明显，如果数字变化规律很不明显，数字出现的最大差值比原始值还要大，
那么使用这样的编码压缩效果就不明显了。
大致介绍完整数通用编码后，我们继续探讨怎么使用组合拳来实现数字的极致压缩编码
基于列式的数据编码思路：
- 极值处理
- 整数化
- 正数化
- 数据列数值分析，选择合适的编码组合
- 出现一些特殊的情况，可以对原编码进行扩展和定制
- 使用
按照我们最初的GPS我们按照上面的步骤。
1.极值处理
对于经纬度列本身就有极值，对于速度和方向，我们对特别的值进行极值处理，确定数据的最大值：
经度：[-180-180]
纬度：[-90-90]
时间：[now-2039年的最大的到秒的时间戳数值]
速度: [0,300]
方向: [0,360)
定位精度: [0-100)
2.整数化
确定数值保留的小数精度，然后根据该精度对数字*精度。gps经纬度保留6位，其它浮点保留1位
3.正数化
判断数字的极值范围，如果一定要支持负数，使用Zigzag对数字进行编码
4.数据列数值分析，选择合适的编码组合
我们来经度来分析，
对于经度列，存在负数，所以需要Zigzag+正整数化后，数字范围在[0-360000000]。
我们进一步分析列和变化规律，经度是对地理的点二位坐标，按照一般的位移速度，经度的变化还是比较小，而且大部分数前缀都相同，所以我们可以考虑Perfix Encoding和Delta Encoding和Bitpacking。
5.出现一些特殊的情况，可以对原编码进行扩展和定制
对于方向列，不存在负数，整数化后，数字范围[0-360)。
我们进一步分析变规律，发现方向的在大部分时间变化比较小，偶尔变化比较大，同时会出现300归0的情况。针对这些数字规律，首先我们选用一组数字不是特别多的数进行Delta Encoding和BitPacking，为啥要把数字变成一组组的，因为方向中大部分情况变化不大，但是一旦有变化后，Delta值比较大，使用BitPacking后，会导致整个Body变大。同时为了解决方向300多归0带来的差值，我们对这样的差值进行特殊处理，使Delta的值控制在-180-180。
-
time: delta encoding|bitpacking
header:1551940387,1,5 body:1,1,1,1 total:6Byte
-
lat: perfix encoding|delta encoding|bitpacking
header:3034,5,5653,9,5 body:25,14,100,-192 total:12Byte
-
lon: perfix encoding|delta encoding|bitpacking
header:12134,5,2134,10,5 body:264,402,-119,181 total:14Byte
-
speed: delta encoding|bitpacking
-
header: 783,5,5 body: -9,-11,8,-13 total:7Byte
-
bearing: specia delta encoding|bitpacking
-
header: 3585,5,5 body: 9,7,-7,-8 total:7Byte
-
accuracy: bitpacking
-
header: 6,5 body: .... total:4Byte
-
total:50Byte,ProtoBuffer:90Byte
-
以上结果还只是5列的情况下达到的，如果随着列的增多，压缩的效果会显著增强。