Skip to content

lightweight LSM tree based storage engine implementation using WAL, memtable and sstable with basic operations

Notifications You must be signed in to change notification settings

pradipmudi/lightweight-lsm-storage-engine

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LSM tree Implementation

This Java project provides a basic implementation of an LSM tree-based storage system. SSTables (Sorted String Tables) are critical data structures used in distributed databases and storage systems for efficient storage and retrieval of key-value pairs.

Features

  • Key-Value Storage: Organizes data as key-value pairs, sorted lexicographically by keys.
  • Jigsaw Pattern: Implements a memtable for sequential and append-only write operations, following the Jigsaw pattern.
  • Immutable Structure: Ensures immutability of data once written to SSTables, simplifying concurrency control.
  • Log-Structured Writes: Utilizes memtables for buffering write operations before flushing to SSTable files.
  • Merge and Compaction: Includes methods for merging and compacting SSTables to optimize storage and performance.

Usage

To use the SSTable storage system:

  1. Initialize Storage: Create an instance of SSTableStorage with a specified memtable threshold.
  2. Write Data: Use the write() method to add key-value pairs to the storage system.
  3. Read Data: Utilize the read() method to retrieve values associated with keys.
  4. Merge SSTables: Call the merge() method periodically to merge existing SSTables.
  5. Compact SSTables: Use the compact() method to compact SSTables for improved storage efficiency.

Example

// Initialize storage with memtable threshold
SSTableStorage storage = new SSTableStorage(100);

// Write data
storage.write("key1", "value1");
storage.write("key2", "value2");

// Read data
String value = storage.read("key1");
System.out.println("Value for key 'key1': " + value);

// Merge SSTables
storage.merge();

// Compact SSTables
storage.compact();

Blog

I also discuss about SSTable in details in my blog. Please feel free to explore the blog here: https://pradipmudi.substack.com/p/write-heavy-systems-sstables-sorted

About

lightweight LSM tree based storage engine implementation using WAL, memtable and sstable with basic operations

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages