cpp-consistent-hashing-algorithms

Overview

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

Algorithms

• Jump by Lamping et al. (2014)
• Anchor by Mendelson et al. (2020)
• Dx by Dong et al. (2021)
• Power by Leu et al. (2023)
• Memento by Coluzzi et al. (2023)

You can find new implementations in related branches:

• Ring by Karger et al. (1997)
• Maglev by Eisenbud et al. (2016)

Benchmarks

• Balance: The ability of the algorithm to spread the keys evenly across the cluster nodes.
• Initialization Time: The time the algorithm requires to initialize its internal structure.
• Lookup Time: The time the algorithm needs to find the node a given key belongs to.
• Memory Usage: The amount of memory the algorithm uses to store its internal structure.
• Monotonicity: The ability of the algorithm to move the minimum amount of resources when the cluster scales.
• Resize Balance: The ability of the algorithm to keep its balance after adding or removing nodes.
• Resize Time: The time the algorithm requires to reorganize its internal structure after adding or removing nodes.

Configuration

The format of the configuration file is described in detail in the configs/template.yaml file. The tool will use the configs/default.yaml file that represents the default configuration if no configuration file is provided.

Flow Control

Exploring the flow control of the benchmark routine.

Instructions

Clone the repository and navigate to the cloned repository:

git clone https://github.com/robertovicario/cpp-consistent-hashing-algorithms.git
cd cpp-consistent-hashing-Algorithms

Run repository setup:

• vcpkg:

  # Ensure scripts has executable permissions:
  # chmod +x repo.sh
  ./repo.sh

• CMake:

  # Ensure scripts has executable permissions:
  # chmod +x cmake.sh
  ./cmake.sh

Build the project with Ninja:

cd build
ninja

Start the framework:

• Default configuration:

  ./main

• Custom configuration:

  ./main <your_config>.yaml

Contributing

Adding New Algorithms

1. Insert the algorithm name into any configuration file located in configs/.
2. Implement your algorithm in Algorithms/your_algo/. Keep in mind that the system employs C++ templates to integrate the algorithms into the loop.
3. Integrate a new execution routine into Main.cpp. Append a new else if branch and incorporate your engine using:

   execute<YourEngine>("your_algo", handler, yaml);

Adding New Benchmarks

1. Insert the benchmark name into any configuration file located in configs/.
2. Implement the benchmark in Benchmarks/. Create a function named computeYourBenchmark within it, accepting parameters string algorithm and uint32_t initNodes. Note that the system utilizes C++ templates for benchmark integration into the loop.
3. Integrate a new benchmark routine into Benchmarks/Routine.hpp. Append a new else if branch and incorporate your engine using:

   printInfo(l, algorithm, benchmark, hashFunction, initNodes, iterationsRun);
   results[l] = computeYourBenchmark<Engine>(algorithm, initNodes);

Licence

This project is distributed under GNU General Public License version 3. You can find the complete text of the license in the project repository.

Important

Credits

• java-consistent-hashing-algorithms:
  • Author: SUPSI-DTI-ISIN
  • License: GNU General Public License version 3
  • Source: GitHub Repository
• cpp-anchorhash:
  • Author: anchorhash
  • License: The MIT License
  • Source: GitHub Repository
• DxHash:
  • Author: ChaosD
  • License: none
  • Source: GitHub Repository

Contacts

• Amos Brocco: amos.brocco@supsi.ch
• Roberto Vicario: roberto.vicario@student.supsi.ch