現代の分散ストレージシステムをサポートするアルゴリズム

アプリケーションによって処理されるデータの量が増え続けるにつれて、ストレージの拡張はますます困難になります。各データベース システムには独自のスキームがあります。これらのオプションの中から正しい選択を行うには、それらを理解することが重要です。

アプリケーションごとに、読み取りと書き込みの負荷分散、一貫性、レイテンシ、アクセス パターンが異なります。データベースと基盤となるストレージに精通していると、アーキテクチャ上の決定を下したり、システムの動作を説明したり、トラブルシューティングを行ったり、特定の状況に合わせて調整したりするのに役立ちます。

[[265061]]

システムをあらゆる面で最適化することは不可能です。もちろん、ストレージのオーバーヘッドなしで最高の読み取りおよび書き込みパフォーマンスを保証できるデータ構造が望まれますが、明らかに、これは存在しません。

この記事では、ほとんどの最新データベースで使用されている2つのストレージシステム設計、読み取り最適化Bツリー[1]と書き込み最適化LSM（ログ構造マージ）ツリー[5]について詳しく説明し、それぞれの使用例とトレードオフについて説明します。

Bツリー

B ツリーは、一般的な読み取り最適化インデックス データ構造であり、バイナリ ツリーの一般化です。多くのバリエーションがあり、多くのデータベース（MySQL InnoDB [4]、PostgreSQL [7]を含む）やファイルシステム（HFS+ [8]、HTrees ext4 [9]）で使用されています。 B-Tree の B は、元のデータ構造の作成者である Bayer、または当時彼が勤務していた会社である Boeing を表しています。

検索二分木では、各ノードに 2 つの子 (左の子と右の子と呼ばれる) があります。左のサブツリーのノード値は現在のノード値よりも小さく、右のサブツリーの場合はその逆になります。ツリーの深さを最小限に抑えるには、検索バイナリ ツリーのバランスをとる必要があります。調整せずに値がランダムな順序でツリーに追加されると、ツリーは最終的に歪んでしまいます。

バイナリ ツリーのバランスをとる方法の 1 つは、いわゆるローテーションです。つまり、ノードを再配置して、より深いサブツリーの親をその子の下に押し下げ、その子を引き上げ、元の親の場所に置きます。図 1 はバランスのとれた二分木の回転の例です。左側にノード 2 を追加すると、バイナリ ツリーは不均衡になります。ツリーのバランスをとるために、ツリーはノード 3 を中心に回転します (ツリーはノード 3 を中心に回転します)。次に、ノード 5 (回転前はノード 3 のルート ノードであり親ノードであった) がその子ノードになります。回転が完了すると、左のサブツリーの深さが 1 減少し、右のサブツリーの深さが 1 増加します。ツリーの最大深さが減少しました。

バイナリツリーは最も便利なメモリ内データ構造です。ただし、バランス (すべてのサブツリーの深さを最小限に保つ) と低い出力次数 (各ノードには最大 2 つの子がある) のため、ディスク上ではうまく機能しません。 B ツリーでは、ノードごとに 2 つ以上のポインターを保存でき、ノード サイズをページ サイズ (例: 4 KB) に一致させることでブロック デバイスを操作できます。今日の実装の中には、複数のページにまたがる、はるかに大きなノード サイズを使用するものもあります。

B ツリーには次の特性があります。

• 整然としている。これにより、順次スキャンが可能になり、検索が簡素化されます。

• 自己バランス。挿入および削除中にツリーのバランスを取る必要はありません。B ツリー ノードがいっぱいになると 2 つの部分に分割され、隣接するノードの使用率が特定のしきい値を下回ると 2 つのノードが結合されます。これは、各リーフ ノードとルート ノード間の距離が等しく、検索プロセス中にそれを見つけるためのステップ数も同じであることを意味します。

• 対数的な検索時間の複雑さ。検索時間は非常に重要であるため、B ツリーはデータベース インデックスに最適です。

• 揮発性があります。挿入、更新、削除（結果の分割と結合を含む）はディスク上で実行されます。インプレース更新を可能にするには、一定量のスペースオーバーヘッドが必要です。 B ツリーは、実際のデータがリーフ ノードに格納されるクラスター化インデックスとして使用することも、ヒープ ファイルと呼ばれる非クラスター化インデックスとして使用することもできます。

この記事で説明するB+ツリー[3]は、データベースストレージでよく使用されるBツリーの最新版です。 B+ツリーは、オリジナルのBツリー[1]と次の点で異なります：(1) 値を格納するために追加のリンクされたリーフノードを使用する。(2) 値を内部ノードに格納できない。

Bツリーの分析

まず、図 2 に示すように、B ツリーの構造を詳しく見てみましょう。 B ツリー ノードには、ルート ノード、内部ノード、リーフ ノードなど、いくつかの種類があります。ルート ノード (最上位) は親を持たないノードです (つまり、どのノードの子でもありません)。内部ノード (中央) には親と子があり、ルート ノードをリーフ ノードに接続します。リーフ ノード (下部) にはデータが保持され、子はありません。図 2 は、分岐係数が 4 の B ツリー (ポインターが 4 つ、内部ノードにキーが 3 つ、リーフにキーと値のペアが 4 つ) を示しています。

B-Tree の特徴は次のとおりです。

• 分岐係数 – 子ノードへのポインターの数 (N)。ポインタに加えて、ルート ノードと内部ノードも N-1 個のキーを保持します。

• 使用率 – ノードが現在保持している子ノードへのポインターの数と使用可能な *** 値の比率。たとえば、ツリーの分岐係数が N で、ノードが現在 N/2 個のポインターを保持している場合、ノードの使用率は 50% になります。

• 高さ – B ツリーの大きさ。検索中にトラバースする必要があるポインターの数を示します。

ツリー内の各非リーフ ノードは最大 N 個のキー (インデックス エントリ) を保持でき、これによりツリーは対応するポインターによって見つけられる N+1 個のサブツリーに分割されます。項目 Ki 内のポインタ i は、Ki-1 <= Ktarget < Ki (ここで、K はキーのセット) のすべてのインデックス項目を含むサブツリーを指します。最初のポインタと最後のポインタは、それらが指すサブツリー内のすべての項目が、左端の子ノードの K0 以下であるか、右端の子ノードの KN-1 より大きいという点で特別です。リーフ ノードは、同じレベルの前のノードと次のノードへのポインターも保持し、兄弟ノード間の双方向リンク リストを形成します。すべてのノード内のキーは常に順序どおりです。

探す

検索する場合、検索はルート ノードから開始され、内部ノードを経由してリーフ ノード レベルまで再帰的に移動します。各レイヤーでは、子ノードへのポインタを通じて、検索範囲がサブツリー（検索対象値を含むサブツリー）に絞り込まれます。図 3 は、B ツリーのルートからリーフへの検索プロセスを示しています。ポインターは 2 つのキーの間にあり、そのうちの 1 つは検索ターゲットより大きい (または等しい) キーであり、もう 1 つは検索ターゲットより小さいキーです。ポイント クエリを実行すると、リーフ ノードが見つかった後に検索が完了します。範囲スキャンを実行するときは、見つかったリーフ ノードのキーと値を走査し、次に範囲内の兄弟リーフ ノードを走査します。

複雑さの点では、B ツリーでは、図 4 に示すように、ノード内のキーの検索にバイナリ検索が使用されるため、クエリの時間複雑度が log(n) になることが保証されます。バイナリ検索は、すべての単語がアルファベット順に並べられている辞書で、特定の文字で始まる単語を検索すると簡単に説明できます。まず、辞書の真ん中のページを開きます。探している単語が現在のページよりアルファベット順で小さい（前にある）場合は、辞書の左半分で検索を続けます。それ以外の場合は、右半分で検索を続けます。残りのページ範囲を半分に分割し、片側を選択して、目的の文字が見つかるまでこれを続けます。各ステップで検索範囲が半分になるため、検索の時間計算量は対数的になります。 B ツリー ノード上のキーはバイナリ検索アルゴリズムを使用して順序付けおよび照合されるため、B ツリーの検索の複雑さは対数的になります。これは、木の利用率を高く保ち、アクセスを均一に保つことの重要性も示しています。

挿入、更新、削除

