一週間のLSM

シンプルなキーバリューストレージエンジンを1週間で構築しましょう!

チュートリアル

このチュートリアルは https://skyzh.github.io/mini-lsm で入手できます。付属のスターターを使用できます コードを使用してプロジェクトを開始し、チュートリアルに従ってLSMツリーを実装します。

発達

cargo x install-tools
cargo x check
cargo x book

参照ソリューションでパブリック API を変更した場合は、スターター クレートに同期する必要もあります。 これを行うには、.

cargo x sync

経過

チュートリアルは8つの部分で構成されています(7日で完了できます)。

• 1日目:エンコードをブロックします。SSTは複数のデータブロックで構成されています。ブロックエンコーディングを実装します。
• 2日目:SSTエンコーディング。
• 3日目:メモリテーブルとマージイテレータ。
• 4日目:キャッシュとエンジンをブロックします。ディスクI / Oを削減し、パフォーマンスを最大化するために、moka-rsを使用してブロックキャッシュを構築します LSM ツリーの場合。この日には、APIを備えた機能的な(ただし永続的ではない)キー値エンジンを取得します。

  get

  put

  scan

  delete

• 5日目:圧縮。次に、SSTの平準化された構造を維持します。
• 6日目:回復。再起動後にエンジンが回復できるように、WALとマニフェストを実装します。
• 7日目:ブルームフィルターとキー圧縮。これらは、LSMツリー構造で広く使用されている最適化です。

今のところ、4日目までのリファレンスソリューションと4日目までのチュートリアルがあります。