この記事では、中心となる概念や構造を含め、ログ構造マージ ツリー (LSM ツリー) を理解する方法を説明します。最終的には、LSM-Tree に基づいて独自のストレージ エンジンを最初から構築できるようになります。
ログ構造マージ ツリー (LSM ツリー) は、高スループットの書き込み操作用に最適化されたデータ構造です。 Cassandra、RocksDB、LevelDB などのデータベースやストレージ システムで広く使用されています。
LSM ツリーの重要なアイデアは、まずメモリ内のデータ構造 (通常はスキップ リストや AVL ツリーのような順序付けられた構造) に操作を書き込むことです。その後、これらの書き込みはバッチ処理され、SSTable としてディスクに順次書き込まれるため、ランダム I/O が最小限に抑えられます。
LSM ツリーは 2 つの主要コンポーネントに分かれています:
通常、SSTable の構造には、順序付けされた一連のキーと値のペア (データ ブロック) だけではありません。また、インデックス ブロック、メタデータ ブロック、およびその他のコンポーネントも含まれています。これらの詳細については、実装セクションで詳しく説明します。
データの書き込みには、新しいキーと値のペアの追加または既存のキーと値のペアの更新が含まれます。更新により古いキーと値のペアが上書きされ、後で圧縮プロセス中に削除されます。
データが書き込まれると、まず Memtable に送られ、そこでキーと値のペアがメモリ内の順序付けされたデータ構造に追加されます。同時に、書き込み操作は WAL に記録され、データベース クラッシュ時のデータ損失を防ぐためにディスクに保存されます。
Memtable には定義されたしきい値があります (通常はサイズに基づきます)。 Memtable がこのしきい値を超えると、読み取り専用モード に切り替えられ、新しい SSTable に変換され、ディスク上の レベル 0 に永続化されます。
Memtable が SSTable としてフラッシュされると、対応する WAL ファイルを安全に削除できます。後続の書き込み操作は、新しい Memtable (および新しい WAL) 上で続行されます。
LSM-Tree では、データはすぐには削除されません。代わりに、削除は トゥームストーン と呼ばれるメカニズム (論理的な削除と同様) を使用して処理されます。キーと値のペアが削除されると、「廃棄」のマークが付いた新しいエントリが書き込まれ、対応するキーと値のペアが削除されたことを示します。実際の削除は圧縮プロセス中に行われます。
この廃棄ベースの削除により、LSM ツリーの 追加専用 プロパティが保証され、ランダム I/O が回避され、ディスクへの順次書き込みが維持されます。
データのクエリのプロセスは、Memtable での検索から始まります。キーと値のペアが見つかった場合は、クライアントに返されます。廃棄マークが付けられたキーと値のペアが見つかった場合は、要求されたデータが削除されたことを示し、この情報も返されます。 Memtable でキーが見つからない場合、クエリは レベル 0 から レベル N まで SSTable の検索に進みます。
データのクエリには複数の SSTable ファイルの検索が含まれる可能性があり、ランダムなディスク I/O が発生する可能性があるため、LSM-Tree は一般に、読み取り集中型のワークロードよりも、書き込み負荷の高い ワークロードに適しています。
クエリ パフォーマンスの一般的な最適化の 1 つは、ブルーム フィルター の使用です。ブルーム フィルターは、キーと値のペアが特定の SSTable に存在するかどうかを迅速に判断し、不必要なディスク I/O を削減します。さらに、SSTable のソートされた性質により、バイナリ検索などの効率的な検索アルゴリズムを使用して検索を高速化できます。
ここでは、LevelDB と RocksDB で使用される レベルドコンパクション戦略 を紹介します。
もう 1 つの一般的な戦略は サイズ階層型圧縮戦略 です。この戦略では、新しくて小さい SSTable が、古くて大きい SSTable に連続的にマージされます。
前述したように、SSTable にはキーによってソートされた一連のエントリが保存されます。レベル圧縮戦略では、SSTable は複数のレベル (レベル 0 からレベル N) に編成されます。
レベル 0 では、SSTable は Memtable から直接フラッシュされるため、重複するキー範囲を持つことができます。ただし、レベル 1 から N では、同じレベル内の SSTable に重複するキー範囲はありませんが、異なるレベルの SSTable 間でのキー範囲の重複は許可されます。
説明のための (完全に正確ではありませんが) 例を以下に示します。 レベル 0 では、最初と 2 番目の SSTable のキー範囲が重複していますが、レベル 1 と レベル 2 では、各レベル内の SSTable のキー範囲が互いに素になっています。ただし、異なるレベル間の SSTable (例: レベル 0 とレベル 1、またはレベル 1 とレベル 2) では、キー範囲が重複する場合があります。
次に、レベルド・コンパクション戦略がこの組織構造をどのように維持するかを見てみましょう。
レベル 0 は特殊なケースであるため、圧縮戦略の説明は 2 つの部分に分かれています。
レベル 0 からレベル 1 圧縮と レベル N からレベル N 1 (N > 0) 圧縮の主な違いは、下位レベル (レベル) での SSTable の選択にあります。 0 またはレベル N)。
マルチ SSTable の圧縮とマージのプロセスを以下に示します。マージ中は、各キーの最新の値のみが保持されます。最新の値に「廃棄」マーカーがある場合、キーは削除されます。実装では、k-way マージ アルゴリズムを使用してこのプロセスを実行します。
圧縮プロセスに関する上記の説明は、高レベルの概要のみを提供していることに注意することが重要です。実際の実装では多くの詳細に対処する必要があります。
たとえば、LevelDB では、圧縮中にレベル N 1 の新しい SSTable を構築するときに、新しい SSTable がレベル N 2 の 10 個を超える SSTable と重複する場合、プロセスは別の SSTable の構築に切り替わります。これにより、1 回の圧縮に含まれるデータ サイズが制限されます。
上記の LSM-Tree の概要に基づいて、LSM-Tree の基本とその実装に関するいくつかのアイデアを理解できたと思います。次に、LSM-Tree に基づいたストレージ エンジンを最初から構築します。以下では、コアコードのみを紹介します。完全なコードについては、https://github.com/B1NARY-GR0UP/originium を参照してください。
LSM ツリーの実装を次のコア コンポーネントに分割し、それらを 1 つずつ実装します。
データ書き込みの紹介の過程で、LSM ツリーが最初にデータをメモリ内の順序付けされたデータ構造に書き込むと述べました。一般的な順序付きデータ構造とその操作の時間計算量は次のとおりです。
| Data Structure | Insert | Delete | Search | Traverse |
|---|---|---|---|---|
| Skip List | O(logn) | O(logn) | O(logn) | O(n) |
| AVL Tree | O(logn) | O(logn) | O(logn) | O(n) |
| Red-Black Tree | O(logn) | O(logn) | O(logn) | O(n) |
スキップ リストを選択した主な理由は 2 つあります。1 つは実装と保守が簡単 (KISS 原則)、もう 1 つは基礎となるリンク リスト構造によりシーケンシャル トラバーサルが容易で、メモリ内データをディスクに永続化することが容易です。
スキップ リストの完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go で入手できます。
スキップ リストは、基本リンク リストとその上に構築された複数レベルのインデックスで構成されます。大規模なデータセットの場合、インデックス レイヤーにより検索パスが大幅に短縮されます。
私たちの実装では、スキップ リストのコア構造は次のように定義されています。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
スキップ リストに格納される要素の構造は次のように定義されます。
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
types.Entry は、キー、値、削除用の廃棄フラグを含む、ストレージ エンジン内のキーと値のペアを表します。
next: 各レベルの次の要素へのポインターが含まれます。
この構造は抽象的に見えるかもしれないので、例で説明してみましょう:
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
この 3 レベルのスキップ リストでは、ヘッド ノードの次のポインターは各レベルの最初のノードを参照します。要素 3 と 6 には、各レベルの次の要素が格納されます。
たとえば、レベル 2 で要素 19 の次のノードを見つけたい場合は、e19.next[2-1] を使用します。
func (s *SkipList) Set(entry types.Entry)
LSM ツリーは削除を実行するためにトゥームストーンを使用するため、スキップ リストの実装に Delete メソッドは必要ありません。要素を削除するには、エントリの Tombstone を true に設定するだけです。したがって、Set メソッドは、新しいキーと値のペアの挿入、既存のキーと値のペアの更新、要素の削除を処理します。
Set メソッドの実装を見てみましょう。各レベルのノードを最上位からたどることで、設定するキーより小さい最後の要素が更新スライスに保存されます。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
この走査の終わりに、curr は最下位レベルのリンク リストに設定されるキーより小さい最後の要素を指します。したがって、curr の次の要素が設定したいキーと等しいかどうかを確認するだけで済みます。一致する場合、要素はすでに挿入されています。既存の要素を更新して戻ります。
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
要素が見つからない場合は、新しい要素として挿入されます。 randomLevel を使用して、この要素のインデックス レベルを計算します。スキップ リストの現在のレベル数を超える場合は、ヘッド ノードを更新スライスに追加し、s.level を新しいレベル数に更新します。
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
次に、挿入する要素を構築します。各レベルの次のポインターが更新されて、挿入が完了します。
func (s *SkipList) Set(entry types.Entry)
スキップ リストは、複数のインデックス層に依存して高速な検索操作を実行できます。実装内のネストされた for ループは、インデックスベースの検索操作を表します。最終的に対応する要素が最下位のリンク リストで見つかった場合は、それが返されます。
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
スキップ リストを選択した理由の 1 つは、その便利な順次走査です。これは、最下位レベルのリンク リストを走査するだけで可能になります。
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
WAL の完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go にあります。
前述したように、WAL (Write-Ahead Logging) の目的は、データベースのクラッシュによる Memtable でのデータ損失を防ぐことです。したがって、WAL は Memtable 上の操作を記録し、データベースの再起動時に WAL ファイルから Memtable を復元する必要があります。
WAL のコア構造は次のとおりです。ここで、fd は WAL ファイルのファイル記述子を保存します。
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Memtable で操作を記録する必要があるため、これには基本的に各操作 (Set、Delete) をエントリとして WAL に書き込むことが含まれます。 Write メソッドの定義は次のとおりです:
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
これらのエントリをファイルに書き込むときは、WAL ファイル形式を標準化する必要があります。ここで使用する形式は長さデータです。まず、エントリをシリアル化し、次にシリアル化されたデータの長さを計算し、最後に長さとシリアル化されたデータを WAL ファイルに順番に書き込みます。
コアコードは次のとおりです:
func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
curr := s.head
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < key {
curr = curr.next[i]
}
}
curr = curr.next[0]
if curr != nil && curr.Key == key {
return types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
}, true
}
return types.Entry{}, false
}
WAL ファイル形式 長さデータ を使用しているため、読み取り時には、まず 8 バイト (int64) を読み取り、データの長さを取得し、次にこの長さに基づいてデータを読み取り、デシリアライズします。エントリを取得します。
コアコードは次のとおりです:
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Memtable の完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go にあります。
Memtable は、クライアント操作をスキップ リストに書き込み、WAL に記録する役割を果たします。データベースの起動時に WAL からデータを復元することもできます。
Memtable のコア構造は次のとおりです。これには、2 つの主要コンポーネント Skiplist と wal が含まれます。
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Set 操作を実行する場合、スキップ リストと WAL の両方を同時に更新する必要があります。
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
値を取得するには、単純にスキップ リストの Get オペレーションの結果を返します。
func (s *SkipList) Set(entry types.Entry)
WAL ファイルから Memtable を復元するには、まず WAL ファイルを読み取り、次に WAL ファイルからエントリ レコードを Memtable に順次適用し、最後に復元された WAL ファイルを削除します。
WAL ファイルのリストを取得します:
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
WAL を読み取り、Memtable を回復します:
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
前回の紹介では、「SSTable (Sorted String Table) は、順序付けされた一連のキーと値のペアを維持するデータ ストレージ形式である」とだけ説明しました。ここでは、SSTableの構造についてより詳しく説明します。
LevelDB では、SSTable は異なる目的を持つ複数のブロックで構成されます。概略図を以下に示します。
インデックス情報は本質的に BlockHandle と呼ばれるポインター構造であり、対応するブロックを見つけるために使用されるオフセットとサイズの 2 つの属性が含まれます。
SSTable の実装では、LevelDB SSTable 構造を簡素化しました。概略図を以下に示します。
SSTable の完全な実装は、https://github.com/B1NARY-GR0UP/originium/tree/main/sstable にあります。
データ ブロックの構造は次のように定義され、順序付けられた一連のエントリが格納されます。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
データ ブロックに 3 つの主要なメソッドを実装しました。
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
プレフィックス圧縮を使用してキーと値のシーケンスをエンコードします。バッファーには、共通プレフィックスの長さ、サフィックスの長さ、サフィックス自体、値の長さ、値、および「廃棄」マーカーを順番に書き込みます。
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
最後に、s2 を使用してデータを圧縮します。
S2 は、Snappy 圧縮アルゴリズムの高性能拡張です。
func (s *SkipList) Set(entry types.Entry)
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
デコード中は、プロセスが単に逆に行われます。完全なキーと値のペアは、プレフィックスとサフィックスを使用して再構築されます。
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
インデックスブロックの構造は以下のように定義されます。各データ ブロックの最初と最後のキーと、対応するデータ ブロックの BlockHandle が保存されます。
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
同様に、インデックス ブロックは、エンコード、デコード、および検索の 3 つの主要なメソッドを実装します。 Encode メソッドと Decode メソッドの実装の考え方は基本的に同じであるため、Search メソッドに焦点を当てます。
データ ブロックの検索メソッドは、単一のデータ ブロックに格納されている順序付けされたキーと値のシーケンス内で特定のキーと値のペアを見つけるように設計されています。対照的に、インデックス ブロックの Search メソッドは、SSTable 全体内で指定されたキーを含むデータ ブロックを見つけるために使用されます。
func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
curr := s.head
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < key {
curr = curr.next[i]
}
}
curr = curr.next[0]
if curr != nil && curr.Key == key {
return types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
}, true
}
return types.Entry{}, false
}
func (s *SkipList) All() []types.Entry {
var all []types.Entry
for curr := s.head.next[0]; curr != nil; curr = curr.next[0] {
all = append(all, types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
})
}
return all
}
これら 2 つのブロックの実装は非常に簡単で、両方とも Encode メソッドと Decode メソッドのみが必要です。
SSTable にすべてのブロックを導入した後、SSTable を構築するには、キーと値のペアに基づいて各ブロックを段階的に構築するだけです。最後に、メモリ内のインデックスとエンコードされた SSTable が返されます。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
K-Way Merge の完全な実装は、https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway で入手できます。
概念的なセクションでは、複数の SSTable を圧縮およびマージするプロセスを図で説明します。このプロセスは、k-way merge アルゴリズムを使用して実行されます。
k ウェイ マージ アルゴリズムは、k 個のソートされたシーケンスを単一のソートされたシーケンスにマージする方法であり、時間計算量は O(knlogk) です。
このアルゴリズムの 1 つの実装では、min-heap を補助構造として使用します。
標準ライブラリはコンテナ/ヒープでヒープ実装を提供します。 heap.Interface を実装することで、最小ヒープを構築できます。
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
func (s *SkipList) Set(entry types.Entry)
Merge メソッドの関数定義:
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
k-way マージ アルゴリズム プロセスに従います。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
最後に、マップを走査して結果キューに要素を追加し、「廃棄」としてマークされたキーと値のペアをすべて削除します。マップには順序がないため、結果キューは返される前に並べ替える必要があります。
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
ブルーム フィルターの完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go にあります。
ブルーム フィルターは、要素がセットのメンバーであるかどうかを効率的にチェックするデータ構造です。
挿入操作とクエリ操作の両方の時間計算量は O(k) です。k はハッシュ関数の数です。 偽陽性が発生する可能性があります (ブルーム フィルターは、要素がセット内に存在すると予測しますが、実際には存在しません)。しかし、偽陰性は発生しません (ブルーム フィルターは、要素がセット内に存在しないと予測します)セットではありますが、実際にはそうなります)。
真陽性 (TP): システムはイベントを「陽性」と予測し、実際に陽性です。
偽陽性 (FP): システムはイベントを「陽性」であると予測しますが、実際は陰性です。
真陰性 (TN): システムはイベントを「陰性」と予測し、実際に陰性です。
偽陰性 (FN): システムはイベントを「陰性」と予測しますが、実際には陽性です。
ブルーム フィルターのコア構造には、ビット配列 (uint8 を使用するように最適化可能) と複数のハッシュ関数が含まれます。
func (s *SkipList) Set(entry types.Entry)
ブルーム フィルター インスタンスを作成するメソッドは、n (予想される要素数) と p (希望する誤検知率) の 2 つのパラメーターを受け入れます。
まず、パラメータが検証されます。次に、ビット配列のサイズ (m) とハッシュ関数の数 (k) が特定の式を使用して計算されます。最後に、ビット配列とハッシュ関数が m と k に基づいて初期化されます。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
要素を追加するとき、すべてのハッシュ関数を使用してキーのハッシュ値が計算されます。これらの値はビット配列内のインデックスにマッピングされ、対応する位置が true に設定されます。
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
キーがセット内にあるかどうかを確認するために、ハッシュ関数はハッシュ値を計算し、それらをビット配列のインデックスにマップします。これらの位置のいずれかが true でない場合、その要素はセットに含まれず、false が返されます。
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Leveled Compaction の完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/level.go にあります。
K-Way マージやブルーム フィルターなどのコンポーネントを実装した後、実装の最後の部分、つまり LSM-Tree ストレージ エンジンで最も重要な SSTable 圧縮プロセスを完了できます。この実装は、「データ コンパクション」セクションで説明されているレベルド コンパクション戦略に従います。
レベル圧縮戦略では、SSTable は複数のレベル (レベル 0 ～ レベル N) に編成されます。この情報を保存し、さまざまなレベルにわたって SSTable を管理するための構造が必要です。
そこで、levelManager と呼ばれる構造を実装しました。 []*list.List を使用して各レベルの SSTable 情報を保存します。スライスのインデックスはレベルに対応します。スライス内の各要素は list.List であり、特定のレベルのすべての SSTable に関する情報を保持する二重リンク リストです。
func (s *SkipList) Set(entry types.Entry)
compactLN メソッドは、レベル N からレベル N 1 (N > 0) までの圧縮を担当します。 LN から最も古い SSTable と、この SSTable と重複するキー範囲を持つ LN 1 のすべての SSTable を選択します。
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
選択した SSTable は、古いものから新しいものの順に処理されます。データ ブロックのキーと値のペアは 2 次元スライスに追加され、K-Way マージ アルゴリズムを使用してマージされます。
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
マージされたキーと値のペアを使用して、新しいブルーム フィルターと SSTable を構築します。新しい SSTable に関する関連情報は、レベル N 1 の最後に追加されます。
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
最後に、古い SSTable が削除され、新しく構築された SSTable がディスクに書き込まれます。
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
compactL0 メソッドは、レベル 0 からレベル 1 への圧縮を処理します。 CompactLN とは異なり、L0 から 1 つの SSTable だけでなく、L0 内の重複するすべての SSTable も選択します。プロセスの残りの部分は、compactLN と同じです。
検索メソッドは、すべての SSTable にわたって対応するキーと値のペアを見つけます。 L0 から開始し、LN まで各レベルを反復します。ブルーム フィルターと SSTable の順序付けされた構造を活用することで、目的のキーと値のペアを含まない SSTable を効率的にスキップできます。
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
これにより、LSM ツリーベースのストレージ エンジンのすべてのコア コンポーネントが実装されました。 LSM-Tree の概要で説明したようにこれらのコンポーネントを組み立てることにより、データベース インターフェイスを完成させることができます。
完全なコード: https://github.com/B1NARY-GR0UP/originium/blob/main/db.go
ドキュメント: https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage
私たちは LSM-Tree を理解し、そのコアコンポーネントとクライアントリクエストを処理するプロセスに慣れることから始めました。最終的に、私たちは独自の LSM-Tree ストレージ エンジンをゼロから構築しました。
もちろん、この実装は単なるプロトタイプです。実稼働グレードのストレージ エンジンでは、さらに多くの詳細を考慮する必要があります。 ORIGINIUM は今後も最適化と改善を続けていきます。この記事と ORIGINIUM が LSM-Tree への理解をさらに深めるのに役立つことを願っています。
これで、この記事で説明した内容はすべて終了です。エラーや質問がある場合は、プライベートメッセージでご連絡いただくか、コメントを残してください。ありがとうございます!
以上がLSM ツリー ストレージ エンジンを最初から構築するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
