🥰

Scala でナイーブな HPACK(RFC 7541 ) を実装する

2024/01/03に公開

Scala

HTTP2

Scala 3

tech

About

HPACK は HTTP/2 で利用されるヘッダ圧縮方式である. RFC 7541 で仕様が定められている.

最近業務で使っている Rust と gRPC に関する記事を書いたのだが、gRPC のベースにある HTTP/2 について全然理解してない気がしてきたので色々と RFC を読んでみた.

HTTP/2 の RFC の中で RFC 7541 - HPACK: Header Compression for HTTP/2 は分量も少なくサンプルも充実していて、試しに実装してみるのにちょうどいい題材だったのでこれを Scala で実装してみた.

実装したコードの cloc . --vcs git の結果は以下の通り. コメント・空行やテストも含めて 1000 行未満.

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Scala                            7             43            242            968
Markdown                         1             21              0             42
-------------------------------------------------------------------------------
SUM:                             8             64            242           1010
-------------------------------------------------------------------------------

実装に当たっては Crystal の HTTP2::HPACK パッケージを大いに参考にした.
RFC に "Values are unsigned unless otherwise indicated" とあり　Java のプリミティブは全て Signed^[1] なので注意が必要だが(例えば、unsigned の時の十進数表現を得るには& 0xff する必要がある)、それ以外は素直に一対一にコードを移植することができる.

レポジトリはここにある.

https://github.com/i10416/hpack.git

Scala CLI Tips

ただ実装するだけではつまらないので Scala CLI の機能を色々と試してみた.

どこからともなく現れた Scala CLI や //> using コメントに読者が混乱しないよう、このセクションでは HPACK を実装するに当たって利用した Scala CLI の機能を紹介する.

Scala CLI に興味がない読者は HPACK のセクションまで読み飛ばしてほしい.

Scala CLI は簡単にいうと Scala の開発体験を良くするための CLI ツールである.

Scala コードのコンパイル、テスト、フォーマットやパッケージングなどの機能をコマンドラインからシュッと呼び出すことができる.

Rust における Cargo、Node.js における npm を想像してほしい.

複数ファイルへの分割とインポート

Scala CLI は一つのファイルだけでなく複数のファイルをまとめてコンパイルすることができる.
呼び出し側のモジュール(ファイル) に以下のように呼び出し先のモジュール(ファイル)のパスを書けば他のファイルの内容をインポートできる.

hpack.scala

//> using file "dynamic_table.scala"

ちょっとしたコードを書くには一つのファイルで十分だが、それなりにコード量が増える場合はファイルを分割した方が見通しがいい. 今回は以下のようにファイルを分割した.

.
├── README.md
├── dynamic_table.scala
├── hpack.scala
├── hpack.test.scala
├── huffman.scala
├── primitive_codecs.scala
├── static_table.scala
└── syntax.scala

テスト

Scala CLI ではテストを書いて実行することもできる.

以下のいずれかのルールに従えばソースコードをテスト用のファイルとして扱える.

ファイル名を *.test.scala にする
ソースディレクトリ以下でソースディレクトリへの相対パスに test を含む階層にファイルを配置する
- e.g. {src}/dir0/test/dir1/file.scala
//> using target.scope test を含む

今回は *.test.scala を利用した.

HPACK はファイルやネットワーク I/O を伴わない圧縮コーデックなので unit テストを充実させてテストで挙動を確認しながら開発を進めやすい.

テストは scala-cli test . で呼び出せる.

以下のように --test-only オプションやパターンを渡すことでパターンにマッチしたテストだけ実行することもできる.

scala-cli test . --test-only 'http2.hpack.*' -- '<pattern>'

ドキュメント

Scala CLI では doc コマンドを使って Scaladoc を生成することができる.

ドキュメントはソース中のコメントや -doc-root-content オプションで指定した Markdown ファイル、 -siteroot で指定したディレクトリに含まれる Markdown ファイルから生成することができる.
また、-snippet-compiler オプションを使うと、コメント内の Scala コードブロックのコンパイルが通るかチェックできる.

