Skip to content

Terminology

Takeru Ohta edited this page Oct 21, 2018 · 3 revisions

CannyLS内で使われている用語をまとめたページ。用語の並びはアルファベット順および五十音順。

lump

ストレージへの格納対象となる個々のデータに対する呼称。日本語に訳すと"塊"となる。

各lumpは「128bit長のLumpId」および「最大で約32MBのLumpData」の組となっている。IDおよびデータは単なるバイト列として扱われる。

ストレージ内のlumpに対する各操作(e.g., GET/PUT/DELETE)は、LumpIdをキーとして実行される。

lumpインデックス

ストレージに格納されているlumpのインデックス情報を保持するためのオンメモリデータ構造。実体としてはRustの標準ライブラリで提供されているBTreeMapであり、「キーはLumpId」かつ「値はLumpDataの格納位置情報」となっている。 一つのデバイスに付き一つのlumpインデックスが存在し、そこに対象デバイスに格納されている全lumpの情報が集約されている。

lusf

"LUmp Storage Format"の略称。 CannyLS用に定義されたlump群を格納するためのファイルフォーマットであり、この中にジャーナル領域データ領域が存在する。 フォーマットの詳細はストレージフォーマットを参照のこと。

この形式のファイルの拡張子としては".lusf"が推奨されている。

NVM

"Non-Volatile Memory"の略称。

HDDやSSDのような永続化デバイス(i.e., 電源を切ってもデータが失われない)上で提供されている連続的かつ読み書き可能な領域(アドレス空間)、を意味する。

操作的にはNonVolatileMemoryトレイトの実装物のことを指しており、それらはlumpの保存先として利用可能となっている。

埋め込みlump

通常、lumpのデータはデータ領域に保存されることになる。 ただし、それではデータサイズが小さい場合に効率が悪くなってしまう(ディスク書き込み回数が増えるのと、データ領域での領域割り当てはブロック単位で行われるため容量の活用効率も下がってしまう)ので、PUT操作時にジャーナル領域に追記されるレコード内にlumpのデータを埋め込むことも可能となっている。 そのようなジャーナル領域内にデータが埋め込まれたlumpは"埋め込みlump"と呼称される。

ジャーナルレコード

ジャーナル領域内のリングバッファに追記されているレコード。 PUTやDELETEのような更新系の操作を処理する際には、必ず対応するレコードが追記されることになる。 デバイスの再起動時には、リングバッファ内に保持されている全レコードを走査することでlumpインデックスおよびデータ領域アロケータの再起動前の状態を復元することが可能となる。 具体的にどういったレコードが存在するのか、といったことに関してはストレージフォーマットを参照のこと。

ジャーナル領域

lumpの保存や削除といった更新系操作のログを永続化して保持するためのディスク上の領域。 構造としてはジャーナルレコードをエントリとして持つリングバッファとなっている。 更新系操作が実行される度、対応するレコードがリングバッファの末尾に追記されていき、反対に不要となったレコードに関してはGCのタイミングで回収(破棄)されることになる。 ジャーナル領域の具体的なフォーマットに関してはストレージフォーマットを参照のこと。

ジャーナル領域のサイズは、後から変更することができないため埋め込みlumpを多用したい場合等には、ストレージの構築時に慎重にサイズを決定してあげる必要がある。

ストレージ

lump群を格納するためのストレージ、あるいは、そのインスタンスのことを指す。 典型的には、一つのディスク上にlusf形式の巨大なファイルが生成され、その中のジャーナル領域およびデータ領域を用いて、永続化されたlump群が管理されることになるが、そのlusfファイルが一つのストレージインスタンスとして見做すことが可能。 Overview内の図も参考となる。

プログラム上の構成要素としてはStorage構造体に対応する。

"ストレージ"という用語はデータ構造(lusf)や永続化されているデータ集合を表現する意味合いが強い。実際にそれをプログラム内で使用する際には、対象のストレージインスタンスを管理するデバイスを起動し、それを経由して各種操作を実行することになる。

ダイレクトI/O

CannyLSでは、各操作のレイテンシを安定させたり、要求のデッドラインを考慮するために、独自のI/Oスケジューリング機構を備えている。CannyLS層でディスクに対して発行されるI/Oの正確な制御を行うためには、より低レイヤでキャッシュやスケジューリングが行われてしまうと邪魔なので、ダイレクトI/Oを用いることでOS層でのそういった処理をバイパスするようになっている。

具体的には、Linux環境でO_DIRECTフラグ(参考: Man page of OPEN)、macOS環境ではF_NOCACHEフラグ、を指定してファイルを開いている。

ディスク

HDDやSDD等の物理ディスクのことを指す。

デッドライン

デバイスに対する各操作要求(e.g., PUT、GET)に対して付与可能な優先順位。 該当の要求が「いつまでに処理されてほしいか」をデッドラインとして指定することで、よりデッドラインが近い要求が優先して処理されるようになる。 デッドラインで指定された時刻以内に確実に操作が実施されることを保証するようなものでもなく、指定時刻を超過したからといってエラーとなったりもしないので、単なる時間軸ベースの優先順位、と考えておくのが良い。

プログラム上の構成要素としてはDeadline列挙体に対応する。

デバイス

ストレージに対する操作要求を管理するための構成要素。

プログラム上の構成要素としてはDevice構造体に対応する。 Device構造体は生成時に、Storage構造体のインスタンスを引数で受け取り、それを実行するためのOSスレッドを起動する。 デバイススレッドに対してはDeviceHandle構造体経由で要求を発行することが可能。

APIとしてはStorage構造体を直接操作することも可能になっているが、Device構造体を経由することで、以下のような機能が利用可能となる:

  • デッドラインを考慮したI/Oスケジューリング
  • 複数スレッドからの要求の発行
  • バックグラウンドタスクの実行 (e.g., ジャーナル領域のGC)

データ領域

lumpのデータを格納するための領域。 埋め込みlumpを除いて、ストレージにPUTされた全てのlumpはデータ領域に格納されることになる。 データ領域内のどこに配置するのかはデータ領域アロケータが決定する。

データ領域の具体的なフォーマットに関してはストレージフォーマットを参照のこと。

データ領域アロケータ

ストレージにPUTされたlumpのデータをデータ領域内のどこに配置するかを決定するためのアロケータ。 「現在割当済みの部分領域一覧」の情報をメモリ上に保持している。 アロケータの状態はジャーナルレコード群から完全に復元可能であり、デバイスの再起動時には、レコード群を走査することで以前のアロケータの状態が再構築される。

ブロック

CannyLSではストレージおよびNVMは、内部的には"ブロック"という単位で、データの割当を行ったり、I/O処理を実行している。

用語としては、どちらも"ブロック"という単語が使用されはするが、ストレージとNVMでは、その役割が異なっている。

例えばLinuxの場合では、ダイレクトI/O用にO_DIRECTフラグを指定してファイルを開いた場合、そのファイルに対する読み書き操作では、ファイルシステムの論理ブロックサイズを意識する必要が出てくる(e.g., 読み書き用のメモリの開始アドレスをその倍数に揃えなければならない)。NVMでの"ブロック"は、このようなOSや物理ディスクがダイレクトI/Oのために要求する制約を表現するために使用されている。

ストレージの"ブロック"には、性能や実装の都合上「ストレージのブロックサイズは、NVMが要求するブロックサイズの倍数でなければならない」という制限はあるが、本質的には両者の間に関係はなく、ストレージがブロック単位で各種処理を行っているのは、消費メモリ量を節約するためでしかない。 具体的には、lumpインデックスデータ領域アロケータが認識するアドレス空間では、アドレスの単位がバイト単位ではブロック単位となっており、これによってストレージ内のアドレスを表現する際に必要なビット数を節約している(e.g., ブロックサイズが512なら、16bit整数を使って、最大で32MBの範囲が表現可能)。

なおCannyLSが許容する最小のブロックサイズは512である。

ブロックサイズ

ストレージないしNVMが使用しているブロックのサイズ(バイト数)。

要求キュー

デバイスに対して発行された未処理の要求群を保持しておくための優先順序付きキュー。 キュー内のエントリ群は、そのデッドラインに従ってソートされ、デッドラインが近いものから順番にデバイスによって処理されていくことになる。

You can’t perform that action at this time.