つくって学ぶ Protocol Buffers エンコーディング

この記事は、Merpay Tech Openness Month 2021 の 15 日目の記事です。
こんにちは。メルペイのバックエンドエンジニアの @ktr です。

メルペイではマイクロサービスアーキテクチャを採用しており、それぞれのマイクロサービス間の通信プロトコルとして gRPC を、リクエスト・レスポンスのシリアライズフォーマットとして Protocol Buffers を採用しています。Protocol Buffers はバイナリベースのプロトコルであり、テキストベースのプロトコルと比較して通信における転送量を大きく削減できます。

Protocol Buffers はどのような規則に基づいて入力をエンコード・デコードし、リクエスト・レスポンスのサイズを縮小させているのでしょうか？Protocol Buffers の仕組みについて理解し、さらにその理解を深めるために自分自身で Protocol Buffers のエンコーダ・デコーダをつくってみましょう。

なお、この記事ではプログラミング言語に Go を、Protocol Buffers 3 の実装として protocolbuffers/protocolbuf-go を参照します。

Protocol Buffers の基本

実装をしていく前に Protocol Buffers の基本について紹介します。

型

Protocol Buffers にはスカラ型として次のような型があります。

型	説明	対応する Go の型
double	倍精度浮動小数点型	float64
float	浮動小数点型	float32
int32	32 ビット整数型	int32
int64	64 ビット整数型	int64
uint32	32 ビット符号なし整数型	uint32
uint64	64 ビット符号なし整数型	uint64
sint32	int32 と同様。負数をより効率的に扱うことができる。	int32
sint64	int64 と同様。負数をより効率的に扱うことができる。	int64
fixed32	4 バイト固定の 32 ビット符号なし整数型	uint32
fixed64	8 バイト固定の 64 ビット符号なし整数型	uint64
sfixed32	4 バイト固定の 32 ビット整数型	int32
sfixed64	8 バイト固定の 64 ビット整数型	int64
bool	真偽値	bool
string	UTF-8 エンコードされた文字列もしくは ASCII	string
bytes	バイト列	[]byte

また、コンポジット型として message 型と enum 型があります。

message 型

message 型は複数のフィールドを持つ型です。それぞれのフィールドはスカラ型もしくはコンポジット型となっています。

message Request {
  string foo = 1;
  int32 bar = 2;
}

enum 型

enum 型は事前定義された値のリストを扱うための型です。

message Request {
  enum Enum {
    FOO = 0;
    BAR = 1;
    BAZ = 2;
  }
  Enum enum_field = 1;
}

フィールド

message 型のフィールドには oneof や repeated といったものを指定することができます。

oneof

oneof フィールドは選択肢の中からいずれか一つのみを受け入れるフィールドです。

message Request {
  oneof oneof_field {
    int32 foo = 1;
    string bar = 2;
  }
}

repeated

repeated フィールドはリストを表すフィールドです。

message Request {
  repeated int32 foo = 1;
}

map

次のように map のフィールドをつくることができます。

map<string, int32> foo = 1;

map は型ではないという点に気をつけてください。上記の構文はあくまでシンタックスシュガーであり、実際は次のような repeated な message 型と等価です。

message MapFieldEntry {
  key_type key = 1;
  value_type value = 2;
}

repeated MapFieldEntry map_field = 1;

Descriptor

型やフィールドの情報等を持つ要素のことを descriptor と呼びます。

Protocol Buffers はシリアライズしたバイト列に descriptor を一切保持していません。
かわりに、シリアライズ・デシリアライズするアプリケーション自身に持たせています。送信側が descriptor を元にリクエストをシリアライズし、受信側が descriptor を元にデシリアライズします。
これは通常、自動生成されたコード中で行われているので普段は目にすることはありません。

実装

ここまでで簡単に Protocol Buffers について紹介しました。では次に具体的な実装に触れつつ実際にエンコーダとデコーダを実装していきましょう。

エンコードされたバイト列に含まれる要素

たとえば次のような message 型があるとします。

message Request {
  int32 foo = 1;
}

フィールド foo の値が 150 のとき、エンコードされた message は 16 進数で表記すると次のようになります。

08 96 01

エンコードされたそれぞれのフィールドは必ず共通のヘッダを持ち、これをタグと呼びます。この例だと先頭 1 バイトの 08 がタグです。タグは次の 2 つの要素から導出されます。

• フィールド番号
• Wire type

フィールド番号はそのフィールドが持つ番号です。この例の場合、フィールド foo には 1 が割り当てられています。
Wire type はそのフィールド値がどのくらいの長さを持つかを知るための手がかりです。Wire type は次のような種類があります。

