Skip to content

Latest commit

 

History

History
116 lines (85 loc) · 3.08 KB

README.md

File metadata and controls

116 lines (85 loc) · 3.08 KB

Garner

Format check Build & Tests status License: MIT

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