ネットワーク・プロトコル#166

スキーマ駆動シリアライゼーション — Protocol Buffersに見る可変長エンコーディングと後方互換性

CCSDS Space Packetの固定ビット幅ヘッダは、フィールドを1つ足すたびに送受信双方のコードを手で書き換える必要がある。Protocol Buffers的なスキーマ駆動シリアライゼーションが、タグ付きフィールドとVarint可変長エンコーディングによってこの問題をどう解決するかを、符号量の数式とともに読み解く。

前提知識: CCSDS Space Packetプロトコル — 探査機データを仕分ける最小単位の器

Protocol BuffersシリアライゼーションVarint後方互換性スキーマ設計

この回で学ぶこと

前回のCCSDS Space Packetでは、一次ヘッダの48ビットを、Packet Version Number(3ビット)、Packet Type(1ビット)、APID(11ビット)……というように、フィールドごとに固定のビット幅を割り当てて手作業で定義するやり方を見ました。この「固定ビット幅を人間が決め、その通りに送受信双方のパーサを実装する」というアプローチには、大きな強みがあります。ビット位置さえ分かれば即座にフィールドへアクセスでき、処理系は何の解析ロジックも持たずに済みます。

しかしこのアプローチには、ソフトウェア工学的な代償もあります。もし新しい観測モードのために「校正温度」という16ビットのフィールドをパケットに追加したくなったらどうなるでしょうか。探査機側のフライトソフトウェアと、地上側のパケット解析ソフトウェアの両方を、寸分違わず同じビットレイアウトになるよう書き換え、再コンパイルし、両者を同時に(あるいは互換性を保つ順序で)デプロイしなければなりません。フィールドの追加・削除・並び替えのたびにこの同期が発生し、双方の実装が少しでもズレれば、後続のすべてのフィールドがずれて読めなくなります。これは特に、探査機が打ち上げ後に何年もかけてミッションを遂行し、その間に地上側のソフトウェアだけが何度も更新されるような長期ミッションにおいて、深刻な運用上の負担になります。

今回は、この「手作業でのビットレイアウト定義」が抱える保守性の課題に対して、地上のソフトウェア工学の世界がどう答えを出してきたかを見ます。題材とするのは、Googleが開発し2008年にオープンソース化した Protocol Buffers に代表される、スキーマ駆動シリアライゼーションという考え方です。データ構造を.protoファイルのようなスキーマ言語で宣言し、そこから送受信双方のシリアライズ/デシリアライズコードを自動生成する仕組みが、なぜフィールドの追加・変更に強いのか。その心臓部にあるVarint(可変長整数)エンコーディングの数理と、フィールド番号によるタグ付けが実現する後方互換性の設計原則を、数式とともに追っていきます。

直感的導入: 「間取り図を手で測る」から「設計図から自動生成する」へ

CCSDS Space Packetのヘッダ設計を、部屋の間取りに例えてみましょう。設計者は「玄関は3畳、リビングは11畳、寝室は14畳……」というように、各部屋(フィールド)の広さ(ビット幅)をあらかじめ紙の上で決め、そのメジャー(ビット位置)を大工(送受信双方の実装者)に手渡します。大工はメジャー通りに正確に壁を立てなければ、部屋同士が重なったりズレたりしてしまいます。この方式は、一度設計が固まれば非常に効率よく施工できますが、後から「玄関にもう1畳分の下駄箱スペースを足したい」となったとき、玄関から先のすべての部屋の壁を(送受信双方で同時に)立て直す必要があります。

Protocol Buffers的な発想は、これとは違うアプローチを取ります。設計者は各部屋に固有の番号札(フィールド番号)を割り当てるだけにして、実際の広さは部屋ごとに「これくらいの荷物が入る分だけ」その場で確保します(可変長)。そして「番号札1番の部屋、番号札2番の部屋……」という設計図(スキーマ)をコンパイラに渡すと、コンパイラが送信側・受信側それぞれの言語で、荷物の詰め方・取り出し方のコードを自動的に書き出してくれます。受け取った側は、知らない番号札の部屋(未知のフィールド)に出くわしても、「この部屋の広さはここまで」という自己申告(長さ情報)を頼りに、中身を理解できなくてもその部屋をまるごと読み飛ばして次の部屋に進めます。これが、後述する後方互換性の核心です。

もう少し工学的に言うと、Protocol Buffersのワイヤーフォーマットは、各フィールドを

