🧒🏾 #⃣ 👩🏽‍🎓 レコードのデータストレージ 🤚 👨🏿‍🚒 🙎🏽

2016年、 Highloadでタランツールのディスクにデータを保存するためのエンジンであるVinylについて講演しました。それ以来、多くの新機能を追加しましたが、ディスクにデータを保存することは非常に膨大なトピックであるため、この記事で説明する基本的なことはまったく変更していません。

コンテンツ（ナビゲートしやすくするため）：

なぜ新しいエンジンを作成したのですか？

ご存じのとおり、Tarantoolは、データを100％RAMに保存するトランザクション対応の永続DBMSです。 RAMに保存する主な利点は、速度と使いやすさです。データベースを調整する必要はありませんが、パフォーマンスは安定して高いままです。

数年前、データキャッシュのみがRAMに格納され、バルクがディスクに消去される通常のDBMSのように、従来のストレージテクノロジーを使用した製品の拡張に困惑しました。 MySQLで実装されているように、ストレージエンジンはテーブルごとに個別に選択できると決めましたが、同時にトランザクションサポートは最初から実装されていました。

最初に答える質問は、独自のエンジンを作成するか、既存のライブラリを使用するかです。オープンソースコミュニティには、使用可能な既製のライブラリがあります。選択時には、RocksDBライブラリが最も積極的に開発され、現在では最も人気のあるライブラリの1つになりました。しかし、WiredTiger、ForestDB、NestDB、LMDBなど、あまり知られていないライブラリも多数ありました。

それでも、既存のライブラリのソースコードを見て、すべての長所と短所を比較検討して、独自のライブラリを作成することにしました。

現在存在するすべてのサードパーティライブラリは、データリクエストがオペレーティングシステムの複数のスレッドから送信され、データへの同時アクセスを制御する複雑な同期プリミティブを含むことを前提としています。そして、それらを私たちのアーキテクチャに組み込むと、ユーザーは何も返品せずにマルチスレッドアプリケーションのコストを負担せざるを得なくなります。

実際、Tarantoolはアクターベースのアーキテクチャに基づいています。専用スレッドでトランザクションを処理するアプローチにより、不必要なロック、プロセス間通信、およびマルチスレッドDBMSのCPU時間の最大80％を消費するその他のオーバーヘッドコストなしで実行できます。

Tarantoolプロセスは、一定数の役割ベースのスレッドで構成されています。

また、最初に協調マルチタスクに注目してストレージサブシステムを設計する場合、作業を大幅にスピードアップできるだけでなく、マルチスレッドエンジンには複雑すぎる最適化を実装することもできます。一般に、サードパーティのソリューションをTarantoolに統合しても、最良の結果は得られません。

アルゴリズム

既存のライブラリを埋め込むという考えを捨てたため、独自のアーキテクチャを構築するためのアーキテクチャに基づいて決定する必要がありました。現在、ディスクにデータを保存するためのソリューションには2つの世代があります。さまざまなBツリーと、LSMツリー（ログ構造化マージツリー）に基づいて構築された新しいBツリーを使用します。たとえば、MySQL、PostgreSQL、OracleはBツリーを使用し、Cassandra、MongoDB、CockroachDBはすでにLSMを使用しています。

同時に、Bツリーは読み取りに対してより効率的であり、LSMツリーは書き込みに対してより効率的であると考えられています。ただし、書き込みパフォーマンスに比べて読み取りパフォーマンスが数倍高いSSDの急増により、ほとんどのシナリオでLSMの利点が明らかになりました。

TarantoolでLSMツリーがどのように配置されるかを理解する前に、それらがどのように機能するかを見てみましょう。これを行うには、通常のBツリーのデバイスとそれに関連する問題を分析します。

Bツリーの名前の「B」はブロックを意味します。つまり、ブロックで構成されるバランスの取れたツリーです。ブロックには、要素のソートされたリスト、つまりキーと値のペアが含まれます。ツリーの充填、バランス調整、分割、およびブロックのマージの質問は省略します;詳細はウィキペディアで読むことができます。その結果、コンテナは昇順キーでソートされ、その最小要素は左端のノードに格納され、最大要素は右端のノードに格納されます。 Bツリーがデータを検索および更新する方法を見てみましょう。

クラシックBツリー

要素を見つける必要がある場合、またはその存在を確認する必要がある場合は、通常どおり、上から検索を開始します。キーがルートブロックで見つかった場合、検索は終了します。それ以外の場合は、最も小さいキーを持つブロック、つまり、必要な要素よりも小さい要素がまだある最も右のブロックに移動します（すべてのレベルの要素は昇順で配置されます）。そこに要素が見つからない場合は、再び下のレベルに移動します。最後に、葉の1つに自分自身を見つけ、おそらく、目的の要素を見つけます。ツリーのブロックはディスクに保存され、メモリ全体で読み取られると想定されます。つまり、1回の検索でアルゴリズムはlog _B （N）ブロックを読み取ります。Nはツリーの要素数です。最も単純で最も大規模な場合の記録も同様に実行されます。探している要素を含むブロックを見つけ、その中の値を更新（挿入）します。