Scaladoc はデフォルトではpublic クラスやメソッドしかドキュメントに表示しないが -private オプションを付与すると private なクラスやメソッドもドキュメントに含めることができる.

プロジェクトのルートで以下のコマンドを打つと scala-doc ディレクトリにドキュメントが生成される.

scala-cli  doc --default-scaladoc-opts -f --scalac-option "-private" \
  --scalac-option "-doc-root-content:`pwd`/README.md" \
  --scalac-option "-project:hpack" .

cd scala-doc && python3 -m http.server などのコマンドで HTTP サーバーを立てれば localhost からドキュメントを閲覧できる.

the image showing the top page of generated document in the broweser

Scala 3 の Scaladoc は Markdown の見出し、リンクやコードブロックなどをサポートしている.

an image to demonstrate markdown reandering in scaladoc

HPACK

HPACK は以下のコンポーネントからなる.

既知の HTTP ヘッダのインデックスとヘッダーの値を管理するイミュータブルな Static table
受け取った値を FIFO の順序で追加・削除する有限サイズの Dynamic table
データのハフマン符号化・復号化
データのバイト列へのエンコード・バイト列からのデコード

このうち、状態をもつものは Dynamic table のみである. エンコーディング・デコーディングでそれぞれ独立したテーブルを持つ.

高頻度に送受信される既知の HTTP ヘッダの値の代わりに static table のインデックスを利用したり、dynamic table にヘッダをキャッシュしたりすることで送受信されるデータを圧縮している.

ハフマン符号化とは

よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている

アルゴリズムである.

オプショナルなハフマン符号化を利用することでデータによっては更なる圧縮が期待できる(がデータによってはハフマン符号化しても圧縮率がよくならないこともある)

データは整数または文字列で https://datatracker.ietf.org/doc/html/rfc7541#section-5 や https://datatracker.ietf.org/doc/html/rfc7541#section-5.2 で説明される形式でバイト列と相互に変換される.

Static table

インデックスアクセス可能な (String, String) のリスト. HPACK の論理的なインデックスは 1 はじまりなので配列のインデックスを HPACK で利用する際は +1 する.

Dynamic table

HTTP ヘッダをキャッシュする動的なテーブル. これもインデックスアクセス可能な (String, String) のリスト. HPACK における唯一の stateful なモジュール.
Index 空間で Static table の背後の連続した領域に配置される. 要するに Dynamic Table のi 番目 (dynamic_table[i]; i = 0,1,...) は index_space[STATIC_TABLE_SIZE + i + 1] として扱われる.

Dynamic table の最も新しい要素が内部のリストの先頭に、最も古い要素が内部のリストの末尾にくる. テーブルの容量が足りない場合は最も古い要素から順に削除される.

Huffman

ハフマン符号化・復号化を扱うモジュール. ハフマン符号化の出力は可変長なので 8 bits ぴったりにならないことがある. 余った bits は RFC で定義された EOS シンボルの最上位ビットで埋められる.

ハフマン符号のテーブルは rfc7541#appendix-B で定義されている.

Golang の HPACK ではハフマン符号のツリーを bit ごとではなく byte ごとの 256 文木で定義して最適化をしているらしい.

HPACK Codec

Codec は型でいうと Array[Byte] => Int | String や Int | String => Array[Byte].

HPACK で扱うプリミティブなデータ型には整数と文字列がある. エンコーディングは可変長だが octet 単位で行われる.

整数は octet の下位 N bitsにデータがおさまる場合のエンコーディングとおさまらない場合のエンコーディングが定義されている.

文字列のエンコーディングはハフマン符号化の有無のフラグがある. データの octet 長のうしろにデータ本体が続く.

ヘッダは rfc7541#section-6.2 で定義される複数の形式のうちのどれかでエンコードされる.

エンコード方式はデータの先頭のビットフラグにエンコードされている.

まとめ

