कंसिस्टेंट हैशिंग: Difference between revisions

Latest revision as of 16:13, 25 July 2023

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

इतिहास

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

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

मूलभूत तकनीक

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

\zeta \leq {\text{server ID}}

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

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

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

कार्यान्वयन

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

इन्सर्टिंग $x$ क्लस्टर में: माना $\beta$ ब्लॉब का हैश मान इस प्रकार हो कि, $h_{b}(x)=\beta \ \%\ 360$ जहाँ $x\in \mathrm {BLOB}$ और $h_{b}(x)=\zeta$ . दर्ज करना $x$ , का उत्तराधिकारी सर्चें $\zeta$ के बीएसटी में ${\text{server ID}}$ एस। यदि $\zeta$ सभी से बड़ा है ${\text{server ID}}$ s, बीएलओबी को सबसे छोटे सर्वर में रखा गया है ${\text{server ID}}$ कीमत।
क्लस्टर से $x$ हटाना: $\zeta$ के उत्तराधिकारी का पता लगाएं बीएसटी में, रिटर्न से बीएलओबी हटा दें ${\text{server ID}}$ . यदि $\zeta$ इसका कोई उत्तराधिकारी नहीं है, सबसे छोटे से बीएलओबी हटा दें ${\text{server ID}}$ s है।^[10]
क्लस्टर में सर्वर डालें: माना $\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$ में है .^[11]
क्लस्टर से सर्वर हटाएं: $\theta$ के उत्तराधिकारी का पता लगाएं बीएसटी में, बीएलओबी को यहां से हटाएं $\theta$ इसके उत्तराधिकारी सर्वर में यदि $\theta$ इसका कोई उत्तराधिकारी नहीं है, बीएलओबी को सबसे छोटे में ले जाएं ${\text{server ID}}$ s है।^[12]

विचरण में कमी

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

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

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

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

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

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

समष्टि

असममित समय समष्टि के लिए $N$ नोड्स (या स्लॉट) और $K$ कीज
	क्लासिक हैश टेबल	कंसिस्टेंट हैशिंग
नोड जोड़ें	$O(K)$	$O(K/N+\log N)$
एक नोड हटाएँ	$O(K)$	$O(K/N+\log N)$
एक कीज जोड़ें	$O(1)$	$O(\log N)$
एक कीज हटाएँ	$O(1)$	$O(\log N)$

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

उदाहरण

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

काउचबेस स्वचालित डेटा विभाजन ^[14]
ओपनस्टैक या ओपनस्टैक की ऑब्जेक्ट स्टोरेज सर्विस स्विफ्ट ^[15]
अमेज़ॅन की संग्रहण सिस्टम डायनमो (संग्रहण सिस्टम) का विभाजन घटक ^[16]
अपाचे कैसेंड्रा में डेटा विभाजन ^[17]
वोल्डेमॉर्ट में डेटा विभाजन (वितरित डेटा स्टोर)^[18]
अक्का (टूलकिट) का सुसंगत हैशिंग राउटर ^[19]
रिआक, वितरित कीज-मूल्य डेटाबेस ^[20]
ग्लस्टर , नेटवर्क-अटैच्ड स्टोरेज फ़ाइल सिस्टम ^[21]
अकामाई टेक्नोलॉजीज पदार्थ वितरण नेटवर्क ^[22]
डिस्कॉर्ड (सॉफ़्टवेयर) चैट एप्लिकेशन ^[23]
कॉर्ड (पीयर-टू-पीयर) एल्गोरिदम ^[24]

संदर्भ

↑ ^1.0 ^1.1 Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA. pp. 654–663. doi:10.1145/258533.258660.
↑ ^2.0 ^2.1 ^2.2 Bruce Maggs and Ramesh Sitaraman (2015). "सामग्री वितरण में एल्गोरिथम नगेट्स" (PDF). ACM SIGCOMM Computer Communication Review. 45 (3).
↑ Roughgarden & Valiant 2021, p. 2.
↑ Roughgarden & Valiant 2021, p. 7.
↑ Roughgarden & Valiant 2021, p. 8.
↑ I. Stoica et al., "Chord: a scalable peer-to-peer lookup protocol for Internet applications," in IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 17–32, Feb. 2003, doi: 10.1109/TNET.2002.808407.
↑ Nygren., E.; Sitaraman R. K.; Sun, J. (2010). "The Akamai Network: A Platform for High-Performance Internet Applications" (PDF). ACM SIGOPS Operating Systems Review. 44 (3): 2–19. doi:10.1145/1842733.1842736. S2CID 207181702. Archived (PDF) from the original on September 13, 2012. Retrieved November 19, 2012.
↑ Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). "लगातार हैशिंग के साथ वेब कैशिंग". Computer Networks. 31 (11): 1203–1213. doi:10.1016/S1389-1286(99)00055-9. Archived from the original on 2008-07-21. Retrieved 2008-02-05.
↑ Roughgarden & Valiant 2021, p. 6.
↑ Moitra 2016, p. 2.
↑ Moitra 2016, p. 2–3.
↑ Moitra 2016, p. 3.
↑ Roughgarden & Valiant 2021, p. 6–7.
↑ "What Exactly Is Membase?". Retrieved 2020-10-29.
↑ Holt, Greg (February 2011). "एक सुसंगत हैशिंग रिंग का निर्माण". openstack.org. Retrieved 2019-11-17.
↑ DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, Werner (2007). "Dynamo: Amazon's Highly Available Key-Value Store" (PDF). Proceedings of the 21st ACM Symposium on Operating Systems Principles. 41 (6): 205–220. doi:10.1145/1323293.1294281. Retrieved 2018-06-07.
↑ Lakshman, Avinash; Malik, Prashant (2010). "Cassandra: a decentralized structured storage system". ACM SIGOPS Operating Systems Review. 44 (2): 35–40. doi:10.1145/1773912.1773922.
↑ "डिज़ाइन - वोल्डेमॉर्ट". www.project-voldemort.com/. Archived from the original on 9 February 2015. Retrieved 9 February 2015. Consistent hashing is a technique that avoids these problems, and we use it to compute the location of each key on the cluster.
↑ "अक्का रूटिंग". akka.io. Retrieved 2019-11-16.
↑ "तरंग अवधारणाएँ". Archived from the original on 2015-09-19. Retrieved 2016-12-06.
↑ "GlusterFS Algorithms: Distribution". gluster.org. 2012-03-01. Retrieved 2019-11-16.
↑ Roughgarden, Tim; Valiant, Gregory (2016-03-28). "आधुनिक एल्गोरिथम टूलबॉक्स" (PDF). stanford.edu. Retrieved 2019-11-17.
↑ Vishnevskiy, Stanislav (2017-07-06). "How Discord Scaled Elixir to 5,000,000 Concurrent Users". Retrieved 2022-08-16.
↑ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (25 Feb 2003). "Chord: a scalable peer-to-peer lookup protocol for Internet applications". IEEE/ACM Transactions on Networking. 11 (1): 17–32. doi:10.1109/TNET.2002.808407.

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.

