テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(writeboost report) ライトブーストのロック設計

ライトブーストの実装はフィックスしたと言っても過言ではない. そこで, ロック設計について説明しようと思う.

ライトブーストで難しいのはこの点だ. 理由は以下

  1. RAM buffer - SSD - HDD という多層を制御する.
  2. SSDのシーケンシャル性能を完全に活かすためには, CPU部分のオーバーヘッドはほぼゼロとする必要がある.
/*
 * (locking) dirtiness
 * a cache data is placed either on RAM buffer or SSD if it was flushed.
 * to make locking easy,
 * simplify the rule for the dirtiness of a cache data.
 *
 * 1) if the data is on the RAM buffer, the dirtiness (dirty_bits of metablock)
 *    only "increases".
 *    the justification for this design is that
 *    the cache on the RAM buffer is seldom migrated.
 * 2) if the data is, on the other hand, on the SSD after flushed the dirtiness
 *    only "decreases".
 *
 * this simple rule can remove the possibility of dirtiness fluctuating
 * while on the RAM buffer.
 * thus, simplies locking design.
 *
 * --------------------------------------------------------------------
 * (locking) refcount
 * writeboost two refcount locking mechanism
 * (only one if not using plog)
 *
 * the basic common idea is
 * 1) increment the refcount with lock for serialization
 * 2) wait for the decrement outside the lock
 *
 * process_write:
 *   prepare_write_pos:
 *     mutex_lock (to serialize buffer write)
 *       inc in_flight_ios # refcount on the dst segment
 *     mutex_unlock
 *
 *   process_write_job:
 *     wait_event (to serialize plog write)
 *       inc in_flight_plog_writes
 *
 *       # submit async plog write
 *       # dec in_flight_plog_writes in endio
 *       append_plog()
 *     wake_up
 * 
 *     # wait for all async plog writes complete
 *     # not always. only if we need to make precedents persistent.
 *     barrier_plog_writes()
 *
 *     dec in_flight_ios
 *     bio_endio(bio)
 */

昨日, 私はコメントにこれを記した. 詳細に説明しよう.

dirtinessについて

4KBキャッシュブロックを管理するmetablockというオブジェクトにはdirtinessという値が定義される. これは, 1sectorごとのdirty bitである. 実装では1byte(8bit)のデータで表現されている. これについて, 単純な規則を設けている. RAM bufferがwbflusherにqueueされるまでの間は, そのRAM bufferに所属するmetablockのdirtinessは単調増加することにしましょうということだ.

これは「本来ならばdiritnessを減少出来るケースもあるが無視する」ということを意味する. dirtinessの減少を無視することは論理的に破綻しない. 単に, 本来あるべきdirtinessが消えてしまうと問題である.

SSDに書きだされたあと, metablockのdirtinessは単調減少する. これは自明である. ライトブーストのライト窓口はRAM bufferだけなので, SSDに書きだされてしまえばもはやdirtinessを増加させる手段は存在しない. しかしこの単調特性もロッキングに利用している.

ライトブーストは複数のmetablockをまとめて非同期ライトバックする. この特徴がライトバック性能に大きく貢献するため, ライトブーストの層を一枚挟むだけでHDDをただ使った場合よりライトバック性能が高くなることがある. これはファイルシステムから発行されるライトバリアをSSDキャッシュの層でさばいているため, ライトバック時にはこれを気にせずにHDDに対して単に非同期ライト出来るという特性を活かしている(特にplog使用時にはこの特性が顕著になる).

ライトバックはバックグラウンドで動作する. しかし, foregroundでもmetablockはdirtinessを減少され続けている可能性がある. 私はこれを止めることは理に適わないと判断した. 例えば4Kフルの上書きライトがあった場合に, 古いキャッシュはライトバックせず単に捨てられる(メモリ上のメタデータの変更で済む)はずである. マイクロソフトのGriffinなど, この特性を活かした研究してライトバックを減らす研究例も存在するため, ライトブーストとしてもこの挙動を排除するわけにはいかないと判断した(現実的にも上書きライトは頻繁に起こるものである).

ここで一連のmetablockをライトバック対象を判断したものとして, foregroundでもdirtinessが減少している可能性を考えた時, どの瞬間のdirtinessを採用するのがもっとも良いだろうか?それは時間軸上過去のモノであれば何でもいい(これをライトブーストではdirtiness_snapshotと呼んでいるが, saved_dirtinessくらいの方が適しているかも知れないと今気づいた). なぜならばdirtinessは「単調」減少しているから. 「もっとも汚れているものをライトバックすればデータは失われない」は自明であろう. 場合によっては同じブロックを2度ライトバックすることがあり得るが, それは大したロスではない(某企業にいると, こういう判断をするにしても多大なリーズニングが必要となる. バカバカしいことこの上ない).

以上, ライトブーストは, metablockのdirtinessに関して単調増加/減少を仮定することによってdirtinessのゆらぎによってダーティデータを失うことを防いでいる.

参照カウント

ライトブーストは, 「ロックの中で参照カウントをincして外でdec」パターンを2回使っている.

ただし意図は異なる.

最初の参照カウントはio_lockというmutex_lockの中でとる. この意図は「そのsegmentは今利用中なので勝手に上書きしてデータ消したりしないでね」というものだ. 例えば, RAM bufferにデータを全部書き込むまではwbflusherに対してqueueして欲しくないとか. readをそのキャッシュブロックに対して発行したので, ACKするまでは上書きしてくれるなとか.

次の参照カウントは, plogを利用している時限定であり, plogに対して発行した非同期ライトをカウントするものだ. waitqueueによってシリアライズされた排他区間でincする(今気づいたがこれが本当に必要かどうかわからなくなってきた. どうせ非同期発行してるのだから). plogに対して毎回同期ライトすると, plogとして利用するデバイスによってはまるで性能が出ないので非同期ライトして, 必要な時だけ永続化することにした. SSDを数MBと残りすべて(例えば200GB)の2パーティションに分割し, 前者をplogとして使うだけで仮想マシン上でやってもこれが50MB/secくらいは安定して出るようになる. 安定して出るというのがポイントだ. 50MB/secのランダムライトを出すのは, HDDを並べた場合いくらかかるだろうか?50台では足りない. plogからackした時点でかなりの確率でデータが残るはずなので, RAM bufferしかない時よりも, (永続化していないデータについても)残る確率が上がる(別に残さなくてもいいだけど, 残した方がベター).

用途によってはplogはない方が良い場合もある. plogを使うかどうかは初期化時に決めることが出来る. 「データが吹っ飛んでもあんまり問題ない. バリアとかあまり発行しない」ケースではplogなしでぶっ飛ばしてもいいと思うが, ふつうのファイルサーバなどでは, plogを使った方が良いだろうと思う. 永続メモリがあったら性能的になおベターだが, なくてもまぁまぁの性能を出すことは出来る.


(番外編)

waitqueueのwake_upをする場合, waitqueue_activeで「待ってるプロセスがいるか」を調べてからwake_upするイディオムがアップストリームコードの中からはたくさん見つかる. これは「ほとんどの場合はキューされてないはずだが論理的には一応待たないといけない」ケースではより効果的だ. そしてライトブーストのケースはまさにそれである. ちゃんとカウントしているわけではないが, ライトブーストで使っているwaitqueueはすべて, ほとんどの場合はwaitしない. 待つ確率は1%もないと思う. 従って, ほとんどの場合は, 以下のコードでwake_upまで到達しない. これを明示的に示すためunlikelyをつけた方がいいかも知れない.

static void wake_up_active_wq(wait_queue_head_t *wq)
{
    if (waitqueue_active(wq))
        wake_up(wq);
}