Internet Infrastructure Review（IIR）Vol.52
2021年9月30日

3. フォーカス・リサーチ（2）

HaskellによるQUICの実装

IIJの目標の1つはインターネットの発展に貢献することであり、技術研究所は貢献方法の1つとして新しいプロトコルの標準化に参加しています。新しいプロトコルの仕様を議論し、その仕様を実装し、他の実装と相互接続性を検証することで、仕様の完成度を高めることに長年取り組んでいます。

2013年以降はHTTP/2とTLS 1.3の標準化に参加しました。最近の2年半は、この2つのプロトコルに関連が深いQUICやHTTP/3の標準化に関わりました。この記事では、QUICやHTTP/3をどのように実装したかについて説明します。

3.1 QUICとHTTP/3

QUICは、UDPを利用する新しいトランスポートプロトコルです。以下の機能を取り込む大きな仕様として定義されています。

• TCPが提供する信頼性、フロー制御、及び輻輳制御
• HTTP/2由来の非同期ストリームによる多重化 （ストリームの分割と再構成）
• TLS 1.3が提供するセキュリティ機能（鍵交換や通信相手の認証、通信の暗号化）

QUICの基本単位は「パケット」と呼ばれます。パケットには、「フレーム」と呼ばれる単位のデータを複数格納できます。フレームにはいくつかの種類があり、例えばアプリケーションのデータは、STREAMフレームに収められます。ACK（確認応答） の情報は、ACKフレームに格納されます。QUIC上に定義されたHTTPが、HTTP/3と呼ばれています。

3.2 Haskellで実装する理由

QUIC及びHTTP/3は、これまでに実装したHTTP/2やTLS 1.3 と同様に、プログラミング言語Haskellで実装しています。我々がHaskellを選んだ理由は以下のとおりです。

• 豊かなデータ型で問題を簡潔に表現でき、強い型検査でコードの誤りの多くを検出可能
• 軽量スレッドが標準で提供されているおかげで、状態管理が煩雑になりがちなイベント駆動プログラミングよりも見通しが良く、なおかつスレッドを切り替えたり生成したりする際のオーバーヘッドが少ないスレッドプログラミングが可能（以下、単にスレッドと言えば、軽量スレッドを意味する）
• 多くのデータ型が不変であり、安全にスレッド間で共有できる
• STM（Software Transactional Memory）が標準で提供されており、デッドロックのないスレッドプログラミングが可能

我々以外のチームが手がけるQUICの多くの実装では、イベント駆動プログラミングを採用しています。これに対して我々はスレッドプログラミングを採用しています。スレッドプログラミングを採用することでプログラムの見通しが良くなるだけでなく、他の実装者とは違う観点で仕様を検証できると考えています。

以下、具体的な実装のポイントについて説明します。

3.3 QUICのストリームとコネクション

QUICは、1つのコネクションの中で通信を多重化するために通信を「ストリーム」という単位で分割します。HTTP/2においても同様の目的で「ストリーム」を用いますが、HTTP/2のストリームがHTTPの要求と応答しか運べない一方、QUICのストリームはどのようなアプリケーションのデータでも運搬できます。

QUIC用のAPIを長期に渡って考案した結果、以下のような抽象化を発見しました。

• QUICのコネクションの役割は、OSが担っているネットワーク入出力管理に相当する
• QUICのストリームは、TCPコネクションに相当する

ここでのTCPコネクションは、HTTP/1.0のように、コンテンツを1つだけやり取りする最も単純な利用形態のTCPコネクションを意味しています。このように考えると、ストリームはソケットAPIを模倣したAPIで操作できることに気付きました。現時点でのAPIの一部を以下に示します。

このようにHaskellの型注釈は、型を右矢印で区切った形で表現されます。一番右に返り値の型を書きます。それ以外は引数の型です。型の左横にIOが付くと、入出力など副作用を伴うという意味です。付いていなければ副作用がない不変データ型です。()は返り値がない型、ByteStringはバイト列の型です。よって、IO ()は返り値には意味がなく、副作用だけに興味がある型です。

