Kafka 消息格式中的變長(zhǎng)字段（Varints）

kafka從0.11.0版本開(kāi)始所使用的消息格式版本為v2，這個(gè)版本的消息相比于v0和v1的版本而言改動(dòng)很大，同時(shí)還參考了Protocol Buffer而引入了變長(zhǎng)整型（Varints）和ZigZag編碼。為了更加形象的說(shuō)明問(wèn)題，首先我們來(lái)了解一下變長(zhǎng)整型。

Varints是使用一個(gè)或多個(gè)字節(jié)來(lái)序列化整數(shù)的一種方法。數(shù)值越小，其所占用的字節(jié)數(shù)就越少。Varints中每個(gè)字節(jié)都有一個(gè)位于最高位的msb位（most significant bit），除了最后一個(gè)字節(jié)外其余msb位都設(shè)置為1，最后一個(gè)字節(jié)的msb位設(shè)置為0。這個(gè)msb位表示其后的字節(jié)是否和當(dāng)前字節(jié)一起來(lái)表示同一個(gè)整數(shù)。除msb位之外，剩余的7位用于存儲(chǔ)數(shù)據(jù)本身，這種表示類型又稱之為Base 128。通常而言，一個(gè)字節(jié)8位可以表示256個(gè)值，所以稱之為Base 256，而這里只能用7位表示，2的7次方即為128。Varints中采用小端字節(jié)序，即最小的字節(jié)放在最前面。

舉個(gè)例子，比如數(shù)字1，它只占一個(gè)字節(jié)，所以msb位為0：

0000 0001

再舉一個(gè)復(fù)雜點(diǎn)的例子，如數(shù)字300：

1010 1100 0000 0010

300的二進(jìn)制表示原本為：0000 0001 0010 1100 = 256+32+8+4=300，那么為什么300的變長(zhǎng)表示為上面的這種形式？

首先我們先去掉每個(gè)字節(jié)的msb位，表示如下：

1010 1100 0000 0010
-> 010 1100 000 0010

如前所述，varints是小端字節(jié)序的布局方式，所以這里兩個(gè)字節(jié)的位置需要翻轉(zhuǎn)一下：

010 1100 000 0010
-> 000 0010 010 1100 (翻轉(zhuǎn))
-> 000 0010 ++ 010 1100
-> 0000 0001 0010 1100 = 256+32+8+4=300

Varints可以用來(lái)表示int32、int64、uint32、uint64、sint32、sint64、bool、enum等類型。在實(shí)際使用過(guò)程中，如果當(dāng)前字段可以表示為負(fù)數(shù)，那么對(duì)于int32/int64和sint32/sint64而言，它們?cè)谶M(jìn)行編碼時(shí)存在著較大的區(qū)別。比如你使用int64表示一個(gè)負(fù)數(shù)，那么哪怕是-1，其編碼后的長(zhǎng)度始終為10個(gè)字節(jié)（可以通過(guò)下面的代碼來(lái)測(cè)試長(zhǎng)度），就如同對(duì)待一個(gè)很大的無(wú)符號(hào)長(zhǎng)整型一樣。為了使得編碼更加的高效，Varints使用了ZigZag的編碼方式。

public int sizeOfLong(int v) {
    int bytes = 1;
    while ((v & 0xffffffffffffff80L) != 0L) {
        bytes += 1;
        v >>>= 7;
    }
    return bytes;
}

ZigZag編碼以一種鋸齒形（zig-zags）的方式來(lái)回穿梭于正負(fù)整數(shù)之間，以使得帶符號(hào)整數(shù)映射為無(wú)符號(hào)整數(shù)，這樣可以使得絕對(duì)值較小的負(fù)數(shù)仍然享有較小的Varints編碼值，比如-1編碼為1,1編碼為2，-2編碼為3，參考下表：

對(duì)應(yīng)的公式為：

(n << 1) ^ (n >> 31)

這是對(duì)于sint32而言的，sint64對(duì)應(yīng)的公式為：

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

以-1為例，其二進(jìn)制表現(xiàn)形式為：1111 1111 1111 1111 1111 1111 1111 1111（補(bǔ)碼）。

(n << 1) = 1111 1111 1111 1111 1111 1111 1111 1110
(n >> 31) = 0000 0000 0000 0000 0000 0000 0000 0001
(n << 1) ^ (n >> 31) = 1

最終-1的Varints編碼為0000 0001，這樣原本用4字節(jié)表示的-1現(xiàn)在可以用1個(gè)字節(jié)來(lái)表示了。對(duì)于1而言就顯得非常簡(jiǎn)單了，其二進(jìn)制表現(xiàn)形式為：0000 0000 0000 0000 0000 0000 0000 0001。

(n << 1) = 0000 0000 0000 0000 0000 0000 0000 0010
(n >> 31) = 0000 0000 0000 0000 0000 0000 0000 0000
(n << 1) ^ (n >> 31) = 2
最終1的Varints編碼為0000 0010，也只占用一個(gè)字節(jié)。

