# LLAMA LLAMA(ラッチフリーで、ログ構造化されていて、アクセスメソッドを意識する、Latch-free, Log-structured, Access-Method Aware ストレージサブシステム)は、Bw ツリー(B ツリーのイミュータブルなバージョン)の下層に置かれるレイヤである[Levandoski13]。このレイヤ構成は、Bw ツリーが動的に拡張・縮小することを可能にし、その一方でガベージコレクションとページ管理をツリーに対して透過的にする。 論理的な Bw ツリーのノードは、物理的なデルタノードの連結リストで構成される。これは最新の更新から最古の更新までの更新チェーンで、末尾はベースノードで終わる。論理的なノードはメモリ内のマッピングテーブルでリンクされ、ディスク上の最新の更新の場所をポイントする。キーと値の追加・削除は論理的なノードに対して行われるが、それらの物理的な構成はイミュータブルである。 ログ構造化ストレージは 4 MB のフラッシュバッファでノードの更新(デルタノード)をまとめてバッファリングし、ページが一杯になるとディスクにフラッシュする。定期的に未使用のデルタノード・ベースノードの領域回収がガベージコレクションによって行われ、有効なノードが再配置されて断片化したページが解放される。 もっとも興味深い点は、LLAMA が「アクセスメソッドを意識する」ことである。アクセスメソッドを意識しないと異なる論理ノードに属するインターリーブされたデルタノードは挿入順に書き込まれるが、LLAMA における Bw ツリーへの意識によって複数のデルタノードを単一の連続した物理的場所へ統合できる。挿入に続く削除のように取り消しあう2つの更新も論理的に統合でき、後者の削除だけが永続化される。LSS のガベージコレクションはこの論理的な Bw ツリーのノード内容統合にも対応し、空き領域の回収だけでなく物理的なノードの断片化を大幅に削減する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] §7.7) ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] - 概念: [[B-Tree]](Bw ツリーとの関係) ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]](§7.7 LLAMA と注意深いスタック — デルタノード、フラッシュバッファ、アクセスメソッドを意識したガベージコレクション)