QUICの技術要素分解

この投稿はHTTP2 Advent Calendar 2014の18日目の記事です。
前日は HTTP2におけるProxyに関する議論 でした。


(あらすじ・前略)
もっこすにはHTTPがわからぬ。もっこすは、ただのゲーマーである。ヴァナディールで市場価格操作に命を懸け、艦娘と遊んで暮らしてきた。けれどもトランスポート層のプロトコルについては、人一倍に敏感であった。

QUIC

HTTP2とは直接関係ないので、念のため概要を説明してから進みます。HTTP2勉強会 #hｔtp2studyシリーズに参加されている方だと、もうご存知の方が多そうな気はしますが、とりあえず。

QUICとは、Googleが開発しChromiumに実装中のトランスポート層、すなわちTCPと同じ層のプロトコルです。Internet上で運用される独自実装トランスポートの常として、UDPで包んだ中に独自実装が入っています。

QUICの主目的は、1にも2にも接続開始時の遅延削減です。Design Documentをはじめ各所には、QUICによるメリットがいくつも箇条書きされていますが、最初の遅延削減だけは飛びぬけてプライオリティが高いです。せっかくの新プロトコルなので、改良できそうな点はたくさんありますが、Webを扱うGoogleとしてのプライオリティは明確に「ページを早く表示する」ことに置かれているのです。IETFでの発表資料(PDF注意)でも、太字になっていますよね？

最低限の概要説明はここまで。以後、QUICで使われている技術要素から、面白そうなものを紹介していきます。

マルチストリーミング

QUICでは、ひとつの接続(Connection)の上に、複数の論理的接続(Stream)が走ります。

• Streamに優先度をつけたり
• Stream毎に違う挙動にしたり
• 再送制御をStream毎に独立して行ったり

と色々な柔軟性が生まれます。一番インパクトが大きいのは最後のもので、例えばStream #1でパケットが落ちても、他のStreamに悪影響を及ぼしません。TCPだと仕様上そういうことは出来なくて、パケットが1個落ちたら、同じ接続上の後続パケットは全部影響を受けます。いわゆるHoLブロッキングというもの。その一個が再送されるまで、後ろのデータは一切アプリケーションに渡されません。つらぽよ。

このマルチストリーミングは、SCTPというプロトコルでかなり前から用いられています。SCTPについての説明は、古いですがIBM Developer worksのものをどうぞ。"2000年10月にRFCになった比較的新しいプロトコルです"なんて書いてありますね…。

既にあるならば、それを使えば良いではないですか！ 実際WebRTCのデータ転送では、DTLS(UDP+セキュリティ)の上にSCTPが走っています。このレイヤーを弄っているギークなら、QUICを見て最初に思う事は「なんでDTLS＋SCTPじゃダメなの？」であって、Design DocumentにもQUIC FAQ for Geeksにも理由の説明があります。本件の説明はこの後で少しずつ。

0-RTT connection

古き良きTCPで接続すると3-way ハンドシェイクによる接続が始まり、上にセキュリティレイヤーがあればそのレイヤーでも情報が行ったり来たりして、ようやく通信が始まります。これはたまらん。特に、RTTの長い場合に、ページが表示され始めるまでの時間がやたら長くなってしまいます。

TCPには、既にTCP Fast Openという技があります。乱暴に説明するならば、一番最初のパケットにリクエスト内容も載せてしまえるもの。Linuxカーネルには年単位で昔に入っていますが、クライアント側での普及率はまだかなり低いのではないかと思われます。BSDソケットAPIのconnect()にはデータを載せられないので、TCPなのにconnect()ではなくてsendto()で接続しに行くんですけど、どれくらいの方が使用経験ありますかね？


(左が普通のTCP、右がTFOが上手くいったときの図)

TFOのI-D見ると、しっかりGoogleの名前が入っています。Googleの資料に "Deploy in today's internet"と書いてある部分は、TCPにコントリビュートしても、浸透に何年かかるんだよ！という怒りが込められているのかもしれません。もちろん、QUICでは同様の技が実装されます。


QUICで遅延関係でもう一つ進んだところは、トランスポート層と、その上のセキュリティ関係の層(のハンドシェイク)をまとめて済ませようとしているところです。仮想化・レイヤー構造ってものは、柔軟に差し替えられるように存在するものであって、TLSを他に差し替える必要がないのであれば必要ない…という判断は理解できます。これが、DTLSでハンドシェイクして、SCTPでハンドシェイクして、と何度も往復しなければならない DTLS＋SCTPとの違いになります。(他にTLS層でいくつかメリットがあるけども割愛)

WebRTCの選択が悪いわけではありません。あれはコネクション張りっぱなしで色々するものなので、Googleのシナリオとは接続遅延の重要性が全く違います。そこの性能向上が要らないわけではないので、いずれQUICが成熟したら、置き換えの可能性はあるでしょうが…

ペーシング

ペーシングは、パケット送信間隔を均してバースト転送を避けることで、経路上のバッファ溢れによるパケットロスを減らす仕組みです。これを他人に説明するときには、いつも産総研のPSPacerのページに丸投げしています。良い説明です。新しい技術ではありませんが、QUICの送信制御に入るようです。

FEC (エラー訂正)

QUICには、パケットレベルのエラー訂正の仕組みが実装されています。仕組みは単純で、パケットN個のグループあたり1個のエラー訂正パケット(他のパケットのXOR)を追加で送ることにより、そのグループ内でパケットロスが1個ならば訂正し、再送を抑えることが出来る、というもの。(RAID5を思い浮かべましょう)
追加で余計な情報を送るので、再送遅延の節約と、余計な帯域消費とのトレードオフです。

ハンドオーバー

QUICはコネクションに対して64bitのユニークな値を付与し、これをIDとします。既存のInternetトランスポート層では基本的に、IDとなるのは {アドレス, ポート番号} でした。もちろん、アプリケーションレイヤーまで行けばちゃんとユーザーIDなどがありますが…。

IDがアドレスから切り離されることにより、仮にIPアドレスやポート番号が変化したとしても、それをトランスポート層で吸収して隠蔽することができます。接続が切れたからとハンドシェイクをやり直す必要がなくなり、すなわち次にWebページ等を表示したときの遅延が解消されます。モバイル環境で端末が大きく移動したとき、回線を3GからWiFiアクセスポイントに繋ぎかえたときに利点が得られるであろうことは、想像が付きますね。既存技術では、機能の観点からはmobile IPに相当するでしょうか？

QUICの場合、このID仕様が生きる場面はもう一つあり、それはNAT(NAPT)のポートマッピング変更です。UDPはコネクションの概念がないので、既存のmiddleboxはタイムアウトとかLRUとかを用いて、NAPTのマッピングを消したり変えたりします。同じように通信しているつもりが、いつのまにかさっきとユーザー側のポート番号が違う、という恐ろしいことが起こります。そこでこのID仕様が役に立つ…というより無いと困ってしまうわけです。

ついでにNAPTの話をもう少し

NAPT問題は、QUICの実用に向けて、一番難しい課題かもしれません。NAPTエントリが消滅したら、装置の内側から一発飛ばさないと穴が開きません。サーバーからの通信は、タイミングが悪いと落ちてしまいます。定期的に穴あけをしたいですが、keepaliveであまり帯域を食うのも微妙だし、モバイル端末ならバッテリーの問題もあります。つまらない話ですが、TCPへのフォールバックは必ず用意する必要がある、のかもしれません。

keepaliveの間隔はGoogle側で話題になっているし、NAPTのタイムアウト時間設定はISP側で悩ましい問題になりそうです。IPv6ならば、NAPTかまさず出てこられるかもしれないので、ここでv6への機運がなぜか高まる、というシナリオに進んだら面白いと思います。(あまりなさそうと思いつつ書いている)

近況

QUICはその実験的性格から、公開まで時間がかかるのではないかと心配していましたが、意外と早い時期に手の届くところに来るかもしれません。つい最近のQUIC Prototype Protocol Discussion groupの投稿によると…

we're hoping to engage other developers and get real server implementations (apache, nginx etc.) in 2015. 

nginxやapacheに載ってしまえば、あとは設定を変えれば動いてしまうわけで、2015年は良い意味でHTTP激動の年になってくれるかもしれません。HTTP/2のみならず、です。楽しみにしましょう！

〆

この記事では、QUICで実装されている高速化技術を、できるだけ既存の対応する技術と関連させつつ紹介しました。セキュリティ関係は、若干地味な上に背景を説明するのに分量が必要なので、かなり割愛しています。興味のある方は、Design Documentに説明があったはずなので、そちらをどうぞ。


…ああ、思いつき3秒で書いたあらすじの伏線が投げっぱなしで回収されていない。どうしよう。困った。

万歳！Google様万歳！


---
この投稿はHTTP2 Advent Calendar 2014の18日目の記事でした。
後日、ここに翌日へのリンクが入ります。

Scala標準のFutureと並列コレクションの実行コンテキスト

この投稿はScala Advent Calendar 2014の5日目の記事です。4日目はmeganemuraさんの Scalastyle の導入 でした。
5日に出先から戻って以降ダウンしていた影響で、公開が翌朝になっております。すいません。

記事のテーマはシンプルで、Scalaの標準ライブラリの中で勝手にうまいことやってくれる(らしい)並列・非同期処理について、実行されるスレッドがどうなっているのか調べてみるものです。

