現代のストレージシステムの背後にある古典的なアルゴリズムを解釈する

アプリケーションによって処理されるデータの量は増加し続けています。データの増加は、ストレージ機能の拡張に課題をもたらします。この点に関しては、各データベース管理システムに独自のトレードオフがあります。これらのトレードオフを理解することは、データ管理者が複数のアプローチの中から適切な選択を行うために重要です。

[[238427]]

アプリケーションは、読み取り/書き込みワークロードのバランス、一貫性の要件、レイテンシ、アクセスパターンの点で異なります。データベースとストレージの内部インフラストラクチャアーキテクチャの決定を明確に理解していれば、システムが特定の方法で動作する理由を理解し、問題が発生したときに解決し、ワークロードに応じてデータベースを調整するのに役立ちます。

システムがあらゆる面で完璧であることは不可能です。ストレージのオーバーヘッドがなく、最高の読み取りおよび書き込みパフォーマンスを提供するデータ構造は理想的な状況にのみ存在し、もちろん実際には不可能です。

この記事では、ほとんどの最新データベースで使用されている 2 つのストレージシステム設計アプローチ、つまり読み取り最適化 B ツリー 1 と書き込み最適化 LSM (ログ構造マージ) ツリー 5 を分析し、各アプローチの使用例とトレードオフをいくつか示します。

1. Bツリー

B ツリーは、バイナリツリーを一般化した、広く使用されている読み取り最適化インデックスデータ構造です。これにはいくつかのバリエーションがあり、さまざまなデータベース (MySQL InnoDB4 や PostgreSQL 7 を含む) やファイルシステム (たとえば、HFS+8、ext4 9 の HTrees) で使用されてきました。 B ツリーの「B」は「Bayer」の略で、データ構造のオリジナルの作成者であるルドルフ・ベイヤー、または当時ベイヤーが勤務していたボーイング社を指します。

二分木では、各ノードに 2 つの子ノード (左の子と右の子と呼ばれる) があります。左と右のサブツリーに格納されているキーの値は、それぞれ現在のノードのキーより小さい値と大きい値になります。ツリーの深さを最小限に抑えるには、バイナリツリーのバランスをとる必要があります。ツリーにキーをランダムな順序で追加すると、最終的にはツリーの片側がもう片側よりも深くなるのが自然です。

バイナリツリーを再調整する方法の 1 つは、「回転」方式と呼ばれます。回転メソッドは、より深いサブツリーの親ノードをその子ノードの下に押し下げ、子ノードを上に移動して親ノードの元の位置に効果的に配置することにより、ノードの再配置を実装します。図 1 は、バランスのとれた二分木を実現するための回転方法の例を示しています。左側のバイナリツリーは、ノード "2" を追加した後は不均衡になります。バイナリツリーのバランスをとるために、ツリーをノード「3」を中心に回転させ、次にノード「5」を中心に回転させます。ノード「5」は元のルートノードであり、ノード「3」の親ノードです。回転後、ノード「3」の子ノードになります。回転が完了すると、右図のツリーが得られます。このツリーでは、左のサブツリーの深さが 1 減少し、右のサブツリーの深さが 1 増加し、ツリーの最大深さが減少します。

図1 例: 回転を使用した二分木のバランス調整

バイナリツリーは非常に便利なメモリ内データ構造です。バイナリツリーは、バランス (つまり、すべてのサブツリーの深さを最小限に抑える必要がある) とファンアウトの低さ (各ノードには最大 2 つのポインターがある) の特性により、ディスク上ではパフォーマンスがよくありません。 B ツリーでは、ノードごとに 3 つ以上のポインターが許可され、ページ内に収まるようにノードサイズを調整できるため (たとえば、4 KB)、ブロックデバイスで適切に機能します。現在、一部の実装では、複数のページにまたがる、はるかに大きなノードが使用されています。

B データには次のプロパティがあります。

ソート: ソートは順次スキャンをサポートし、検索を簡素化します。
自己バランス: 挿入および削除操作ではツリーの再バランス調整は必要ありません。 B ツリーノードがいっぱいになると、2 つのノードに分割されます。隣接する 2 つのノードの占有率が特定のしきい値を下回ると、ノードは結合されます。これは、各リーフノードがルートノードから等距離にあり、検索時に同じステップ数を使用して見つけることができることを意味します。
ルックアップ操作には対数時間の計算量があることが保証されています。このため、検索時間が重要なデータベースインデックスには B ツリーが適しています。
可変データ構造のサポート。挿入、更新、削除 (および後続のノードの分割と結合) はディスク上で実行されるため、詳細な更新を実装するには一定量のスペースオーバーヘッドが必要です。 B ツリーは、実際のデータをリーフノードに格納するクラスター化インデックスとして構成することも、データをヒープファイルとして格納する非クラスター化インデックスとして構成することもできます。

この記事ではB+ツリー3についても紹介します。 B+ ツリーは B ツリーのバリエーションであり、データベースストレージによく使用されます。元の B ツリーと比較すると、B+ ツリーは次の点で異なります。1. B+ ツリーのリーフノードは値を格納し、追加のリンク層を形成します。 2. B+ ツリーの内部ノードには値は格納されません。

Bツリーの構造

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

図2 例: Bツリー

B ツリーを識別するには、次のインジケーターを使用できます。

分岐係数: 子ノードを指すポインターの数 (N)。ポインタの存在を考慮すると、ルートノードと内部ノードは N-1 個のキー値を格納できます。
使用率: 使用可能なポインターの総数のうち、サブ項目へのポインターが現在いくつ使用されているか。たとえば、ツリーの分岐係数が N で、ノードが現在 N/2 個のポインターを保持している場合、使用率は 50% になります。
高さ: B ツリーのレベル数。検索中にトラバースする必要があるポインターの数を示します。

ツリー内の各非リーフノードは最大 N 個のキー (インデックスエントリ) を保持し、ツリーを対応するポインタを使用して見つけることができる N+1 個のサブツリーに分割します。エントリ Ki 内のポインタ i が指すサブツリーでは、すべてのインデックスエントリは Ki-1 <= Ksearched < Ki となります (ここで、k はキーのセットです)。最初と最後のポインタは特別なケースです。左端の子ノードが指すサブツリーでは、すべてのエントリが K0 以下であり、右端の子ノードが指すサブツリーでは、すべてのエントリが KN-1 より大きくなります。リーフノードに含まれるポインターは、同じレイヤー内の前のノードまたは次のノードを指すことができ、隣接ノードの二重リンクリストを形成します。すべてのノードにわたって、キーは常にソートされます。

探す

ルックアップを実行すると、検索はルートノードから開始され、内部ノードを経由してリーフレベルまで再帰的に下降します。各レベルでは、子ノードポインターをたどることで、検索空間を検索値を含むサブツリーに縮小できます。図 3 は、B ツリーでの検索、つまり 2 つのキー間のポインターをたどるルートからリーフへのトラバーサルを示しています。1 つのポインターは検索語句以上であり、もう 1 つは検索語句より小さいです。ポイントクエリを実行すると、リーフノードが見つかった後に検索が終了します。範囲検索では、見つかったリーフノードのキーと値が走査され、次に隣接するリーフノードが走査され、範囲の終わりに達するまで続けられます。

図3 ルートからリーフへの単一のトラバーサル

複雑さの観点から見ると、図 4 に示すように、B ツリーはノードからキーを見つけるためにバイナリ検索が使用されるため、log(n) の複雑さの検索を保証します。バイナリ検索は簡単に説明できます。辞書から特定の最初の文字を持つ単語を検索すると、すべての単語がアルファベット順に並べられます。まず、正確な中央の位置から辞書を開くことを選択します。検索文字が、開始文字よりアルファベット順で「小さい」（最初に現れる）場合、辞書の左半分で検索が続行されます。それ以外の場合は、辞書の右半分が検索されます。次に、残りのページ範囲を半分に減らし、目的の文字が見つかるまで検索方向を選択して縮小し続けます。各ステップで検索空間が半分になり、検索は時間に対して対数的になります。 B ツリーでの検索は、ノードレベルのキーがソートされ、一致を見つけるためにバイナリ検索が使用されるため、対数的な時間計算量を持ちます。このため、ツリー全体で使用率を高く、一貫して維持することが非常に重要です。

図4 Bツリーバイナリ検索

挿入、更新、削除

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

2. LSMツリー

ログ構造化マージ (LSM) ツリーは、書き込みに最適化されたデータ構造であり、変更不可能でディスク常駐であり、レコードの検索と取得よりも書き込み操作が頻繁に行われるシステムに適しています。 LSM ツリーは、ランダムな挿入、更新、削除を排除するため、より多くの注目を集めています。

LSM ツリーの構造

