M3-algorithm-implementation

A Matlab implementation of the M3 algorithm as described in Beyond the Ring: Quantized Heterogeneous Consistent Hashing. This repo also contains the code for the evaluations presented in the paper.

Documentation

return_alloc(q,M)

An implementation function of the M3 algorithm.

• q - number of virtual servers in the system
• M - vector of service rates of the physical servers The function returns an array indicating how many virtual servers should be assigned to each physical server according to the order presented in the service rates vector M.

fnvhash_vec(msg)

A vectorized implementation function of the fnv-1a hash algorithm.

• msg - column vector of identifiers to hash The function returns a column vector of hashed identifiers according to the order presented in the input vector.

compare_algorithms_stability_LB

A script file used to generate the output figure as presented in the evaluation section (Fig. 8). This script uses a random function and may yield a slightly different output for each run.

compare_algorithms_stability_storage

A script file used to generate the output figure as presented in the evaluation section (Fig. 7). This script uses a random function and may yield a slightly different output for each run.

max_stable_load

A script file used to generate the output figure as presented in the evaluation section (Fig. 6).

inspect_fairness_graph

A script file used to generate the output figure as presented in the evaluation section (Fig. 5). This script uses a random function and may yield a slightly different output for each run.

Usage

To run compare_algorithms_stability.m, you must first download the file 'unique_keys_hashed_154M.mat' into the same directory of the scripts.