SSTable(Sorted String Table)は、LSM-Treeでデータを永続的に保存するためのファイルフォーマットです。SSTableは、ディスクに効率的にデータを格納するためにソートされたキーとバリューのペアを格納します。主に以下の構造を持っています。
- SSTableの基本構造
SSTableファイルは、通常以下の要素から構成されています:
- データブロック(Data Block)
- メタデータ(Metadata)
- インデックス(Index)
- フィルタ(Filter)
- チェックサム(Checksum)(オプション)
これらの要素が一つのSSTableファイルに格納され、効率的に検索と書き込みが行えるようになっています。
Goで実装
SSTableは、主にKVSのデータ構造です。LSM-Treeや多くのNoSQLデータベースで使用される永続的なデータフォーマットとして、キーとバリューのペアをソートされた形式で格納することに特徴があるらしいです。Goでのサンプル実装。
package main
import (
"fmt"
"os"
"log"
"time"
"bytes"
"encoding/gob"
)
type MemTable struct {
data map[string]string
}
func NewMemTable() *MemTable {
return &MemTable{data: make(map[string]string)}
}
func (mt *MemTable) Put(key, value string) {
mt.data[key] = value
}
func (mt *MemTable) Get(key string) (string, bool) {
value, exists := mt.data[key]
return value, exists
}
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
}
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
}
type LSMTree struct {
memTable *MemTable
sstableFile string
}
func NewLSMTree(sstableFile string) *LSMTree {
return &LSMTree{
memTable: NewMemTable(),
sstableFile: sstableFile,
}
}
func (lsm *LSMTree) Put(key, value string) {
lsm.memTable.Put(key, value)
if len(lsm.memTable.data) > 10 {
err := lsm.memTable.FlushToDisk(lsm.sstableFile)
if err != nil {
log.Fatal(err)
}
lsm.memTable = NewMemTable()
}
}
func (lsm *LSMTree) Get(key string) (string, bool) {
if value, found := lsm.memTable.Get(key); found {
return value, true
}
data, err := ReadSSTable(lsm.sstableFile)
if err != nil {
log.Fatal(err)
}
if value, found := data[key]; found {
return value, true
}
return "", false
}
func main() {
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")
}
}
コンパクション
func Compaction(sstableFiles []string, newSSTableFile string) error {
mergedData := make(map[string]string)
for _, fileName := range sstableFiles {
data, err := ReadSSTable(fileName)
if err != nil {
return err
}
for key, value := range data {
mergedData[key] = value
}
}
var buffer bytes.Buffer
enc := gob.NewEncoder(&buffer)
if err := enc.Encode(mergedData); err != nil {
return err
}
file, err := os.Create(newSSTableFile)
if err != nil {
return err
}
defer file.Close()
_, err = file.Write(buffer.Bytes())
return err
}