Wire type	意味	説明	対応する型
0	Varint	可変長整数	int32、int64、uint32、uint64、sint32、sint64、bool、enum
1	Fixed64	64 ビット固定長整数	fixed64、sfixed64、double
2	Bytes	バイト列	string、bytes、messages、packed repeated fields
5	Fixed32	32 ビット固定長整数	fixed32、sfixed32、float

Wire type は実際の型を示しているわけではないことに注意してください。Wire type はあくまでも値を読み取るための手がかりにすぎないため、読み取った値をどの型にするべきか知るためには descriptor を参照しなければいけません。

タグは次のようなロジックでエンコードされます。

fieldNumber << 3 | wireType

たとえばフィールド foo の場合、フィールド番号は 1、Wire type は 0 なので 08 となります。これはエンコードされたバイト列の先頭バイトと一致しています。

fieldNumber := 1
wireType := 0
tag := fieldNumber<<3 | wireType

fmt.Printf("%x", tag) // 08

タグの直後にはそのフィールドに対応する実際の値が続きます。

Wire type に基づいたエンコード・デコード

Varint

まず Wire type 0、すなわち Varint の値から見ていきましょう。
Varint の値のバイト列は MSB (Most Significant Bit) の値によって後続があるかどうかを示します。後続がある場合は MSB が 1 となり、ない場合は 0 となります。

たとえば 150 という値の場合、2 進数表記は次のようになります。

1001 0110

この値は次のようにエンコードされます。
先頭 1 バイト目を見てみると MSB が 1 となっており、後続があることがわかります。また、2 バイト目を見ると MSB が 0 となっており、これが最後の値ということがわかります。

1001 0110 0000 0001

この値を試しにデコードしてみましょう。
Varint の値を計算するには、各バイトの MSB を取り除き、各 7 ビットのグループを逆さにします。

1001 0110 0000 0001
→ 001 0110 000 0001
→ 000 0001 001 0110
→ 1001 0110

正しくデコードできました。

次が Varint をエンコードするコードです。
はじめにグループの数を求め、それに従って 7 ビットごとに値を分割します。先頭のグループが末尾に現れるようにするために、末尾から 7 ビットごとに切り出していき、append によって []byte 型の b の末尾に追加していきます。
末尾のグループ以外には 0x80 と OR 演算を行うことで MSB に 1 を付与しています。

func encodeVarint(val uint64) (int, []byte) {
    length := 1
    for v := val; v >= 1<<7; v >>= 7 {
        length++
    }

    b := make([]byte, 0, length)
    for i := 0; i < length; i++ {
        v := val >> (7 * i) & 0x7f
        if i+1 != length {
            v |= 0x80
        }

        b = append(b, byte(v))
    }

    return len(b), b
}

デコードを行うためには MSB が 0 になるまで 1 バイトずつ読み取りを行います。最初に読み取ったバイトが末尾になるようにループ変数 i を使って uint64(v) << (7*i) のように左シフト演算をしています。

func decodeVarint(in io.ByteReader) (length int, n uint64, _ error) {
    for i := 0; ; i++ {
        b, err := in.ReadByte()
        if err != nil {
            return 0, 0, err
        }

        length++

        v, hasNext := dropMSB(b)
        n |= uint64(v) << (7 * i)

        if !hasNext {
            return length, n, nil
        }
    }
}

func dropMSB(b byte) (_ byte, hasNext bool) {
    hasNext = b>>7 == 1
    return b & 0x7f, hasNext
}

Fixed64 および Fixed32

Wire type 1 の Fixed64 と Wire type 5 の Fixed32 はそれぞれ 64 ビットと 32 ビットの固定長値にエンコードされます。バイトオーダはリトルエンディアンです。

func decodeFixed64bit(in io.Reader) (uint64, error) {
    var n uint64
    if err := binary.Read(in, binary.LittleEndian, &n); err != nil {
        return 0, err
    }

    return n, nil
}

func decodeFixed32bit(in io.Reader) (uint32, error) {
    var n uint32
    if err := binary.Read(d.in, binary.LittleEndian, &n); err != nil {
        return 0, err
    }

    return n, nil
}

デコードも同様にリトルエンディアンで行います。

func encodeFixed64(n uint64) (int, []byte) {
    b := make([]byte, 8)
    binary.LittleEndian.PutUint64(b, n)
    return 8, b
}

func encodeFixed32(n uint32) (int, []byte) {
    b := make([]byte, 4)
    binary.LittleEndian.PutUint32(b, n)
    return 4, b
}

Bytes

Wire type 2 の Bytes の場合、値の長さと実際の値がエンコードされています。たとえば、bytes フィールドの値が foo であればエンコードされた値は次のようになります。

03 66 6f 6f

03 がこのフィールドの値の長さです。この値は Varint としてエンコードされます。
66 6f 6f が実際の値、つまり foo です。

func encodeBytes(b []byte) (int, []byte) {
    vn, vb := encodeVarint(uint64(len(b)))

    return vn + len(b), append(vb, b...)
}

デコードでは同じく Varint として値の長さを読み取り、次に実際の値を長さ分読み取ります。

func decodeBytes(in interface {
    io.ByteReader
    io.Reader
}) ([]byte, error) {
    _, n, err := decodeVarint(in)
    if err != nil {
        return nil, err
    }

    b := make([]byte, n)
    if _, err := in.Read(b); err != nil {
        return nil, err
    }

    return b, nil
}

実際の型への対応付け

ここまでで Wire type に基づいてどのようにバイト列を書き込んだり読み取ったりすれば良いのかを見てきました。
しかしこれだけではエンコーダ・デコーダと呼ぶにはまだ不十分です。Wire type はあくまでバイト列の読み取り・書き込みを行うための仕組みなので、実際の Protocol Buffers の型と対応しているわけではありません。そのため、型を Wire type に対応付けたり、Wire type を型に対応付ける必要があります。

Varint

Varint に対応する型は int32、int64、uint32、uint64、sint32、sint64、bool、enum のいずれかです。
sint32 と sint64 以外の型であれば単純にエンコード関数の型と揃うように型変換を行います。

