GoogleのQUICの論文が知見の塊だった

雑 QUIC

20181107追記 QUICプロトコルについての概要は別途記事を書きました
asnokaze.hatenablog.com

概要

ACM SIGCOMM 2017という通信系の学会に、Googleの人 総勢21人によって書かれた「The QUIC Transport Protocol: Design and Internet-Scale Deployment」という論文が提出され、学会ホームページより閲覧出来る。

この論文は、QUICの設計仕様と実際にGoogleのサービスにデプロイした結果について書かれている。

すでにGoogler SearchやYoutubeでQUICは有効になっており、一日あたり数十億の接続を処理し、Googleのegress trafficのうち30%がQUICになっており、インターネットのトラフィックの内7%がQUICだと推定されるという説明から論文は始まる。

QUICはGoogle Searchのレイテンシをデスクトップユーザでは8%, モバイルユーザでは3%削減しており。Youtubeのリバッファリングをデスクトップで18%、モバイルで15%削減したようである。

QUICの設計、機能の説明とデプロイ結果からパフォーマンスについて詳細に書かれている。

特に7章の知見については面白かったので簡単に読んだことをまとめた。

雑であしからず

全体構成

  • 1.INTRODUCTION
  • 2.MOTIVATION: WHY QUIC?
  • 3.QUIC DESIGN AND IMPLEMENTATION
  • 4.EXPERIMENTATION FRAMEWORK
  • 5.INTERNET-SCALE DEPLOYMENT
  • 6.QUIC PERFORMANCE
  • 7.EXPERIMENTS AND EXPERIENCES
  • 8.RELATED WORK

個人的に面白いと思ったのは、3章、6章、7章である。

3.QUIC DESIGN AND IMPLEMENTATION

3章の「QUIC DESIGN AND IMPLEMENTATION」はQUICの基本的な機能とその仕組について書かれている。

  • Connection Establishment
  • Stream Multiplexing
  • Authentication and Encryption
  • Loss Recovery
  • Flow Control
  • Congestion Control
  • NAT Rebinding and Connection Migration
  • QUIC Discovery for HTTPS

6.QUIC PERFORMANCE

6章の「QUIC PERFORMANCE」が、今回のメインであるパフォーマンス測定に関する章である。
TLS/TCPとQUICのハンドシェイク遅延の比較、Google Search及びYoutubeのレイテンシの比較、South Korea・USA・India地域ごとの性能比較、サーバ側のCPU使用率の話

7.EXPERIMENTS AND EXPERIENCES

7章の「EXPERIMENTS AND EXPERIENCES」は直接QUICと関係ないが実験より得られた知見が書かれている。
個人的には非常に面白かったので、幾つかピックアップ。FECについては、以前書いたので割愛。

asnokaze.hatenablog.com

Packet Size Considerations

プロジェクトの初期に、UDPパケットの最大サイズを決定するための調査が行われていました。
2014年にネットワーク上のエコーサーバに向けて、UDPペイロードを1200バイトから1500バイトまで5バイトおきに接続性のテストを行っていたようです。

f:id:ASnoKaze:20170813015054p:plain
(引用: 7.1節 図12)

接続の失敗は、1450バイト後に急増しておりQUICでは1350バイトが選択された。

UDP Blockage and Throttling

UDPの疎通性に関して、2016年にビデオ再生に関するメトリックスで

  • 95.3% が問題なく使用できた
  • 4%が、UDPがブロックされるか経路のMTUが小さすぎて使用できなかった。これは企業内のファイアウォールケースが多いようです。
  • 残りの0.3はUDPのトラフィックが制限されており、トラフィックが高い場合はパケット損失率が大幅に上がるようです。ASレベルの制限は減少傾向にあるようです。
User-space Development

QUICはユーザスペースで処理されます。このメリットについて書かれています。

ユーザランドで開発することで、カーネルでは制限されているような機能でもロギングが可能で様々なバグの発見に役立ったようです。

