Journal Region GC

CannyLSはインクリメンタルにジャーナル領域のGCを行っているので、その具体的な方法について説明する。

前提知識

ジャーナル領域は、リングバッファ形式でレコード群を保持している
- リングバッファは、HEAD位置とTAIL位置を管理
- HEAD位置は、先頭レコードの位置を示す
- 新規レコードはTAIL位置に追記され、その際にはTAIL位置も(新規レコードの末尾を指すように)更新される
レコードは、末尾に追加され続けていく
リングバッファのサイズは有限なので、いつかは古いレコードの回収(i.e., GC)が必要となる
- 操作的には"GC"とは「HEAD位置を進めていく」ことに対応する

以下のレコードは、GCによって回収可能と言える:

次の条件を満たすPUTレコード:
- 後方にlumpIDが等しいPUT/EMBED/DELETEレコードが存在する
- => 要するに「既に削除ないし上書きされている」なら不要ということ
次の条件を満たすEMBEDレコード:
- 後方にlumpIDが等しいPUT/EMBED/DELETEレコードが存在する
- => 要するに「既に削除ないし上書きされている」なら不要ということ
次の条件を満たすDELETEレコード:
- 前方にlumpIDが等しいPUT/EMBEDレコードが存在しない
次の条件を満たすDELETE_RANGEレコード:
- 前方に対象範囲に含まれるlumpIDを有するPUT/EMBEDレコードが存在しない

※ 上記以外の制御系のレコードは、GCの対象に含める必要がないので考慮しない

以下のようにしてGCを実施する:

(1) リングバッファの先頭(HEAD位置)のレコードを読み込む
(2) レコードの種類に応じて、回収可能かどうかを判定:
- PUT/EMBED:
  - 「該当のIDを持つlumpがストレージ内に存在する」かつ「データの格納位置が一致する」なら回収不可
  - それ以外は回収可能（削除済みないし上書き済み）
- DELETE/DELETE_RANGE:
  - 常に回収可能
  - 「リングバッファの先頭」という時点で、常に前節の条件を満たしているため
(3) 回収不可能な場合には、そのレコードをリングバッファの末尾に追記(再配置)する
- 各lumpは互いに独立しているため、生存しているlump用のPUT/EMBEDレコードは、リングバッファ内の任意の位置に移動可能
- 回収可能なレコードは、再配置を行わないことで、次のステップで暗黙的に回収される
(4) HEAD位置を(次のレコードの先端に)進めることで回収を行う
- また、ジャーナル領域のヘッダ部に存在する Head Position の値も更新する
- なお「対象レコードの再配置後」かつ「このヘッダ部の更新完了前」にプログラムがクラッシュした場合には、リングバッファ内に同一のPUT/EMBEDレコードが二重に存在する状態となってしまうが、これによる問題は特に発生しない
  - PUT/EMBEDレコードは冪等であるため

前節の方法を素直に実装すると、ディスクI/Oが多くなり効率が悪いため、実際には以下のような最適化を適用されている:

先端レコードの読み込みをまとめる:
- 「一度に一つ」ではなく、数百～数千程度をまとめて読み込んでしまう
- また、ジャーナル領域の容量に余裕がある場合には、GC用の読み込みを行うのは、I/O使用率が低い時のみとする
GC用の再配置を、通常のレコード追記にまとめる:
- 前節の方法で「回収不可能」と判明したレコードは、リングバッファの末尾に再配置を行う必要がある
- ただし、それを即座に行うのではなく、通常のレコード追記と合わせて実施することで、シークや書き込みの回数を減らすことが可能となる
Head Position の更新を遅らせる:
- GCの度に、ジャーナル領域のヘッダ部を更新していると、シークや書き込み回数が増えてしまう
- 幸いなことに Head Position の更新を行わなくても、容量面以外での問題は発生しない
- そのため Head Position の更新を都度都度ではなく、ある程度まとめて行うようにする

上の対策を実施することで、GCのコストを(通常操作時に必要となるI/Oコストの中に)償却し、事実上無視可能なレベルに抑えることができるようになる。

Contents: