要約

  • Mendel Rosenblum と John Ousterhout の Sprite LFS は、細かなランダム書き込みを大きなシーケンシャル転送へ変えたが、無効になった旧版は後で回収しなければならなかった。
  • 1992年論文の「write cost」は、クリーナーが読み出し、再配置する生きたデータまで新規書き込みの費用として数えた。
  • 後続研究は条件を明らかにした。真のアイドル時間があれば回収は背後で進むが、容量が埋まり、ランダム更新が増え、余裕が消えると負債は利用者の待ち時間へ戻る。

追記の完了と仕事の完了

アプリケーションに成功が返った瞬間、書き込みは終わったように見える。しかしストレージ内部では、古い版がまだ場所を占め、クリーンなセグメントの在庫が減り、障害時にはどの版が最新かを再構成する必要が残る。応答時間は入口の状態を示す。循環全体の健全性までは示さない。

Mendel Rosenblum と John K. Ousterhout が1992年に発表した LFS は、この見えない後半を設計の中心へ引き出した。Berkeley の Sprite プロジェクトは、ファイルデータとメタデータの変更をバッファーし、まとめて大きなシーケンシャル転送として書いた。同期的で小さなランダム書き込みを、非同期の長い流れへ変換したのである。

読み出しのためにログ全体を走査するわけではない。通常の索引が現在のブロックを指し、inode map が各 inode の現位置を持つ。ログは配置の規則であり、ランダムアクセスを放棄する仕組みではなかった。

更新時には古い場所を上書きせず、新しい版を末尾へ置く。旧版は無効になるが、物理的には生きたブロックの間に残る。ログが一周した後、散らばった穴へ直接書けば、せっかくの連続書き込みが崩れる。そこでディスクを大きなセグメントへ分け、セグメント単位で空きを作った。

クリーナーが請求書をまとめる

セグメントクリーナーは候補を読み、まだ有効なブロックだけを選び、別の場所へ詰め直し、元のセグメントを解放する。segment summary には各ブロックのファイルと論理位置が記録され、現行メタデータとの比較で生死を判定する。この要約は、クラッシュ後にチェックポイントから先をたどる際にも使われる。

候補セグメントの利用率が費用を左右する。ほとんど死んだセグメントなら、少量のコピーで大きな空きを得られる。大部分が生きていれば、大量に読み書きしても少ししか空かない。したがって未使用容量は単なる遊休資産ではない。安い候補を選ぶための自由度である。

論文はその費用を write cost として表した。分母は新しいデータ量、分子はその受け入れに必要な総 I/O で、クリーナーの読み出しと生存ブロックの再書き込みを含む。1なら新規データ以外を動かさない理想状態、10なら生データに使える帯域はおよそ10分の1になる。前面の速さだけで設計を評価させない指標だった。

どのセグメントを選ぶかには未来の推定が入る。単純な greedy 法は利用率が最も低いものを選ぶが、局所性があると期待ほど良くなかった。冷たいデータが半端なセグメントへ残り、熱いデータは移した直後に再び更新されるからだ。cost-benefit 法は利用率と最も若いブロックの年齢を組み合わせ、おおよそ (1-u) × age / (1+u) で順位を付けた。

年齢は安定性の代理でしかない。それでも、冷たいセグメントは多少生存率が高くても一度整理し、熱いものは十分に空くまで待つ、という区別ができる。論文のシミュレーションでは、対象負荷において greedy 法より write cost が最大で半減した。一方、負荷の性質が変われば、昨日の「冷たい」は今日の再コピー要因になる。

ベンチマークから外れていたもの

原論文のマイクロベンチマークにはクリーニングが含まれていない。入口の最良値を示したのであって、定常状態を示したのではない。より重要なのは4か月の運用測定である。Sprite の対象環境では write cost は約1.2から1.6、長期の書き込み性能は最大シーケンシャル帯域のおよそ70%と報告された。

稼働コードから得た強い証拠だが、あらゆる装置と負荷へ適用できる定数ではない。著者らも経験の限界を明記した。復旧にも別の収支がある。チェックポイントで inode map の基準を定め、後続セグメントを roll forward する。間隔を短くすれば通常時の仕事が増え、長くすれば障害後の走査が増える。書き込み応答、チェックポイント、復旧時間は関連していても同じ証明ではない。

BSDが示した反対側

Margo Seltzer、Keith Bostic、Marshall Kirk McKusick、Carl Staelin は BSD に LFS を実装した。そこで見えたのは一方的な勝利ではない。従来型ファイルシステムもクラスタリングを改善すると一部の差を埋められた。LFS の優位はメタデータ処理と多数の小さなファイルで明瞭だったが、大きなファイルでは同程度だった。

1995年の比較では、試験ディスクが50%使用の時点でもクリーナーの負荷によりトランザクション性能が33%以上低下した。先行測定の最大40%低下にも触れている。別のヒューリスティック研究は、最も忙しいシステムでクリーニングの97%をバックグラウンドで実行できたと報告した。

この二つは両立する。バックグラウンドとは支払いの時間帯であり、費用の不存在ではない。実際の空き時間があれば需要と競合する前に処理できる。連続流入でクリーンな在庫が減り、空き時間が消えれば、同じコピーが前面の性能を奪う。

その後の adaptive LFS は適地をさらに限定した。頻繁な小規模書き込み、キャッシュが吸収する読み出し、十分なアイドル時間は有利である。満杯に近いディスクでのランダム更新と少ない空き時間は不利である。セグメントサイズや方針を変えれば境界は動くが、交換条件は消えない。

Ousterhout の仕事を「シーケンシャルは速い」で終わらせると、重要な部分を失う。Rosenblum と Sprite チームが残したのは、簡潔な入口と、先送りされた仕事を追跡する会計だった。追記の記録は一段階の採用事実を示す。クリーンな余裕、回収済み空間、復旧可能性は別の現実を示す。

出典