読者です 読者をやめる 読者になる 読者になる

WalB こぼれ話: プロトタイプの性能問題解決

Linux アドベントカレンダー プログラミング

「サイボウズ・アドベントカレンダー2012」も、今日を入れて残り3日となりました(これまでの記事一覧)。


はじめに

こんにちは,サイボウズ・ラボの星野です.

私は先日開催されました WebDB Forum 2012 にて,ブロックデバイス(ストレージ) のバックアップとレプリケーションを効率化する Linux カーネルデバイスドライバ「WalB」についての発表を行いました.

発表内容につきましては,資料を SlideShare にて公開しておりますので,こちら をご覧下さい.

発表の中で私は,WalB プロトタイプの性能評価を行った結果,オーバーヘッドが小さいことを示すグラフを提示しました.ただし,最初からこのような性能が出たわけではありません.初めてプロトタイプを動かして性能データのグラフを見たときは,「最初からうまくいくわけないよね」と思いながらも期待と現実の差にがっかりしました.

本エントリでは,そのような状態から性能問題を解決するまでの道程をご紹介しようと思います.特別な方法論があるわけではなく,仮説検証の考え方で問題解決を図ります.

出来たてのプロトタイプ性能

まずは,こちらの性能グラフをご覧ください. 4KBランダムライト 改善前 4KBシーケンシャルライト 改善前

WalB プロトタイプが動作するようになり,性能評価実験を初めて実施したときの, SSD を使った 4KB ランダムライトと 4KB シーケンシャルライトの性能です.横軸は並列度で,縦軸はスループット(IOPS) です.

赤い線で示した凡例「base」は SSD の素の性能を示しています.WalB には 2 種類のアルゴリズム「easy」と「fast」があります.それに,アクセス領域が重複する IO を直列化する制御を入れた「easy-ol」と「fast-ol」の,計 4 つのバリエーションがあります.残りの凡例は SSD を 2 台 (ログ用とデータ用) 用いてそれらの WalB デバイスを構成したときの性能を示しています.

一般に,並列度が高くなればスループットは増加し,ストレージの処理能力の限界に達すると頭打ちになります.「base」のグラフはその傾向を示しています.ところが,「fast」,「fast-ol」では並列度があがったときに不自然な性能低下が見られます.このままでは使い物になりません.どこに問題があるのか,どうすれば改善するのか(しないのか),突き止める必要があります.

解決への道

このようなとき私は以下の 4 点を心掛けて問題解決に取り組むようにしています.

  • 観察する
  • 可能性を絞り込む
  • 仮説を立てる
  • 検証する

これから,この方法論にそって,性能が出ない原因を突き止めていきます.

観察する

ソフトウェアが相手の場合,直接は目に見えないものが多いので,必要に応じて,能動的に現象を起こしたり,データを取得して加工したりすることによって事態を把握することが多々あります.最初に示した性能グラフもそのひとつで,特に並列度に応じて性能がどのように変化するかは,ストレージの性能特性を知るために最も重要な指標であるため,これをじっくりと観察します.

ランダムライトにおいて,並列度が低い領域では,並列度が上がると性能も上がる傾向が見られますが,あるところ(並列度 2 または 4)から「fast」と「fast-ol」の性能は大きく落ち込んでいます.シーケンシャルライトでも同様に「fast」そして「fast-ol」の性能が落ち込んでいることが分かります.これは,並列度が上がると性能も上がる,という一般的な挙動と異なります.これを「不自然な」性能低下と感じたわけです.また,並列度が高い領域において「easy」と「easy-ol」,「fast」と「fast-ol」の性能差も目立ちます.

可能性を絞り込む

観察の結果,性能低下の原因は直列化処理か,重複 IO 処理に絞られると考えました.前者については,WalB のライト IO の処理の多くは直列化されていますが,その中に,並列度が高くなるとオーバーヘッドが大きくなるものが存在する可能性です.後者については,「easy」 とそれ以外の実装の大きな違いは重複 IO 処理なので,その中に原因が存在する可能性です.

仮説を立てる

直列化処理または重複 IO 処理に関するもので,かつ並列度が高くなったときにオーバーヘッドが大きくなりそうな実装部分を思いつくまま列挙します.その結果,5 個の仮説が出てきました.

  • (1) チェックサム計算
    WalB はクラッシュリカバリ時のログ永続化確認のため,データのチェックサムを計算します.現時点の実装においてチェックサム計算処理は直列化されているので,並列度が高くなるとチェックサム計算が積み重なってレスポンスが悪化し,性能が下がるのではないか,という仮説です.
  • (2) 最大ログサイズ
    ログヘッダサイズは物理セクタサイズ(512Bもしくは4KB)固定です.ひとつのログにまとめる IO は多い方が容量効率は良いのですが,並列度が高いからといってログをまとめすぎると,レスポンスが悪化し,性能が下がるのではないかという仮説です.
  • (3) 重複検出
    アクセス領域が重複する IO を検出する処理は,mutex lock によって直列化されており,並列度が高くなると滞留する IO が増え,重複検出コストも増えるのではないか,という仮説です.
  • (4) Mutex lock の排他時間
    Spin lock と違い mutex lock のクリティカルセクション内ではコンテクストスイッチしても良く,便利に使えます.しかし,コンテクストスイッチしたときのペナルティが大きいため,並列度が高くなったときにこれがオーバーヘッドとして無視できなくなるのではないかという仮説です.
  • (5) Workqueue
    Workqueue は関数とデータを渡すと直後もしくは与えられた時間経過後に実行してくれる便利な機構です.プロトタイプはこれを頻繁に利用していますが,これの使い方などが悪くて並列度が高いときに性能が出ない可能性があります.ただ,この時点で具体的な仮説を立てられるほど workqueue のことを知らなかったので,上記の仮説がどれも間違っていたときにこれを疑うことにしました.

(1)(2)(3)(5) は直列化処理に関するもので,(3)(4) は重複 IO 処理に関するものです.

検証する

ひとつひとつ検証していくのですが,その前に優先順位を考えます.検証にかかる予測コストと,仮説がどのくらい正しいのかという期待に基づいて,コスト対効果が高そうなものから検証します.私は,上記で列挙した順に確かめていくことにしました.

  • (1) チェックサム計算
    チェックサム計算は実用では不可欠ですが,性能を測定するだけならチェックサムの計算を省いたものも用意できます.それらを比較すれば,チェックサム計算のオーバーヘッドを検証できます.

    結果,性能はほとんど変化しませんでした……ハズレです.この実験設定では無視できるほどのオーバーヘッドしかなかったようです.チェックサム計算のみ実行したところ,1MB の計算に 300μs かかりました.4KB あたり 1.2μs となり,ゼロではありませんが,SSD を使った場合の IO レスポンスの中で占める割合は低いようです.

  • (2) 最大ログサイズ
    ログサイズを制限するパラメータを設け,それを変化させて同じ実験を行い,性能を比較することで,最大ログサイズの影響を検証できます.

    結果,性能はほとんど変化しませんでした……ハズレです.後で判明したことですが,IO の出方を別の方法で観察すると,DIRECT IO を使っている場合,たとえ並列度が高くても IO はほとんどまとめられていませんでした.先にそちらを確かめるべきでした.

  • (3) 重複検出
    重複検出アルゴリズムのために,IO の先頭アドレスをキーにした key-value 構造を使っています.key-value 構造の範囲走査を用いて重複の可能性のある IO を絞り込んでから,実際に重複するかどうかをひとつひとつチェックします.当時の実装では,事前の絞り込みが甘く,チェック対象が多いことを問題だと感じていました.その実装を改善することで,無駄な重複チェックが問題かどうか検証できます.

    結果,性能はほとんど変化しませんでした……ハズレです.走査量は減っているはずなのですが,key-value の範囲走査コストは,(1) と同じく相対的に小さかったものと思われます.

  • (4) Mutex の排他時間
    重複検出データ構造の排他のため,最初は spin lock を使っていました.その後,クリティカルセクション内でコンテクストスイッチする可能性のある関数を使わざるを得なくなったため,仕方なく mutex lock に変えたのですが,さらにその後,その関数は自作の別関数に置き換えられており,spin lock に戻すことができる状況でした.これを spin lock に戻して性能を測定することで検証できます.

    結果,劇的に性能が改善しました :) 事前の予想通り,並列度が高くなると,IOPS も徐々に増加し,そのうち頭打ちになる様子が観測されました.万歳!

  • (5) Workqueue
    (4) で解決したので,これについては今回調査,検証しませんでした.

