Consistent Hashing の実装
最近、Consisten Hashing について調べている。 日本語で解説してくれているページはいくつもあって、それが言っていることはわかるのだけれど、やっぱりコードを読んでみないとちゃんとわかっているかわからない。
そこで、Github を漁っていたら、簡単なNode.js 実装を発見した。 それを読んでスッキリ理解できたのだが、自分で実装してみないことには落ち着かない。 そこで、この Node.js の Consistent Hashing 実装を Python に移植してみた。
#-*- coding: utf-8 -*-
import math
from hashlib import sha1
class ConsistentHashing(object):
def __init__(self, nodes):
self.replicas = 160
self.ring = {}
self.keys = []
self.nodes = []
for node in nodes:
self.add_node(node)
def add_node(self, node):
self.nodes.append(node)
for x in range(self.replicas):
key = sha1(u'%s:%d' % (node, x)).hexdigest()
self.keys.append(key)
self.ring[key] = node
self.keys.sort()
def remove_node(self, node):
while node in self.nodes:
self.nodes.remove(node)
for x in range(self.replicas):
key = sha1(u'%s:%d' % (node, x)).hexdigest()
del self.ring[key]
while key in self.keys:
self.keys.remove(key)
def get_node(self, key):
if len(self.ring) is 0:
return 0
key_hash = sha1(key).hexdigest()
position = self.get_node_position(key_hash)
return self.ring[self.keys[position]]
def get_node_position(self, key_hash):
upper = len(self.ring) - 1
lower = 0
index = 0
compare = 0
if upper is 0:
return 0
while lower <= upper:
index = int(math.floor((lower + upper) / 2))
compare = self.compare(self.keys[index], key_hash)
if compare is 0:
return index
elif compare is 1:
upper = index - 1
else:
lower = index + 1
if upper < 0:
upper = len(self.ring) - 1
return upper
def compare(self, v1, v2):
return 1 if v1 > v2 else -1 if v1 < v2 else 0
