序列化格式是一种用于存储和传输的,线性排列的二进制数据。序列化格式用于在不同平台交换通用的数据格式。比如JSON就是一种流行的序列化格式。
可以从时间和空间的角度评估一款序列化格式的性能。
设计私有的 通信协议 / 数据格式 在大型企业中非常常见,如Google内部采用私有的路由协议取代TCP/IP协议,国内BAT内部也使用私有的RPC通信协议来取代HTTP。
互联网行业大致可以分类为2类:搞平台的和做内容的。任何一个平台,随着体量增大,内部不可避免地趋于臃肿,为此,从底层考虑新的协议或格式尤为重要。
Zipack准备借鉴messagepack的设计思想(不是基于),参考TCP/IP路由协议的前缀格式,设计出一套适用于企业和互联网平台的格式。
评估一款产品的好坏通常从功能、性能、安全性的角度来评估,序列化格式也不例外。
Zipack将汲取世界上各种优秀的编码思想,这其中包括JSON,message pack,protoBuf等,将他们组合成一套原创的压缩格式。
大体上Zipack使用Huffman来编码所有的数据类型,每个类型分配一前缀,前缀长度从1到8不等,具体见最下面的Zipack树图。
由于硬件的限制,无论是类型前缀,长度段还是内容负载,都是字节的整数倍,不到1字节的前缀和负载一起组成整字节。
信息论要求编码值(序列化的二进制值)与实际含义一一对应,才能将信息压缩至最小,而打破一一对应关系的情况分为2种:
Zipack的每种数据类型都避免了这2种情况。
扫描仪(decoder)在一条序列化数据上从左至右扫描的时候,当扫描到某一个“子元素/对象/字符/值”身上时,何时结束是一个关键点,通常有2种方式来暗示何时停止。
前一种将长度写在前缀中的方式在二进制的协议格式中非常常见,比如众多IP子协议和二进制序列化格式;后一种通过“休止符”来终止的方式则常见于海量的文本格式以及古老的文本型通讯协议,连DNA的解码都是通过“终止子”来分隔肽链。
Zipack中会综合使用2种终止模式。接下来要谈到的VLQ就属于后一种“休止符”。
VLQ技术是一种流行的“变长量”编码方案,在序列化消息中从左向右扫描(big-endian)某个值时,每个字节的最高位如果是1则该值还有后续字节,知道扫描到最高位是0的字节为止。
VLQ节省空间的同时还保留了一定的扩展性。VLQ编码在Zipack的设计中经常出现。
VLQ自然数指在VLQ编码的基础上存储的二进制自然数。多字节VLQ自然数的实际值等于它的面值加上一个偏移值,这个偏移值等于上一级字节数的最大值加一,也就是本级的最小值。
偏移的原因在于,自然状态下不同的实数长度共享了一部分实数空间,比如3字节的实数包含了2字节的全部空间,例如 00 00 01 和 00 01都是1.。
所以每一种长度的实数的实际值要加上之前所有更短长度的空间总和。例如 00 01代表1,则 00 00 01代表257(255+2)。
不同字节数的VLQ整数和对应的实际值具有如下关系:
字节数 | 整数空间 | min | max |
---|---|---|---|
1 | 2^7 | 0 | -1+2^7 |
2 | 2^14 | 2^7 | -1+2^7+2^14 |
3 | 2^21 | 2^7+2^14 | -1+2^7+2^14+2^21 |
n | 2^7n | 2^7+2^14+...+2^7(n-1) | -1+2^7+2^14+...+2^7n |
其中,每个min等于上一行的max+1。
min代表此整数空间中若干个7bit组“全0”的意义,max代表此整数空间中“全1”的意义。
“VLQ偏移自然数”是Zipack的基础,不论是实数类型还是各种对象的数量,都有VLQ偏移自然数的身影,以下简称VLQ自然数。
VLQ字符指在VLQ自然数的基础上映射的Unicode字符。每个VLQ自然数对应一个Unicode序号。
VLQ字符串则是若干个VLQ字符无缝拼接而成,字符串前还需要一个VLQ自然数来表示字符的个数。VLQ字符串是Zipack的基本类型之一。
兼容性是万恶之源,utf8从信息论的角度严重浪费空间,Zipack的字符编码采用Unicode-on-VLQ的编码方案,与utf8彻底解耦,将每个字符的Unicode序号(自然数)存储为VLQ整数,彼此拼接在一起便成了Zipack字符串。
VLQ长度前缀指在VLQ自然数的基础上,VLQ自然数前缀暗示某个数据类型的长度,所谓的长度分4种情况:
注意,在数量较短的情况下,长度会以定长自然数的形式,存放在第一个byte中,目前这个宽度是5bit(见最下面的Zipack树)。
这个比较好理解,就是存储无格式的字节流(byteArray)。字节流文本型格式无法轻易存储的类型。
列表是一种嵌套类型,其格式就是若干个元素顺序无缝拼接。Zipack流也是这么拼接的。
字典是一种嵌套类型,其格式是若干个键值对顺序无缝拼接:[键, 值, 键, 值...]。
首先让键的类型锁定为VLQ字符串(需要长度前缀),从而省去了类型字节。
本来根据“无序字典”的理论,应该对字符串键强行排序,用增量取代实际值,但由于我们统一使用VLQ字符,字符的Unicode编号上限不确定(不止于65535),因此无法对所有的字符串排序,所以我们的字典仍然是“有序字典”。
关于非整数的编码,Zipack采用原创的“精度反转算法”以取代IEEE浮点数。
计算机的发展历史上,用二进制存储自然数本是最“自然”的选择,后来为了存储负数,就出现了原码、2补码、zigzag等编码,再后来为了存储浮点数,就出现了3个主流的IEEE标准:
但是以上三种都是浮点数编码,浮点数编码只是非整数编码的其中一种,全部的种类共有3种:
这就是通过2个自然数来编码1个非整数的3种范式。由于正小数和负小数是完全对称的(因为不包括0),所以只需要另外一个符号位来暗示正负性。
还需要指出,IEEE的3种精度只是浮点数编码范式的3种实现,而且还包含整数、NaN和Infinity等特殊类型,因此浪费了不少空间,以紧凑(compact)为宗旨的Zipack自然不能照搬,我们要一种原创的非整数格式。
经过综合的考虑,Zipack准备采用小数点分隔式编码,即将小数表示为整数部分和小数部分的自然值。
这三个比较简单,都是单字节的常量。具体可以参考Zipack的规格:https://gitee.com/zipack/spec
这里的短/小指的是字符串长度、列表元素数量、字典键值对的数量、浮点数的指数(以2为底)较小。对于这4种情况不用VLQ自然数来指定长度,直接使用镶嵌在首字节的4~5个bit来表示0~31的长度。
与这4个类型相比,字节流类型一般都很大(如图片),而其单位又最小(byte),所以不考虑短字节流。
在已有的十几种格式之外,Zipack树上还有几个空缺位,可以作为“可定制”类型,比如适用于公司内部交流常用的格式,最常见的用法就是通过一个编号来指定一个对象,避免传递整个对象。
在所有实数中,按照使用频率来分类的话,大致上有以下三种“趋势”(下面的">"符号比较的是使用频率):
将3个“>”左边的实数组合在一起,就诞生了使用频率最最高的类型:较小的正整数和0,即小自然数。理所当然,小自然数的地位是最高的,应该受到最高的待遇,所以小自然数的前缀一定要最短,也就是1个bit:0。小自然数的整体长度是1个byte,能表示的范围就是0~127之间的整数。
在对有符号整数进行编码的方案上,主要有3种主流的编码方案,分别是:
但是在序列化格式中,不用考虑怎样兼容所有整数,可以将正整数,负整数当作不同的数据类型,和其他的类型并列处理,无差别对待。
Zipack将正整数和负整数当作2种类型,都将VLQ二进制自然数作为自身的绝对值,但这个绝对值还要加上一个偏移值才得到实际值。
VLQ正整数的实际值等于VLQ值加上128,因为前面提到我们需要预留一个特殊优待的小自然数,小自然数的最大值是127。
VLQ负整数的实际值等于-1减去VLQ值,因为负整数从-1开始计。
Zipack格式天然支持流传输,在Zipack单体过于庞大时,可以拆分为多个Zipack对象,对象之间无缝衔接,从而做到“一边传输,一边解析”。不用像JSON一样需要一个分隔符来分隔不同的JSON对象,参考ndJSON。
Zipack参考资料 官网:http://zipack.github.io/ (同Gitee) 百科:https://baike.baidu.com/item/zipack
仓库:https://github.com/zipack (同Gitee) 介绍:https://jimmy.blog.csdn.net/article/details/107031802
作者:https://jimmy.blog.csdn.net/