感想: イベントVs.スレッドをhigh-conccurencyサーバを対象に
して真面目に考え直してみた論文。

• Abstract
  • イベントモデルは high-concurrency システムでは良いとされて
    きたが、それは間違いだ! (筆者らの信じるところによれば)
  • イベントの良い点(高い並列性、低いオーバヘッド、シンプルな
    並列モデル)などはスレッドでも達成できる。さらに、スレッドの
    方がよりシンプルで自然なモデルでプログラムを書ける。
  • スレッドの弱さは本質的なものではなくスレッドパッケージの実装のせい。
  • これを示すために、10万スレッド規模のスケーラビリティと高い性能
    を示すユーザレベルスレッドパッケージを構築。
  • また、高い並列性を得るにはコンパイラ支援が重要であることを示す。

1. Introduction
   • これまでイベントモデルの良い点とされてきたこと:
     • 協調マルチタスク(cooperative multitasking)による効率的な同期
     • 状態管理における低いオーバヘッド(スタックモデルではない)
     • アプリケーションレベルの情報に基づいたスケジューリングと局所性
     • より柔軟な制御フロー(単純なcall/returnだけではない)

     これらの点を追求するため、既存のイベントを使用した high-concurrency
     システムをいろいろ調べてみた。Ninja, SEDA, InktomiのTraffic Serverなど。
     その結果、これらの良い点はスレッドでも達成できると気づいた。

   • スレッドに関して彼らが言いたいのは:
     1. スレッドの方がサーバプログラムをより自然に抽象化できる。
     2. コンパイラとランタイムの少しの改良により弱点はなくせる。
        さらに、スレッドシステムはよりコンパイラベースの改良に向いている。

2. Threads vs. Events
   • 並列プログラミングにおいて、スレッドとイベントのどちらがいいか
     というのは非常に古い論争。Lauer and Needham がこの2つのモデルは
     本質的に同じであると言ったが、論争に終止符は打たれなかった…

   1. 2.1 Duality Revisited
      • Lauer and Needham の論じたスレッドとイベントの二重性:

                              Events - Threads
                      event handlers - monitors
        events accepted by a handler - functions exported by a module
            SendMessage / AwaitReply - procedure call, or fork/join
                           SendReply - return from procedure
                waiting for messages - waiting on condition variables
        

        適切な実装であれば、両者の性能は同等である。
        従って、対象アプリケーションによって適切なパラダイムを選ぶべき。

      • Lauer and Needham が論じてない点
        • 最近のイベントシステムは同期に Cooperative scheduling を使っている
        • 最近のイベントシステムはみんな共有メモリを使っている
        • スレッドシステムには未だ「適切な実装」が存在しない

      • Lauer and Needham は性能の同等性を示すために "blocking graph"
        というものを使った。このグラフでは各点が block あるいは yield
        を示し、各辺がそうした2点間で実行されるコードを示す。
        スレッドとイベントではどちらも同じグラフを描ける→同等

   2. 2.2 "Problems" with Threads
      • 性能: スレッドは性能が悪い:
        high-concurrency システムについて言えば、これは実装のせい。
        スレッドシステムのオーバヘッド源は2つ:
        • スレッド数nに比例するO(n)の操作 (スケジューリングなど)
        • コンテキストスイッチ

        スケジューラからO(n)の操作を取り除く改良を施して実験したら、
        ほぼ同等の性能が得られた(図2)。

      • 制御フロー: スレッドの制御フローは柔軟性がない:
        スレッドモデルではタスクを線形に書くため、より効率の良い並列
        フローの利用を妨げるという批判。しかし、既存システムを調べると
        イベントシステムでも主に使われているフローは call/return,
        parallel calls, pipelines の3種類だけ。→ スレッドでもOK!

        また、複雑な制御フローは複雑性を産み、新たなエラーや競合状態
        を引き起こすからどっちにしても望ましくないと思われる。

        multicast や publish/subscribe アプリケーションで見られる
        dynamic fan-in / fan-out だけはスレッドでは実現が難しい。
        しかしこのフローは high concurrency サーバではほとんど見られない。

        堅牢なシステムを作るには、処理後に何らかのack処理が必要である。
        これは結局イベントモデルでも何らかの形で "return" 処理が必要
        となることを示している。

      • 同期: スレッドの同期は高負荷である:
        イベントでは mutex などの同期処理がいらない。しかしこれは
        単に協調マルチタスクのおかげ、というか non preemptive な並列
        実行モデルのおかげであって、別にイベントのおかげではない。
        また、プロセッサが複数あったら結局イベントモデルでも同期が必要。

      • 状態管理: スレッドスタックは状態管理には非効率な方法である:
        スレッドシステムではスタック上に各スレッドの実行状態を積んで
        いけるが、この手法には小さいスタックを使うとスタックオーバフロー
        の危険があり、大きいスタックを使うと無駄にメモリを浪費するという
        トレードオフがある。
        → 新しい dynamic stack growth 機構を提案

        イベントモデルは状態管理を block point であまり保持しないよう
        なプログラムになりやすいという利点があり、block 時に保持される
        スタック上のデータが比較的少なくすむ。
        → コンパイラサポートによる解決を提案

      • スケジューリング: スレッドモデルは最適なスケジューリングが困難:
        イベントモデルでは、汎用的な仮想多重プロセスモデルを取るスレッドに
        比べると、アプリケーションレベルでタスクのスケジューリングを調整
        でき、またコードの局所性も高いという説。
        → Lauer-Needham duality から、スレッドでも同等のことが可能なはず

   3. 2.3 Summary
      • というわけで、イベントに本質的な利点はない。

3. The Case for Threads

   ここまではスレッドとイベントの同等性を示したが、3. ではスレッドの方が
   より優れているということを示す。

   • 制御フロー:
     イベントはアプリケーションの制御フローを曖昧にする。
     • call/return もモジュール間のイベント呼び出しで書かなければならない
     • call/return のたびにプログラマが実行状態をsave/restoreしないとダメ
       (stack ripping)
     → 新たな競合とエラー を引き起こしやすい

     スレッドモデルだと、cause/effect 関係などが理解しやすいし、スタックが
     全てのタスク実行状態をカプセル化してくれるのでわかりやすい。

   • 例外処理と状態管理:
     スレッドモデルの方がタスク終了後の状態の後片付けがやりやすい。
     イベントモデルでは制御フローを追いにくいため、例外時や通常終了時など
     それぞれのときに状態をいつ捨てればいいのかわかりにくい。
     多くの最近のイベントシステムではGCを使ってるが、GCはhigh-performance
     系の処理には向かない。参照カウンタを使ってるシステムもあるが、エラー
     処理時などに問題を引き起こしやすいのは同じ…

   • 既存のシステム:
     既存のイベントシステムにおいてすら複雑なところや性能が問題ない
     ところではスレッドを使いがち。

   • Just Fix Events?:
     イベントの問題をツールや言語サポートで解決する試みもあるが、こうした
     試みは結局スレッドlikeなモデルに落ち着く… (ex. Adya)

4. Compiler Support for Threads

   コンパイラとランタイムのちょっとした変更で、スレッドシステムが
   安全性、性能、コード生産性ともに達成できることを示す。

   1. 4.1 Dynamic Stack Growth

      スタックサイズを固定ではなく実行時に調整できるように変更し、
      スタックにおけるトレードオフを解消。

      • コンパイラの解析により、各関数のスタック使用上限を検出
      • どの呼び出しがスタック伸長を必要とするか解析

      ただし、再帰、関数ポインタなどはもっと追求が必要だろう。

   2. 4.2 Live State Management
      • コンパイラの解析により、関数呼び出し前にいらない状態変数を
        スタックから消去。例えば、
        • 子ルーチン呼び出し前に一時変数をポップ
        • テールコールではそれまでのフレーム全体をポップ
      • 生存時間がかぶってる変数はスタック上の再配置を行い、
        必要ないメモリをいつまでもスタック上に確保し続けることを防止
      • プログラマへの警告

   3. 4.3 Synchronization
      • コンパイラ解析によるデータ競合に対する適切な警告
      • 例えば、nesC は atomic 領域と並列モデルをサポートするCライクな
        言語で、イベントとスレッドを mix して書ける。
        nesC では、コンパイラが
        • call graph を使って atomic section がグラフの一辺におさまることを
          保証する (つまり atomic領域中で block/yield はできない)
        • どの atomic section が並列に走れるか解析し、ランタイムにその
          情報を渡す

5. Evaluation
   • Linux上で5000行のユーザレベルスレッドパッケージを設計・実装
   • coro ライブラリ[12]により最小のコンテキストスイッチ、ブロッキングI/O
     の非同期リクエストへの変換を実現。(poll()＋スレッドプール)
   • その上に700行のWebサーバ Knot を実装
     • Knot-C: accept より active connections の処理を優先
     • Knot-A: active connections の処理より accept を優先
   • SEDAのイベントドリブンWebサーバHaboobと性能比較

   • 図3: 結果:
     • Haboob と Knot-A の飽和後の性能低下は poll() のダメな実装のせい。
       sys_epoll() を使うともっと性能は良くなる。
     • Knot-C は 700Mbps で飽和・安定。
     • Haboob は 500Mbps, 512クライアントくらいが限界。
       • ハンドラ毎にスレッドプールをおいてイベント処理するモデルのため、
         飽和時には30,000回ものコンテキストスイッチが発生(Knotの6倍)
       • イベントモデルのため小さいモジュールが大量にある→GCの負荷大

6. Related Work
7. Conclusion

This html is automatically converted by Txt2Html 0.9b
Fri Jun 27 16:54:02 2003