HaskellでHTTP/1.0サーバを実装する際は、クライアントからのTCPコネクション1つにつき、1つのスレッドを起動し、要求を読んで応答を書き込み、スレッドを終了させる同期的な手法が常套手段です。HTTP/2では、多重化を実現するために、複数のスレッドを管理する必要がありました。HTTP/3を実現する際は、この多重化はQUICライブラリが担います。そのため、前述のAPIを用いると、1つのストリームにつき、1つのスレッドを起動する同期的な常套手段の利用が可能となりました。

3.4 サーバでのコネクションの受け付け

サーバを起動する関数の型注釈は、以下のとおりです。

すなわちrunは、サーバの設定とサーバアプリケーション関数（コネクションを受け取って入出力を含む何らかの処理をする関数）を引数に取ります。この関数で起動されるDispatcherスレッドは、ネットワークインタフェースごとに待ち受け（ワイルドカード）ソケットを開きます。新しいコネクションを受け付けると、コネクションを構成するスレッド群を起動します（3.5節参照）。

QUICパケットは6種類あります。Initialパケット、0-RTTパケット、Handshakeパケット、及び1-RTTパケットは本文が暗号化され、ヘッダも保護されます。Version NegotiationパケットとRetryパケットは、本文の暗号化やヘッダの保護が施されません。これらのパケットを統一的に解析するために、解析を2段階に分ける方法を考案しました。

1. （1）ヘッダ保護で守られていないヘッダ領域の構文解析（パケットの種類の判別など）
2. （2）暗号化されている本文の復号とヘッダ保護の除去

（1）はDispatcherスレッドで実行されます。Dispatcherスレッドは、（1）の解析結果を見て、Initialパケットであれば新しいコネクションを作成し、適切な1-RTTパケットであればマイグレーション処理を実施します（3.9節参照）。また、Version NegotiationパケットやRetryパケットをサーバが受け取ることは仕様上不正なので、その場合は単に破棄します。

（1）は後述のReaderスレッドでも実行され、（2）は後述のReceiverスレッドで実施されます。この2段階の解析というアイディアにより、ヘッダ情報のデータ構造が共通化され、それ以前の実装に比べてコードが簡潔になりました。

3.5 コネクションを構成するスレッド群

Dispatcherスレッドが新しいコネクションを作成する際は、そのコネクションのメインとなるスレッドを起動し、作成を依頼します。メインのスレッドは、図-1に示すようなコネクションを構成するスレッド群を起動し、終了を待ちます。

拡大する

図-1 コネクションを構成するスレッド群

コネクションの生成時には、接続済みソケットが生成されます。そのため、このコネクションに関係するパケットは、Dispatcherスレッドではなく、Readerスレッドが読み込むようになります。Readerは前述のパケット解析（1）を実行し、解析できたヘッダ情報、保護されたヘッダ、及び暗号化された本文を、キュー（RecvQ）を通じてReceiverスレッドに渡します。

Receiverスレッドは、前述の（2）を実行し、パケット中のフレーム群を取り出し、それぞれを処理します。STREAM フレームに関しては、再構成をして、キュー（InputQ）を通じてServerスレッドに渡します。また、ACKフレームを受け取ると、3.10節で述べる再送情報コンテナ（SentPackets）から対応する情報を削除します。

Serverスレッドは、サーバアプリケーション関数を起動するスレッドです。出力は、キュー（OutputQ）を通じてSenderスレッドに送られます。Serverスレッドは、アプリケーションを起動する前に、TLS handshakerスレッドを起動し鍵交換を実行させると共に、鍵が利用可能なタイミングの同期を取る役割も果たします。

Senderスレッドは、Serverスレッドからの出力を分割してSTREAMフレームに格納し、QUICパケットを構成します。そして、パケットの本文を暗号化し、ヘッダを保護して、最終的なUDPデータグラムを生成し、接続済みのソケットを通じて出力します。また、QUICパケットに含まれた情報を再送情報コンテナに格納します。

