RNTree is a durable concurrent B+tree using both non-volatile memory (NVM) and hardward transactional memory (HTM). Our paper Building Scable NVM-based B+tree with HTM on ICPP'19 describes its details.
This repo relies on the following libraries:
- intel threading building block (tbb).
- C++ boost library
- Googletest (gtest)
TBB is embeded in this project, while Boost and gtest should be installed in your OS (gtest is not necessary, you can eliminate the dependency on gtest by modifying the CMakeLists.txt, if you do not need the test case.) We build it successfully on Ubuntu-18.04.01, and g++ 7.3.0. Other environments are not evaluated but should work well with little modification.
After installing the dependencies, clone the repo and execute the following command. If you have some troubles with compiling, a hint is to check the "link_directories" and "link_libraries" settings in the CMakeLists.txt.
$ mkdir build
$ cd build
$ cmake ..
$ make -j
$ ./benchmark --help
$ ./benchmark -t 1 -n 1
Note that only FPTree and RNTree support multi-threads. Do not execute NVTree or WB+tree with more than one threads, otherwises segment faults would happen.
There are several important compile flags
NO_CONCURRENT: All code for concurrency control would be removed, like locking, version, etc. This flag is set when testing the performance of single thread.USE_NVM_MALLOC: Persistent memory are allocated from a real persistent memory pool generated by mapping a NVM file. Without this flag, all persistent memory allcations are simulated by normal malloc. Users who can not access to NVM hardwares can disable this flag to simulate NVM with DRAM.CLEAR_NVM_POOL: This flag will clear the data on the NVM when booting up. This flag can be used when users want to evaluate performance round and round and do not care the recoverability.
For simiplicity, we set these flags by setting CMAKE_CXX_FLAGS in CMakeLists.txt. Thus, if you compile successfully, but do not get expected results, please check whether flags have been set correctly.
We suppose there exists a NVM-aware file system supporting direct access (DAX). A NVM file is mapped into a static virtual address range beginning at 0x50000000, which is supposed as persistent memory. The path of the NVM file and the pool size are hard coded in nvm_mgr.h. More details can be found in this file too.
For performance, we allocate NVM in the granularity of pages (4K). A thread local allocator gets chunks from the NVM manager and then divide the chunk into multiple leaf nodes. The first page in the file is reserved as NVM metadata, recording variables like how many pages has been allocated. For simplicity, we do not handle the garbage collection and memory leak problems.
We only implement the recoverability of RNTree yet. Here is a simple test:
# insert key values
$ ./recover_test 0
# search keys inserted before
$ ./recover_test 1
...
[REBUILD] rebuild RNTree
[REBUILD] rebuild over..
check successfully..
Please make sure that the flag CLEAR_NVM_POOL is closed when doing the recovery test.
This repo can be used as a testbed of different tree structures (or other types with similar interfaces) under different benchmarks.
If you want to compare your work with RNTree in our framework, you can inherit the base class Index in include/index.h and implement its virtual functions like insert, remove, update, etc. Then add a new entry in the include/index_factory.h to return an index of your own class. Then just run the benchmark and see how efficient your work is!
You can also run your own workloads. More information can be found in coordinator.h and benchmarks.h.
In addtion to RNTree, we also provide our implementations of other works: FPTree, WB+tree, NVTree. We try out best to follow their original algorithms except some modifications decribed in our paper for better comparision. You can compare to these works with our implementations, but we do not promise that our implementations are exactly the same to these works.
RNTree uses SATA License (Star and Thank Author License, originally here). Please star this project before you use it :)