谈谈Zipack格式的设计初衷

这期主要谈谈当初我设计Zipack格式的初衷和规划，文章很多地方直接引用自年初写的Zipack设计稿。 什么是序列化格式

序列化格式是一种用于存储和传输的，线性排列的二进制数据。序列化格式用于在不同平台交换通用的数据格式。比如JSON就是一种流行的序列化格式。

序列化格式的性能评估标准

可以从时间和空间的角度评估一款序列化格式的性能。

• 时间：序列化格式编码和解码的速度。
• 空间：相同信息量下，序列化格式的体积。

为何要开发一套序列化格式

设计私有的 通信协议 / 数据格式 在大型企业中非常常见，如Google内部采用私有的路由协议取代TCP/IP协议，国内BAT内部也使用私有的RPC通信协议来取代HTTP。

互联网行业大致可以分类为2类：搞平台的和做内容的。任何一个平台，随着体量增大，内部不可避免地趋于臃肿，为此，从底层考虑新的协议或格式尤为重要。

Zipack准备借鉴messagepack的设计思想（不是基于），参考TCP/IP路由协议的前缀格式，设计出一套适用于企业和互联网平台的格式。

评估一款产品的好坏通常从功能、性能、安全性的角度来评估，序列化格式也不例外。

• 功能：相对于流行的JSON格式，Zipack可以支持新的数据类型，比如bytearray，timestamp，extention（扩展类型）...
• 性能：Zipack将采用多种数据压缩算法，空间上，预计较JSON能够节约20%~40%的体积；时间上，相对于文本格式的JSON，二进制格式的Zipack能够更快地编码、解码
• 安全：平台内部交流使用私有格式，一定程度上增加黑客攻击的难度（比如爬虫）

Zipack可能存在的局限性

• 在v8引擎（JavaScript引擎）上Zipack的速度可能慢于原生的JSON（原因是v8引擎之上无法获得接近硬件的速度）
• 使用时需要引入Zipack的依赖
• 可视化读写Zipack的插件需要另外开发，如浏览器调试和IDE编辑Zipack文件

应用场景

• 内存缓存
• 通信协议
• 配置文件
• ......

Huffman前缀编码（最优二叉树）

Zipack将汲取世界上各种优秀的编码思想，这其中包括JSON，message pack，protoBuf等，将他们组合成一套原创的压缩格式。

大体上Zipack使用Huffman来编码所有的数据类型，每个类型分配一前缀，前缀长度从1到8不等，具体见最下面的Zipack树图。

由于硬件的限制，无论是类型前缀，长度段还是内容负载，都是字节的整数倍，不到1字节的前缀和负载一起组成整字节。

信息编码的2大原则：无歧义、无冗余

信息论要求编码值（序列化的二进制值）与实际含义一一对应，才能将信息压缩至最小，而打破一一对应关系的情况分为2种：

• 歧义：同一种编码有多个不同的含义
• 冗余：多种编码对应同一个含义

Zipack的每种数据类型都避免了这2种情况。

扫描终止信号的2种模式：前缀VS休止符

扫描仪（decoder）在一条序列化数据上从左至右扫描的时候，当扫描到某一个“子元素/对象/字符/值”身上时，何时结束是一个关键点，通常有2种方式来暗示何时停止。

• 前缀式：将子元素的长度存在前缀中。
• 休止符式：通过末端的一个“休止符”来提示扫描仪，它可以是一个终止字符也可以是一个终止字节。

前一种将长度写在前缀中的方式在二进制的协议格式中非常常见，比如众多IP子协议和二进制序列化格式；后一种通过“休止符”来终止的方式则常见于海量的文本格式以及古老的文本型通讯协议，连DNA的解码都是通过“终止子”来分隔肽链。

Zipack中会综合使用2种终止模式。接下来要谈到的VLQ就属于后一种“休止符”。

VLQ变长编码（Variable-length quantity）