Resenderスレッドは、パケットのロスを検知すると、再送情報コンテナから関連する情報を取り出し、OutputQに入れることで再送します。

キューやその他のデータの共有にはSTMを活用しており、これらのスレッドはデッドロックを起こすことはありません。また、どれか1つのスレッドが致命的なエラーを起こすと、スレッド群全体が消滅します。この際、リソースは正しく解放され、リークは起こりません。

3.6 接続済みソケット

TCPではaccept()システムコールを利用すれば、ワイルドカードソケットから、接続済みソケットを生成できます。しかしながら、accept()システムコールはUDPに対しては使用できません。

例えば、サーバにワイルドカードソケット{UDP, 192.0.2.1, 443, *, *}が存在し、203.0.113.1:3456のクライアントから接続要求があったとしましょう。生成したい接続済みソケットは{UDP, 192.0.2.1, 443, 203.0.113.1, 3456} です。素朴な方法としては、以下が考えられます。

1. （1）新しいUDPソケットを開き、SO_REUSEADDRオプションを設定する
2. （2）192.0.2.1:443を指定してbind()システムコールを呼ぶ
3. （3）203.0.113.1:3456を指定してconnect()システムコールを呼ぶ

残念ながらBSD系OSでは、（2）でエラーを起こします。Linuxは（2）を受け付けますが、レースコンディションが発生すると思われます。これらの問題を解決する方法は、以下のとおりです。

1. （1）新しいUDPソケットを開き、SO_REUSEADDRオプションを設定する
2. （2）*:443を指定してbind()システムコールを呼ぶ
3. （3）203.0.113.1:3456を指定してconnect()システムコールを呼ぶ。この際、ローカルアドレスが192.0.2.1に設定される

この方法は、多くのOSで問題なく動作し、レースコンディションも発生しません。ただし、特権の扱いには注意する必要があります。TCPで、root特権を保有しているプロセスが特権ポートに対するワイルドカードソケットを生成したとしましょう。このプロセスがセキュリティ上の理由からroot特権を手放したとしても、accept()システムコールは問題なく実行できます。しかし、上記の方法でUDP接続済みソケットを生成する際には、Linuxでは最低限CAP_NET_BIND_SERVICEケーパビリティが必要です。

3.7 コネクションの消去

ソケットAPIでTCPを利用している場合、アプリケーションがclose()システムコールを呼んだ際は、制御は直ちにアプリケーションに戻され、以降のTCPの終了処理はOSが担います。QUICの実装でも、このような制御を可能にすべきでしょう。

我々の実装では、サーバ（あるいはクライアント）アプリケーション関数が終了する際は、メインのスレッドを除いた他のスレッド群は終了し、不要な情報は破棄されます。また、CONNECTION_CLOSEフレームを再送するための最小限の情報と共に、終了処理用の別スレッドがメインのスレッドから起動されます。

QUICでは、CONNECTION_CLOSEフレームを含むパケットには、ACKが返ってきません。通信相手がCONNECTION_ CLOSEフレームを受け取ったなら、直ちにあらゆるパケットの送信を停止します。そこで、CONNECTION_CLOSEフレームを送った後は、一定期間待ち、相手からのパケットが届かなくなることを確かめます。届く場合は、CONNECTION_CLOSE フレームが紛失したと考えられるので、CONNECTION_ CLOSEフレームを含むパケットを再送します。

3.8 TLSハンドシェイク

QUICでは、TLS 1.3を利用してハンドシェイクを実行し、通信相手を認証したり、鍵を交換したりします。TLS 1.3のメッセージは、TLSのレコード層から切り離され、単なるデータ書式として、CRYPTOフレームに格納されます。

これらを受け取ったクライアントは、Handshake鍵と1-RTT 鍵を生成します。また、生成したFinishedをHandshakeパケットに格納し、Handshake鍵で暗号化して送信します。この時点で、アプリケーションデータを格納できる1-RTTパケットが送信可能になります。

2回目のコネクションの場合、クライアントは保存している情報から0-RTT鍵を生成し、Initialパケットの後に、アプリケーションデータを格納できる0-RTTパケットを0-RTT鍵で暗号化して送信できます。

TLS 1.3の機能をQUICで利用可能とするために、TLSライブラリの拡張を様々な方法で試みました。レコード層を分離するためには大改造が必要でしたが、それ以上の改造をせずにTLS ライブラリを再利用するには、TLS専用のスレッドを起動する方法が適切だと分かりました。

Client/ServerスレッドでTLS 1.3の状態を管理しなくて済むよう、TLSライブラリ内に状態を閉じ込めるには、コールバック方式が有効でした。鍵を生成すると、指定されたコールバックを用いて、共有データに鍵をインストールします。また、STMを利用することで、鍵がインストールされたタイミングを他のスレッドが測れるようにしました。

サーバ側のTLS handshakerスレッドは、NewSessionTicket メッセージを1-RTTパケットで送信したあとに終了します。一方、クライアント側のTLS handshakerスレッドは、HANDSHAKE_DONEフレームを受け取った後、一定時間後に終了します。

3.9 マイグレーション

クライアント側のIPアドレスやポート番号が変更されることがあります。例えばネットワークインタフェースを携帯電話からWi-Fiに切り替えたり、途中にあるNATがポートの対応表を変更したりした際に起こります。このような場合でも、コネクションを継続させる機能がコネクションマイグレーションです。

クライアント側のIPアドレスやポート番号が変更されると、我々の実装のサーバ側では待ち受けソケットに1-RTTパケットが届くようになります。コネクションIDを調べると、不正なパケットではなく、マイグレーションが起こったと判断できます。

ここで、クライアント側でのマイグレーションの方法を考察します。まず、接続済みソケットを使う場合です。

1. （1）何らかの方法で、優先させる新しいネットワークインタフェースが利用可能になったことを検知する
2. （2）マイグレーションのAPIを呼ぶ。新しいソケットが生成され、connect()システムコールが呼ばれると、OSはリモートのアドレスとポートを引数から設定する。そして、経路表をリモートのアドレスで検索し、経路が向いているネットワークインタフェースを得る。そのネットワークインタフェースのIPアドレスが、ソケットのローカルアドレスに選ばれる。ローカルポートは、乱数的に選ばれる
3. （3）作成した接続済みソケットとsend()を使ってパケットを送信する

この方法の利点は（2）でパス検証を実施できること、欠点は（1）を実施するためにはOS固有の手法を使わなければならないことです。一方、ワイルドカードソケットを利用する方法も考えられます。

• sendto()が呼ばれると、OSは引数からリモートのアドレスとポートを設定する。また、経路表をリモートのアドレスで検索し、経路が向いているネットワークインタフェースを得る。そのネットワークインタフェースのIP アドレスが、ソケットのローカルアドレスに選ばれる。ローカルポートは、最初にsendto()が呼ばれた際に、乱数的に選択される

この方法の利点は、優先されるネットワークインタフェースを見張る必要もなければ、特別なマイグレーションのAPIを用意する必要もなく、マイグレーションが自動的に実施されることです。欠点は、パケットの送信にコストがかかって性能が悪くなること、パス検証をするタイミングがないことです。どちらの方法にも一長一短があります。そこで、両方の方法を提供し、クライアントを起動する際の設定で選択できるようにする予定です。

3.10 ACK処理のアルゴリズム

QUICでは再送の際に新しいパケット番号が使われます。再送の際にシーケンス番号を再利用するTCPと違って、QUICにはACK の曖昧さの問題が存在しません。再送の際には、パケット番号や暗号文も変わります。そのためRFC9000では、単純なパケットの再送ではなく「情報の再送である」と表現されています。

標準的なTCPでは、ACKは次に届くべきシーケンス番号を指定するので、その他のTCPセグメントが通信相手に届いているか判定できません。一方で、QUICのACKフレームには、受信したパケット番号を列挙できます。

送信したパケットの情報を再送できるようにするには、再送情報コンテナを用意して、送信時に情報を蓄えます。再送情報コンテナの操作は、以下の3つが考えられます。

