Tiny-LSM

Tiny-LSM is an educational project built by Vanilla-Beauty to learn about storage engines and database internals. It implements a simple key-value database from scratch using an LSM-tree (Log-Structured Merge-tree) as the storage engine. The project uses xmake as the build system and is inspired by mini-lsm, tinykv, and leveldb.

The project is partly compatible with the Redis Resp protocol, allowing it to be used as a Redis backend to replace redis-server for learning and experimentation purposes.

📦 Build Configuration

The project uses xmake as the build system. Below is the xmake configuration for building the project and running tests:

1. Compile the project

xmake

2. Run the example program or test

xmake run example
xmake run test_lsm

3. Install the shared library

xmake install --root lsm_shared

🛠️ Usage

Use as a library

Here is a simple example demonstrating how to use the LSM Tree for basic key-value operations:

#include "../include/lsm/engine.h"
#include "../include/lsm/level_iterator.h"
#include <iostream>
#include <string>

using namespace ::tiny_lsm;

int main() {
  // create lsm instance, data_dir is the directory to store data
  LSM lsm("example_data");

  // put data
  lsm.put("key1", "value1");
  lsm.put("key2", "value2");
  lsm.put("key3", "value3");

  // Query data
  auto value1 = lsm.get("key1");
  if (value1.has_value()) {
    std::cout << "key1: " << value1.value() << std::endl;
  } else {
    std::cout << "key1 not found" << std::endl;
  }

  // Update data
  lsm.put("key1", "new_value1");
  auto new_value1 = lsm.get("key1");
  if (new_value1.has_value()) {
    std::cout << "key1: " << new_value1.value() << std::endl;
  } else {
    std::cout << "key1 not found" << std::endl;
  }

  // delete data
  lsm.remove("key2");
  auto value2 = lsm.get("key2");
  if (value2.has_value()) {
    std::cout << "key2: " << value2.value() << std::endl;
  } else {
    std::cout << "key2 not found" << std::endl;
  }

  // iterator
  std::cout << "All key-value pairs:" << std::endl;
  // begin(id): id means transaction id, 0 means disable mvcc
  for (auto it = lsm.begin(0); it != lsm.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
  }

  // transaction
  auto tranc_hanlder = lsm.begin_tran(IsolationLevel::REPEATABLE_READ);
  tranc_hanlder->put("xxx", "yyy");
  tranc_hanlder->put("yyy", "xxx");
  tranc_hanlder->commit();

  auto res = lsm.get("xxx");
  std::cout << "xxx: " << res.value() << std::endl;

  lsm.clear();

  return 0;
}

Use to replace redis-server

⚠️ Now the project only partly compatible with the Redis Resp protocol, you can check TODO for the supported Redis commands.

xmake run server

Then you can use redis-cli to connect to the server:

The project is under development, and the current version is not stable.

📈 Benchmark

We use the official tool redis-benchmark to test the performance of the wrapper redis server. The QPS of commonly used commands are relatively high, considering its IO between memory and disk.

🔍 The testing environment is: macOS, 64GB RAM, Apple M4 Max.

(base) ➜  ❯ redis-benchmark -h 127.0.0.1 -p 6379 -c 100 -n 100000 -q -t SET,GET,INCR,SADD,HSET,ZADD
WARNING: Could not fetch server CONFIG
SET: 86206.90 requests per second, p50=0.575 msec
GET: 89285.71 requests per second, p50=0.575 msec
INCR: 89686.10 requests per second, p50=0.567 msec
SADD: 88888.89 requests per second, p50=0.575 msec
HSET: 88417.33 requests per second, p50=0.575 msec
ZADD: 88652.48 requests per second, p50=0.575 msec

🔍 Besides, the QPS of lpush/rpush is so slow that its design needs to be optimized.

The performance of the wrapper redis server is not very good, but it is still fast enough for most use cases. Howerver, the redis server is built based on the LSM Tree KV engine, so it consists of some redundancy locks. If you use the LSM Tree KV engine directly, you can get much better performance. The reason why we use redis-benchmark to test the compatible redis api but not the actual KV engine API is that writing a sophisticated testing tool costs much time so we choose to use the existed redis-benchmark.

✅ Features && TODO

• SkipList
  • get/put/remove
  • iterator
  • Range Query
• MemTable
  • Iterator
  • Range Query
  • flush to sst
• SST
  • Encode/Decode
  • Iterator
  • Query
  • Range Query
  • Compact
• Wal
  • Sync Wal
  • Async Wal
  • Recover
• Transaction
  • MVCC
  • Isolation Level
    • Read Uncommitted
    • Read Committed
    • Repeatable Read (Default)
    • Serializable
• Config
  • Toml Config
• Redis
  • Fundamental KV Operations
    • set/get
    • ttl/expire
  • Hash Operations
    • hset/hget/hdel
    • hkeys
  • List Operations
    • lpush/rpush/lpop/rpop
    • llen
    • lrange
  • ZSet
    • ZADD/ZREM/ZINCRBY
    • ZCARD
    • ZRANGE
    • ZSCORE
    • ZRANK
  • Set
    • SADD/SREM
    • SMEMBERS/SISMEMBER
    • SCARD
  • IO Operations
    • FLUSHALL
    • SAVE
  • SDK
    • Python

🔍 Only commonly used redis commands are supported. The other implementations can refer to src/redis_wrapper/redis_wrapper.cpp. If you need more commands, please submit a pull request.

Redis Resp

Currently, the project only supports a subset of the Redis Resp protocol. The supported commands are listed above. You can add more commands by following the existing implementations in src/redis_wrapper/redis_wrapper.cpp.

📜 License

This project is licensed under the MIT License.