Go with Examples: Protobuf Encoding Mechanics

7 min readNov 2, 2020

TLDR;

Minimise usage of field numbers > 15
Use packed option for long repeated fields
Embedded Messages are wrapped with metadata of higher level messages

Background

Protobuffers is an encoding mechanism for message sending between servers & services. It is highly popular at many companies mainly because of its great performance in terms of

(1) encoding & decoding speed &

(2) its ability to save bandwidth by being able encode into binary.

This blog will describe the mechanisms of how objects gets encoded to be sent over the wire. Follow along with the examples on your own!

Part 1 — Message Structure

Let’s look the simplest message me can send:

//example 1 proto filemessage SingleInteger {
    optional uint64 integer = 1;
}//main.gom1 := &integers.SingleInteger{
    Integer: proto.Uint64(1),
}

After Marshalling the above object, you will get the following []byte. For every object being marshalled, we will get some bytes encoding the metadata (data about the data) as well as the data itself to be sent.

MetaData

Let’s first look at the metadata. There are two important metadata that needs to be communicated — it’s field number & its type

Looking at the table provided provided on their website, it is quite clear to see that the meta data is telling us that the data is of type 0 (Varint) and has field number of 1.

source: https://developers.google.com/protocol-buffers/docs/encoding

Q: What is MSB & what happens if we want to store a data value > 127?

Part 2 — Variable length Integers (Varints)

Let’s rewrite our example with a higher value:

//example 2.1 proto filemessage SingleInteger {
    optional uint64 integerA = 1;
}//main.gom1 := &integers.SingleInteger{
    IntegerA: proto.Uint64(18789),
}

Marshalling the object, we get:

To store value 18789, it will overflow the 7 bits allocated for data storage & will require another 2 bytes to encode its data. This is where the MSB comes into play.

Each byte in a varint, except the last byte, has the most significant bit (msb) set — this indicates that there are further bytes to come.

So to get the data value, what you do is:

Step 1 — Remove the MSB for each byte

Step 2 — Rearrange them with the least significant byte first

Step 3 — Join them Together!

Calculating binary 100100101100101 → decimal 18789

Q: Does this apply for the field number too?

Yes! Let’s first look at Integer A which is on field number 15 and fits nicely into the four bits allocated to it within the MetaData byte.

But for Integer B, its field number 16 will overflow the 4 bits allocated & will require another byte to encode its metadata. This is where the MSB comes into play.

//example 2.2 proto filemessage SingleInteger {
    optional uint64 integer = 16;
}//main.gom1 := &integers.SingleInteger{
    Integer: proto.Uint64(1),
}

After applying the same steps above, you should be able to get the following bits to determine the field number = 16.

Q: How can we use this knowledge to our advantage?

If you really want to be efficient, fields 1–15 should be be reserved for the most frequently used fields. Alternatively, using embedded messages where it makes sense is also another way to go. (see below)

Part 3 — Signed Integers

Looking at the variable integer types (Type 0) that protobuf supports, one interesting comparison is that between standard integers (int32, int64) and signed integer types (sint32, sint64).

If you use int32 or int64 as the type for a negative number, the resulting varint is always ten bytes long…(but) If you use one of the signed types, the resulting varint uses ZigZag encoding, which is much more efficient.

Let’s take a look at an example:

//example 3 proto filemessage SignedInteger {
    optional int32 integer = 1;
    optional sint32 s_integer = 2;
}//main.gom1 := &integers.SignedInteger{
    Integer:  proto.Int32(-1),
    SInteger: proto.Int32(-1),
}

Here’s the Encoding for the Integer field

And here’s the Encoding for the SInteger field

Q: Why 10 bytes?

Protobuf stores a negative int32 in 64 bits (I assume because to allow a negative int32 to be able to be unmarshalled into a int64 field).

Remember each data byte only has 7 useful bits for storing data. So to store 64 bits, we will need 10 bytes.

Q: What is ZigZag encoding? Why is the data byte for SInteger = 1?

Google probably noticed that for most applications, the usual integers to be used in messages are usually close to zero. So they used the following encoding.

This way, negative integers need not waste space storing the entire two’s complement in 10 bytes when it can be done in less.

Part 4 — Strings

The principle design consideration for strings is that unlike ints, it can be of variable lengths from 1 byte to infinitely long.

Therefore what we do is to insert the length of the string into the metadata.

//example 4 proto filemessage ProtoString {
    optional string s = 1;
}//main.gom1 := &protostrings.ProtoString{
    S: proto.String("123"),
}

After marshalling…

Some things to take note of…

1) The Metadata value is 10 now instead of 8 now that we are using a type 2 value

2) Length byte is 6 as we have 6 following bytes encoding the string data

3) The following byte thereafter stores the UTF encoding of the string.

Part 5 — Repeated fields

For repeated fields, the encoding mechanism varies slightly between proto2 and proto3 with thee use of packed fields. Let’s first start with the use of packing

//example 5 proto filemessage RepeatedInteger {
    repeated uint64 integer = 1;
    repeated uint64 packed_integer = 2 [packed=true];
}//main.gom1 := &repeated.RepeatedInteger{
    Integer:       []uint64{1, 2, 3},
    PackedInteger: []uint64{1, 2, 3},
}

Encoding for Integer Field

Encoding for Packed Integer Field

As we can see, unpacked repeated fields repeat the metadata byte of each element within the array while with the packing option turned on, all data bytes share the same metadata.

The encoding mechanism varies slightly between proto2 and proto3 with thee use of packed fields. In proto2, the packing option must be explicitly toggled in the example above, but for proto 3 packing will be used by default.

Part 6 — Embedded messages

In our final example, let’s see how messages within messages are encoded.

//example 5 proto filemessage TopMessage{
    optional EmbeddedMessage m = 1;
}message EmbeddedMessage{
    optional uint64 i = 1;
    optional string s = 2;
    optional bool b = 3;
}//main.gom1 := &embedded.EmbeddedMessage{
    I: proto.Uint64(1),
    S: proto.String("123"),
    B: proto.Bool(true),
}m2 := &embedded.TopMessage{
    M: m1,
}

Result:

If you have noticed, this is very similar to TCP/HTTP headers where lower level messages are wrapped with a header from the higher level messages. Let’s see if you correctly identify why each byte is encoded as such. I’ve already gave you half the answer and told you what the byte encodes for

Part 7 — Conclusion & Further Puzzles

Protobuf is a very neat & efficient encoding mechanism for message sending and on top of the that, the code is so intuitive as you can see by the simple examples.

There are many more features to protobuf that was not mentioned in this tutorial. But I hope i’ve provided the basics for you to carry on by yourself.

If you want, there are some interesting cases I have listed below. How many do you think you can guess correctly?

Marshalling into a different object with same field types but different names?
Marshalling into a different object with different field types?
How will protobuf encode Packed strings?
Can you unmarshall a packed repeated []uint64 into an embedded message & vice versa?