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

कंप्यूटर विज्ञान में, लगातार हैशिंगएक विशेष प्रकार की हैश फंकशन तकनीक है जैसे कि जब हैश तालिका का आकार बदला जाता है $n/m$ कुंजियों को औसतन कहाँ पुनः मैप करने की आवश्यकता है $n$ चाबियों की संख्या है और $m$ स्लॉट की संख्या है. इसके विपरीत, अधिकांश पारंपरिक हैश तालिकाओं में, सरणी स्लॉट की संख्या में बदलाव के कारण लगभग सभी कुंजियों को फिर से मैप करना पड़ता है क्योंकि कुंजियों और स्लॉट्स के बीच मैपिंग को मॉड्यूलर अंकगणित द्वारा परिभाषित किया जाता है।

इतिहास

सुसंगत हैशिंग शब्द डेविड कार्गर एट अल द्वारा प्रस्तुत किया गया था। एमआईटी में वितरित कैश में उपयोग के लिए, विशेष रूप से वर्ल्ड वाइड वेब के लिए। कंप्यूटिंग के सिद्धांत पर संगोष्ठी में 1997 के इस अकादमिक पेपर ने वेब सर्वर की बदलती आबादी के बीच अनुरोधों को वितरित करने के तरीके के रूप में लगातार हैशिंग शब्द को पेश किया। फिर प्रत्येक स्लॉट को वितरित सिस्टम या क्लस्टर में सर्वर द्वारा दर्शाया जाता है। केवल सर्वर को जोड़ने और सर्वर को हटाने (स्केलेबिलिटी या आउटेज के दौरान) की आवश्यकता होती है $num\_keys/num\_slots$ स्लॉट की संख्या (अर्थात सर्वर) बदलने पर आइटमों को फिर से फेरबदल किया जाना चाहिए। लेखक रैखिक हैशिंग और अनुक्रमिक सर्वर जोड़ और निष्कासन को संभालने की इसकी क्षमता का उल्लेख करते हैं, जबकि लगातार हैशिंग सर्वर को मनमाने क्रम में जोड़ने और हटाने की अनुमति देता है। वितरित हैश तालिका जैसे पीयर-टू-पीयर | पीयर-टू-पीयर नेटवर्क में फ़ाइल का ट्रैक रखने की तकनीकी चुनौती को संबोधित करने के लिए बाद में पेपर को फिर से तैयार किया गया था। टेराडाटा ने 1986 में जारी अपने वितरित डेटाबेस में इस तकनीक का उपयोग किया, हालांकि उन्होंने इस शब्द का उपयोग नहीं किया। ठीक इसी उद्देश्य को पूरा करने के लिए टेराडेटा अभी भी हैश तालिका की अवधारणा का उपयोग करता है। स्मार्ट टेक्नोलॉजीज की स्थापना 1998 में वैज्ञानिक डेनियल लेविन और एफ. थॉमसन लीटन (कंसिस्टेंट हैशिंग गढ़ने वाले लेख के सह-लेखक) द्वारा की गई थी। अकामाई के सामग्री वितरण नेटवर्क में, लगातार हैशिंग का उपयोग सर्वर के क्लस्टर के भीतर लोड को संतुलित करने के लिए किया जाता है, जबकि स्थिर विवाह समस्या एल्गोरिदम का उपयोग क्लस्टर में लोड को संतुलित करने के लिए किया जाता है। बड़े वेब अनुप्रयोगों में आंशिक सिस्टम विफलताओं के प्रभाव को कम करने के लिए लगातार हैशिंग का भी उपयोग किया गया है ताकि सिस्टम-व्यापी विफलता के बिना मजबूत कैशिंग प्रदान की जा सके। लगातार हैशिंग वितरित हैश तालिकाओं (डीएचटी) की आधारशिला भी है, जो नोड्स के वितरित सेट में कीस्पेस को विभाजित करने के लिए हैश मानों को नियोजित करती है, फिर कनेक्टेड नोड्स के ओवरले नेटवर्क का निर्माण करती है जो कुंजी द्वारा कुशल नोड पुनर्प्राप्ति प्रदान करती है।

