Key-Value Store (LSM-Tree Based)

Project Description

This repository contains a simple key-value database implemented in Go, built around a Log-Structured Merge-Tree (LSM tree) design. It provides persistent storage of key-value pairs with efficient write and read operations, using:

• an in-memory write buffer (memtable),
• on-disk sorted files (SSTables),
• and advanced supporting structures for performance like Bloom filters, Count-Min Sketch, and HyperLogLog.

Features

• Persistent Storage via LSM Tree
• Write-Ahead Log (WAL) for durability
• In-memory Memtable (Skip List)
• Sorted String Tables (SSTables) on disk
• Compaction with obsolete/tombstone cleanup
• LRU Cache for recently accessed keys
• Bloom Filters for fast negative lookups
• Count-Min Sketch for approximate frequency counting
• HyperLogLog for cardinality estimation
• Merkle Tree for data integrity verification
• Token Bucket Rate Limiting for throughput control

Algorithms & Data Structures

• LSM Tree: Multi-level log-structured tree of sorted files with compaction and tombstone handling.
• Skip List: In-memory structure for the memtable with log-time access.
• Write-Ahead Log: Append-only log to ensure durability before in-memory insertions.
• SSTables: Immutable sorted tables stored on disk, periodically merged.
• Compaction: Background merging of SSTables to reduce redundancy and maintain read efficiency.
• Bloom Filter: Per-SSTable filters that prevent unnecessary reads (false-negative resistant).
• LRU Cache: Stores most recently accessed key-value pairs for faster reads.
• Count-Min Sketch: Probabilistic structure for identifying frequently accessed keys.
• HyperLogLog: Space-efficient estimator for number of unique keys.
• Merkle Tree: Cryptographic hash tree for validating data consistency.
• Token Bucket: Rate-limiting algorithm to control write and compaction rates.

Project Structure

• Structures/ – All core data structures (skip list, bloom filter, sketches, etc.)
• Configuration/ – YAML-based runtime configuration system
• main.go – Entry point
• utils/ – Serialization, hashing, compression utilities

Running the Project

1. Install dependencies

Make sure you have Go installed (go version).

2. Build the binary

cd key-value-store/ProjekatGO
go build .

3. Run the project

go run main.go

By default, configuration is loaded from Configuration/configuration.yaml.

4. Adjust settings (optional)

Modify configuration.yaml to set:

• WAL size
• Memtable flush threshold
• Bloom filter false positive rate
• Cache size
• Token refill rates
• Number of LSM levels and SSTables per level

5. Data Output

• WAL and SSTable files are written to disk in the working directory.
• Upon restart, the WAL will be replayed into a fresh memtable.

Notes

This project showcases foundational techniques used in modern databases like RocksDB, LevelDB, and Cassandra, but built from scratch for educational clarity.