【Protobuf】Varintエンコーディングの仕組みとフィールド番号の重要性

プロトコールバッファーとは
1. Protobufの基本
2. フィールド番号の重要性
ワイヤーフォーマット
Protobufの利用シーン

プロトコールバッファーとは

プロトコルバッファ（Protocol Buffers、protobuf）は、構造化データのシリアライズ形式で、Googleによって開発された。
protobufは、XMLやJSONよりも効率的にデータをシリアライズし、小さいメッセージサイズと高速なパーシングを実現する。
基本的には、アプリとサーバーがProtobufを使ってデータをやり取りする際には、両方が同じメッセージ定義（.protoファイル）を共有している必要がある。これは、メッセージが正しくシリアライズされ、デシリアライズされるために必要。

Protobufの基本

.protoファイル: protobufのスキーマは.protoファイルに記述される。このファイルは、メッセージの型を定義し、フィールドの名前、型、番号を指定する。
メッセージ: protobufでデータ構造を定義する際に使用する基本的な単位。メッセージは一つ以上のフィールドを持つ。
フィールドの型: フィールドには様々な型を指定でき、スカラー型（数値、文字列、ブール値など）、他のメッセージ、列挙型などがある。
フィールド番号: 各フィールドにはタグ番号が割り当てられ、この番号はそのフィールドをユニークに識別する。この番号はワイヤーフォーマットで重要な役割を果たす。

Protocol Buffers

syntax = "proto3";

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

https://protobuf.dev/programming-guides/proto3/

フィールド番号の重要性

フィールド番号は、シリアライズされたデータ内で各フィールドを一意に識別するために使用される。受信側がメッセージをデシリアライズする際、これらの番号を使用して各フィールドのデータを適切に解釈し、元のメッセージ構造を再構築する。

したがって、フィールド番号はメッセージ定義内で一意でなければならず、一度使用された番号は変更することができない（後方互換性を保つため）。

例えば、先ほどのメッセージ定義にに対してname = "Alice", id = 123, has_pet = trueという値を設定した場合、シリアライズされたメッセージ全体は次のようなバイト列になる。

Protocol Buffers

0a 05 41 6c 69 63 65 10 7b 18 01

メッセージ全体のバイト列において、フィールド番号は各フィールドの値の前にあるキーにエンコードされている。このキーはフィールド番号とそのフィールドの型に基づいて計算された値。

0a ：name フィールド（フィールド番号1）のキー。
05 ：文字列 “Alice” の長さを表すvarint。
41 6c 69 63 65 ： “Alice” のUTF-8エンコーディング。
10 ：id フィールド（フィールド番号2）のキー。この場合、ワイヤータイプは0（varint）で、フィールド番号は2。したがってキーは (2 << 3) | 0 で 10 になる。
7b ：数値 123 を表すvarint
18 ：has_pet フィールド（フィールド番号3）のキー。ワイヤータイプは0で、フィールド番号は3。キーは (3 << 3) | 0 で 18 になる。
01 ：true（has_pet）を表すvarint

受け取り側はこのバイト列を先頭から順に読み、各キーを解析してどのフィールドがどのような型のデータを持っているかを識別する。そして、適切なデコーディング手法を使用して各フィールドの値を復元する。このプロセスを通じて、元のメッセージ構造が正確に再現される。

ワイヤーフォーマット

ワイヤーフォーマットは、メッセージがバイト列としてシリアライズされる形式。非常に効率的で、メッセージをパースしたりシリアライズしたりする際のオーバーヘッドが非常に小さい。ワイヤーフォーマットのプロセスの中でvarintエンコーディングが使われる。

https://protobuf.dev/programming-guides/encoding/

基本のVarintエンコーディングの仕組み

Varintは、整数のサイズに応じて使用するバイト数を変えることができるため、データのサイズを効率的に小さく保つことができる。
各バイトの最上位ビット（MSB、最も左側のビット）は継続ビットと呼ばれ、次のバイトもvarintの一部であるかどうかを示す。このビットが1である場合は、次のバイトもこの数値の一部であることを意味する。
各バイトの残りの7ビットはペイロードとして使われ、これらのビットを結合して最終的な数値を形成する。

Protocol Buffers

message Test1 {
  optional int32 a = 1;
}

Test1 メッセージでフィールド a に 150 を設定した場合、。a フィールドが1番目のフィールドであると仮定すると、エンコードされたメッセージは 08 96 01 というバイト列になる。

数値シリアライズ後のサイズ比較（VarInt・JSON・XML）

150という数字をVarInt・JSON・XMLでシリアライズした時のデータサイズを比較してみる

