Repository files navigation

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 byLamping and Veach
• [2020]anchor hash byGal Mendelson et al., using the implementation found onGithub
• [2023]power consistent hash byEric Leu
• [2023]memento hash byM. Coluzzi et al.

The project includes three benchmarking toolsspeed_test,balance, andmonotonicity derived from the same tools provided byAnchorhash

speed_test also recordsheap allocations and the maximum allocated heap space.

Clone the repository:

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

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

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

Generate the build file (forNinja):

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

Move into thebuild directory and start building:

cd buildninja

Thespeed_test benchmark performs several random key lookups, the syntax is:

./speed_test Algorithm AnchorSet WorkingSet NumRemovals Numkeys ResFilename

where

• Algorithm can bememento (for MementoHash usingboost::unordered_flat_map for the removal set),mementoboost (for MementoHash usingboost::unordered_map for the removal set),mementostd (for MementoHash usingstd::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 byanchor but must be set to a valueat least equal to WorkingSet even withMementoHash;
• WorkingSet is the size of the initial Working set (w);
• NumRemovals is the number of nodes that should be removed (randomly, except forJump) 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.txtAlgorithm: 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: 802488Memento<boost::unordered_flat_map> Elapsedtime is 0.333966 seconds, maximum heap allocated memory is 802488 bytes, sizeof(Memento<boost::unordered_flat_map>) is 56

Thebalance benchmark performs a balance test and accepts the same parameters asspeed_test. Example:

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

Themonotonicity benchmark performs a monotonicity test and accepts the same parameters asspeed_test. Example:

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

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

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