बाहरी संबंध

[KargerEtAl1997-1] 1.0 ^1.1 Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA. pp. 654–663. doi:10.1145/258533.258660.

[nuggets-2] 2.0 ^2.1 ^2.2 Bruce Maggs and Ramesh Sitaraman (2015). "सामग्री वितरण में एल्गोरिथम नगेट्स" (PDF). ACM SIGCOMM Computer Communication Review. 45 (3).

[FOOTNOTERoughgardenValiant20212-3] Roughgarden & Valiant 2021, p. 2.

[FOOTNOTERoughgardenValiant20217-4] Roughgarden & Valiant 2021, p. 7.

[FOOTNOTERoughgardenValiant20218-5] Roughgarden & Valiant 2021, p. 8.

[6] I. Stoica et al., "Chord: a scalable peer-to-peer lookup protocol for Internet applications," in IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 17–32, Feb. 2003, doi: 10.1109/TNET.2002.808407.

[7] Nygren., E.; Sitaraman R. K.; Sun, J. (2010). "The Akamai Network: A Platform for High-Performance Internet Applications" (PDF). ACM SIGOPS Operating Systems Review. 44 (3): 2–19. doi:10.1145/1842733.1842736. S2CID 207181702. Archived (PDF) from the original on September 13, 2012. Retrieved November 19, 2012.

[KargerEtAl1999-8] Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). "लगातार हैशिंग के साथ वेब कैशिंग". Computer Networks. 31 (11): 1203–1213. doi:10.1016/S1389-1286(99)00055-9. Archived from the original on 2008-07-21. Retrieved 2008-02-05.

[FOOTNOTERoughgardenValiant20216-9] Roughgarden & Valiant 2021, p. 6.

[FOOTNOTEMoitra20162-10] Moitra 2016, p. 2.

[FOOTNOTEMoitra20162–3-11] Moitra 2016, p. 2–3.

[FOOTNOTEMoitra20163-12] Moitra 2016, p. 3.

[FOOTNOTERoughgardenValiant20216–7-13] Roughgarden & Valiant 2021, p. 6–7.

[14] "What Exactly Is Membase?". Retrieved 2020-10-29.

[15] Holt, Greg (February 2011). "एक सुसंगत हैशिंग रिंग का निर्माण". openstack.org. Retrieved 2019-11-17.

[Amazon2007-16] DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, Werner (2007). "Dynamo: Amazon's Highly Available Key-Value Store" (PDF). Proceedings of the 21st ACM Symposium on Operating Systems Principles. 41 (6): 205–220. doi:10.1145/1323293.1294281. Retrieved 2018-06-07.

[Lakshman2010b-17] Lakshman, Avinash; Malik, Prashant (2010). "Cassandra: a decentralized structured storage system". ACM SIGOPS Operating Systems Review. 44 (2): 35–40. doi:10.1145/1773912.1773922.

[18] "डिज़ाइन - वोल्डेमॉर्ट". www.project-voldemort.com/. Archived from the original on 9 February 2015. Retrieved 9 February 2015. Consistent hashing is a technique that avoids these problems, and we use it to compute the location of each key on the cluster.

[akka-routing-19] "अक्का रूटिंग". akka.io. Retrieved 2019-11-16.

[riak-consistent-hashing-20] "तरंग अवधारणाएँ". Archived from the original on 2015-09-19. Retrieved 2016-12-06.

[GlusterFS_Algorithms:_Distribution-21] "GlusterFS Algorithms: Distribution". gluster.org. 2012-03-01. Retrieved 2019-11-16.

[22] Roughgarden, Tim; Valiant, Gregory (2016-03-28). "आधुनिक एल्गोरिथम टूलबॉक्स" (PDF). stanford.edu. Retrieved 2019-11-17.

[how_discord_scaled_elixir_to_5,000,000_concurrent_users-23] Vishnevskiy, Stanislav (2017-07-06). "How Discord Scaled Elixir to 5,000,000 Concurrent Users". Retrieved 2022-08-16.

[ChordTON2003-24] Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (25 Feb 2003). "Chord: a scalable peer-to-peer lookup protocol for Internet applications". IEEE/ACM Transactions on Networking. 11 (1): 17–32. doi:10.1109/TNET.2002.808407.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

@@ Line 1: / Line 1: @@
 {{Short description|Hashing technique}}
-[[कंप्यूटर विज्ञान]] में, '''निरंतर हैशिंग''' <ref name="KargerEtAl1997" /><ref name="nuggets" /> एक विशेष प्रकार की [[हैश फंकशन]] तकनीक है जैसे कि जब [[हैश तालिका]] का आकार बदला जाता है इस प्रकार <math>n/m</math> कीज को औसतन पुनः मैप करने की आवश्यकता है इस प्रकार <math>n</math> कीज की संख्या है और <math>m</math> स्लॉट की संख्या है. इसके विपरीत, अधिकांश पारंपरिक हैश तालिकाओं में, सरणी स्लॉट की संख्या में बदलाव के कारण लगभग सभी कीज को फिर से मैप करना पड़ता है क्योंकि कीज और स्लॉट्स के बीच मैपिंग को [[मॉड्यूलर अंकगणित]] द्वारा परिभाषित किया जाता है।
+[[कंप्यूटर विज्ञान]] में, '''कंसिस्टेंट हैशिंग''' <ref name="KargerEtAl1997" /><ref name="nuggets" /> एक विशेष प्रकार की [[हैश फंकशन]] तकनीक है जैसे कि जब [[हैश तालिका|हैश टेबल]] का आकार बदला जाता है इस प्रकार <math>n/m</math> कीज को औसतन पुनः मैप करने की आवश्यकता है इस प्रकार <math>n</math> कीज की संख्या है और <math>m</math> स्लॉट की संख्या है. इसके विपरीत, अधिकांश पारंपरिक हैश टेबलओं में, सरणी स्लॉट की संख्या में बदलाव के कारण लगभग सभी कीज को फिर से मैप करना पड़ता है क्योंकि कीज और स्लॉट्स के बीच मैपिंग को [[मॉड्यूलर अंकगणित]] द्वारा परिभाषित किया जाता है।
 ==इतिहास==
