对象序列化与反序列化是各类语言构建的应用间通信的基石,一个高效、兼容性良好、易于交换的序列化方案是重要的。无论是高级语言内置的实现,或是第三方独立的通用方案,对象序列化都要在编解码规则上适应不同的场景。对于 C++ 来说,标注库并无提供对其基本对象类型的序列化的方案,当基于 C++ 的系统与其他平台数据通信时,我们需要自己实现一个适合自己场景的序列化方案(造轮子)。无论是编码成 JSON/XML 一类的文本,还是直接二进制序列,C++ 对于内存数据的操作相比于其他语言的细节更多、对象设计范式更多,正如 C++ 的设计那样,努力使程序员掌握每一个字节。

本文先介绍了对象序列化的介绍和通用方案,再针对 C++ 语言的二进制序列形式序列化设计提出了一种实现方案。

对象序列化与编码

当然本文的主题是 C++ 编解码的方法思路,但还是先介绍一些数据序列化的背景。如果已经了解的读者可以跳过此节。

数据编码模式

无论是数据密集型的应用(如 web)还是计算密集的场景(各类计算引擎)都涉及到将外部数据加载入内存使用这一过程。较小的应用一般采用语言自身的文件 IO 的接口即可满足需求。而大型的系统需要考虑如下两个复杂的过程:

  • 接受数据流(加载)-> 解码 -> 内存
  • 内存 -> 编码 -> 发送(存储)数据流

对数据的编解码的过程是基于程序的两种不同数据表示形式:

  • 在内存中,数据保存为对象、结构体、列表、哈希表等结构,这些结构各语言实现了 cpu 对其访问的优化。
  • 字节序列,用于存储或通过网络发送,由内存中的对象编码而来。

以上两种形式的转换就是标题中的名词序列化与反序列化的概念:

从内存中的表示到字节序列的转换成为编码(序列化 serialize), 相反的过称为解码(反序列化)。

我们先来谈编码格式,也就是字节序列的具体表现形式。这里有人可能疑惑,计算机世界里数据的表示不都是为字节吗?为何还有不同的字节序列模式?这一点也许是大家刚学编程都有的疑惑,从 C 语言的二进制文件函数和文本函数开始疑惑:

#include <stdio.h>
FILE* fp_byte = fopen("filename", "rb"); //读取二进制,需要具体的内存类型接受(反序列化)
FILE* fp_text = fopen("filename", "r");  //读取文本,已经经过的某种编码,常表现为字符串

为了程序能认识各种字节序列,有效地辨别各种对象类型,需要字节编码为一定的格式。主要的编码形式有如下几种情况:

语言内置编码

  • 语言特定的格式:各种编程语言内置支持的字节序列: Java 的 java.io.Serializable, python 的 pickle(数据科学领域的朋友一定也对 Tensorflow/pytorch 序列化的各类 model 不陌生), Ruby 的 Marshal
  • 各类第三方通用库:如跨语言使用的 Protobuf (Google)\MessagePack (Facebook)\Thrift (Apache) 等。

上述两种都与语言自身的支持分不开,然而各种语言支持的对象类别有不同,这就比较考验这些模式的泛化能力,越复杂的编解码模式也牺牲了效率。因此语言内置的序列化方法通常不被用在大型系统中。下面这种模式是大家最熟悉也是最流行的:

JSON, XML 文本格式

这类文本类形式优点很多,可读性强,各个语言都认识,很多都提供了内置的编解码模块如 Python 的json.loadsjson.dumps, Golang 的json.Marshal/json.Unmarshal。C++ 没内置不要紧,因其高度结构化的格式,解析起来也很简单。这样的特性使得 Json 和 XML 成为了 Web 领域数据交换格式的主流选择,非常适合不同语言间的通信。我们数据的通信方法如 Restful, RPC 等都用 JSON 做基本支持。

当然文本格式的缺点也是显而易见的,最明显的是:

  • 文本不能很好的区别数字与数字字符串,解析时可能会丢失精度。
  • 文本不能很好的表示二进制字符串,对 unicode 支持良好。对于二进制还需要使用 Base64 再次进行编解码。
  • 空间占用要大一些

但上述缺点不妨碍 JSON 在 Web 领域大放异彩,因 Web 的应用通信多,且多为数据密集型场景,可读性和简易性成为第一选择要素。然而如果数据流是内部使用,且比较在意空间占用和存取效率呢?

二进制序列

二进制的编码方式直接理解,就是讲内存中的数据(不含字段名)更紧凑地编码在一起,解码时使用约定好的规则解码。这一特点正是各静态语言的特性,预先确定好的数据类型和空间占用。我们看一个例子,来自 RPC 框架Thrift对于二进制编码的解决方案。他规定数据的编解码两方都使用如下的数据结构:

struct Person {
    1: required string       username,
    2: optional i64          Number,
    3: optional list<string> interests
}

可读性与 json 一样良好,特别的是每个字段加上了 id, 这样不需要再将字段名编码,只将数据和 id 紧凑地编码,至于解码时字段的动态性,则根据定义好的 id 判断。关于 Thrift 的二进制具体编解码规则可以见参考[2].

编码的其他问题

当然上述讨论了多种编码格式,没哪种方案是最好的。当然选择编码模式还有一个重要问题必须考虑:兼容性。一个经常遇见的场景就是数据结构变化了(添加新字段,改动字段),编解码的程序是否要重新修改。为了使系统顺利运行,理想的状态是保持双向的兼容:

  • 向后兼容:新代码可以读旧数据
  • 向前兼容:新数据也可以由旧代码读取

离线加载 or 动态加载?

一般你的系统在运行中对数据的需求可以采用离线的加载和实时的加载两种模式。例如需要获取某个城市的人口数据,你可以采用两种办法:

  • 在线请求,找到数据源,可能来自 rest 或 rpc, 发生 io。
  • 离线加载,直接从内存或数据库读之前离线已经加载好的数据,通常要设置定时更新。

对于比较在意响应速度的场景,如搜索引擎,地图导航引擎等都倾向采用离线的模式,尽量地避免实时的数据 IO。对于 C++ 应用,离线编译就需要将来源数据的格式(可能是 json/xml 也可能来自数据库等)序列化为 C++ 能快速解码和读取的形式,二进制序列是效率最高,存储最紧凑的形式。下面的章节就将介绍一种 C++ 的轮子设计,用于高效序列化 C++ 内置对象。

C++ 对象序列化类设计

本节主要讲述两个 C++ 的一种二进制序列化的实现设计,主要有以下特点:

  • 使用标准库接口,仅支持 C++ 基本对象类型,数组、结构体、类;STL 容器暂不考虑支持
  • 采用二进制序列紧凑存储
  • 数据源默认为 json 文本格式,同时可扩展其他来源

不同于动态语言,C++ 的内置类型的大小都是静态固定的,于是很多可能动态增长的类型如数组、不定长的字符串等,这些类型在 C++ 序列化时就需要经过一些设计。

从对象的成员类型分析

Json 格式几乎支持了所有能用的类型,本文采用看如下的数据结构 Person 类型为例:

//person.json
data json type:
{
    id: int64, // 8 字节
    name: string, // 不定长,最大长度16
    friends: int64[] // 8 * N 字节,N最大6
}

本文采用了一个模拟的数据生成逻辑 mock.py 生成了 1000 个这样的数据,纯 json 文本的大小大约为 200k-350k 之间(因为成员的大小是随机生成的,故每次文件大小不一)。在此之前我们先采用 python 内置的pickle编解码测试下:

import pickle
 # test pickle in python
start_dumps_time = time.time()
with open(DATA_PATH + '/person.pkl', 'wb') as fp:
    pickle.dump(persons, fp)
end_dumps_time = time.time()
print("Pickling time: %d " % (end_dumps_time - start_dumps_time))

    # test pickle load in python
start_loads_time = time.time()
with open(DATA_PATH + '/person.pkl', 'rb') as fp:
    pickle.load(fp)
end_loads_time = time.time()
print("Pickling loading time: %d " % (end_loads_time - start_loads_time))

看见 pickle 对文件操作使用的是wbrb了吗?这预示着 pickle 模块也是采用一定格式的二进制文件。看下文件大小:

$ du -h person.pkl 
72K    person.pkl

编解码速度在这里先不考虑,我们稍后会将空间占用与 C++ 的二进制序列做对比。数据源确定后,对每种语言的序列化一样,我们要考虑适配的数据结构,python 和 javascript 内置的字典和对象类型已经直接适配了 json 的结构,且动态扩容,对于这两种语言来说不需要再额外设计结构。对于 C++,我们需要仿照设计一个结构体或类。而成员类型的选择则需要根据 C++ 实际选择。我们试着根据 person 的结构写出一个 C++ 结构体:

#include <vector>
using std::vector;
struct s_Person_Info
{
    uint64_t nPersonID;
    string PersonName;
    vector<uint64_t> vPersonFriends;
};

这似乎完美地适配了 person 类型的结构,虽然PersonNamevPersonFriends的长度不定,我们仍然可以将一个s_Person_Info尝试序列化:

struct s_Person_Test
{
    uint64_t nPersonID;
    string PersonName;
    vector<uint64_t> vPersonFriends;
};

s_Person_Test st {12100, "test", {13100, 12300} };
FILE * fp = fopen("person_byte", "wb");
fwrite(&st, sizeof(s_Person_Test), 1, fp);
fclose(fp);

接口fwrite()以二进制写文件,会将内存中的二进制形式原封不动地写进二进制文件,清楚的是在内存中空间大小与文件大小保持一致。我们看下生成的二进制大小:

$ du -h person_byte 
4.0K    person_byt