• 送信時に、パケット番号をキーとして、情報を挿入し保存する
• ACKの受信時に、パケット番号をキーとして、情報を削除する
• 一定期間ACKが返らない場合、情報を削除して取り出し、それぞれを再送する

このような操作が提供されているデータ構造で、Haskellで一般的なのは、PSQ（Priority Search Queue）です。キーとしてパケット番号、プライオリティとして送信時間、そして値として情報を指定します。

再送情報コンテナをPSQで実装したところ、性能が著しく悪くなる場合があることに気付きました。通常の実装では、ACKを例えば以下のように返します。

すなわち、ACKに対するACKを処理して、ACKを返すべきパケット番号を動的に管理します。一方で、一時のFirefox Nightlyは以下のようなACKを返していました。

ACKに対するACKを処理しないので、不要になったパケット番号が削除されません。この形態は、仕様では許されています。PSQの大きさをn、ACKに指定されたパケット番号の数をmとすると、全体の削除操作の計算量はO（m log n）です。Firefox Nightlyのようにmが巨大になると、削除操作は極めて高価になります。

この問題を解決するために、述語（predicate）を活用する方法を思いつきました。例えば、[4,5,7,8,9]というパケット番号群は、ACKフレームの中では[(4,5),(7,9)]のように範囲で指定されます。この範囲を以下のような述語に変換します。

Haskellには、双方向リストのように両端の操作がやりやすいデータ構造であるFinger Treeが標準で提供されています。このFinger Treeには、述語に合致する要素のみを含むFinger Treeと、合致しない要素のみを格納するFinger Tree とに分割する操作があり、その計算量はO（n）です。そこで、PSQの代わりにFinger Treeと述語による分割を組み合わせることで、ACKを受信した際の操作の計算量を低減することに成功しました。

3.11 ストリームの再構成

QUICパケットは、複数のIPパケットに跨りません。すなわち、IPレベルにおいて分割されたり、再構成されたりしません。一方で、ストリームのデータは複数のQUICパケットに跨ります。そのため、送信側ではストリームのデータを適切な大きさに分割し、受信側では再構成する必要があります。

STREAMフレームが到着した際は、その断片を再構成用のコンテナに挿入します。そして、期待しているオフセットから始まる連続した断片群が存在するなら、それらを取り出してrecvStreamのキューに入れます。このように、再構成用のコンテナの操作には、挿入と取り出し削除があります。

我々の古い実装では、再構成用のコンテナに一方向リストを利用していました。挿入と取り出し削除の計算量は、それぞれO（n）とO（n）です。実践環境での通信のプロファイルを取ると、ストリームの再構成がボトルネックとなっていました。

そこで、再構成用のコンテナのデータ構造として、前述のFinger Treeを要素としたねじれヒープを採用しました。Finger Tree は、先頭にも末尾にも要素をO（1）で追加でき、連続した断片群を表現します。挿入と取り出し削除の計算量は、それぞれO（log n）とO（n）となり、計算量を低減できました。

3.12 フロー制御

フロー制御とは、受信者が受信できる範囲で、送信者がパケットを送信する仕組みです。QUICでは、受信できるデータ量（クレジット）を送信者に伝える方式を採用しています。3.13節で述べる輻輳制御と同一視されがちですが、別々の仕組みです。

我々の実装では、ストリームAPIのレベルでフロー制御を実現しています。

• sendStreamは、通信相手が許す範囲でデータを送り、超える場合は、通信相手からのクレジットを待ちます
• recvStreamは、アプリケーションがこのデータを消費すると考え、受信したデータ分のクレジットを通信相手へ送ります

3.13 ロス検知と輻輳制御

QUICのロス検知と輻輳制御は、RFC9002（注2）で定義されています。ロス検知は、ACKに基づく方法とprobeタイムアウトに基づく方法の両方を活用します。また、輻輳制御にはNewRenoに基づくアルゴリズムを採用しています。我々は、掲載されている疑似コードを忠実にHaskellで実装しました。その過程で、仕様の不整合をいくつか発見し報告しました。この貢献が認められて、この記事の筆者である山本の名前が、RFC9002の貢献者リストに掲載されました。