この構造を視覚化するために、100,000,000ノードのツリーを取得し、ブロックサイズが4096バイト、要素サイズが100バイトであると仮定します。ブロックでは、オーバーヘッドコストを考慮して、最大40個の要素を配置できます。ツリーには約2,570,000ブロック、5つのレベルがあり、最初の4つは約256 MB、最後の約10 GBを占めます。明らかに、最新のコンピューターでは、最後のレベルを除くすべてのレベルがファイルシステムキャッシュに正常に到達し、実際には、読み取り操作に必要なI / O操作は1つだけです。

視点を変えると、状況はずっとバラ色に見えません。単一のツリーアイテムを更新するとします。ツリーの操作はブロックの読み取りと書き込みを行うため、1ブロックをメモリに読み取り、4096から100バイトを変更して、新しいブロックをディスクに書き込む必要があります。したがって、変更されたデータの実際の量の40倍を記録する必要がありました。 SSDディスクの内部ブロックサイズは64 KB以上になる可能性があり、要素のすべての変更が完全に変更するわけではないことを考慮すると、ディスクの「スプリアス」負荷の量はさらに大きくなる可能性があります。

ディスクストレージに関する文献やブログでの「偽の」読み取りの現象は読み取り増幅と呼ばれ、偽の読み取りの現象は書き込み増幅と呼ばれます。正式には、増幅係数、つまり増倍率は、実際に必要な（または変更された）サイズに対する実際に読み取られた（または書き込まれた）データのサイズの比率として計算されます。 Bツリーの例では、係数は読み取りと書き込みの両方で約40になります。

データを更新するときの偽のI / O操作の量は、LSMツリーが解決する主な問題の1つです。仕組みを見てみましょう。

LSMツリーと従来のBツリーの主な違いは、LSMがデータ、つまりキーと値を保存するのではなく、データ操作（挿入と削除）を保存することです。

たとえば、挿入操作の要素には、キーと値に加えて、操作コードを含む追加のバイトが含まれています-図ではREPLACEとして示されています。削除には、要素のキー（値を保存する必要はありません）およびDELETEオペレーションコードが含まれます。また、各LSM要素には、操作シーケンス番号ログシーケンス番号（LSN）が含まれています。これは、各操作を一意に識別する単調に増加するシーケンス値です。したがって、ツリー全体が最初にキーの昇順で、1つのキー内でLSNの降順で並べられます。

シングルレベルデバイス

LSMツリー充填

ディスクに完全に保存され、RAMに部分的にキャッシュできるBツリーとは異なり、LSMツリーでは、メモリとディスクの分離が最初から明確に存在します。同時に、揮発性メモリにあるデータの安全性の問題は、ストレージアルゴリズムの枠から外されています。たとえば、変更を記録するなど、さまざまな方法で解決できます。

RAMにあるツリーの部分は、L0（レベル0）と呼ばれます。 RAMの量は限られているため、L0には固定領域が割り当てられます。たとえば、Tarantool構成では、サイズL0はvinyl_memoryオプションで指定されます。最初に、ツリーに要素が含まれていない場合、操作はL0に書き込まれます。ツリー内の要素は昇順キー、降順LSNの順に並んでいるので、このキーに新しい値を挿入すると、前の値を簡単に検出して削除できることを思い出してください。提示されるL0は、要素の順序を保持する任意のコンテナです。たとえば、TarantoolはストレージにL0 B + *-ツリーを使用しています。これについてはブログで説明しました。 L0での検索および挿入操作は、L0を表すために使用されるデータ構造の標準操作であり、それらについては詳細に検討しません。

遅かれ早かれ、ツリー内の要素の数はサイズL0を超えます。次に、L0はディスク上のファイルに書き込まれ、新しい挿入のために解放されます。この操作はダンプと呼ばれます。

ディスク上のすべてのダンプは、LSNで順序付けられたシーケンスを形成します。ファイル内のLSN範囲は重複せず、シーケンスの先頭に近いのは、より新しい操作のファイルです。これらのファイルをピラミッドの形で想像してみましょう。新しいファイルを上部に、古いファイルを下部に配置します。新しいファイルが表示されると、ピラミッドの高さが大きくなります。この場合、最新のファイルに既存のキーの削除または置換操作が含まれている場合があります。古いデータを削除するには、ガベージを収集する必要があります（このプロセスは、マージと呼ばれることもあるマージと呼ばれ、マージと翻訳されることもあります）。マージ中に同じキーの2つのバージョンが見つかった場合、新しいバージョンのみを残しておけば、キーを挿入した後に削除された場合、両方の操作を結果から除外できます。

LSMツリーの有効性の重要な要素は、どの時点でどのファイルに対してマージが行われるかです。キーとしてのツリーが、1、2、3 ...という形式の単調なシーケンスを格納し、削除操作がないことを想像してください。この場合、マージは役に立たなくなります-すべての要素は既にソートされており、ツリーにはゴミが含まれていません。どのファイルに各キーが含まれているかを明確に判断できます。対照的に、ツリーに多くの削除操作が含まれている場合、マージによりディスク領域が解放されます。ただし、削除がなく、異なるファイルのキー範囲が大きく重複している場合でも、表示するファイルの数が減るため、マージにより検索が高速化されます。この場合、各ダンプの後にマージすることが理にかなっている場合があります。ただし、このようなマージはディスク上のすべてのデータを上書きするため、読み取りが少ない場合は、マージの頻度を減らすことをお勧めします。

上記のシナリオのいずれかでLSMツリーを最適に構成するために、LSMはすべてのファイルをピラミッドに編成します。データ操作が新しいほど、ピラミッド内のファイルは高くなります。この場合、ピラミッド内の2つ以上の隣接ファイルが合併に関与します。可能であれば、ほぼ同じサイズのファイルが選択されます。

ほぼ同じサイズのすべての隣接ファイルは、ディスク上のツリーのレベルを構成します。レベルでのファイルサイズの比率により、ピラミッドの比率が決まります。これにより、集中的な挿入または集中的な読み取りのためにツリーを最適化できます。

サイズL0が100 MBであり、各LSMレベル（vinyl_run_size_ratio変数）でのファイルサイズのステップ（比率）が5であり、各レベルで2つ以下のファイル（vinyl_run_count_per_level変数）が存在できるとします。最初の3つのダンプの後、それぞれ100 MBの3つのファイルがディスクに表示され、これらのファイルはL1レベルを形成します。 3> 2以降、ファイルのマージ（圧縮）が開始され、その結果、サイズが300 MBの新しいファイルが表示され、古いファイルは削除されます。さらに2回のダンプの後、マージが再び開始され、今度はそれぞれ100、100、および300 MBのファイルがサイズ500 MBのファイルがレベルL2（レベルサイズの比率は5）に移動し、レベルL1は「空」になります。さらに10個のダンプが通過し、L2レベルでそれぞれ500 MBの3つのファイルを取得します。その結果、サイズが1500 MBのファイルが1つ作成されます。各100 MBの3つのファイルをマージし、100、100、300 MBのファイルを2回マージする別の10回のダンプの後、L2レベル500 MBでさらに2つのファイルを取得します。その結果、マージは既にL2レベル。2500MBで最初のファイルを作成します。このファイルは、そのサイズのため、L3レベルに移動します。

プロセスは無期限に続行でき、LSMツリーワークフローで多くの削除がある場合、マージの結果として形成されるファイルは、ピラミッドを下に移動するだけでなく、上に移動することができます。これは、マージ中に使用されるソースファイルが少ないためです。言い換えれば、ファイルのサイズと、そこに格納されているすべての操作の中での最小および最大LSNに基づいて、ファイルの所属を論理的に追跡するだけで十分です。

LSMツリー形状制御

検索するファイルの数を減らす必要がある場合、さまざまなレベルでのファイルサイズの比率が増加し、その結果、レベルの数が減少します。逆に、コンパクションによって生じるコストを削減する必要がある場合、レベルサイズの比率が低下し、ピラミッドがより高くなり、コンパクションはより頻繁に実行されますが、より小さなファイルで平均的に機能します。一般に、指定されたN-ツリーのすべての要素の合計サイズ、L0-レベルゼロのサイズとx-レベルサイズの比率（level_size_ratio）、LSMツリーの書き込み増幅は、式log _x （N / L0）×x、またはx×ln（N / C0）/ ln（x）、Nのxのグラフ/ C0 = 40（ディスク：メモリ比）は次のようになります。

読み取り増幅は、レベルの数に比例します。各レベルでの検索のコストは、Bツリーでの検索のコストを超えません。 100,000,000の要素、256 MBのRAM、およびvinyl_level_size_ratio = 3.5およびrun_count_per_level = 2のパラメーターの標準値の「標準」ツリーの場合、書き込み増幅係数は約13になります。同時に、読み取り増幅は最大150になります。増幅はとても大きくなります。

検索する

LSMツリーで検索する場合、要素自体ではなく、それを使用した最後の操作を見つける必要があります。これが削除操作の場合、探しているアイテムはツリーにありません。これが挿入操作の場合、検索要素はLSMピラミッドの最高値に対応し、最初のキー一致で検索を停止できます。最悪の場合、ツリーの値は最初は存在していませんでした。次に、L0から始まるツリーのすべてのレベルで検索が繰り返されます。