func encodeValue(desc protoreflect.FieldDescriptor, val protoreflect.Value) (int, []byte, error) {
...
    switch desc.Kind() {
    case protoreflect.Int32Kind:
        n, b = encodeVarint(uint64(int32(val.Int())))
    case protoreflect.Int64Kind:
        n, b = encodeVarint(uint64(val.Int()))
    case protoreflect.Uint32Kind:
        n, b = encodeVarint(val.Uint())
    case protoreflect.Uint64Kind:
        n, b = encodeVarint(val.Uint())
    case protoreflect.Sint32Kind:
        n, b = encodeZigZag(val.Int())
    case protoreflect.Sint64Kind:
        n, b = encodeZigZag(val.Int())
    case protoreflect.BoolKind:
        var v uint64
        if val.Bool() {
            v = 1
        }
        n, b = encodeVarint(v)
    case protoreflect.EnumKind:
        n, b = encodeVarint(uint64(val.Enum()))
...

sint32 と sint64 の場合は若干複雑です。
これらの型は、int32 や int64 に比べて負数を効率的に扱うために ZigZag エンコーディングを用いています。

int32 や int64 で負数を扱うと、2 の補数表現で扱われるため、バイト数が極端に大きくなります。たとえば int32 フィールドの値が -1 であった場合、そのエンコード後の値は ffff ffff ffff ffff ff01 となります。これはたとえば 1 のエンコード後の値 01 と比べると遥かに大きなものとなっています。

ZigZag エンコーディングを使うと、次の表のように正数と負数が交互に現れるようにエンコードされます。

元の値	エンコード後の値
0	0
-1	1
1	2
-2	3
2	4

具体的には次のような計算式となります。

(n << 1) ^ (n >> 31)

これ元にした Go のコードは次のとおりです。

func encodeZigZag(n int64) (int, []byte) {
    v := uint64(n<<1) ^ uint64(n>>63)
    return encodeVarint(v)
}

デコードは次のような計算式です。

(n << 1) ^ (n >> 63)

また、Go のコードは次のとおりです。

func decodeZigZag(n uint64) int64 {
    return int64(n>>1) ^ int64(n)<<63>>63
}

Fixed64 および Fixed32

Fixed64 に対応する型は fixed64、sfixed64、double です。また、Fixed32 に対応する型は fixed32、sfixed32、float です。
double と float 以外の型であれば単純にエンコード関数の型と揃うように型変換を行います。

func encodeValue(desc protoreflect.FieldDescriptor, val protoreflect.Value) (int, []byte, error) {
...
    switch desc.Kind() {
...
    case protoreflect.Fixed64Kind:
        n, b = encodeFixed64(val.Uint())
    case protoreflect.Sfixed64Kind:
        n, b = encodeFixed64(uint64(val.Int()))
    case protoreflect.DoubleKind:
        n, b = encodeFixed64(math.Float64bits(val.Float()))
...
    case protoreflect.Fixed32Kind:
        n, b = encodeFixed32(uint32(val.Uint()))
    case protoreflect.Sfixed32Kind:
        n, b = encodeFixed32(uint32(val.Int()))
    case protoreflect.FloatKind:
        v := math.Float32bits(float32(val.Float()))
        n, b = encodeFixed32(v)
...
}

double と float の場合、単純に型変換をすることはできず、IEEE 754 の交換方式での表現を行う必要があります。Go の場合、これは math.Float64bits 関数で行えます。
デコード時には math.Float64frombits を使うことで float64 の値にできます。

Bytes

Bytes に対応する型は string、bytes、messages、packed repeated フィールド です。
packed repeated フィールド以外の型であれば単純にエンコード関数の型と揃うように型変換を行います。

func encodeValue(desc protoreflect.FieldDescriptor, val protoreflect.Value) (int, []byte, error) {
...
    switch desc.Kind() {
...
    case protoreflect.BytesKind:
        n, b = encodeBytes(val.Bytes())
    case protoreflect.StringKind:
        n, b = encodeBytes([]byte(val.String()))
    case protoreflect.MessageKind:
        msg, err := Encode(val.Message().Interface())
        if err != nil {
            return 0, nil, err
        }

        n, b = encodeBytes(msg)
...

packed repeated フィールドの扱いについては後述します。

repeated フィールド

repeated キーワードが付与されたフィールドの場合、エンコーディング方式が 2 種類あります。
1 つ目が単純なフィールドと同じようにエンコードする方式、2 つ目がフィールド値の packing を行う方式です。

まず、1 つ目の方式について紹介します。次の例は repeated フィールドを含む message 型とそのエンコードされたバイト列です。foo には 1、2、3 の値がセットされています。

message Request {
  repeated int32 foo = 1;
}

08 01 08 02 08 03

この方式の場合、単純に同じタグが複数回バイト列中に出現します。この例では 08 がタグですが、08 が 3 回出現していることがわかるかと思います。Protocol Buffers のデコーダは読み取りの際、このフィールドに対応する descriptor が、 このフィールドが repeated であることを示していれば出現したすべての値を保持し、リスト化します。

この方式は実装が非常にシンプルである反面、同じタグが繰り返し現れるため、その分だけ転送量が増加します。これを最適化するのが 2 つ目の方式です。

2 つ目の方式では、repeated フィールドの値をひとまとめにすることでタグが一度しか現れないようにします。この方式が使えるのは数値型のみで、Protocol Buffers 3 ではデフォルトで使用されます。

この方式では repeated フィールドの Wire type を 2、Bytes としてエンコードします。そのため、タグの次にバイト列の長さが格納されています。実際の値はこのフィールドの値を連結したものとなります。次の例は先程の message 型と値をこの方式を使ってエンコードした結果です。

0a 03 01 02 03

タグが 0a となっています。0x0a & 0x07 の結果から、Wire type が Bytes になっていることがわかります。その次のバイト 03 が値の長さを示し、後続の 01 02 03 がそれぞれの値となります。

oneof フィールド

oneof フィールドはエンコードされたバイト列に特有の情報を持ちません。oneof フィールドに属するいずれかのフィールドが単純にエンコードされているだけです。しかし、一つの oneof フィールドが複数回バイト列中に出現した場合は最後に出現した不値を採用しなければならないということが仕様として定義されているため、その点に注意する必要があります。

不明なフィールド

Descriptor に情報がないフィールド番号が現れることがあります。これは API が更新され、message 型に新しいフィールドが追加された場合などに発生します。この場合、Protocol Buffers は後方互換性を維持するためにエラーを出さずに単純にそのフィールドを無視します。

最終的な実装

これまで紹介した Protocol Buffers の仕組みを元に実装したエンコーダ・デコーダは以下のリポジトリにあります。

https://github.com/ktr0731/proto

まとめ

この記事では Protocol Buffers の基本から紹介し、次にエンコーダ・デコーダを実装する上で必要な仕組みについて紹介しました。
エンコードされたバイト列はスキーマの情報を持たず、タグと呼ばれるフィールド番号と Wire type の組み合わせのみをメタデータとして保持します。実際のフィールド値は型および Wire type に基づいてエンコードされています。同じ Varint のフィールドであっても、型の違いによってエンコード方式が変わることがあります。たとえば、sint32 や sint64 は ZigZag エンコードの結果を Varint としてエンコードします。

このようにスキーマの情報をデータ自身ではなく descriptor のみに持たせたり、sint32 や sint64 で ZigZag エンコーディングによって負数を効率的に扱うことでテキストベースのプロトコルよりデータサイズを大きく縮小できています。

Protocol Buffers のエンコーディングを理解し、実際に実装してみると部分的に複雑なところはあっても、全体としては非常にコンパクトな仕様だということが見えてきます。
興味があればぜひ皆さんも実装してみてください。

関連記事

• https://developers.google.com/protocol-buffers/docs/encoding
• https://developers.google.com/protocol-buffers/docs/proto3
• https://github.com/protocolbuffers/protobuf-go