Cubicをユーザランドで再実装することによってLinuxにあった古くからあったcubicの実装にバグを見つけたのはニュースにもなりました。
news.mynavi.jp

また、カーネルに組み込むよりもユーザに早く更新を届ける事が出来た旨も書かれています。これはセキュリティプロトコルにとっては非常に重要なことです。

Experiences with Middleboxes

ファイアウォールといった中間装置の振る舞いについて

QUICでは殆どのデータを暗号化していますが、一部は暗号化されていません。2016年10月にその暗号化されてない部分の1bitの変更を加えたところ、一部のファイアウォールが混乱し最初のパケットのみを疎通させその後はブロックするような振る舞いをするようになりました。その場合、TCPに正常にフォールバックされません。

フラグ部分をもとに戻すことで対応するとともに、ファイアウォールベンダーを特定し連絡を取りフラグの分類について更新することで問題は解決されたようです。

その時はベンダーを特定し対応できたが、インターネット上で特定のビットがファイアウォールにどのように影響するか答えることはできません。

これはファイアウォールの影響を避けるために殆どの領域を暗号化するQUICの設計の前提を強めた形になります。

ジオロケーションを要求・送信する HTTP Geolocationヘッダの提案仕様

HTTP internet-draft

GoogleのLuis Barguno Jane氏より、HTTPヘッダでジオロケーション情報の要求・送信を可能にする「Geolocation Header for HTTP over a Secure Context」という仕様が出ています。

背景

ユーザエージェントにおいてジオロケーションの取得は「Geolocation API」で取得可能でした。

しかし、この方法はHTMLを読み込んで、JavaScriptを実行して、サーバに送信する流れになります。サーバは、最初に読み込まれるHTMLを生成時はどうしても位置情報が使えないという事情があります。

また、スマートでバイスやIoT機器でJavaScriptの実行をサポートしてない環境においては、ジオロケーションの要求・送信に仕様はないのが現状です。

Secure Contexts下でジオロケーションの要求・送信が出来る仕組みを定義したのがこの仕様です。

HTTPレスポンスでGeolocation-Requestヘッダを受け取ったクライアントは、次回から指定されたPathにアクセスした時はGeolocationヘッダでジオロケーションを送信するようになります。

example

Geolocation-Requestヘッダ

サーバから、HTTPレスポンスにおいてジオロケーションを要求するGeolocation-Requestヘッダ

Geolocation-Request: Path="/localService"; Type=IfAlreadyGranted;
       Expires=Thu, 18 Dec 2017 12:00:00 UTC

