mini-lsm - 一週間でLSM-Treeストレージエンジンを構築するチュートリアル!(仕掛品)

(A tutorial of building an LSM-Tree storage engine in a week! (WIP))

Created at: 2022-12-24 03:16:00
Language: Rust
License: Apache-2.0

一週間のLSM

CI (メイン)

シンプルなキーバリューストレージエンジンを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日目までのチュートリアルがあります。