挿入する場合、最初のステップはターゲットのリーフ ノードを見つけることです。このプロセスでは、事前順序検索アルゴリズムが使用されます。ターゲットのリーフ ノードが見つかったら、キーと値がノードに追加されます。ノードに十分な空き領域がない場合、オーバーフローと呼ばれる状況が発生し、リーフ ノードは 2 つの部分に分割されます。これは、新しいリーフ ノードを割り当て、要素の半分を新しいノードに移動し、この新しいノードへのポインタを親ノードに追加することによって行われます。親ノードに十分なスペースがない場合は、親ノードでも分割が行われます。操作はルート ノードに到達するまで続行されます。ルート ノードがオーバーフローすると、その内容は新しく割り当てられたノード間で分割され、ルート ノード自体は再配置を避けるために上書きされます。これは、ツリー (およびその高さ) が常にルート ノードを分割することによって大きくなることも意味します。

LSMツリー

構造化ログ マージ ツリーは、不変のディスク ベースの書き込み最適化データ構造です。書き込み操作がクエリ操作よりも頻繁に行われるシナリオに適しています。 LSM-Tree は、ランダムな挿入、更新、削除を回避できるため、注目を集めています。

LSMツリーの分析

継続的な書き込みを可能にするために、LSM-Tree はメモリ内テーブルへの書き込みと更新をバッチ処理し (通常はバイナリ検索ツリーやスキップ リストなど、検索の対数時間計算量をサポートするデータ構造を使用)、サイズがしきい値に達するとディスクに書き込みます (フラッシュと呼ばれる操作)。データを取得するには、ツリーのディスク上のすべての部分を検索し、メモリ内のテーブルをチェックし、その内容をマージして、結果を返す必要があります。図 5 は、書き込み用のメモリベースのテーブルである LSM-Tree の構造を示しています。メモリ テーブルのサイズが一定のレベルに達すると、メモリ テーブルはディスクに書き込まれます。読み取り時には、ディスク テーブルとメモリ テーブルの両方が同時に読み取られ、マージ操作によってデータが統合されます。

順序付きシリアルリスト

SSTable (順序付けられたシリアル テーブル) のシンプルさ (書き込み、検索、読み取りが簡単) とマージ パフォーマンス (マージ中にソース SSTable がスキャンされ、マージ結果が順番に書き込まれる) のため、ほとんどの最新の LSM-Tree 実装 (RocksDB や Apache Cassandra など) では、ディスク テーブルとして SSTable が選択されます。

SSTable は、ディスクに基づく順序付けられた不変のデータ構造です。構造的な観点から見ると、SSTable は、図 6 に示すように、データ ブロックとインデックス ブロックの 2 つの部分に分けられます。データ ブロックには、キー順に記述された一意のキーと値のペアが含まれます。インデックス ブロックには、実際のレコードの場所を指すデータ ブロック ポインターにマップされるキーが含まれます。高速な検索を実現するために、インデックスは通常、B ツリーやポイント クエリのハッシュ テーブルなどの最適化された構造を使用して実装されます。 SSTable 内の各値には、タイムスタンプが関連付けられています。タイムスタンプは、挿入、更新 (通常は両者は区別されません)、および削除の時刻を記録します。

SSTable には次の利点があります。

• 主キー インデックスをクエリすることで、高速なポイント クエリ (キーによる値の検索) を実現できます。

• スキャンは、データ ブロック上のキーと値のペアを順番に読み取るだけで実現できます (たとえば、指定された範囲内のキーと値のペアを走査する)。

SSTable は、一定期間にわたるすべてのデータベース操作のスナップショットを表します。これは、SSTable がその期間中にデータベースの状態のバッファーとして機能する memtable へのフラッシュ操作によって作成されるためです。

クエリ

データを取得するには、ディスク上のすべての SSTable を検索し、memtable をチェックし、それらの内容をマージしてから結果を返す必要があります。検索対象のデータは複数の SSTable に格納される可能性があるため、マージ手順が必要です。

削除と更新が適切に機能することを確認するためにも、マージ手順が必要です。 LSM-Tree では、プレースホルダー (多くの場合、トゥームストーンと呼ばれます) を挿入することによって、キーが削除対象としてマークされます。同様に、更新操作では、単にタイムスタンプが新しいレコードがコミットされます。読み取り中、削除対象としてマークされたレコードはスキップされ、クライアントに返されません。更新操作も同様です。同じキーを持つ 2 つのレコードのうち、タイムスタンプが新しいレコードのみが返されます。図 7 は、異なるテーブルに格納されている同じキーを持つデータを統合するマージ操作を示しています。図に示すように、Alex のレコードのタイムスタンプは 100 で、その後、新しい電話番号がタイムスタンプ 200 で更新され、John のレコードは削除されます。他の 2 つの項目は上書きされなかったため変更されませんでした。

SSTableの検索回数を減らし、キーを見つけるためにすべてのSSTableを検索するのを避けるために、多くのストレージシステムではブルームフィルタ[10]と呼ばれるデータ構造を使用しています。これは、要素がセットに属しているかどうかをテストするために使用できる確率的なデータ構造です。偽陽性 (つまり、要素がセットのメンバーではないのに、セットのメンバーであると判断する) を生成する可能性がありますが、偽陰性 (つまり、否定的な結果を返す場合、要素はセットのメンバーではないはず) を生成することはできません。言い換えると、ブルーム フィルターは、キーが「SSTable に存在する可能性がある」か「SSTable に確実に存在しない」かを判断するために使用されます。検索中、ブルーム フィルターが否定的な結果を返す SSTable はスキップされます。

LSM ツリーのメンテナンス

SSTable は不変であるため、順番に書き込まれ、変更用に予約された空き領域はありません。つまり、挿入、更新、または削除の操作では、ファイル全体を書き換える必要があります。データベースの状態を変更するすべての操作は、メモリ テーブル内で「バッチ処理」されます。時間が経つにつれて、ディスク テーブルの数が増加し (同じキーのデータが複数の異なるファイルに配置され、同じレコードの複数の異なるバージョンが存在し、冗長なレコードが削除される)、読み取り操作のコストがますます大きくなります。

読み取りオーバーヘッドを削減し、削除されたレコードによって占有されたスペースを統合し、ディスク テーブルの数を減らすために、LSM-Tree では、ディスクから完全な SSTable を読み取ってマージする圧縮操作が必要です。 SSTable はキーでソートされるため、その圧縮はマージ ソートに似ています。マージ ソートは非常に効率的な操作です。レコードは複数のソース順序付けされたシーケンスから読み取られ、マージされた出力は結果ファイルにすぐに追加されるため、結果ファイルも順序付けされます。マージソートの利点の 1 つは、メモリに収まらないほど大きなファイルをマージする場合でも効率的に動作できることです。結果のテーブルでは、元の SSTable の順序が保持されます。

このプロセス中、マージされた SSTable は破棄され、「圧縮された」バージョンに置き換えられます (図 8 を参照)。複数の SSTable を圧縮し、1 つにマージします。一部のデータベース システムでは、異なるテーブルをサイズ別に論理的に異なるレベルに分割し、同じ「レベル」にグループ化して、特定のレベルに十分なテーブルがある場合にマージ操作を開始します。圧縮後、SSTable の数が減り、クエリの効率が向上します。

原子性と耐久性

I/O 操作を減らして順次実行するために、B-Tree と LSM-Tree はどちらも、実際に更新する前にメモリ内でバッチ操作を実行します。つまり、障害が発生した場合、データの整合性、アトミック性 (一連の操作に、すべてまたは何もない 1 つの操作としてアトミック性を与える)、および耐久性 (プロセスがクラッシュしたり電源が落ちたりしたときに、データが永続的なストレージに到達していることを保証する) は保証されません。

この問題を解決するために、ほとんどの最新のストレージ システムでは WAL (先行書き込みログ) が使用されます。 WAL の基本的な考え方は、すべてのデータベース状態の変更が最初にディスク上の追加専用ログに保存されるというものです。ジョブの途中でプロセスがクラッシュした場合、データが失われず、すべての変更がアトミックであることを確認するためにログが再生されます。

B-Tree では、WAL の使用は、書き込み操作が記録された後にのみデータ ファイルに書き込みを行うことを意味します。通常、B ツリー ストレージ システムのログのサイズは比較的小さく、永続ストレージに変更が適用されるとすぐに破棄できます。 WAL は実行時操作のバックアップとしても機能します。データ ページに適用されていない変更は、ログ レコードに基づいてやり直すことができます。

