Skip to content

Instantly share code, notes, and snippets.

@stupidbodo
Created December 31, 2015 02:46
Show Gist options
  • Save stupidbodo/dcd0b62df4dbdef6c1d3 to your computer and use it in GitHub Desktop.
Save stupidbodo/dcd0b62df4dbdef6c1d3 to your computer and use it in GitHub Desktop.
Consistent Hashing Example - Python
from hashlib import md5
from bisect import bisect
class Ring(object):
def __init__(self, server_list, num_replicas=3):
nodes = self.generate_nodes(server_list, num_replicas)
hnodes = [self.hash(node) for node in nodes]
hnodes.sort()
self.num_replicas = num_replicas
self.nodes = nodes
self.hnodes = hnodes
self.nodes_map = {self.hash(node): node.split("-")[1] for node in nodes}
@staticmethod
def hash(val):
m = md5(val)
return int(m.hexdigest(), 16)
@staticmethod
def generate_nodes(server_list, num_replicas):
nodes = []
for i in xrange(num_replicas):
for server in server_list:
nodes.append("{0}-{1}".format(i, server))
return nodes
def get_node(self, val):
pos = bisect(self.hnodes, self.hash(val))
if pos == len(self.hnodes):
return self.nodes_map[self.hnodes[0]]
else:
return self.nodes_map[self.hnodes[pos]]
server_list = ["127.0.0.1", "127.0.0.2", "127.0.0.3"]
ring = Ring(server_list)
print ring.get_node("KNKLn")
print ring.get_node("12213")
print ring.get_node("2434")
print ring.get_node("1")
# Will Print:
# 127.0.0.2
# 127.0.0.2
# 127.0.0.1
# 127.0.0.3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment