后台开发中的时空转换艺术

augustzhang

作者介绍：augustzhang，安全平台部基础架构组员工，先后从事密保、验证码等后台研发工作，现在主要负责安全平台部大数据平台的研发工作，致力于研究每秒GB级的数据如何进行实时分析等问题。

背景

后台设计

经常会遇到空间上的问题，比如：网卡流量爆了，Cache又快满了，APP的手机流量过高等。通常情况下，一般是选择提高硬件成本的方式扩容来解决这个问题。然而，本文所提供的是另一种方式，通过牺牲少量的时间换取更高的空间利用率，以达到减少网卡流量、内存使用量的目的。

在安平的很多个系统设计中，都采用了一些数据压缩算法，比如海立方平台，在对数据协议进行压缩后，使得网络流量比原来降低了接近50%；IPC系统，在经过对数据的Huffman编码后，也使得Cache的内存使用下降了50%，可以说，这两个系统，光是算法优化，就节省了近百台机器的开销。

本文并不打算介绍业界比较流行的一些gzip,7z等通用压缩算法，这类算法并不太适合于后台开发中使用，原因主要有两个：一是这些算法的CPU开销比较大，不适合于实时的后台系统，二是这类算法对于小数据量时(字节级)的压缩效果很差。因此，它们更适合大量数据的离线压缩，而不是后台设计中。而本文介绍的，会以一些适合于后台开发的轻量级压缩为主，他们包括：整数编码、快速压缩0、Huffman编码、定长压缩、二维Hash压缩。除了介绍其原理以外，也会介绍一下具体的实现方法。

整数编码

多数情况

大部分整数字段的实际值都很小(1个字节以内)，但是为了少部分的较大值，我们不得不把值域开到理论最大值（比如32位或者64位），这导致了大把的空间浪费。其实业界已经有一些变长的整数编码来解决这个问题，比如在ProtoBuf中就使用了variant编码来对整数进行编码，以获得更优的空间使用率。这里给出另外一种变长的自适应长度的数值编码方案：用前缀位的方式来描述数据字节长度，剩余的位则用来描述实际数据，如下图所示：

有了前缀位来描述真实长度，我们就可以使用变长的字节来记录整数，其好处不言而喻，它可以根据数据的实际大小来分配空间，缺点是它也需要额外的一些开销来存储前缀位。这在大部分数据都非常小的时候非常好用，特别是类似于：AppID, Command 这种字段。这种编码方式和ProtoBuf所使用的variant编码空间上效果一样，但在编解码速度上要更快，具体的参考接下来的实现方案。

编码方案

第一步：确定数据的实际有效位数，根据数据有效位数来指定前缀。通过二分来判断数值的有效位数是一个不错的方法，但仍然太慢，在x86/x64 平台下，有一条CPU指令：BSR ,其功能是从最高位开始扫描，遇到第一个1时返回其位置。利用这条CPU指令，我们可以用一条指令就直接得到数据的实际有效位长，这比二分法确定位长要高效的多，而在GCC里，有对这条CPU指令专门做了内建函数，更方便于我们的使用：

第二步：得到有效位长之后，可以通过位长来进行查表，以获取其前缀和实际数据长度(表的最大长度是64，预先构造好即可)。将数据左移前缀的长度然后与前缀求或运算，即可完成数据编码。 （因为是小端模式，低字节在前，需要把前缀放在低位，所以是左移而不是右移）算法复杂度为O(1)。

解码方案

由于前缀必定在第一个字节中，因此我们可以遍历第一个字节的所有情况，进行查表，总共256种可能，全部事先计算出来，解码的时候直接用第一个字节查表，即可得到数据的实际长度，以及需要右移的位数。算法复杂度为O(1)。

快速压缩0

场景

不得不说，在大量的数据存储、数据传输过程中，字节：0的出现概率是最高的。 特别是在早期的一些定长协议中， 0的出现概率甚至达到了一半以上，无论是对于存储，还是对于网络流量都是巨大的浪费。这里提供一种实现简单且处理高效的方法：

编码方案：首先对数据进行分组，每8字节为一组，对于每一组，用一个额外的起始字节(8bits)记录每一个字节是否非0。之后就只需要把非0的字节挨个记录下来即可。解码方案： 每次解码先取出位表字节，然后依据位表中的位逐字节处理，若为0，则直接添加0，否则读取下一个非0字节。 如下图所示，就是一个简单的编码样例，8个字节，构成8个bits,正好一个字节。1表示非0，0表示字节为0。 构成首字节，再把剩余的非0字节挨个存储即可。这种算法的实现非常简单明了，而且执行效率也非常高，经测试，C1的机器单核50MB/S以上的编解码效率。额外开销为：1/8， 收益 = 所有为0的字节总和。 净收益 = 0字节总数 - 数据量/8

Huffman编码Huffman也称为最优编码，是一种根据取值的出现概率来构造编码，使得平均长度最短编码方案。其基本思想是，出现概率越高，编码长度越短，出现概率越低，编码长度越长，以求平均长度最短。适用场景：当字段取值分布不均匀时，效果非常好。

编码方案

第一步，构造Huffman编码树，如下图所示就是一个简单的Huffman编码树。1. 每个可能出现的值，都作为一个节点，其出现概率即为节点权重。2. 每次选择当前权重最小的两个节点，合为一个节点，他们的权重求和构成新的权重。3. 直到合并到只剩一个节点为止。4. 此时节点合并的路径，就会构成一棵二叉树，树上的叶子节点即为原来的各种合法值。优化算法：每次选择都需要选取权重最小的节点，此时可以通过最小堆的算法来进行优化，使得整个编码的算法复杂度由O(N^2) 降低为O(N * LogN)。

第二步，编码：从根节点到每个叶子节点都会构成一个路径，设往左为0，往右为1，则这个路径就是一段二进制编码，以上图为例，'a' 的编码就是：010， 'm'的编码就是0111。遍历整个编码树，将每个字符的编码构造成一个编码表，即可通过查表的方式进行编码。不难发现，出现概率越大（权重越大）的值，就自动的离根节点越近，其编码也就越短。且不可能出现一个字符的编码是另一个字符的编码前缀。

解码方案：把整个数据看为二进制流，从编码树的根节点开始，遇到0则往左，遇到1则往右。逢叶子节点时则成功解出来一个字符。然后回到根节点继续解下一个字符。

解码加速算法：按照常规的解码方案，每次都需要从根节点开始解码，显然费时费力。假如我们可以建立一个加速表，把前N位的所有可能全部记录下来，直接指向第N位所对应的Huffman树节点，那么就只需要一次查表操作，就可以直接处理掉前N位。这里以16位的加速表为例。首先开一个65536长度的数组，记录一个指针，该指针就直接指向其下标所代表的树节点。显然，当编码长度>=16时，一次查询即可完成16位的解码。那么问题来了，倘若编码长度<16时，这时怎么办？ 方法是，当长度不足时，构造后续不足位的所有可能，让他们指向一个相同的树节点，同时记录下实际的位长。以下图的编码 010010为例， 那么从 0100100000000000 到 0100101111111111的所有下标元素全部都指向010010所在节点，且记录长度为6。 那么解码时，不管这6位之后是什么内容，都会解码出010010所在内容，然后把位指针后移位。 这里16位只是一个例子，如果空间足够，也可以构造更大的加速表，一次性加速更多的解码位。

定长数据压缩

KEY在很多时候，会需要数据是定长的以支持随机访问（比如二分查找），前面提到的各种编解码方案虽然可以得到较高的空间收益，但由于会改变数据的定长性质，使得数据的随机访问变的很困难。这里提供一种定长的压缩方式，即数据压缩后仍然是定长的。

在研究这个问题之前，我们先举出一个现实的应用场景以方便大家的理解。假设有一批数据，KEY是UIN(4字节)，Value是一个指针/偏移（先假定4字节）指向一块数据，数据规模有10亿条。要求通过UIN能快速的获取到Value。

第一种方法，也是最简单的方法，按照UIN进行排序，之后通过二分查找的方式来进行查找，那么所需的空间 = 10亿 * 8字节 = 8GB。

第二种方法是开辟一个覆盖所有KEY范围的数组，直接以KEY作为下标进行访问。比如访问UIN:12345678就是pValue[12345678]，此时需要的空间是 4 * 2^32 = 16GB。

第三种方法，其实是综合上述两种方法。我们把一半提取出来作为下标，另一半仍然用二分查找。先划分2^16个桶，以UIN的高16位进行分桶。那么显然，同一个桶中的所有UIN的高16就都是相同的，就无需再重复记录了，只需要记录低16位即可。然后再开辟一个 2^16个元素，以高16位作为下标，指向每一个桶的位置即可。

如此一来，KEY就只需要记录2个字节，Value仍然是4个字节。此外还需要记录每个桶的起始位置，开销是2^16 * 4= 256KB，基本可忽略。总空间开销= 10亿 * 6字节 + 2^16 * 4 = 6GB。倘若把桶的长度提高到24位(3字节)，那么此时KEY就只需要记录1个字节即可，总开销= 10亿 * 5字节 + 2^24 * 4 = 5.064 GB。

现在KEY已经基本上优化成1个字节了，那么我们再进一步优化，看看Value是否能进一步优化。Value的本身其实是一个指针，或者一个偏移。在大部分情况下，数据都是顺序存储下来的，因此会有一个惊人的事实，就是同一个桶中的元素，其Value的偏差也会非常小，那么问题就好办了，我们只需要记录桶中的第一个Value的值，之后的元素都只记录一个差值就好了，那么值域就会瞬间的缩小。在大部分情况下，2字节就可以足够存储这个差值了（视业务特性而定）。如此一来，原本8个字节的存储，就可以优化为3个字节。由原本的8GB，可以缩减为 3GB+。 而指针所指向的数据，因为可以通过指针来定位，所以通过前面所描述过的变长编码，来进行进一步的编码以节省空间。那么另外一个问题来了，是否还需要额外存储一个长度，来记录指针所指向的数据长度？答案其实是不需要，在紧凑存储的情况下，下一个元素的开始位置，就是上一个元素的结束位置。

Hash表中的KEY压缩

HashTable

先给出一种比较常用的Hash算法：二维Hash算法，然后我们再一起讨论一下如何对KEY进行压缩存储。其他的Hash算法也可以作为参考，但不一定能照搬。如下图所示，将存储空间看做一个N行M列的二维数组，每一个行都有一个小于等于 M的不同素数（通常是从M开始，从大到小依次选取素数），这就是一个简单的二维HashTable，也可以看成是N个不同的一维HashTable。

当元素插入时，先从第一行开始，把KEY和这一行的长度(素数)取模，即可得到对应的存储位置。若该位置为空，就可以直接插入，否则表示Hash冲突，继续到下一行，重复上述过程。查询时，也是从第一行开始，每行都有一个对应位置，若存在一个KEY == 待查询KEY的，就表示找到了。这种Hash算法的处理冲突能力特别好，而且实现简单，很容易在共享内存中实现，还能很方便的在此基础上实现LRU淘汰算法，是比较推荐的算法。

小结

抛砖引玉到此为止，已经介绍了五种适合于后台开发中使用的数据压缩了，当然，还有更多的方法还等着大家的发掘。不过不难发现，他们有着一些共同点，这也是数据之所以能压缩的根本原理：

1. 出现越频繁的数据，应使用越短的编码，反之使用越长的编码

2. 物以类聚，把有相同规律的数据放一起，则共同部分可以压缩掉。

3. 利用一切可利用的信息量，包括位置信息，也是构成数据的一部分。