\underbrace{\text{タグ}}_{\text{フィールド番号 + 型情報}} \;\|\; \underbrace{(\text{長さ})}_{\text{型による}} \;\|\; \underbrace{\text{値}}_{\text{データ本体}}

というTag-(Length-)Value形式で並べたバイト列として表現します。CCSDS Space Packetの一次ヘッダが「決められた順序で決められたビット幅を並べる」だけだったのに対し、この形式では各フィールドが「自分が何番のフィールドで、値がどこまで続くか」を自分自身のバイト列の中に埋め込んでいる点が本質的に異なります。

数式定式化

スキーマ定義とコード生成

Protocol Buffersでは、まずデータ構造をスキーマ言語で宣言します。たとえば探査機のハウスキーピングテレメトリを表すメッセージは、次のように書けます。

message HousekeepingTelemetry {
  uint32 timestamp   = 1;
  float  temperature = 2;
  float  bus_voltage = 3;
  repeated float solar_panel_current = 4;
}

ここで = 1, = 2, … は各フィールドの値そのものではなく、フィールド番号を宣言しています。この.protoファイルをコンパイラ(protoc)に通すと、C++・Python・Java・Rustなど、送信側と受信側がそれぞれ使っている言語ごとに、このメッセージをシリアライズ/デシリアライズするクラスやコード一式が自動生成されます。両者は同じ.protoファイルという単一の真実の源(single source of truth)からコードを生成しているため、「送信側と受信側で手作業によるビットレイアウトの実装がズレる」というCCSDS的な固定フォーマットが抱えていたリスクが、そもそも構造的に発生しません。フィールドを1つ追加したければ、スキーマに1行足して両者のコードを再生成するだけで済みます。

タグの符号化: フィールド番号とワイヤ型の合成

各フィールドの手前に置かれるタグは、フィールド番号 $F$ と、値のバイト列としての種類を表すワイヤ型 $W$ を、次のように1つの整数へ合成したものです。

T = (F \ll 3) \mathbin{|} W, \qquad W \in \{0, 1, 2, 5\}

ここでビットシフト $\ll 3$ とビット論理和 $|$ が使われており、下位3ビットがワイヤ型、残りの上位ビットがフィールド番号を表します。主なワイヤ型は次の通りです。

$W$	名称	用途	値の続き方
0	Varint	整数(int32, uint32, bool など)	後述のVarintとして続く
1	64-bit	double, fixed64	固定8バイトが続く
2	Length-delimited	string, bytes, 埋め込みメッセージ, repeated	Varintで長さ $L$ を示した後、 $L$ バイトの値が続く
5	32-bit	float, fixed32	固定4バイトが続く

この合成されたタグ $T$ 自体も、後述するVarintとして符号化されます。つまり受信側は、バイト列の先頭からまずタグをVarintとして読み、 $T \bmod 8$ でワイヤ型を、 $T \gg 3$ でフィールド番号を復元し、ワイヤ型に応じた読み方(固定長読み・長さ接頭辞読み・Varint読み)で値を取り出す、という手順を1つのループとして繰り返すだけで、メッセージ全体を復元できます。

Varint: 可変長整数エンコーディング

Protocol Buffersのワイヤーフォーマットの中核が Varint です。非負整数 $n$ を、7ビットずつのグループ(ディジット)に分解します。

n = \sum_{i=0}^{k-1} d_i \, 128^{i}, \qquad 0 \le d_i \le 127 \ (i = 0, \dots, k-2), \quad 1 \le d_{k-1} \le 127

すなわち $n$ を128進法(7ビット単位)で展開し、各ディジット $d_i$ を1バイトに収めます。ただしそのバイトの最上位ビット(MSB)は継続フラグとして使い、まだ続くディジットがあれば1、これが最後のディジットなら0とします。

\text{byte}_i = \begin{cases} d_i \mid 0x80 & (i < k-1, \text{まだ続く}) \\ d_i & (i = k-1, \text{最後}) \end{cases}

各バイトの残り7ビットにデータそのものが入るため、1バイトあたり実質7ビット分の情報しか運びませんが、値が小さいほど必要なバイト数 $k$ が少なく済むという可変性こそがこの符号のねらいです。 $n$ を表現するのに必要なバイト数は

k(n) = \begin{cases} 1 & n = 0 \\ \left\lfloor \dfrac{\lfloor \log_2 n \rfloor}{7} \right\rfloor + 1 & n \ge 1 \end{cases}

