Overview

CannyLSは"Canny Lump Storage"の略称であり、"lump"と呼称されるオブジェクト群を格納するための永続ストレージである。

提供する機能

基本的には、単純なKVS相当の操作を提供している:

• lumpの取得 (GET)
• lumpの存在確認 (HEAD)
• lumpの保存 (PUT)
• lumpの削除 (DELETE, DELETE_RANGE)
• 保存済みのlump一覧の取得 (LIST, LIST_RANGE)

また各操作の要求には"デッドライン"が指定可能:

• 要求を受け取ったデバイスは、そのデッドラインに従って要求群のスケジューリングを行う
  • i.e., デッドラインが近い要求ほど、より早く処理される
• これにより、CannyLSの利用者側で各操作の優先度(重要度)が指定可能となる

目標

端的に表現するなら「一台のサーバに数十TB～数百TBのディスクが積まれており、それらに対して均等(ランダム)に読み書きが発生する」という状況を効率的に処理することが目的といえる。

目指すこと

• 中規模程度(数百KB～十数MB)のデータ保管に最適なストレージ
• 大容量HDDの性能を最大限に活用
• ランダムアクセスなワークロードに最適化
• 各操作において、予測可能かつ安定したレイテンシを提供:
  • 発生するディスクアクセス回数を厳密に制御（PUTなら最大二回、それ以外は最大一回)
  • CannyLS層より下の層での不確定要因を極力排除 (e.g., ダイレクトI/Oの使用)
  • バックグランドで(コンパクションやGCのための)巨大なディスクI/Oを発生させない
• 発行されるディスクI/Oの完全な制御:
  • 一つのディスクに対するI/O要求群は、全て一つの管理用スレッドが処理
  • そこで要求の優先度を考慮したI/Oスケジューリングを実施

目指さないこと

• 大量の小規模データ(e.g., 数百バイト)の保存:
  • 保存数が比較的小数(e.g, 数十万程度)なのであれば埋め込みlumpという仕組みが利用可能
• SSDの性能を最大限に活用:
  • SSD使用時の性能が悪い訳ではないが、それ向けに最適化がなされている訳でもない (参考: Threading Model)
• 以下のような機能・特性の提供は上位層(利用側)に任せ、CannyLSは行わない:
  • Compare-And-Swapのような高度な操作
  • キャッシュ層
  • データの整合性保証(バリデーション)
  • データの冗長化

アーキテクチャの概要や構成要素

CannyLSでは、典型的には一つのディスク(e.g., HDD、SSD)に対して、一つの管理用OSスレッドが割り当てられ、それが該当ディスクに対する全ての操作リクエストを一括して管理することになる。
そのOSスレッドが管理する単位は、下記の図の"デバイス"に相当する:
上述の通り、典型的には一つのディスクに対して一つのデバイスが対応することになるので、例えばHDDが四本あるようなサーバでは四つのデバイス(i.e., OSスレッド)が起動することになる。

各デバイスは、利用者から発行された要求群をデッドラインに応じてスケジューリングするためのオンメモリのキューを有している。
キューが空ではない場合には、その先頭から順にエントリ(i.e., 操作要求)が取り出され、ストレージに対して該当の要求で指示された操作が実行されることになる。

ストレージ内には、lumpインデックスおよびデータ領域アロケータと呼ばれるオンメモリデータ構造と、ジャーナル領域およびデータ領域と呼ばれるディスク上のデータ構造、が存在している。

lumpインデックスの実体は「lumpIDをキー、そのデータの格納位置を値」とするBTreeMapであり、保存済みのlumpの一覧はここで一括して管理されている。例えばGET操作の場合には、まずlumpインデックスに対してIDの問い合わせが行われ、もしエントリが存在するなら、その値が示すディスク位置から該当lumpのデータの読み込みが行われることになる。

データ領域アロケータは、新規にPUTされたlumpのデータをデータ領域内のどこに保存するかを決定するためのコンポーネントとなる。