-सुसंगत हैशिंग शब्द [[डेविड कार्गर]] एट अल द्वारा प्रस्तुत किया गया था। एमआईटी में [[वितरित कैश]] में उपयोग के लिए, विशेष रूप से [[वर्ल्ड वाइड वेब]] के लिए।{{sfn|Roughgarden|Valiant|2021|p=2}} [[कंप्यूटिंग के सिद्धांत पर संगोष्ठी]] में 1997 के इस अकादमिक पेपर ने वेब सर्वर की बदलती जनसंख्या के बीच अनुरोधों को वितरित करने के विधि के रूप में निरंतर हैशिंग शब्द को प्रस्तुत किया था।{{sfn|Roughgarden|Valiant|2021|p=7}} फिर प्रत्येक स्लॉट को वितरित सिस्टम या क्लस्टर में सर्वर द्वारा दर्शाया जाता है। केवल सर्वर को जोड़ने और सर्वर को हटाने (स्केलेबिलिटी या आउटेज के समय) की आवश्यकता होती है इस प्रकार <math>num\_keys/num\_slots</math> स्लॉट की संख्या (अर्थात सर्वर) बदलने पर आइटमों को फिर से फेरबदल किया जाना चाहिए। लेखक [[रैखिक हैशिंग]] और अनुक्रमिक सर्वर जोड़ और निष्कासन को संभालने की इसकी क्षमता का उल्लेख करते हैं, जबकि निरंतर हैशिंग सर्वर को इच्छानुसार क्रम में जोड़ने और हटाने की अनुमति देता है। <ref name="KargerEtAl1997">{{cite conference
+सुसंगत हैशिंग शब्द [[डेविड कार्गर]] एट अल द्वारा प्रस्तुत किया गया था। एमआईटी में [[वितरित कैश]] में उपयोग के लिए, विशेष रूप से [[वर्ल्ड वाइड वेब]] के लिए।{{sfn|Roughgarden|Valiant|2021|p=2}} [[कंप्यूटिंग के सिद्धांत पर संगोष्ठी]] में 1997 के इस अकादमिक पेपर ने वेब सर्वर की बदलती जनसंख्या के बीच अनुरोधों को वितरित करने के विधि के रूप में कंसिस्टेंट हैशिंग शब्द को प्रस्तुत किया था।{{sfn|Roughgarden|Valiant|2021|p=7}} फिर प्रत्येक स्लॉट को वितरित सिस्टम या क्लस्टर में सर्वर द्वारा दर्शाया जाता है। केवल सर्वर को जोड़ने और सर्वर को हटाने (स्केलेबिलिटी या आउटेज के समय) की आवश्यकता होती है इस प्रकार <math>num\_keys/num\_slots</math> स्लॉट की संख्या (अर्थात सर्वर) बदलने पर आइटमों को फिर से फेरबदल किया जाना चाहिए। लेखक [[रैखिक हैशिंग]] और अनुक्रमिक सर्वर जोड़ और निष्कासन को संभालने की इसकी क्षमता का उल्लेख करते हैं, जबकि कंसिस्टेंट हैशिंग सर्वर को इच्छानुसार क्रम में जोड़ने और हटाने की अनुमति देता है। <ref name="KargerEtAl1997">{{cite conference
   | url = http://portal.acm.org/citation.cfm?id=258660
   | doi = 10.1145/258533.258660
@@ Line 12: / Line 12: @@
   | publisher = ACM Press New York, NY, USA
   | title = Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
-}}</ref> [[वितरित हैश तालिका]] जैसे पीयर-टू-पीयर या पीयर-टू-पीयर नेटवर्क में फ़ाइल का ट्रैक रखने की तकनीकी चुनौती को संबोधित करने के लिए बाद में पेपर को फिर से तैयार किया गया था।{{sfn|Roughgarden|Valiant|2021|p=8}}<ref>I. Stoica et al., "Chord: a scalable peer-to-peer lookup protocol for Internet applications," in IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 17–32, Feb. 2003, doi: 10.1109/TNET.2002.808407.</ref> [[टेराडाटा]] ने 1986 में जारी अपने वितरित डेटाबेस में इस तकनीक का उपयोग किया था, चूँकि उन्होंने इस शब्द का उपयोग नहीं किया था। ठीक इसी उद्देश्य को पूरा करने के लिए टेराडेटा अभी भी हैश तालिका की अवधारणा का उपयोग करता है। [[ स्मार्ट टेक्नोलॉजीज |स्मार्ट टेक्नोलॉजीज]] की स्थापना 1998 में वैज्ञानिक [[डेनियल लेविन]] और एफ. थॉमसन लीटन (कंसिस्टेंट हैशिंग गढ़ने वाले लेख के सह-लेखक) द्वारा की गई थी। अकामाई के पदार्थ वितरण नेटवर्क में,<ref>{{cite journal |author1=Nygren., E. |author2=Sitaraman R. K. |author3=Sun, J. |title=The Akamai Network: A Platform for High-Performance Internet Applications |journal=ACM SIGOPS Operating Systems Review |volume=44 |issue=3 |year=2010 |pages=2–19 |doi=10.1145/1842733.1842736 |s2cid=207181702 |url=http://www.akamai.com/dl/technical_publications/network_overview_osr.pdf |accessdate=November 19, 2012 |archive-url=https://web.archive.org/web/20120913205810/http://www.akamai.com/dl/technical_publications/network_overview_osr.pdf |archive-date=September 13, 2012 |url-status=live }}</ref> निरंतर हैशिंग का उपयोग सर्वर के क्लस्टर के अन्दर लोड को संतुलित करने के लिए किया जाता है, जबकि [[स्थिर विवाह समस्या|वितरित हैश टेबल]] एल्गोरिदम का उपयोग क्लस्टर में लोड को संतुलित करने के लिए किया जाता है।<ref name=nuggets>{{cite journal | author=  Bruce Maggs and [[Ramesh Sitaraman]] | title = सामग्री वितरण में एल्गोरिथम नगेट्स| journal= ACM SIGCOMM Computer Communication Review |year=2015|volume=45|issue=3|url = http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf}}</ref> इस प्रकार बड़े वेब अनुप्रयोगों में आंशिक सिस्टम विफलताओं के प्रभाव को कम करने के लिए निरंतर हैशिंग का भी उपयोग किया गया है जिससे सिस्टम-व्यापी विफलता के बिना सशक्त कैशिंग प्रदान की जा सकता है।<ref name=KargerEtAl1999>{{cite journal |url=http://www8.org/w8-papers/2a-webserver/caching/paper2.html |doi=10.1016/S1389-1286(99)00055-9 |author1=Karger, D. |author2=Sherman, A. |author3=Berkheimer, A. |author4=Bogstad, B. |author5=Dhanidina, R. |author6=Iwamoto, K. |author7=Kim, B. |author8=Matkins, L. |author9=Yerushalmi, Y. |journal=Computer Networks |volume=31 |issue=11 |pages=1203–1213 |year=1999 |title=लगातार हैशिंग के साथ वेब कैशिंग|access-date=2008-02-05 |archive-url=https://web.archive.org/web/20080721013638/http://www8.org/w8-papers/2a-webserver/caching/paper2.html |archive-date=2008-07-21 |url-status=dead }}</ref> निरंतर हैशिंग वितरित हैश तालिकाओं (डीएचटी) की आधारशिला भी है, जो नोड्स के वितरित सेट में कीस्पेस को विभाजित करने के लिए हैश मानों को नियोजित करती है, फिर कनेक्टेड नोड्स के ओवरले नेटवर्क का निर्माण करती है जो कीज द्वारा कुशल नोड पुनर्प्राप्ति प्रदान करती है।
+}}</ref> वितरित हैश टेबल जैसे पीयर-टू-पीयर या पीयर-टू-पीयर नेटवर्क में फ़ाइल का ट्रैक रखने की तकनीकी चुनौती को संबोधित करने के लिए बाद में पेपर को फिर से तैयार किया गया था।{{sfn|Roughgarden|Valiant|2021|p=8}}<ref>I. Stoica et al., "Chord: a scalable peer-to-peer lookup protocol for Internet applications," in IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 17–32, Feb. 2003, doi: 10.1109/TNET.2002.808407.</ref> [[टेराडाटा]] ने 1986 में जारी अपने वितरित डेटाबेस में इस तकनीक का उपयोग किया था, चूँकि उन्होंने इस शब्द का उपयोग नहीं किया था। ठीक इसी उद्देश्य को पूरा करने के लिए टेराडेटा अभी भी हैश टेबल की अवधारणा का उपयोग करता है। [[ स्मार्ट टेक्नोलॉजीज |स्मार्ट टेक्नोलॉजीज]] की स्थापना 1998 में वैज्ञानिक [[डेनियल लेविन]] और एफ. थॉमसन लीटन (कंसिस्टेंट हैशिंग गढ़ने वाले लेख के सह-लेखक) द्वारा की गई थी। अकामाई के पदार्थ वितरण नेटवर्क में,<ref>{{cite journal |author1=Nygren., E. |author2=Sitaraman R. K. |author3=Sun, J. |title=The Akamai Network: A Platform for High-Performance Internet Applications |journal=ACM SIGOPS Operating Systems Review |volume=44 |issue=3 |year=2010 |pages=2–19 |doi=10.1145/1842733.1842736 |s2cid=207181702 |url=http://www.akamai.com/dl/technical_publications/network_overview_osr.pdf |accessdate=November 19, 2012 |archive-url=https://web.archive.org/web/20120913205810/http://www.akamai.com/dl/technical_publications/network_overview_osr.pdf |archive-date=September 13, 2012 |url-status=live }}</ref> कंसिस्टेंट हैशिंग का उपयोग सर्वर के क्लस्टर के अन्दर लोड को संतुलित करने के लिए किया जाता है, जबकि [[स्थिर विवाह समस्या|वितरित हैश टेबल]] एल्गोरिदम का उपयोग क्लस्टर में लोड को संतुलित करने के लिए किया जाता है।<ref name=nuggets>{{cite journal | author=  Bruce Maggs and [[Ramesh Sitaraman]] | title = सामग्री वितरण में एल्गोरिथम नगेट्स| journal= ACM SIGCOMM Computer Communication Review |year=2015|volume=45|issue=3|url = http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf}}</ref> इस प्रकार बड़े वेब अनुप्रयोगों में आंशिक सिस्टम विफलताओं के प्रभाव को कम करने के लिए कंसिस्टेंट हैशिंग का भी उपयोग किया गया है जिससे सिस्टम-व्यापी विफलता के बिना सशक्त कैशिंग प्रदान की जा सकता है।<ref name=KargerEtAl1999>{{cite journal |url=http://www8.org/w8-papers/2a-webserver/caching/paper2.html |doi=10.1016/S1389-1286(99)00055-9 |author1=Karger, D. |author2=Sherman, A. |author3=Berkheimer, A. |author4=Bogstad, B. |author5=Dhanidina, R. |author6=Iwamoto, K. |author7=Kim, B. |author8=Matkins, L. |author9=Yerushalmi, Y. |journal=Computer Networks |volume=31 |issue=11 |pages=1203–1213 |year=1999 |title=लगातार हैशिंग के साथ वेब कैशिंग|access-date=2008-02-05 |archive-url=https://web.archive.org/web/20080721013638/http://www8.org/w8-papers/2a-webserver/caching/paper2.html |archive-date=2008-07-21 |url-status=dead }}</ref> कंसिस्टेंट हैशिंग वितरित हैश टेबलओं (डीएचटी) की आधारशिला भी है, जो नोड्स के वितरित सेट में कीस्पेस को विभाजित करने के लिए हैश मानों को नियोजित करती है, फिर कनेक्टेड नोड्स के ओवरले नेटवर्क का निर्माण करती है जो कीज द्वारा कुशल नोड पुनर्प्राप्ति प्रदान करती है।
-में डिज़ाइन किया गया [[मिलन स्थल हैशिंग|रेनडेज़वस हैशिंग]] सरल और अधिक सामान्य तकनीक है यह बहुत अलग उच्चतम यादृच्छिक वजन (एचआरडब्ल्यू) एल्गोरिदम का उपयोग करके निरंतर हैशिंग के लक्ष्यों को प्राप्त करता है।
+में डिज़ाइन किया गया [[मिलन स्थल हैशिंग|रेनडेज़वस हैशिंग]] सरल और अधिक सामान्य तकनीक है यह बहुत अलग उच्चतम यादृच्छिक वजन (एचआरडब्ल्यू) एल्गोरिदम का उपयोग करके कंसिस्टेंट हैशिंग के लक्ष्यों को प्राप्त करता है।
 ==मूलभूत तकनीक==
-[[File:Consistent Hashing Sample Illustration.png|thumb|इस स्थिति में, निरंतर हैशिंग का उपयोग करने से बीएलओबी संग्रहीत सर्वर 139 हो जाएगा। बीएलओबी को अगले सर्वर पर मैप किया जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है जब तक कि यह सर्वर तक नहीं पहुंच जाता है <math>\zeta \le \text{server ID}</math>]]लोड संतुलन (कंप्यूटिंग) की समस्या में, उदाहरण के लिए, जब [[बाइनरी बड़ी वस्तु|बाइनरी]] को इनमें से किसी <math>n</math> [[कंप्यूटर क्लस्टर]] पर सर्वर को नियुक्त जाना होता है, मानक हैश फ़ंक्शन का उपयोग इस तरह से किया जा सकता है कि हम उस बीएलओबी के लिए हैश मान की गणना करते हैं, यह मानते हुए कि हैश का परिणामी <math>\beta</math> मान है , हम सर्वरों की संख्या के साथ मॉड्यूलर अंकगणित करते हैं (<math>n</math> इस स्थिति में) उस सर्वर को निर्धारित करने के लिए जिसमें हम <math>\zeta = \beta\ \%\ n</math> ब्लॉब रख सकते हैं: इसलिए बीएलओबी को सर्वर में रखा जाएगा <math>\text{server ID}</math> का उत्तराधिकारी है इस स्थिति में <math>\zeta</math> चूँकि, जब किसी सर्वर को आउटेज या स्केलिंग के समय जोड़ा या हटाया जाता है (जब <math>n</math> परिवर्तन), हैश टेबल डायनेमिक आकार बदलने के कारण प्रत्येक सर्वर में सभी बीएलओबी को पुन: असाइन और स्थानांतरित किया जाना चाहिए, किन्तु यह ऑपरेशन महंगा है।
+[[File:Consistent Hashing Sample Illustration.png|thumb|इस स्थिति में, कंसिस्टेंट हैशिंग का उपयोग करने से बीएलओबी संग्रहीत सर्वर 139 हो जाएगा। बीएलओबी को अगले सर्वर पर मैप किया जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है जब तक कि यह सर्वर तक नहीं पहुंच जाता है <math>\zeta \le \text{server ID}</math>]]लोड संतुलन (कंप्यूटिंग) की समस्या में, उदाहरण के लिए, जब [[बाइनरी बड़ी वस्तु|बाइनरी]] को इनमें से किसी <math>n</math> [[कंप्यूटर क्लस्टर]] पर सर्वर को नियुक्त जाना होता है, मानक हैश फ़ंक्शन का उपयोग इस तरह से किया जा सकता है कि हम उस बीएलओबी के लिए हैश मान की गणना करते हैं, यह मानते हुए कि हैश का परिणामी <math>\beta</math> मान है , हम सर्वरों की संख्या के साथ मॉड्यूलर अंकगणित करते हैं (<math>n</math> इस स्थिति में) उस सर्वर को निर्धारित करने के लिए जिसमें हम <math>\zeta = \beta\ \%\ n</math> ब्लॉब रख सकते हैं: इसलिए बीएलओबी को सर्वर में रखा जाएगा <math>\text{server ID}</math> का उत्तराधिकारी है इस स्थिति में <math>\zeta</math> चूँकि, जब किसी सर्वर को आउटेज या स्केलिंग के समय जोड़ा या हटाया जाता है (जब <math>n</math> परिवर्तन), हैश टेबल डायनेमिक आकार बदलने के कारण प्रत्येक सर्वर में सभी बीएलओबी को पुन: असाइन और स्थानांतरित किया जाना चाहिए, किन्तु यह ऑपरेशन महंगा है।
-जब किसी सर्वर को पूरे क्लस्टर में जोड़ा या हटाया जाता है, जिससे प्रत्येक ब्लॉब को पुन: असाइन करने की समस्या से बचने के लिए निरंतर हैशिंग को डिज़ाइन किया गया था। केंद्रीय विचार यह है कि, हम हैश फ़ंक्शन का उपयोग करते हैं जो सामान्यतः बीएलओबी और सर्वर दोनों को यूनिट सर्कल में यादृच्छिक <math>2\pi</math> रेडियंस. रूप से मैप करता है उदाहरण के लिए, <math>\zeta = \Phi\ \%\ 360</math> (जहाँ <math>\Phi</math> बीएलओबी या सर्वर के पहचानकर्ता का हैश है, जैसे आईपी पता या [[सार्वभौमिक रूप से अद्वितीय पहचानकर्ता]])। फिर प्रत्येक बीएलओबी को अगले सर्वर को नियुक्त जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है। सामान्यतः, [[बाइनरी खोज एल्गोरिदम]] या [[रैखिक खोज]] का उपयोग उस विशेष बीएलओबी को रखने के लिए किसी स्थान या सर्वर को खोजने के लिए किया जाता है इस प्रकार <math>O(\log N)</math> या <math>O(N)</math> क्रमशः समष्टिएँ; और प्रत्येक पुनरावृत्ति में, जो दक्षिणावर्त विधि से होता है, ऑपरेशन <math>\zeta\ \le\ \Psi</math> (जहाँ <math>\Psi</math> क्लस्टर के अन्दर सर्वर का मान है) बीएलओबी लगाने के लिए सर्वर को खोजने के लिए किया जाता है। यह सर्वरों को बीएलओबी का समान वितरण प्रदान करता है। किन्तु, अधिक महत्वपूर्ण बात यह है कि यदि कोई सर्वर विफल हो जाता है और सर्कल से हटा दिया जाता है, तो केवल बीएलओबी जो विफल सर्वर पर मैप किए गए थे, उन्हें दक्षिणावर्त क्रम में अगले सर्वर पर पुन: असाइन करने की आवश्यकता होती है। इसी तरह, यदि कोई नया सर्वर जोड़ा जाता है, जिससे इसे यूनिट सर्कल में जोड़ा जाता है, और केवल उस सर्वर पर मैप किए गए बीएलओबी को पुन: असाइन करने की आवश्यकता होती है।
+जब किसी सर्वर को पूरे क्लस्टर में जोड़ा या हटाया जाता है, जिससे प्रत्येक ब्लॉब को पुन: असाइन करने की समस्या से बचने के लिए कंसिस्टेंट हैशिंग को डिज़ाइन किया गया था। केंद्रीय विचार यह है कि, हम हैश फ़ंक्शन का उपयोग करते हैं जो सामान्यतः बीएलओबी और सर्वर दोनों को यूनिट सर्कल में यादृच्छिक <math>2\pi</math> रेडियंस. रूप से मैप करता है उदाहरण के लिए, <math>\zeta = \Phi\ \%\ 360</math> (जहाँ <math>\Phi</math> बीएलओबी या सर्वर के पहचानकर्ता का हैश है, जैसे आईपी पता या सार्वभौमिक रूप से अद्वितीय पहचानकर्ता)। फिर प्रत्येक बीएलओबी को अगले सर्वर को नियुक्त जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है। सामान्यतः, [[बाइनरी खोज एल्गोरिदम|बाइनरी सर्च एल्गोरिदम]] या [[रैखिक खोज|रैखिक सर्च]] का उपयोग उस विशेष बीएलओबी को रखने के लिए किसी स्थान या सर्वर को सर्चने के लिए किया जाता है इस प्रकार <math>O(\log N)</math> या <math>O(N)</math> क्रमशः समष्टिएँ; और प्रत्येक पुनरावृत्ति में, जो दक्षिणावर्त विधि से होता है, ऑपरेशन <math>\zeta\ \le\ \Psi</math> (जहाँ <math>\Psi</math> क्लस्टर के अन्दर सर्वर का मान है) बीएलओबी लगाने के लिए सर्वर को सर्चने के लिए किया जाता है। यह सर्वरों को बीएलओबी का समान वितरण प्रदान करता है। किन्तु, अधिक महत्वपूर्ण बात यह है कि यदि कोई सर्वर विफल हो जाता है और सर्कल से हटा दिया जाता है, तो केवल बीएलओबी जो विफल सर्वर पर मैप किए गए थे, उन्हें दक्षिणावर्त क्रम में अगले सर्वर पर पुन: असाइन करने की आवश्यकता होती है। इसी तरह, यदि कोई नया सर्वर जोड़ा जाता है, जिससे इसे यूनिट सर्कल में जोड़ा जाता है, और केवल उस सर्वर पर मैप किए गए बीएलओबी को पुन: असाइन करने की आवश्यकता होती है।
 महत्वपूर्ण रूप से, जब कोई सर्वर जोड़ा या हटाया जाता है, जिससे अधिकांश बीएलओबी अपने पूर्व सर्वर असाइनमेंट को बनाए रखते हैं, और इसके अतिरिक्त <math>n^{th}</math> सर्वर ही कारण बनता है इस प्रकार <math>1/n</math> स्थानांतरित करने के लिए बीएलओबी का अंश यद्यपि क्लस्टर में कैश सर्वरों में बीएलओबी को स्थानांतरित करने की प्रक्रिया संदर्भ पर निर्भर करती है, सामान्यतः, नया जोड़ा गया कैश सर्वर अपने उत्तराधिकारी की पहचान करता है और सभी बीएलओबी को स्थानांतरित करता है, जिनकी मैपिंग इस सर्वर से संबंधित है (अर्थात जिसका हैश मान इससे कम है) नया सर्वर), इससे चूँकि, [[वेब कैशिंग]] के स्थिति में, अधिकांश कार्यान्वयन में कैश्ड बीएलओबी अधिक छोटा मानते हुए, इसे स्थानांतरित करने या कॉपी करने की कोई भागीदारी नहीं होती है। जब कोई अनुरोध नए जोड़े गए कैश सर्वर से कोलिसन करता है, जिससे कैश (कंप्यूटिंग) कैश-मिस होता है और वास्तविक [[वेब सर्वर]] से अनुरोध किया जाता है और भविष्य के अनुरोधों के लिए ब्लॉब को स्थानीय रूप से कैश किया जाता है। पहले उपयोग किए गए कैश सर्वर पर अनावश्यक बीएलओबी कैश प्रतिस्थापन नीतियों के अनुसार हटा दिए जाते है।{{sfn|Roughgarden|Valiant|2021|p=6}}
 ===कार्यान्वयन===
-माना <math>h_{b}(x)</math> और <math>h_{s}(x)</math> क्रमशः बीएलओबी और सर्वर के विशिष्ट पहचानकर्ता के लिए उपयोग किए जाने वाले हैश फ़ंक्शन होंता है। व्यवहार में, गतिशील रूप से बनाए रखने के लिए [[बाइनरी सर्च ट्री]] (बीएसटी) का उपयोग किया जाता है इस प्रकार <math>\text{server ID}</math> क्लस्टर या हैशिंग के अन्दर, और बीएसटी के अन्दर उत्तराधिकारी या न्यूनतम खोजने के लिए, [[ वृक्ष परिभ्रमण |ट्री परिभ्रमण]] का उपयोग किया जाता है।
+माना <math>h_{b}(x)</math> और <math>h_{s}(x)</math> क्रमशः बीएलओबी और सर्वर के विशिष्ट पहचानकर्ता के लिए उपयोग किए जाने वाले हैश फ़ंक्शन होंता है। व्यवहार में, गतिशील रूप से बनाए रखने के लिए [[बाइनरी सर्च ट्री]] (बीएसटी) का उपयोग किया जाता है इस प्रकार <math>\text{server ID}</math> क्लस्टर या हैशिंग के अन्दर, और बीएसटी के अन्दर उत्तराधिकारी या न्यूनतम सर्चने के लिए, [[ वृक्ष परिभ्रमण |ट्री परिभ्रमण]] का उपयोग किया जाता है।
 ;इन्सर्टिंग <math>x</math> क्लस्टर में
-:माना <math>\beta</math> ब्लॉब का हैश मान इस प्रकार हो कि, <math>h_{b}(x)=\beta\ \%\ 360</math> जहाँ <math>x \in \mathrm{BLOB}</math> और <math>h_{b}(x)=\zeta</math>. दर्ज करना <math>x</math>, का उत्तराधिकारी खोजें <math>\zeta</math> के बीएसटी में <math>\text{server ID}</math>एस। यदि <math>\zeta</math> सभी से बड़ा है <math>\text{server ID}</math> s, बीएलओबी को सबसे छोटे सर्वर में रखा गया है <math>\text{server ID}</math> कीमत।
+:माना <math>\beta</math> ब्लॉब का हैश मान इस प्रकार हो कि, <math>h_{b}(x)=\beta\ \%\ 360</math> जहाँ <math>x \in \mathrm{BLOB}</math> और <math>h_{b}(x)=\zeta</math>. दर्ज करना <math>x</math>, का उत्तराधिकारी सर्चें <math>\zeta</math> के बीएसटी में <math>\text{server ID}</math>एस। यदि <math>\zeta</math> सभी से बड़ा है <math>\text{server ID}</math> s, बीएलओबी को सबसे छोटे सर्वर में रखा गया है <math>\text{server ID}</math> कीमत।
 ;क्लस्टर से <math>x</math> हटाना
 :<math>\zeta</math> के उत्तराधिकारी का पता लगाएं बीएसटी में, रिटर्न से बीएलओबी हटा दें <math>\text{server ID}</math>. यदि <math>\zeta</math> इसका कोई उत्तराधिकारी नहीं है, सबसे छोटे से बीएलओबी हटा दें <math>\text{server ID}</math>s है।{{sfn|Moitra|2016|p=2}}
@@ Line 39: / Line 39: @@
 ==व्यावहारिक विस्तार                                                                                                                                                                                                                                                                                 ==
-अभ्यास में लोड संतुलन के लिए निरंतर हैशिंग का प्रभावी विधि से उपयोग करने के लिए मूलभूत तकनीक में कई विस्तार की आवश्यकता है। उपरोक्त मूल योजना में, यदि कोई सर्वर विफल हो जाता है, उसके सभी बीएलओबी को दक्षिणावर्त क्रम में अगले सर्वर पर पुनः असाइन किया जाता है, जिससे संभावित रूप से उस सर्वर का लोड दोगुना हो जाता है। यह वांछनीय नहीं हो सकता. सर्वर विफलता पर बीएलओबी का अधिक समान पुनर्वितरण सुनिश्चित करने के लिए, प्रत्येक सर्वर को यूनिट सर्कल पर कई स्थानों पर हैश किया जा सकता है। जब कोई सर्वर विफल हो जाता है, जिससे यूनिट सर्कल पर उसके प्रत्येक प्रतिकृति को दिए गए बीएलओबी को दक्षिणावर्त क्रम में अलग सर्वर पर पुन: असाइन किया जाएगा, इस प्रकार बीएलओबी को अधिक समान रूप से पुनर्वितरित किया जाता है। अन्य एक्सटेंशन ऐसी स्थिति से संबंधित है जहां एकल बीएलओबी गर्म हो जाता है और बड़ी संख्या में एक्सेस किया जाता है और उसे कई सर्वरों में होस्ट करना होता है। इस स्थिति में, यूनिट सर्कल को दक्षिणावर्त क्रम में घुमाकर बीएलओबी को कई सन्निहित सर्वरों को नियुक्त जा सकता है। अधिक जटिल व्यावहारिक विचार तब उत्पन्न होता है जब दो बीएलओबी यूनिट सर्कल में दूसरे के पास हैश किए जाते हैं और दोनों ही समय में गर्म हो जाते हैं। इस स्थिति में, दोनों बीएलओबी यूनिट सर्कल में सन्निहित सर्वर के समान सेट का उपयोग करते है। प्रत्येक बीएलओबी द्वारा यूनिट सर्कल में सर्वर को मैप करने के लिए अलग हैश फ़ंक्शन चुनने से इस स्थिति में सुधार किया जा सकता है।<ref name="nuggets" />
+अभ्यास में लोड संतुलन के लिए कंसिस्टेंट हैशिंग का प्रभावी विधि से उपयोग करने के लिए मूलभूत तकनीक में कई विस्तार की आवश्यकता है। उपरोक्त मूल योजना में, यदि कोई सर्वर विफल हो जाता है, उसके सभी बीएलओबी को दक्षिणावर्त क्रम में अगले सर्वर पर पुनः असाइन किया जाता है, जिससे संभावित रूप से उस सर्वर का लोड दोगुना हो जाता है। यह वांछनीय नहीं हो सकता. सर्वर विफलता पर बीएलओबी का अधिक समान पुनर्वितरण सुनिश्चित करने के लिए, प्रत्येक सर्वर को यूनिट सर्कल पर कई स्थानों पर हैश किया जा सकता है। जब कोई सर्वर विफल हो जाता है, जिससे यूनिट सर्कल पर उसके प्रत्येक प्रतिकृति को दिए गए बीएलओबी को दक्षिणावर्त क्रम में अलग सर्वर पर पुन: असाइन किया जाएगा, इस प्रकार बीएलओबी को अधिक समान रूप से पुनर्वितरित किया जाता है। अन्य एक्सटेंशन ऐसी स्थिति से संबंधित है जहां एकल बीएलओबी गर्म हो जाता है और बड़ी संख्या में एक्सेस किया जाता है और उसे कई सर्वरों में होस्ट करना होता है। इस स्थिति में, यूनिट सर्कल को दक्षिणावर्त क्रम में घुमाकर बीएलओबी को कई सन्निहित सर्वरों को नियुक्त जा सकता है। अधिक जटिल व्यावहारिक विचार तब उत्पन्न होता है जब दो बीएलओबी यूनिट सर्कल में दूसरे के पास हैश किए जाते हैं और दोनों ही समय में गर्म हो जाते हैं। इस स्थिति में, दोनों बीएलओबी यूनिट सर्कल में सन्निहित सर्वर के समान सेट का उपयोग करते है। प्रत्येक बीएलओबी द्वारा यूनिट सर्कल में सर्वर को मैप करने के लिए अलग हैश फ़ंक्शन चुनने से इस स्थिति में सुधार किया जा सकता है।<ref name="nuggets" />
 == रेनडेज़वस हैशिंग और अन्य विकल्पों के साथ तुलना ==
-में डिज़ाइन किया गया रेंडेज़वस हैशिंग सरल और अधिक सामान्य तकनीक है, और सेट पर पूरी तरह से वितरित समझौते की अनुमति देता है इस प्रकार <math>k</math> संभावित सेट में से विकल्प <math>n</math> विकल्प. रेंडीज़वस हैशिंग कंसिस्टेंट हैशिंग के साथ तुलना कि निरंतर हैशिंग रेंडीज़वस हैशिंग का विशेष स्थिति है। इसकी सरलता और व्यापकता के कारण, कई अनुप्रयोगों में कंसिस्टेंट हैशिंग के स्थान पर अब मिलनसार हैशिंग का उपयोग किया जा रहा है।
+में डिज़ाइन किया गया रेंडेज़वस हैशिंग सरल और अधिक सामान्य तकनीक है, और सेट पर पूरी तरह से वितरित समझौते की अनुमति देता है इस प्रकार <math>k</math> संभावित सेट में से विकल्प <math>n</math> विकल्प. रेंडीज़वस हैशिंग कंसिस्टेंट हैशिंग के साथ तुलना कि कंसिस्टेंट हैशिंग रेंडीज़वस हैशिंग का विशेष स्थिति है। इसकी सरलता और व्यापकता के कारण, कई अनुप्रयोगों में कंसिस्टेंट हैशिंग के स्थान पर अब मिलनसार हैशिंग का उपयोग किया जा रहा है।
-यदि मुख्य मान सदैव [[एकरस]] रूप से बढ़ेंगे, तो हैश टेबल मोनोटोनिक कीज का उपयोग करने वाला वैकल्पिक विधि निरंतर हैशिंग की तुलना में अधिक उपयुक्त हो सकता है।
+यदि मुख्य मान सदैव [[एकरस]] रूप से बढ़ेंगे, तो हैश टेबल मोनोटोनिक कीज का उपयोग करने वाला वैकल्पिक विधि कंसिस्टेंट हैशिंग की तुलना में अधिक उपयुक्त हो सकता है।
 == समष्टि ==
@@ Line 50: / Line 50: @@
 !
 !क्लासिक हैश टेबल
-!निरंतर हैशिंग
+!कंसिस्टेंट हैशिंग
 |-
 |नोड जोड़ें
@@ Line 68: / Line 68: @@
 |<math>O(\log N)</math>
 |}
-सी प्रकार <math>O(K/N)</math> h> कीज के पुनर्वितरण के लिए औसत निवेश है और <math>O(\log N)</math> निरंतर हैशिंग के लिए समष्टि इस तथ्य से आती है कि रिंग पर अगले नोड को खोजने के लिए नोड्स कोणों के बीच बाइनरी खोज एल्गोरिदम की आवश्यकता होती है।
+सी प्रकार <math>O(K/N)</math> h> कीज के पुनर्वितरण के लिए औसत निवेश है और <math>O(\log N)</math> कंसिस्टेंट हैशिंग के लिए समष्टि इस तथ्य से आती है कि रिंग पर अगले नोड को सर्चने के लिए नोड्स कोणों के बीच बाइनरी सर्च एल्गोरिदम की आवश्यकता होती है।
 == उदाहरण  ==
-निरंतर हैशिंग उपयोग के ज्ञात उदाहरणों में सम्मिलित हैं:
+कंसिस्टेंट हैशिंग उपयोग के ज्ञात उदाहरणों में सम्मिलित हैं:
 * [[काउचबेस]] स्वचालित डेटा विभाजन <ref>{{cite web|url=https://blog.couchbase.com/what-exactly-membase/|title=What Exactly Is Membase?|accessdate=2020-10-29}}</ref>
 * ओपनस्टैक या ओपनस्टैक की ऑब्जेक्ट स्टोरेज सर्विस स्विफ्ट <ref>{{cite web|url=https://docs.openstack.org/swift/latest/ring_background.html|title=एक सुसंगत हैशिंग रिंग का निर्माण|date=February 2011| access-date=2019-11-17| website=openstack.org| first1=Greg|last1=Holt}}</ref>
@@ Line 114: / Line 114: @@
 *{{cite web|url=https://people.csail.mit.edu/moitra/docs/6854lec3.pdf|publisher=[[Massachusetts Institute of Technology]]| first=Ankur|last=Moitra|date=10 February 2016|title=Advanced Algorithms, 6.854|archive-url=https://web.archive.org/web/20210413045612/http://people.csail.mit.edu/moitra/docs/6854lec3.pdf|archive-date=13 April 2021|url-status=live|access-date=8 October 2021}}
 == बाहरी संबंध ==
-* [https://web.archive.org/web/20110721203235/http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/ Understanding निरंतर हैशिंग]
+* [https://web.archive.org/web/20110721203235/http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/ Understanding कंसिस्टेंट हैशिंग]
-* [http://michaelnielsen.org/blog/consistent-hashing निरंतर हैशिंग by Michael Nielsen on June 3, 2009]
+* [http://michaelnielsen.org/blog/consistent-hashing कंसिस्टेंट हैशिंग by Michael Nielsen on June 3, 2009]
-* [https://www.youtube.com/watch?v=apHAqUG3Pi8 निरंतर हैशिंग, Danny Lewin, and the Creation of Akamai]
+* [https://www.youtube.com/watch?v=apHAqUG3Pi8 कंसिस्टेंट हैशिंग, Danny Lewin, and the Creation of Akamai]
-* [[arxiv:1406.2294|Jump निरंतर हैशिंग: A Fast, Minimal Memory, Consistent Hash Algorithm]]
+* [[arxiv:1406.2294|Jump कंसिस्टेंट हैशिंग: A Fast, Minimal Memory, Consistent Hash Algorithm]]
-* [https://medium.com/i0exception/rendezvous-hashing-8c00e2fb58b0 Rendezvous Hashing: an alternative to निरंतर हैशिंग]
+* [https://medium.com/i0exception/rendezvous-hashing-8c00e2fb58b0 Rendezvous Hashing: an alternative to कंसिस्टेंट हैशिंग]
 * Implementations in various languages:
 ** [https://github.com/chrismoos/hash-ring C]
@@ Line 133: / Line 133: @@
 ** [https://github.com/bradclawsie/Hash-Consistent Perl6]
 {{DEFAULTSORT:Consistent hashing}}
-[[Category: हैशिंग]]
+[[Category:Created On 11/07/2023|Consistent hashing]]
+[[Category:Lua-based templates|Consistent hashing]]
-[[Category: Machine Translated Page]]
+[[Category:Machine Translated Page|Consistent hashing]]
-[[Category:Created On 11/07/2023]]
+[[Category:Pages with script errors|Consistent hashing]]
+[[Category:Templates Vigyan Ready|Consistent hashing]]
+[[Category:Templates that add a tracking category|Consistent hashing]]
+[[Category:Templates that generate short descriptions|Consistent hashing]]
+[[Category:Templates using TemplateData|Consistent hashing]]
+[[Category:हैशिंग|Consistent hashing]]

Anonymous

Search

कंसिस्टेंट हैशिंग: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:13, 25 July 2023

Contents

इतिहास

मूलभूत तकनीक

कार्यान्वयन

विचरण में कमी

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

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

समष्टि

उदाहरण

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

कंसिस्टेंट हैशिंग: Difference between revisions

Latest revision as of 16:13, 25 July 2023

इतिहास

मूलभूत तकनीक

कार्यान्वयन

विचरण में कमी

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

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

समष्टि

उदाहरण

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories