# WiscKey WiscKey [LU16] は、[[LSMツリー]]によってキーがソートされた状態を保ちつつ、ガベージコレクションからソート処理を切り離し、vLog(値ログ)と呼ばれる順序付けられていない追記型のファイルでデータレコードを保持する設計である。このアプローチにより、[[Bitcask]] が抱えていた2つの問題(すべてのキーをメモリ内に保持しなければならないこと、起動時にハッシュテーブルを再構築しなければならないこと)を解決する。 vLog ファイルには順序付けされていないデータレコードが保持され、キーはソートされた LSM ツリーに格納されてログファイル内の最新のデータレコードをポイントする。キーは関連付けられたデータレコードよりはるかに小さいため、圧縮の効率が高い。このアプローチは、ガベージコレクションでそれほど大きなディスク領域が解放されない、更新・削除の頻度が低いユースケースで特に有効である。 主要な課題は、vLog のデータがソートされていないため、範囲スキャンでランダム I/O が必要になることである。WiscKey では範囲スキャン時にブロックをパラレルにプリフェッチし、内部的な SSD のパラレル処理を使ってランダム I/O のコストを削減するが、1つのデータレコードを取り出すだけでもそれが含まれるページ全体を読み取る必要があるため、ブロック転送の観点でコストは高いままである。 コンパクション時には vLog ファイルの内容がシーケンシャルに読み取られ、マージされ、新しい場所に書き込まれる。LSM ツリー内のポインタはこれらの新しい場所を指すよう更新される。vLog 全体をスキャンしなくて済むよう head ポインタと tail ポインタが使用される。vLog のデータはソートされておらず無効な情報を含むため、キーツリーをスキャンしてどの値がまだ有効かを確認する必要があり、これが従来の LSM ツリー(コンパクション時にキーインデックスを扱わずに済む)と比べてガベージコレクションの複雑さを増す要因になる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] §7.4.2) ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] - 概念: [[LSMツリー]] - エンティティ: [[Bitcask]](解決対象とする2つの問題の出所) ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]](§7.4.2 WiscKey — インデックスLSMツリーとvLogの分離、範囲スキャンのコスト、ガベージコレクションの複雑さ)