NoSQL Engine Internals: LSM Trees & SSTables

// Python 3.10+ LSM-Tree Core Engine with WAL and MemTable
import os, bisect

class LSMStorageEngine:
    def __init__(self, wal_path: str = "wal.log", max_memtable_size: int = 1000):
        self.wal_path = wal_path
        self.max_size = max_memtable_size
        self.memtable = {}    # In-memory sorted buffer (SkipList)
        self.sstables = []    # List of immutable on-disk SSTables
        self.wal = open(wal_path, "a", encoding="utf-8")

    def put(self, key: str, value: str):
        # 1. Append sequentially to Write-Ahead Log on disk for durability
        self.wal.write(f"{key}:{value}\n")
        self.wal.flush()

        # 2. Insert into sorted in-memory MemTable
        self.memtable[key] = value

        # 3. If MemTable exceeds capacity, flush to immutable SSTable on disk
        if len(self.memtable) >= self.max_size:
            self.flush_memtable()

    def get(self, key: str):
        # 1. Search Active MemTable in RAM (O(1) / O(log N))
        if key in self.memtable:
            val = self.memtable[key]
            return None if val == "__TOMBSTONE__" else val

        # 2. Search SSTables from newest to oldest
        for sstable in reversed(self.sstables):
            if sstable.bloom_filter.contains(key):
                val = sstable.search(key)
                if val is not None:
                    return None if val == "__TOMBSTONE__" else val
        return None

// C++17/20 LSM MemTable using std::map
#include <iostream>
#include <map>
#include <string>
#include <fstream>

class LSMTree {
    std::map<std::string, std::string> memtable;
    std::ofstream wal;
public:
    LSMTree() : wal("wal.log", std::ios::app) {}

    void put(const std::string& key, const std::string& val) {
        wal << key << ":" << val << "\n";
        wal.flush();
        memtable[key] = val;
    }

    std::string get(const std::string& key) {
        auto it = memtable.find(key);
        if (it != memtable.end()) return it->second;
        // Search on-disk SSTables with Bloom Filter check
        return "";
    }
};

// Java 17+ ConcurrentSkipListMap MemTable
import java.io.*;
import java.util.concurrent.ConcurrentSkipListMap;

public class LSMStorageEngine {
    private final ConcurrentSkipListMap<String, String> memtable = new ConcurrentSkipListMap<>();
    private final BufferedWriter walWriter;

    public LSMStorageEngine() throws IOException {
        walWriter = new BufferedWriter(new FileWriter("wal.log", true));
    }

    public void put(String key, String value) throws IOException {
        walWriter.write(key + ":" + value + "\n");
        walWriter.flush();
        memtable.put(key, value);
    }
}

// Go 1.20+ LSM Tree MemTable
package main

import (
    "os"
    "sync"
)

type LSMEngine struct {
    mu       sync.RWMutex
    memtable map[string]string
    wal      *os.File
}

func (e *LSMEngine) Put(key, val string) error {
    e.mu.Lock()
    defer e.mu.Unlock()

    // Append to WAL
    e.wal.WriteString(key + ":" + val + "\n")
    e.memtable[key] = val
    return nil
}

// TypeScript / Node.js LSM Tree Engine
import * as fs from 'fs';

export class LSMTreeEngine {
    private memtable: Map<string, string> = new Map();
    private walStream: fs.WriteStream;

    constructor() {
        this.walStream = fs.createWriteStream('wal.log', { flags: 'a' });
    }

    put(key: string, value: string): void {
        this.walStream.write(`${key}:${value}\n`);
        this.memtable.set(key, value);
    }
}