Skip to content

Memory Usage

Jump to bottom
Takeru Ohta edited this page Oct 17, 2018 · 1 revision

CannyLSでは、以下の特徴により、そのメモリ使用量をかなり正確に見積もることが可能となっている:

  • キーとなるLumpIdの長さが128bit固定
  • オンメモリキャッシュ機構が存在しない
    • またダイレクトI/Oを使用しているため、間接的にOSのメモリ(ページキャッシュ)を消費することも無い
  • メモリを消費する主なデータ構造は以下の二つだが、これらは完全なオンメモリデータ構造であり、自分の状態の一部をディスク上に保持したりはしない:

以降では「lumpインデックス」および「データ領域アロケータ」のメモリ使用量の見積もり方法について説明していく。

lumpインデックスのメモリ使用量

lumpインデックスは「ストレージに格納済みのlumpのID一覧」を管理するためのデータ構造であり、 実体としては「キーをLumpId、値をlumpデータの格納位置(offsetとlenght)」とするBTreeMapである。

上述の通りキー長は128bitと決まっており、また値の長さも64bit固定であるが、以下のような式でメモリ使用量(バイト単位)を算出することが可能となる:

lumpインデックスのメモリ使用量 = 格納lump数 * (128bit + 64bit) / 8bit * BTreeMapのオーバヘッド

仮に「BTreeMapのオーバヘッド」が2だとして、格納lump数が一千万なら10000000 * (128 + 64) / 8 * 2 = 480000000 = 約457MBが必要なメモリ量となる。

データ領域アロケータのメモリ使用量

データ領域アロケータのメモリ使用量を見積もりは、lumpインデックスに比べると若干複雑になる。

単純化してしまえば、データ領域アロケータは、データ領域の内の未割当領域を単一の(いわゆる)フリーリストを用いて管理している。 フリーリストの実体はBTreeSetであり、そこには128bit長の「データ領域内の割当済みの部分領域」を示す要素が格納されている。 そのため、データ領域アロケータのメモリ使用量(バイト単位)は、以下の式で算出可能となる:

データ領域アロケータのメモリ使用量 = フリーリスト内の要素数 * (128bit / 8bit) * BTreeSetのオーバヘッド

問題は「フリーリスト内の要素数」の正確な見積もりが難しいことである。例えば、仮に十万個のlumpがストレージに格納されているとしても、それらが全て、データ領域内の隣接する領域に割当てられているのであれば、フリーリストの長さは1となる（要するにlumpの数だけではなく、そのサデータサイズや、追加・削除の実行パターンに依存して変化することになる）。

ただし、フリーリストの長さの上限は「格納中のlump数」となるので、実際のメモリ使用量ではなく最悪値であれば、次の式で求めることができる:

データ領域アロケータの最大メモリ使用量 = 格納lump数 * (128bit / 8bit) * BTreeSetのオーバヘッド

仮に「BTreeSetのオーバヘッド」が2だとして、格納lump数が一千万なら10000000 * (128 / 8) * 2 = 320000000 = 約302MBが最悪時に必要なメモリ量となる。

Contents:

Clone this wiki locally