Repository files navigation

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

The implemented algorithms are:

• [1997]ring hash byD. Karger et al.
• [1998]rendezvous hash byThaler and Ravishankar
• [2014]jump hash byLamping and Veach
• [2015]multi-probe hash byAppleton and O’Reilly
• [2016]maglev hash byD. E. Eisenbud
• [2020]anchor hash byG. Mendelson et al.
• [2021]dx hash byChaos Dong and Fang Wang
• [2023]memento hash byM. Coluzzi et al.
• [2024]flip hash byMasson and Lee
• [2024]jumpback hash byO. Ertl
• [2024]binomial hash byM. Coluzzi et al.

Each implementation is divided into two classes:

• Each Engine class (e.g., AnchorEngine) contains an accurate implementation of the algorithm as described in the related paper. These classes do not make any consistency check to keep the performance as close as possible to what was claimed in the related papers.
• Each Hash class (e.g., AnchorHash) is a wrapper of the related Engine class allowing every implementation to match the same interface. These classes also perform all the consistency checks needed to grant a safe execution.

The project includes a benchmarking tool designed explicitly for consistent hashing algorithms.The tool allows benchmarking the following metrics in a fair and agnostic way:

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

You can build the tool usingApache Maven. It will generate ajar file calledconsistent-hashing-algorithms-1.0.0-jar-with-dependencies.jar. You can then run the jar file providing a configuration file to customize your execution.

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

If the config files are not correctly configured, the tool warns the user and tries to continue the execution.It will run only the correctly configured benchmarks. If the proceeding is not possible, the tool will return an error.

Refer to thetemplate.yaml file for a complete explanation of the configurations.

Once the configuration file is ready, you can run the benchmarks with the following command:

$ java -jar consistent-hashing-algorithms-1.0.0-jar-with-dependencies.jar<your-config>.yaml

You can add your own consistent hash algorithm by performing a merge request.The class implementing your algorithm should be calledYourAlgorithmEngine.All the classes subfixed byEngine implement the consistent hash algorithms as described in the related papers.

You must implement three more classes to compare your algorithm against the available ones using the benchmark tool. Namely:

• YourAlgorithmHash: this must implement theConsistentHash interface and possibly perform all the consistency checks (that can be avoided in theYourAlgorithmEngine).
• YourAlgorithmEnginePilot: this must implement theConsistentHashEnginePilot interface and performs the operations of adding a node, removing a node, and lookup a key by invoking the related methods of theYourAlgorithmEngine class in the most efficient way.
• YourAlgorithmFactory: this must implement theConsistentHashFactory interface and provides a convenient way to instantiate the algorithm and the other utility classes.