Repository files navigation

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.

sudo add-apt-repository -y ppa:ubuntu-toolchain-r/testsudo apt updatesudo apt upgradesudo apt install build-essential gcc-11 g++-11 cpp-11 cmakesudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-11 100sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-11 100sudo update-alternatives --install /usr/bin/gcov gcov /usr/bin/gcov-11 100

Build Garner library & client executables:

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

Run all tests (recommend release mode build):

cd buildctest

Run an individual test for detailed output:

./tests/test_<name> -h

Run simple benchmarking of transaction throughput:

./bench/simple_bench -h

sudo apt install clang-format python3-pippip3 install black matplotlib

Run formatter for all source code files:

./scripts/format-all.sh

Build in debug mode:

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

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

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

• 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

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