残念ながら、実際にはこの最悪のケースは非常に一般的です。たとえば、主キーまたは一意キーのツリーに挿入する場合、重複がないことを確認する必要があります。 LSMで「存在しない」値の検索を高速化するために、確率的データ構造（ブルームフィルター）が使用されます。それらの詳細については、Vinylの内部構造のセクションで説明します。

範囲検索

1つのキーで検索する場合、最初の一致後にアルゴリズムが終了し、範囲内のすべての値、たとえば姓が「Ivanov」であるすべてのユーザーを検索するには、ツリーのすべてのレベルを表示する必要があります。

範囲検索[24,30）

この場合の望ましい範囲の形成は、ファイルをマージするときと同じです：すべてのソースから最大のLSNを持つキーが選択され、このキーの残りの操作は破棄され、検索位置は次のキーにシフトされます。

削除する

削除をまったく保存しないのはなぜですか？そして、たとえば、i = 1,10000000 put（i）delete（i）endのスクリプトで、これがツリーのオーバーフローを引き起こさないのはなぜですか？

検索中の削除操作の役割は、目的の値がないことを通知し、マージするときに、古いLSNの「ジャンク」レコードのツリーをクリアすることです。

データがRAMにのみ保存されている限り、削除を保存する必要はありません。また、マージがツリーの最下位レベルにも影響する場合、マージ後に削除を保存する必要はありません。これには、最も古いダンプのデータが含まれます。実際、最後のレベルに値が存在しないということは、ツリーに値が存在しないことを意味します。

削除、ステップ1：L0に挿入

削除、ステップ2：廃棄（tombstone）は中間レベルを通過します

削除、ステップ3：主要な圧縮の廃棄標識がツリーから削除されたとき。

一意の値の挿入の直後に削除が行われることがわかっており、これがセカンダリインデックスの値が変更される頻繁なケースである場合、削除操作は中間レベルのマージで既に除外できます。この最適化はVinylに実装されています。

LSMの利点

書き込み増幅の削減に加えて、L0レベルを定期的にダンプ（ダンプ）し、L1-Lkレベルをマージ（圧縮）するアプローチには、Bツリーで使用される書き込みアプローチに比べていくつかの利点があります。

ダンプとコンパクションは比較的大きなファイルを書き込みます。通常のL0サイズは50〜100 MBで、これはBツリーブロックのサイズの数千倍です。
サイズが大きいため、記録する前にデータを効率的に圧縮できます。 Tarantoolは自動的に圧縮するため、書き込みの増幅がさらに減少します。
ファイル内の要素はボイド/パディングなしで互いに続くため、断片化コストはありません。
すべての操作で新しいファイルが作成され、古いデータは変更されません。これにより、私たちに嫌われているロックを取り除くことができますが、いくつかの操作は互いに競合することなく並行して実行できます。また、データをレプリカに簡単にバックアップおよび転送できます。
古いバージョンのデータを保存すると、複数バージョンの同時実行制御アプローチを使用してトランザクションサポートを効果的に実装できます。

LSMの欠点とその除去

検索のためのデータ構造としてのBツリーの主な利点の1つは予測可能性です。すべての操作にlog _B （N）しかかかりません。従来のLSMでは、読み取り速度と書き込み速度の両方が、最高でも最悪でも、何百倍も何千倍も異なる可能性があります。たとえば、L0に要素を1つだけ追加するとオーバーフローが発生し、L1、L2などのオーバーフローが発生する可能性があります。読み取りプロセスでは、L0のソース要素を検出でき、すべてのレベルが関与する可能性があります。 Bツリーに匹敵する速度を実現するには、同じレベルでの読み取りも最適化する必要があります。幸いなことに、多くの欠点は、補助アルゴリズムとデータ構造を使用して明るくしたり、完全に除去したりできます。これらの欠点を体系化し、タランツールで使用されるそれらの対処方法を説明します。

予測不可能な書き込み速度

LSMツリーへのデータの挿入には、ほとんど常にL0のみが含まれます。 L0に割り当てられたRAMの領域がいっぱいの場合、ダウンタイムを回避する方法は？

L0の解放には、ディスクへの書き込みとメモリの解放という2つの長い操作が含まれます。 L0をディスクに書き込む際のダウンタイムを避けるため、Tarantoolは先書きを使用します。

L0のサイズが256 MBだとしましょう。ディスクへの書き込み速度は10 MB /秒です。その後、L0をディスクに書き込むのに26秒かかります。データ挿入速度は1秒あたり10,000リクエストで、1つのキーのサイズは100バイトです。記録のために、使用可能なRAMを約26 MB確保し、実際に使用可能なサイズL0を230 MBに減らします。

Tarantoolはこれらすべての計算を自動的に行い、DBMSの負荷の移動平均とディスク速度のヒストグラムを常にサポートします。これにより、L0を可能な限り効率的に使用し、書き込み操作で使用可能なメモリを待機するタイムアウトを回避できます。負荷が急激に増加しても、待機は可能です。そのため、貼り付け操作のタイムアウト（vinyl_timeout）もあります。デフォルト値は60秒です。記録自体は専用スレッドで実行され、その数（デフォルトでは2）はvinyl_write_threads変数によって設定されます。値を2にすると、圧縮と並行してダンプすることができます。これは、予測可能なシステム操作にも必要です。

Tarantoolマージは、ダンプに関係なく、実行の別のスレッドで常に実行されます。これは、ツリーの追加のみの性質により可能です。書き込み後、ツリー内のファイルは決して変更されず、圧縮は新しいファイルを作成するだけです。

L0のローテーションとディスクに書き込まれたメモリの解放も遅延につながる可能性があります。記録プロセス中、オペレーティングシステムの2つのスレッドがL0のメモリを所有します。トランザクション処理ストリームと書き込みストリームです。回転したL0には要素は追加されませんが、検索に参加できます。検索中の読み取りロックを回避するために、書き込みストリームは書き込まれたメモリを解放しませんが、このタスクをトランザクション処理スレッドに残します。ダンプの完了後、自動的に解放されます。これには、L0で専用のアロケーターが使用され、1回の操作ですべてのメモリを解放できます。

ダンプは、いわゆる「シャドウ」L0から取得され、新しい挿入と読み取りをブロックしません

予測不可能な読み取り速度

読み取りは、LSMツリーの最適化にとって最も難しいタスクです。複雑さの主な要因は、多数のレベルです。これにより、検索が何度も遅くなるだけでなく、ほぼすべての最適化の試みに対してメモリ要件が増加する可能性があります。幸いなことに、LSMツリーの追加のみの性質により、これらの問題を従来のデータ構造の標準ではない方法で解決できます。

圧縮およびページネーションインデックス

Bツリーでのデータの圧縮は、実装するのが難しいタスクであるか、本当に便利なツールというよりもマーケティングツールです。圧縮の実装の難しさに関する詳細は、MySQLとPostgreSQLの実装を比較したAlexei Kopytovの投稿にあります。 LSMの圧縮は次のように機能します。

ダンプまたはマージでは、1つのファイル内のすべてのデータをページに分割します。ページサイズはvinyl_page_size構成オプションによって設定されます。これは、インデックスごとに個別に変更できます。ページは、vinyl_page_sizeで指定されたバイト数を厳密に占有する必要はありません。格納されているデータに応じて、ページはわずかに大きくなったり小さくなったりする場合があります。これにより、ページにボイドが含まれることはありません。圧縮には、Facebookのzstdストリームアルゴリズムが使用されます。各ページの最初のキーとファイル内のページのオフセットは、いわゆるページインデックスに追加されます。これは、目的のページをすばやく見つけることができる個別のファイルです。ダンプまたはマージ後、作成されたファイルのページインデックスもディスクに書き込まれます。すべての.indexファイルはRAMにキャッシュされます。これにより、.runファイルから1回の読み取りで目的のページを見つけることができます（このファイル名拡張子は、ダンプまたはマージの結果のファイルのVinylで使用されます）。ページ内のデータはソートされているため、読み取りと圧縮解除後、目的のキーを簡単なバイナリ検索で見つけることができます。個別のスレッドが読み取りと解凍を担当し、その数はvinyl_read_threads設定オプションで決定されます。

Tarantoolは、すべてのファイルに単一の形式を使用します。たとえば、.runファイルのデータ形式は、.xlogファイル、つまりログファイルの形式と同じです。これにより、バックアップとリカバリ、および外部ツールの作業が簡素化されます。

ブルームフィルター

ページインデックスを使用すると、単一のファイルを検索するときに表示されるページ数を減らすことができますが、ツリーのすべてのレベルで検索する必要がなくなるわけではありません。データの不足をチェックする必要がある重要な特別な場合があり、すべてのレベルを表示することは避けられません：一意のインデックスへの挿入。データが既に存在する場合、一意のインデックスへの挿入は失敗します。 LSMツリーでトランザクションが完了する前にエラーを返す唯一の方法は、挿入する前に検索することです。 DBMSのこれらの種類の測定値は、「非表示」または「疑似」測定値と呼ばれるクラス全体を形成します。

非表示の読み取りにつながる別の操作は、セカンダリインデックスの作成に使用される値の更新です。セカンダリキーは、データが異なる順序で格納される通常のLSMツリーです。ほとんどの場合、すべてのデータをすべてのインデックスに格納しないために、このキーに対応する値は完全にプライマリインデックス（キーと値の両方を格納するインデックスはカバーまたはクラスターと呼ばれます）にのみ格納され、フィールドのみがセカンダリインデックスに格納されますセカンダリインデックス、およびプライマリインデックスに含まれるフィールドの値を作成しました。次に、セカンダリキーの作成に使用される値を変更した場合、まずセカンダリインデックスから古いキーを削除してから、新しいキーを挿入する必要があります。更新中の古い値は不明です。主キーから「内部」で読み取る必要があるのはまさにこれです。

例：

update t1 set city='Moscow' where id=1

特に存在しない値の場合、ディスクからの読み取り回数を減らすために、ほとんどすべてのLSMツリーは確率的データ構造を使用します。 Tarantoolも例外ではありません。クラシックブルームフィルターは、いくつかの（通常3〜5）ビットマップのコレクションです。書き込み時には、いくつかのハッシュ関数がキーごとに計算され、ハッシュ値に対応するビットが各配列に設定されます。ハッシュすると衝突が発生する可能性があるため、一部のビットを2回置くことができます。興味深いのは、すべてのキーを書き込んだ後に付加されなかったビットです。検索では、選択したハッシュ関数も計算されます。ビットマップの少なくとも1つにビットがない場合、ファイルの値は欠落しています。ブルームフィルターがトリガーされる確率は、ベイズの定理によって決まります。各ハッシュ関数は独立したランダム変数であるため、すべてのビット配列で同時に衝突する確率は非常に小さくなります。

Tarantool Bloom Filtersを実装する主な利点は、セットアップが簡単なことです。インデックスごとに独立して変更できる唯一の構成パラメーターはbloom_fpr（fprは偽陽性率を表します）と呼ばれ、デフォルトでは0.05または5％です。このパラメーターに基づいて、Tarantoolは部分キーと完全キーの両方を検索するための最適なサイズのブルームフィルターを自動的に構築します。ブルームフィルター自体は、ページインデックスと共に.indexファイルに保存され、RAMにキャッシュされます。

キャッシング

多くの人々は、すべてのパフォーマンスの問題に対して万能薬をキャッシュすることを検討することに慣れています。理解できない状況では、キャッシュを追加します。 Vinylでは、キャッシュをディスクの全体的な負荷を軽減する手段とみなし、その結果、キャッシュにヒットしなかったリクエストに対してより予測可能な応答時間を取得します。 Vinylは、トランザクションシステム用のユニークなタイプのキャッシュ、レンジタプルキャッシュを実装しています。たとえばRocksDBやMySQLとは異なり、このキャッシュはページを保存しませんが、ディスクから読み込んですべてのレベルでマージした後の既製のインデックス値の範囲を保存します。これにより、単一のキーと一連のキーの両方のリクエストにキャッシュを使用できます。ホットデータのみがキャッシュに格納され、たとえばページのデータは格納されないため（データの一部のみがページで要求できる）、RAMが最も最適に使用されます。キャッシュサイズは、vinyl_cache構成変数によって決まります。

ガベージコレクション管理

おそらく、この場所に到達したので、あなたはすでに焦点を失い始めており、十分な量のドーパミンが必要です。休憩を取る時間です。残りに対処するためには、真剣な努力が必要です。

Vinylでは、1つのLSMツリーのデバイスはパズルの一部にすぎません。 Vinylは、1つのテーブル（スペース）に対しても複数のLSMツリーを作成および管理します（各インデックスに1つのツリー）。ただし、単一のインデックスでさえ、多数のLSMツリーで構成できます。理由を理解してみましょう。

標準的な例を考えてみましょう：各100バイトの100,000,000レコード。しばらくして、LSMの最下位レベルで、10 GBのファイルがある場合があります。最後のレベルのマージ中に、一時ファイルを作成します。これも約10 GBを占有します。中間レベルのデータもスペースを占有します。ツリーは同じキーを使用して複数の操作を保存できます。合計で10 GBの有用なデータを保存するには、最大30 GBの空き領域が必要になる場合があります。10GBが最終レベル、10 GBが一時ファイル、10 GBがその他すべてです。また、データが1 GBではなく1 TBの場合はどうなりますか？空きディスク容量を常に有用なデータの数倍にすることは、経済的に実現不可能であり、1TBファイルの作成には数十時間かかる場合があります。事故やシステムの再起動が発生した場合、操作を新たに開始する必要があります。

別の問題を検討してください。木の主キーが単調なシーケンス、たとえば時系列であると想像してください。この場合、メインの挿入はキー範囲の右側になります。すでに巨大なファイルの末尾に数百万のレコードを追加するためだけに再マージすることは意味がありません。

そして、挿入が主にキー範囲の一部で発生し、他の部分から読み取る場合はどうなりますか？この場合、ツリーの形状を最適化するにはどうすればよいですか？高すぎると、読み取りに影響し、書き込みが低すぎます。

Tarantoolは、インデックスごとに1つだけでなく、多数のLSMツリーを作成することにより、問題を「ファクタリング」します。各サブツリーのおおよそのサイズはvinyl_range_size変数によって設定され、デフォルトは1 GBであり、サブツリー自体は範囲と呼ばれます。

ランキングを使用した大規模なLSMツリーの因数分解

最初、インデックスには要素がほとんどありませんが、1つの範囲で構成されています。いっぱいになると、合計ボリュームがvinyl_range_sizeを超える場合があります。この場合、分割操作が実行されます-ツリーを2つの等しい部分に分割します。分離は、ツリーに格納されているキー範囲の中央の要素によって発生します。たとえば、最初にツリーが-inf ... + infの全範囲を格納している場合、中間キーXで分割した後、2つのサブツリーを取得します。1つは-infからX、もう1つはXから+ infのすべてのキーを格納します。したがって、挿入または読み取りの際に、どのサブツリーを参照するかが明確にわかります。ツリーに削除があり、隣接する範囲のそれぞれが「重量を失った」場合、逆の操作が実行されます-合体。隣接する2つのツリーを1つに結合します。

分割と合体は、マージ、新しいファイルの作成、その他の重い操作にはつながりません。 LSMツリーは単なるファイルのコレクションです。 Vinylでは、どのファイルがどのサブツリーに属しているかを簡単に追跡できる特別なメタデータジャーナルを実装しています。ログには.vylog権限があり、.xlogファイルの形式と互換性があり、.xlogファイルと同様に、すべてのチェックポイントで自動的にローテーションされます。分割または合体を伴うファイルの作成を回避するために、中間エンティティ-スライスを導入しました。これは、メタデータログに排他的に保存されるキー値の範囲を持つファイルへのリンクです。ファイルへのリンクの数がゼロになると、ファイルは削除されます。また、分割または合体が必要な場合、Tarantoolは新しいツリーごとにスライスオブジェクトを作成し、古いスライスオブジェクトを削除し、これらの操作をメタデータログに書き込みます。文字通り、メタデータログには、<tree id、slice id>または<slice id、file id、min、max>の形式のレコードが保存されます。

したがって、ツリーを2つのサブツリーに分割するという難しい作業は、圧縮されるまで遅延され、自動的に実行されます。

キーの範囲全体をサブ範囲（範囲）に分割するアプローチの大きな利点は、L0のサイズと各サブツリーのダンプおよび圧縮プロセスを独立して制御できることです。その結果、これらのプロセスは制御可能で予測可能です。個別のメタデータログを使用すると、truncateやdropなどの操作の実装も簡素化されます。ビニールでは、メタデータログと排他的に動作し、ガベージ削除がバックグラウンドで実行されるため、即座に処理されます。

高度なビニール機能

アップサート

前に、LSMツリーが保存する2つの操作、つまり削除と置換についてのみ記述しました。他の全員がどのように表現されているかを見てみましょう。挿入は置換を使用して表すことができます。同じキーを持つ要素がないことを確認するだけです。更新を実行するには、ツリーから古い値を事前に読み取る必要があるため、この操作は置換としてツリーに簡単に書き込むことができます。これにより、このキーの将来の読み取りが高速化されます。さらに、更新は新しい値を返す必要があるため、隠れた測定値を避けることはできません。

Bツリーでは、非表示の読み取りのコストはほとんどかかりません。ブロックを更新するには、いずれにしても、ディスクから読み取る必要があります。 LSMツリーの場合、非表示の読み取りにつながらない特別な更新操作を作成するというアイデアは非常に魅力的です。

このような操作には、キーにまだデータがない場合に挿入する必要があるデフォルト値と、値が存在する場合に実行する必要がある更新操作のリストの両方が含まれている必要があります。トランザクションの段階で、Tarantoolは操作全体をLSMツリーにのみ保存し、マージ中にのみ「実行」します。

操作アップサート

残念ながら、操作をマージ段階に延期した場合、エラーを処理するための適切なオプションはありません。そのため、Tarantoolはツリーに書き込む前に、可能な限りupsert操作を検証するように努めていますが、一部のチェックは、古いデータのみを使用して実行できます。たとえば、更新によって文字列に数値が追加されたり、存在しないフィールドが削除されたりした場合。

同様のセマンティクスを持つ操作は、PostgreSQLやMongoDBを含む多くの製品に存在します。しかし、それらのすべてにおいて、更新と置換を組み合わせた構文上の砂糖にすぎず、DBMSに隠された読み取りを実行する必要性を軽減することはありません。その理由は、ストレージのデータ構造としてのLSMツリーの相対的な新規性だと思います。

アップサートは非常に重要な最適化であり、実装されたときに多くの血を飲みましたが、その適用性は限られていることを認めなければなりません。テーブルに二次キーまたはトリガーがある場合、隠された読み取り値を避けることはできません。セカンダリキーを必要としないスクリプトがあり、トランザクションの完了後に更新してもエラーが発生しないことは間違いありません。この操作はあなたのためです。

この演算子に関連する話をしたいと思います。 Vinylは成長を始めたばかりで、最初に本番環境でアップサートを開始しました。アップサートの理想的な条件は、キーの巨大なセット、値としての現在の時間です。更新操作は、キーを挿入するか、現在の時刻を更新します。読み取り操作はまれです。ストレステストは優れた結果を示しました。

しかし、数日間の操作の後、TarantoolプロセスはCPUの100％を消費し始め、システムパフォーマンスはほぼゼロまで低下しました。

掘り始めました。キーによるリクエストの分散は、テスト環境で見たものとは大きく異なることが判明しました。それは...まあ、非常に不均一でした。文字通り、キーのほとんどは1日に1〜2回更新され、それらのデータベースは明らかに「スモーク」されました。しかし、キーははるかに熱かった-1日あたり何万もの更新。 Tarantoolは、この一連の更新で素晴らしい仕事をしました。しかし、何万ものupsert'ovのキーで読むと、光を消すことができました。「最後の」値を返すために、Tarantoolは毎回何万ものupsertコマンドのストーリーを読んで「失う」必要がありました。アップサートを設計する際、レベルのマージ中にこれが自動的に行われることを期待していましたが、マージには至らず、L0メモリが十分にあり、LSMツリーはディスクにプッシュすることを急いでいませんでした。

数十個以上のupsert'ovを蓄積したキーの「先読み」読み取り値を提供するバックグラウンドプロセスを追加し、その後、upsert'ovのスタック全体を読み取り値で置き換えることにより、問題を解決しました。

二次キー

更新操作だけでなく、非表示の読み取りを最適化するという深刻な問題があります。置換でも、セカンダリキーがある場合、古い値を強制的に読み取る必要があります。セカンダリインデックスから個別に削除する必要があり、新しい要素を挿入してもこれが行われない場合があり、インデックスにゴミが残ります。

セカンダリインデックスが一意でない場合、それらからゴミを削除することもマージフェーズに転送できます。これはTarantoolで行います。

取引

LSMツリーの追加のみの性質により、Vinylで完全にシリアル化可能なトランザクションを実装できました。読み取り専用リクエストは古いバージョンのデータを使用し、書き込みをブロックしません。トランザクションマネージャ自体は依然として非常に単純です。従来の分類では、MVTOクラスを実装し、最初に完了したトランザクションが競合に勝ちます。それらに固有のロックやデッドロックはありません。奇妙なことに、これは利点よりも不利な点です。パラレル実行では、ロックの適切なタイミングでトランザクションの一部を「保持」することにより、成功したトランザクションの数を増やすことができます。当面の計画におけるトランザクションマネージャーの開発。現在のリリースでは、アルゴリズムを100％正確で予測可能なものにすることに重点を置いています。たとえば、トランザクションマネージャは、いわゆるギャップロックをサポートする数少ないNoSQL環境の1つです。

おわりに

この記事では、ディスクエンジンの配置方法を説明しようとしました。その作業中に、Tarantoolプロジェクトは真剣に成熟しました。今日ではMail.Ru Groupや他のインターネット企業で使用されているだけでなく、銀行、通信会社、および産業部門の企業のサーバーのエンタープライズ版も販売およびサポートしています。今日、ビニール付きのTarantoolの安定バージョンは、Mail.Ru Groupとその外部の両方でテストされており、当社のWebサイトからダウンロードできます。

T +会議は、2018年6月21日にMail.Ruグループオフィスで開催されます。これは、私たちにとって初めてのインメモリコンピューティング会議です。その上で、Vinylのチューニングとモニタリングについて詳しく説明します。私たちはチケットを売ってお金を稼ぐという目標を持っていませんが、会議は支払われます。今日のTarantoolは、産業レベルのソリューションを作成するために自信を持って使用できる数少ないロシアのオープンソースソリューションの1つであるため、このカンファレンスには多くの開発者が集まると確信しています。そのため、会議中に、可能な限り専門的にすべてを行うことも決定しました。

Tarantoolプロジェクトは急速に成長しています。そして、世界クラスのDBMSを一緒に作成するために、志を同じくする人々を常に探しています。この記事に記載されているトピックに強い関心があり、私たちの目標が重要で興味深いと思われる場合は、必ずご連絡ください。私たちには多くの仕事があります。

レコードのデータストレージ