他のプロセスに与える影響の少ない 実行時ミラーリングシステム 柳澤　佳里*1 千葉　滋*1 *1 東京工業大学　情報理工学研究科

サーバーのディスクバックアップ YahooやGoogleでのバックアップ作成は困難 バックアップの災害耐性を持たせるのは困難 常時アクセスがある環境でのバックアップは困難 バックアップ作成中は極度に性能低下 繫がらないユーザの[Reload]による輻輳の恐れ バックアップの災害耐性を持たせるのは困難 バックアップが手元にあると同時に被災する恐れ 遠隔地にバックアップテープを移送するのは手間

サーバーのディスクバックアップの要件 実行時ディスクバックアップ 遠隔地ディスクバックアップ Incrementalにディスクバックアップを実行 バックアップ実行の負荷を時間分散 時間分散させることで瞬間バックアップ負荷を軽減 遠隔地ディスクバックアップ 遠隔地のマシンのディスクにバックアップ 災害耐性を持たせる e.g. 隣のビルにバックアップし火災によるデータ破損に対処

バックアップ処理のスケジューリング バックアップ処理による性能低下を避けたい 競合する資源全てを考慮してスケジュールしたい サーバー負荷増大時にバックアップ処理を休止 バックアップ処理はサーバープロセスより低い重要度 サーバーへのアクセスが多いときには変更も多い 競合する資源全てを考慮してスケジュールしたい スケジューリングで考慮する資源は多岐にわたる ディスクバックアップは多種の資源を使用

我々の Tottottoミラーリングシステム スケジューリングの工夫 ヒントつきprogress-based regulation (Pbr) ネットワークの使用量をヒントとしたPbr Pbrと従来スケジューリングとのハイブリッド Pbr: プログラムの進捗を見てスケジューリング 特定の資源によらずスケジューリング 統計処理を行うので反応が遅い 従来型:資源の使用量を見てスケジューリング 即応性が必要な資源競合をスケジューリング Pbrの遅さをカバー

Progress-based regulation (Pbr) 進捗状況のフィードバックによるスケジューリング 重要度の低いプロセスは進捗をスケジューラに報告 資源を譲る善意のプロセスのためのスケジューリング 進捗悪化時:重要度の低いプロセスを停止 資源の競合の恐れ 進捗良好時:重要度の高いものと同じ資源割り当て 個々の資源の使用量を調べずスケジューリング可 資源ごとのスケジューラ作成は不要

Progress-based regulationの難点 Pbrは統計処理で進捗を判断 適切な閾値を設定するのは困難 従来の閾値による動作への反省 急激な資源の使用量の上昇への対応に遅れ 統計処理に足るデータ量が必要 量に限りがある資源の割り当てには不向き 個々の資源を見ずにスケジューリング

資源監視によるスケジューリング 資源使用量を見てスケジューリング 閾値のチューニングが困難 閾値を超える変化をした場合に停止 即応性のあるスケジューリングが可能 量に限りがある資源も適切にスケジュール可能 閾値のチューニングが困難 うまくスケジュールするには適度な閾値が必要 適切な閾値を多数の資源に定めるのは困難 Tottottoではネットワーク流量について閾値を経験的に定め監視

スケジューラの実装 ミラーリングソフトが自主的にスケジューリング ヒントつき Pbr NetBSD 1.6Rに実装 Kernelの改造が不要 資源競合時に Usleep(2),Sleep(3)により他プロセスに資源を移譲 Sleep時間はbinary exponential back-offで増加 ヒントつき Pbr ネットワーク流量監視スケジューリングをヒント 競合する資源をネットワーク資源(mbuf)と想定 ネットワークサーバー用途を想定 NetBSD 1.6Rに実装 LFSが実装されているOS

Tottottoにおけるミラーリング LFSv2/NetBSD対象 LFS: Log-structured File System,ログ構造のFS LFSのブロック(segment)単位でミラーリング 前回ミラーリングした箇所との差分発見が容易 LFSでは追記にてファイルシステムの変更を表現 現在書き込み中のsegmentはsuperblockに記録

スケジューリングのタイミング 流量監視スケジューリング: segment送信ごと ネットワーク使用の直前に使用量を調査 混雑時に混雑を助長するのを防止 Progress-based regulation: 差分送信ごと 進捗を調べやすいところで進捗調査 前回からの差分を求める箇所も調査対象に Segment送信ごとだと重み付けが困難

提案するスケジューリング法の 効果を見る実験 目的 バックアップ処理がWebサーバープロセスに資源を譲る速さを測定 実験方法 http_loadにて8並列でミラーリング元へ負荷をかけ、throughputを計測 実験環境 ミラーリング元、先: AMD Athlon 1.8GHz,メモリ 1GB,NetBSD 1.6R Web Client: AMD Athlon 1.8GHz,メモリ 1GB,FreeBSD 4.7R

実験1: ネットワーク流量が多い場合 目的 実験方法 急激な資源使用量上昇への反応を確認 送信された文字列を記録し、送り返すCGI 流量監視によるスケジューリングを加えた効果を測定 実験方法 送信された文字列を記録し、送り返すCGI 単純な処理なので処理時間が短い 相対的にネットワーク流量増大

Progress-based regulation 実験結果1: 流量が多い場合 処理性能比(%) Tottotto Progress-based regulation Schedulingなし (秒)経過時間 図: バックアップ実行中の時間あたりのプロセス処理量 　　バックアップしない場合を0とした比で表現 考察 Tottottoがprogress-based regulationより早くスケジューリング

実験2: ネットワーク流量が少ない場合 目的 実験方法 流量が少ない場合の反応を確認 ファイルを検索し記録した後に送り返すCGI 流量監視のみによるスケジューリングの効果を測定 実験方法 ファイルを検索し記録した後に送り返すCGI 検索には長時間を要する 相対的にネットワーク流量(mbuf使用量)減少

実験結果2: 流量が少ない場合 考察 処理性能比(%) 経過時間(秒) 図: バックアップ実行中の時間あたりの処理量 Tottotto 流量監視のみ Schedulingなし 経過時間(秒) 図: バックアップ実行中の時間あたりの処理量 　　バックアップしない場合を0とした比で表現 考察 ネットワーク流量監視では流量が少ない場合うまく動かない Pbrによるフォローが必要

関連研究 資源監視によるスケジューリング 資源監視によるスケジューリングの難点 対象資源以外のスケジュールは困難 資源ごとにスケジューラを作るのはよくない 個別に実装するのは面倒 協調動作させるのに苦労

関連研究 Progress-based regulation 低重要プロセス プログラムの進捗を報告し、競合時には自主的に停止 Kernelの改造不要 限りある資源を使うプロセスのスケジュールに向かない 統計処理により進捗を判断 競合への対応が遅い データ量が不足するとスケジュールしない Progress-based regulation of low importance processes [Johnら ‘99]

関連研究 Kernel改造を伴うProgress-based regulation 進捗を見てCPU割り当て時間を変更 進捗はリソース処理具合より判断 User landとOSを分離 kernel schedulerへの変更が必要 Kernel改造は万人向きではない Tottottoは改造不要で内部にスケジューラーを保持 A Feedback-driven Proportion Allocator for Real-Rate Scheduling [Davidら ‘99]

まとめ ヒントつきprogress-based regulation (Pbr)の提案 実行時ミラーリングシステムTottottoを作成 Kernel改造不要 実験 流量監視による効果があった ヒントを付けたことでPbrよりも早くスケジュール 流量監視のみでは不十分なことを確認 Pbrによるフォローは重要

今後の課題 ディスクなど他資源の検討 スケジューリングの粒度の検討 ミラーリングの粒度の検討 サーバー以外の用途への応用 パケット単位のスケジューリング 細粒度でのオーバーヘッドの検討 ミラーリングの粒度の検討 Segment単位よりも細かい単位でのミラーリング