1996 में डिज़ाइन किया गया मिलन स्थल हैशिंग सरल और अधिक सामान्य तकनीक है . यह बहुत अलग उच्चतम यादृच्छिक वजन (एचआरडब्ल्यू) एल्गोरिदम का उपयोग करके लगातार हैशिंग के लक्ष्यों को प्राप्त करता है।

बुनियादी तकनीक

इस मामले में, लगातार हैशिंग का उपयोग करने से बीएलओबी संग्रहीत सर्वर 139 हो जाएगा। बीएलओबी को अगले सर्वर पर मैप किया जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है जब तक कि यह सर्वर तक नहीं पहुंच जाता है $\zeta \leq {\text{server ID}}$

लोड संतुलन (कंप्यूटिंग) की समस्या में, उदाहरण के लिए, जब बाइनरी बड़ी वस्तु को इनमें से किसी को सौंपा जाना होता है $n$ कंप्यूटर क्लस्टर पर सर्वर, मानक हैश फ़ंक्शन का उपयोग इस तरह से किया जा सकता है कि हम उस बीएलओबी के लिए हैश मान की गणना करते हैं, यह मानते हुए कि हैश का परिणामी मान है $\beta$, हम सर्वरों की संख्या के साथ मॉड्यूलर अंकगणित करते हैं ($n$ इस मामले में) उस सर्वर को निर्धारित करने के लिए जिसमें हम BLOB रख सकते हैं: $\zeta =\beta \ \%\ n$; इसलिए बीएलओबी को सर्वर में रखा जाएगा ${\text{server ID}}$ का उत्तराधिकारी है $\zeta$ इस मामले में। हालाँकि, जब किसी सर्वर को आउटेज या स्केलिंग के दौरान जोड़ा या हटाया जाता है (जब $n$ परिवर्तन), हैश टेबल#डायनेमिक आकार बदलने के कारण प्रत्येक सर्वर में सभी बीएलओबी को पुन: असाइन और स्थानांतरित किया जाना चाहिए, लेकिन यह ऑपरेशन महंगा है।

जब किसी सर्वर को पूरे क्लस्टर में जोड़ा या हटाया जाता है, तो प्रत्येक BLOB को पुन: असाइन करने की समस्या से बचने के लिए लगातार हैशिंग को डिज़ाइन किया गया था। केंद्रीय विचार यह है कि, हम हैश फ़ंक्शन का उपयोग करते हैं जो आमतौर पर बीएलओबी और सर्वर दोनों को यूनिट सर्कल में यादृच्छिक रूप से मैप करता है $2\pi$ रेडियंस. उदाहरण के लिए, $\zeta =\Phi \ \%\ 360$ (कहाँ $\Phi$ बीएलओबी या सर्वर के पहचानकर्ता का हैश है, जैसे आईपी पता या सार्वभौमिक रूप से अद्वितीय पहचानकर्ता)। फिर प्रत्येक बीएलओबी को अगले सर्वर को सौंपा जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है। आमतौर पर, बाइनरी खोज एल्गोरिदम या रैखिक खोज का उपयोग उस विशेष बीएलओबी को रखने के लिए किसी स्थान या सर्वर को खोजने के लिए किया जाता है $O(\log N)$ या $O(N)$ क्रमशः जटिलताएँ; और प्रत्येक पुनरावृत्ति में, जो दक्षिणावर्त तरीके से होता है, ऑपरेशन $\zeta \ \leq \ \Psi$ (कहाँ $\Psi$ क्लस्टर के भीतर सर्वर का मान है) बीएलओबी लगाने के लिए सर्वर को खोजने के लिए किया जाता है। यह सर्वरों को बीएलओबी का समान वितरण प्रदान करता है। लेकिन, अधिक महत्वपूर्ण बात यह है कि यदि कोई सर्वर विफल हो जाता है और सर्कल से हटा दिया जाता है, तो केवल बीएलओबी जो विफल सर्वर पर मैप किए गए थे, उन्हें दक्षिणावर्त क्रम में अगले सर्वर पर पुन: असाइन करने की आवश्यकता होती है। इसी तरह, यदि कोई नया सर्वर जोड़ा जाता है, तो इसे यूनिट सर्कल में जोड़ा जाता है, और केवल उस सर्वर पर मैप किए गए बीएलओबी को पुन: असाइन करने की आवश्यकता होती है।