Future

どこのFutureチュートリアルでも基本的に、 import ExecutionContext.Implicits.global をとりあえず書きましょう、と但し書きしてスタートします。これがデフォルトのFuture用の実行コンテキスト。 実行コンテキストの指定をしなかった場合 Cannot find an implicit ExecutionContext と怒られます。

ExecutionContext.Implicits.global の実装は、object Implicitの中にimplicit lazy val global: ExecutionContextExecutorがあって…中略、辿っていくと最終的に、以下の部分に辿り着きます。2.11.4では scala/concurrent/impl/ExecutionContextImpl.scala 内。

    try {
      new ForkJoinPool(
        desiredParallelism,
        threadFactory,
        uncaughtExceptionHandler,
        true) // Async all the way baby
    } catch {

java.util.conncurrentにあるForkJoinPoolですね。
デフォルトのものを使った場合の挙動は以前確認してみたのですが、最大スレッド数＝CPU数としてForkJoinスレッドを扱う、無難な実装であるようです。

並列コレクション (parallel collection)

listやmap等のコレクションに対し、par を呼び出すことで簡単に並列処理になるよ！というやつです。

x: List[Int] =  // なにかListがあるとして…
scala> x.map(_ + 1)  // 普通のmap
scala> x.par.map(_ + 1)  // 並列版

基本的な説明も使い方も、公式のドキュメントにあります。設定は「並列コレクションの設定」のページ。特に実行環境を何も指定せず、おもむろに par を使っても、デフォルトの設定により実行されます。Futureと違って怒られない。

デフォルト以外の設定をする方法

Futureが要求するのはscala.concurrent.ExecutionContextExecutor で、並列コレクションが要求するのはscala.collection.parallel.TaskSupportなので微妙に違いますが、大したことはありません。

scala> import scala.concurrent._
scala> val pool = new forkjoin.ForkJoinPool(4)

pool: scala.concurrent.forkjoin.ForkJoinPool = scala.concurrent.forkjoin.ForkJoinPool@7f39e4a3[Running, parallelism = 4, size = 0, active = 0, running = 0, steals = 0, tasks = 0, submissions = 0]

並列コレクションはtasksuppoortに設定。

scala> import scala.collection.parallel
scala> val pc = parallel.mutable.ParArray(1, 2, 3)

pc: scala.collection.parallel.mutable.ParArray[Int] = ParArray(1, 2, 3)

scala> pc.tasksupport = new scala.collection.parallel.ForkJoinTaskSupport(pool)

pc.tasksupport: scala.collection.parallel.TaskSupport = scala.collection.parallel.ForkJoinTaskSupport@81df807

Futureは、object ExecutionContextを使ってなんとか。

scala> implicit val ece: ExecutionContextExecutor = scala.concurrent.ExecutionContext.fromExecutor(pool)

ece: scala.concurrent.ExecutionContextExecutor = scala.concurrent.impl.ExecutionContextImpl@2bacfa90

これでどちらも好きに設定できそうです。



この投稿はScala Advent Calendar 2014の5日目の記事でした。
6日目はkawachiさんによるscalac にもっと警告してもらう です。

2014年のElixir1.0初心者

この投稿はElixir Advent Calendar 2014の1日目の記事です。

今年後半になってようやくElixirを触り始めました。初心者の踏んだ罠や、良さを感じたところなどを紹介したいと思います。Elixir v1.0になってから触った日本人初心者というのもあまり多くはないはずなので、これから誰かに勧めたい人・あるいはこれから始めたい人の参考になれば。

モチベーション

何故Elixirを触りたくなったかというと、特に突飛な理由はなく…

• Erlang VMを使いたい
• OTPを使いたい

この2点です。メモリ回収がプロセス単位GC＋参照カウントバイナリなErlang VM、圧倒的な稼働実績を誇るOTP、どちらも代替になるものがないので。普通にErlang書けよと言われればまあそうなのですが、どうせなら変わったものを使ってみようという好奇心ですね。

◎良かった点

文字列の扱いが楽

• 文字列は <> で繋がり、マッチングも出来る

iex(28)> str = "hogehige"
"hogehige"
iex(29)> str <> "123"
"hogehige123"
iex(30)> "hoge" <> s = str
"hogehige"
iex(31)> s
"hige"

• 文字列に値を埋め込みたいときは、だいたいinspectでOK

iex(34)> "value: " <> inspect xs
"value: [1, 2, 3, 4, 5, 4, 3, 2, 1, 4]"
iex(35)> "value: #{inspect xs}"
"value: [1, 2, 3, 4, 5, 4, 3, 2, 1, 4]"
iex(36)> "value: #{inspect xs |> Enum.take 2}"
"value: [1, 2]"

ただ、全部Unicodeで処理してくれるElixirのライブラリは、Erlangにあるものとは別の枯れていないライブラリなので、性能とか信頼性とかは若干怪しげです。先日、「\n\rが1文字にカウントされる」という謎のバグを踏んで、ちょっとビビってました。既に修正が入っているようですが。

REPL (iex) が使いやすい

組み込みのプロジェクト管理 mix で作ったプロジェクト、その中で作ったモジュールがコマンドラインで簡単に読み込んで試せる(という機構がデフォルトでついてくる)のが楽でした。

iex -S mix

これで起動するとプロジェクト中のMyModule.hogeなどを試せる。l(MｙModule)でリロード。ちゃんとしたテストのフレームワークも揃っていますが、色々よくわかっていない段階では、テストとしてメンテすべき単位よりも小さい単位でずんどこコケますので…。ここValueじゃなくて[Value]が返ってきてたのかー、みたいな。

Erlangのerlと比べると、再代入出来たり行末に記号が必要なかったりという仕様はREPLとの相性がよく、ヒストリから使い回すのも簡単。触っているときの快適さはかなり違います。

パイプライン演算子 |>

F#のステキアイテム、パイプライン演算子。

iex(11)> Enum.take(xs, 5)
[1, 2, 3, 4, 5]
iex(12)> xs |> Enum.take 5
[1, 2, 3, 4, 5]
iex(13)> xs |> Enum.take(5) |> Enum.map &(&1 * 2)
[2, 4, 6, 8, 10]

Erlangっぽく{:ok, xxx}で返ってくる関数が困るのですが、それについては去年のAdvent Calendarにあるmururuさんの説明が詳しいのでそちらを。末尾に ! のついた関数(Dicr.fetch!など)を使うと、:ok のタプルではなくて直接結果が返ってくるものがあるので組み合わせやすいですが、それで全体を例外処理で囲んじゃう方法が良いのかどうかは、ちょっとまだわからない…。

△はまった点

わかってみれば大したことではないけれども、多分みんな通る(ような気がする)部分もいくつか。

整数のリストを表示しようとしてびびる

iex(43)> now_hp = [64, 57, 67, 83, 49, 33]
'@9CS1!'

ファッ！？

これはErlangで、文字列と整数のリストの区別がないからですね…。inspectのオプションに:char_listsがあるのですが、触り始めたら早い時期に踏む仕様なのに、初心者がそこまで自力でたどり着くのはなかなか厳しいのでは。もし今後初心者向けの紹介を書く人がいたら、これには一言触れておいて欲しいところ…

iex(44)> [-1 | now_hp]
[-1, 64, 57, 67, 83, 49, 33]

とりあえず仮で表示するだけの場合は、ASCII文字っぽく見えないようにするWorkaroundで回避しています。

mapはどこ？

Listに対してmap処理をしようとしたらListにMapはありませんでした。Enumの方にまとめられているんですね。List.foldlはあるがList.mapはない！List.tailはどこにもない？なかなか覚えられなくて、いまだにEnumのドキュメントは開きっぱなしでコーディングしています orz

総括

生のErlangと比べるとだいぶ初心者にやさしい言語ですね！
なんとかErlangのプロジェクトを、最初は部分的にでも乗っ取る感じで使えたらいいなーと目論んでおります。


この投稿はElixir Advent Calendar 2014の1日目の記事でした。
次は niku さんです → 2014/12/02/Extwitterでtwitter streamingを眺めてあそぶ - ヽ（´・肉・｀）ノログ

Visual Studio Communityで(貧乏人の)F#が捗る

Visual Studio Community 2013 が公開され、個人開発者はこれを利用できるようになりました。今まではExpressがいまいちで、かといってランクを上げるには6万円ほど必要で、趣味で使い始めるにはとても敷居が高かったのです。
そして、開発ターゲット毎にエディションが異なり、さらに複数言語プロジェクトの混在を扱えないExpressは、F#を扱うのがとても大変でした。参考；VS2012頃のF#関連の記事。いつのまにか触らなくなってしまいました。

しかしVS Communityの到来により、またF#を考えるべき時期が到来したのかもしれません。
まず初回起動時に聞かれる開発設定の選択肢に姿が見え、


新規作成プロジェクトの選択肢にもいて、

 

ちゃんと複数言語混在ソリューションも作れます。これで、C#のGUIの裏側でF#のライブラリを使うことが、難しくなくなりました。



習得したい積み言語が積み上がっていて、F#は奥の方(やる気のかなり低い方)に埋もれてしまっていたのですが、今後.NETのGUIを組むときにはまた使ってみましょう。