कंसिस्टेंट हैशिंग

रीहैशिंग की समस्या

साधारण hash(key) % N शार्डिंग में, एक नोड जोड़ने या हटाने से N बदलता है और लगभग हर की फिर से मैप हो जाती है — एक विशाल, अनावश्यक डेटा फेरबदल।

लॉकरों की रिंग

कंसिस्टेंट हैशिंग नोड्स और की दोनों को एक रिंग (हैश सर्कल) पर रखती है। एक की उस नोड की होती है जो घड़ी की दिशा में सबसे पहले मिलता है। नोड जोड़ने पर केवल उसके नज़दीकी पड़ोसी से की छिनती हैं — बाकी सब अछूते रहते हैं।

वर्चुअल नोड्स

हर भौतिक नोड को रिंग पर कई बिंदु दें (वर्चुअल नोड्स) ताकि लोड यादृच्छिक स्थान पर निर्भर होने के बजाय समान रूप से फैले।

ring = {}
for node in nodes:
  for v in range(150):  # virtual replicas
    ring[hash(node + str(v))] = node

def lookup(key):
  h = hash(key)
  return ring[first_point_clockwise_from(h)]

Output:

More virtual nodes = smoother load distribution

इसका उपयोग कहाँ

कंसिस्टेंट हैशिंग कैश क्लस्टर (Memcached क्लाइंट), CDN और Cassandra व DynamoDB जैसे वितरित डेटाबेस को शक्ति देती है — जहाँ भी नोड जुड़ते/छूटते हैं और आप न्यूनतम डेटा मूवमेंट चाहते हैं।