云风的 BLOG: sproto 的实现与评测

这个周末，我实现了上周设计的简化版 protocol buffers 协议，并重新命名为 sproto 。

在实现过程中，发现了许多编码格式上可以优化的地方，所以一边实现一边做调整，使结构更适合编码和解码，并且更紧凑。

做了如下改动：

由于这个东西主要 binding 到 lua 这样的动态语言中使用，所以我不需要按 Cap'n Proto 那样，直接访问编码后的数据结构（直接把数据结构映射为 C/C++ 对象），所以数据对齐是不必要的。

编码时的 tag 如果要求严格升序也可以更快的处理数据，减少实现的复杂度。数据段也要求按持续排列，且不准复用。这样可以让数据中有更多的 0 方便压缩。

把 boolean 数组按位打包的意义也不太大（会增加实现的复杂度）。

暂时先不实现 64bit id 的类型。（以后再加）

最终的 Wire Protocol 是这样的：

所有的数字编码都是以小端方式(little-endian) 编码。

打包的单位是一个结构体（用户定义的类型）每个包分两个部分：1. 字段 2. 数据块

首先是一个 word n，描述字段的个数，接下来有 n 个 word 描述字段的内容。这个结构体的前半部分的长度就是 (n+1) * 2 字节。

字段的 tag 从 0 开始累加，每处理一个字段，将 tag 加一。

如果一个字段 v 为奇数，则把当前 tag 加上 (v-1)/2 + 1 ，并继续处理下一个字段值。如果一个字段为 0 ，表示这个字段引用后面的一个数据块。如果一个字段不为 0(且为偶数），这个字段的值为 v/2 - 1。（可以表示 [0, 32767] 的值）

接下来是被上面字段引用的数据块。

数据块用于描述字段中的大数据。它是由一个 dword 长度 + 字节串构成。通常用来表示数组或结构。大于 32767 的整数和负整数用 4 字节或 8 字节长的数据块表示(取决于需要和实现)。

数组的编码就是把同一类型的数据依次打包成数据块。如果是布尔数组，按 1 字节一个编码。如果是整数数组，它比较特殊，会根据需要打包成 4 字节或 8 字节一个数字；第一字节是 4 或 8 ，指明后面的整数宽度。

最后，数据中的 0 将被压缩的。压缩算法见上一篇 blog 。

我的实现分两部分：C 库，和 Lua 绑定。

C 库最主要的用途是用于其它语言的绑定，所以并没有提供类似 pbc 那样丰富的 api 。而仅仅提供了回调模式的 encode 和 decode 。

#define SPROTO_TINTEGER 0
#define SPROTO_TBOOLEAN 1
#define SPROTO_TSTRING 2
#define SPROTO_TSTRUCT 3

typedef int (*sproto_callback)(void *ud, const char *tagname, int type, 
  int index, struct sproto_type *, void *value, int length);

int sproto_decode(struct sproto_type *, const void * data, int size, sproto_callback cb, void *ud);
int sproto_encode(struct sproto_type *, void * buffer, int size, sproto_callback cb, void *ud);

encode 的时候，将回调用户传入的 callback 函数，通知现在要打包哪个字段（tagname），以及数据的类型。如果数据类型为 SPROTO_TSTRUCT ，表示这是一个结构，这个时候有另一个参数 sproto_type 指明结构类型。用户可以递归调用 encode 编码。

callback 函数给出了 buffer 地址和长度，如果 buffer 长度不够，应该返回 -1 ；如果正确的打包，返回使用掉的 buffer 的长度。

如果需要打包的是一个数组，index 大于 0 ，表示要把数据打包到 tagname 指向的数组的 index 索引处（base 1）；对于非数组的数据，index 等于 0。

encode 函数本身不会分配任何内容，当你的 buffer 给的不够大时，请适当加大，再调用一次。

decode 的过程和 encode 类似，只不过这个时候，buffer 指针指向的是解码器解开的数据。callback 函数只需要把数据复制到 tagname 指明的位置即可。

这个库尚未全部完工，但基本功能都已经全了。我把 sproto 和我自己实现的 pbc 的 lua binding 做了一个简单的性能测试：

首先我定义了这个一组协议。

.Person {
    name 0 : string
    id 1 : integer
    email 2 : string

    .PhoneNumber {
        number 0 : string
        type 1 : integer
    }

    phone 3 : *PhoneNumber
}

.AddressBook {
    person 0 : *Person
}

如果用 google protocol buffers 描述，大概长得是这样的：

message Person {
  required string name = 1;
  required int32 id = 2;        // Unique ID number for this person.
  optional string email = 3;

  message PhoneNumber {
    required string number = 1;
    optional int32 type = 2 ;
  }

  repeated PhoneNumber phone = 4;
}

message AddressBook {
  repeated Person person = 1;
}

完全一致，只是语法上略有区别而已。

我编写两段 lua 代码测试。处理以下数据：

local ab = {
    person = {
        {
            name = "Alice",
            id = 10000,
            phone = {
                { number = "123456789" , type = 1 },
                { number = "87654321" , type = 2 },
            }
        },
        {
            name = "Bob",
            id = 20000,
            phone = {
                { number = "01234567890" , type = 3 },
            }
        }
    }
}

编码很简单，对于解码，另外还加上了遍历所有的字段，这是因为 pbc 库对于二级以上的结构是惰性展开的（不访问就不解码），而 sproto 则是全部展开。