VarInt：96 01になり2バイト
JSON：単純に150という文字列になる。UTF-8では、標準のASCII文字（0から9の数字を含む）は1バイトでエンコードされるので、150は3バイト必要。キーを含むオブジェクト（例：{"a": 150}）では、追加の文字も考慮に入れる必要がある。この例では、{、"、a、"、:、スペース（省略可）、1、5、0、}が含まれるので、合計10バイト（スペースを含まない場合は9バイト）になる。
XML：<a>150</a>となる。<a>は3バイト、150は3バイト、</a>は4バイトで、合計10バイトが必要。

というわけで、VarInt（2バイト）・JSON（9-10バイト）・XML（10バイト）となり、VarIntを使用するProtoufではデータサイズを小さくできる。

150をvarintエンコーディングしたら9601になる理由

150を二進数に変換すると10010110になる。しかし、Protocol Buffersのvarintでは、数値を一連の7ビットのグループに分けてエンコードする。そして、各グループの前に1ビットを追加して、そのグループが最後かどうかを示す。これが継続ビット。

継続ビットが1である場合、それは「まだ数値が続く」という意味。0であれば、それが最後のグループ。

150の二進数表記10010110をvarintでエンコードするためには、7ビットごとに分け、必要に応じて継続ビットを追加する。しかし、150は7ビットで表すには多すぎる（150>2の7乗=128）ので、2つのバイトに分ける必要がある。

最初の7ビット（右から数えて）は 0010110 だが、これは150の最下位7ビット。
残りは 0000001 。これが上位ビットになる。

これらのグループの前に継続ビットを追加する

0010110 に継続ビット 1 を追加して 10010110 にする。これは「まだ続く」という意味。
0000001 に継続ビット 0 を追加して 00000001 にする。これは「これで終わり」という意味。

最終的には 10010110 00000001 というバイト列が得られるる。これが150をvarintでエンコードした結果。

Protobufの後方互換性

Protobufは後方互換性を重視している。既存のフィールドを削除せず、新しいフィールドを追加することで、既存のデプロイされたサービスと新しいサービスが互換性を保つ。
フィールドを削除する代わりに、非推奨とし、新しいフィールドを追加することが推奨される。

Protocol Buffers

// 旧バージョン
message Person {
  string name = 1;
  int32 id = 2;
}

// 新バージョン（フィールドの追加）
message Person {
  string name = 1;
  int32 id = 2;
  bool has_pet = 3; // 新しいフィールド
}

// 新バージョン（フィールドの削除）
message Person {
  string name = 1;
  int32 id = 2;
  // has_pet フィールドは削除されました
}

高度なフィールド型

Repeated Fields: 同じフィールドが複数回出現する場合に使用する。つまり、複数の値を一つのフィールドに持つことができる。配列やリストとして扱われる。
Map Fields: キーと値のペアを保持するためのフィールド。
Oneof Fields: 複数のフィールドのうち、同時に一つだけが値を持つことを保証する。

Protocol Buffers

syntax = "proto3";

message Person {
  string name = 1;
  int32 id = 2;
  bool has_pet = 3;
  repeated string emails = 4;
  map<string, string> attributes = 5;

  oneof contact_info {
    string email = 6;
    string phone = 7;
  }
}

ちなみに、このデータをProtobufでシリアライズするとすると、下記のようなバイナリデータになる。実際にはこちらのバイナリデータが通信時に送受信される。

Protocol Buffers

0a 05 41 6c 69 63 65 10 7b 18 01 22 12 61 6c 69 63 65 40 65 78 61 6d 70 6c 65 2e 63 6f 6d 2a 15 61 6c 69 63 65 2e 77 6f 72 6b 40 65 78 61 6d 70 6c 65 2e 63 6f 6d 32 0e 0a 03 61 67 65 12 02 33 30 32 10 0a 03 63 69 74 79 12 08 4e 65 77 20 59 6f 72 6b 3a 12 63 6f 6e 74 61 63 74 40 61 6c 69 63 65 2e 63 6f 6d

上記メッセージ定義はjsonだと下記のような構造を意味する。

Protocol Buffers

{
  "name": "Alice",
  "id": 123,
  "has_pet": true,
  "emails": [
    "alice@example.com",
    "alice.work@example.com"
  ],
  "attributes": {
    "age": "30",
    "city": "New York"
  },
  "email": "contact@alice.com"
}

サービス定義

Protobufはデータメッセージだけでなく、RPCサービスも定義できる。これにより、gRPCなどのRPCフレームワークと組み合わせて利用することができる。

Protocol Buffers

syntax = "proto3";

service PersonService {
  rpc GetPerson (PersonRequest) returns (PersonResponse);
}

message PersonRequest {
  int32 id = 1;
}

message PersonResponse {
  Person person = 1;
}