で与えられます。具体的な境界値を並べると次の表の通りです。

$n$ の範囲	必要バイト数 $k(n)$	固定4バイト(uint32)との比較
$0 \le n \le 127$ ( $2^7-1$ )	1	$-75\%$
$128 \le n \le 16{,}383$ ( $2^{14}-1$ )	2	$-50\%$
$16{,}384 \le n \le 2{,}097{,}151$ ( $2^{21}-1$ )	3	$-25\%$
$2{,}097{,}152 \le n \le 268{,}435{,}455$ ( $2^{28}-1$ )	4	$\pm 0\%$
$268{,}435{,}456 \le n \le 2^{32}-1$	5	$+25\%$

ここで重要な非対称性が見えます。値が小さい( $n < 2^{28}$ )限りはVarintが固定4バイト表現より得をしますが、32ビット整数の値域の上限付近( $n$ が $2^{28}$ を超える)まで使われる場合は、逆に固定長より1バイト多く消費してしまいます。つまりVarintは万能に帯域を節約する符号ではなく、値の分布が小さい側に偏っている(テレメトリのカウンタ、シーケンス番号、多くのフラグ値など)ことを前提にした符号だという点に注意が必要です。

平均符号長と帯域節約の定量的評価

この非対称性を定量的に評価するために、簡単化のため「 $n$ の桁数(ビット長 $\lfloor \log_2 n\rfloor + 1$ )が $[1, B]$ の範囲でほぼ一様に分布する」というモデルを考えます(これは多くのユニバーサル符号の解析で使われる標準的な単純化です)。ビット長 $b$ のとき必要なVarintバイト数は $k = \lceil b/7 \rceil$ なので、期待符号長は

\mathbb{E}[k] = \frac{1}{B}\sum_{b=1}^{B} \left\lceil \frac{b}{7} \right\rceil

たとえば $B = 32$ (uint32の最大ビット長)とすると、 $b=1,\dots,7$ で $k=1$ 、 $b=8,\dots,14$ で $k=2$ 、 $b=15,\dots,21$ で $k=3$ 、 $b=22,\dots,28$ で $k=4$ 、 $b=29,\dots,32$ で $k=5$ となり、

\mathbb{E}[k] = \frac{7(1) + 7(2) + 7(3) + 7(4) + 4(5)}{32} = \frac{7+14+21+28+20}{32} = \frac{90}{32} \approx 2.81 \ \text{バイト}

固定4バイトと比べると、この一様分布モデルの下でも平均約 $1 - 2.81/4 \approx 30\%$ の節約になります。しかし実際の宇宙データのフィールド(シーケンスカウンタ、デルタ圧縮されたセンサ値、フラグの束など)は一様分布よりもさらに小さい値に偏っていることが多く、実務上はしばしば50%以上の削減が報告されます。Googleの公開資料でも、Protocol Buffersで符号化した典型的なメッセージは、同等のXML表現と比べてサイズが3〜10分の1、エンコード/デコード速度が20〜100倍になると報告されています(出典は本文末尾)。ただし後者の速度差は主に、XMLのようなテキストベースのパース(文字列マッチングと数値変換)を回避できることによるもので、Varintそのものの寄与は主にサイズ削減の側です。

後方互換性: フィールド番号が実現する「読み飛ばし」の原則

CCSDS Space Packetの固定フォーマットでは、パケットデータフィールドの先頭から何ビット目が何のフィールドかは、送信側・受信側の双方があらかじめ完全に同一の仕様を共有していることを大前提にしています。もし送信側だけが新しいフィールドを先頭付近に追加すれば、受信側は以降のすべてのビットオフセットがずれた状態で誤ってデータを解釈してしまいます。固定フォーマットには「このフィールドは知らないので読み飛ばす」という余地がそもそもありません。

Protocol Buffers的なタグ付きフィールドでは、事情が大きく異なります。前述の通り、すべてのフィールドはタグ(フィールド番号+ワイヤ型)から始まり、ワイヤ型さえ分かれば値の終わりの位置を、その値の中身を意味的に理解しなくても機械的に特定できます。

ワイヤ型0(Varint)なら、継続ビットが0になるバイトまで読めば終わり。
ワイヤ型2(Length-delimited)なら、直前のVarintで示された長さ $L$ バイトぶん読み飛ばせば終わり。
ワイヤ型1・5(固定長)なら、8バイトまたは4バイト読み飛ばせば終わり。

