テストステ論

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

(writeboost report) ログの設計とログリプレイアルゴリズム

writeboostは, SSD上に書かれたセグメント列から, しかるべき状態を再構築する必要がある.

また, 性能/寿命の面から, 以下を実現したい.

  1. RAMバッファが揮発であっても, キャッシュデバイスに対する並列フラッシュは出来るようにしたい. 並列にフラッシュ出来るという特性は, それをするしないに関わらず, 設計が単純な原理に支えられていて, 柔軟であることを意味する. 並列フラッシュは, 高スループットなフラッシュデバイスを最大限に利用するために必要である(512KBをシングルで同期ライトし続けるだけでは酷使が足りない. ただし, そんな超絶領域を狙うものであるかはそもそも目的が微妙だが, 楽しい実験データをとるためには必要).
  2. バッファのフラッシュは, FUAライトしない.
  3. ライトをするごとにスーパーブロックを更新するなど, 無駄なライトはしない. セグメントに直列に書かれたデータのみから, それらをどのようにリプレイすべきかを判断する.

以下, セグメントについて分かっていることを雑記式に列挙する. 妥当な限りあらゆるSSDのFaultに対して破綻しない論理を構築する必要がある.

  1. SSDに対してシーケンシャルに書き, その順番にACKされたとしても, 電断後には途中のセグメントが不完全(不完全かどうかは, チェックサムで判定)となる可能性がある.
  2. 従って, セグメントを並列にフラッシュした場合, この領域で, セグメントが部分的に不完全(穴あき)となる可能性がある.
  3. バッファ数以上の並列フラッシュは不可能であり, バッファ数は全セグメント数よりも小さい. 自然な仮定.
  4. 不完全なデータをリプレイしてはならない. 上位でメタデータ不整合が起こる可能性がある.
  5. セグメントを再利用した時点でこれらのセグメントはcleanになっている(すでにライトバックされている).
  6. 永続化ACKを返したデータについてはもれなくリプレイする必要がある.
  7. 永続化ACKされた領域に対して新しいセグメントが穴あきになった場合, 並列フラッシュを行った区間の永続されたセグメントは, 「すべて無視する」必要がある. ライトバックされているのでリプレイする必要がない. 中途半端にリプレイすることが害.
  8. セグメントはatomicとは限らない. データブロックのみが中途半端に書かれていることがある. ヘッダのみが書かれている場合もある.
  9. 1セクタ(512B)ライトはアトミックである.
  10. ある時点で永続化ACKを返した場合, それ以前のセグメントは永続化されている (#1)
  11. 逆にいうと, 永続化されていない場合にのみ, セグメントが穴あきである可能性がある.
  12. 永続化されなかったが, バッファ上からたまたまチップに書き込まれて残ったデータは, リプレイしてもしなくても良い.
  13. 従って, 「完全なセグメントはリプレイする」で統一出来る (#2)
  14. 上位は, ディスク上で順序付けしたいものについては永続化命令を使う必要がある. これをしていないのだから, セグメントの順序性も保存する必要はない.
  15. 穴あきセグメントの議論は, 仮にフラッシュ数の上限を1とした場合は, 「利用するSSDがACK順にライトバックすることを保証していないならば, writeboostで包んだところでこれは保証されない」という意味になるが, 並列にフラッシュした場合はACK順が非決定的なので, SSDのバッファ上でもセグメントがシーケンシャルにACKするとは限らない(しかしその確率は現実的にいうとほぼ100%).

すべてを踏まえる必要があるかどうかは分からないが, 私の頭が考えだした最善のリプレイアルゴリズムは以下,

flush_all_presistent_buffers() # バッファが不揮発の場合, まずこれをフラッシュすることが簡単.
max_id, max_idx = find_max_id(cachedevice) # 最大のidを見つける
start_idx = (max_idx + 1) % nr_segments # この右横から始める
for i in start_idx ... start_idx + nr_segments:
  j = i % nr_segments
  seg = read(cachedevice, j)

  # 不完全なものは無視. それ以外を取り込む.

  if seg.id == 0 # idが0のものはそもそも何の書き込みもされていないので不完全
    skip
  checksum = calc_checksum(seg)
  if seg.checksum != checksum: # チェックサムは, crc32cを利用. btrfsも利用.
    skip

  update_by_seg(seg) # 無事に検査されたセグメントのみを取り込み.

最大のidの右から始めれば良い理由は以下である.

  1. もし, 全部完全にフラッシュされていた場合(正常なシャットダウン時など), 最大のidの右横は, id=0あるいは, 一番古いidである.
  2. 並列フラッシュをしていた場合, 最大idの右横はid=0あるいは, 不完全なセグメントか, 一番古いidである(永続化されたかは知らないが, 上記(#2)によって, 取り込めば良いことが分かる).
  3. 例として, すでに永続されている連続領域(永続化されたセグメントは中途半端にリプレイ出来ない)に対して, 5並列で書き込み途中で電断したとする. この時, この領域の状態[x x 5 6 x], [x 4 x 6 x], [x x x 6 7] いずれも正しく動くことが分かる.
  4. 仮に, [x x 5 6 x]のうち, 5で永続ACKしていた場合, 先頭の2つが不完全であることはあり得ない(#1)ので, [3 4 5 6 x]となるはずである. この場合も, 最大idの6の横から始めて, 最終的にローテーションして6までリプレイすれば永続化されたセグメントも過不足なくリプレイ出来る.

並列フラッシュの実装, チェックサムの実装については別に書く.