graphite-project/carbon — pull request #196 by jssjr (2013-12-16 03:49:19+00:00)
Title: Demonstrate hash ring collisions in sufficiently large clusters

The hash ring algorithm computes a positional element to correspond to the ring replica for the node being inserted into the consistent hash ring. The current implementation of the hash ring does not track the hash of position to node mappings, but instead appends the position and node as a tuple to the ring using bisect.insort_right(). This creates a situation where rebalancing the ring by a safe (where safe is defined as less than the replication_factor) number of nodes can result in unrouted metrics in the cluster.

In addition, a buggy CH implementation in python makes it quite difficult to recreate the CH behavior in other languages when creating tooling that works with Carbon.

Potential fixes include modifying the consistent hash ring implementation by:

- Incrementing the positional key before insort insertion if a collision is detected.
- Using a sufficiently large value for the consistent hash key to prevent collisions during node addition/removal. (I think this should be mathematically safe, but haven't done the tests/calculations.)
- Other?

Unfortunately, all of the proposed solutions will result in a very small number of unbalanced metrics in a cluster after the algorithm change, so tooling to compensate or a clear description of how to upgrade is required.

### The test case failure

What is being tested below is the uniqueness between a ring lookup position and the node it reflects. When hashing metric names we will use these ring positions to determine the order of nodes that map to the supplied metric name.

```
% bin/python lib/carbon/tests/test_hashing.py
....FFFF
======================================================================
FAIL: test_6_node_positional_itegrity (__main__.HashIntegrityTest)
Make a cluster, verify we don't have positional collisions
----------------------------------------------------------------------
Traceback (most recent call last):
File "lib/carbon/tests/test_hashing.py", line 54, in test_6_node_positional_itegrity
len(set([n[0] for n in ring.ring])))
AssertionError: 600 != 598

======================================================================
FAIL: test_7_node_positional_itegrity (__main__.HashIntegrityTest)
Make a cluster, verify we don't have positional collisions
----------------------------------------------------------------------
Traceback (most recent call last):
File "lib/carbon/tests/test_hashing.py", line 64, in test_7_node_positional_itegrity
len(set([n[0] for n in ring.ring])))
AssertionError: 700 != 698

======================================================================
FAIL: test_8_node_positional_itegrity (__main__.HashIntegrityTest)
Make a cluster, verify we don't have positional collisions
----------------------------------------------------------------------
Traceback (most recent call last):
File "lib/carbon/tests/test_hashing.py", line 74, in test_8_node_positional_itegrity
len(set([n[0] for n in ring.ring])))
AssertionError: 800 != 796

======================================================================
FAIL: test_9_node_positional_itegrity (__main__.HashIntegrityTest)
Make a cluster, verify we don't have positional collisions
----------------------------------------------------------------------
Traceback (most recent call last):
File "lib/carbon/tests/test_hashing.py", line 84, in test_9_node_positional_itegrity
len(set([n[0] for n in ring.ring])))
AssertionError: 900 != 894

----------------------------------------------------------------------
Ran 8 tests in 0.030s

FAILED (failures=4)
```