他のプロセスに与える影響の 少ない 実行時ミラーリン

他のプロセスに与える影響の少ない
実行時ミラーリングシステム
柳澤 佳里*1 千葉 滋*1
*1 東京工業大学 情報理工学研究科
1
サーバーのディスクバックアップ

YahooやGoogleでのバックアップ作成は困難
• 常時アクセスがある環境でのバックアップは困難
• バックアップ作成中は極度に性能低下
• 繫がらないユーザの[Reload]による輻輳の恐れ

バックアップの災害耐性を持たせるのは困難
• バックアップが手元にあると同時に被災する恐れ
• 遠隔地にバックアップテープを移送するのは手間
2
サーバーのディスクバックアップの要件

実行時ディスクバックアップ
• Incrementalにディスクバックアップを実行
• バックアップ実行の負荷を時間分散
• 時間分散させることで瞬間バックアップ負荷を軽減

遠隔地ディスクバックアップ
• 遠隔地のマシンのディスクにバックアップ
• 災害耐性を持たせる
• e.g. 隣のビルにバックアップし火災によるデータ破損に対処
3
バックアップ処理のスケジューリング

バックアップ処理による性能低下を避けたい
• サーバー負荷増大時にバックアップ処理を休止
• バックアップ処理はサーバープロセスより低い重要度
• サーバーへのアクセスが多いときには変更も多い

競合する資源全てを考慮してスケジュールしたい
• スケジューリングで考慮する資源は多岐にわたる
• ディスクバックアップは多種の資源を使用
4
我々の
Tottottoミラーリングシステム

スケジューリングの工夫
• ヒントつきprogress-based regulation (Pbr)
• ネットワークの使用量をヒントとしたPbr
• Pbrと従来スケジューリングとのハイブリッド
• Pbr: プログラムの進捗を見てスケジューリング
• 特定の資源によらずスケジューリング
• 統計処理を行うので反応が遅い
• 従来型:資源の使用量を見てスケジューリング
• 即応性が必要な資源競合をスケジューリング
• Pbrの遅さをカバー
5
Progress-based regulation (Pbr)

進捗状況のフィードバックによるスケジューリング
• 重要度の低いプロセスは進捗をスケジューラに報告
• 資源を譲る善意のプロセスのためのスケジューリング
• 進捗悪化時:重要度の低いプロセスを停止
• 資源の競合の恐れ
• 進捗良好時:重要度の高いものと同じ資源割り当て

個々の資源の使用量を調べずスケジューリング可
• 資源ごとのスケジューラ作成は不要
6
Progress-based regulationの難点

Pbrは統計処理で進捗を判断
• 適切な閾値を設定するのは困難
• 従来の閾値による動作への反省

急激な資源の使用量の上昇への対応に遅れ
• 統計処理に足るデータ量が必要

量に限りがある資源の割り当てには不向き
• 個々の資源を見ずにスケジューリング
7
資源監視によるスケジューリング

資源使用量を見てスケジューリング
• 閾値を超える変化をした場合に停止
• 即応性のあるスケジューリングが可能
• 量に限りがある資源も適切にスケジュール可能

閾値のチューニングが困難
• うまくスケジュールするには適度な閾値が必要
• 適切な閾値を多数の資源に定めるのは困難

Tottottoではネットワーク流量について閾値を
経験的に定め監視
8
スケジューラの実装

ミラーリングソフトが自主的にスケジューリング
• Kernelの改造が不要
• 資源競合時に
• Usleep(2),Sleep(3)により他プロセスに資源を移譲
• Sleep時間はbinary exponential back-offで増加

ヒントつき Pbr
• ネットワーク流量監視スケジューリングをヒント
• 競合する資源をネットワーク資源(mbuf)と想定
• ネットワークサーバー用途を想定

NetBSD 1.6Rに実装
• LFSが実装されているOS
9
Tottottoにおけるミラーリング

LFSv2/NetBSD対象
• LFS: Log-structured File System,ログ構造のFS
• LFSのブロック(segment)単位でミラーリング
• 前回ミラーリングした箇所との差分発見が容易
• LFSでは追記にてファイルシステムの変更を表現
• 現在書き込み中のsegmentはsuperblockに記録
10
スケジューリングのタイミング

流量監視スケジューリング: segment送信ごと
• ネットワーク使用の直前に使用量を調査
• 混雑時に混雑を助長するのを防止

Progress-based regulation: 差分送信ごと
• 進捗を調べやすいところで進捗調査
• 前回からの差分を求める箇所も調査対象に
• Segment送信ごとだと重み付けが困難
11
提案するスケジューリング法の
効果を見る実験

目的
• バックアップ処理がWebサーバープロセスに資源を譲る速さを測定

実験方法
• http_loadにて8並列でミラーリング元へ負荷をかけ、throughputを計
測

実験環境
• ミラーリング元、先:
AMD Athlon 1.8GHz,メモリ 1GB,NetBSD 1.6R
• Web Client:
AMD Athlon 1.8GHz,メモリ 1GB,FreeBSD 4.7R
12
実験1: ネットワーク流量が多い場合

目的
• 急激な資源使用量上昇への反応を確認
• 流量監視によるスケジューリングを加えた効果を測定

実験方法
• 送信された文字列を記録し、送り返すCGI
• 単純な処理なので処理時間が短い
• 相対的にネットワーク流量増大
13
実験結果1: 流量が多い場合
処理性能比(%)
Tottotto
Progress-based
regulation
Schedulingなし
(秒)経過時間
図: バックアップ実行中の時間あたりのプロセス処理量
バックアップしない場合を0とした比で表現

考察
• Tottottoがprogress-based regulationより早くスケジューリング
14
実験2: ネットワーク流量が少ない場合

目的
• 流量が少ない場合の反応を確認
• 流量監視のみによるスケジューリングの効果を測定

実験方法
• ファイルを検索し記録した後に送り返すCGI
• 検索には長時間を要する
• 相対的にネットワーク流量(mbuf使用量)減少
15
実験結果2: 流量が少ない場合
処理性能比(%)
Tottotto
流量監視のみ
Schedulingなし
経過時間(秒)
図: バックアップ実行中の時間あたりの処理量
バックアップしない場合を0とした比で表現

考察
• ネットワーク流量監視では流量が少ない場合うまく動かない
16
• Pbrによるフォローが必要
関連研究
資源監視によるスケジューリング

資源監視によるスケジューリングの難点
• 対象資源以外のスケジュールは困難
• 資源ごとにスケジューラを作るのはよくない
• 個別に実装するのは面倒
• 協調動作させるのに苦労
Run queues
High
priority
process
process
process
process
process
.
.
.
Low
priority
17
関連研究
Progress-based regulation

低重要プロセス
• プログラムの進捗を報告し、競合時には自主的に停止
• Kernelの改造不要
• 限りある資源を使うプロセスのスケジュールに向かない

統計処理により進捗を判断
• 競合への対応が遅い
• データ量が不足するとスケジュールしない
Progress-based regulation of low importance processes [Johnら ‘99]
18
関連研究
Kernel改造を伴うProgress-based
regulation

進捗を見てCPU割り当て時間を変更
• 進捗はリソース処理具合より判断
• User landとOSを分離

kernel schedulerへの変更が必要
• Kernel改造は万人向きではない
• Tottottoは改造不要で内部にスケジューラーを保持
A Feedback-driven Proportion Allocator for Real-Rate Scheduling [Davidら ‘99]
19
まとめ

ヒントつきprogress-based regulation (Pbr)の提案
• Pbrの反応の遅延をカバー

実行時ミラーリングシステムTottottoを作成
• 流量監視をヒントとする Pbr
• Tottottoが自主的に他プロセスに資源を移譲
• Kernel改造不要

実験
• 流量監視による効果があった
• ヒントを付けたことでPbrよりも早くスケジュール
• 流量監視のみでは不十分なことを確認
• Pbrによるフォローは重要
20
今後の課題

ディスクなど他資源の検討
• サーバー以外の用途への応用

スケジューリングの粒度の検討
• パケット単位のスケジューリング
• 細粒度でのオーバーヘッドの検討

ミラーリングの粒度の検討
• Segment単位よりも細かい単位でのミラーリング
21