HeapKV: Enabling Efficient Garbage Collection for KV-Separated LSM Stores on Modern SSDs

Overview

This repository contains a naive prototype of HeapKV that written in C++ based on RocksDB v8.11.3 . The core implementation of HeapKV is under db/heap directory.

Build

Requirement

• Linux Kernal 6.x (recommended)
• g++ 13.0+
• CMake 3.10.0+
• liburing 2.6+
• filesystem that support reflink feature (e.g. XFS, Btrfs, ZFS...)

Clone repository

$ git clone https://github.com/PDS-Lab/HeapKV.git

Build

# use CC=gcc-13 CXX=g++-13 if the default compiler of your system is not g++ 13
# ninja librocksdb.so if you need shared lib

$ mkdir build && cd build
$ cmake -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DCMAKE_BUILD_TYPE=Release .. -GNinja
$ ninja librocksdb.a

Usage

target_include_directories(${target} ${PATH_TO_HEAPKV}/include)
target_link_libraries(${target} ${PATH_TO_HEAPKV}/build/librocksdb.a uring)

HeapKV Specific Configuration

enable_heapkv: whether use heapkv key-value separation

min_heap_value_size: value ≥ this setting while be separated during flush operation

heap_extent_relocate_threshold: the GC ratio of HeapKV. (i.e. 0.3 means GC will be triggered if 30% of space are garbage or unavailable fragmentation)

enable_fast_path_update: whether update fast path info during compaction

heap_value_cache: the cache object to use for value and value index in extent file. It is recommended to create a new cache instance instead of using block cache of rocksdb.

Test

Benchmarking with YCSB

To benchmark the performance of HeapKV prototype using YCSB, you can link against HeapKV in YCSB-cpp build configuration (as described in Usage). On top of the base RocksDB setup, apply HeapKV specific configurations on your target column family (e.g., cf in the example below):

cf.options.enable_heapkv = true;
cf.options.min_heap_value_size = min_heap_value_size;
cf.options.heap_value_cache = heap_value_cache;
cf.options.heap_extent_relocate_threshold = heap_extent_relocate_threshold;

Run Verification Tests

cd heapkv_tests

# `snapshot_test` verifies that HeapKV correctly maintains data consistency across snapshots during read/write operations
./run_snapshot_test.sh

# `crash_test` verifies that HeapKV can correctly recover data after a simulated process crash, including standard recovery and handling of overwritten keys
./run_crash_test.sh