Welcome to serialize’s documentation!¶

序列化¶

简介¶

序列化是指将内存中的对象持久化。比如讲对象保存到磁盘。反过来从二进制流恢复到内存称为反序列化。序列化技术也广泛用于网络传输(如 RPC)、多进程通信。

序列化离我们并不遥远, 日常开发过程中，很多时候我们意识不到自己正在使用序列化，甚至在创建序列化协议。

日常序列化¶

这是一个常见的例子。

我们要保存一批语料，每一条有三个字段: 领域、句子、分类。最先想到的大概就是使用逗号分隔字段, 保存到文件中。

corpus.txt:

金融,昨天上证指数又跌了,1
计算机,PHP是世界上最好的语言,0
科技,GPT-3消耗资源很多,2

然后，把这个文本交给业务方用, 一切都很顺利。在这个场景中, 涉及到一些概念。

我们自定义了专用的序列化协议

尽管这个协议很简单，而且很不完美，但是它能满足业务需求。

这个序列化协议不是 schema-less 的

这份数据本身并不带有格式，要知道每个字段含义，必须提供 领域、句子、分类 这个 schema 才知道具体怎么解释语料。

而这个 schema 也是不明确的，比如没有明确说明第三个字段是 int 类型还是 string 类型。只能靠人观察。

困境¶

方案的缺陷: 当……

句子中有逗号¶

这是很明显的缺陷，也有很多种解决方法。

调整字段的顺序，把长文本类放在最后: 其他,3,我喜欢苹果,还喜欢西瓜

这是一种规避方案,固定解释前两个无歧义字段，剩下的都当作文本处理。
引入斜杠转义逗号: \, , 感觉没几个人有这耐性…… ，因为这意味着你还要继续实现转义斜杠: \\ ，还有预料不到的歧义逻辑。
使用 CSV。嗯…… 反正都是逗号分隔。

坏处就是，你要找一个csv解析库, 顺便学一学它的用法。
使用 json。

句子中有换行¶

这个问题，使用 csv 也解决不了, 建议用 json 或者 Excel。

schema-less¶

你幸苦制作了一批语料，两个月之后，因为记不起schema而不知道怎么使用，这是一件很恼火的事情。

csv 数据某种程度上说是自描述 (schema-less) 的, 可以通过表头表示每一列的含义，问题是 csv 的表头并不是强制的。

所以，这里我还是推荐使用 JSON:

schema-less 。

可以表示复杂数据，如 list-map 之间相互嵌套。

具有类型的概念。如 string、number、bool、null

如何解决¶

我还是推荐 json , 对 nlp 来说，它够用了，而且 json 是最容易使用和 debug 的无歧义序列化方案。

但要bb一句: 在其他领域，json 通常并不是好的选择。真正的生产环境的(非文本)序列化场景，有很多其他(二进制)序列化框架可供选择。

序列化框架¶

选择序列化框架的时候，有几个指标可以考虑。

是否人可阅读。即文本还是二进制类型的序列化。
解码速度
编码速度
数据编码后大小。这对网络IO有影响。

有很多网上的性能评测可以参考，只不过把它们用在自己的业务场景性能如何就是另外一回事了，不能尽信。

根据数据种类、要求的特性、传输方式、server/client性能的不同，对序列化框架的选择也有很大影响。

本章节是入门教程，主要介绍各个序列化框架的内部实现。以便在编码过程中对序列化框架做出正确的选择。

C/C++ 的序列化¶

介绍¶

C-Style 序列化是一种比较古老的序列化形式。这类底层语言在很多方面都不如高级语言好用，却在序列化方面出乎意料地简单。

得益于 C 内存操作能力，只需要将待序列化对象的内存内容拷贝出来就行了。

struct UserInfo
{
    char name[32];
    int age;
};

void writer(struct UserInfo *pInfo)
{
    FILE *fp = fopen("test.info", "wb");
    // 将 info 所处的内存内容直接写入文件
    fwrite(pInfo, 1, sizeof(struct UserInfo), fp);
    fclose(fp);
}

void reader(struct UserInfo *pInfo)
{
    FILE *fp = fopen("test.info", "rb");
    // 将文件内容恢复回来
    fread(pInfo, sizeof(struct UserInfo), 1, fp);
    fclose(fp);
}

只不过涉及到跨平台时，会有一些坑……

而这些问题也是几乎所有序列化库需要解决的。

大小端¶

不同大小端的系统会将同样的数据序列化为不同的格式。

一般方法是转换为统一的网络序。

字节对齐¶

内存的字节对齐也是阻止 C-Style 序列化推广的原因之一。

这个策略有助于加速数据在内存的寻址速度，但是对序列化毫无用处。

一般序列化库会直接去除对齐, 使数据紧凑化。采用的方式有 type+定长、flag实现的变长(Varint)、length+data 等。

JSON、XML¶

简介¶

比较简单，格式不做介绍。

这几种格式有很明显的特点: 可阅读性好、低效、schema-less。尤其是 JSON 更是因为JS亲儿子的身份在 HTTP 界经久不衰。

很适合于序列化配置等小数据量，对于大数据量的情况，通常并不是好的选择。
格式易于阅读，甚至还能添加注释。
对开发友好，入门0门槛。
具有卓越的跨语言跨平台性。具有基本的字符串操作的编程语言都能解析。
schema-less 格式非常灵活，能够存储非结构化文档。