महत्वपूर्ण रूप से, जब कोई सर्वर जोड़ा या हटाया जाता है, तो अधिकांश बीएलओबी अपने पूर्व सर्वर असाइनमेंट को बनाए रखते हैं, और इसके अतिरिक्त $n^{th}$ सर्वर ही कारण बनता है $1/n$ स्थानांतरित करने के लिए बीएलओबी का अंश। यद्यपि क्लस्टर में कैश सर्वरों में बीएलओबी को स्थानांतरित करने की प्रक्रिया संदर्भ पर निर्भर करती है, आमतौर पर, नया जोड़ा गया कैश सर्वर अपने उत्तराधिकारी की पहचान करता है और सभी बीएलओबी को स्थानांतरित करता है, जिनकी मैपिंग इस सर्वर से संबंधित है (यानी जिसका हैश मान इससे कम है) नया सर्वर), इससे। हालाँकि, वेब कैशिंग के मामले में, अधिकांश कार्यान्वयन में कैश्ड बीएलओबी काफी छोटा मानते हुए, इसे स्थानांतरित करने या कॉपी करने की कोई भागीदारी नहीं होती है। जब कोई अनुरोध नए जोड़े गए कैश सर्वर से टकराता है, तो कैश (कंप्यूटिंग)#CACHE-MISS होता है और वास्तविक वेब सर्वर से अनुरोध किया जाता है और भविष्य के अनुरोधों के लिए BLOB को स्थानीय रूप से कैश किया जाता है। पहले उपयोग किए गए कैश सर्वर पर अनावश्यक बीएलओबी कैश प्रतिस्थापन नीतियों के अनुसार हटा दिए जाएंगे।

कार्यान्वयन

होने देना $h_{b}(x)$ और $h_{s}(x)$ क्रमशः बीएलओबी और सर्वर के विशिष्ट पहचानकर्ता के लिए उपयोग किए जाने वाले हैश फ़ंक्शन हों। व्यवहार में, गतिशील रूप से बनाए रखने के लिए बाइनरी सर्च ट्री (BST) का उपयोग किया जाता है ${\text{server ID}}$ क्लस्टर या हैशिंग के भीतर, और बीएसटी के भीतर उत्तराधिकारी या न्यूनतम खोजने के लिए, वृक्ष परिभ्रमण का उपयोग किया जाता है।

डालना $x$ क्लस्टर में

होने देना $\beta$ BLOB का हैश मान इस प्रकार हो कि, $h_{b}(x)=\beta \ \%\ 360$ कहाँ $x\in \mathrm {BLOB}$ और $h_{b}(x)=\zeta$. दर्ज करना $x$, का उत्तराधिकारी खोजें $\zeta$ के बीएसटी में ${\text{server ID}}$एस। अगर $\zeta$ सभी से बड़ा है ${\text{server ID}}$एस, बीएलओबी को सबसे छोटे सर्वर में रखा गया है ${\text{server ID}}$ कीमत।

हटाना $x$ क्लस्टर से

के उत्तराधिकारी का पता लगाएं $\zeta$ बीएसटी में, रिटर्न से बीएलओबी हटा दें ${\text{server ID}}$. अगर $\zeta$ इसका कोई उत्तराधिकारी नहीं है, सबसे छोटे से बीएलओबी हटा दें ${\text{server ID}}$एस।

क्लस्टर में सर्वर डालें

