BLOG

将来の夢はおもしろお兄さんです。

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