SOSP 2009適当まとめ

夏休みで一週間ハワイに行ってました。身も心もリフレッシュ。

というのはタイトルとは関係なくて、システム系では最高峰の学会SOSPの最新の論文が公開されていたのを見つけたので、適当に流し読みしてみました。

• SOSP 2009: Technical Programs

主に僕の興味の有るやつになります。無いのはアブスト読むどころかリストにすら入ってないので、ご注意を。特にセキュリティ周りとか。

しかしHadoopを利用した論文が結構多い。どの学会もMapReduce流行り過ぎ感がちょっと否めないですね。。。以下リストです。

- FAWN: A Fast Array of Wimpy Nodes
遅いCPUとFlashドライブを並べて低消費電力なストレージを作るというアーキテクチャ「FAWN」を提案。この上に「FAWN-KV」と呼ばれるKey-Value Storeを作成し、実験を行った。Chain-Replication、ノード追加時のプロトコル等が詳しく載っている。

- The Multikernel: A new OS architecture for scalable multicore systems
メニーコア時代に向けてMultikernelという新しいカーネルアーキテクチャを提案。マシンをネットワークで接続されたコアの集合体とみなし、基本のOS機能を資源共有ではなく、コアをノードとみなした分散システムとして実装する。Barrelfish OSというプロトタイプを作成し、評価した。

- Fast Byte-Granularity Software Fault Isolation
デバドラのバグをカーネルから隔離し、かつオーバヘッドが少ないFault Isolation技術「BGI」を提案。従来までは非常にオーバーヘッドが高かったのに対し、0～16%のオーバヘッドに抑える事が出来る。

- Tolerating Hardware Device Failures in Software
ハードウェアが故障した際に、クラッシュしたりハングしたりするデバドラが有が、そのようなバグは負荷テスト時にも発見しづらい。そこで、Carburizerと呼ばれるシステムを提案する。コードを静的に解析するツールとそれに付随するランタイムで構成され、ハードウェアの故障を間違って信じてしまっているコードを自動的に発見する事が出来る。

- Debugging in the (Very) Large: Ten Years of Implementation and Experience
Windows Error Reporting (WER)の仕組み。数百万のユーザーから来るバグ報告を以下に効率よく集め、裁いているか。

- Detecting Large-Scale System Problems by Mining Console Logs
コンソールログから、問題の究明を行うシステムを提案。具体的にはコンソールログ/ソースコード解析/機械学習を組み合わせる。オンラインゲームのログと、HDFSのログからいくつか実際に問題を発見する事が出来た。

- Better I/O Through Byte-Addressable, Persistent Memory
Phase Change Memory (PCM)と呼ばれる、バイトアクセス可能なPersistentメモリが登場している。そのようなハードウェア上で高速に動作するファイルシステムBPFSを提案する。BPFSでは強い一貫性を提供するほか、パフォーマンスも非常に向上する。

- Modular Data Storage with Anvil
Anvilと呼ばれる、モジュラーなデータストアシステムを提案している。dTablesという仕組みにより、バックエンドストレージのデータレイアウトなどをフレキシブルに変える事が出来る。これにより、様々なワークロードやデータに対して実験を行う基盤を作る事が出来る。

- Operating System Transactions
OSが提供するSystme Transactionという仕組みを提供する事で、プログラマがアプリケーションからトランザクションを発行する事が出来る。これによって、TOCTTOU (time-of-check-to-time-of-use) などのレースコンディションを無くす事が出来る。TxOSというLinuxベースのシステムを実装し、オーバーヘッドも少ない事を確認した。System Transactionを用いて、ext3のようなジャーナリングが必要なシステムを約1か月で実装出来た。

- seL4: Formal Verification of an OS Kernel
マイクロカーネルを機械的にverificationする方法を提案。L4カーネルをベースにしたシステムseL4を実装し、verificationの為の変更コストとランタイムオーバーヘッドが小さい事を確認した。

- Distributed Aggregation for Data-Parallel Computing: Interfaces and Implementations
MapReduceや行列演算のように、計算の途中でデータを一か所に集めるDistributed Aggregationが重要性を増している。これをプログラマーが簡単に行える事も重要である。この論文ではOracle Parallel Server, Hadoop, DryadLINQを使って様々なAggregationユースケースを評価した。

- Quincy: Fair Scheduling for Distributed Computing Cluster
MapReduceやDryadの様なデータインテンシブな処理では、データのローカリティやジョブ間の公平性が非常に重要となる。それらを考慮したスケジューリングアルゴリズムを提案する。具体的にはグラフのエッジにデータローカリティ・公平性などをエンコードし、スケジューリングを行う。Quincyと呼ばれるプロトタイプ実装を作成し、スループットが向上する事を確認した。

- UpRight Cluster Services
Byzantine Failureセーフを実現するUpRightライブラリを、ZookeeperとHDFSに適用した。これにより、更なる信頼性が得られたのに加え、パフォーマンス劣化も非常に少ない事が確認された。

Similar Posts:

• BlueGeneのアーキテクチャ超適当まとめ
• タモリ倶楽部 20060729 「初潜入世界最高峰のIT企業独占公開！超リアルで遊べる地図」
• 複数マシンへHadoopをインストールする