卡夫卡消息格式中的变长字段(Varints)

　　

卡夫卡从0.11.0版它本开始所使用的消息格式版本为v2,这个版本的消息相比于v0和v1的版本而言改动很大,同时还参考了协议缓冲区而引入了变长整型(Varints)和锯齿形编码。为了更加形象的说明问题,首先我们来了解一下变长整型。

　　

Varints是使用一个或多个字节来序列化整数的一种方法。数值越小,其所占用的字节数就越少.Varints中每个字节都有一个位于最高位的msb位(最高有效位),除了最后一个字节外其余msb位都设置为1,最后一个字节的msb位设置为0。这个msb位表示其后的字节是否和当前字节一起来表示同一个整数。除msb位之外,剩余的7位用于存储数据本身,这种表示类型又称之为基地128。通常而言,一个字节8位可以表示256个值,所以称之256年为基础,而这里只能用7位表示,2的7次方即为128. Varints中采用小端字节序,即最小的字节放在最前面。

　　

举个例子,比如数字1,它只占一个字节,所以msb位为0:

　　
　　

0000 0001 　　 　　

再举一个复杂点的例子,如数字300:

　　
　　

1010 1100 0000 0010 　　 　　

300的二进制表示原本为:0000 0001 0010 1100=256 + 32 + 8 + 4=300,那么为什么300的变长表示为上面的这种形式?

　　

首先我们先去掉每个字节的msb位,表示如下:

　　
　　


→1010 1100 0000 0010010年1100 000 0010

　　 　　

如前所述,varints是小端字节序的布局方式,所以这里两个字节的位置需要翻转一下:

　　
　　


→010 1100 000 0010000 0010 010 1100(翻转)
→0010 + 000 + 010 1100
→0000 0001 0010 1100=256 + 32 + 8 + 4=300

　　 　　

Varints可以用来表示int32, int64, uint32, uint64, sint32, sint64, bool,枚举等类型。在实际使用过程中,如果当前字段可以表示为负数,那么对于int32/int64和sint32/sint64而言,它们在进行编码时存在着较大的区别。比如你使用int64表示一个负数,那么哪怕是1,其编码后的长度始终为10个字节(可以通过下面的代码来测试长度),就如同对待一个很大的无符号长整型一样。为了使得编码更加的高效,Varints使用了锯齿形的编码方式。

　　
 <代码>公共int sizeOfLong (int v) {
　　int字节=1;
　　而(v,0 xffffffffffffff80l) !=0 l) {
　　字节+=1;
　　v祝辞祝辞祝辞=7;
　　}
　　返回字节;
　　}
　　

曲折编码以一种锯齿形(锯齿线)的方式来回穿梭于正负整数之间,以使得带符号整数映射为无符号整数,这样可以使得绝对值较小的负数仍然享有较小的Varints编码值,比如1编码为1,1编码为2、2编码为3,参考下表:

　　

卡夫卡消息格式中的变长字段(Varints)

　　

对应的公式为:

　　
　　

(n & lt; & lt;1)^ (n祝辞祝辞31)

　　 　　

这是对于sint32而言的,sint64对应的公式为:

　　
　　

(n & lt; & lt;1)^ (n祝辞祝辞63)

　　 　　

以1为例,其二进制表现形式为:1111 1111 1111 1111 1111 1111 1111 1111(补码)。

　　
　　

(n & lt; & lt;1)=1111 1111 1111 1111 1111 1111 1111 1110
(n祝辞祝辞31)=0000 0000 0000 0000 0000 0000 0000 0001
(n & lt; & lt;1)^ (n祝辞祝辞31日)=1

　　 　　

最终1的Varints编码为0000 0001,这样原本用4字节表示现的1在可以用1个字节来表示了。对于1而言就显得非常简单了,其二进制表现形式为:0000 0000 0000 0000 0000 0000 0000 0001。

　　
　　

(n & lt; & lt;1)=0000 0000 0000 0000 0000 0000 0000 0010
(n祝辞祝辞31)=0000 0000 0000 0000 0000 0000 0000 0000
(n & lt; & lt;1)^ (n祝辞祝辞31)=2
最终1的Varints编码为0000 0010,也只占用一个字节。

　　 　　

前面说过Varints中的一个字节中只有7位是有效数值位,即只能表示128个数值,转变成绝对值之后其实质上只能表示64个数值。比如对于消息体长度而言,其值肯定是个大于等于0的正整数,那么一个字节长度的Varints最大只能表示63(从0开始计)。对于64年而言,其二进制表示为:

　　
　　

0100 0000 　　 　　

经过曲折处理后为:

　　
　　

1000 0000 0000 0000=1000 0000 ^

　　 　　

每个字节的低7位是有效数值位,所以1000 0000进一步转变为:

　　
　　

000 0001 000 0000 　　 　　

而Varints又是小端字节序,所以需要翻转一下位置:

卡夫卡消息格式中的变长字段(Varints)