【LSM-tree】SSTable

SSTable（Sorted String Table）は、LSM-Treeでデータを永続的に保存するためのファイルフォーマットです。SSTableは、ディスクに効率的にデータを格納するためにソートされたキーとバリューのペアを格納します。主に以下の構造を持っています。

1. 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"
)

// 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
}