Mkyong

WiscKey：SSDを意識したストレージの値からキーを分離する



Wisckey Separating Keys From Values Ssd Conscious Storage



2019-12-20
  • 記事のタイトル：WiscKey：SSDを意識したストレージの値からキーを分離する。 TOS17に掲載された拡張アプリケーションペーパーであるFAST16に関する記事。
  • SLMDB最適化LSMKVストアの組み合わせについて読む前に、LSMについてより深く理解する必要があります。
  • 主にLSMKV永続ストレージに基づく論文は、特にSSDデバイスのデータレイアウトを最適化する方法を示しています
  • ところで、会議転送ジャーナルの典型的な例....（エスケープ

概要

  • WiscKey、ベースのLSM Tree KV永続ストレージ、パフォーマンスのためのデータレイアウト最適化
  • WiscKeyの設計は、ランダムシーケンスとデバイスのパフォーマンス特性を使用して高度に最適化されたSSDです
  • LevelDBおよびRocksDBと比較して、パフォーマンスが大幅に向上します

前書き

導入された関連概念

  • KV永続ストレージ：その効率的な挿入ポイント範囲の検索およびクエリ機能により、永続ストレージは多くの最新のアプリケーションストアの基盤になっています。
  • LSM-Trees KVストア：
    • 書き込みに敏感な負荷の場合、KVベースのストレージソリューションLSMツリーは業界の主流ソリューションになりました。
    • LSMツリーは順序を保証するため、バッチ書き込みモードの使用は、導入されたランダムな小文字のBツリーと比較して、ハードウェアIOを助長します。これは、SSDまたはHDDの両方で、シーケンシャル書き込みのパフォーマンスがランダム書き込みよりも優れているためです。

問題を解決するため

  • LSMツリー秩序を保証するために、より深刻な問題の書き込み増幅があります（LSMツリーは特定の原因に関連するプレゼンテーションを参照します）
  • 従来のSSDのLSMツリー相関特性は特に友好的ではありません（SSDの十分に活用されていないプロパティ）
    • SSDのランダム書き込みとシーケンシャル書き込みのパフォーマンスギャップは比較的小さく、元のLSMツリーは良いよりも害があります したがって、ランダム書き込みを減らし、書き込みに多くのメモリ帯域幅を使用することは、不要な無駄になる可能性があります（LSMツリーが存在する場合でも、シーケンシャル書き込みとランダム書き込みのパフォーマンスギャップによるHDDは大きいですが、書き込み増幅に深刻な問題がありますが、シーケンシャル書き込み機能によってLSMがHDDに実装されるようにすることで、パフォーマンスを大幅に向上させることができます）
    • SSD内の並列処理が十分に活用されていない 元のLSMツリーはSSDの内部並列処理を考慮していません
    • SSDの寿命は深刻な影響を受けます書き込み増幅の問題に影響を与えます 元のLSMツリーの深刻な書き込み増幅は、書き換え可能な多くの問題を引き起こす可能性があります

提案されたプログラムの紹介

  • WiscKey：SSD向けに提案された永続的なKV最適化ストレージソリューションであるLevelDBLSMベースのGMを実現
  • コアアイデア：キーと値の分離、LSMツリーに格納されたキー、ログインに格納された値（キーの並べ替えとガベージコレクションの分離）
  • 実装の効果：LSMツリーは、ライトアンプリフィケーションの問題が軽減されるという利点を保持しています

問題の解決

  • 注文するときは、ライトアンプリフィケーションを減らすために不要な値の移行を避けてください
  • LSMツリーは、少量のデータであるキーのみを格納するため、ストレージデバイスへのアクセス数が減り、キャッシュの使用が容易になります。

プログラムが直面している課題と解決策

分離KV
  • 整然としたストレージの価値はなく、パフォーマンス範囲クエリ（スコープクエリ）に影響を与える可能性があります->エクスプロイト並列処理内のSSDは、範囲クエリのパフォーマンスを向上させます（ 救済策 ）。
  • 値はガベージコレクションである必要があり、無効なスペースをリサイクルします->軽量のオンラインガベージコレクションメカニズムを提案しました。これにはシーケンシャルI / Oのみが含まれます。
  • 一貫性のクラッシュを実現する方法->クラッシュガベージデータの時点では添付されていない機能の最新のファイルシステムを利用し、同じ効果を実現するための一貫性とメカニズムを確保するように設計されていますLSMツリー