对 Json 的思考¶

Json 的应用太广泛，已经无法单纯理解为一个序列化格式了，这也导致 Json 使用过程中的一些争论。从序列化角度去理解 Json，也许也能理解其中的设计:

Key 只能是 string

文档可以理解为 class、object, key 则对应了 property。即 Key 仅能作为字段的描述。

利用 key 存放数据, 是一种不合理的行为(虽然技术上是合法的)。

MessagePack 等框架中也明确规定 key 只能是 string，这样的设计并非技术上无法实现。而是因为当一种序列化格式支持复杂类型作为 key 的时候，结构就从 class 退化成了普通 Map 。在对象的序列化场景下有很大的限制。

注意: yaml 支持复杂类型作为 key。

Key 的 Unique 语义

Json 的 key 带有 unique 语义, 这也是另一个容易误用的特性。这种特性是因为 class 的 property 无法重名。

正常情况下不应该利用这种语义来达到去重的目的，而是在业务层做去重。

仅支持有限类型

Json 是 JS 子集, 不是 JS 。这种限制带来的好处也很大: 实现简单，不确定性小。

注意: yaml 支持通过 !! 扩充为任意类型

Protobuf¶

简介¶

Protobuf 是 google 推出的一种序列化格式, 应用非常广泛，如 grpc、tfrecord。

内部编码: https://developers.google.com/protocol-buffers/docs/encoding
使用文档: https://developers.google.com/protocol-buffers/docs/proto3
支持的数据格式: https://developers.google.com/protocol-buffers/docs/reference/google.protobuf

proto schema 案例¶

syntax = "proto3";

message SearchRequest {
    string query = 1;
    int32 page_number = 2;
    int32 result_per_page = 3;
}

字段后面的数字是 Field Number , 用于编码索引，其范围为 1~(2^29 - 1)。推荐将 1~15 范围的数值预留用于频繁访问的属性, 这个范围的 Field Number 进行 Varint 编码后只需要 1 字节, 16~2047 耗费 2 字节，越大的 Field Number 编码后字节越多。

probobuf 编码¶

类型	含义	适用类型
0	Varint(变长数值)	int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	64-bit(64位数值)	fixed64, sfixed64, double
2	Length-delimited(指定长度)	string, bytes, embedded messages, packed repeated fields
3	Start group	groups (deprecated)
4	End group	groups (deprecated)
5	32-bit(32位数值)	fixed32, sfixed32, float

每一个字段首字节表示类型, byte 末3位是主类型, 前5位是 Field Number, 其中首位 msb (most significant bit) 有特殊用途。

上图表示主类型为0(Varint)， Field Number 为 2 。

变长类型

这里的变长类型特指变长数值 - Varint 。 Varint 数值区域中每个 byte 首位标识后面还有没有内容(此标识即 msb)。当首位为1，表示后面还有内容，为 0 表示当前已经是最后一字节。

这种变长策略是 Protobuf 的亮点, 使整数类型的存储非常紧凑，小整数高位为0，这些无效位可以省略，所以通常只会占 1 byte，大整数才会占据更多空间。基于统计，越小的整数使用越频繁，这种策略是合理的。

int32 类型的 -1 二进制是 0xffffffff ，由于补码的特性，绝对值很小的负数有效位非常多。也许你已经猜到了，对于这个小整数，使用 Varint 编码却需要占据 5 字节。所以，对于有符号整数， Protobuf 先采用 ZigZag 映射为无符号整数，再进行编码。

定长类型

当 type 字段是定常类型, 只需要从后面取固定长度字节解释为对应类型， 1、5 两种主类型都是定常类型。

指定长度

字符串、结构体等类型长度没有上限，都需要手动指定长度，所以除了首字节type，还有第二段内容说明数据长度，再后面才是真正的数据。

Optional & Repeated

由于每个字段都有 Field Number 作为索引, Optional 字段可以不出现在编码中，即缺失。

Repeated 字段比较有意思。 Protobuf 存储的策略是相同的 Field Number 可以出现多次, 并且可以不连续，如下是包含了2个元素的数组(Field Number索引为3);

schema¶

Protobuf 编码有 type 的概念，但是作用很弱, 数据解释很依赖于 schema , 甚至基于 schema 可以对相同的数据做出不同解释。

比如 protobuf 支持的 option、默认值、数组、结构体等概念，都是在 .proto 文件中描述的，还有涉及到向后兼容性等功能， schema 层承载了大量业务逻辑。

如以下 schema (v1):

message TestMessage {
    string query = 1;
}

此时新增一个字段 (v2):

message TestMessage {
    string query = 1;
    optional string page_number = 2 [default = 10];
}

这种情况，如果 v2 客户端接收到 v1 协议数据, schema 层可以把这个字段补全。 v1 客户端接收到 v2 协议的消息，也能正确忽略这个字段.

总结¶

从各方面讲 Protobuf 比 json 更像是一种合格并且可靠的序列化格式。从上面的描述可以看出，Protobuf 有一定的编解码的性能损耗，但是消耗不大。

同时 protobuf 对编程非常友好，强类型、跨平台跨语言、周边完善。属于序列化方面的大一统框架，各方面比较平衡。