(#本当は1行)

  • Path: ジオロケーションを送信するスコープとなるPath
  • Type:
    • IfAlreadyGranted: 既にそのオリジンにおいて、ジオロケーションの取得が許可されていた場合のみジオロケーションを送信する
    • MayPrompt: ジオロケーション取得のパーミッション要求プロンプトを表示してもよい(ユーザエージェント次第)
  • Expires: 有効期限
Geolocationヘッダ

クライアントから、HTTPリクエストにおいてジオロケーションを送信するGeolocationヘッダ

Geolocation: Position=[47.368684, 8.535741, 345]; Accuracy=10;
         Timestamp=1495804846156; AltitudeAccuracy=20; Speed=1.5;
         Heading=27.53;

(#本当は1行)

  • Position:RFC7946 GeoJSON形式の位置情報 (必須)
  • Accuracy: メートル単位の精度 (必須)
  • Timestamp: 取得時のタイムスタンプ (必須)
  • AltitudeAccuracy: メートル単位の高度精度
  • Speed: 速度(m/sec)
  • Heading: 方位(0～360)

QUICにおけるヘッダ圧縮の提案仕様 QPACK(旧QCRAM)

internet-draft QUIC

20190408追記
最新版について記事を書きました
asnokaze.hatenablog.com

QUICとヘッダ圧縮

HTTP over QUICの仕様は現状、HTTP/2と同様HPACK(RFC 7541)を利用してHTTPヘッダの圧縮を行う。

HPACKはHTTP/2を想定としており、トランスポートはTCPであり順番通りにパケットが届く想定の仕様となっている。具体的には、動的テーブルにおいてエントリーの追加やそれに伴う暗黙的なエントリのエヴィクションが発生してもエンコーダ側とデコーダ側で状態が同期できるのがHPACKである。

QUICはUDPを使うとともに、同一のストリーム上でのみデータの順番が保証される仕組みになっている。これによってパケットロスが他のストリームをブロックすることがなくなるというメリットがあるが、前述の通りHPACKを使っている限りヘッダのデコードは順番通りにしか処理が出来ない。結局としてパケットロスがHTTPヘッダのデコード部分についてはブロックする可能性が出てくる。

QUICの標準化を行っているIETFのQUIC WGでは、HTTP over QUICで使用する新しいヘッダ圧縮の方式が議論されている。
現在案は2つある

  • QPCAK: HPACKのワイヤフォーマット自体変更する
  • QCRAM: HPACKのワイヤフォーマットを維持する

QPACKについては、以前ブログに書いたとおりです(仕様はブログを書いてから更新されているため注意)
asnokaze.hatenablog.com

今回はQCRAMについて説明する

QCRAM

QCRAMは「Header Compression for HTTP over QUIC」という仕様であり、QPACKと区別してQCRAMと呼ばれる。仕様の著者はGoogleのCharles 'Buck' Krasic氏である。

QCRAMではHPACKのワイヤフォーマットにプレフィックスを付ける形で、動的テーブルの参照におけるヘッドオブラインブロッキングを緩和する。

順番が保証されない状態で、HPACKの動的テーブルを使うときの問題点は主に2つある

  • Insertion Pointよりエントリが挿入されることで、その他のエントリも index値 が変化する
  • エントリが挿入されることによって、テーブル上限に達した場合は Dropping Point より古いエントリが削除される
           <----------  Index Address Space ---------->
           <-- Static  Table -->  <-- Dynamic Table -->
           +---+-----------+---+  +---+-----------+---+
           | 1 |    ...    | s |  |s+1|    ...    |s+k|
           +---+-----------+---+  +---+-----------+---+
                                  ^                   |
                                  |                   V
                           Insertion Point      Dropping Point

https://tools.ietf.org/html/rfc7541#section-2.3.3


QCRAMではHEADERSフレームとPUSH_PROMISEフレームにおけるHPACK形式で表現されるヘッダブロックに以下のprefixを追加します

       0 1 2 3 4 5 6 7
      +-+-+-+-+-+-+-+-+
      |Fill       (8+)|
      +---------------+
      |Evictions  (8+)|
      +---------------+
  • Fill: 現在の動的テーブルのエントリー数
  • Evictions: エヴィクション回数

それぞれHPACKにおける整数表現が使用されます。また両方を足すと今まで挿入したエントリ数となります。

f:id:ASnoKaze:20170805204704p:plain

このprefixを使えば、挿入によってindex値がずれていたとしてもEvictionsとFillの情報から指し示しているindexが求められます。指し示すindex値がすでに到着して入ればそれを使用します。そのindex値が指し示すエントリがまだ挿入されていなければ待つことになります。

また、エヴィクションに関してもエンコーダが明示的にエヴィクションされた回数を送ってくるので、デコーダ側は自身のエヴィクション回数と比べて多ければエヴィクション出来ることになります。（保持する上限は別途実装依存となる）

その他

QCRAMの仕様はprefixの仕組みが大きいがそれ以外にも幾つかの支持がある。
例えば、QUICレイヤのAckをHTTPレイヤに伝えることで、相手に届いたことを確認してからそのindexを使うように進めている。また、動的テーブル上のエントリを再登録するIndexed Header Field with Duplicationなどの定義が与えられている。

minqを弄って memcached over quic を簡単に実装してみる

QUIC 雑

IETF QUIC

QUICの標準化がIETFで進められています。

QUICといえば既にChromeとGoogleのサービスで使用されていますが、そちらはGoogle QUICであり、IETFで標準化されているものとは微妙に異なっています。

IETF QUICの方は仕様の策定の議論が重ねられるとともに、7月に行われたIETF99で幾つかの実装が持ち寄られ相互接続テストが行われている状況です。しかし、「First Implementation」に書かれている通り1-RTTのハンドシェイクにフォーカスした相互接続テストであり、HTTPマッピング, 0-RTT, Key Updateなどといった多くの機能は今回のテストの対象外でした。

現在は引き続き仕様の議論を続けるとともに、10月に行われるQUIC WGの中間会議で行われるであろう次回の接続テストに向けてテスト項目( Second Implementation Draft)の議論が行われています。

相互通信テストでは上に乗っけるプロトコルがまだ決定しておりません。
QUIC WGの一旦の目標はHTTP over QUICが目標ですが、相互通信テストではもっと簡単なプロトコルが選ばれるかもしれません。
また、DNS over QUICなども別途仕様の方は議論されています。

既存実装

既存の実装としては、QUIC WGのWikiにまとめれています。

versionにdraftと書かれているものがIETF版 QUICで、Q035などのバージョンのものはGoogle QUICの実装になります。

IETF QUICの実装の実装状況は、まだまだマチマチな状況ですが概ね「First Implementation」相当のものかと思われます。

minqを弄ってみる

IETF QUICのGo実装の一つに ekr 氏の minqがあります (ekr氏は、TLS1.3の仕様のauthorでもあります)
github.com

今回は、minqのbin以下のclient/main.go と server/main.goを弄って雑に memcached over quic ぽいものを作ってみました
(意味があるかは別として)

github.com
(中身は本当に簡易です)

minq側のREADME.mdの通り一旦セットアップして、
serverを起動してから、clientで接続しに行くと、telnetと同じ要領でsetとgetを叩くとこんな感じです
(stream 1で通信されます。同一ストリームなので順番は保証されます)

$go run ./server.go > null &

$ go run ./client.go
State changed to  3
State changed to  5
Connection established
set hoge 0 0 4
test
STORED

$ go run ./client.go
State changed to  3
State changed to  5
Connection established
get hoge
VALUE hoge 0 4
test
END

今回はお遊びですが実装が進んだらまた何かプロトコルを乗っけてみたいなと思いました。

Chromeがシマンテックの古い証明書を信頼しなくなる今後のスケジュール(2017/09/13更新)

雑

2017/09/13 更新

Googleのブログで公式アナウンスが出ました。
一部対応者の表記がDigiCertになりましたが、大きなスケジュール変更はありません
security.googleblog.com


今年の上旬より、Chromeが古いシマンテックの証明書を失効扱いするニュースが世間を賑わせたのは記憶にあたらしいかと思います。
internet.watch.impress.co.jp


議論は続いており、Blinkの開発者メーリングリストの「Intent to Deprecate and Remove: Trust in existing Symantec-issued Certificates」にてシマンテックとGoogle(+ Mozilla)が協議を重ねていることがわかります。

本日、「Google ChromeとChromiumプロジェクトを代表して」という形で最終になるであろうFinal Planが提案されています。

原文を見ることをオススメしますが、自分用に簡単にメモ書きします。

補足ですが、Mozilla側はまた別ですのでそちらも注視しておく必要があります
(https://groups.google.com/forum/#!msg/mozilla.dev.security.policy/gn1i2JNVCnc/y7IRQALJBgAJ)

今後の予定

Chrome66での対応

Chrome66より 2016年6月1日よりも前に発行された証明書がdistrustされます

  • Beta: 2018/3/15 予定
  • Stable: 2018/4/17 予定

Chrome70での対応

Chrome70より、シマンテックがManaged Partner Infrastructure(2017/12/1)より以前に発行した証明書がdistrustされるようになります。

  • Beta: 2018/9/13 予定
  • Stable: 2018/10/23 予定

タイムテーブル

日付 イベント
2017年7月27日 ～ 2018年3月15日 2016年6月1日より前に発行されたシマンテック発行のTLSサーバー証明書を使用しているサイト運営者は、これらの証明書を置き換える必要があります。
2017年10月24日 Chrome62より distrustされる証明書がdevtoolで警告されます
2017年12月1日 シマンテックによれば、Managed Partner Infrastructureが有効になります。
この時点より以前に発行された証明書は将来的に機能しなくなっていきます(Chrome70)
2018年3月15日 Chrome66 Beta公開
2016年6月1日以前に発行された証明書が信頼されなくなります
2018年4月17日 Chrome66 Stable公開
2018年9月13日 Chrome70 Beta公開
Managed Partner Infrastructure(2017/12/1)以前に発行された証明書が信頼されなくなります
2018年10月23日 Chrome70 Stable公開

HTTP/2でのプライオリティ・プレースホルダの提案仕様

HTTP QUIC internet-draft

元々はHTTP over QUICでの議論に端を発するが、HTTP over QUICの仕様の著者でもあるMicrosoftのMike Bishop氏から「Priority Placeholders in HTTP/2」という仕様が提案されている。

解説すると長くなるので割りと雑目ですみません

HTTP2のプライオリティ制御

まずHTTP/2のプライオリティ制御について軽く説明する。

HTTP/2ではHTTPリクエストが並列的に送信される。そこで、クライアント側からHTTPリクエストを送る際にその要求の優先度を指定できる。サーバはその優先度を尊重してHTTPレスポンスを返す。

これによって、ページの表示に大事なCSSなどは早く、画像などは後でほしいと言ったことが実現されている。

この優先度では各ストリームにDependencyとWegithが設定される。Dependencyは各ストリームの依存関係(ストリームAが終わってから、ストリームBといった制御)、Weightは各コンテンツを返すのに使用するサーバリソースの比である。

すべてのストリームはストリームID=0もしくは他のどれかのストリームに依存する。つまり、木を構成することになり、Priority Treeと呼ばれる。

f:id:ASnoKaze:20170728010502p:plain
(引用: HTTP/2 Deep Dive: Priority & Server Push // Speaker Deck )

丸がストリームID, 四角がWegith，矢印がDependencyを表します。

上記図に示すとおり、Firefoxではストリーム3, 5, 7, 10をidle状態のまま各ストリームをグループに分けるために使用します。画像群やCSS群といったストリーム毎に一括で優先度処理するような形になっています。

ここでポイントになるのは

  • idle状態のストリームを用いて各ストリームの優先度をグループ化している(idleストリーム自体は以後使用しない)
  • HTTP/2ではcloseしたストリームもPriorityに影響してくる(closeしたストリームに依存するストリームを後から追加できる)

QUICとHTTP/2のプライオリティ

現段階ではQUICでもHTTP/2同様のプライオリティ制御方式を使用します。HTTP/2ではTCPを用いていたため送信した順序どおりに受信され処理されていたため、クライアントとサーバでPriority Treeを同期できました。しかし、QUICでは同一ストリーム上でのみ順番が保証されているため、Priorityフレームはconnection controlストリームで送られる事になっています。

また、一点大事な事として、HTTP over QUICでは各ストリームIDを飛ばすことなく使用しなければなりません。

つまりidleのストリームを用いてストリームの依存をグループ分け出来なくなっている。

Priority Placeholders in HTTP/2

Mike Bishop氏の「Priority Placeholders in HTTP/2」では、Priority Tree内でグループ分けをしたい場合は、それ専用のプレースホルダを使用します。このPriority PlaceholdersはSETTINGSフレームで各エンドポイントが合意した場合に使用できます(使用できるプレースホルダ数も合わせて通知されます)。

プレースホルダはプレースホルダIDを持っており、新しく追加されたDEPENDENT_ON_PLACEHOLDERフラグがon担っている場合はdependencyの指定がプレースホルダIDという事になります。

プレースホルダの作成はPLACEHOLDER_PRIORITYフレームで作成されます。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |0|                    Placeholder ID (31)                      |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |0|                  Stream Dependency (31)                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Weight (8)  |
      +-+-+-+-+-+-+-+-+

Flagやペイロードの意味はPRIORITYフレームとほぼ同等です。

この仕様では、プライオリティ・プレースホルダを使っている場合、サーバはアクティブでないストリームをPriority Treeから削除出来ることになっています(MAY)。詳しいやり方も仕様中に書かれています。

議論

冒頭で述べたように、元々はQUICでのIssueが最初にあり、IETFのオフラインミーティングを通して議論されてきており、その結果として今回の提案仕様となった。

議論はML上で続いており「QUICの問題を解決するには、プレースホルダとして「ストリームID」を指定できるように、PRIORITYフレームにフラグを追加してはどうか？」
という話も出ている。

Nginxで、リクエストを複製するmirrorモジュールが標準搭載された

nginx

[20170809追記] nginx-1.13.4に ngx_http_mirror_module は含まれました

Nginxで、リクエストを複製するmirrorモジュールがコミットされ、何もせずとも使用できるようになりそうです(現状最新コミットをビルドする必要あり)。

例えば本番環境のproxyからリクエストを複製して開発環境に流すような事も出来ます。もちろん複製処理は本来のリクエスト処理をブロックしません。

例えば以下のように、mirrorに来たリクエストを複製してバックエンドサーバに投げるようにしてみます
f:id:ASnoKaze:20170724032715p:plain

conf

    server {
        listen       80 ;
        server_name  localhost;

        mirror_request_body on;
        log_subrequest on;

        location /mirror {
            mirror /proxy; #/proxy宛にリクエストを複製する
        }
        location /proxy {
            proxy_pass http://127.0.0.1/proxyed/;#任意のサーバにproxyする
        }
    }
  • mirror ディレクティブでリクエストを複製し、自身の任意のPATHにリクエストを送ります。今回は別のサーバに送るために一旦 /proxy宛に複製します($request_uriは変更されません)。proxy_passではいつも通り任意のサーバにリクエストを送ります。
  • log_subrequestを有効にすると複製したリクエスト自体もaccess.logに記録されるようになります。
  • mirror_request_body はおそらくPOSTのデータと言ったリクエストボディも合わせて複製されるようになるものだと思います。

もちろん2つ以上複製することもできます

動作確認

上記 .conf では、access.logに3つのリクエストが記録される。
本来のリクエスト、log_subrequest onによって記録される複製されたリクエスト、自身にproxyされたのを受け取ったリクエスト

vagrant@vagrant:~/nginx-mirror$ curl localhost/mirror
mirror

vagrant@vagrant:~/nginx-mirror$ tail -f /usr/local/nginx/logs/access.log
127.0.0.1 - - [23/Jul/2017:18:08:14 +0000] "GET /proxyed/ HTTP/1.0" 200 0 "-" "curl/7.47.0"
127.0.0.1 - - [23/Jul/2017:18:08:14 +0000] "GET /mirror HTTP/1.1" 200 256 "-" "curl/7.47.0"
127.0.0.1 - - [23/Jul/2017:18:08:14 +0000] "GET /mirror HTTP/1.1" 200 7 "-" "curl/7.47.0"

(本来のリクエストのログは複製処理が終わったあとに出るが、本来のリクエストへのレスポンス処理はブロックされていないように見えました)

追記2018/04/11
tagomoris先生の検証記事が非常に分かりやすくて素晴らしいです
tagomoris.hatenablog.com



便利！！