深入解析VarInt变长整数：编码原理、工程实现与踩坑指南

1. 为什么二进制协议里要专门搞出一个 VarInt先从一个很平凡的问题说起。写网络通信、写序列化框架的人几乎都遇到过这种尴尬协议里要传一个字段明明大多数情况下它的值只有几十、几百但为了照顾极端情况你不得不给它分配固定的 4 字节甚至 8 字节。一个字符串数组、一堆小整数扎堆的时候光这些“撑场面”的字节就占了半条消息CPU 和带宽都花在了毫无信息量的 0 上。VarIntVariable-length Integer变长整数就是冲着这个问题去的。它不再给每个整数分配固定宽度而是按数值大小动态决定长度值越小占的字节越少。Protocol Buffers、SQLite、Apache Avro、Kafka 的底层存储、Bitcoin 的区块格式全都在用类似机制。可以说凡是追求极致压缩率的二进制协议几乎都绕不开 VarInt 这个话题。这篇笔记是我在实际项目里折腾 VarInt 的一段记录。不打算只讲定义我会从编码规则、手写实现、性能对比、踩坑排查几个角度展开。适合想搞懂序列化底层原理的人也适合正在设计自有二进制协议、纠结“字段到底怎么编码”的同行。看完之后你至少能自己手写一套可用的变长整数编解码并且知道什么时候该用它、什么时候该绕开它。2. 核心编码规则7 位一组的切分游戏2.1 先说最关键的直觉VarInt 的实现思路其实特别朴素每个字节只取低 7 位当作“数据位”最高位当作“延续标记”。如果最高位是 1说明这个数还没编码完后面还有后续字节如果最高位是 0说明这是最后一个字节。换句话说把一个整数切成一堆 7-bit 的小段按小端顺序往外排每一段前面再加一个“是否还有下一段”的标记位。就这么简单。用数字 300 走一遍完整流程。300 的二进制是1001011009 位需要拆成两段低 7 位0101100也就是十进制 44高 2 位10也就是十进制 2按规则第一个字节要设置延续位所以0101100变成10101100也就是十六进制0xAC。第二个字节不用延续直接是00000010也就是0x02。所以 300 编码成 VarInt 就是两个字节0xAC 0x02。解码的时候从第一个字节开始先读低 7 位 44看到最高位是 1 就继续读下一个字节下一个字节读出 2最高位是 0 结束。然后按位移累加44 (2 7) 44 256 300。完全还原。2.2 不同位宽的上限因为每个字节贡献 7 个有效位所以32 位以内的无符号整数编码后最多 5 个字节7 × 4 28位放不下 32 位需要第 5 个字节补 4 位64 位以内的无符号整数编码后最多 10 个字节7 × 9 63位最后一个字节只放最高 1 位常用数值的字节数分布大概是数值范围编码字节数有效位0 ~ 1271 字节7 位128 ~ 163832 字节14 位16384 ~ 20971513 字节21 位2097152 ~ 2684354554 字节28 位268435456 ~ 42949672955 字节35 位实际只需要 32 位这里有个很关键的直觉如果你的数据大量集中在 127 以内VarInt 可以把字段宽度压缩到原来的四分之一到八分之一。但如果你的数据是均匀分布的随机大整数VarInt 反而会膨胀——一个 64 位随机数常常要占用 9、10 个字节比固定 8 字节还大。2.3 负数与 ZigZag绕不开的坎大多数语言里整数默认带符号。如果直接把负数当成无符号位模式去做 VarInt由于负数的二进制表示是高位全 1编码结果必然是整整 10 个字节分毫不少。这完全违背了压缩的初衷。Protocol Buffers 的解决思路是如果你确定字段可能是负数就用sint32/sint64类型。这种类型先做一次 ZigZag 变换把负数映射成正数再做 VarInt。ZigZag 的核心思想是让绝对值小的数映射出来的无符号数也小。映射规则很简单对于 int32 n映射成 uint32 ( n 1 ) ^ ( n 31 ) 对于 int64 n映射成 uint64 ( n 1 ) ^ ( n 63 )这个公式怎么理解如果 n 是非负数n 31是 0结果就是n 1等于把原来的数左移一位低位补 0。如果 n 是负数n 31是 0xFFFFFFFF结果相当于(n 1) ^ 0xFFFFFFFF也就是按位取反后的结果低位补 1。举几个例子原值ZigZag 结果00-1112-2324-3521474836474294967294-21474836484294967295看到规律了吗ZigZag 把 -1 变成 1把 1 变成 2把 -2 变成 3数值在零附近时映射结果都在个位数。这样一来诸如步长、偏移量、时间差这类“偶尔为负但绝对值通常不大”的字段编码后同样可以压缩到 1、2 个字节。解码同样是对称的逆运算uint32 u 还原成 int32 ( u 1 ) ^ -( u 1 )拆开看u 1取最低位是 0 说明原数是正数是 1 说明原数是负数。-(u 1)配合异或正好恢复原来的符号和数值。这个技巧在工程里太常用了。我自己后来设计协议时凡是会存差值、增量、距离之类字段的一律默认走 ZigZag压根不给负数留“全 10 字节”的坑。3. 手写实现与性能实测记录3.1 编码器的 C 语言实现原理清楚了代码其实非常短。我在项目里维护的原型大概长这样static inline size_t encode_varint(uint64_t value, uint8_t *out) { size_t n 0; do { uint8_t byte (uint8_t)(value 0x7F); value 7; if (value ! 0) { byte | 0x80; } out[n] byte; } while (value ! 0); return n; }这里有个容易忽略的点do-while 而不是 while。因为即使 value 是 0也要输出一个0x00字节不能输出空串。如果没有字段内容或者没有长度前置解码端读到的会是乱码。编码器注意两点value 0x7F确保字节的高位始终是 0再按需置位延续标记避免与数据位冲突。无符号右移是必须的。如果误用了带符号类型负数的算术右移会把高位补 1循环就会变成一个死循环。3.2 解码器的鲁棒版本解码看起来更简单但工程上最容易出问题的是“边界与恶意数据”。裸写版如下static inline int decode_varint(const uint8_t *buf, size_t len, size_t *used, uint64_t *result) { uint64_t value 0; int shift 0; size_t i 0; while (i len shift 63) { uint8_t byte buf[i]; value | (uint64_t)(byte 0x7F) shift; if ((byte 0x80) 0) { *used i; *result value; return 0; } shift 7; } return -1; // 数据截断或编码非法 }两个防护点截断保护i len必须放第一位。实际网络包经常粘包、拆包流式解析时很可能只收到半个 VarInt此时要返回“数据不完整”等待后续数据到达而不是硬解。长度上限保护64 位 VarInt 最多 10 字节所以shift超过 63 仍未遇到结束字节已经可以断定是非法数据。如果把 10 个连续延续字节都读进来并继续位移可能会发生未定义行为的左移超宽位。3.3 ZigZag 的配套实现ZigZag 部分我直接给出常用写法static inline uint64_t zigzag_encode_i64(int64_t n) { return ((uint64_t)n 1) ^ (uint64_t)(n 63); } static inline int64_t zigzag_decode_i64(uint64_t u) { return (int64_t)((u 1) ^ -(u 1)); }注意这里编码时必须先把n 63用无符号数语义处理。C 语言对带符号右移是否算术移位是编译器实现定义的绝大多数平台上是算术右移但保险起见我会先转成uint64_t再移位避免平台差异。3.4 性能实测压缩率和耗时我在一个内部统计系统的消息格式上做过一次对比。场景是传输一组“采样计数”大多数值落在一两百范围内偶尔有几个几千的峰值。用三套方案编码同一批 100 万个采样值方案总字节数相对体积固定 uint324 字节4,000,000100%固定 uint648 字节8,000,000200%VarInt1,312,468约 33%VarInt Delta 差分986,221约 25%注意VarInt Delta 差分那行不是 VarInt 本身的功劳而是先把相邻采样值做差再对差值做 VarInt。因为采样的差值一般很小压缩效果又上了一个台阶。这个组合拳我强烈建议做监控、时序数据的人试试。耗时方面编解码都是纯位运算加循环现代 CPU 分支预测非常擅长处理“绝大多数情况只有 1 个字节”的模式。实测单次解码在 10 纳秒量级相比序列化框架里的内存拷贝和系统调用基本可以忽略不计。这也是 VarInt 能大规模铺开的核心原因既省带宽又不拖 CPU 后腿。注意不要盲目迷信压缩率。如果你的字段是随机数或者哈希值VarInt 编码后平均 9~10 字节比固定 8 字节还糟。设计协议前先统计真实分布再说。4. 工程中的典型坑与排查技巧4.1 坑一缓冲越界与“半截数据”这是我在做 TCP 流式解码时踩得最狠的一次。客户端发来长度字段我用 VarInt 解码结果测试环境偶发崩溃。排查半天发现是有一次只收到了 VarInt 的第一个字节且该字节的延续位是 1解析函数继续读第二个字节时直接越界。修复方式就是前面代码里的i len检查。但这里还有一个更隐蔽的细节解码函数如果遇到“数据不完整”的情况不应该返回一个错误就完事因为接收缓冲区里可能还有后续有效的完整包。我的做法是把used置为 0让上层知道“这个包还没收齐继续等待数据别移位、别丢弃”。排查这类问题最直接的手段是打印收到的每个字节的十六进制原始值逐字节对照协议。别一上来就怀疑并发、怀疑锁先确认字节流长得到底对不对。4.2 坑二负数还在裸奔对这个必须反复强调。Protocol Buffers 里如果你把int32类型的负数直接编码规则上它不会按 4 字节或 5 字节输出而是先符号扩展成 64 位再输出 10 字节。也就是说负数在int32字段里比正数多占一倍空间。防御措施很明确协议设计阶段凡是可能为负的字段一律用 sint 类型走 ZigZag。解码端如果看到数值超出字段预期范围优先检查是不是符号处理错误。JSON 互操作场景别把 ZigZag 结果直接当原始整数暴露要还原成带符号数。4.3 坑三字节序的错位这里说的“小端顺序”只针对 VarInt 内部的分组顺序。比如300编码后是0xAC 0x02先低 7 位、后高 7 位这和 x86 的小端内存布局有点相似但不完全是一回事。很多人第一反应是拿htons、ntohl那套去转结果越转越乱。记住一点VarInt 的分组排序是固定的与平台字节序无关。编码器和解码器只要都按“先低组后高组”的规则写就不需要做任何hton处理。如果中间有一层网络字节序转换那也要在 VarInt 的整体处理之外去考虑不要混在一起。排查字节序问题时我习惯手写几个边界值做单测输入期望编码0001277F12880 0116383FF 7F1638480 80 014294967295FF FF FF FF 0F9223372036854775807FF FF FF FF FF FF FF FF 7F这几个用例能覆盖 1 字节到 9 字节的所有边界切换每次改动编解码代码后我都会先跑一遍。4.4 坑四超长数据与拒绝服务解码端必须限制 VarInt 的最大长度否则恶意方可以构造一串无限延续字节让你的解析循环一直转下去。标准做法是超过 10 字节或位移超过 63 位直接判定非法协议并断开连接或抛出异常。我见过不少项目不加这个限制觉得“自己人发的数据不会这么坏”。直到某次压测工具误生成了一串0x80开头的垃圾字节整个接入层直接卡死。从那以后我的解码器一律分两层物理层限制最长 10 字节逻辑层再限制字段值不超过约定类型范围。两道闸门缺一不可。5. VarInt 的变体与不同场景的取舍5.1 主流的三种变体VarInt 并不是只有一种规则不同生态各自演化出了略有差异的版本。LEB128主要出现在 DWARF 调试信息和部分编译器工具链里。规则和前面讲的基础版完全一致小端分组、7 位有效位、最高位标记。负数可以按无符号位模式编码也可以走 ZigZag。Protocol Buffers 的 Varint规则同样是 base-128 变长编码但特别之处在于它的负数处理策略普通 int32 负数符号扩展到 64 位后走 10 字节sint32/sint64 强制搭配 ZigZag。此外Protobuf 的 field key字段号左移 3 位或上 wire type本身就是个 VarInt解码的时候先解 field key再按 wire type 决定接下来怎么解析。Bitcoin 的 CompactSize和上面两种不太一样。它按首字节的数值分段小于 0xfd 时就是一个字节的直接值0xfd 表示后面跟 2 字节小端 uint160xfe 表示后面跟 4 字节 uint320xff 表示后面跟 8 字节 uint64。这种设计的好处是解码时直接按前缀决定后续字节数不用逐位判断延续标记代价是 252~65535 之间的数值会多花一个字节。Bitcoin 大部分计数交易数量、脚本长度都不大所以这个折中很划算。5.2 各主流格式里的实际应用场景使用方式特点Protocol Buffers字段 key 数值都用 VarInt核心设计配 ZigZag 处理负数SQLite页面内记录长度用 VarInt1~9 字节数据库文件紧凑性的关键Apache Avro长整、整数都用 ZigZag VarInt大数据生态里默认选项Kafka 消息格式记录长度与时间戳差分用 VarInt高吞吐下节省磁盘和带宽BitcoinCompactSize 表示数量和长度前缀决定长度不逐位判断这些格式虽然细节有差异但设计动机惊人的一致在实际业务数据里小整数是绝大多数长度字段、数量字段、索引字段极少撑满 4 字节。花几十行代码做一次变长编码换来的往往是 30%~60% 的体积缩减。5.3 什么时候不要用 VarInt我不止一次建议团队别用 VarInt场景主要有三类固定结构、固定宽度的硬件寄存器或传感器数据。这类数据每个字段都有严格的对齐要求变长编码会破坏结构体美感和随机访问能力。需要随机寻址的数组索引表。可变长意味着你不能直接index * 4定位第 N 个元素而必须顺序扫描或额外维护偏移表。如果想快速下标访问固定宽度还是最优。随机大整数密集的数据。已经说过了编码完比原来还大纯亏。一句话总结VarInt 是给“头重脚轻”的数据用的不是给“所有整数”无脑套的。设计协议前先盯着你的真实数据分布看一会儿。6. 一点个人体会我从第一次接触 Protobuf 编解码到亲手设计一个小型消息协议中间隔了好几年。回头看VarInt 给我最大的启发不是那套位运算技巧而是“去掉对固定宽度的执念”这件事本身。很多人在设计二进制协议时第一反应是“这是一个 int那就分配 4 字节那是一个 long分配 8 字节”。这个思维模式在大多数业务场景里其实是浪费。真正值钱的不是字节宽度而是信息的概率分布。高频小值给短编码低频极端值给长编码这几乎就是压缩的本质。另外一个小技巧送给你如果你的通信场景里有一条消息需要反复编解码先把 VarInt 编解码做成内联函数或者宏避免函数调用开销。我实测过内联后整体吞吐能提升 5%~8%。这点提升可能不重要但在网关、接入层这种每秒几百万次编解码的场合积少成多很容易拉开差距。最后还想再说一句不管多复杂的二进制协议Debug 的起点永远是打开编辑器看原始字节。把 VarInt 那套“高位置延续位 低 7 位负载”的规则刻进脑子里你解任何变长字段都会快很多。