ジャーナル領域は、更新系操作(i.e., PUT、DELETE、DELETE_RANGE)のログを保持するためのディスク上の領域。この領域はリングバッファ形式を取っており、各更新系操作が発行される度に、その末尾に該当操作を示すレコードが追記されていく。またリングバッファが溢れるのを防止するためのインクリメンタルなGC機構も備えている。
上述のlumpインデックスやデータ領域アロケータの状態は、このジャーナルレコード群から完全に復元可能になっており、デバイスの起動時にはレコード全体を走査することで、それらの再構築が行われる。

データ領域には、ストレージに永続化されているlump群のデータが格納されている。CannyLSは、各lumpが中規模程度のデータ(e.g., 数百KB～十数MB)を保持することを想定しているため、それをジャーナル領域に追記されるレコードに含めてしまうとジャーナル領域GC時の再配置コストが高くなってしまうため、データ部分だけは分離して再配置が発生しないように専用の領域を設けている。ただし、例外としてデータサイズが極めて小さなlumpに関しては埋め込みlumpとしてジャーナル領域内に埋め込み可能となっている(これによりPUT時のディスク書き込み回数が一回減らせる)。

CannyLSを使用する場合の典型的な構成では、各ディスク上に巨大な一つのファイルが作成されることになる（拡張子としてはlusfが推奨されている）。そのファイルの形式はストレージフォーマットに従ったものとなり、その中にジャーナル領域とデータ領域も存在することとなる。

各操作の処理の流れ

CannyLSでの計算量やディスクアクセス回数の概観を掴んで貰うために、各操作の処理の流れの概要を記載しておく。 なおいずれの操作に関しても、要求キューから取り出された後の、ストレージ内での処理に関する記述となっている（i.e., 要求のスケジューリング部分は対象外）。 また、ストレージ内での処理は全て同期的に実行される。

GET

• (1) lumpインデックスに、IDの問い合わせを行う: O(log(n = 保持lump総数))
• (2-a) 対応するエントリが存在しなかった場合は、ここで終了
• (2-b) 対応するエントリが存在する場合には、値が該当lumpのディスク上の位置を示している
• (3) lumpのデータをディスク上から読み込む: ディスクREADが一回

HEAD

• (1) lumpインデックスに、IDの問い合わせを行う: O(log n)

LIST、LIST_RANGE

• (1) lumpインデックスから、対象となるlumpのID一覧を取得する: O(log n + (m = 対象lump数))

PUT

• (1) データ領域アロケータに、新規lumpデータ用の保存領域割当を依頼: O(log n)
• (2) lumpインデックスに、エントリ(IDとデータ格納位置)を登録: O(log n)
• (3) データ領域にlumpデータを書き込む: ディスクWRITEが一回
• (4) ジャーナル領域にPUTレコードを追記: ディスクWRITEが一回

※ 埋め込みlumpの場合には(1)と(3)の手順が省略される

DELETE、DELETE_RANGE

• (1) lumpインデックスから、該当エントリ(IDとデータ格納位置)を削除:
  • DELETEならO(log(n))
  • DELETE_RANGEならO(m log n) (m = 該当lump数)
• (2) データ領域から、該当lump用の割当を解放:
  • DELETEならO(log n)
  • DELETE_RANGEならO(m log n)
• (3) ジャーナル領域にDELETEないしDELETE_RANGEレコードを追加: ディスクWRITEが一回

※ 埋め込みlumpの場合には(2)の手順が省略される

バックグランド処理

CannyLSのデバイスは、基本的には利用者からの要求に応じて動作することになるが、一定時間(デフォルトでは100msの間)要求を受信しなかった場合には、デバイスが空いているものと判断して、以下のようなバックグランド処理が実行される:

• ジャーナル領域のインクリメンタルGC（の一単位分）
• ジャーナル領域のメモリバッファのディスクへの書き戻し