另一种古老而广泛应用的序列化格式是 ASN.1 。 protobuf 借鉴了它的协议描述层，并且定义了数据编码格式，而 ASN.1 并没有限定数据编码格式，底层实现可以选择 json、xml 等任意编码格式，甚至是私有编码格式，所以不做过多讨论。

MessagePack¶

官网的介绍: It’s like JSON. but fast and small.

官网: https://msgpack.org/
编码格式: https://github.com/msgpack/msgpack/blob/master/spec.md

MessagePack 也是一种紧凑的二进制序列化格式, 支持流式序列化，非常适合RPC传输，编解码速度、占用空间和 Protobuf 一个量级，其优势是 schema-less , 可以灵活地传输各种数据。

主要编码范式也是 type+length+data 以及 type+data。但实现数据紧凑的方式和 Protobuf 有所不同，Protobuf 使用首位标识后面是否有数据，而 MessagePack 通过类型系统决定整数有多长，如 uint8 存放小整数，uint16 类型存放大整数。

1 byte 类型¶

这类type本身就是一个值，没有data，只需要 type 字段就能表示。

这个分类只有三种类型: nil、true、false 。

如 nil (type 是 0xc0):

+--------+
|  0xc0  |
+--------+

数值类型¶

数值类型编码范式是 type+data。

根据数值大小自动选择 int8/int16/int32/int64 ,从而节省空间。

如 uint 16(type 是 0xcd):

+--------+--------+--------+
|  0xcd  |ZZZZZZZZ|ZZZZZZZZ|
+--------+--------+--------+

这里就有必要介绍 MessagePack 另一个创新之处: type 内部也能存储数据。对于太小的整数（0~127）, 其值可以直接存储在 type 里面，放在后 7 位。

如 uint7:

+--------+
|0XXXXXXX|
+--------+

所以数值 1 的编码为:

+--------+
|00000001|
+--------+

可变类型¶

字符串一般范式是 type length data。和数值类型一样，对于超短的字符串，length/type 可以存储在一个 byte 里面。

长度小于 31 的字符串:

+--------+========+
|101XXXXX|  data  |
+--------+========+

长度在 (2^8)-1 以内的字符串:

+--------+--------+========+
|  0xd9  |YYYYYYYY|  data  |
+--------+--------+========+

以此类推……

所有编码类型¶

format name	first byte (in binary)	first byte (in hex)
positive fixint	0xxxxxxx	0x00 - 0x7f
fixmap	1000xxxx	0x80 - 0x8f
fixarray	1001xxxx	0x90 - 0x9f
fixstr	101xxxxx	0xa0 - 0xbf
nil	11000000	0xc0
(never used)	11000001	0xc1
false	11000010	0xc2
true	11000011	0xc3
bin 8	11000100	0xc4
bin 16	11000101	0xc5
bin 32	11000110	0xc6
ext 8	11000111	0xc7
ext 16	11001000	0xc8
ext 32	11001001	0xc9
float 32	11001010	0xca
float 64	11001011	0xcb
uint 8	11001100	0xcc
uint 16	11001101	0xcd
uint 32	11001110	0xce
uint 64	11001111	0xcf
int 8	11010000	0xd0
int 16	11010001	0xd1
int 32	11010010	0xd2
int 64	11010011	0xd3
fixext 1	11010100	0xd4
fixext 2	11010101	0xd5
fixext 4	11010110	0xd6
fixext 8	11010111	0xd7
fixext 16	11011000	0xd8
str 8	11011001	0xd9
str 16	11011010	0xda
str 32	11011011	0xdb
array 16	11011100	0xdc
array 32	11011101	0xdd
map 16	11011110	0xde
map 32	11011111	0xdf
negative fixint	111xxxxx	0xe0 - 0xff

FlatBuffers¶

FlatBuffers 是 google 推出的另一种具有 schema 的序列化格式, 面向移动端。

github: https://github.com/google/flatbuffers
编码格式: https://github.com/dvidelabs/flatcc/blob/master/doc/binary-format.md

Flatbuffers 和 Protobuf¶

Flatbuffers 和 Protobuf 有很多共同点，比如都需要先编写一个协议描述文件，通过它生成各种语言的代码才能使用。也都是二进制编码，但是 Flatbuffers 的解码性能更好。更适合一次存储、多次读取，或者 client 解码性能很差的情况。

编码格式¶

FlatBuffers 编码方式应该是本文涉及的所有序列化方法中最复杂的。但是它的出发点很简单: 设计一种不需要解码的数据格式，以适应低性能的移动端。

设计思路¶

在 C/C++ 的序列化章节，提到过 C 的序列化可以直接把内存拷贝出来存储为二进制。这种编码方式优点很明显: 完全不需要编码和解码，效率极高。

Flatbuffers 也是按照这种思路来设计的, 只不过事实上无法做到这么简单粗暴。

考虑下面存在指针的例子。

struct User {
    char * name;
    int age;
};

name 字段是一个指针, 只存放数据地址，真正的数据需要根据指针所指向的地址去访问。 32位环境下，指针占用 4 字节，int 占用 4 字节，User 结构体总共固定占用 8 字节。对这种结构体，如果只是粗暴地把这8字节拷贝出去，而不管 name 真实引用的内容，会导致序列化不完整。

第一种解决方案是采用 length+data 的方法。这也是大部分序列化库选择的方案，在前面加一个长度字段，表示后面 N 个字节就是 name 的内容。

