varint是啥你真的知道么？

shysh95

发布于 2020-07-28 07:25:02

1.6K00

代码可运行

文章被收录于专栏：shysh95shysh95

运行总次数：0

代码可运行

作为熟悉Kafka的读者，肯定知道Kafka的消息中的很多长度字段均采用了可变长度的编码格式，那么这种可变的编码格式是什么呢，没错，就是我们今天要讲的varint编码格式。下面我们会有两个知识点需要讲解：

字节序
varint编码

字节序

计算机在信息传输的过程中都是采用一定的编码格式将数据编码为二进制，当数据接收方收到数据以后也会进行相应的解码将二进制数据转换成响应的格式。在计算机中，一个二进制数字（0或1）代表1Bit，8个Bit又称为1个字节(byte)。

字节序指的就是多个字节在通信中的排列顺序，字节序目前有两种格式：

大端序：整数的最高字节在存储时在最低字节的前面则称为大端序，通俗一点说就是按照数字的书写顺序进行二进制的转换
小端序：整数的最低字节在存储时在最高字节的前面则称为小端序，通俗一点说就是按照数字书写的颠倒顺序进行二进制的转换

下图就是数字123456的断续和小端序的二进制格式：

首先int类型的数据占据4个字节，以大端序为例我们可以看到123456的高位的第一个字节都是无用的，我们可以使用三个字节就能代表123456，由于Kafka的长度字段的数值都会远远小于123456，甚至1个字节也可以表示，如果我们依旧使用int来表示长度的话将会浪费大量的空间，因此基于这个原因，Kafka在自己的v2消息格式中的长度字段具采用了可变长度的表示，这种表示方式就是通过varint编码。

varint

varint其实并不仅仅在kafka中有所使用，大名鼎鼎的Protocol Buffers也使用varint编码。

varint是使用一个或多个字节序列化整数的方式，他可以把一个固定字节的整数编码成变长字节。

varint编码中每一个字节的最高位都不用来存储数字的真正表示，而是表示当前字节是否还属于当前数据，1代表是，0代表不是（也就是该字节是当前数据的最后一个字节数据）。每一个字节的低7位用于以7位为一组存储数字的二进制补码表示，最低有效数组在前，这也就表明varint编码是按照小端序来排列的。

图中对数字123456进行varint编码，123456用二进制表示为1 11100010 01000000，每次低从向高取7位再加上最高有效位变成11000000 11000100 00000111。

下面我们通过一段Java代码实现varint编码和解码，其中只实现了无符号Interger类型的数据。

public class VarInt {

    public static void writeUnsignedVarint(int value, DataOutput output) throws IOException {
        // value & 0xffffff80 当前字节是否为最后一个字节，不是则执行while
        while ((value & 0xffffff80) != 0) {
            // value & 0x7f保证可以取到整数最低7位
            // | 0x80 填充字节最高位为1，因为当前字节还不是数据的最后一个字节
            byte b = (byte) ((value & 0x7f) | 0x80);
            output.writeByte(b);
            System.out.println(b);
            value >>>= 7 ;
        }
        // 写入最后一个字节
        System.out.println(value);
        output.writeByte(value);
    }

    public static int readUnsignedVarint(ByteBuffer buffer) {
        int value = 0;
        int b;
        int i = 0;
        while (((b = buffer.get()) & 0x80) != 0) {
            value |= (b & 0x7f) << i;
            i += 7;
            if (i >= 28) {
                throw new IllegalArgumentException("illegal varint");
            }
        }
        value |= b << i;
        return value;
    }

    public static void main(String[] args) throws IOException {
        DataOutputStream output = new DataOutputStream(new ByteArrayOutputStream(2));
        writeUnsignedVarint(123456, output);
        System.out.println("encode size:" + output.size());
        System.out.println("-----------");
        byte[] bytes = new byte[]{-64, -60, 7};
        ByteBuffer wrap = ByteBuffer.wrap(bytes);
        System.out.println("decode:" + readUnsignedVarint(wrap));
        System.out.println("-----------");
    }
}