以下,改善後の性能グラフです. 4KBランダムライト 改善後 4KBシーケンシャルライト 改善後

結論として,重複 IO 処理の直列化のために,spin lock ではなく mutex lock を使用していたことが,並列度が高くなるにつれ IOPS が激減していた原因だったと言えます.

より深く知る

さて,問題は解決したのですが,mutex の一体何がどういけなかったのでしょうか.立てた仮説は Mutex lock が spin lock と異なりクリティカルセクション内でのコンテクストスイッチを許すためペナルティが大きい,でした.その振る舞いをより詳細に観察するために簡単なカーネルモジュールを作って実験してみました.具体的には,以下のコードを 8 並列で実行しました.

for (i = 0; i < 250; i++) {
    mutex_lock(&shared_mutex_);
    SLEEP();
    mutex_unlock(&shared_mutex_);
    msleep(8);
}

SLEEP() については,以下の 6 通りで評価し,総実行時間を測定しました.

id SLEEP() 総実行時間(秒)
(1) udelay(4000) 8.03
(2) udelay(8000) 16.20
(3) msleep(3) 16.02
(4) msleep(4) 16.01
(5) msleep(5) 24.24
(6) msleep(8) 24.01

udelay(us) はコンテクストスイッチしません.
msleep(ms) はコンテクストスイッチします.
また,実験をした Linux kernel の tick は 4ms の設定でした.

250 回ループする処理が 8 並列ですから,計 2000 回が実行されることになります.総実行時間が 8 秒の場合,クリティカルセクションあたりの実行時間は 4ms ということになります.(1) (2) はクリティカルセクションあたりの実行時間が 4ms および 8ms であり,クリティカルセクションの中でコンテクストスイッチが起きていないことを示しています.(3) (4) はクリティカルセクションあたりの実行時間が 4ms だと期待したけれども 8ms で,(5) (6) は 8ms と期待したけれど,12ms でした.つまり,msleep() を使った場合は 4ms 余分にかかっていることになります.

これの意味するところは,mutex lock を使うと,クリティカルセクションが 4ms よりも遥かに短い時間で終わることが期待されていても,クリティカルセクション内でコンテクストスイッチが発生した場合,最低でも 4ms 余計に mutex lock を掴んだままになるということです.これは我々の要求に対して遅すぎます(SSD の IO レスポンスは 50us 程度です).並列度が高いと,コンテクストスイッチの頻度も高くなりますので,mutex lock を掴んだまま何もしない時間が積み重なり,IOPS が激減した,というわけです.

めでたし,めでたし.

おわりに

以上が WalB のプロトタイプの性能問題解決までの道程になります.楽々と原因を見つけたかのように見えるかも知れませんが,実際は,1 週間以上この問題に取り組んでいました. 仮説がことごとく崩れさっていくと,やはり不安は増大していきます.それでも,この方法論で問題を解決してきた経験があるからこそ,五里霧中の中を不安ながらも進んでいけたのだと思います.やっとのことで mutex が原因だということが分かったときは霧が消えさり,とても晴れ晴れとした気分になりました.え,mutex を最初に疑っていれば,もっと早く解決できたじゃないかって? その通りです……どこが臭うか当たりをつける,どのくらい怪しいかを見積もる,というのは経験と知識によるところが大きいと思います.私などまだまだだということです.地道に腕を磨いていくしかありませんね.


明日は「WordPress の負荷テストと環境改善」をお送りします。お楽しみに。