ロス検知と輻輳制御に関しては、qlog形式（注3）で書き出したログをビジュアライザーであるqvis（注4）で可視化し、動作を確認したり、間違いを発見したりしました。

3.14 テスト

我々のQUICライブラリやHTTP/3ライブラリでは、様々な単体テストを実装しています。この節では、特筆すべき単体テストと外部テストの利用に関して説明します。

ロス検知

ロス検知が正しく動くかテストするために、中継スレッドを通じてUDPデータグラムを中継する仮想ネットワークを実装しました。中継スレッドは与えられたシナリオを元に、UDPデータグラムを落とします。乱数的にUDPデータグラムを落とすテストはもちろん実装しています。また、クライアントの第1 パケットを落とすテスト、第2パケットを落とすテストのように、問題を起こしやすいハンドシェイクのパケットロスに対して、すべてのパターンを網羅しています。

h3spec

テスト項目で漏れがちなのが、エラーケースです。HTTP/2 の場合、エラーケースをサーバに対してテストする優れたツールh2spec（注5）が存在します。我々は、HaskellのQUICライブラリにフックを用意すれば、簡単にエラーケースに対するテストを実現できることに気付きました。以下にフックの一部を示します。

このフックはトランスポートパラメータが生成された際に、その値から別の値へ変換します。エラーとなる値へ変換することで、エラーケースを作成できます。このアイディアに基づいて、QUICあるいはHTTP/3サーバに対してエラーケースをテストするh3spec（注6）というツールをリリースしました。現時点では、QUICのエラーテストを32項目、HTTP/3のエラーテストを16項目提供しています。h3specは、HaskellのQUICライブラリに対してはもちろん、他の実装のテストにも利用され、実装を安定化させることに役立ちました。

QUIC tracker

QUIC trackerは、公開サーバに対して様々なテストを1日1回実行し、その結果を公開するサービスです。我々の公開サーバも登録していただき、たくさんのバグを発見できました。最終的には、対応していない2項目を除いたすべてのテストケースでパスするようになりました。

3.15 謝辞

接続済みソケットの生成方法のアイディアは、奥一穂さんからいただきました。また、マイグレーションのAPIに関しては、Tatsuhiro Tsujikawaさんに議論していただきました。Robin Marxさんにはqlogやqvisに関して様々なことを教えていただきました。ここに名前を記して感謝します。

1. （注1）参考文献 J. Iyengar, M. Thomson, "QUIC:A UDP-Based Multiplexed and Secure T ransport", RFC9000, 2021
2. （注2）参考文献 J. Iyengar, I. Swett, "QUIC Loss Detection and Congestion Control", RFC9002, 2021
3. （注3）参考文献 R. Marx, "QUIC and HTTP/3 event definitions for qlog", Internet -Draft, 2020
4. （注4）qvis、"Welcome to qvis v0.1, the QUIC and HTTP/3 visualization toolsu ite!"（https://qvis.quictools.info/）。
5. （注5）h2spec、"A conformance testing tool for HTTP/2 implementation"（https://github.com/summerwind/h2spec）。
6. （注6）h3spec、"Test tool for error cases of QUIC and HTTP/3"（https://github.com/kazu-yamamoto/h3spec）。

3. フォーカス・リサーチ（2） HaskellによるQUICの実装

• 3.1 QUICとHTTP/3
• 3.2 Haskellで実装する理由
• 3.3 QUICのストリームとコネクション
• 3.4 サーバでのコネクションの受け付け
• 3.5 コネクションを構成するスレッド群
• 3.6 接続済みソケット
• 3.7 コネクションの消去
• 3.8 TLSハンドシェイク
• 3.9 マイグレーション
• 3.10 ACK処理のアルゴリズム
• 3.11 ストリームの再構成
• 3.12 フロー制御
• 3.13 ロス検知と輻輳制御
• 3.14 テスト
• 3.15 謝辞