होने देना $\Phi$ सर्वर के पहचानकर्ता का हैश मान इस प्रकार हो, $h_{s}(x)=\Phi \ \%\ 360$ कहाँ $x\in \{{\text{IP address, UUID}}\}$ और $h_{s}(x)=\theta$. उन सभी बीएलओबी को स्थानांतरित करें, जिनका हैश मान इससे छोटा है $\theta$, सर्वर से जिसका ${\text{server ID}}$ का उत्तराधिकारी है $\theta$. अगर $\theta$ सभी में सबसे बड़ा है ${\text{server ID}}$एस, प्रासंगिक बीएलओबी को सबसे छोटे से स्थानांतरित करें ${\text{server ID}}$में है $\theta$.

क्लस्टर से सर्वर हटाएं

के उत्तराधिकारी का पता लगाएं $\theta$ बीएसटी में, बीएलओबी को यहां से हटाएं $\theta$ इसके उत्तराधिकारी सर्वर में। अगर $\theta$ इसका कोई उत्तराधिकारी नहीं है, बीएलओबी को सबसे छोटे में ले जाएं ${\text{server ID}}$एस।

विचरण में कमी

रेडियन के भीतर कई नोड्स की विषमता से बचने के लिए, जो क्लस्टर के भीतर सर्वर के संभाव्यता वितरण में यादृच्छिकता की कमी के कारण होता है, कई लेबल का उपयोग किया जाता है। उन डुप्लिकेट लेबल को वर्चुअल नोड्स कहा जाता है यानी एकाधिक लेबल जो क्लस्टर के भीतर वास्तविक लेबल या सर्वर की ओर इशारा करते हैं। क्लस्टर के भीतर किसी विशेष सर्वर के लिए उपयोग किए जाने वाले वर्चुअल नोड्स या डुप्लिकेट लेबल की मात्रा को उस विशेष सर्वर का वजन कहा जाता है।

व्यावहारिक विस्तार

अभ्यास में लोड संतुलन के लिए लगातार हैशिंग का प्रभावी ढंग से उपयोग करने के लिए बुनियादी तकनीक में कई विस्तार की आवश्यकता है। उपरोक्त मूल योजना में, यदि कोई सर्वर विफल हो जाता है, तो उसके सभी बीएलओबी को दक्षिणावर्त क्रम में अगले सर्वर पर पुनः असाइन किया जाता है, जिससे संभावित रूप से उस सर्वर का लोड दोगुना हो जाता है। यह वांछनीय नहीं हो सकता. सर्वर विफलता पर बीएलओबी का अधिक समान पुनर्वितरण सुनिश्चित करने के लिए, प्रत्येक सर्वर को यूनिट सर्कल पर कई स्थानों पर हैश किया जा सकता है। जब कोई सर्वर विफल हो जाता है, तो यूनिट सर्कल पर उसके प्रत्येक प्रतिकृति को सौंपे गए बीएलओबी को दक्षिणावर्त क्रम में अलग सर्वर पर पुन: असाइन किया जाएगा, इस प्रकार बीएलओबी को अधिक समान रूप से पुनर्वितरित किया जाएगा। अन्य एक्सटेंशन ऐसी स्थिति से संबंधित है जहां एकल बीएलओबी गर्म हो जाता है और बड़ी संख्या में एक्सेस किया जाता है और उसे कई सर्वरों में होस्ट करना होगा। इस स्थिति में, यूनिट सर्कल को दक्षिणावर्त क्रम में घुमाकर बीएलओबी को कई सन्निहित सर्वरों को सौंपा जा सकता है। अधिक जटिल व्यावहारिक विचार तब उत्पन्न होता है जब दो बीएलओबी यूनिट सर्कल में दूसरे के पास हैश किए जाते हैं और दोनों ही समय में गर्म हो जाते हैं। इस मामले में, दोनों बीएलओबी यूनिट सर्कल में सन्निहित सर्वर के समान सेट का उपयोग करेंगे। प्रत्येक बीएलओबी द्वारा यूनिट सर्कल में सर्वर को मैप करने के लिए अलग हैश फ़ंक्शन चुनने से इस स्थिति में सुधार किया जा सकता है।

