コンシステンシhashおよびpythonコード実装

背景:自分の前のプロジェクトではKVとしてredisを使用しているが,性能だけでなく,主にredisのhashデータ構造を使用する必要がある.その後、業務が発展するにつれて、読み書きの圧力はますます大きくなり、最初は読み書きが分離され、それから主が多く、書くredisの圧力をうまく解決できないことに気づいた.また、自分が使っているredisバージョンが低いため、分布式の機能をサポートしていないので、自分で分布式のredisストレージシステムを配置したいと思っていたが、考え始めたのは簡単にhashを作ることで、hashcode=hash(key/machine_num)だった.次に対応するキーを対応するマシンに置くが、マシンが異常にダウンしたり、新しいマシンが追加されたりすることを考慮すると、データ移行の代価が大きいので、コンシステンシhashを理解して、分散型のKVストレージシステムを実現する準備をした.
主な思想:一致性hashの経典の紹介はネット上でたくさんあって、私は以下のこの文章の紹介の悪くないと感じます.
http://blog.csdn.net/cywosp/article/details/23397179/
実は主な考えは以下のように思います.

マシンを何らかのhashアルゴリズム(例えばMD 5)に従って計算するマシンのhashcode値

を得る.

記憶されたデータについて、データのkeyに基づいて、マシンと同じhashアルゴリズムを用いて対応するhashcode値を取得し、keyを時計回りに最も近いマシンに書き込む.hashcode(key)<=hashcode(machine)であってもよい機器

新しい機械が加入した場合、新しい機械が影響したデータを再分配するだけである.マシンを削除する場合、削除されたマシンのデータを再割り当てするだけで、データの移行コストを削減できます.

平衡性を維持するために、雪崩効果を防止するために、仮想ノードを実マシンの代わりに使用し、1つの実マシンが複数の仮想ノードに対応することで、データの分布均衡

を保証することができる.
以下はPythonのコード実装であり,実装構想は上述したものである.コードもネット上を参考にしています.http://www.cnblogs.com/xuxm2007/archive/2011/08/28/2156015.html

   #! /usr/bin/env python
    # -*- coding:utf8 -*-

    import md5

    class HashRing(object):
        def __init__(self, nodes=None, replicas=3):
            """
            Manages a hash ring
            :nodes 
                a list of object that have a proper __str__ representation
            :replicas
                indicates how many virtual points should be used per node,
                replicas are required to improve the distribution
            """

            self.replicas = replicas
            self.ring = {}
            self._sorted_keys = []
            if nodes:
                for node in nodes:
                    self.add_node(node)

        def add_node(self, node):
            """
            Adds a node to the hash ring(including a number of replicas)
            """
            for i in xrange(0, self.replicas):
                key = self.gen_key("%s:%s" % (node, i))
                self.ring[key] = node
                self._sorted_keys.append(key)

            self._sorted_keys.sort()

        def remove_node(self, node):
            """
            Removes node from the hash ring and its replicas
            """
            for i in xrange(0, self.replicas):
                key = self.gen_key("%s:%s" % (node, i))
                del self.ring[key]
                self._sorted_keys.remove(key)

        def get_node_keys(self, node):
            """
            Given a node return all its virturl node keys
            """
            keys = []
            for i in xrange(0, self.replicas):
                key = self.gen_key("%s:%s" % (node, i))
                keys.append(key)
            return key

        def get_node(self, string_key):
            """
            Given a string key corresponding node in the hash ring is returned.
            If the hash ring is empty, None is returned.
            """
            return self.get_node_pos(string_key)[0]

        def get_node_pos(self, string_key):
            """
            Given a string key corresponding node in the hash ring is returned
            along with it's position in the ring.

            If the hash ring is empty, (None, None) is returned
            """
            if not self.ring:
                return None, None

            key = self.gen_key(string_key)
            nodes = self._sorted_keys
            for i in xrange(0, len(nodes)):
                node = nodes[i]
                if key <= node:
                    return self.ring[node], i

            return self.ring[nodes[0]], 0

        def get_nodes(self, string_key):
            """
            Given a string key it returns the nodes as a generator that can hold the key.
            The generator is never ending and iterates through the ring starting at the correct position.
            """
            if not self.ring:
                yield None

            node, pos = self.get_node_pos(string_key)
            for key in self._sorted_keys:
                yield self.ring[key]

        def gen_key(self, key):
            """
            Given a string key it return a long value,
            this long value represent a place on the hash ring.

            md5 is currently used because it mixes well.
            """

            m = md5.new()
            m.update(key)
            return long(m.hexdigest(), 16)