/usr/lib/python2.7/dist-packages/carbon/hashing.py is in graphite-carbon 1.0.2-1.
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | try:
from hashlib import md5
except ImportError:
from md5 import md5
import bisect
try:
import pyhash
hasher = pyhash.fnv1a_32()
def fnv32a(string, seed=0x811c9dc5):
return hasher(string, seed=seed)
except ImportError:
def fnv32a(string, seed=0x811c9dc5):
"""
FNV-1a Hash (http://isthe.com/chongo/tech/comp/fnv/) in Python.
Taken from https://gist.github.com/vaiorabbit/5670985
"""
hval = seed
fnv_32_prime = 0x01000193
uint32_max = 2 ** 32
for s in string:
hval = hval ^ ord(s)
hval = (hval * fnv_32_prime) % uint32_max
return hval
class ConsistentHashRing:
def __init__(self, nodes, replica_count=100, hash_type='carbon_ch'):
self.ring = []
self.nodes = set()
self.replica_count = replica_count
self.hash_type = hash_type
for node in nodes:
self.add_node(node)
def compute_ring_position(self, key):
if self.hash_type == 'fnv1a_ch':
big_hash = '{:x}'.format(int(fnv32a( str(key) )))
small_hash = int(big_hash[:4], 16) ^ int(big_hash[4:], 16)
else:
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):
if self.hash_type == 'fnv1a_ch':
replica_key = "%d-%s" % (i, node[1])
else:
replica_key = "%s:%d" % (node, i)
position = self.compute_ring_position(replica_key)
while position in [r[0] for r in self.ring]:
position = position + 1
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
if len(self.nodes) == 1:
# short circuit in simple 1-node case
for node in self.nodes:
yield node
return
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)
|