cpp-consistent-hashing-algorithms

This project collects C++ implementations and benchmarking tools of some of the most prominent consistent hashing algorithms for non-peer-to-peer contexts.

The implemented algorithms are:

• [2014] jump hash by Lamping and Veach
• [2020] anchor hash by Gal Mendelson et al., using the implementation found on Github
• [2023] power consistent hash by Eric Leu
• [2023] memento hash by M. Coluzzi et al.

Benchmarks

The project includes three benchmarking tools speed_test, balance, and monotonicity derived from the same tools provided by Anchorhash

speed_test also records heap allocations and the maximum allocated heap space.

Building

Clone the repository:

git clone https://github.com/slashdotted/cpp-consistent-hashing-algorithms.git

Move into the project's directory and update the vcpkg submodule:

cd cpp-consistent-hashing-algorithms/
git submodule update --init
cd vcpkg
./bootstrap-vcpkg.sh -useSystemBinaries

Generate the build file (for Ninja):

cd ..
cmake -B build/ -S . -GNinja -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake -DCMAKE_BUILD_TYPE=Release

Move into the build directory and start building:

cd build
ninja

Running the benchmarks

The speed_test benchmark performs several random key lookups, the syntax is:

./speed_test Algorithm AnchorSet WorkingSet NumRemovals Numkeys ResFilename

where

• Algorithm can be memento (for MementoHash using boost::unordered_flat_map for the removal set), mementoboost (for MementoHash using boost::unordered_map for the removal set), mementostd (for MementoHash using std::unordered_map for the removal set), mementomash (for MementoHash using a hash table similar to Java's HashMap), anchor (for AnchorHash), mementogtl (for Memento with gtl hash map), jump (for JumpHash), power (for Power Consistent Hashing)
• AnchorSet is the size of the Anchor set (a): this parameter is used only by anchor but must be set to a value at least equal to WorkingSet even with MementoHash;
• WorkingSet is the size of the initial Working set (w);
• NumRemovals is the number of nodes that should be removed (randomly, except for Jump) before starting the benchmark;
• Numkeys is the number of keys that will be queried during the benchmark;
• ResFilename is the filename containing the results of the benchmark; By default, details about the allocate memory will also be produced in the output. For example:

./speed_test memento 1000000 1000000 20000 1000000 memento.txt
Algorithm: memento, AnchorSet: 1000000, WorkingSet: 1000000, NumRemovals: 20000, NumKeys: 1000000, ResFileName: memento.txt, Random: rand()
   @StartBenchmark: Allocations: 0, Allocated: 0, Deallocations: 0, Deallocated: 0, Maximum: 0
   @AfterAlgorithmInit: Allocations: 0, Allocated: 0, Deallocations: 0, Deallocated: 0, Maximum: 0
   @AfterRemovals: Allocations: 11, Allocated: 802488, Deallocations: 10, Deallocated: 401076, Maximum: 802488
   @EndBenchmark: Allocations: 11, Allocated: 802488, Deallocations: 10, Deallocated: 401076, Maximum: 802488
Memento<boost::unordered_flat_map> Elapsed time is 0.333966 seconds, maximum heap allocated memory is 802488 bytes, sizeof(Memento<boost::unordered_flat_map>) is 56

The balance benchmark performs a balance test and accepts the same parameters as speed_test. Example:

./balance memento 1000000 1000000 20000 1000000 memento.txt
Algorithm: memento, AnchorSet: 1000000, WorkingSet: 1000000, NumRemovals: 20000, NumKeys: 1000000, ResFileName: memento.txt
Memento<boost::unordered_flat_map>: LB is 8.82

The monotonicity benchmark performs a monotonicity test and accepts the same parameters as speed_test. Example:

./monotonicity memento 1000000 1000000 1000 1000000 memento.txt
Algorithm: memento, AnchorSet: 1000000, WorkingSet: 1000000, NumRemovals: 1000, NumKeys: 1000000, ResFileName: memento.txt
Done determining initial assignment of 1000000 unique keys
Removed node 424868
Memento<boost::unordered_flat_map>: after removal misplaced keys are 0% (0 keys out of 1000000)
Added node 424868
Memento<boost::unordered_flat_map>: after adding back misplaced keys are 0% (0 keys out of 1000000)

Java implementation

For a Java implementation of these and additional algorithms please refer to this repository

Credits

The AnchorHash implementation is based on code Copyright (c) 2020 anchorhash released under the MIT License MementoHash is based on the Java implementation found on this repository, released under the GNU GPL-3.0 license