{"name": "Washington", "age": 10} 按照这种方法序列化的内容:

0x0a W a s h i n g t o n 0x00 0x00 0x00 0x0a

这种数据结构的劣势在于不能随机访问，如果定义了一个数组 struct User users[10], 原本每个对象占用8字节，想访问下标为 m 的对象只需要固定偏移 m*8 字节就可以，而这种方式导致每个对象的长度不一样，不能随机访问。这与 Flatbuffers 复制到内存即可用 的目标是违背的。

第二种解决方案是模仿内存空间的分配策略。即模拟指针的行为。一般的方法是为指针内容开辟另外的副数据段，将指针指向的内容存放在副数据段中，并记录下其在副数据段中的地址，序列化到 User 中。如下:

主数据段:

0x0000: 00 00 01 00 ; name 的地址 -> Washington
0x0004: 00 00 00 0a ; age = 10
0x0008: 00 00 01 0c ; name 的地址 -> Lincoln
0x000c: 00 00 00 0b ; age = 11

副数据段:

0x0100: W  a  s  h  ;
0x0104: i  n  g  t  ;
0x0108: o  n  00 00 ;
0x010c: L  i  n  c  ;
0x0110: o  l  n  00 ;

重要

再次提醒，这种方式需要客户端程序知道如何解释这个数据。

通过这种方式就可以实现解码 0 复杂度。

而 FlatBuffers 针对方案2还有以下改进。

相对定位

上面的方案中，第二个 User 结构体 name 内容是 00 00 01 0c , 使用时根据它找到 0x010c 地址就能获取到内容。

不过整个序列化内容所处的内存片段不可能起始地址是 0x0000 , 可能是任意值，这里假设是 base ，真实的数据地址就需要通过 base + 0x010c 运算得到。所以反序列化过程中，需要保留全局 base 地址。

而 flatbuffers 将绝对定位修改为相对当前位置偏移，不必保留base地址。所以 name 字段存放的地址会变成 数据地址(0x010c) - 当前地址(0x0004)=0x0108 。

注意: 思路是这样，真实协议会兼顾到底层编码、历史原因等, 会有差异。

vtable

Flatbuffers 数据不是简单地分为两段。除了数据头部的元信息, 还有vtable, 总共四段。 vtable 的存在使数据序列化字段的存储可以乱序。可以理解为 vtable 是数据格式, table 是上述主数据段，多个 table 数据段可以共享一个 vtable 格式。

另外， vtable 也是实现 flatbuffers schema-less 的关键。

重要

以上纯属个人对 Flatbuffers 的理解，官方并没有提及。如有出入，欢迎修正。

数据说明¶

下面通过官方案例讲解真实的 flatbuffers 数据编码。

Schema

namespace Eclectic;

enum Fruit : byte { Banana = -1, Orange = 42 }
table FooBar {
    meal      : Fruit = Banana;
    density   : long (deprecated);
    say       : string;
    height    : short;
}
file_identifier "NOOB";
root_type FooBar;

待编码的 json 内容

{ "meal": "Orange", "say": "hello", "height": -8000 }

编码结果

header:

    +0x0000 00 01 00 00 ; find root table at offset +0x0000100.
    +0x0004 'N', 'O', 'O', 'B' ; possibly our file identifier

    ...

table:

    +0x0100 e0 ff ff ff ; 32-bit soffset to vtable location
                        ; two's complement: 2^32 - 0xffffffe0 = -0x20
                        ; effective address: +0x0100 - (-0x20) = +0x0120
    +0x0104 00 01 00 00 ; 32-bit uoffset string field (FooBar.say)
                        ; find string +0x100 = 256 bytes _from_ here
                        ; = +0x0104 + 0x100 = +0x0204.
    +0x0108 42d         ; 8-bit (FooBar.meal)
    +0x0109 0           ; 8-bit padding
    +0x010a -8000d      ; 16-bit (FooBar.height)
    +0x010c  ...        ; (first byte after table end)

    ...

vtable:

    +0x0120 0c 00       ; vtable length = 12 bytes
    +0x0122 0c 00       ; table length = 12 bytes
    +0x0124 08 00       ; field id 0: +0x08 (meal)
    +0x0126 00 00       ; field id 1: <missing> (density)
    +0x0128 04 00       ; field id 2: +0004 (say)
    +0x012a 0a 00       ; field id 3: +0x0a (height)

    ...

string:

    +0x0204 05 00 00 00 ; vector element count (5 ubyte elements)
    +0x0208 'h' 'e'     ; vector data
    +0x020a 'l' 'l'     ; vector data
    +0x020c 'o'         ; vector data
    +0x020d  00         ; zero termination
                        ; special case for string vectors

    ...

解释流程:

流程如下

header 首字节存放第一个 table 的地址偏移量。
table 首字节存放自己引用的 vtable 的地址偏移量。
3、4、5 步骤分别是 schema 中 0、1、2、3 字段在 table 中的偏移量，以便取数。

可以看到 vtable 中字段顺序与 schema 是严格对应的，而 table中的字段与 vtable 中的顺序可以不一样。
vtable中只是说了数据起始地址，真正的数据需要按照 schema 来解释。

比如 meal 字段是 enum, 底层存储固定为 4 字节 int, 则从起始地址 0x0108 取 4 字节数据。