以上のように Scala で HPACK を実装した. 細かい実装はリンク先のコードやコメントを参照されたし.
ナイーブな実装なのでコーナーケースのハンドリングやパフォーマンスチューニングの余地は無数にある.
HTTP/2 の RFC ときくと難しそうでちょっと身構えるが実際に中身を見て実装してみると 1000 行に満たないコードで実装できる. ここから実用的に使い物になる水準まで持っていくのは大変だが、普段使っている道具の中身を知る手段としてこういった簡易的な再実装は悪くないので、読者の皆さんもぜひ試してみてほしい.

Scala の文法 Tips

ここからは付録である. https://github.com/i10416/hpack.git を読む上で役立つ Scala の文法を紹介する.

パターンマッチのバックティック

既知の変数を使って変数にマッチする式、例えば case value if value == expected は以下のように書ける.

// define person, name and surname at once
val person @ (name, surname) = ("John", "Doe")
val people = Seq(("Hanako", "Suzuki"), person, ("Taro", "Yamada"))

// comparing by `==` operation
people.collectFirst {
  case (n, s) if n == name && s == surname => s"$n $s"
} //=> Some("John Doe")

// is the same as
people.collectFirst {
  case (`name`, `surname`) => s"${`name`} ${`surname`}"
} //=> Some("John Doe")

// but this is NOT the same!
people.collectFirst {
  case (name, surname) => s"$name $surname" 
} //=> Some("Hanako Suzuki")

参考

パターンマッチと　string interpolation

match のアームで s".... $value ..." の文字列補完の形式で文字列にマッチしつつ値を抽出することができる.


val person = "John Doe"

def doeFamily(person: String): Option[String] =
  person match
    case s"$name Doe" => Some(name)
    case _ => None

参考

変数名のバックティック

Identifier として使えない変数名もバックティックで括れば使える.

val `0b1000000`: Byte = 64

参考

Null

Scala 3 では、コンパイラフラグ -YExplicit-Nullsを有効化することで nullable な値と non-nullable な値を明確に区別することができる.

例えば、以下のコードは -YExplicit-Nulls 有効化時にはコンパイルエラーになる. なぜならば getBytes() の返り値の型は Array[Byte] | Null だから.

val strBytes = string.getBytes().size

絶対に null にならないことを示すには .nn を使う.

val strBytes = string.getBytes().nn.size

Array[Byte] | Null でお気づきのように Scala 3 では | オペレータを使ってユニオン型を定義できる. ちょっとしたラッパーを書けば T | Null 型に対して a.?.b.?.c.?.d というふうにオプショナルチェーンを呼び出すこともできる.

while・loop の break、continue や early return

while・loop の break、continue や early return のセマンティクスは再帰で書き換えることができる.

Crystal 版の実装ではここで for loop から return で抜け出している.

Scala でそのまま書き換えると return は foreach[U]: T => U の関数の返り値として扱われ呼び出し元の関数から抜け出すことはできない.

def indexed(name: String, value: String) =
  STATIC_TABLE.zipWithIndex.foreach:
    (header, index) =>
      ...
         return　//=> これは indexed から抜け出せない.

このような「繰り返し+継続または中断」のパターンは再帰で書き換えると元の動作やそれに近い動作を表現できる. 再帰で書くことで、ループによって変化する状態を意識せず、ある状態から次の状態への遷移だけを考えればよくなる.

さらに、末尾再帰のコードはコンパイラが while 文に変換してくれるため foreach の呼び出し + 関数の呼び出しと比べてパフォーマンス上の利点がある(微々たるものだが).

visibility

以下の private[hpack] は「bar メソッドは原則 private だが、http2.hpack パッケージ内からは参照できる」という意味になる.

package http2.hpack
object Foo:
  private[hpack] def bar = ???

これの何が嬉しいかというと、パッケージのユーザーやインテグレーションテストには公開したくないがパッケージの内部ではあちこちで呼び出したい&呼び出しても問題がないクラスやメソッドを定義できることにある.

Java 系の言語ではテストは同一パッケージに配置する慣習があるので、ちょっとしたユーティリティのユニットテストは書きたいがそのメソッドをパッケージのユーザーには公開したくない場合に便利である.

参考

脚注

Crystal 言語には unsigned なプリミティブがある ↩︎