मिलन स्थल हैशिंग और अन्य विकल्पों के साथ तुलना

1996 में डिज़ाइन किया गया रेंडेज़वस हैशिंग सरल और अधिक सामान्य तकनीक है, और सेट पर पूरी तरह से वितरित समझौते की अनुमति देता है $k$ संभावित सेट में से विकल्प $n$ विकल्प. रेंडीज़वस हैशिंग#कंसिस्टेंट हैशिंग के साथ तुलना कि लगातार हैशिंग रेंडीज़वस हैशिंग का विशेष मामला है। इसकी सरलता और व्यापकता के कारण, कई अनुप्रयोगों में कंसिस्टेंट हैशिंग के स्थान पर अब मिलनसार हैशिंग का उपयोग किया जा रहा है।

यदि मुख्य मान हमेशा एकरस रूप से बढ़ेंगे, तो हैश टेबल#मोनोटोनिक कुंजियों का उपयोग करने वाला वैकल्पिक तरीका लगातार हैशिंग की तुलना में अधिक उपयुक्त हो सकता है।

जटिलता

Asymptotic time complexities for $N$ nodes (or slots) and $K$ keys

	Classic hash table	Consistent hashing
add a node	$O(K)$	$O(K/N+\log N)$
remove a node	$O(K)$	$O(K/N+\log N)$
add a key	$O(1)$	$O(\log N)$
remove a key	$O(1)$	$O(\log N)$

$O(K/N)$ h> चाबियों के पुनर्वितरण के लिए औसत लागत है और $O(\log N)$ लगातार हैशिंग के लिए जटिलता इस तथ्य से आती है कि रिंग पर अगले नोड को खोजने के लिए नोड्स कोणों के बीच बाइनरी खोज एल्गोरिदम की आवश्यकता होती है।

उदाहरण

लगातार हैशिंग उपयोग के ज्ञात उदाहरणों में शामिल हैं:

• काउचबेस स्वचालित डेटा विभाजन
• ओपनस्टैक|ओपनस्टैक की ऑब्जेक्ट स्टोरेज सर्विस स्विफ्ट
• अमेज़ॅन की भंडारण प्रणाली डायनमो (भंडारण प्रणाली) का विभाजन घटक
• अपाचे कैसेंड्रा में डेटा विभाजन
• वोल्डेमॉर्ट में डेटा विभाजन (वितरित डेटा स्टोर)
• अक्का (टूलकिट) का सुसंगत हैशिंग राउटर
• रिआक, वितरित कुंजी-मूल्य डेटाबेस
• चमकीला , नेटवर्क-अटैच्ड स्टोरेज फ़ाइल सिस्टम
• अकामाई टेक्नोलॉजीज सामग्री वितरण नेटवर्क
• डिस्कॉर्ड (सॉफ़्टवेयर) चैट एप्लिकेशन
• कॉर्ड (पीयर-टू-पीयर) एल्गोरिदम

संदर्भ

• Roughgarden, Tim; Valiant, Gregory (28 March 2021). "The Modern Algorithmic Toolbox, Introduction to Consistent Hashing" (PDF). Stanford University. Archived (PDF) from the original on 25 July 2021. Retrieved 7 October 2021.
• Moitra, Ankur (10 February 2016). "Advanced Algorithms, 6.854" (PDF). Massachusetts Institute of Technology. Archived (PDF) from the original on 13 April 2021. Retrieved 8 October 2021.

बाहरी संबंध

• Understanding Consistent hashing
• Consistent hashing by Michael Nielsen on June 3, 2009
• Consistent Hashing, Danny Lewin, and the Creation of Akamai
• Jump Consistent Hashing: A Fast, Minimal Memory, Consistent Hash Algorithm
• Rendezvous Hashing: an alternative to Consistent Hashing
• Implementations in various languages:
  • C
  • C++
  • C#
  • Erlang
  • Go
  • Java
  • PHP
  • Ruby
  • Python
  • Python (again)
  • Perl
  • Perl6