プログラムテスト結果はじめに

  • 比較：LevelDB、RocksDB
  • テストロード：LevelDBのマイクロベンチマーク、YCSBマクロベンチマーク

試験結果：

  • LevelDBのマイクロベンチマーク：
    • データベースのロード：WiscKeyLevelDBが2.5x-111xより高速
    • ランダムルックアップ：WiscKeyLevelDBが1.6x-14xより高速
    • 小さな値をランダムな順序で書く：悪い
    • 大規模なデータセットは、順次クエリされます：悪い
  • YCSBマクロベンチマーク：
    • 6種類の負荷の下で、WiscKeyのパフォーマンスが向上します

バックグラウンド

  • のメインセクション LSMツリー 、 LevelDB 、 増幅リテラシー と 新しいメモリデバイス 4つの部分について説明します。

LSMツリーとLevelDB

画像

増幅リテラシー

  • LevelDBの例では、その存在の分析は増幅を読み取ります
  • 根本原因：ディスク上のデータが厳密なグローバル順序になっていることを確認する

主な理由

  • 書く：
    • ディスク上のレベル間のサイズ制限は通常10倍の差があり、上位層L（i）下位層L（i + 1）が圧縮されていることを意味し、最悪の場合、L（i + 1）すべてのデータを読み取る可能性がありますデータをマージしてソートするレイヤーL（i）レイヤー、新しいデータはL（i + 1）レイヤーをソートした後に結果を完了するために書き込まれ、SSTableの10倍の状況下で単純な2レイヤーの最悪のデータ中に圧縮されますファイルデータの移行が発生する可能性があります。
    • この極端な場合、データをL0レイヤーからレイヤーL6に移行する必要がある場合、データは移行数の50倍に達します。
  • 読んだ：
    • 拡大された読み取りの理由の1つ：多層構造は、多層クエリデータクエリの必要性につながります。最悪の場合、照会スキャン操作は8つのSSTableファイルL0レイヤーであり、下位レイヤーはレイヤーL6、つまり合計8 + 6 = 14のクエリファイルまで検索を続けません。 （L0レイヤーに格納されている各ファイルのSSTableはキーが重複している可能性があり、すべてのファイルをトラバースする必要がありますSSTable L0レイヤー、およびレイヤーL1〜L6キーは厳密に順序付けられているため、ファイルを読み取るだけで済みます）
    • センスアンプを引き起こす2番目の理由：SSTableで対応するキー値を見つけるために、多くの場合、複数のファイルメタデータブロックを読み取る必要があります。 （インデックスブロック、ブルームフィルターブロックおよびデータブロック）。 KV 1KBの読み取りでは、16KBのインデックス、ブルームフィルターデータ、4KBブロック4KBブロック、つまりセンスアンプを24回読み取る必要があります。
    • したがって、最悪の場合、センスアンプは24 * 14 = 336倍に達し、IOが小さいと、増幅の読み取りにさらに深刻な問題が発生する可能性があります。

新しいメモリデバイス

LSMはSSDの理由で適しています

  • シーケンシャルランダムIOIOのパフォーマンスと比較してパフォーマンスが低いSSDHDD。
  • SSD自体の書き込み消去とSSD損傷のガベージコレクションメカニズムにより、ランダム書き込みが優れています。
  • したがって、必要なLSMシーケンシャル書き込みデータを確保するには

その他の機能SSD

  • HDDと比較して、IOパフォーマンスSSDのランダムおよびシーケンシャルIOパフォーマンスのギャップは小さい
  • ランダムIOパフォーマンスSSDはHDDのランダムパフォーマンスよりも優れています
  • テストの結果、SSDに近いシーケンシャル書き込みパフォーマンスの一部のシーンでのSSDの同時ランダム書き込みパフォーマンスが見つかりました
    画像

WiscKey

  • 4つのコアアイデア：
    • キー値、LSMツリーに保存されているキー、値を分離すると、別のログファイルに保存されます
    • ログファイルに保存されたランダム処理の値（ハードディスクには範囲クエリへのランダムアクセスが必要）、SSDランダム読み取り内部のパフォーマンスを向上させる並列処理のWiscKeyの利点
    • WiscKeyは、特別なセーフガードメカニズムとクラッシュコンシステントなガベージコレクションメカニズムを使用して、値に対応するログを効率的に管理します
    • WiscKeyは、LSMツリーログを除く前提の一貫性を確保してパフォーマンスを向上させ、特に小さなIOのオーバーヘッドを削減します