say 字段为 string, 其值 0x00010000 应该解释为地址偏移量, 则找到相应地址对应的内容为 “hello”

FlexBuffers¶

官方有 FlatBuffers 的 schema less 版本: FlexBuffers

总结¶

由于数据结构比较复杂，并不能直观地看出 Flatbuffers 的编码复杂度, 目测 FlatBuffers 的相对定位策略对编码性能影响还是比较大的，网传各种压测结果也能佐证其编码复杂度相比 Protobuf 高很多。所以这种策略相当于加重服务端复杂度来减轻客户端负担。

BSON¶

官网: http://bsonspec.org/

BSON 是 MongoDB 文档的存储格式。

和 Json 一样, BSON 也是一种 schema-less 的序列化格式。如果不追求数据的可阅读性, 还喜欢 Json 的灵活， bson 可以作为一个候选。另外 bson 修改成本小，比 Json 效率高，扩充了 Json 类型, 支持 DateType、BinData 等。

BSON 协议比较简单。见 http://bsonspec.org/spec.html 。

基础类型¶

BSON 基础类型都是固定长度。

类型	占用空间
byte	1 byte (8-bits)
int32	4 bytes (32-bit 有符号整型、补码)
int64	8 bytes (64-bit 有符号整型、补码)
uint64	8 bytes (64-bit 无符号整型)
double	8 bytes (64-bit IEEE 754-2008 浮点数)
decimal128	16 bytes (128-bit IEEE 754-2008 十进制浮点)

变长类型¶

string: 变长类型和 protobuf 差不多, 普遍采用 length+data 的方式编码
cstring: cstring 是 c 风格字符串, 约定以 0 作为字符串结尾, 不需要长度字段。
binary: 二进制数据。编码方式为 length(int32) subType(byte) data

key-value¶

key-value 格式是 json 特色格式, key 是字符串，value可以是多种类型。

编码为: valueType(byte) key(cstring) value

总结¶

从功能上来说，bson 是json 的扩充。

反序列化效率高

由于基础类型直接是二进制存储，反序列化效率比json高很多。

从存储空间来说， BSON 并不见得比 Json 好

对于字符串类型，json需要额外耗费两个双引号，而 BSON 也需要额外两字节指定长度和结束字符。

最常用的数值类型 int32 在 bson 中固定耗费 4 字节, 而通常情况下，小数值(如 1、2)在 json 中只需要存储1字节，甚至 1000 以内的整数也只需要3字节。

对于数组, BSON 内部存储为 {0: xx, 1: xx, 2: xx} , 这也是 BSON 一个值得吐槽的地方。

修改成本很低

BSON 并不属于紧凑类型格式，但固定长度的基础类型带来的好处是修改成本极小。

考虑一个小数字如 1，在 json 字符串中虽然只占用1字节，如果运行期需要修改为 10，则需要把这个字段后面所有内容都往后移动1位，才能擦除原有值写入 10。

而BSON中是固定长度，就不会有这种问题，非常适合做修改。

这也是 MongoDB 使用 BSON 的原因，这个优势是其他序列化方法无法比拟的。

BSON 反序列化快、修改成本小，面向存储的优势极大。

Apache Thrift¶

官网: http://thrift.apache.org/
github: https://github.com/apache/thrift/

Thrift 思路和 ASN.1 更像，并不和某一种序列化方式绑死，不过其内部仍然自带三种序列化实现: Json、简单二进制编码、紧凑二进制编码。

Thrift 将 schema 编译好后保存在程序中，网络传输只传输数据，不涉及 type。

Thrift 官方文档写的不怎么好。只找到下面两个链接介绍其内部的紧凑编码:

wiki: https://cwiki.apache.org/confluence/display/THRIFT/New+compact+binary+protocol
jira: https://issues.apache.org/jira/browse/THRIFT-110
紧凑编码格式: compact-proto-spec-2.txt

通过上面的链接可以依稀看出来, 其紧凑编码格式从 Protobuf 借鉴了很多。

Protocol 实现代码位于 thrift github 仓库的 lib/cpp/src/thrift/protocol/ 目录

下面稍微介绍下二进制编码、紧凑二进制编码。

简单二进制编码¶

实现代码: lib/cpp/src/thrift/protocol/TBinaryProtocol.tcc

和想象中一样，这种方式和 C-style 拷贝内存的方式并没有什么不同。

以 int64 类型的整数为例。

可以看到, 直接取了数据内存的 8 byte 写进去了(int64 占8byte内存)。

紧凑二进制编码¶

实现代码: lib/cpp/src/thrift/protocol/TCompactProtocol.tcc

紧凑编码中对数值的编码借鉴了 Protobuf：

varint¶

如果数值类型是 double、float 等类型，先转换为 int 类,
对 int 类进行 zig-zag 编码。
使用每个 byte 的首位标识内容是否结束，为 1 则后面还有内容，为 0 表示当前是最后的 byte 。

string¶

对于 string、binary ，采用 length data 的编码方式。

collection¶

在紧凑编码中， map、list、set 统称为 collection 。

编码方式是 subtype length data ， subType 字段用于说明具体是哪个类型。

collection 还有另外一个处理，如果 length <= 14，则省略 1 字节，直接把 length 写到 subtype 里面, 这一点很像 MessagePack 。

附¶

ZigZag 源码