LSM-Tree では、メモリ テーブル内にあるがまだディスクに完全にフラッシュされていない変更を保存するには WAL が使用されます。 memtable がフラッシュされ置き換えられている限り、新しく作成された SSTable で読み取り操作を実行でき、memtable からディスクにフラッシュされた WAL の変更を破棄できます。

要約する

B ツリーと LSM ツリーのデータ構造の最大の違いの 1 つは、最適化の目的と最適化の効果です。

B-Tree と LSM-Tree の特徴を比較してみましょう。一般に、B-Tree には次の特性があります。

• 変更可能であるため、ある程度のスペースオーバーヘッドとより多くの書き込みパスを伴うインプレース更新が可能になり、ファイルの書き換えや複数ソースのマージが必要ありません。

• 読み取り最適化されているため、複数のソースから読み取る（またはマージする）必要がなく、読み取りパスが簡素化されます。

• 書き込み操作によりカスケードノード分割が発生する可能性があり、書き込み操作のコストが高くなります。

• ページング環境 (ブロック ストレージ) 向けに最適化されており、バイト アライメント操作が不要になります。

• 頻繁な更新によって断片化が発生すると、追加のメンテナンスとブロックの書き換えが必要になる場合があります。ただし、B-Tree のメンテナンスは、一般的に LSM-Tree よりも少なくなります。

• ラッチとロック チェーンを伴う同時アクセスの読み取り/書き込み分離。

LSM-Tree には次の特性があります。

• 変更不可能です。 SSTable がディスクに書き込まれると、変更されることはありません。圧縮操作は、占有されているスペースを統合し、エントリを削除し、異なるデータ ファイル内の同じキーを持つデータをマージするために使用されます。圧縮操作の一環として、マージが成功した後、ソース SSTable は非推奨となり、削除されます。この不変性により、更新されたテーブルに同時にアクセスできるという別の便利な特性が得られます。

• 書き込みが最適化されているため、書き込みはバッファリングされ、その後ディスクに順番にフラッシュされ、ディスクベースの空間的局所性をサポートする可能性があります。

• 異なる時間に書き込まれた同じキーのデータが異なるデータ ファイルに存在する可能性があるため、読み取り操作では複数のデータ ソースにアクセスする必要がある場合があります。レコードは、クライアントに返す前にマージ プロセスを経る必要があります。

• バッファリングされた書き込みがディスクにフラッシュされるため、メンテナンス/圧縮が必要です。

ストレージシステムの評価

ストレージ システムの開発には、常に同様の課題に直面し、同様の要素を考慮する必要があります。どの方向に最適化するかを決定すると、結果に大きな影響を与える可能性があります。書き込み中に構造をレイアウトする時間を増やして読み取りの効率を高め、インプレース更新のためのスペースを残すか、データをバッファリングして順次書き込みを確実に行い、書き込みを高速化することができます。しかし、それを一度にすべて行うことは不可能です。理想的なストレージ システムは、読み取りコストと書き込みコストが最小限で、追加のオーバーヘッドがないものでなければなりません。しかし、現実には、データ構造は複数の要素の間でバランスをとることしかできません。これらのトレードオフを理解することが重要です。

ハーバード大学 DASlab (データ システム研究所) の研究者は、データベース システムの最適化の方向性における 3 つの重要なポイントとして、読み取りオーバーヘッド、更新オーバーヘッド、メモリ オーバーヘッド (略して RUM) をまとめました。アルゴリズムは特定のユースケースに合わせて調整されるため、データ構造、アクセス方法、さらには特定のワークロードへの適合性の選択は、ユースケースにとってどのパラメータが最も重要であるかに基づいて決定する必要があります。

RUM仮説[2]は、上記のコストのうち2つに上限を設定し、3つ目に下限を設定します。たとえば、B ツリーは、書き込みオーバーヘッドと予約領域の増加 (メモリ オーバーヘッドも生成) を犠牲にして読み取り最適化されます。 LSM-Tree では、読み取り時に複数のハードディスク テーブルにアクセスする必要があるため、読み取りオーバーヘッドは高くなりますが、書き込みオーバーヘッドは低くなります。競争三角形の 3 つのパラメータのうち、ある側面の改善は別の側面の譲歩を意味する場合があります。図9はRUM仮説を示しています。

B ツリーは読み取りパフォーマンスを最適化します。インデックスは、ツリーを走査するために必要なディスク アクセスを最小限に抑えるようにレイアウトされます。インデックス ファイルにアクセスすることでデータを見つけることができます。これはインデックス ファイルを継続的に更新することで実現されますが、ノードの分割と結合、再配置、断片化と不均衡に関連するメンテナンスにより、書き込みオーバーヘッドも追加されます。更新コストを平滑化し、分割数を減らすために、B-Tree はノードのすべてのレベルで追加のスペースを予約します。これにより、ノードが飽和する前に書き込みオーバーヘッドの増加を遅らせることができます。つまり、B-Tree は読み取りパフォーマンスを向上させるために更新とメモリのパフォーマンスを犠牲にします。

LSM-Tree は書き込みパフォーマンスを最適化します。更新と削除の両方でディスク上のデータを見つける必要があり (B ツリーの場合も同様)、すべての挿入、更新、削除操作をメモリ テーブルにキャッシュすることで順次書き込みが保証されます。これには、メンテナンス コストと圧縮要件の増加 (増大する読み取りオーバーヘッドを軽減し、ディスク上のテーブルの数を減らす唯一の方法) と読み取りコストの増加 (複数のソースからデータを読み取って結合する必要があるため) が伴います。同時に、LSM-Tree は予約スペースを予約しないことでメモリのオーバーヘッドを削減します (インプレース更新に必要なオーバーヘッドを含め、平均使用率が 70% である B-Tree ノードとは異なります)。使用率が高く、最終ファイルが不変であるため、LSM-Tree はブロック圧縮をサポートします。つまり、LSM-Tree は、書き込みパフォーマンスの向上とメモリ使用量の削減を実現するために、読み取りパフォーマンスを犠牲にし、メンテナンス コストを増加させます。

必要な属性ごとに最適化できるデータ構造があります。適応型データ構造を使用すると、メンテナンスコストは高くなりますが、読み取りパフォーマンスは向上します。トラバーサルを支援するメタデータ (スキャッター カスケードなど) を追加すると、書き込み時間に影響し、より多くのスペースが必要になりますが、読み取りパフォーマンスは向上します。圧縮を使用してメモリ使用量を最適化すると（Gorilla圧縮[6]、デルタエンコーディング、その他多くのアルゴリズムなど）、書き込み時にデータを圧縮し、読み取り時にデータを解凍するためにオーバーヘッドが追加されます。効率性のために機能性を犠牲にしなければならない場合もあります。たとえば、ヒープ ファイルとハッシュ インデックスは、ファイル形式がシンプルなため、優れたパフォーマンスと小さなスペース オーバーヘッドを保証できますが、その代償として、ポイント クエリ以外の機能はサポートされません。また、近似データ構造 (Bloom フィルター、HyperLogLog、Count-Min スケッチなど) を使用することで、スペースと効率のために精度を犠牲にすることもできます。

読み取り、更新、メモリ オーバーヘッドという 3 つの変数は、データベースを評価し、データベースが最適なワークロードについての洞察を得るのに役立ちます。これらはすべて非常に直感的で、ストレージ システムを 1 つに分類し、そのパフォーマンスを推測し、広範なテストを通じてその仮定を検証することが簡単です。

もちろん、ストレージ システムを評価する際に考慮すべき重要な要素は他にもあります。たとえば、メンテナンスのオーバーヘッド、使いやすさ、システム要件、頻繁な追加や削除への適応性、アクセス パターンなどです。 RUM 仮説は、直感を養い、初期の方向性を示すのに役立つ単なる経験則です。動作部分を理解することは、スケーラブルなバックエンドを構築するための第一歩です。

いくつかの要因は実装によって異なる場合があり、同様のストレージ設計原則を使用する 2 つのデータベースでも動作が異なる場合があります。データベースは、多数のプラグ可能なモジュールで構成される複雑なシステムであり、多くのアプリケーションの重要な部分です。この情報は、データベースの内部を覗き込み、基礎となるデータ構造とその内部動作の違いを理解して、どれが最適かを判断するのに役立ちます。