キーと値の分離

  • 問題の解決策：バックグラウンドでの従来のLSM-Treeの最大のタスクは、圧縮のパフォーマンスオーバーヘッドです。圧縮は、主にファイルのディスク上のマルチレベル構造間で実行されるIO操作の順序を保証することですSSTableマージソート、そのため、多数のファイルの移行やその他の操作を読み取る必要があります。

理論的根拠

  • WiscKeyの並べ替えは、キーを並べ替えるだけで済みます。値SSDは、他の場所のアドレス、キーと値の間の保存された関連付けを使用するのに適しています。LSMツリーに保存されます。キーアドレスです。この実施形態は、ソートプロセスにおけるデータの量を大幅に減らすことができ、それによって書き込み増幅の問題を減らすことができる。 16Bキー-1024B値、WiscKeyを採用した従来のライトアンプリフィケーション係数10倍の2つのレイヤー間、（16 * 10 + 1024）/（16 + 1024）= 1.14。 ここで計算される増幅率は正確ではないことに注意してください。増幅プロセスで保存されるアドレスのサイズと 。
  • 増幅は書き込みを減らし、消去はそれに応じてSSDの書き込みを減らし、SSDの寿命を延ばします
  • 新しいセンスアンプ問題の導入かどうか？それは存在しますが、全体的なパフォーマンスを向上させるためにセンスアンプが少なくなっています。 LSMツリーに格納されるデータ量は従来のKVに比べて大幅に減少し、LSMツリーからデータ情報を読み取るため、WiscKeyはまずこのキーを読み取り、次に読み取り速度を読み取ります。対応するデータ量に応じてアドレスに対応する値は次のようになります。比較的大きい方が速いです。さらに、LSMツリーキャッシュメモリを使用してキーの取得を高速化する少量のデータにも対応します。

構造とプロセス

画像
組成：
  • LSMツリー-ストア
  • 値ログファイル-ストレージ値
処理する
  • インサート ：値最初の値がログに追加で書き込まれ、対応するキーと値のアドレス情報（主にオフセットアドレス情報vlog-offsetとvalue-sizeに対応するValueデータのサイズを含む）がキーに挿入されます-のLSMツリーで構成される値のペア
  • 削除 ：対応するLSMツリーキーで直接削除します。値ログは含まれません。対応する値は、ガベージコレクションメカニズムによって一律に処理されます。
  • ポイント/範囲クエリ ：LSMツリーに移動して対応するキーを取得した後、対応する値ログファイルから対応する値アドレス情報を取得して、対応する値を読み取ります。

KV分離に対応する課題（問題）

並列クエリの範囲並列範囲クエリ

  • 範囲クエリの重要性とアプリケーションのシナリオは繰り返されません。外部から提供される範囲クエリを実現するための簡単なAPILevelDBの順序です。
    • Seek（key）、Next（）、Prev（）、Key（）、Value（）
    • キー呼び出し（）が最初のキーの検索を開始し、次に呼び出しまたは前に1つずつキーを取得し、必要な実際のポインターを取得してキーに対応します。値は値（）と呼ばれます。
問題
  • 従来のLSMツリーLevelDBは、範囲クエリ操作中にKVペアがLSMツリーに順次格納されるため、順次IOを読み取ることができますが、WiscKeyのスキームは分離されたKVであり、必然的にランダムな書き込みが発生します。問題の価値。
  • ランダムSSD書き込みおよびランダム書き込み特性がセクションに導入されましたが、パフォーマンスは比較的低くなっています。
ソリューションと実装
  • ソリューション ：前のセクションでは、内部IO並列ランダムSSDのパフォーマンスをテストしました。特定の条件下では、IOの速度に達する可能性があります。並列処理を改善して、ランダムIOによる影響を軽減すると考えられます。
  • 実現する方法 ：操作のための範囲クエリ、連続キーの要求が発生すると、シーケンスの読み取りを開始する順序の値、多数の後続キーからのWiscKey LSMツリー、キーアドレス情報が対応するキューに挿入され、その後マルチスレッドを開始して、キューからアドレス情報を再度取得し、情報内の対応する値値ログファイルを同時に読み取ります。

ガベージコレクションを実現するためのガベージコレクションメカニズム

  • LSMツリーのガベージコレクションの従来の方法は、削除するデータまたは古いデータに対してマークが付けられ、圧縮プロセスの実装でガベージデータがリサイクルされます。
  • WiscKeyは圧縮プロセスValueを使用しないため、ガベージコレクションの値をガベージコレクションに分離するメカニズムを設計する必要があります。
アイデアのガベージコレクションの実現
  • 最も簡単な方法（最も直接的な方法）：キー値の値タグに保存されたスキャンLSMツリーキーに対応するすべての有効な有効アドレス。対応するファイルはゴミ箱のログデータに保存されておらず、その後回復されます。
  • より効率的な方法：WiscKey調整データレイアウト。
実現する方法
  • データレイアウト：外部に対応するログ値値のアクセス情報に加えて、キーに対応するアクセスデータ。データユニットはタプルになります。タプルは、キーサイズ、値サイズ、キー、値で構成されます。
  • ガベージコレクション操作用のヘッドポインタとテールポインタ、ガベージコレクションが移動される場合のみのテールポインタ、追加データが値ログファイルに書き込まれる場合のヘッドポインタが提供されます。
  • ごみ収集プロセス ：テールポインタの位置から読み取られたWiscKeyは、現在の値が書き込みまたは削除でカバーされているかどうかを判断するためのLSMツリークエリのセットにキー情報があるかどうかによって、約数MBのチャンクサイズのキーKVセットを指します。 。値は、有効な状態がヘッドポインターの追加の位置に書き込まれ、次にチャンクに対応するテールポインターの空きストレージスペースに書き込まれ、テールポインターの位置が更新されると判断されます。
    画像
一貫性を確保するためのガベージコレクションプロセス
  • データの損失（ガベージコレクション中に障害が発生したなど）を回避するには、新しいストレージスペースと永続デバイスへのテールポインタに対応する追加の書き込みをリリースする前に、新しい有効な値を確認する必要があります。
  • 次のガベージコレクションステップ中のWiscKeyの一貫性：
    • さらに、ログの値に新しい値を書き込みます
    • 値ログファイルの同期であるfsync（）を呼び出します
    • 値の同期アドレスと新しいアドレスは、LSMツリーのテールポインタに書き込まれます。 （テールポインタはキー：テール-値：テール-vlog-オフセットの形式で保存されます）
    • 最後に、適切なガベージコレクション、対応するスペースを解放します
ガベージコレクション時間
  • WiscKeyは、主に次の2つの方法で、実際のニーズに応じて構成できます。
    • 定期的に実行されるガベージコレクション
    • トリガーガベージコレクションが特定のしきい値に達する

クラッシュの一貫性はクラッシュの一貫性を保証します

  • WALが挿入したKVペアのアトミック性を保証するために使用される従来のLSMツリーのクラッシュ整合性保証は、厳密な挿入順序で復元できますが、一貫性メカニズムを保証するLSMツリーKVの個別の方法のおかげで、より複雑になります。
  • WiscKey達成一貫性メカニズムは、ファイルシステムの機能を利用します。システム障害のイベント、データ損失の発生、順次書き込みのデータシーケンスX1 X2 X3 ...、X1が失われると、X1以降のすべてのデータが失われます。 OSDI固有の説明は、すべてのファイルシステムが等しく作成されていないの記事14を参照してください：クラッシュコンシステントアプリケーションの作成の複雑さについて。
実装/プロセスフロー
  • データが失われるため、対応するLSMツリーで欠落しているキーが見つからない場合は、リターンエアまたはキーとして従来のLSMツリーにアプローチします。 （Value Vlogファイルに書き込まれていても、ガベージコレクションになります）
  • LSMツリーを探すためのキーがある場合、従来のLSMツリーよりも複数の操作をチェックします。これは主にLSMツリーからの操作を検証し、有効なVlogファイルの範囲内の値のアドレス情報がキーのアドレスとクエリへのキー値アクセスは同じです。チェックが失敗した場合、対応するLSMツリーキーが削除され、クライアントのキーが見つかりませんに返されます。
  • Vlogをチェックするための問い合わせの価値、キー対応情報、マジックナンバー、またはチェックサムメカニズムを使用してチェックを容易にすることもできます。
  • ユーザーがデータ同期の挿入を要求すると、LSMツリーキーはクラッシュ後のシステムの永続性も保証しますWiscKeyと同期は、ブラシバックの同期データのLSMツリーキーに対応する同期の前に挿入することによっても実現できますVlogデータの挿入。

