/usr/share/pyshared/carbon/hashing.py is in graphite-carbon 0.9.12-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | try:
from hashlib import md5
except ImportError:
from md5 import md5
import bisect
class ConsistentHashRing:
def __init__(self, nodes, replica_count=100):
self.ring = []
self.nodes = set()
self.replica_count = replica_count
for node in nodes:
self.add_node(node)
def compute_ring_position(self, key):
big_hash = md5( str(key) ).hexdigest()
small_hash = int(big_hash[:4], 16)
return small_hash
def add_node(self, node):
self.nodes.add(node)
for i in range(self.replica_count):
replica_key = "%s:%d" % (node, i)
position = self.compute_ring_position(replica_key)
entry = (position, node)
bisect.insort(self.ring, entry)
def remove_node(self, node):
self.nodes.discard(node)
self.ring = [entry for entry in self.ring if entry[1] != node]
def get_node(self, key):
assert self.ring
node = None
node_iter = self.get_nodes(key)
node = node_iter.next()
node_iter.close()
return node
def get_nodes(self, key):
assert self.ring
nodes = set()
position = self.compute_ring_position(key)
search_entry = (position, None)
index = bisect.bisect_left(self.ring, search_entry) % len(self.ring)
last_index = (index - 1) % len(self.ring)
while len(nodes) < len(self.nodes) and index != last_index:
next_entry = self.ring[index]
(position, next_node) = next_entry
if next_node not in nodes:
nodes.add(next_node)
yield next_node
index = (index + 1) % len(self.ring)
|