VLQ技术是一种流行的“变长量”编码方案，在序列化消息中从左向右扫描（big-endian）某个值时，每个字节的最高位如果是1则该值还有后续字节，知道扫描到最高位是0的字节为止。

VLQ节省空间的同时还保留了一定的扩展性。VLQ编码在Zipack的设计中经常出现。

VLQ自然数【重点】、VLQ自然偏移

VLQ自然数指在VLQ编码的基础上存储的二进制自然数。多字节VLQ自然数的实际值等于它的面值加上一个偏移值，这个偏移值等于上一级字节数的最大值加一，也就是本级的最小值。

偏移的原因在于，自然状态下不同的实数长度共享了一部分实数空间，比如3字节的实数包含了2字节的全部空间，例如 00 00 01 和 00 01都是1.。

所以每一种长度的实数的实际值要加上之前所有更短长度的空间总和。例如 00 01代表1，则 00 00 01代表257（255+2）。

不同字节数的VLQ整数和对应的实际值具有如下关系：

其中，每个min等于上一行的max+1。

min代表此整数空间中若干个7bit组“全0”的意义，max代表此整数空间中“全1”的意义。

“VLQ偏移自然数”是Zipack的基础，不论是实数类型还是各种对象的数量，都有VLQ偏移自然数的身影，以下简称VLQ自然数。

VLQ字符与字符串

VLQ字符指在VLQ自然数的基础上映射的Unicode字符。每个VLQ自然数对应一个Unicode序号。

VLQ字符串则是若干个VLQ字符无缝拼接而成，字符串前还需要一个VLQ自然数来表示字符的个数。VLQ字符串是Zipack的基本类型之一。

兼容性是万恶之源，utf8从信息论的角度严重浪费空间，Zipack的字符编码采用Unicode-on-VLQ的编码方案，与utf8彻底解耦，将每个字符的Unicode序号（自然数）存储为VLQ整数，彼此拼接在一起便成了Zipack字符串。

VLQ长度前缀

VLQ长度前缀指在VLQ自然数的基础上，VLQ自然数前缀暗示某个数据类型的长度，所谓的长度分4种情况：

• 字节流：纯粹二进制类型（字节流）中，VLQ自然数暗示字节的数量。
• 字符串：字符串类型（字符流）中，VLQ自然数暗示字符的数量。
• 列表：列表类型（数组）中，VLQ自然数暗示列表中元素的数量。
• 字典：存储键值对的字典类型中，VLQ自然数暗示键值对的数量。
• 浮点数：浮点数类型中，VLQ自然数暗示指数位的大小。（Zipack中并不一定使用）

注意，在数量较短的情况下，长度会以定长自然数的形式，存放在第一个byte中，目前这个宽度是5bit（见最下面的Zipack树）。

Zipack的数据类型

• 小自然数
• 正整数（正自然数）
• 负整数
• 正非整数
• 负非整数
• 小列表
• 列表
• 小字典
• 字典
• 短字符串
• 字符串
• 字节流
• True
• False
• null
• （保留类型）

字节流类型（纯二进制类型）

这个比较好理解，就是存储无格式的字节流（byteArray）。字节流文本型格式无法轻易存储的类型。

列表（数组）

列表是一种嵌套类型，其格式就是若干个元素顺序无缝拼接。Zipack流也是这么拼接的。

字典（键值对）

字典是一种嵌套类型，其格式是若干个键值对顺序无缝拼接：[键, 值, 键, 值...]。

首先让键的类型锁定为VLQ字符串（需要长度前缀），从而省去了类型字节。

本来根据“无序字典”的理论，应该对字符串键强行排序，用增量取代实际值，但由于我们统一使用VLQ字符，字符的Unicode编号上限不确定（不止于65535），因此无法对所有的字符串排序，所以我们的字典仍然是“有序字典”。

关于非整数（小数）

关于非整数的编码，Zipack采用原创的“精度反转算法”以取代IEEE浮点数。