最適化

  • KVの個別の対応により、新しい考え方が生まれ、オリジナルのLSMツリーログオンバリューログの書き込みと書き込みが行われました。最適化プログラムは、対応するログ書き込みパフォーマンスの向上に重点を置いています。

値-ログ書き込みバッファ

  • 各書き込み操作の値ログ、システムは書き込み（）を呼び出し、機密性の高い負荷を挿入するために、さまざまな帯域幅のデバイスに対して多数の小文字のファイルシステム操作を開始し、適切なサイズの書き込みユニットを選択します非常に必要です。
書く
  • オーバーヘッドを削減するために、バッファタンク内のデータがユーザーによって設定されたしきい値に達した場合にのみバッファリングメカニズムを使用するWiscKeyユーザースペース、または同期挿入操作を使用する場合は、データにブラシで戻るだけで、書き込み（呼び出し数）が削減されます。 。
読んだ
  • クエリ、WiscKeyは、Vlogファイルから読み取るキーがなくなった場合、最初にVLogでバッファをクエリするキーがあるかどうかを検索します。
問題
  • システム障害によってバッファ内のデータが失われる可能性がある場合、その整合性が崩壊すると、LevelDBでも同じことが保証されます。 疑問に思う？ ？ ？ ？ ？

最適化LSMツリーログ

  • 設計のLSMツリーログの開始は、挿入LSMツリーが、障害が発生したときに、挿入順序に従ってログファイルから適切に回復できるようにキーと値のペアの整合性を確保することです。
  • ガベージコレクション以降のWiscKeyの設計、Vlog Ketに追加された情報に保存されたデータ構造、ログはキーLSMツリーにのみアクセスする役割を果たしてきました。
回復
  • また、スキャンVlogのLSM障害回復データのキーで直接回復することもできます。
  • データ復旧モード、つまりVlogスキャンモードまたは2つに分割：
    • （最も簡単ですが最も効果が低い）データ復旧のためにファイルVlog全体をスキャンする
    • より効率的な方法 ：データの一部のみをスキャンするため、またガベージコレクションメカニズムが導入されているため、データが書き込まれたときにのみ移動するHEADポインターが導入されているため、byItへの情報WiscKeyHEADポインターがLSMツリーに挿入されます。
  • データ復旧プロセス ：データベースを開くと、WiscKey VLogは、LSMツリーに保存されているファイルHEADの最近の情報を、これまでのチームに対応するテールポインターのスキャン位置までスキャンします。
  • 多数の小文字の操作の場合、LSMツリーログの省略された書き込み操作により、パフォーマンスが大幅に向上します。

成し遂げる

  • Vlogのさまざまなコンポーネントにアクセスするため、posix_fadvise（）を使用して、クエリvlogのランダムアクセス操作を許可するなど、さまざまな所定のパターンのvlogセンスにアクセスすると、ガベージコレクターをテールポインターの位置から順番に読み取ることができます。書き込みポインタの先頭アドレスを順次加算して対応します。
  • スレッドプールスレッド（デフォルトではスレッド32）を管理するために使用される範囲クエリは、キュークエリに特定の数のアドレスがある場合、クエリ操作が同時に実行され、これらの値は自動的にキャッシュバッファに対応します。
  • 効率的なガベージコレクションのために、従来の穴あけメカニズムを使用して最新のファイルシステムを使用し、WiscKeyの弾力性のあるストレージスペースを確保します。

評価

テスト環境

  • プロセッサー：2 x Intel（R）Xeon（R）CPU E5-2667 v2 @ 3.30GHz
  • メモリ：64GB
  • オペレーティングシステム：64ビットLinux 3.14
  • ファイルシステム：ext4
  • ストレージデバイス：500 GB Samsung 840 EVO SSD（SeqR 500MB / S、SeqW 400MB、内部並列処理SSDとしてのテストのRandRead正面図）
  • ワークロード：マイクロベンチマーク、YCSBベンチマーク

マイクロベンチマーク

  • LevelDBのデフォルトのマイクロベンチマーク、つまりdb_benchを使用します
  • キーサイズの修正16B、値のサイズの変更
  • データ圧縮が無効

ロードパフォーマンスロードパフォーマンス

  • SeqLoadとRandLoadに分けられます。 （違いは、データを挿入するためのデータベースの構築順序、順序付き挿入、ランダム挿入です）
チャートの説明
  • 図7と図9はそれぞれ、ランダムなプロパティ変更を伴うデータのロードとロードのシーケンスを示しています。値の変更サイズ、見つけるのが難しいWiscKeyはデバイスの帯域幅を利用し、LevelDBデバイスの帯域幅とパフォーマンスは特にランダムなプロセスです。データをロードするため。
  • 図8は、データをロードするための時間LevelDB、さまざまなサイズのValueのロード時間の負荷分布を示しています。時間の消費には、ログファイルの書き込み、MemTableの書き込みなどの3つの部分があります。Memtableをディスクにブラシで戻します。
  • 図10より直感的な統計的ライトアンプリフィケーションファクター
画像
原因分析
  • 読み込みと読み込みのパフォーマンスのランダムなシーケンス、パフォーマンスの向上は主にWiscKeyであり、LSMツリーは大きなオーバーヘッドをログに記録せず、WiscKeyはLSMツリーを省略し、Vlogの方法を使用して、直接書き込みの追加のパフォーマンスを低下させます。したがって、クライアントからの要求の処理が拒否された場合、LevelDBのスループットに影響します。 WiscKey LSMキーは少量のデータにしかアクセスしないため、オーバーヘッドが小さく、帯域幅をより有効に活用できます。
  • 図8では、値が小さく、ログファイルに書き込まれるメインに費やされる時間（主に小さいIOがfsync（）呼び出しの数に対応するため、前述の長い理由）、大きいIO、Memtableの書き込み、および並べ替えログは比較的効率的であり、この時点でのブラシバックMemtableがボトルネックになります
  • ライトアンプリフィケーション係数の理由WiscKey特に少量の主に小さいLSMデータのツリーWiscKey

クエリパフォーマンスクエリパフォーマンス

画像
分析
  • 図11の場合、WiscKeyがLSMツリーと値ログを照会する必要がある場合でも、スループットはLevelDBよりも優れています。これは主に、前述のLevelDB増幅の深刻な読み取りの問題、LSMツリーの小さいボディマス自体によるWiscKey、センスアンプの対応によるものです。問題はそれほど深刻ではありません。さらに、LSMツリーWiscKeyは、圧縮プロセスがもたらすIOの影響が多すぎないために存在しません。
  • 図12の場合、4KBより前、4 KBを超える後の特定の上昇傾向値のように、データ読み込み範囲クエリの両方のランダムシーケンスのLevelDBは、SSTableファイルのみが格納するキーと値のペアKVの量が少ないため、オーバーヘッドは大きなものに集中します。開いているファイルの数、およびSSTableがインデックスデータブロックとブルームフィルターデータを読み取ると、スループットは低下傾向になり始めます。この点で、WiscKeyのオーバーヘッドははるかに小さいため、値の時間が4KBを超えると、WiscKeyのパフォーマンスが向上します。
  • サイズ64-Bの値、12倍の差のLevelDBよりもWiscKeyのパフォーマンス。これは、特定の制限されたWiscKeyに対する小さなランダム読み取り要求の並列デバイスのサイズが高スループットの並列ランダム読み取りSSDで比較的高いパフォーマンスを発揮するためです。 。さらに、これは最悪の場合のワークロード、つまりランダムに入力されたデータベースであり、データはvLogでソートされていません
  • シーケンシャルロードロードの場合、図12のランダムロードロードに示されている傾向データは類似しています。値のサイズが64Bの場合、WiscKeyのパフォーマンスはLSMツリーよりも劣っていました。しかし、ランダムデータの読み込みと比較すると、違いは比較的小さく、パフォーマンスを向上させるために採用されたWiscKeyを並べ替えるランダムなvlogデータに読み込むことができ、64BLevelDB以降の同じシーンのギャップを減らすことができます。

その他のテスト

