Consistent hashing

Consistent hashing, özel bir hashing türüdür. Bu yöntem, slot ekleme veya çıkarma durumunda, diğer slotların key mapping lerini önemli ölçüde değişmemesini sağlar. Buna rağmen geleneksel hash table, dizi içerisindeki bir tek değerin değişmesi ile tüm key lerin remapping yapılması gerekir.

Consistent hashing, ortalama olarak K/n kadar remapping gerekir. (K->Key sayısı, n->Slot sayısı) İnternet kullanımının artması ile gün geçtikçe önem derecesi artmaktadır.

David Karger tarafından MIT de kullanmak için tasarlandı.[1]

Resimdeki çember üzerindeki mavi noktalar(1,2,3,4) nesneler, kırmızı noktalar önbelleklerdir.

Çember üzerinde, saat yönünde  dönerek hangi nesnenin hangi önbelleğe denk geldiğini bulabiliriz.
1. ve 4. nesneler A önbelleği, 2. nesne B önbelleği, 3. nesne C önbelleğindedir.
Eğer C önbelleği kaldırılırsa, 3. nesne A önbelleğinde yer alır ve diğer tüm nesnelerin mapping i değişmez.

Eğer D önbelleği eklenirse, 3. ve 4. nesneler D önbelleğinde, 1. nesne A önbelleğinde.


Consistent hashing basit bir python implementasyonu

import md5

class HashRing(object):

    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas

        self.ring = dict()
        self._sorted_keys = []

        if nodes:
            for node in nodes:
                self.add_node(node)

    def add_node(self, node):
        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):
        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(self, string_key):
        return self.get_node_pos(string_key)[0]

    def get_node_pos(self, string_key):
        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):
        if not self.ring:
            yield None, None

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

        while True:
            for key in self._sorted_keys:
                yield self.ring[key]

    def gen_key(self, key):
        m = md5.new()
        m.update(key)
        return long(m.hexdigest(), 16)


Kullanımı

import HashRing

memcache_servers = ['192.168.0.246:11212',
                    '192.168.0.247:11212',
                    '192.168.0.249:11212']
ring = HashRing(memcache_servers)
server = ring.get_node('my_key')



[1]http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf
http://en.wikipedia.org/wiki/Consistent_hashing
http://www.lexemetech.com/2007/11/consistent-hashing.html
http://amix.dk/blog/post/19367