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
													  = 128
VarInt(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编码前后一致：

$$ \begin{equation} f(x)=\left{ \begin{array}{rcl} 0 & & {x = 0}\\ 2x & & {x > 0}\\ |2x|-1 & & {x < 0}\\ \end{array} \right. \end{equation} $$

我们再来看编码公式：

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)

公式如下

$$ \begin{equation} f^{\prime}(x)=\left{ \begin{array}{rcl} 0 & & {x = 0}\\ x/2 & & {x > 0}\\ -x/2 - 1 & & {x < 0}\\ \end{array} \right. \end{equation} $$

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使用场景，采用行式存储格式。在作者比较了二者的原理和效率之后会奉上这种零拷贝传输协议的文章，敬请期待！