順次書き込みをサポートするために、LSM ツリーは、メモリテーブルのサイズが設定されたしきい値に達するまで、常駐メモリテーブル (通常は、バイナリ検索ツリーやスキップリストなどの対数時間複雑度検索をサポートするデータ構造を使用して実装されます) にバッチで書き込まれ、更新されます。しきい値に達すると、ツリーはディスクに書き込まれます。この操作は「フラッシュ」と呼ばれます。データを取得するには、ツリーのディスク上のすべての部分を検索し、メモリ内のテーブルをチェックし、結果を戻す前に内容をマージする必要があります。図 5 は、書き込み用のメモリ常駐テーブルを備えた LSM ツリーの構造を示しています。メモリ内テーブルが一定のサイズに達すると、ソートされた内容がディスクに書き込まれます。読み取りには、ディスク常駐テーブルとメモリ常駐テーブルの両方へのアクセスが必要であり、データを統合するためのマージプロセスが必要です。

図5 LSMツリーの構造

ソートされた文字列テーブル (SSTable)

RocksDB や Apache Cassandra などの多くの最新システムでは、LSM ツリーのディスク常駐テーブルは SSTable (Sorted String Table) として実装されています。 SSTable にはシンプルさ (書き込み、検索、読み取りが簡単) とマージプロパティ (マージ中、ソース SSTable のスキャンとマージ結果の書き込みが順次操作される) があります。

SSTable は、不変のディスク常駐ソート済みデータ構造です。図 6 に示すように、SSTable は構造的にデータブロックとインデックスブロックの 2 つの部分に分けられます。データブロックは、順番に書き込まれる一意のキーと値のペアで構成され、キーと値のペアはキーによってソートされます。インデックスブロック内のキーには、実際のレコードの場所を指すデータブロックポインターへのマップが含まれています。インデックスは通常、B ツリーなどの高速検索に最適化された形式で実装されるか、ポイントクエリ用のハッシュテーブルを使用して実装されます。 SSTable 内の各値エントリには、タイムスタンプが関連付けられています。タイムスタンプは、挿入と更新の書き込み時間（通常は区別なし）と、削除の削除時間を指定します。

図6 SSTable構造

SSTable には、いくつかの優れた特性があります。

ポイントクエリ (つまり、キーに基づいて値を検索する) は、プライマリインデックスを検索することによってすばやく実行できます。
スキャン (つまり、指定されたキー範囲内のすべてのキーと値のペアを反復処理すること) は、データブロック内のキーと値のペアを順番に読み取るだけで効率的に実行できます。

SSTable は、一定期間にわたるすべてのデータベース操作のスナップショットを提供します。 SSTable はメモリ内テーブルのフラッシュ操作によって作成されるため、この期間中、テーブルはデータベース状態に対する操作のバッファーとして機能します。

探す

データを取得するときは、ディスク上のすべての SSTable を検索し、常駐メモリテーブルをチェックし、それらの内容をマージしてから結果を返す必要があります。検索対象のデータが複数の SSTable に存在する可能性があるため、読み取り操作ではマージプロセスが必要になります。

削除と更新が確実に実装されるようにするには、マージ手順も必要です。削除が発生すると、墓石と呼ばれるプレースホルダーが LSM ツリーに挿入されます。墓石は削除されたキーをマークするために使用されます。同様に、更新では、より新しいタイムスタンプを持つレコードが追加されるだけです。読み取り中、削除対象としてマークされたレコードはスキップされ、クライアントに返されません。更新の場合も同様のアプローチが取られます。同じキーを持つ 2 つのレコードの場合、タイムスタンプが新しいレコードのみが返されます。図 7 は、同じキーを持つ別々のテーブルに格納されているデータをマージによって結合する方法を示しています。図に示すように、Alex のレコードのタイムスタンプは書き込まれた時点では 100 であり、電話番号が更新された後のレコードのタイムスタンプは 200 です。ジョンの記録は抹消されました。他の 2 つのエントリはマークされていないため、そのまま残ります。

図7 例: マージ手順

検索する必要がある SSTable の数を減らし、キーを検索するときにすべての SSTable をチェックしないようにするために、一部のストレージシステムでは、ブルームフィルター10 と呼ばれるデータ構造を使用します。ブルームフィルタは、要素がセットのメンバーであるかどうかを検出するために使用できる確率的なデータ構造です。偽陽性一致 (つまり、要素がセットのメンバーではないのに、その要素がセットのメンバーであると示す) は生成されますが、偽陰性一致 (つまり、結果が一致しない場合は、要素がセットのメンバーではないはず) は生成されません。言い換えると、ブルームフィルターを使用すると、キーが「おそらく SSTable にある」か「間違いなく SSTable にない」かを判断できます。 SSTable が Bloom フィルターによって不一致として返された場合、クエリではスキップされます。

LSMツリーの維持

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

読み取りコストを削減し、マークされたレコード領域を統合し、ディスク常駐テーブルの数を減らすために、LSM ツリーには圧縮プロセスが必要です。圧縮プロセスでは、ディスクから SSTable 全体を読み取り、それらをマージします。 SSTable はキーでソートされるため、圧縮プロセスはマージソートと同様に機能し、操作も非常に効率的です。レコードは複数のデータソースから順番に読み取られ、マージされた出力は結果ファイルに一度に順番に追加できます。マージソートの利点の 1 つは、メモリに収まらない大きなファイルをマージする場合でも効率的に機能することです。結果のテーブルでは、元の SSTable の順序が維持されます。

圧縮プロセス中、マージされた SSTable は破棄され、図 8 に示すように、より「コンパクトな」テーブルに置き換えられます。圧縮操作の入力は複数の SSTable であり、出力は結合されたテーブルです。一部のデータベースシステムでは、同じサイズのテーブルを論理的に同じ「レベル」にグループ化し、レベル内に十分な数のテーブルがある場合にマージプロセスを開始します。圧縮により、処理する必要がある SSTable の数が減り、クエリがより効率的になります。

図8: 締め付けプロセス

原子性と耐久性

I/O 操作の数を減らし、連続性を保つために、B ツリーと LSM ツリーはどちらも、更新が実際に発生する前にメモリ内で更新をバッチ処理します。つまり、障害が発生した場合にデータの整合性が保証されず、アトミック性 (一連の変更がすべて、単一の操作であるかのようにアトミックに適用されるか、まったく適用されないかのいずれか) も耐久性 (プロセスクラッシュや停電が発生した場合にデータが一貫したストレージに保持されることを保証する) も保証されません。

この問題を解決するために、多くの最新のストレージシステムでは WAL テクノロジ (Write-Ahead Logging) が使用されています。 WAL の主な考え方は、データベースの状態変更はすべて、まずディスク上にある追加専用のログに保存されるというものです。操作中にプロセスクラッシュが発生した場合、データが失われず、すべての変更がアトミックであることを確認するために、ログが再実行されます。

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

LSM ツリーでは、メモリテーブルに加えられたがディスクに完全にフラッシュされていない変更を永続化するために WAL が使用されます。 memtable が完全にフラッシュされ、切り替えられると、新しく作成された SSTable で読み取り操作を完了でき、フラッシュされた memtable データを保持する WAL セグメントを破棄できます。

要約する

B ツリー構造と LSM ツリー構造の最大の違いの 1 つは、最適化の目的と重要性にあります。

以下は B ツリーと LSM ツリーの比較です。要約すると、B ツリーには次の特性があります。

B ツリーは変更可能であり、ある程度のスペースのオーバーヘッドとより関連性の高い書き込みパスを犠牲にして、インプレース更新をサポートします。 B ツリーでは、完全なファイルの書き換えや複数ソースのマージは必要ありません。
B ツリーは読み取り最適化されています。つまり、B ツリーは複数のソースから読み取る必要がないため (したがって、後続のマージ操作も不要)、読み取りパスが簡素化されます。
書き込みによってノードのカスケード分割がトリガーされる可能性があり、一部の書き込み操作のコストが高くなる可能性があります。
B ツリーは、バイトアドレスが存在しないページ化された (ブロックストレージ) 環境向けに最適化されています。これらは、バイトアドレス指定が不可能なページ環境 (ブロックストレージ) 向けに最適化されています。
書き換えも必要ですが、B ツリーストレージは通常、LSM ツリーストレージよりもメンテナンスが少なくて済みます。
同時アクセスには、一連のロックとラッチを伴う読み取り/書き込みの分離が必要です。

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