为什么会这么大?这只能从 STL 容器对象本身的内存模型找原因了,但目前最主要的问题并非是占用空间大的问题,编解码过程必须都要满足,我们看下解码能顺利吗?

编解码同时考虑

我们尝试使用原生的读接口fread()解析刚生成的二进制:

FILE * fpr = fopen("person_byte", "rb");
s_Person_Test sr;
fread(&sr, sizeof(s_Person_Test), 1, fpr);

fread()做的事也很直接,将文件中的二进制序列原封不动地搬到&sr地址后的内存,开辟大小为s_Person_Info的长度。这一步不会出问题,但程序在析构sr时会报出错误:

main(48697,0x7fffb7f41380) malloc: *** error for object 0x7fc1315572c0: pointer being freed was not allocated

熟悉vector的读者知道 STL 容器会将数据动态分配在堆上,且会有各种类型的指针指向,这种直接的解码方法当然不能给vector对象的全部成员准确地赋值,析构时就会出现未定义行为。

我们考虑将结构体设置为 C++ 的基本类型,需要提前确定长度:

// For bytes 
struct s_Person
{
    uint64_t person_id;
    char     person_name[10];
    uint64_t person_friends[6];
    s_Person()
    {
        memset(this, 0, sizeof(s_Person));
    }
};

换成基本类型后,编解码都不会出现问题,但缺陷仍然有很多。最主要的是:

  • stuct 内的成员没有内存对齐,造成空间浪费和 CPU 缓存的伪共享问题
  • 重复数据太多,person_friends 存储了大量重复的 id, 浪费空间

我们先来看内存对齐的问题。

请注意 struct 的内存对齐

C++ 的内存对齐最直接的原因是 CPU 取内存总线长度为固定 8 字节(不同的架构不同),这造成第一个问题是空间浪费:

struct s_Person
{
    uint64_t person_id;  // 8 bytes
    char     person_name[10]; // 10 * 1 = 10 bytes
    uint64_t person_friends[5]; // 5 * 8 = 40 bytes
};

理想的紧凑占用就是各成员大小的加和,是 58B, 然而实际上sizeof(s_Person)的大小为 64B. 问题出在第二个成员,10 个char实际占用是两个 8B。为何要内存对齐及如何尽量做到对齐的方法可以参看问题[3] 中的回答。此外结构体如果涉及到多核读写操作,CPU 的缓存一致性的效率也跟内存是否对齐息息相关,知晓 CPU 三级缓存是如何工作的,以及结构体的内存排布可以帮助我们写出最大性能的代码。[4]

使用索引避免重复

内存对齐后结构体仍然还有空间浪费的问题,char[10]的类型每个实例不可能都占满,大家的名字一般有长有短。其次uint64_t person_friends[5]存储的都是每个实例唯一的主键 id,针对这两个类型,我们再想出尽量节省内存的方法:

  • 字符串类型,全体紧凑存储,额外为每个名字添加索引用于寻址。
  • 为每个 id 也建立长度更短的索引,尽可能节省数组保存成员的长度。由 uint64 缩短为 uint32.

这种思路引入了索引机制,尤其在数据量很大的情况,引入索引不但能节省空间,而且能提升查询效率。索引的构建方式有很多种,这里我们不采用复杂的哈希函数,使用简单的顺序序号构建哈希表。使用索引后的结构体为:

struct s_Person
{
    uint32_t person_name_index;
    uint32_t person_id_index;
    uint32_t person_friends[FRIENDS_SIZE];
};

存储策略采用下图的形式:

我们需要额外维护两个哈希表用于对原始数据的寻址,这种方式适合大数据量的情况,可以让哈希表的空间消耗远小于字节序列的空间占用。接下来的问题就是两个哈希表如何维护,内存如何布局,若要存储,又该如何存储,这一切的前提都是不能借用 STL 的哈希表实现。同时整个编解码、取数据的接口设计也需要考虑内存使用,读写速度等,这些更为工程化的设计将在 C++ 序列化对象(二)介绍。下一节又将引出关于文件 IO 的更多轮子,如何有效地减少磁盘访问、减少文件 IO 过程中的拷贝[1]、巧妙地设计 buffer 与 cache,这对于 C++ 来说,都是要考虑的事情。(造的轮子)

总结

  • 序列化方案的选择很重要,需要在可读性、空间占用、传输效率、解码效率之间做权衡。二进制序列相比文本序列空间更省,解析速度更快。
  • C++ 的结构体对象序列化要考虑成员的类型,复杂对象类型不适合直接二进制的转换。
  • C++ 的结构体设计要充分考虑内存对齐布局,引入 CPU 读取数据和三级缓存机制的思考,写出尽可能高效的程序。
  • 对于序列化大量可变长对象(如字符串、数组),相比设置最大长度较为浪费空间的做法,紧凑存储同时辅之以索引寻址将会是更好的方案。

Reference