5. protbuf中的Base 128 Varints（大端模式 & 小端模式）_protobuf 大小端

1. 絮絮叨叨

• 学习protobuf的Encoding部分时，就对其使用的数值编码格式产生的了浓厚的兴趣
• ORC中大量使用little endian：
  • ORC的每一个压缩块（chunk），通过3 bytes的header来标识其数据长度、是否压缩，header使用little endian（小端存储）
  • 在Run Length Encoding部分，有介绍Base 128 Varints，并指明该varint来自protobuf中
  • 不管是Base 128 Varints，还是对header的记录，都有提到 little endian
• 因此，一下子想起了自己学习计算机组成原理、汇编语言等基础课程时，经常使用到的大端存储（big endian，大端模式）、小端存储（小端模式）

2. big endian VS little endian

2.1 概念解释

• 以十进制数305419896为例，其对应的16进制表示为0x12345678

• 计算机中，输出存储的单位是byte（8 bit），可以存储2位16进制数

• 在大多数计算机资料中，存储地址以字节为单位进行编码，一般都是左边是低地址，右边是高地址
  

• 按照人类的阅读习惯，左边是数字的高位，右边是数字的低位

• 这时，如何将数据以二进制的形式存入计算机，就产生了分歧

  • 方法一： 按照人类阅读习惯，将数字的高位放到左边（低地址）、低位放到右边（高地址）？
  • 方法二： 还是与存储地址的高低保持一致，将数字的高位放到右边（高地址）、低位放到左边（低地址）？

• 方法一，被称作大端存储（big endian），the most significant bytes are stored before the less significant bytes.
  

• 方法二，被称作小端存储（little endian），the least significant bytes are stored before the more significant bytes
  

2.2 总结

• 大端存储还是小端储存，可以按照先存的是低位还是高位数据进行区分
  • 先存储的是高位数据，则是大端存储
  • 先存储的是低位数据，则是小端存储
• 两种存储方式存储的都是同一个数，只是因为存入方式的不同，读取出来的字节的组合方式就发生了变化
  • 对于大端存储，读取出的字节流无需做任何处理
  • 对于小端存储，读取出的字节流，反转后得到的才是真实值

3. Base 128 Varints

• Base 128 Varints采用了little endian，是little endian的一种变种

• 每8个bit，实际只有7个bit对应真实的数据，最高位的bit表示是否还有下一个byte

• 具体的操作，举例如下：

  十进制：127
  二进制：111 1111
  Varints：0111 1111 （最高位0，表示没有后续byte） ----> 16进制: 0x7f
  
  十进制：128
  二进制（7bit分隔）： 1|000 0000
  Varints：
  	① 取最低的7bit: 1000 0000 （最高位1，表示有后续byte）----> 16进制: 0x80
  	② 剩余的1bit，不足补0: 0000 0001  （最高位0，表示没有后续byte）----> 16进制: 0x01
  	③ 小端存储：0x80，0x01
  	
  十进制：16385
  二进制（7bit分隔）：1|000 0000|000 0001
  Varints：
  	① 取最低的7bit: 1000 0001 （最高位1，表示有后续byte）----> 16进制: 0x81
  	② 中间7bit: 1000 0000 （最高位1，表示有后续byte）----> 16进制: 0x80
  	③ 剩余的1bit: 0000 0001 （最高位0，表示没有后续byte）----> 16进制: 0x01
  	③ 小端存储：0x81，0x80，0x01
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

4. 大端模式 vs 小端模式

• 在与阿里的大佬交流的过程中，他突然问了我这样一个问题：计算机中，使用大端模式更多，还是小端模式更多？

4.1 大端模式更好，还是小端模式更好？

• 要回答这个问题，可以先回答另一个问题：大端模式更好，还是小端模式更好？
• 哪种模式更好，需要结合具体的场景去判断
  • 从人类阅读习惯来说，大端模式的可读性更好
  • 有符号数的二进制表示中，最高位是符号位。使用大端模式存储有符号数，只需要读取第1 bit就可以判断数的正负性
  • 奇数的最低bit为1，使用小端模式，只需要读取第1 bit就可以判断数的奇偶性
  • 数的大小比较，都是从最低位开始比较。使用小端模式，数字是左对齐的，可以直接按位读取并比较
  • 乘法使用小端模式，可以向右进位，相对向左进位的大端模式更有优势
  • 还有很多其他场景，具体可以参考：字节序探析：大端与小端的比较
• 总结一下的话：
  • 如果要求数据的可读性较强，或者计算只涉及高位，则可以选择大端模式
  • 如果需要逐位运算，或者需要到从个位数开始运算，则可以选择小端模式

4.2 大端模式 & 小端模式的应用场景

• 大端模式的use case：
  • IBM 370大型机、大多数的精简指令集（reduced instruction set computers，RISC）计算机、摩托罗拉（Motorola）的微处理器
  • 计算网络的TCP/IP使用大端模式，因此大端模式又叫network order
• 小端模式的use case：
  • Intel处理器，DEC Alphas等都是用小端模式
  • 还有种说法：大多数的主机都是用小端模式

5. 总结

• 可别小瞧了计算机中，各种进制之间的转换或存储。对没有系统学习过的、或者学艺不精的人来说，是非常难的
• 就拿笔者这种，自认为计算机基础不错的人，在最开始看Base 128 Varints，是有点晕乎的
• 参考链接：
  • 大端和小端存储模式详解
  • Little and Big Endian Mystery
  • What Is Little-Endian And Big-Endian Byte Ordering?
  • big-endian and little-endian（use case）