/**
* Convert l into a zigzag long. This allows negative numbers to be
* represented compactly as a varint.
*/
template <class Transport_>
uint64_t TCompactProtocolT<Transport_>::i64ToZigzag(const int64_t l) {
    return (static_cast<uint64_t>(l) << 1) ^ (l >> 63);
}

/**
* Convert from zigzag long to long.
*/
template <class Transport_>
int64_t TCompactProtocolT<Transport_>::zigzagToI64(uint64_t n) {
    return (n >> 1) ^ static_cast<uint64_t>(-static_cast<int64_t>(n & 1));
}

Apache Avro¶

官网: https://avro.apache.org
编码格式: https://avro.apache.org/docs/current/spec.html

Avro 类似 thrift, 也是 Apache 旗下的 RPC 框架，主要面向大数据场景。 schema定义非常灵活，属于半 schema-less。

Avro 内部支持两种序列化方式：

Json。用于开发环境或者其他要求数据可阅读的场合(如 Web )
二进制。常用于生产环境

Schema¶

作为一个带 schema 的序列化框架，为了应对真实大数据场景中的数据多样性，Avro 对 Schema 做了几个改进：

schema 直接使用 json 定义好就可直接使用，且不需要像 thrift、Protobuf 一样编译。实现运行时定义 schema 。
每次序列化数据时，头部都要带上 schema。即每条数据都是自描述的，实现类似 schema-less 的功能。
传递数据时可以传递单条数据或者多条数据，传递多条数据可以提高 schema 的利用效率。
对于 schema 本身比较大的情况，为了减少每条数据的体积，可以只传递 schema 的 8-bit 指纹。

schema 案例

{
    "type": "record",
    "name": "Test",
    "fields" : [
        {"name": "a", "enum": "long"},
        {"name": "b", "type": "string"},
        {"name": "c", "type": "enum", "symbols": ["A", "B", "C"]}
    ]
}

数据¶

由于每条数据都会带有单独的schema, 数据部分就不用再维护 schema , 只负责按照schema中fields定义的顺序存储数据就可以了。

如以下fields:

[
    {"name": "a", "enum": "long"},
    {"name": "b", "type": "string"}
]

上图流程中，需要序列化的数据是 {"a": 27, "b": "foo"} , 存储的格式如下:

0x36 0x06 f o o

0x36: 27 进行 zig-zag 编码后的16进制。

0x06: 十进制3，即 foo 字符串长度。也是 zig-zag 编码。

解码的时候，如果缺少 schema , 并不知道 0x36 应该如何解释, 有 schema 后，才知道需要解析成整数 27。所以数据对 schema 的依赖性非常强，而且schema的独立存储让数据部分变得比 protobuf 还紧凑。

对于 enum ，Avro 根据 schema 中列举的枚举值对他们进行顺序编号，变成 int ，如上面的枚举值 ["A", "B", "C"] ,分别编码成 0/1/2 。

对于 float，由于 float 在内存中固定占用 4 字节，先把它内存中的 buffer 强制解释为 int32 , 然后使用 int 的编码方法处理。

其他说明¶

本文档尽量保证中立地介绍各种序列化库的内部编码方式，所有提及编解码性能的部分只是理论猜测。实际操作过程中，编解码性能根据各种语言的实现会有很大的差别, 网上各种压测也存在数据集偏离的情况。

从上面介绍可以看出，序列化的优化都是对于数值，并不适用于字符串类型。所以一般拿纯文本来测试序列化都是耍流氓，因为这种情况下一般没必要用序列化， txt/json + zip 压缩几乎可以秒杀一切。

另外，真实使用场景中如果很在意体积，也可以通过 zip/gzip 对序列化结果进行二次压缩。

数据归档¶

文件与磁盘¶

磁盘与文件系统¶

磁盘作为一种存储介质，有自己的最小存储单位 —— 扇区。扇区是物理划分出的存储块，存在于现实生活中，一般大小是 512 字节。

操作系统的文件系统也有自己的存储单位，叫块。典型文件系统的块大小是 4K。

按照典型值来算，一个文件系统块包含了 8 个物理扇区, 这 8 个扇区一定是连续的，在分区的时候就固定好了。

磁盘的物理结构长久以来都没有变化，使用机械旋转进行寻址和读取。机械硬盘最大转速普遍 7200转/min ，是一种比较低效的 IO 介质。

由于这种物理特性，磁盘在进行性连续读取的时候，IO性能非常好。进行随机读取的时候，极端情况下每次读一个扇区就要寻址一次，效率很差。

注解

这种 极端情况 实际发生概率非常高。比如训练图像模型的时候，每个图像文件很小，读取的文件顺序经过 shuffle , 就会有这种情况。

文件存储¶

一些特性¶

文件一定是按照块分配空间的，对于占不满一个块的文件，也一定会单独占用一块。

所以大量小文件会导致磁盘利用率很低。
小于4K的文件，一个块就可以存储。
文件大于4K, 就需要占用多个块。

碎片¶

分区在刚使用的时候，同一个文件占用的磁盘块、扇区都是连续的。

随着时间的推移，经常有删除旧文件的操作，会形成某个磁盘片区空闲，而周围的磁盘块被占用的情况，类似于空洞，这种情况叫 磁盘碎片 。

磁盘碎片进一步导致文件存储不连续。

