Skip to content

Latest commit

 

History

History
45 lines (32 loc) · 1.96 KB

README.md

File metadata and controls

45 lines (32 loc) · 1.96 KB
Raw

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