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