编码和压缩

编码前置知识

变长编码和定长编码：

定长编码使用固定字节数来表示，如int32类型固定使用4个字节表示
变长编码是需要几个字节就使用几个字节，如对于int32类型的数字1来说，只需要1个字节

小端序和大端序

Big-Endian：大端序，高位字节在前，低位字节在后，这是人类读写数值的方法
Little-Endian：小端序，低位地址在前，高位地址在后

TLV编码格式

TLV即Tag-Length-Value, Tag作为该字段的唯一标识，Length代表Value数据域的长度，最后即Value数据本身

负数的处理

如果要表示的数是一个负数，采用上面所说的方式编码，就会占用很多字节，因为对于比较常用（数值比较大）的负数来说，转成补码后会有很多个1，也就是说占用的字节会比较多，这样如果还采用上面那种方式编码，就得不偿失了，因此Google又新增加了一种数据类型，叫sint，专门用来处理这些负数，其实现原理是采用zigzag编码，zigzag编码的映射函数为：

ZigZag(n) = (n << 1) ^ (n << k)，k为31或者63

最终的效果就是将负数映射为正整数，了解到这里即可

thrift

Thrift是一套包含序列化功能和支持服务通信的RPC框架，主要包含三大部分：代码生成、序列化框架、RPC框架，大致相当于protoc + protobuffer + grpc，并且支持大量语言，保证常用功能在跨语言间功能一致，是一套全栈式的RPC解决方案。

二进制编码常用TLV编码实现，TLV是指由数据的类型Tag，数据的长度Length，数据的值Value组成的结构体，几乎可以描述任意数据类型，TLV的Value也可以是一个TLV结构，正因为这种嵌套的特性，可以让我们用来包装协议的实现。Thrift中Binary和Compact编码实现都是采用的TLV编码变种实现，两者不同点主要在于对整数类型处理方面。

每个字段又有一个编号，因此是一个四元组: (id,type, length,value) 其中length在定长里不用，在非定长里用最高位表示。

两种序列化方式:

binary序列化

简单数据类型为定长编码，包含一个字节类型标识+两个字节编号+类型对应定长值。因此这里就不用长度来记录了，因为是定长。

compact序列化

区别就是使用不定长编码，每个字节，我们只使用低7位，最高的一位作为一个标志位（msb）：

1：下一个byte也是该数字的一部分
0：下一个byte不是该数字的一部分

该编码好处是对于小数字采用更少字节，大数字采用更多字节，但大部分使用都是小数字，则整体看压缩作用明显。

对于负数用了最高位，会先做个转换。

protocol buffer

Protobuf 是什么？

简要说明 Protobuf 是一种由 Google 开发的语言中立、平台中立、可扩展的序列化协议，通常用于数据存储和通信。
它将数据结构定义为 .proto 文件，并通过工具生成不同语言的代码，用于序列化和反序列化数据。

Protobuf 的数据结构是如何定义的？

通过 .proto 文件定义消息（message）和字段（field），每个字段都有一个唯一的标识符（tag number）。

syntax = "proto3";

message Person {
  string name = 1;
  int32 id = 2;
  string email = 3;
}

Protobuf 是如何进行序列化的？

解释如何将数据结构转换为二进制格式，如何在网络中传输数据，以及如何反序列化为原始数据结构。

Protobuf 相比 JSON 和 XML 的优点是什么？

更紧凑的二进制格式，序列化和反序列化速度更快，传输数据量更小，适合高效的网络通信。

Protobuf 适用的场景有哪些？

适用于高性能的网络通信、存储、RPC 服务、微服务等。

Protobuf 的版本兼容性：

解释 Protobuf 如何支持向前兼容性和向后兼容性。例如，通过字段编号（tag）确保不同版本之间的数据兼容性。
介绍如何处理字段添加、删除、重命名等操作时的兼容性问题。

Protobuf 2 与 Protobuf 3 的区别：

required 字段在 proto3 中被移除。在 protobuf v2 中，required 字段如果缺失，反序列化时会导致解析错误（parsing error），而 v3 移除了 required，使得所有字段都是可选的，以提高兼容性。
解释如何处理字段类型、枚举默认值、extensions 和 oneof 等问题。
Pb3 如果值为默认值则不传输，所以pb3传输效率更高

字段修改

Protobuf中字段类型和名字的修改

字段名称不可更改，如果要更改名称，应该删除原字段并添加新字段。
字段类型可以改变，但需要谨慎，避免不兼容的类型变更。
删除字段后，字段编号不能重用，需要保持向后兼容性。

Thrift 中字段类型和名字的修改

字段名称不可直接更改，应当删除原字段并添加新字段。
字段类型可以更改，但需要注意更改的兼容性，尽量避免不兼容的类型更改。
删除字段后，字段编号不能重用，需要确保向后兼容性。
字段名称改了，网络传输时对比的是序号，所以type兼容的话，还是可以解析出value的。

压缩算法

RLE

RLE 又叫 Run Length Encoding ，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如， JPEG 就使用它）。

比如aaabbb变成3a3b

哈夫曼

哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。

哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。

Fulongのblog

编码和压缩