SSTable（Sorted String Table）は、LSM-Treeでデータを永続的に保存するためのファイルフォーマットです。SSTableは、ディスクに効率的にデータを格納するためにソートされたキーとバリューのペアを格納します。主に以下の構造を持っています。
- SSTableの基本構造
SSTableファイルは、通常以下の要素から構成されています：
これらの要素が一つのSSTableファイルに格納され、効率的に検索と書き込みが行えるようになっています。
Goで実装
SSTableは、主にKVSのデータ構造です。LSM-Treeや多くのNoSQLデータベースで使用される永続的なデータフォーマットとして、キーとバリューのペアをソートされた形式で格納することに特徴があるらしいです。Goでのサンプル実装。
package main import ( "fmt" "os" "log" "time" "bytes" "encoding/gob" ) // MemTableはメモリ内に保持するデータ構造 type MemTable struct { data map[string]string } // 新しいMemTableを作成 func NewMemTable() *MemTable { return &MemTable{data: make(map[string]string)} } // MemTableにデータを追加 func (mt *MemTable) Put(key, value string) { mt.data[key] = value } // MemTableからデータを取得 func (mt *MemTable) Get(key string) (string, bool) { value, exists := mt.data[key] return value, exists } // MemTableの内容をディスクにフラッシュ func (mt *MemTable) FlushToDisk(fileName string) error { var buffer bytes.Buffer enc := gob.NewEncoder(&buffer) if err := enc.Encode(mt.data); err != nil { return err } file, err := os.Create(fileName) if err != nil { return err } defer file.Close() _, err = file.Write(buffer.Bytes()) return err } // SSTableをディスクから読み込む func ReadSSTable(fileName string) (map[string]string, error) { file, err := os.Open(fileName) if err != nil { return nil, err } defer file.Close() var data map[string]string dec := gob.NewDecoder(file) if err := dec.Decode(&data); err != nil { return nil, err } return data, nil } // LSM-Tree構造体 type LSMTree struct { memTable *MemTable sstableFile string } // 新しいLSM-Treeを作成 func NewLSMTree(sstableFile string) *LSMTree { return &LSMTree{ memTable: NewMemTable(), sstableFile: sstableFile, } } // LSM-Treeにデータを挿入 func (lsm *LSMTree) Put(key, value string) { // MemTableに追加 lsm.memTable.Put(key, value) // MemTableが一定サイズに達した場合、SSTableにフラッシュ if len(lsm.memTable.data) > 10 { // 任意の閾値 // フラッシュ処理 err := lsm.memTable.FlushToDisk(lsm.sstableFile) if err != nil { log.Fatal(err) } // 新しいMemTableを作成 lsm.memTable = NewMemTable() } } // LSM-Treeからデータを取得 func (lsm *LSMTree) Get(key string) (string, bool) { // MemTableから検索 if value, found := lsm.memTable.Get(key); found { return value, true } // MemTableに無い場合、SSTableを検索 data, err := ReadSSTable(lsm.sstableFile) if err != nil { log.Fatal(err) } // SSTableから検索 if value, found := data[key]; found { return value, true } return "", false } func main() { // LSM-Treeの作成 lsm := NewLSMTree("sstable.data") // データ挿入 lsm.Put("key1", "value1") lsm.Put("key2", "value2") lsm.Put("key3", "value3") // データ取得 if value, found := lsm.Get("key1"); found { fmt.Println("key1:", value) } else { fmt.Println("key1 not found") } // データ取得 if value, found := lsm.Get("key2"); found { fmt.Println("key2:", value) } else { fmt.Println("key2 not found") } // データ取得 if value, found := lsm.Get("key3"); found { fmt.Println("key3:", value) } else { fmt.Println("key3 not found") } }
コンパクション
// コンパクション（複数のSSTableをマージ） func Compaction(sstableFiles []string, newSSTableFile string) error { mergedData := make(map[string]string) // 各SSTableファイルを読み込んでマージ for _, fileName := range sstableFiles { data, err := ReadSSTable(fileName) if err != nil { return err } // データをマージ（重複を排除） for key, value := range data { mergedData[key] = value } } // マージされたデータを新しいSSTableとしてディスクに書き込む var buffer bytes.Buffer enc := gob.NewEncoder(&buffer) if err := enc.Encode(mergedData); err != nil { return err } // 新しいSSTableファイルを作成して書き込み file, err := os.Create(newSSTableFile) if err != nil { return err } defer file.Close() _, err = file.Write(buffer.Bytes()) return err }
