論文メモ Tree Indexing on Solid State Drives

February 15, 2021

SSDのランダムな書き込みを高速化するために、インデックスのためのデータ構造FD-treeを提案した。 FD-treeのエントリ数が\(n\), ページサイズが\(B\)であれば、ランダムな読み込みと書き込みの計算量はともに\(\mathcal{O}(\log_B(n))\)になる。

SSDでは、書き込み前に書き込み先のデータを削除しなければならず、小さくランダムな書き込みはランダムな読み込みと比べてかなり遅くなる。論文以前にもBFTLなど書き込み速度を上げるためのインデックス構造が提案されていたが、これらは書き込み以外の性能とのトレードオフがある構造だった。 FD-treeは読み込み性能を維持しつつ書き込み性能の向上を実現した。

FD-treeは検索、挿入、マージ、削除、更新の5つの操作に対応しており、そのアルゴリズムは3つの原則\(\mathcal{P}1,2,3\)にしたがい、目標の書き込み性能を獲得する。原則は、 \(\mathcal{P}1\) ランダムな書き込みリクエストをシーケンシャルな書き込みに変換し、ランダムな書き込みを減らす。 \(\mathcal{P}2\) ランダムに書き込む箇所を限定し、局所化する。 \(\mathcal{P}3\) 1度のI/O操作で複数のページにアクセスする。の3つで、そのためにlogarithmic methodとfractional cascadingをもちいる。

FD-treeは、ことなる2層のデータ構造からなる。最上位\(L_0\)がHead TreeとよばれるB+-treeで、以下の階層\(L_1, L_2, \dots\)は連続するページに格納されたsorted runとよばれる。 runは、主記憶に収まるほど小さなファイルの一部を意味する。以下にFD-treeの例を図示する。 fd-tree

ページの要素にはIndex EntryとFenceの2種類があり、どちらも図中の数字がしめすキーをもつ。 Index EntryはレコードのIDをもち、さらに、Filter EntryとNormal Entryの2種類にわかれる。 Filter Entryは、削除でFD-treeに挿入され、対応するレコードとIndex Entryが論理的に削除されたことをあらわす。論理的に削除されたが物理的に残るIndex EntryはPhantom Entryという。 Filter Entryでないものは、Normal Entryとよばれる。 Fenceはポインタであり、キーにはIndex entryから選ばれる。 Fenceは、1つ下の階層にある次に探索すべきページID, pidをもつ。各ページの最初の要素はFenceであり、また、隣接するFence内のキーがとりえる値の範囲は、Fenceによって参照される下層のページにあるキーの範囲に収まる。

FenceにはExternal FenceとInternal Fenceの2種類がある。図でいうと、71がExternal Fenceで、88がInternal Fenceにあたる。 \(L_i\)のExternal Fenceのキーは\(L_{i+1}\)から選ばれる。 \(L_{i+1}\)のページ\(P\)の最初要素のキーがExternal Fenceのpidになる。 \(L_i\)のInternal Fenceは同じ階層\(L_i\)から選ばれる。もし、ページ\(P\)の最初の要素がExternal Fenceでなければ、\(P\)の先頭にInteral Fenceをつくる。 Internal Fenceのキーは\(P\)の最初のIndex Entryのキーであり、pidは直下の層にあるキーを範囲に含んだページのidになる。

下層ほど容量が大きい。ランダムな書き込みはHead Treeに局所化される。上層の容量があふれると隣接する層同士のマージ処理が走り、その際、ランダムな書き込みはシーケンシャルにかわる。マージ時は、まず、2層をシーケンシャルに読み、結合して連続するページに1つのsorted runをつくる。作成された層を\(L_i\)は\(L_{i-1}\)のすべてのIndex Entryと旧\(L_i\)のIndex EntryとExternal Fenceを引き継ぐ。 Internal Fenceはページの最初の要素がExternal Fenceでなければ\(L_i\)に作成される。同時に、作られた\(L_i\)のExternal Fenceと整合性をとるために、\(L_j(0\le j< i)\)は再作成される。つまり、\(L_{i-1}\)と\(L_{i}\)をマージするとき、\(L_0\)から\(L_i\)までのすべての層を更新するために\(i+1\)個のsorted runsが作成される。もし新しい\(L_i\)が容量を超えていたら、マージ後に容量を超えることがなくなるまで、マージ処理が下層に伝播する。

論文をこちらからダウンロードできます。画像は論文から引用されています。