LSM ツリーは書き込み可能ではありません。 SSTables はディスクに一度書き込まれ、その後は更新されません。圧縮操作では、複数のデータファイルからエントリを削除し、同じキーを持つデータをマージすることで、スペースを統合します。圧縮中、マージされた SSTable は破棄され、マージが成功すると削除されます。非書き込み可能によって提供されるもう 1 つの便利な機能は、フラッシュされたテーブルに同時にアクセスできることです。
LSM は書き込みが最適化されています。これは、書き込み操作がキャッシュされ、ディスクに順番にフラッシュされ、ディスク上の空間的な局所性をサポートする可能性があることを意味します。
読み取り操作では、複数のデータソースからのデータにアクセスする必要がある場合があります。異なる時間に書き込まれた同じキーを持つデータは、異なるデータファイルに分類される可能性があるためです。レコードがクライアントに返される前に、統合プロセスを経る必要があります。
キャッシュされた書き込みがディスクにフラッシュされるため、LSM ツリーではメンテナンスと圧縮が必要です。

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

ストレージシステムの開発には、考慮すべき課題や要素が常に存在します。最適化の目標は、ストレージシステムの選択に大きな影響を与えます。書き込みに多くの時間を費やすことができれば、読み取りに効率的な構造を展開し、インプレース更新用に余分なスペースを確保することができます。これにより、書き込み操作が高速化され、メモリ内のデータのキャッシュが可能になり、順次書き込み操作が保証されます。しかし、これらすべてを一度に達成することはできません。当社の理想的なストレージシステムは、読み取りコストと書き込みコストが最も低く、その他のオーバーヘッドがありません。しかし、実際には、データ構造は複数の要素の間で妥協する必要があります。これらのトレードオフを理解することは非常に重要です。

ハーバード大学の DASlab (データシステム研究所) の研究者は、データベースシステムの最適化のための 3 つの主要なパラメータ、つまり読み取りオーバーヘッド、更新オーバーヘッド、メモリオーバーヘッド (総称して「RUM」) をまとめました。特定のユースケースにとってこれらのパラメータのどれが最も重要であるかを理解することは、データ構造、アクセス方法、さらには特定のワークロードへの適合性にも影響を及ぼします。これは、アルゴリズムを特定のユースケースに合わせて調整する必要があるためです。