如果某一片区域删除了一个 8K 的旧文件，让出了空闲空间，这时候对文件系统写入一个 20K 的文件，就需要在另外一个地方再找12K空间。这个文件就会存储在磁盘的两个不同地方。

还有另一种情况也会导致文件存储不连续。

如果有一个文件初始大小 8K, 且后方块已经存放了其他文件。然后以追加模式打开这个文件，写入其他内容。这个时候也需要在其他地方寻找空闲块

由于文件可能存储在磁盘不同的地方，所以文件头有一个索引。

文件夹不存储内容，但是要存储当前文件夹包含的文件的索引。这也是文件夹一般都占用 4K 的原因。

对于包含文件比较多的文件夹，4K无法存储下所有文件元信息，则需要更多空间，如上图的 tmp 文件夹。

如果需要存储大量小文件( 小于 4K)，也不适合用文件系统来存储，因为就算一个文件只有 1 字节，也会至少分配 4K 的空间。但不必担心空文件，操作系统有优化，空文件并不会占用空间。

在磁盘分区的时候，可以选择块大小，块选择的大了，不利于小文件存储，但是能加速大文件 IO 性能，块选择小了，对小文件存储有利，但是可能产生很多磁盘碎片，降低 IO 性能。所以大数据磁盘块一般设置为 64M 这个级别。

如果要存储大量小文件，还要保证 IO 性能，可以选择把他们打包成压缩包，变成一个文件。虽然打包成单文件并不能保证文件不会被分片，但是操作系统会尽量保证连续，分片数量更少。另一方面，减少文件大小，也能进一步提升 IO 性能。这样做的影响是首次读取可能很慢，类似于 Hadoop 慢启动的问题，只不过没有 Hadoop 那么严重。

Tar¶

tar 规范: https://www.gnu.org/software/tar/manual/html_node/Standard.html
tar 源码: https://ftp.gnu.org/gnu/tar/

功能¶

tar 格式的功能很简单: 将多个文件打包成一个文件。

Linux 的 tar 命令可用于打包、解包 tar 文件，也经常能看到 tar.gz 、 tar.bz 等后缀的压缩文件。其实 tar 本身并不提供压缩功能，.tar.gz 文件是通过 tar 将多个文件打包成 .tar 文件，再调用 gzip 命令将单个 .tar 文件压缩为 .tar.gz 。只不过 tar 命令为了使用上的便利，提供了 -g 选项用于自动调用 gzip

文件格式¶

tar 是一种古老的格式, 它被设计之初，是用于将多个文件归档为单文件，从而能够写入到磁带上。磁带并没有文件系统的概念，tar 模拟了文件系统部分功能。

tar 最小存储单元是 512 字节，内部每个文件开始的 512 字节存放文件元信息，如文件名、文件长度、权限等， tar 末尾有两个块内容存放全 0 ，标识此tar归档已经结束。

tar 中存储的文件元信息并不是统一管理，而是跟随被归档文件，所以很适合于顺序读取以及追加写入。如果tar中存在多个同名文件，解压的时候，以最后的文件内容为准，这也让 tar 很适合作为备份的格式。

重要

实际归档的时候，如果文件名+路径大于100字符，会导致 header 中元信息存不下，出现扩展 header, 最直接的影响就是浪费了512字节，如果文件大小只有 1K，却因为文件名太长而导致有 1K 的 header，空间利用率就很低。

tar 是一种入门级的归档格式，如果有兴趣，推荐按照规范实现一个 tar 的解压缩程序。

注解

tar 格式还定义了稀疏存储模式, 特别适合于存储像 coredump 这类大部分内容都是 0 的文件。

tar + gzip¶

Linux 上 tar.* 的压缩方式都是将所有文件打包到单个 tar，然后使用某种算法压缩。

理论上压缩过后的文件要支持增量写入、顺序读写是比较困难的。如果所采用的压缩算法支持增量压缩，那么压缩包就也可以支持增量写入，但是顺序读写还是比较困难。

Zip¶

zip 格式: https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT
zip 格式(PDF版): http://www.idea2ic.com/File_Formats/ZIP%20File%20Format%20Specification.pdf

两个版本文档稍微有些区别, 下面的讲解以 PDF 版为准。

注解

我也不知道目前流通的是哪个版本, 要翻源码确认一下。但是整体思路都是一样的。

zip 文档结构¶

基础结构:

[local file header 1]
[file data 1]
[data descriptor 1]
.
.
.
[local file header n]
[file data n]
[data descriptor n]

[archive decryption header]
[archive extra data record]
[central directory]
[zip64 end of central directory record]
[zip64 end of central directory locator]
[end of central directory record]

从上面的结构可以明显看到， zip 压缩策略与 tar.* 明显不同，tar 将所有文件打包到一起进行压缩， zip 保留了文件元信息, 只对内容进行压缩(即 [file data] 段), 这个特性使zip在不进行解压的情况下就能得到文件信息。

文件数据¶

每个文件包含三个数据段: local file header/file data/file descriptor 。

一个 zip 中可以包含多个文件，即以上三段重复多次。

其中 local file header 包含文件元信息，如文件名、压缩前大小、压缩后大小、校验码。 file data 包含压缩后的数据。 file descriptor 是 local file header 的补充，因为 local file header 首先写入zip包，而有些信息无法在压缩前就得知，如压缩后大小，就可以在 file descriptor 中补充, 多用于无法进行 seek 操作的存储介质。

local file header 结构:

local file header signature     4 bytes  (0x04034b50)
version needed to extract       2 bytes
general purpose bit flag        2 bytes
compression method              2 bytes
last mod file time              2 bytes
last mod file date              2 bytes
crc-32                          4 bytes
compressed size                 4 bytes  // 压缩后大小
uncompressed size               4 bytes
file name length                2 bytes
extra field length              2 bytes
file name (variable size)
extra field (variable size)

中央目录结构¶

另一个很重要的结构是 central directory (中央目录结构)。

central directory:

[file header 1]
.
.
.
[file header n]
[digital signature]

File header:

central file header signature   4 bytes  (0x02014b50)
version made by                 2 bytes
version needed to extract       2 bytes
general purpose bit flag        2 bytes
compression method              2 bytes
last mod file time              2 bytes
last mod file date              2 bytes
crc-32                          4 bytes
compressed size                 4 bytes // 压缩后大小
uncompressed size               4 bytes
file name length                2 bytes
extra field length              2 bytes
file comment length             2 bytes
disk number start               2 bytes
internal file attributes        2 bytes
external file attributes        4 bytes
relative offset of local header 4 bytes // 文件数据偏移量
file name (variable size)
extra field (variable size)
file comment (variable size)

Digital signature:

header signature                4 bytes  (0x05054b50)
size of data                    2 bytes
signature data (variable size)

中央目录结构在zip中的设计有几个特点:

此结构放在zip文件末尾。这使得zip在追加文件的时候比较方便，对整个 zip 包影响很小。

存放了所有文件的信息。这种设计让 zip 具备了一定程度的随机读取能力，

所以, 对于大量小文件，如果使用zip压缩，使用时只需要将 zip 包尾部的少量信息加载到内存，就能根据根据其中的信息找到需要的文件并解压出来。

警告

zip 的随机读取仅限于理论，实际情况要看库的实现方式，比如 Python 读取zip，使用过程中发现仍然会把整个 zip 文件缓存到内存。

7Z¶

格式介绍¶

下面是 7Z 数据段组织结构，为了便于理解，简化了 Header 部分。

SignatureHeader
[PackedStreams]
[PackedStreamsForHeaders]
[Header]

其中 Header 结构如下, 精简了很多无关的部分。

{
    ArchiveProperties
    AdditionalStreams
    MainStreamsInfo
    {
        PackInfo
        {
            PackPos
            NumPackStreams // 文件数量
            Sizes[NumPackStreams] // 每个文件压缩后大小
            CRCs[NumPackStreams] // 每个文件校验码
        }
        CodersInfo
        SubStreamsInfo
        {
            NumUnPackStreamsInFolders[NumFolders];
            UnPackSizes[] // 压缩前大小
            CRCs[]
        }
    }

    FilesInfo  // 文件名信息
    {
        NumFiles
        Properties[]
        {
            ID
            Size
            Data
        }
    }
}

7Z 的结构类似于 Zip, 元数据也是存放在文件末尾, 并且保留了压缩包中所有文件的信息。 7Z 是一种更加紧凑的压缩结构, 但也丢失了很多文件原始信息，如权限等，所以不适合用于文件备份。

7Z 文档写的比较详细，但是它更多的算是一个软件，而不是一种格式规范。因为内部实现是很多压缩算法合集, 而且针对资源消耗做了很多定向优化。 (所以咱也没看懂文档写的什么)

等以后有空研究它的实现细节，再继续补充。

构造 Header 的部分代码截取如下:

void COutArchive::WriteHeader(
    const CArchiveDatabaseOut &db,
    UInt64 &headerOffset)
{
    WriteByte(NID::kHeader);

    // Archive Properties
    if (db.Folders.Size() > 0)
    {
        // 写入 MainStreamsInfo.PackInfo
        WriteByte(NID::kMainStreamsInfo);
        WritePackInfo(0, db.PackSizes, db.PackCRCs);
        // 写入 MainStreamsInfo.CodersInfo
        WriteUnpackInfo(db.Folders, (const COutFolders &)db);

        ... ...

        // 写入 MainStreamsInfo.SubStreamsInfo
        WriteSubStreamsInfo(db.Folders, (const COutFolders &)db, unpackSizes, digests);
        WriteByte(NID::kEnd);
    }


    WriteByte(NID::kFilesInfo);
    WriteNumber(db.Files.Size());

    {
        /* ---------- Empty Streams ---------- */
        ... ...
    }


    {
        /* ---------- Names ---------- */
        ... ...
        WriteByte(NID::kName);
        WriteNumber(namesDataSize);
        WriteByte(0);
        FOR_VECTOR (i, db.Files)
        {
            const UString &name = db.Names[i];
            for (unsigned t = 0; t <= name.Len(); t++)
            {
                wchar_t c = name[t];
                WriteByte((Byte)c);
                WriteByte((Byte)(c >> 8));
            }
        }

    }
}

数据库¶

Sqlite。嵌入式数据库
RocksDB、LevelDB。高性能KV数据库，可以当嵌入式KV数据库。
Redis。 KV数据库
Postgresql。号称最先进的开源数据库。
Mysql。号称最流行的开源数据库。
Etcd。作为实现分布式一致性的介质。