Protobuf 源码解读之编解码

我们都知道 RPC 框架之所以相较 Rest API 高效，原因之一是 RPC 框架使用了高效的编码方案。对比 Rest API 的 JSON/XML 明文传输，使用二进制协议对编码后的信息进行交换要高效很多。例如 Protobuf 之于 gRPC，Avro 之于 Kafka。本文会介绍 protobuf/avro 中如何对 int 类型进行编解码。为什么是 int 类型呢？因为这是编码其它类型的基础，同时也是整个序列化/反序列化中最有意思的部分！

缘起

由于工作需要，近期需要手撸一套高可用低功耗的 RPC 协议。考虑到 Protobuf 和 gRPC 的普及以及 Google 的背书，决定采用 Protobuf 协议。于是阅读了 Protobuf 的编码标准以及各种语言的实现。编码规则主要采用 variable-length 方式(除去一部固定长度类型比如 float)，实现起来比较直观。

在对整数进行编码的时候，采用的是 ZigZag 编码方式。由于太久不做算法题，导致花了整整一个番茄钟周期才证明了其位运算的算法（这里感叹：吃饭的家伙不能丢哇😂）。

由于需要保证高性能和低功耗，还需要考虑编译器和多平台的优化，在此也一并记录。

预备

本文几乎不需要什么预备知识。唯一需要了解的只有计算机 101——如何表示整数：

