/usr/lib/python2.7/dist-packages/graphite/render/hashing.py is in graphite-web 0.9.12+debian-6.
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 | """Copyright 2008 Orbitz WorldWide
Copyright 2011 Chris Davis
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License."""
from graphite.logger import log
import time
try:
from hashlib import md5
except ImportError:
from md5 import md5
import bisect
def hashRequest(request):
# Normalize the request parameters so ensure we're deterministic
queryParams = ["%s=%s" % (key, '&'.join(values))
for (key,values) in request.GET.lists()
if not key.startswith('_')]
normalizedParams = ','.join( sorted(queryParams) ) or 'noParam'
myHash = stripControlChars(normalizedParams) #memcached doesn't like unprintable characters in its keys
return compactHash(myHash)
def hashData(targets, startTime, endTime):
targetsString = ','.join(targets)
startTimeString = startTime.strftime("%Y%m%d_%H%M")
endTimeString = endTime.strftime("%Y%m%d_%H%M")
myHash = targetsString + '@' + startTimeString + ':' + endTimeString
myHash = stripControlChars(myHash)
return compactHash(myHash)
def stripControlChars(string):
return filter(lambda char: ord(char) >= 33, string)
def compactHash(string):
hash = md5()
hash.update(string)
return hash.hexdigest()
class ConsistentHashRing:
def __init__(self, nodes, replica_count=100):
self.ring = []
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, key):
for i in range(self.replica_count):
replica_key = "%s:%d" % (key, i)
position = self.compute_ring_position(replica_key)
entry = (position, key)
bisect.insort(self.ring, entry)
def remove_node(self, key):
self.ring = [entry for entry in self.ring if entry[1] != key]
def get_node(self, key):
position = self.compute_ring_position(key)
search_entry = (position, None)
index = bisect.bisect_left(self.ring, search_entry)
index %= len(self.ring)
entry = self.ring[index]
return entry[1]
|