「RUM 仮説」(http://daslab.seas.harvard.edu/rum-conjecture/)2 は、RUM 項の 2 つに上限を設定すると、3 つ目の項にも下限が設定されると述べています。たとえば、B ツリーは、書き込みオーバーヘッドと余分なスペース (したがってメモリオーバーヘッド) が予約されることを犠牲にして読み取りが最適化されます。 LSM ツリーではスペースのオーバーヘッドが少なくなりますが、読み取り操作中に複数のディスク常駐テーブルにアクセスする必要があり、読み取りオーバーヘッドが発生します。これら 3 つのパラメータは完全な三角形を形成し、そのうちの 1 つを改善すると、他の項目を妥協することになります。図9はRUM仮説を示しています。

図9 RUM仮説

B ツリーは読み取りパフォーマンスに最適化されています。インデックスは、ツリーをトラバースするために必要なディスクアクセスの数が最小限に抑えられるようにレイアウトされます。データを検索するときは、1 つのインデックスファイルのみにアクセスする必要があります。これは、インデックスファイルを書き込み可能な状態にしておくことで実現されます。書き込み可能性により、ノードの分割、マージ、再配置、および断片化/不均衡に関連するメンテナンスによって引き起こされる書き込み増幅の問題が増加します。更新コストを軽減し、分割数を減らすために、B ツリーは各レベルのノードに追加の空き領域を予約します。これにより、ノードがいっぱいになるまで書き込み増幅の問題を延期することができます。つまり、B ツリーは、読み取りパフォーマンスを向上させるために、更新とメモリのオーバーヘッドの間でトレードオフを行います。

LSM ツリーは書き込みパフォーマンスに最適化されています。更新する場合でも削除する場合でも、ディスク上のデータを見つける必要があります (B ツリーでも必要です)。 LSM ツリーは、すべての挿入、更新、および削除操作をメモリ常駐テーブルにキャッシュすることで、順次書き込みを保証します。このコストは、メンテナンスのオーバーヘッドの増加、圧縮操作の必要性（圧縮は、増大する読み取りコストを軽減し、ディスク常駐テーブルの数を減らすための方法にすぎません）、および読み取りコストの増加（複数のソースからデータを読み取ってマージする必要があるため）です。同時に、LSM ツリーは空き領域を維持しないため、メモリのオーバーヘッドがいくらか削減されます (平均使用率が 70% の B ツリーノードとは異なり、インプレース更新には一定量のオーバーヘッドが必要です)。 LSM ツリーの最終ファイルは書き込まれないため、より優れた使用率を実現するにはブロック圧縮をサポートする必要があります。つまり、LSM ツリーは、読み取りパフォーマンスと、より優れた書き込みパフォーマンスと低いメモリオーバーヘッドの維持との間のトレードオフです。

望ましい特性ごとに、その特性に最適化されたデータ構造が存在します。適切なデータ構造を使用して読み取りパフォーマンスを向上させると、メンテナンスコストが高くなります。トラバーサルを容易にするためにメタデータを追加すると (部分カスケードなど)、書き込み時間に影響し、スペースを占有しますが、読み取り時間は短縮されます。圧縮技術 (Gorilla 圧縮6、デルタエンコーディング、その他のアルゴリズムなど) を使用すると、書き込み時のデータのパックと読み取り時のデータのアンパックにオーバーヘッドが追加され、メモリ効率が最適化されます。場合によっては、機能性と効率性をトレードオフできることもあります。たとえば、ヒープファイルとハッシュインデックスは、ファイル形式が単純なため、優れたパフォーマンス保証と小さいスペースオーバーヘッドを提供できますが、実行ポイントクエリのみがサポートされるという欠点があります。 Bloom フィルター、HyperLogLog、Count-Min スケッチなどの近似データ構造を使用することで、空間の精度と効率をトレードオフすることもできます。

読み取り、更新、メモリの 3 つの調整可能なコストは、データベースを評価し、データベースがどのようなワークロードに適しているかをより深く理解するのに役立ちます。これら 3 つはいずれも非常に直感的で、ストレージシステムをバケットに分類し、パフォーマンスを推測し、詳細なテストを通じてこの仮説を検証することが簡単です。

もちろん、ストレージシステムを評価する際には、メンテナンスコスト、操作の簡便性、システム要件、頻繁な更新と削除への適合性、アクセスパターンなど、他の重要な要素もあります。 RUM 仮説は、直感を与え、初期の方向性に関する経験則を提供することのみを目的としています。私たち自身のワークロードを理解することは、スケーラブルなバックエンドシステムを構築するための第一歩です。

実装によって一部の要素が異なる場合があります。同様のストレージ設計原則を使用する 2 つのデータベースであっても、動作がまったく異なる可能性があります。データベースは、多くの可動部分を持つ複雑なシステムです。データベースは、多くのアプリケーションにとって重要かつ不可欠な部分でもあります。パフォーマンスのトレードオフは、データベースの基本的なメカニズムを理解するのに役立ちます。基礎となるデータ構造と内部原則の違いを理解することで、最適な選択を行うことができます。

参考文献

Comer, D. 1979. ユビキタスBツリー。コンピューティングサーベイ11(2); 121-137;

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.6637.

ハーバード大学 DASlab。RUM 予想。

http://daslab.seas.harvard.edu/rum-conjecture/.

Graefe, G. 2011. 最新のBツリー技術。データベースの基礎と動向3(4): 203-402;

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.219.7269&rep=rep1&type=pdf.

MySQL 5.7 リファレンスマニュアル。InnoDB インデックスの物理構造。

https://dev.mysql.com/doc/refman/5.7/en/innodb-physical-structure.html を参照してください。

O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. 1996. ログ構造化マージツリー. Acta Informatica 33(4): 351-385;

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782.

Pelkonen, T.、Franklin, S.、Teller, J.、Cavallaro, P.、Huang, Q.、Meza, J.、Veeraraghavan, K. 2015.「Gorilla: 高速でスケーラブルなインメモリ時系列データベース」VLDB Endowment 誌 8(12): 1816-1827;

http://www.vldb.org/pvldb/vol8/p1816-teller.pdf.

鈴木秀. 2015-2018. PostgreSQLの内部構造;

http://www.interdb.jp/pg/pgsql01.html.

Apple HFS Plus ボリューム形式。

https://developer.apple.com/legacy/library/technotes/tn/tn1150.html#BTrees

Mathur, A.、Cao, M.、Bhattacharya, S.、Dilger, A.、Tomas, A.、Vivier, L. (2007)。新しい ext4 ファイルシステム: 現在の状況と将来の計画。Linux シンポジウムの議事録。カナダ、オタワ: Red Hat。

ブルーム、BH（1970）、許容誤差を伴うハッシュコーディングにおける空間/時間のトレードオフ、Communications of the ACM、13（7）：422-426

<<: 世界トップ13の産業用ロボット専門家

>>: 機械学習を使用して、GPU と TPU で高速化できる O(N) 複雑度のソートアルゴリズムを構築します。