Skip to content

Data Region Allocator

Jump to bottom
Takeru Ohta edited this page Oct 18, 2018 · 3 revisions

CannyLSの一つのストレージインスタンスが管理するディスク領域は、大まかにはジャーナル領域とデータ領域に分かれている。 データ領域にはLumpData群が格納されるが、「新規にLumpDataをPUTする際に、データ領域内のどこに配置するか」を決定するためのコンポーネントとしてデータ領域アロケータが存在する。

データ領域アロケータは、ストレージのブロック単位で割当領域の管理を行う。 対象lumpのデータサイズがブロックサイズと一致していない場合には、内部的にサイズの切り上げが行われ、余剰分は適当なバイト列で埋められることになる。なお、ストレージのブロックサイズの最小値は512バイトであり、lumpのデータサイズがこれより小さな場合には埋め込みlumpを使用した方がディスクの利用効率的には望ましいものとなる。

割当済み領域の表現方法

アロケータは、各lumpデータに対して「40bitの開始位置」と「16bitの長さ」のペアからなる情報を持っている。 ここで、それぞれの値の単位はバイトではなくブロックであることに注意する。 従って、仮にブロックサイズが512の場合には、データ領域の容量としては512TBが、個々のlumpデータとしては32MBが、扱えるサイズの理論上の上限値となる。ブロックが操作の基本単位となるので、この表現により計算領域を節約することができる。

現状の割当戦略

データ領域内の空き領域の割当戦略は、以下の単純なものである:

  • データ領域内の「連続する空き領域」を要素とした集合(実体はBTreeSet)を管理:
    • 「連続する空き領域」の実体は(40bitの開始位置, 24bitの長さ)のタプル
    • 実際には、上記要素の並び順に応じて、「空き領域の開始位置順に並んだBTreeSet」と「空き領域の長さ順に並んだBTreeSet」の二つの集合がある
  • lumpの格納時には ベストフィット方式 で、データの割当先を決定する:
    • 「空き領域の長さ順に並んだBTreeSet」を用いて、データサイズ以上の長さを持つ最小の空き領域を探索し、そこからデータ用の領域割当を行う
    • 要求データサイズと選択された空き領域のサイズが完全に一致した場合には、エントリを(二つの)集合から完全に削除し、そうではない場合に開始位置と長さの更新処理を実施する
  • lumpの削除時には、対象データの格納位置を上記集合群に追加した上で、もし連接する要素(空き領域)の開始位置と終端位置が接している場合には、それらのマージ処理を行う
    • 「両者が接しているかどうか」の判定には「空き領域の開始位置順に並んだBTreeSet」を用いる

なお、領域の割当および解放は完全にメモリ上で完結する処理であり、これに関連したディスクI/Oは発生しない。

ストレージ再起動時の状態復元

ストレージの再起動時には、既に使用済みの領域に対して再割当を行ってしまうのを防止するために、アロケータを再起動前の状態に復元する必要がある。 ただし、ストレージ内にはアロケータの状態を格納(永続化)するための専用領域は存在せず、ジャーナル領域内のレコード群を走査することで復元するような仕組みとなっている。

具体的には、ジャーナルのPUTレコードには、対象lumpのデータの「格納開始位置」と「長さ」が記録されているので、アロケータの割当ログと見做すことが可能となっている。

具体的には、以下のような流れで、アロケータの状態の復元が行われる(※ 実際のコードはもう少し最適化されている):

  1. データ領域内の全てを空き領域とした状態(i.e., 格納lumpが0)でアロケータを初期化
  2. ジャーナル領域内の全ての有効なPUTレコード群を読み込む
  3. 各PUTレコードを走査し、それが示す範囲を、アロケータが管理する空き領域集合から除去していく
    • 格納済みの全lumpに対して疑似的に、以前のデータ領域割当を再現している、とも見做せる

課題

現状の割当戦略には、データ領域のフラグメンテーションの防止対策が存在しない、という問題が残っており、理論上は格納されているlump数と同じだけのフラグメンテーションが発生し得る（実際にはここまで悪くなることはまずないはずではあるが）。 フラグメンテーションによって、各操作の処理性能が劣化することは無いが、これが多いとアロケータのメモリ使用量が増え、ディスク容量の利用効率も下がってしまう。

対策としては、以下のようなものが考えられる:

  • (a) CannyLSの利用側でフラグメンテーションが(あまり)発生しないような使い方をする
    • 極端な話、lumpデータのサイズが全て等しいのであれば、フラグメンテーションは一切発生しない
  • (b) デフラグ機構を実装する
    • 完全にフラグメンテーションを解消することが可能（デフラグ完了直後）
    • ただし、CannyLSは大容量HDDを主対象としており、デフラグに要する時間もかなり長くなると想定されるため、使い所が難しい可能性がある
  • (c) 割当戦略を工夫する
    • 今よりもフラグメンテーションの発生を抑止できる割当アルゴリズムがあるかもしれない

Contents:

Clone this wiki locally