画像
ガベージコレクション
  • 負荷の影響下でのガベージコレクションはプログラム全体のパフォーマンスに大きな影響を与えるため、ガベージコレクションのパフォーマンスをテストするために負荷を使用してランダムにロードされます。
  • テストモード：最初にデータをランダムにロードし、次に特定の割合のデータを削除してガベージコレクションをトリガーし、次に再ランダム化してデータをロードします。この時点でパフォーマンスをテストします。
  • このテストでは、値のサイズは4KBであり、さまざまな比率の空き領域をテストした場合のパフォーマンスです。
  • 分析：ガベージコレクターが無効なデータが100％であることを検出した場合、つまり、すべてのデータがガベージデータである場合、コピーオーバーヘッドがないため、この時点で書き込まれます。パフォーマンスは約10％低下するだけで、一部のデータは有効であり、約35％、追加のバックグラウンドガベージコレクションスレッド書き込みが必要なため。しかし、35％低下したとしても、パフォーマンスはLevelDBよりも少なくとも70％高くなっています。
適合性テストのクラッシュ
  • テストツール：ALICE、ツールを選択し、システムクラッシュの多面的なセットをシミュレートします。これらのクラッシュは、データの不整合につながる可能性があります
  • テストケース：この問題により、ext4、xfs、btrfsで少数の同期および非同期PUT操作がトリガーされ、データの不整合は発生しませんでした
  • また、主に最大回復時間をテストするために、回復時間をテストしました。 LevelDBの最長リカバリ時間は、ログファイルのサイズと、Memtableが最大になる前にファイルがディスクに書き込まれる時間によって異なります。この場合も、WiscKeyが最長のリカバリを必要としました。 1KBの値の場合、LevelDBの回復には約0.7秒かかりますが、WiscKeyには約2.6秒かかります。
拡大された空間空間増幅
  • 以前の研究は、読み取りと書き込みの増幅の問題のみに焦点を当てており、空間増幅の問題にはほとんど注意が払われていません。空間増幅率は、データベースのサイズと、占有されているディスク上の論理的意味データベースの実際のサイズの比率です。 KVなどの1KBのキーと値のペアがディスクスペース4KBを占める可能性がある場合、スペースの拡大率は4になります。
  • LSM Treeの従来の圧縮プロセスでは、増幅の問題に対応するスペースの量を減らし、それによってディスクスペースの使用率を向上させます。ロードスペースのシーケンシャルロードの場合、通常は1増幅率に近く、ロードロードの場合、ロード増幅率は一般にスペースよりも大きくなります（無効なデータがガベージコレクションに十分な時間ではない場合）。
  • 図14は、ランダムデータセットをロードする100GBの各ストレージスペースのメインプログラムのオーバーヘッドを示しています。一方、オーバーヘッドストレージスペースにWiscKey-GCがあり、Valueのサイズが大きくなると、メタデータ情報は、ユーザーデータの実際のサイズに近いオーバーヘッドWiscKey-GCの値に比べて十分に小さくなります。つまり、メタデータのサイズは比較的小さくなります。 。ただし、スペースオーバーヘッドのWiscKey相対LevelDBは大きくなります。
  • ストレージシステムは、書き込み増幅、増幅、および空間センスアンプを削減しながら達成することはできません。ストレージシステムでは、多くの場合、3つの増幅率に対応するトレードオフの間で行われます。増幅率を下げるためのLevelDBスペース、圧縮メカニズムの導入は、それに応じて、ライトアンプリフィケーションにも深刻な問題を引き起こします。 IO増幅のロード動作中のWiscKeyを減らすために、必然的にスペースの拡大の問題が発生します。
CPU使用率-CPU使用率
画像
  • LevelDBによるシーケンシャル書き込みロードの場合、各KVオーバーヘッドをエンコードして対応するログファイルに保存する必要があるため、WALオーバーヘッドに多くの時間がかかります。対応するCPUも比較的大きくなります。オーバーヘッド先行書き込みログを省略して、CPU占有率が比較的低くなるように、WiscKeyが最適化した実施形態。
  • RangeQueryの場合、WiscKeyは複数のスレッドを使用して同時に読み取りと書き込みを行うため、LevelDBのCPU占有率が高くなります。
  • LevelDBは多数の操作（シングルライター、バックグラウンド圧縮）が使用されるシングルスレッドテクノロジーであるため、実際にはCPUパフォーマンスのボトルネックを制限するよりもLevelDB、およびRocksDBはマルチコアシステム用であるため、マルチスレッド圧縮の使用が含まれています。

YCSBベンチマーク

  • YCSBベンチマークは、ここでは説明していません。実際のシーン、KVストレージシステムテストをシミュレートするために、読み取り操作と書き込み操作のさまざまな比率を使用することです。
    画像
  • 注目に値する点は、小さい値を使用する場合のガベージコレクションWiscKeyの場合、ガベージコレクターユニットのデフォルトサイズはチャンクであるため、4MBであるため、値に対応するキーと値のペアの数が少ないほど、キーは有効です。より多くのLSMツリーで必要な回数を確認すると、パフォーマンスが比較的低下します。

関連作業

その他のプログラムはじめに

KVストアのハッシュテーブルに基づく

  • FAWN：KVはSSDに保存され、ログを書き込むために追加されます。メモリに格納されているインデックスメンテナンスハッシュテーブルは、クエリのみを高速化します。
  • FlashStoreとSkimpyStash：FAWNの設計に従いますが、メモリ内のハッシュインデックスを最適化します。 FlashStoreはカッコウハッシュを使用し、ハッシュテーブルの線形リンク部分を使用してSSDへの署名モバイルSkimpyStashをキー圧縮します
  • BufferHash：複数のメモリHASHテーブル、およびブルームフィルターを使用して対応するHASHテーブルクエリを選択します
  • SILT：主にメモリ、ログ構造化ツリー、ハッシュテーブル、およびソート済みリストの組み合わせで使用されるデータ構造用に最適化されています

KVストアの元のLSMツリーの最適化

  • bLSM：新しい複合スケジューラーの書き込みレイテンシー制限を提供します。これにより、一定の書き込みスループットを維持し、ブルームフィルターを使用してパフォーマンスを向上させます。
  • VT-tree：間接参照を使用することにより、VT-tree [50]は、以前にソートされた-ソートされた値の圧縮中に結合を回避します。
  • LOCS：チャネルは内部フラッシュLSMツリーキーストレージに公開されます。これは、達成された豊富な並列処理を使用して、より効率的な圧縮を行うことができます。
  • アトラス：ARMプロセッサとイレイジャーコーディングに基づく分散ストレージキー、さまざまなハードキーと値が格納されています。
  • LSM-trie：trie構造を使用してキーを整理し、trieのより効率的な圧縮方法に基づいて提案しましたが、この設計では、クエリの有効範囲のサポートなど、LSMツリーの一部の機能が犠牲になりました。
  • RocksDB：RocksDBの設計とLevelDBは本質的に類似しているため、書かれた倍率はまだ高いですが、マルチスレッドのLevelDB圧縮の使用と比較されます。
  • Walnut：LSMツリーに小さなオブジェクトを格納するミキシングオブジェクトストアと、ファイルシステムに直接書き込まれる大きなオブジェクト。
  • IndexFS：メタデータはそのに保存されます
    特定の挿入を高速化するための、列タイプのパターンを持つLSMツリー
  • 純度：インデックスを格納するために時系列でソートされたタプルとデータタプルは、インデックスのみで区切られます

KVベースのストレージエンジンの他のデータ構造

  • TokuDB：フラクタルツリーに基づくフラクタルツリーインデックスは、ソートされていないノードキーの内部バッファを更新し、良好なパフォーマンスを得るために、大きなメモリ内インデックスを維持する必要があります。
  • ForestDB：HB + -trieは長いキーインデックスを効果的に使用し、パフォーマンスを向上させ、内部ノードのオーバーヘッドスペースを削減します
  • NVMKV：キーストレージサポートFTL。トランザクションサポートスパースアドレッシングなどのローカルFTL機能を使用し、単一操作のキーベクトルストレージインターフェイスにさらに多くの要求パケットを提案しました。

最適化スキームは、メモリのKey-Valueストアのスケーラビリティのボトルネックを克服します

  • マストリー
  • MemC3
  • Memcache
  • 小さい
  • cLSM
  • 上記のスキームの後、WiscKeyに基づくさらなる最適化に使用できます

参考文献

  • Patrick ONeil、Edward Cheng、Dieter Gawlick、
    とエリザベスオニール。ログ構造化マージツリー（LSMツリー）。 Acta Informatica、33（4）：351–385,1996。

問題

拡張する

参照リンク

論文 ストレージ FAST 2017-2019 文学の読み書きスキル エルビス

簡単な方法または正しい方法。