计算机的发展历史上，用二进制存储自然数本是最“自然”的选择，后来为了存储负数，就出现了原码、2补码、zigzag等编码，再后来为了存储浮点数，就出现了3个主流的IEEE标准：

• 半精度half：16bit
• 单精度single：32bit
• 双精度double：64bit

但是以上三种都是浮点数编码，浮点数编码只是非整数编码的其中一种，全部的种类共有3种：

• 浮点数编码：存储【指数，有效部位】
• 分数编码：存储【分子，分母】
• 小数点分隔式：存储【整数部分，小数部分】

这就是通过2个自然数来编码1个非整数的3种范式。由于正小数和负小数是完全对称的（因为不包括0），所以只需要另外一个符号位来暗示正负性。

还需要指出，IEEE的3种精度只是浮点数编码范式的3种实现，而且还包含整数、NaN和Infinity等特殊类型，因此浪费了不少空间，以紧凑（compact）为宗旨的Zipack自然不能照搬，我们要一种原创的非整数格式。

经过综合的考虑，Zipack准备采用小数点分隔式编码，即将小数表示为整数部分和小数部分的自然值。

单字节的true、false、null

这三个比较简单，都是单字节的常量。具体可以参考Zipack的规格：https://gitee.com/zipack/spec

短字符串、短列表、小字典、弱精度浮点数

这里的短/小指的是字符串长度、列表元素数量、字典键值对的数量、浮点数的指数（以2为底）较小。对于这4种情况不用VLQ自然数来指定长度，直接使用镶嵌在首字节的4~5个bit来表示0~31的长度。

与这4个类型相比，字节流类型一般都很大（如图片），而其单位又最小（byte），所以不考虑短字节流。

保留类型

在已有的十几种格式之外，Zipack树上还有几个空缺位，可以作为“可定制”类型，比如适用于公司内部交流常用的格式，最常见的用法就是通过一个编号来指定一个对象，避免传递整个对象。

特别优待的实数类型：小自然数（小非负整数0~127）

在所有实数中，按照使用频率来分类的话，大致上有以下三种“趋势”（下面的">"符号比较的是使用频率）：

• 整数 > 浮点数
• 绝对值小的数 > 绝对值大的数
• 正数 > 负数

将3个“>”左边的实数组合在一起，就诞生了使用频率最最高的类型：较小的正整数和0，即小自然数。理所当然，小自然数的地位是最高的，应该受到最高的待遇，所以小自然数的前缀一定要最短，也就是1个bit：0。小自然数的整体长度是1个byte，能表示的范围就是0~127之间的整数。

关于整数编码（正负数分离）、正偏移和负偏移

在对有符号整数进行编码的方案上，主要有3种主流的编码方案，分别是：

• 原码：通过最高位表示整数的符号，简单直观，但造成“+0”和“-0”的冗余。
• 2的补码：最流行的整数编码，通过将负数“平移”至正数之上来进行编码，易于计算。
• zigzag：从0开始，将正负数交替编码，特点是，绝对值小的整数它的编码越“短”。

但是在序列化格式中，不用考虑怎样兼容所有整数，可以将正整数，负整数当作不同的数据类型，和其他的类型并列处理，无差别对待。

Zipack将正整数和负整数当作2种类型，都将VLQ二进制自然数作为自身的绝对值，但这个绝对值还要加上一个偏移值才得到实际值。

VLQ正整数的实际值等于VLQ值加上128，因为前面提到我们需要预留一个特殊优待的小自然数，小自然数的最大值是127。

VLQ负整数的实际值等于-1减去VLQ值，因为负整数从-1开始计。

Zipack流

Zipack格式天然支持流传输，在Zipack单体过于庞大时，可以拆分为多个Zipack对象，对象之间无缝衔接，从而做到“一边传输，一边解析”。不用像JSON一样需要一个分隔符来分隔不同的JSON对象，参考ndJSON。

Zipack的最优二叉树

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/