前面說(shuō)過(guò)Varints中的一個(gè)字節(jié)中只有7位是有效數(shù)值位，即只能表示128個(gè)數(shù)值，轉(zhuǎn)變成絕對(duì)值之后其實(shí)質(zhì)上只能表示64個(gè)數(shù)值。比如對(duì)于消息體長(zhǎng)度而言，其值肯定是個(gè)大于等于0的正整數(shù)，那么一個(gè)字節(jié)長(zhǎng)度的Varints最大只能表示63（從0開(kāi)始計(jì)）。對(duì)于64而言，其二進(jìn)制表示為：

0100 0000

經(jīng)過(guò)ZigZag處理后為：

1000 0000 ^ 0000 0000 = 1000 0000

每個(gè)字節(jié)的低7位是有效數(shù)值位，所以1000 0000進(jìn)一步轉(zhuǎn)變?yōu)椋?/p>

000 0001 000 0000

而Varints又是小端字節(jié)序，所以需要翻轉(zhuǎn)一下位置：

000 0000 000 0001

設(shè)置非最后一個(gè)字節(jié)的msb位為1，最后一個(gè)字節(jié)的msb位為0，最終有：

1000 0000 0000 0001

所以最終64表示為：1000 0000 0000 0001，而63卻表示為：0111 1110。

具體的編碼實(shí)現(xiàn)如下(針對(duì)int32類型)：

public static void writeVarint(int value, ByteBuffer buffer) {
    int v = (value << 1) ^ (value >> 31);
    while ((v & 0xffffff80) != 0L) {
        byte b = (byte) ((v & 0x7f) | 0x80);
        buffer.put(b);
        v >>>= 7;
    }
    buffer.put((byte) v);
}

對(duì)應(yīng)的解碼實(shí)現(xiàn)如下（針對(duì)int32類型）：

public static int readVarint(ByteBuffer buffer) {
    int value = 0;
    int i = 0;
    int b;
    while (((b = buffer.get()) & 0x80) != 0) {
        value |= (b & 0x7f) << i;
        i += 7;
        if (i > 28)
            throw illegalVarintException(value);
    }
    value |= b << i;
    return (value >>> 1) ^ -(value & 1);
}

回顧一下kafka v0和v1版本的消息格式，如果消息本身沒(méi)有key，那么key length字段為-1，int類型的需要4個(gè)字節(jié)來(lái)保存，而如果采用Varints來(lái)編碼則只需要一個(gè)字節(jié)。根據(jù)Varints的規(guī)則可以推導(dǎo)出0-63之間的數(shù)字占1個(gè)字節(jié)，64-8191之間的數(shù)字占2個(gè)字節(jié)，8192-1048575之間的數(shù)字占3個(gè)字節(jié)。而kafka broker的配置message.max.bytes的默認(rèn)大小為1000012（Varints編碼占3個(gè)字節(jié)），如果消息格式中與長(zhǎng)度有關(guān)的字段采用Varints的編碼的話，絕大多數(shù)情況下都會(huì)節(jié)省空間，而v2版本的消息格式也正是這樣做的。

不過(guò)需要注意的是Varints并非一直會(huì)省空間，一個(gè)int32最長(zhǎng)會(huì)占用5個(gè)字節(jié)（大于默認(rèn)的4字節(jié)），一個(gè)int64最長(zhǎng)會(huì)占用10字節(jié)（大于默認(rèn)的8字節(jié)）。下面代碼展示如何計(jì)算一個(gè)int32占用的字節(jié)個(gè)數(shù)：

public static int sizeOfVarint(int value) {
    int v = (value << 1) ^ (value >> 31);
    int bytes = 1;
    while ((v & 0xffffff80) != 0L) {
        bytes += 1;
        v >>>= 7;
    }
    return bytes;
}

有關(guān)int32/int64的更多實(shí)現(xiàn)細(xì)節(jié)可以參考o(jì)rg.apache.kafka.common.utils.ByteUtils。

本文的重點(diǎn)是你有沒(méi)有收獲與成長(zhǎng)，其余的都不重要，希望讀者們能謹(jǐn)記這一點(diǎn)。同時(shí)我經(jīng)過(guò)多年的收藏目前也算收集到了一套完整的學(xué)習(xí)資料，包括但不限于：分布式架構(gòu)、高可擴(kuò)展、高性能、高并發(fā)、Jvm性能調(diào)優(yōu)、Spring，MyBatis，Nginx源碼分析，Redis，ActiveMQ、、Mycat、Netty、Kafka、Mysql、Zookeeper、Tomcat、Docker、Dubbo、Nginx等多個(gè)知識(shí)點(diǎn)高級(jí)進(jìn)階干貨，希望對(duì)想成為架構(gòu)師的朋友有一定的參考和幫助

需要更詳細(xì)架構(gòu)師技能思維導(dǎo)圖和以下資料的可以加一下技術(shù)交流分享群：“708 701 457”免費(fèi)獲取