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

Figure 1: 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