basho/riak_core — pull request #183 by jonmeredith (2012-05-25 20:50:46+00:00)
Title: ClaimV3

Claim V3 - unlike the v1/v2 algorithms, v3 treats claim as an optimization problem. In it's current form it creates a number of possible claim plans and evaluates them for violations, balance and diversity, choosing the 'best' plan.

Violations are a count of how many partitions owned by the same node are within target-n of one another. Lower is better, 0 is desired if at all possible.

Balance is a measure of the number of partitions owned versus the number of partitions wanted. Want is supplied to the algorithm by the caller as a list of node/counts. The score for deviation is the RMS of the difference between what the node wanted and what it has. Lower is better, 0 if all wants are mets.

Diversity measures how often nodes are close to one another in the preference list. The more diverse (spread of distances apart), the more evenly the responsibility for a failed node is spread across the cluster. Diversity is calculated by working out the count of each distance for each node pair
(currently distances are limited up to target N) and computing the RMS on that. Lower diversity score is better, 0 if nodes are perfectly diverse.

For testing and playing around, you may want to look at running riak_core_claim_sim:commission(). which will run comparisons against the v1/v2 claim algorithm for some preset combinations of ring size, number of nodes, and target n.

You could also play with riak_core_claim_sim:print_failure_analysis(Ring, TargetN, NumFailures) which prints reports on the console for how a ring does given a target N and number of nodes to fail.

This code is based on the jdm-claim-sim branch - conflicts with the cluster management changes will need to be resolved between the three branches before we can merge.