Goの固定長/可変長エンコーディングを理解する
この記事では、標準の encoding/binary パッケージを使ってカスタムフォーマットに従ってバイナリエンコーディングする方法と、その仕組みについて解説します。
はじめに
プログラム上で扱うデータ構造をネットワークやファイルに書き込む際は、何らかのフォーマットに従って自己完結したバイト列へとエンコードする必要があります。
プロセス間でデータをやりとりする場合は通常、言語非依存な標準化されたフォーマットを利用します。
しかし、多くの標準化されたフォーマットは冗長すぎる傾向にあります。Protocol BufferやApache Thriftはバイナリエンコーディング形式なので、テキストフォーマットと比べるとはるかにサイズを小さく出来ますが、これらは専用のスキーマを定義することが必須です。一つのプロセスからしかアクセスしないようなケースなど、Go言語特有のフォーマットでエンコードしたくなることがあります。
Go言語はこのようなケースのために、gobという独自のフォーマットを定義しており、 encoding/gob パッケージがそのためのAPIを提供しています。しかしこれはフィールド名をテキストフォーマットでデータに埋め込む仕様になっており、少数の固定長の値のみをエンコードしたい場合はしばしば冗長になりがちです。
Go言語は、バイナリエンコーディングのためのパッケージとして encoding/binary というパッケージも提供しており、少数の固定長数値型の値をエンコードするならこのパッケージがおすすめです。
本記事ではこれを使ってカスタムバイナリフォーマットをエンコード/デコードする方法について説明します。
エンコード対象
次の構造体を様々な方法でエンコードしていきます。
type Data struct {
ID uint32
Timestamp uint64
Value int16
}
全てのフィールドが固定長の数値型であることに注意してください。
固定長エンコーディング
上記の構造体のIDはuint32なので4バイト、Timestampはuint64なので8バイト、Valueはint16なので2バイト。よって1つの構造体の値のサイズ合計は14バイトです。まずはシンプルに、以下のフォーマットで14バイトのバイナリを作ります。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (bytes)
+---------------+-------------------------------+-------+
| ID | Timestamp | Value |
+-------+-------+-------------------------------+-------+
binary.ByteOrder
まずはbinary.ByteOrder インターフェースを使って、各値を愚直に直接エンコードしていく方法を紹介します。エンディアンを選択し、初期化済みのバッファへ順番に詰めていきます。バッファサイズが小さすぎるとパニックが起きてしまうことに注意してください。全てが固定長の型であるため、どんな数値が入っても予めサイズを予測することが可能だからこそ為せる技です。ここではエンディアンとしてBigEndianを選択しました。
data := &Data{
ID: 100, Timestamp: 1600000000, Value: 10,
}
buf := make([]byte, 14)
binary.BigEndian.PutUint32(buf[0:], data.ID)
binary.BigEndian.PutUint64(buf[4:], data.Timestamp)
binary.BigEndian.PutUint16(buf[12:], uint16(data.Value))
fmt.Printf("encoded binary length: %d\n", len(buf))
// encoded binary length: 14
各ビット数に応じてデコード関数が用意されているので、それらを使って順番にデコードしていきます。
decodedData := &Data{}
decodedData.ID = binary.BigEndian.Uint32(buf[:4])
decodedData.Timestamp = binary.BigEndian.Uint64(buf[4:12])
decodedData.Value = int16(binary.BigEndian.Uint16(buf[12:]))
fmt.Printf("ID: %d, Timestamp: %d, Value: %d\n", decodedData.ID, decodedData.Timestamp, decodedData.Value)
// ID: 100, Timestamp: 1600000000, Value: 10
当然ですが、エンコード時と同じエンディアンを指定しないとビットを反対方向から読み出してしまうことになるため、全く異なる結果になってしまいます。
しかしこの方法は少し面倒ですね。構造体にそのままデコードしてくれるAPIは無いのでしょうか？
あります。encoding/binary パッケージは、構造体や配列ごとストリームに読み書きするbinary.Writeとbinary.Readという2つの関数を提供しています。
binary.Write/Read
これらは全てのフィールドが固定長である構造体であれば、フィールドを定義順に埋めてくれます。スライスでも同様です。
エンコードは以下のように構造体を渡すことで、第一引数として渡したio.Writerがストリームに書き込んでくれます。内部では、第二引数として指定したエンディアンに基づいて上のフィールドから順番に詰めていきます。
data := &Data{
ID: 100, Timestamp: 1600000000, Value: 10,
}
buf := &bytes.Buffer{}
_ = binary.Write(buf, binary.BigEndian, data)
fmt.Printf("encoded binary length: %d\n", buf.Len())
// encoded binary length: 14
binary.Readにエンコード済みのバイト列を渡してあげれば、第三引数として渡した構造体へのデコードが可能です。ここでも勿論、エンコード時と同じエンディアンを指定しなければ結果が不正なものになってしまいます。
dst := &Data{}
_ = binary.Read(buf, binary.BigEndian, dst)
fmt.Printf("ID: %d, Timestamp: %d, Value: %d\n", dst.ID, dst.Timestamp, dst.Value)
// ID: 100, Timestamp: 1600000000, Value: 10
全体のコードはこちらです。シンプルにバイナリエンコーディング出来ることが分かりますね。
package main
import (
"bytes"
"encoding/binary"
"fmt"
)
type Data struct {
ID uint32
Timestamp uint64
Value int16
}
func main() {
data := &Data{
ID: 100, Timestamp: 1600000000, Value: 10,
}
buf := &bytes.Buffer{}
_ = binary.Write(buf, binary.LittleEndian, data)
dst := &Data{}
_ = binary.Read(buf, binary.LittleEndian, dst)
}
ただし、どんな型でも受け付けるということは必然的に内部でリフレクションが起きているということです。パフォーマンス要件が厳しい場合は、これがネックになる可能性があります。
ByteOrderで直接バイト列を詰めていく場合と比べてどのくらいのパフォーマンス差があるのか、筆者のラップトップ上（Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz with 16GB of RAM on macOS 10.15.7）でベンチマークを取ってみました。実際に使用したテストコードはこちら。
$ go test -benchmem -bench=. .
goos: darwin
goarch: amd64
pkg: hoge
cpu: Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz
BenchmarkEncodeWithByteOrder-8 1000000000 1.145 ns/op 0 B/op 0 allocs/op
BenchmarkEncodeWithStream-8 6005226 203.1 ns/op 144 B/op 4 allocs/op
PASS
ok hoge 2.944s
binary.Writeでストリームに書き込んだ場合の時間計算量は、直接ByteOrderを使った場合に比べて200倍近く遅いことが分かりました。
バッファサイズを明示的に指定する必要があったりと一手間必要ですが、時間計算量、空間計算量ともに効率を求めるならByteOrderで手動で詰めていく方が良さそうです。
可変長エンコーディング
上で紹介した固定長エンコーディングは事前にバッファサイズを割り当てるため、シンプルにエンコードできます。ただ、必要以上にサイズが大きくなってしまうという問題を抱えています。例えば符号付き32ビット整数値型であるint32は、-2147483648 から 2147483647までの整数値を許容するために常に32ビットのスペースを必要とします。しかしほとんどのケースで、実際の値はこれより小さな値になるはずです。小さな値の場合は末尾のいくつかのビットが空白になってしまうので、サイズを32ビットにするために無駄な大量の0を末尾に埋め込むことになります。これを防ぐには、可変長エンコーディングが便利です。
例えば、10という整数は2進数にすると1010であり、4ビットで表現できます。しかしこれが64ビット符号無し整数値型で表現されている場合、固定長エンコーディングすると末尾が0で埋められ、強制的に8バイト消費してしまいます。
# 本来は4bitなのに
1010
# 残り60bitを0でパディングしてしまう
1010000000000000000000000000000000000000000000000000000000000000
先程のPutUint64を用いて10をエンコードしてみると、実際に8バイト消費していることが分かります。
buf := make([]byte, 8)
binary.BigEndian.PutUint64(buf, 10)
fmt.Printf("encoded binary length: %d\n", len(buf))
// encoded binary length: 8
// 1バイトで十分なはずなのに、、
そこで、binary.PutUvarintを使うと以下のように結果サイズを1バイトにすることが出来ます。
buf := make([]byte, binary.MaxVarintLen64)
var x uint64 = 10
n := binary.PutUvarint(buf, x)
fmt.Printf("encoded binary length: %d\n", len(buf[:n]))
// encoded binary length: 1
可変長なので、数値が大きくなるほどバイトサイズも大きくなります。例えば256という整数は2進数にすると100000000であり、サイズは9ビットになります。そのためエンコードされたデータは2バイトになります。
buf := make([]byte, binary.MaxVarintLen64)
var x uint64 = 128
n := binary.PutUvarint(buf, x)
fmt.Printf("encoded binary length: %d\n", len(buf[:n]))
// encoded binary length: 2
デコードはbinary.Varintで行うことが出来ます。
i, _ := binary.Varint(buf[:n])
構造体を可変長エンコーディング
ではこのVarint関数群を使って、前節でも扱ったData構造体をエンコードしてみましょう。
data := &Data{
ID: 100, Timestamp: 1600000000, Value: 10,
}
IDは100でValueは10なので、これらはそれぞれ1バイトで表現できます。Timestampの1600000000は少し大きいので5バイト必要です。合計するとData構造体の値は、以下のように7バイトで表現出来ることが分かります。
0 1 2 3 4 5 6 7 (bytes)
+---+-------------------+---+
|ID | Timestamp |Val|
+---+-------------------+---+
固定長エンコーディングでは14バイト消費していたので、7バイト節約できましたね。
（6/19 更新: 各値のサイズをバイナリに含める必要は無いので修正しました）
可変長エンコードの実装は以下のようになります。
data := &Data{
ID: 100, Timestamp: 1600000000, Value: 10,
}
buf := make([]byte, 7)
n := binary.PutUvarint(buf, uint64(data.ID))
n += binary.PutUvarint(buf[n:], data.Timestamp)
n += binary.PutVarint(buf[n:], int64(data.Value))
fmt.Printf("encoded binary length: %d\n", len(buf[:n]))
// encoded binary length: 7
無事7バイトになったことが分かります。次にこれをデコードしてみます。
id, idLen := binary.Uvarint(buf)
ts, tsLen := binary.Uvarint(buf[idLen:])
value, _ := binary.Varint(buf[idLen+tsLen:])
decodedData := &Data{
ID: uint32(id),
Timestamp: uint64(ts),
Value: int16(value),
}
fmt.Printf("ID: %d, Timestamp: %d, Value: %d\n", decodedData.ID, decodedData.Timestamp, decodedData.Value)
// ID: 100, Timestamp: 1600000000, Value: 10
元通りにデコードすることが出来ましたね。これで復元可能なバイナリを、固定長エンコーディングよりも小さなサイズで作ることが出来るようになりました。
しれっとデコードしてしまいましたが、1行目のbinary.Uvarintの呼び出しに違和感を感じませんか？エンコードされたバイトスライスをそのまま渡しているのにも関わらず、適切な位置で読み出しを終了してデコードされたidを返してくれています。バイトサイズを指定しているわけでもないのに、どのように終了ビットを判断しているのでしょうか。
これには、Protocol Bufferが内部で使っているVarints (Variable Integers) というエンコーディング手法が使われています。
Varintsの仕組み
固定長バイトのデコードは、何も考えずに必要なバイト数を読み込むだけで実現できました。可変長の数値を許容するとなると、何らかの方法で後続バイトの有無を示す必要があります。
そのためにまず、各バイトを1ビットと7ビットの2つのパートに分けます。
- 先頭1ビット: 後続バイトの有無を示す
- 残りの7ビット: 実際のデータ
この先頭1ビットは最も大事なビットになるため、most significant bit (msb)と呼ばれています。msbが1である場合は、後続にまだ読み出すべきバイト列が続いていることを示します。0であればそのバイトが最後であるため、読み出しを終了します。
例えば、1を2進数で表すと1であり、これは1バイトで十分表現できます。そのため、1バイト目のmsbは0となり、エンコード結果は以下のようになります。
00000001
↑
msbは0
300の場合を考えてみましょう。300は2進数で表すと100101100であり、これは7ビットに収まりません。従ってエンコード結果は以下のように2バイトにまたがります。
10101100 00000010
↑ ↑
msbは1 msbは0なので終了
実データはmsbを除いた7ビットなので、それらをまず取り除きます。
10101100 00000010
0101100 0000010
Varintsでは最下位の7ビットグループが最初に保存されるため、最後にこれらを逆さにする必要があります。そうすると、300の2進数表記になっていることが分かります。
0000010 0101100
-> 100101100
-> 300
まとめ
encoding/binary パッケージを使った様々なバイナリエンコーディング手法を紹介しました。固定長エンコーディングを手動で行っていく方法と、ストリームに行う方法を紹介し、最後に可変長エンコーディングについて解説しました。
自分でプロトコルを定義して最もシンプルなパターンを実装したことで、既存の標準化されたバイナリプロトコルとの距離もグッと近づいたと思います。
最後に紹介したVarintsはProtocol BufferのWire Formatの土台となる概念であるため、これを理解することは現代の標準化されたプロトコルを理解する助けになると思います。この記事がその一助を担えたことを願います。
Discussion
興味のある話で読ませて頂きました。とても分かりやすかったです、ありがとうございますm(__)m
記事の、「まずはシンプルに、以下のフォーマットで10バイトのバイナリを作ります。」のところが、「14バイト」な気がしました。
@ddddddO さん、コメントありがとうございます。おっしゃる通りなので修正しました！