LevelKV*: Checkpoint Based Persistent Key Value Store for Key-Value SSD

Introduction

• recently, another big change has been introduced to storage landscape: Key-Value SSDs.
• Key-Value SSD aims to store key value pairs at a hardware level
• just replacing block SSD with KV SSD underneath LSM-tree structured key-value store will not work
• LevelKV* is a Key-Value-conscious persistent key-value store with LevelDB as interface
• LevelKV* supports range query and crash consistency

LevelDB

• widely used key-value store based on LSM-trees
• supports range queries, snapshots, etc.
• on-disk log file, in-memory memtable, immutable memtable, seven levels of on-disk Sorted String Table (SSTable) files
• excessive reads and writes that are unnecessary has been one of the major drawbacks of LSM-tree structured key-value store

Design

• in-memory B+-Tree, OpQueue (Operation Queue) and on-SSD CheckNodes (Checkpoint Nodes)
• operation in OpQueue is first transformed into an CheckNode then flushed to KV SSD

Operation

• (1) Insertion or deletion operation in OpQueue or 2) Slice (data type in KV SSD interface that is similar to type std::string in c++) type keys that were sorted in the B⁺-Tree have to be transformed into a single key-value pair
• range query: range of queries have to be searched in the B⁺-Tree to get all the indexes; then values are retrieved from KV SSD device by using the internal get function

Crash Consistency

• log insert, delete operation in the background thread
• when the system crashes and B⁺-Tree and OpQueue structure are lost in memory, LevelKV* recovers the structure by first calling the last indexed CheckNode that is dividable by NUM
• log insert, delete operation in the background thread

Benchmarks

• experiments are run on a testing machine with two Intel(R) Xeon(R) CPU @ 2.10GHz (24 cores per CPU processors and 64-GB of memory)
• operating system is 64-bit Ubuntu 18.04.03 LTS and the file system used is ext4
• storage device used is 3.84-TB SAMSUNG PM983 SSD, which has both block interface and KV interface

build emulator (environment without actual device)

	# build kvapi library
	export PRJ_HOME=$(pwd)
	export KVSSD_HOME=$PRJ_HOME/KVSSD-1.2.0/PDK/core
	$KVSSD_HOME/tools/install_deps.sh # install kvapi dependency
	mkdir $KVSSD_HOME/build
	cd $KVSSD_HOME/build
	cmake -DWITH_EMU=ON $KVSSD_HOME
	make -j4

	# copy libkvapi.so
	mkdir $PRJ_HOME/libs
	cp $KVSSD_HOME/build/libkvapi.so $PRJ_HOME/libs/

build levelkv library

	make

build test case

	export PRJ_HOME=$(pwd)
	cd $PRJ_HOME/test
	make lsm # lsm index
	make btree # btree index

run

Configure DB options by environment: (please refer to include/levelkv/options.h)

	export INDEX_TYPE=LSM # LSM, BTREE, BASE
	export PREFETCH_ENA=TRUE # TRUE, FALSE
	export PREFETCH_PREFETCH_DEPTH=16 # any integer
	export RANGE_FILTER_ENA=TRUE # TRUE, FALSE

Note: please keep the kvssd_emul.conf file in the executable file directory. This configuration file override the default configuration by disabling the iops model (run faster).

	export PRJ_HOME=$(pwd)
	cd $PRJ_HOME/test
	export LD_LIBRARY_PATH=$PRJ_HOME/libs/
	./db_test