简介
protostuff是一个java序列化库，支持向前和向后兼容。
protostuff的序列化编码算法和Protobuffer基本一致，都是基于varint编码的变长序列化方式，跟定长序列化相比，在绝大多数情况下，varint编码能够使得编码后的字节数组更小。
下面详解一下protosutff的序列化编码方案以及序列化过程中的内存分配模型。
序列化过程中的数据存储- LinkedBuffer
LinkedBuffer是用于存储序列化过程中字节数组的数据结构。由于在序列化之前，并不知道需要分配多大的连续内存空间，因此Protostuff设计了LinkedBuffer这种数据结构，通过将不连续内存组成一个链表的形式，使得能够在执行序列化过程中，动态的扩张。
public final class LinkedBuffer
{
final byte[] buffer;
final int start;
int offset;
LinkedBuffer next;
}简单说明一下这些成员变量的含义
byte[] buffer：用来存储序列化过程中生成的byte，默认是512大小
int start：buffer从start开始写
int offset：buffer已经写到了offset处
LinkedBuffer next：下一个LinkedBuffer
如上图，就是把多块连续内存，通过链表的形式链接在一起，每个LinkedBuffer的buffer字段保存了部分序列化的内容。当一个LinkedBuffer的buffer写满之后，就会创建一个新的LinkedBuffer，并链到末尾。Protostuff会在一个序列化过程中（称之为一个WriteSession），维护一个全局size，表示最终的byte[]的大小。填充完所有LinkedBuffer之后，还需要将这多个buffer写入到一块连续内存当中，即合并为一个byte[]。这时会根据size值分配一个byte[size]，然后遍历LinkedBuffer，直到把所有的buffer内容copy到byte[size]中，序列化过程结束。
LinkedBuffer到最终的byte[]代码如下：
public final byte[] toByteArray()
{
LinkedBuffer node = head;
int offset = 0, len;
final byte[] buf = new byte[size];
do
{
if ((len = node.offset - node.start) > 0)
{
System.arraycopy(node.buffer, node.start, buf, offset, len);
offset += len;
}
} while ((node = node.next) != null);
return buf;
}由此可以看出，这里需要经过一次内存拷贝。LinkedBuffer中的buffer回收也会导致gc。
编码方式
Protostuff采用了T-L-V的存储格式存储数据，其中的T代表tag，即是key，L是length，代表当前存储的类型的数据长度，当是数值类型（i32,i63等）的时候L被忽略，V代表value，即存入的值，Protostuff会将每一个key根据不同的类型对应的序列化算法进行序列化，然后按照key-length-value key-length-value的格式存储，其中key的type类型与对应的压缩算法关系如下:
|
write_type |
编码方式 |
type |
存储方式 |
|---|---|---|---|
|
0 |
Varint(负数使用Zigzag辅助) |
int32、int64、uint32、uint64、sint32、sint64、bool、enum |
T-V |
|
1 |
64-bit |
fixed、sfixed64、double |
T-V |
|
2 |
Length-delimi |
string、bytes、embedded、messages、packed repeated fields |
T-L-V |
|
3 |
Start group |
Groups |
写在集合内容之前 |
|
4 |
End group |
Groups |
写在集合内容之后 |
|
5 |
32-bit |
fixed32、sfixed32、float |
T-V |
Protostuff对于key（即tag）的计算，是通过（fieldNumber << 3) | wireType，里面的fieldNumber代表该字段的编号，代码为：
public static int makeTag(final int fieldNumber, final int wireType){
return (fieldNumber << TAG_TYPE_BITS) | wireType; //TAG_TYPE_BITS = 3;
}例如
@Tag(1) private long id;
这个tag计算到的结果就是 (1<<3)| 0 = 8
得到tag值之后，会写入到LinkedBuffer的buffer当中，通过当前LinkedBuffer的offset值确实写入的位置。
写入tag的代码如下
WriteSink.class
public LinkedBuffer writeVarInt32(int value,
final WriteSession session, LinkedBuffer lb) throws IOException
{
while (true)
{
session.size++; //session可以理解为对整个序列化长度的记录
if (lb.offset == lb.buffer.length)
{
// grow //这里表示当前的linkedBuffer的byte[]已经填充满了，需要分配下一个linkedBuffer了
lb = new LinkedBuffer(session.nextBufferSize, lb);
}
if ((value & ~0x7F) == 0) //value是正数，并且小于127（127二进制为01111111），则保存value为一个byte
{
lb.buffer[lb.offset++] = (byte) value;
return lb;
}
//保存value的最低7位，并且第8位置为1，然后value右移7位，进行下一次循环
lb.buffer[lb.offset++] = (byte) ((value & 0x7F) | 0x80);
value >>>= 7;
}
}写入一个int32类型的值value时，会判断如果 0 < value < 127，则可以用一个byte表示，低7位是value的值，第8位是0。否则，先保存最低7位，第8位为1，然后右移7位，继续重复这个过程。对于后者，为什么第8位要置为1呢？原因是Protostuff（Protobuffer）中规定：如果一个byte的最高位为1，则表示下一个byte跟当前byte有关，为0表示无关。从上述分析可以看出Protostuff的优势，java中本来用4个byte表示int，但是如果这个int的值比较小，在Protostuff序列化中，就不需要4个byte了。
举两个例子：
例子1:以上述tag计算后=8为例：二进制为00001000，直接写入byte即可，值为8。
例子2:value = 532。二进制为1000010100，第一个byte写入最低7位，第8位是1，即10010100，即-108，然后右移7位，写入第二个byte，最高位是0，即00000100，即4。
writeVarInt64和writeVarInt32是一样的实现逻辑。这就使得在java中本来用4个byte表示的int，用8byte表示的long，在Protostuff序列化中，会用到更少的byte。当然，如果这个int或者long的值比较大的情况下，会导致int分配5个byte,long分配9个或10个byte的情况，但是一般情况下，Protostuff还是能节省空间的。
对于负数的处理：
查看Protostuff源码，发现并没有对于负数进行特殊处理(Protobuf使用zigzag编码，把符号数转化为无符号，再使用varint编码，但在Protostuff中，并未发现这种处理方式)。由于计算机中对负数都是表示为很大的整数，因此Protostuff存储负数时就要花更多的存储空间。这里如果错误或遗漏欢迎指出。
对于String类型的序列化
在Protostuff中，string类型会存储为T-L-V的形式，Tag会采用varient编码。Length也是用varient编码，表示后面多少个byte是这个String的Value。Value是采用UTF-8编码，将string转化为byte[]。Length和Value的写入比较复杂。简单描述一下：
先通过str.length()预估Length的长度，为什么说是预估呢，因为有些char会占用多个byte（比如汉字），然后根据str.length()的大小在LinkedBuffer的byte[]中先预留n个byte，Value写完之后，再回过来写Length。
n的取值规则：
if (len < 43) n = 1; //即使所有的都是非ascii编码，最大也只需要1个byte
if(len < 5462) n = 2; //即使所有的都是非ascii编码，最大也只需要2个byte
if(len < 699051) n = 3; //即使所有的都是非ascii编码，最大也只需要3个byte
if(len < 89478486) n = 4; //即使所有的都是非ascii编码，最大也只需要4个byte
n = 5;
具体代码为
public static LinkedBuffer writeUTF8VarDelimited(final CharSequence str, final WriteSession session,
LinkedBuffer lb)
{
final int len = str.length();
if (len == 0)
{
if (lb.offset == lb.buffer.length)
{
// buffer full
lb = new LinkedBuffer(session.nextBufferSize, lb);
}
// write zero
lb.buffer[lb.offset++] = 0x00;
// update size
session.size++;
return lb;
}
if (len < ONE_BYTE_EXCLUSIVE)
{
// the varint will be max 1-byte. (even if all chars are non-ascii)
return writeUTF8OneByteDelimited(str, 0, len, session, lb);
}
if (len < TWO_BYTE_EXCLUSIVE)
{
// the varint will be max 2-bytes and could be 1-byte. (even if all non-ascii)
return writeUTF8VarDelimited(str, 0, len, TWO_BYTE_LOWER_LIMIT, 2,
session, lb);
}
if (len < THREE_BYTE_EXCLUSIVE)
{
// the varint will be max 3-bytes and could be 2-bytes. (even if all non-ascii)
return writeUTF8VarDelimited(str, 0, len, THREE_BYTE_LOWER_LIMIT, 3,
session, lb);
}
if (len < FOUR_BYTE_EXCLUSIVE)
{
// the varint will be max 4-bytes and could be 3-bytes. (even if all non-ascii)
return writeUTF8VarDelimited(str, 0, len, FOUR_BYTE_LOWER_LIMIT, 4,
session, lb);
}
// the varint will be max 5-bytes and could be 4-bytes. (even if all non-ascii)
return writeUTF8VarDelimited(str, 0, len, FIVE_BYTE_LOWER_LIMIT, 5, session, lb);
}所以，写入String的流程是：
1.写tag，varient编码
2.预估Length，预留n个byte
3.将string内容通过UTF-8编码，写入LinkedBuffer的byte[]中
4.根据3写入的实际的长度，得到Length，经过varient编码，写入预留的n个byte中。
这里就引出了一个问题，假设str.length = 50，预留的n = 2，string经过UTF-8编码后得到的byte[].length = 50，因为50 < 128，通过varient编码后，只需要1个byte。即预留了2个byte，但是实际Length只需要一个byte，因此需要将上述步骤3中的内容整体前移1位，这里就导致了一次System.arraycopy行为，n为其他值时情况类似，可以看到String越长，一旦出现整体前移，会产生一些性能损耗。
对于Map<K，V>的序列化
集合类型的序列化，以Map<K, V>为例。写tag的时候，会写两次，分别是在写内容之前和写内容之后。tag值的计算，同样是通过（fieldNumber << 3) | wireType得到，写内容之前，wireType为3，表示Start group，写内容之后，wireType为4，表示End group。我们简单说一下完整的流程。先通过(fieldNumber << 3) | 3计算得到tag值，写入。然后开始遍历Map<K, V>的Entry<K, V>,由于Entry<K, V>也被认为是一种group，因此写K，V之前又要先写入tag（wireType为3），然后分别按照K和V的类型写入K，V，之后写入tag(wireType为4)。所有的Entry<K, V>遍历完成后，写入Map的结束tag（wireType为4），代码如下：
写入Map的代码
public <T> void writeObject(final int fieldNumber, final T value, final Schema<T> schema,
final boolean repeated) throws IOException
{
tail = sink.writeVarInt32(
makeTag(fieldNumber, WIRETYPE_START_GROUP),
this,
tail);
schema.writeTo(this, value);
tail = sink.writeVarInt32(
makeTag(fieldNumber, WIRETYPE_END_GROUP),
this,
tail);
}上面代码的schema.writeTo(this, value)的实现
MapSchema
public final void writeTo(Output output, Map<K, V> map) throws IOException
{
for (Entry<K, V> entry : map.entrySet())
{
// allow null keys and values.
output.writeObject(1, entry, entrySchema, true); //递归调用writeObject方法
}
}分别写K和V
public void writeTo(Output output, Entry<K, V> message) throws IOException
{
if (message.getKey() != null)
writeKeyTo(output, 1, message.getKey(), false);
if (message.getValue() != null)
writeValueTo(output, 2, message.getValue(), false);
}对于自定义类型的序列化
自定义类型的序列化就不再赘述了，其实就是递归写入。
参考：