Garner

Hierarchical validation in Silo-flavor optimistic concurrency control (OCC) on a B+-tree index (in fact, almost a B-link tree index).

The Garner codebase is aimed to be a well-documented, expandable, and easy-to-adopt in-memory transactional key-value store for future concurrency control research projects. This is an on-going work and is subject to change.

Build

Install dependencies and `gcc` 11.x for full C++-20 support...

sudo add-apt-repository -y ppa:ubuntu-toolchain-r/test
sudo apt update
sudo apt upgrade

sudo apt install build-essential gcc-11 g++-11 cpp-11 cmake

sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-11 100
sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-11 100
sudo update-alternatives --install /usr/bin/gcov gcov /usr/bin/gcov-11 100

Build Garner library & client executables:

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j

Run

Run all tests (recommend release mode build):

cd build
ctest

Run an individual test for detailed output:

./tests/test_<name> -h

Run simple benchmarking of transaction throughput:

./bench/simple_bench -h

Develop

Install development dependencies...

sudo apt install clang-format python3-pip
pip3 install black matplotlib

Run formatter for all source code files:

./scripts/format-all.sh

Build in debug mode:

mkdir build-debug && cd build-debug
cmake -DCMAKE_BUILD_TYPE=Debug ..
make -j

Build with certain compile-time options on (e.g., TXN_STAT):

mkdir build-stats && cd build-stats
cmake -DCMAKE_BUILD_TYPE=Release -DTXN_STAT=on ..
make -j

TODO List

• Basic concurrent BPTree
• Transaction manager
• Basic HV-OCC protocol
• Deadlock-free write locking in validation
• Subtree crossing & node item skip_to
• Proper support for on-the-fly insertions
• More comprehensive benchmarking
• Try jemalloc/tcmalloc
• Better latching to reduce root contention
• Remove shared_mutex in cases where an atomic is fine
• Replace shared_mutex with userspace spinlock
• Start HV protocol at certain level (instead of root)
• Implement Delete & related concurrency
• Implement proper durability logging

References

• Latch crabbing (Latch coupling)
• Silo OCC
• Adaptive OCC