• 反码(1's complement)：对于单个数值（二进制的 0 和 1）而言，对其进行取反操作就是将 0 变为 1，1 变为 0。也就是说，若 X=1，则反码为 0；若 X=0，则反码为 1。

• 补码(2's complement): 是一种用二进制表示有符号数的方法，也是一种将数字的正负号变号的方式，常在计算机科学中使用。补码以有符号比特的二进制数定义。正数和 0 的补码就是该数字本身。负数的补码则是将其对应正数按位取反再加 1。

进入主题

编码

下面就让我们看看 gRPC 中如何对 Int64 进行编码的。我们的目标是编解码部分，所以我们先忽略安全检查和 unsafe 的部分逻辑，直接看编码逻辑。代码如下：

    @Override    public final void writeUInt64NoTag(long value) throws IOException			...			while (true) {        if ((value & ~0x7FL) == 0) {          buffer[position++] = (byte) value;          return;        } else {          buffer[position++] = (byte) (((int) value & 0x7F) | 0x80);          value >>>= 7;        }      }

其中value是待编码的长整型数字，buffer是编码后的目标值，position是当前编码到的位置。代码很短，主要都是位运算。乍一看有点懵，0x7FL和0x80都是什么东西？为什么要>>>=7?在解答这个问题之前，我们需要了解 RPC 中 Int 的编码方式——VarInt 和 ZigZag 编码。

VARINT

VARINT 是远程传输中对整型进行序列化和反序列化的常用手段，整型数字会被表示为一个或多个字节。越小的数字编码后的字节越短。

在 VARINT 中，除了最后一个字节之外的每一个字节都设置了最高有效位（most significant bit - msb），用来表示该字节还有后继，还需要继续读取后面的字节。每个字节的最低 7 位存储 7 位数字的真实值，最高位存储 msb。例如：

Number Bytes

1 0000 0001

2 0000 0010

... ...

127 0111 1111

128 1000 0000 0000 0001

... ...

300 1010 1100 0000 0010

可以看到，目标值小于 127 的时候，最高位（msb）为 0，后面按照正常二进制数字显示。当目标值大于 127 时，截取最低 7 位放入第一个字节，同时将高位（msb）标为 1，然后将截取后的目标值按照上述规则放入第二个字节，依此类推。

例如：

VarInt(1000 0000 0000 0001) = 000 0001(后7位) ++ 000 0000（前七位）													  = 1 << 7 + 0													  = 1000 0000													  = 128VarInt(1010 1100 0000 0010) = 000 0010 ++ 010 1100														= 10 << 7 + 10 1100														= 256 + 44														= 300

可以看到，使用 VarInt 编码，越小的数字占用的字节越短，同时不需要额外的数据结构存储 offset，所有信息都存储在目标缓冲区本身。这样存储可以有效的减少编码所需的字节数，达到压缩的效果；同时这种数据结构本身带有元数据信息，不需要额外的数据结构来表示长度或者 offset 信息。

然而这里还有一个问题——负数怎么表示。我们都知道，负数在计算机中采用补码的形式保存。这样一来，负数的高位为符号位，而且负数的绝对值越小，反而占用的字节越大。为了解决这一问题，我们需要有一个压缩编码算法，对负数也可以采用 VarInt 的表达方式。

ZigZag

ZigZag 编码是使用无符号整数来表示有符号整数的一种编码方式，protobuf 和 avro 都使用这种编码方式对整数进行编码。在上面章节，我们希望有一种编码方式可以连续、自洽的对整数进行编码，同时越小的整数最好占用越少的字节。ZigZag 编码可以帮我们达到这个目标。

ZigZag 顾名思义，通过"zig-zag"的方式交替的将正数和负数编码为无符号整数，具体规则为——-1 -> 1，1 -> 2，-2 -> 3，3 -> 4依次类推，具体如下表：

Signed Original Encoded As

0 0

-1 1

1 2

-2 3

2 4

2147483647 4294967294

-2147483648 4294967295

由上面的定义可以推导出 64 位整型编码的公式为

(n << 1) ^ (n >> 63)

具体推导的过程就不再赘述，这里给出一个直观上的解释。由上表可以看到，对于正整数，编码后的结果为原来数字的 2 倍；对于负数，编码后的结果为原来数字的 2 倍的绝对值减一；对于 0 编码前后一致：

我们再来看编码公式：

n << 1

把 n 左移 1 位，即对 n 进行 2 倍的操作。

n >> 63

将 64 位整数右移 63 位。对于正整数来说，由于符号为为 0，该操作的结果为0x 0000 0000;对于负整数，该操作的结果为0x ffff ffff。

(n << 1) ^ (n >> 63)

最后将上述的两个结果进行异或操作。

由于与 0 的异或结果等于本身，所以对于 0 和正整数来说，上述操作的结果就是对原值进行乘 2 操作（0 不变）。

对于负整数来说，将负数翻倍后的结果再与 1 异或，相当于对结果进行取反——1 变 0，0 变 1。由于计算机中补码为原数字的反码加 1，那么反过来，反码则为补码减 1。所以其结果正好为|2x|-1。

由此，证明完毕。

编码解释

    @Override    public final void writeUInt64NoTag(long value) throws IOException			...			while (true) {        if ((value & ~0x7FL) == 0) {          buffer[position++] = (byte) value;          return;        } else {          buffer[position++] = (byte) (((int) value & 0x7F) | 0x80);          value >>>= 7;        }      }

下面让我们再回过头来看看编码的代码就比较清晰了：

if ((value & ~0x7FL) == 0) {

这一行用来判断当前 value 是不是比 127（低 7 位数字）小，如果是则将当前 value 转化为字节，然后编码过程就完成了。

buffer[position++] = (byte) (((int) value & 0x7F) | 0x80);value >>>= 7;

否则将当前的 value 的低 7 位转化为字节（value & 0x7F），然后将高位（msb）置为 1(| 0x80)。同时将 value 右移 7 位，继续进行上述过程。

最后将 ZigZag 编码过程和 VarInt 编码过程结合，整个整型数字的编码过程就完成了。

解码

有了上述的编码过程介绍，解码过程就相对容易理解多了。我们还是将解码部分拆成两部分来看。

ZigZag 解码

废话不多说，直接上代码：

(n >> 1) ^ -(n & 1)

公式如下

n >> 1

将 n 右移 1 位，即 n 除以 2。

-(n & 1)

该操作会得到最后一位数字的相反数。对于原始值是 0 或者正数的整数，编码后的结果都为偶数，所以该操作的结果为 0；对于原始值是负数的整数，编码后的结果都为奇数，所以上述操作的结果为0x ffff ffff。

(n >> 1) ^ -(n & 1)

对上述结果进行异或操作。对于 0 和偶数来说，与除以 2 的结果相同；对于奇数来说，对其除以 2 之后取反。由于反码和补码的关系，其结果相当于对原结果减一，因此与上述公式一样。在此 ZigZag 解码过程证明完毕。

VarInt 解码

代码如下：

public long ReadLong()        {            byte b = read();            ulong n = b & 0x7FUL;            int shift = 7;            while ((b & 0x80) != 0)            {                b = read();                n |= (b & 0x7FUL) << shift;                shift += 7;            }            long value = (long)n;            return (-(value & 0x01L)) ^ ((value >> 1) & 0x7fffffffffffffffL);        }

我们来简单梳理一下解码过程。

while ((b & 0x80) != 0)

判断最高位是否为 1，是的话则继续，否则则退出循环。

n |= (b & 0x7FUL) << shift;shift += 7;

读取当前字节的低 7 位并转化为整数，然后向左移动shift位。其中 shift 为 7 的倍数，表示当前解码过程的 offset。

return (-(value & 0x01L)) ^ ((value >> 1) & 0x7fffffffffffffffL);

将结果进行 ZigZag 解码并返回。

至此，编解码过程全部结束。完结，撒花🎉!

优化

优化目标

由于我们的编解码库需要在不同平台的不同系统的智能设备上运行，所以只能再回来继续进行性能优化了（苦哇。。。）。这里我们主要针对编码部分进行优化。原因嘛？因为解码是在服务器端啊（逃。。。）。

我们都知道，CPU 会进行分支预测和预加载。由于 VarInt 本身已经针对字节进行编码，因此我们主要针对 CPU 分支预测部分进行优化。

如何增强 CPU 分支预测的准确性呢？方法有很多，在这里我们采取最简单的一种——减少逻辑判断分支。

优化逻辑

让我们再次回顾 VarInt 编码代码:

    @Override    public final void writeUInt64NoTag(long value) throws IOException			...			while (true) {        if ((value & ~0x7FL) == 0) {          buffer[position++] = (byte) value;          return;        } else {          buffer[position++] = (byte) (((int) value & 0x7F) | 0x80);          value >>>= 7;        }      }

我们需要判断待编码数字与0x7F的大小来判断还需不需要进行位移操作。这里的逻辑判断能不能省去呢？

我们再来梳理一下我们这里的逻辑——我们需要将目标整数每隔 7 位进行一次编码。那么如果我们知道目标数字的二进制表示实际有多少位，再除以 7，就可以得到我们需要进行多少次位移操作，而不必进行判断。所以答案是肯定的——我们可以省去逻辑判断的部分！

例如：15 的二进制表示位0x 0000 1111，其中左边有 32 位是 0，那么实际上整数 15 的有效位数为63 - 32 = 31。所以转码 VarInt 需要位移的次数为31 / 7 = 4。由此可见，我们只要减去从高位开始连续 0 的个数，就可以得到我们需要位移的次数，从而省略条件判断。幸运的是，Java/Go/Rust 都有leadingZero相关函数，所以实现起来也比较简单。代码如下：

int varIntLen(long value) {		return (63 - Long.numberOfLeadingZeros(value)) / 7;}

至此，我们成功将分支条件去掉。然而，我们引入了除法。这对编译器可是相当不友好。让我们把除法操作转化为静态变量访问从而对执行进行优化。

private static final int[] VAR_INT_LENGTHS = new int[65];
static {		for (int i = 0; i <= 64; ++i) {		VAR_INT_LENGTHS[i] = (63 - i) / 7;}}
int varIntLen(long value) {		return VAR_INT_LENGTHS[Long.numberOfLeadingZeros(value)];}

从而编码的逻辑变为：

private void writeVarInt(int offset, long value) {		int length = varIntLength(value);    for (int i = 0; i < length; ++i) {    		buffer[offset + i] = ((byte) ((value & 0x7F) | 0x80));   			value >>>= 7;    }    buffer[offset + i] = (byte) value;}

至此，我们完成了对编码逻辑的优化。然而我们引入了新的函数Long.numberOfLeadingZeros，这个函数会不会成为拖垮性能的最后一根稻草呢？不必担心！依托于现代处理器的强大，处理器直接有指令可以得到LeadingZeros的结果：x86_64 下有lzcnt，而 Arm 和 Risc-V 下面有clz。通过一个指令就可以得到我们想要的结果，完美！

优化验证

上面的多环境平台优化都是作者脑补的，真正在机器上执行的时候，编译器会不会智能的将Long.numberOfLeadingZeros转化为对应平台的优化指令呢？还是会光速打脸（捂脸。。。）。就让我们来验证一下吧！

（此处省略编译的过程。。。）

结果是——果然光速打脸了——一半。。。

让我们先看看成功的案例。在 Arm64 平台上得到的结果为：

        text    "".LzCount(SB), LEAF|NOFRAME|ABIInternal, $0-16        funcdata        ZR, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        funcdata        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        movd    "".x(FP), R0        clz     R0, R0        movd    R0, "".~r1+8(FP)        ret     (R30)        text    "".main(SB), LEAF|NOFRAME|ABIInternal, $0-0        funcdata        ZR, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        funcdata        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        ret     (R30)

可以看到在 Arm 平台上，编译器成功优化为clz R0, R0，结果正如我们预期。

下面让我们看看 x86_64 下面的结果：

        text    "".LzCount(SB), NOSPLIT|ABIInternal, $0-16        funcdata        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        funcdata        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        movq    "".x+8(SP), AX        bsrq    AX, AX        nop        movq    $-1, CX        cmovqeq CX, AX        addq    $-63, AX        negq    AX        movq    AX, "".~r1+16(SP)        ret        text    "".main(SB), NOSPLIT|ABIInternal, $0-0        funcdata        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        funcdata        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)        ret

我们并没有找到lzcnt，看来在 intel 的处理器下优化失败了？等等，我们注意到bsrq AX, AX，这一行有什么用呢？为什么这一行之后的代码跟我们之前预测的逻辑相同——addq $-63, AX?

原来bsrq指令是从高位开始寻找第一个不是 0 的索引。这不正是我们想要的么？在 x86 下编译器更进一步直接帮我们找到了第一个非 0 的索引。殊途同归！给 gcc 强大的编译能力点赞！

至此，编译结果与我们的希望相符，我们去掉了逻辑分支，消除了除法对性能的影响，同时编译器在不同平台帮助我们使用原生的机器指令进行了优化。我们的 protobuf 编解码之旅至此告一段落。

小结

本文介绍了 protobuf 和 avro 如何对 Int 进行编解码，过程中我们了解了 VarInt 和 ZigZag 编码方式。最后我们针对现代 CPU 的特点和操作系统的指令集，对编码逻辑进行了优化，使之更适合跨平台的智能设备。

后记

结束不是永远。

在写完代码后进行测试，发现虽然性能相较于原生的 protobuf 代码有一些提升，然而序列化和反序列化依然是瓶颈。考虑到未来的网络基础设施可能会上 IB，这种 CPU 密集型的操作还是如鲠在喉，会对传输效率产生很大影响。

因此最后作者决定，还是不用上述的代码进行序列化和反序列化。那么问题来了——该如何进行 RPC 交互呢？答案是—— 零拷贝（zero copy）传输协议。

这种协议统一了内存中和远程交互的编码格式，不需要进行序列化，所以叫零拷贝传输。目前比较流行的有 Arrow Flight 和 FlatBuffers，前者是针对 OLAP 场景，主要使用列式存储格式，后者则针对 OLTP 使用场景，采用行式存储格式。在作者比较了二者的原理和效率之后会奉上这种零拷贝传输协议的文章，敬请期待！

如果觉得文章对您有帮助，欢迎关注留言和转发。