この性質により、次の2つの後方互換性の原則が成り立ちます。

未知のフィールドの追加に強い。 新しいバージョンの送信側が、旧バージョンの受信側パーサが知らないフィールド番号を新たに送っても、旧パーサはそのフィールドの意味を理解できないまま、タグとワイヤ型の情報だけを頼りに機械的に読み飛ばし、残りのフィールドを問題なく解析し続けられます。
フィールドの省略に強い。 あるフィールドが送信されなければ、受信側はそのフィールド番号がストリーム中に単に現れないだけで、後続のフィールドの位置には一切影響しません(CCSDSの固定フォーマットのように、後続フィールドがすべてズレるということが起きない)。省略されたフィールドはスキーマ側で定義されたデフォルト値として扱われます。

この「フィールド番号によるタグ付け+自己記述的な長さ情報による読み飛ばし可能性」が、スキーマ駆動シリアライゼーションが長期運用のミッションや、頻繁にソフトウェアが更新される地上系システムで好まれる中心的な理由です。ただし、この柔軟性を活かすにはルールがあります。一度使ったフィールド番号は(たとえそのフィールドを廃止しても)決して再利用してはならず、廃止するフィールド番号は「予約済み」として明示的に空けておく必要があります。番号を使い回すと、古いデータを新しいスキーマで誤って解釈してしまう事故につながるためです。

実務での使われ方

なぜCCSDSの固定フォーマットは今なお主流なのか

ここまで見てきた柔軟性にもかかわらず、探査機とのRFリンクを流れる実際のデータは、依然としてCCSDS Space PacketやSpace Data Link Protocolの固定ビット幅フォーマットが主流であり、Protocol Buffers的なタグ付きスキーマへの全面的な移行は起きていません。理由は大きく3つあります。

第一に、決定論的な処理時間(WCET: Worst-Case Execution Time)が要求されるためです。 固定ビット幅のフィールドは、ビットオフセットが定数であるため、パーサはループも条件分岐もほぼ持たず、単純な算術演算だけでフィールドにアクセスできます。これに対しVarintの復号は「継続ビットが立っている限りループする」という、値によって反復回数が変わる処理です。搭載フライトソフトウェアの多くは、安全性認証のために処理時間の上限を静的に保証できることを要求されており(MISRA Cのようなコーディング規約が動的ループ回数や動的メモリ確保を強く制限するのもこのためです)、値依存でループ回数が変わるVarintのような可変長構造は、この種の検証と本質的に相性が悪いのです。

第二に、ハミング符号・ゴレイ符号やBCH符号で学んだ前方誤り訂正符号の多くが、固定長のブロック(符号語)を前提に設計されているためです。 これらの符号は「 $n$ ビットの符号語のうち $k$ ビットが情報ビット」という固定の構造を持ち、ビット誤りが起きても符号語の境界そのものは保たれます。一方、可変長のTLVストリームでは、1つのフィールドの継続ビットや長さVarintが1ビットでも化けると、そのフィールドの終端位置の特定を誤り、後続のフィールドすべてが芋づる式に読み違えられる**同期崩壊(desynchronization)**が起こり得ます。CCSDSのフレーム同期マーカーのような固定間隔の再同期ポイントを持たない可変長ストリームは、深宇宙リンクのように高いビット誤り率を前提とせざるを得ない環境では、単独では扱いにくい構造なのです。

第三に、レイテンシです。 動的な長さ解析やコード生成されたパーサの呼び出しは、単純なビットマスクとシフト演算に比べてわずかとはいえオーバーヘッドを伴います。姿勢制御のような低遅延応答が要求されるリアルタイム処理では、この差が無視できない場合があります。

地上系ソフトウェアでの採用

一方で、地上セグメントアーキテクチャの内部、すなわちミッション運用センターのデータ処理パイプラインや、複数の地上局・複数のミッションを横断するデータ配信基盤では、事情が異なります。ここでは通信路はRFリンクではなく地上の光ファイバー網やクラウドインフラであり、ビット誤り率は無視できるほど低く、計算資源にも比較的余裕があります。CCSDSのミッション運用サービス標準群である MO (Mission Operations) サービス(CCSDS 520.0-M、CCSDS 521.0-B-2 Mission Operations Message Abstraction Layer などで規定)は、もともとXMLベースの符号化を主軸としていましたが、近年はより効率的なバイナリ符号化のバインディングも整備が進んでいます。加えて、多くの新興の商業宇宙事業者やクラウドベースのミッション運用システムでは、地上セグメント内部のマイクロサービス間通信に、gRPC(Protocol Buffersをワイヤーフォーマットとして使うRPCフレームワーク)やJSONベースのREST APIを採用する例が増えています。これは、地上系のAPI設計の回で見たREST/gRPCというウェブ由来の設計思想の議論とも重なりますが、ソフトウェアが頻繁に更新される地上系のシステムでは、フィールド追加のたびに全コンポーネントを同期して書き換えずに済む後方互換性の高さの方が、Varintのようなビット単位の帯域節約よりも実務上の価値が大きい、という判断が働いているためです。

つまり、宇宙データ通信の全体像としては、探査機からRFリンクを介して地上局に届くまでは決定論的な固定フォーマット(CCSDS)、地上局から科学者・運用者の手元に届くまでの地上系ネットワークではスキーマ駆動の柔軟なフォーマット(Protocol Buffers、JSON等) という、通信路の特性に応じた使い分けがなされている、と整理できます。

演習問題

$n = 300$ 、 $n = 16{,}384$ 、 $n = 2{,}097{,}151$ のそれぞれについて、Varintエンコーディングで必要になるバイト数を、本文中の式 $k(n)$ または境界値の表を使って求めてください。
あるテレメトリのシーケンスカウンタが $0$ から $2^{20}-1$ の範囲で一様分布すると仮定します。本文の期待符号長の考え方にならって、Varintで符号化した場合の平均バイト数を計算し、固定4バイト(uint32)表現と比べて何%の帯域削減になるか求めてください。
あるVarintストリームの、あるフィールドの継続ビットがビット誤りによって反転してしまったとします。このとき受信側のパーサに何が起きるかを、本文の「同期崩壊」の議論に沿って説明し、CCSDS Space Packetの一次ヘッダで1ビットが反転した場合(たとえばAPIDフィールドの1ビット)と比べて、被害の範囲がどう異なるかを論じてください。
探査機の搭載フライトソフトウェアが、あえてProtocol Buffers的な可変長タグ付きフォーマットを採用しなかったとして、その設計判断を支持する技術的理由を、本文で挙げた「決定論的な処理時間(WCET)」「前方誤り訂正符号との親和性」の2点に触れながら、自分の言葉で説明してください。

まとめと次回予告

Protocol Buffersに代表されるスキーマ駆動シリアライゼーションは、.protoのようなスキーマ言語から送受信双方のコードを自動生成することで、CCSDS Space Packetの固定ビット幅フォーマットが抱えていた「フィールド変更のたびに双方の実装を手作業で同期する」という保守上の課題を解消します。その心臓部にあるVarint符号化は、小さい値をより少ないバイト数で表現する可変長整数エンコーディングであり、フィールド番号によるタグ付けは、未知のフィールドや省略されたフィールドがあっても受信側パーサが機械的に「読み飛ばし」を行える後方互換性を実現します。一方で、決定論的な処理時間、前方誤り訂正符号との親和性、低レイテンシといった要求から、探査機とRFリンクを結ぶ物理的な経路ではCCSDSの固定フォーマットが今なお主流であり続けています。このように「通信路の特性に応じてシリアライゼーション方式を使い分ける」という視点は、今後の回でも繰り返し登場します。

次回は視点を少し変えて、探査機1機と地上局1つという構図を離れ、月面や火星表面に展開される複数のローバー・着陸機・中継ノードが互いにどうデータをやり取りするか——惑星表面資産のメッシュネットワーキング——に軽く触れていきます。

参考文献

Protocol Buffers Documentation, Encoding, Google, protobuf.dev/programming-guides/encoding
Protocol Buffers Documentation, Language Guide (proto3), Google, protobuf.dev/programming-guides/proto3
Kenton Varda, “Protocol Buffers: Google’s Data Interchange Format,” Google Open Source Blog, 2008
CCSDS 133.0-B-2, Space Packet Protocol, Blue Book
CCSDS 521.0-B-2, Mission Operations Message Abstraction Layer, Blue Book
CCSDS 520.0-M-2, Mission Operations Services Concept, Magenta Book
J. R. Wertz, D. F. Everett, J. J. Puschell (eds.), Space Mission Engineering: The New SMAD