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

Revision as of 09:37, 19 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$ इस मामले में) उस सर्वर को निर्धारित करने के लिए जिसमें हम 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 को स्थानीय रूप से कैश किया जाता है। पहले उपयोग किए गए कैश सर्वर पर अनावश्यक बीएलओबी कैश प्रतिस्थापन नीतियों के अनुसार हटा दिए जाएंगे।^[9]

कार्यान्वयन

होने देना $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}}$ एस।^[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}}$ एस।^[12]

विचरण में कमी

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

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

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

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

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)$  लगातार हैशिंग के लिए जटिलता इस तथ्य से आती है कि रिंग पर अगले नोड को खोजने के लिए नोड्स कोणों के बीच बाइनरी खोज एल्गोरिदम की आवश्यकता होती है।

उदाहरण

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

काउचबेस स्वचालित डेटा विभाजन ^[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.

बाहरी संबंध

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

[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 4: / Line 4: @@
 ==इतिहास==
-सुसंगत हैशिंग शब्द [[डेविड कार्गर]] एट अल द्वारा प्रस्तुत किया गया था। एमआईटी में [[वितरित कैश]] में उपयोग के लिए, विशेष रूप से [[वर्ल्ड वाइड वेब]] के लिए।{{sfn|Roughgarden|Valiant|2021|p=2}} [[कंप्यूटिंग के सिद्धांत पर संगोष्ठी]] में 1997 के इस अकादमिक पेपर ने वेब सर्वर की बदलती आबादी के बीच अनुरोधों को वितरित करने के एक तरीके के रूप में लगातार हैशिंग शब्द को पेश किया।{{sfn|Roughgarden|Valiant|2021|p=7}} फिर प्रत्येक स्लॉट को एक वितरित सिस्टम या क्लस्टर में एक सर्वर द्वारा दर्शाया जाता है। केवल एक सर्वर को जोड़ने और एक सर्वर को हटाने (स्केलेबिलिटी या आउटेज के दौरान) की आवश्यकता होती है <math>num\_keys/num\_slots</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
   | url = http://portal.acm.org/citation.cfm?id=258660
@@ Line 14: / Line 14: @@
   | 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>
+[[टेराडाटा]] ने 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 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> लगातार हैशिंग वितरित हैश तालिकाओं (डीएचटी) की आधारशिला भी है, जो नोड्स के वितरित सेट में कीस्पेस को विभाजित करने के लिए हैश मानों को नियोजित करती है, फिर कनेक्टेड नोड्स के ओवरले नेटवर्क का निर्माण करती है जो कुंजी द्वारा कुशल नोड पुनर्प्राप्ति प्रदान करती है।
+में डिज़ाइन किया गया [[मिलन स्थल हैशिंग]] सरल और अधिक सामान्य तकनीक है . यह बहुत अलग उच्चतम यादृच्छिक वजन (एचआरडब्ल्यू) एल्गोरिदम का उपयोग करके लगातार हैशिंग के लक्ष्यों को प्राप्त करता है।
-में डिज़ाइन किया गया [[मिलन स्थल हैशिंग]] एक सरल और अधिक सामान्य तकनीक है {{Citation needed|date=April 2021}}. यह बहुत अलग उच्चतम यादृच्छिक वजन (एचआरडब्ल्यू) एल्गोरिदम का उपयोग करके लगातार हैशिंग के लक्ष्यों को प्राप्त करता है।<!-- should describe here why the "consistency" of consistent hashing is essential to DHTs -->
 ==बुनियादी तकनीक==
-[[File:Consistent Hashing Sample Illustration.png|thumb|इस मामले में, लगातार हैशिंग का उपयोग करने से बीएलओबी संग्रहीत सर्वर 139 हो जाएगा। एक बीएलओबी को अगले सर्वर पर मैप किया जाता है जो सर्कल पर दक्षिणावर्त क्रम में दिखाई देता है जब तक कि यह सर्वर तक नहीं पहुंच जाता है <math>\zeta \le \text{server ID}</math>]]लोड संतुलन (कंप्यूटिंग) की समस्या में, उदाहरण के लिए, जब एक [[बाइनरी बड़ी वस्तु]] को इनमें से किसी एक को सौंपा जाना होता है <math>n</math> [[कंप्यूटर क्लस्टर]] पर सर्वर, एक मानक हैश फ़ंक्शन का उपयोग इस तरह से किया जा सकता है कि हम उस बीएलओबी के लिए हैश मान की गणना करते हैं, यह मानते हुए कि हैश का परिणामी मान है <math>\beta</math>, हम सर्वरों की संख्या के साथ मॉड्यूलर अंकगणित करते हैं (<math>n</math> इस मामले में) उस सर्वर को निर्धारित करने के लिए जिसमें हम BLOB रख सकते हैं: <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> इस मामले में) उस सर्वर को निर्धारित करने के लिए जिसमें हम BLOB रख सकते हैं: <math>\zeta = \beta\ \%\ n</math>; इसलिए बीएलओबी को सर्वर में रखा जाएगा <math>\text{server ID}</math> का उत्तराधिकारी है <math>\zeta</math> इस मामले में। हालाँकि, जब किसी सर्वर को आउटेज या स्केलिंग के दौरान जोड़ा या हटाया जाता है (जब <math>n</math> परिवर्तन), हैश टेबल#डायनेमिक आकार बदलने के कारण प्रत्येक सर्वर में सभी बीएलओबी को पुन: असाइन और स्थानांतरित किया जाना चाहिए, लेकिन यह ऑपरेशन महंगा है।
-जब किसी सर्वर को पूरे क्लस्टर में जोड़ा या हटाया जाता है, तो प्रत्येक BLOB को पुन: असाइन करने की समस्या से बचने के लिए लगातार हैशिंग को डिज़ाइन किया गया था। केंद्रीय विचार यह है कि, हम एक हैश फ़ंक्शन का उपयोग करते हैं जो आमतौर पर बीएलओबी और सर्वर दोनों को एक यूनिट सर्कल में यादृच्छिक रूप से मैप करता है <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> क्लस्टर के भीतर सर्वर का मान है) बीएलओबी लगाने के लिए सर्वर को खोजने के लिए किया जाता है। यह सर्वरों को बीएलओबी का समान वितरण प्रदान करता है। लेकिन, अधिक महत्वपूर्ण बात यह है कि यदि कोई सर्वर विफल हो जाता है और सर्कल से हटा दिया जाता है, तो केवल बीएलओबी जो विफल सर्वर पर मैप किए गए थे, उन्हें दक्षिणावर्त क्रम में अगले सर्वर पर पुन: असाइन करने की आवश्यकता होती है। इसी तरह, यदि कोई नया सर्वर जोड़ा जाता है, तो इसे यूनिट सर्कल में जोड़ा जाता है, और केवल उस सर्वर पर मैप किए गए बीएलओबी को पुन: असाइन करने की आवश्यकता होती है।
+जब किसी सर्वर को पूरे क्लस्टर में जोड़ा या हटाया जाता है, तो प्रत्येक BLOB को पुन: असाइन करने की समस्या से बचने के लिए लगातार हैशिंग को डिज़ाइन किया गया था। केंद्रीय विचार यह है कि, हम हैश फ़ंक्शन का उपयोग करते हैं जो आमतौर पर बीएलओबी और सर्वर दोनों को यूनिट सर्कल में यादृच्छिक रूप से मैप करता है <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> स्थानांतरित करने के लिए बीएलओबी का अंश। यद्यपि क्लस्टर में कैश सर्वरों में बीएलओबी को स्थानांतरित करने की प्रक्रिया संदर्भ पर निर्भर करती है, आमतौर पर, नया जोड़ा गया कैश सर्वर अपने उत्तराधिकारी की पहचान करता है और सभी बीएलओबी को स्थानांतरित करता है, जिनकी मैपिंग इस सर्वर से संबंधित है (यानी जिसका हैश मान इससे कम है) नया सर्वर), इससे। हालाँकि, [[वेब कैशिंग]] के मामले में, अधिकांश कार्यान्वयन में कैश्ड बीएलओबी काफी छोटा मानते हुए, इसे स्थानांतरित करने या कॉपी करने की कोई भागीदारी नहीं होती है। जब कोई अनुरोध नए जोड़े गए कैश सर्वर से टकराता है, तो एक कैश (कंप्यूटिंग)#CACHE-MISS होता है और वास्तविक [[वेब सर्वर]] से अनुरोध किया जाता है और भविष्य के अनुरोधों के लिए BLOB को स्थानीय रूप से कैश किया जाता है। पहले उपयोग किए गए कैश सर्वर पर अनावश्यक बीएलओबी कैश प्रतिस्थापन नीतियों के अनुसार हटा दिए जाएंगे।{{sfn|Roughgarden|Valiant|2021|p=6}}
+महत्वपूर्ण रूप से, जब कोई सर्वर जोड़ा या हटाया जाता है, तो अधिकांश बीएलओबी अपने पूर्व सर्वर असाइनमेंट को बनाए रखते हैं, और इसके अतिरिक्त <math>n^{th}</math> सर्वर ही कारण बनता है <math>1/n</math> स्थानांतरित करने के लिए बीएलओबी का अंश। यद्यपि क्लस्टर में कैश सर्वरों में बीएलओबी को स्थानांतरित करने की प्रक्रिया संदर्भ पर निर्भर करती है, आमतौर पर, नया जोड़ा गया कैश सर्वर अपने उत्तराधिकारी की पहचान करता है और सभी बीएलओबी को स्थानांतरित करता है, जिनकी मैपिंग इस सर्वर से संबंधित है (यानी जिसका हैश मान इससे कम है) नया सर्वर), इससे। हालाँकि, [[वेब कैशिंग]] के मामले में, अधिकांश कार्यान्वयन में कैश्ड बीएलओबी काफी छोटा मानते हुए, इसे स्थानांतरित करने या कॉपी करने की कोई भागीदारी नहीं होती है। जब कोई अनुरोध नए जोड़े गए कैश सर्वर से टकराता है, तो कैश (कंप्यूटिंग)#CACHE-MISS होता है और वास्तविक [[वेब सर्वर]] से अनुरोध किया जाता है और भविष्य के अनुरोधों के लिए BLOB को स्थानीय रूप से कैश किया जाता है। पहले उपयोग किए गए कैश सर्वर पर अनावश्यक बीएलओबी कैश प्रतिस्थापन नीतियों के अनुसार हटा दिए जाएंगे।{{sfn|Roughgarden|Valiant|2021|p=6}}
 ===कार्यान्वयन===
-होने देना <math>h_{b}(x)</math> और <math>h_{s}(x)</math> क्रमशः बीएलओबी और सर्वर के विशिष्ट पहचानकर्ता के लिए उपयोग किए जाने वाले हैश फ़ंक्शन हों। व्यवहार में, गतिशील रूप से बनाए रखने के लिए एक [[बाइनरी सर्च ट्री]] (BST) का उपयोग किया जाता है <math>\text{server ID}</math> क्लस्टर या हैशिंग के भीतर, और बीएसटी के भीतर उत्तराधिकारी या न्यूनतम खोजने के लिए, [[ वृक्ष परिभ्रमण ]] का उपयोग किया जाता है।
+होने देना <math>h_{b}(x)</math> और <math>h_{s}(x)</math> क्रमशः बीएलओबी और सर्वर के विशिष्ट पहचानकर्ता के लिए उपयोग किए जाने वाले हैश फ़ंक्शन हों। व्यवहार में, गतिशील रूप से बनाए रखने के लिए [[बाइनरी सर्च ट्री]] (BST) का उपयोग किया जाता है <math>\text{server ID}</math> क्लस्टर या हैशिंग के भीतर, और बीएसटी के भीतर उत्तराधिकारी या न्यूनतम खोजने के लिए, [[ वृक्ष परिभ्रमण |वृक्ष परिभ्रमण]] का उपयोग किया जाता है।
 ;डालना <math>x</math> क्लस्टर में
 :होने देना <math>\beta</math> BLOB का हैश मान इस प्रकार हो कि, <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>एस, बीएलओबी को सबसे छोटे सर्वर में रखा गया है <math>\text{server ID}</math> कीमत।
 ;हटाना <math>x</math> क्लस्टर से
 :के उत्तराधिकारी का पता लगाएं <math>\zeta</math> बीएसटी में, रिटर्न से बीएलओबी हटा दें <math>\text{server ID}</math>. अगर <math>\zeta</math> इसका कोई उत्तराधिकारी नहीं है, सबसे छोटे से बीएलओबी हटा दें <math>\text{server ID}</math>एस।{{sfn|Moitra|2016|p=2}}
-;क्लस्टर में एक सर्वर डालें
+;क्लस्टर में सर्वर डालें
 :होने देना <math>\Phi</math> सर्वर के पहचानकर्ता का हैश मान इस प्रकार हो, <math>h_{s}(x)=\Phi\ \%\ 360</math> कहाँ <math>x \in \{\text{IP address, UUID}\}</math> और <math>h_{s}(x)=\theta</math>. उन सभी बीएलओबी को स्थानांतरित करें, जिनका हैश मान इससे छोटा है <math>\theta</math>, सर्वर से जिसका <math>\text{server ID}</math> का उत्तराधिकारी है <math>\theta</math>. अगर <math>\theta</math> सभी में सबसे बड़ा है <math>\text{server ID}</math>एस, प्रासंगिक बीएलओबी को सबसे छोटे से स्थानांतरित करें <math>\text{server ID}</math>में है <math>\theta</math>.{{sfn|Moitra|2016|p=2–3}}
 ;क्लस्टर से सर्वर हटाएं
@@ Line 40: / Line 41: @@
 ===विचरण में कमी===
-रेडियन के भीतर कई नोड्स की विषमता से बचने के लिए, जो क्लस्टर के भीतर सर्वर के संभाव्यता वितरण में यादृच्छिकता की कमी के कारण होता है, कई लेबल का उपयोग किया जाता है। उन डुप्लिकेट लेबल को वर्चुअल नोड्स कहा जाता है यानी एकाधिक लेबल जो क्लस्टर के भीतर एक वास्तविक लेबल या सर्वर की ओर इशारा करते हैं। क्लस्टर के भीतर किसी विशेष सर्वर के लिए उपयोग किए जाने वाले वर्चुअल नोड्स या डुप्लिकेट लेबल की मात्रा को उस विशेष सर्वर का वजन कहा जाता है।{{sfn|Roughgarden|Valiant|2021|p=6–7}}
+रेडियन के भीतर कई नोड्स की विषमता से बचने के लिए, जो क्लस्टर के भीतर सर्वर के संभाव्यता वितरण में यादृच्छिकता की कमी के कारण होता है, कई लेबल का उपयोग किया जाता है। उन डुप्लिकेट लेबल को वर्चुअल नोड्स कहा जाता है यानी एकाधिक लेबल जो क्लस्टर के भीतर वास्तविक लेबल या सर्वर की ओर इशारा करते हैं। क्लस्टर के भीतर किसी विशेष सर्वर के लिए उपयोग किए जाने वाले वर्चुअल नोड्स या डुप्लिकेट लेबल की मात्रा को उस विशेष सर्वर का वजन कहा जाता है।{{sfn|Roughgarden|Valiant|2021|p=6–7}}
 ==व्यावहारिक विस्तार==
-अभ्यास में लोड संतुलन के लिए लगातार हैशिंग का प्रभावी ढंग से उपयोग करने के लिए बुनियादी तकनीक में कई विस्तार की आवश्यकता है। उपरोक्त मूल योजना में, यदि कोई सर्वर विफल हो जाता है, तो उसके सभी बीएलओबी को दक्षिणावर्त क्रम में अगले सर्वर पर पुनः असाइन किया जाता है, जिससे संभावित रूप से उस सर्वर का लोड दोगुना हो जाता है। यह वांछनीय नहीं हो सकता. सर्वर विफलता पर बीएलओबी का अधिक समान पुनर्वितरण सुनिश्चित करने के लिए, प्रत्येक सर्वर को यूनिट सर्कल पर कई स्थानों पर हैश किया जा सकता है। जब कोई सर्वर विफल हो जाता है, तो यूनिट सर्कल पर उसके प्रत्येक प्रतिकृति को सौंपे गए बीएलओबी को दक्षिणावर्त क्रम में एक अलग सर्वर पर पुन: असाइन किया जाएगा, इस प्रकार बीएलओबी को अधिक समान रूप से पुनर्वितरित किया जाएगा। एक अन्य एक्सटेंशन ऐसी स्थिति से संबंधित है जहां एक एकल बीएलओबी गर्म हो जाता है और बड़ी संख्या में एक्सेस किया जाता है और उसे कई सर्वरों में होस्ट करना होगा। इस स्थिति में, यूनिट सर्कल को दक्षिणावर्त क्रम में घुमाकर बीएलओबी को कई सन्निहित सर्वरों को सौंपा जा सकता है। अधिक जटिल व्यावहारिक विचार तब उत्पन्न होता है जब दो बीएलओबी यूनिट सर्कल में एक दूसरे के पास हैश किए जाते हैं और दोनों एक ही समय में गर्म हो जाते हैं। इस मामले में, दोनों बीएलओबी यूनिट सर्कल में सन्निहित सर्वर के समान सेट का उपयोग करेंगे। प्रत्येक बीएलओबी द्वारा यूनिट सर्कल में सर्वर को मैप करने के लिए एक अलग हैश फ़ंक्शन चुनने से इस स्थिति में सुधार किया जा सकता है।<ref name="nuggets" />
+अभ्यास में लोड संतुलन के लिए लगातार हैशिंग का प्रभावी ढंग से उपयोग करने के लिए बुनियादी तकनीक में कई विस्तार की आवश्यकता है। उपरोक्त मूल योजना में, यदि कोई सर्वर विफल हो जाता है, तो उसके सभी बीएलओबी को दक्षिणावर्त क्रम में अगले सर्वर पर पुनः असाइन किया जाता है, जिससे संभावित रूप से उस सर्वर का लोड दोगुना हो जाता है। यह वांछनीय नहीं हो सकता. सर्वर विफलता पर बीएलओबी का अधिक समान पुनर्वितरण सुनिश्चित करने के लिए, प्रत्येक सर्वर को यूनिट सर्कल पर कई स्थानों पर हैश किया जा सकता है। जब कोई सर्वर विफल हो जाता है, तो यूनिट सर्कल पर उसके प्रत्येक प्रतिकृति को सौंपे गए बीएलओबी को दक्षिणावर्त क्रम में अलग सर्वर पर पुन: असाइन किया जाएगा, इस प्रकार बीएलओबी को अधिक समान रूप से पुनर्वितरित किया जाएगा। अन्य एक्सटेंशन ऐसी स्थिति से संबंधित है जहां एकल बीएलओबी गर्म हो जाता है और बड़ी संख्या में एक्सेस किया जाता है और उसे कई सर्वरों में होस्ट करना होगा। इस स्थिति में, यूनिट सर्कल को दक्षिणावर्त क्रम में घुमाकर बीएलओबी को कई सन्निहित सर्वरों को सौंपा जा सकता है। अधिक जटिल व्यावहारिक विचार तब उत्पन्न होता है जब दो बीएलओबी यूनिट सर्कल में दूसरे के पास हैश किए जाते हैं और दोनों ही समय में गर्म हो जाते हैं। इस मामले में, दोनों बीएलओबी यूनिट सर्कल में सन्निहित सर्वर के समान सेट का उपयोग करेंगे। प्रत्येक बीएलओबी द्वारा यूनिट सर्कल में सर्वर को मैप करने के लिए अलग हैश फ़ंक्शन चुनने से इस स्थिति में सुधार किया जा सकता है।<ref name="nuggets" />
 == मिलन स्थल हैशिंग और अन्य विकल्पों के साथ तुलना ==
-में डिज़ाइन किया गया रेंडेज़वस हैशिंग एक सरल और अधिक सामान्य तकनीक है, और एक सेट पर पूरी तरह से वितरित समझौते की अनुमति देता है <math>k</math> संभावित सेट में से विकल्प <math>n</math> विकल्प. रेंडीज़वस हैशिंग#कंसिस्टेंट हैशिंग के साथ तुलना कि लगातार हैशिंग रेंडीज़वस हैशिंग का एक विशेष मामला है। इसकी सरलता और व्यापकता के कारण, कई अनुप्रयोगों में कंसिस्टेंट हैशिंग के स्थान पर अब मिलनसार हैशिंग का उपयोग किया जा रहा है।
+में डिज़ाइन किया गया रेंडेज़वस हैशिंग सरल और अधिक सामान्य तकनीक है, और सेट पर पूरी तरह से वितरित समझौते की अनुमति देता है <math>k</math> संभावित सेट में से विकल्प <math>n</math> विकल्प. रेंडीज़वस हैशिंग#कंसिस्टेंट हैशिंग के साथ तुलना कि लगातार हैशिंग रेंडीज़वस हैशिंग का विशेष मामला है। इसकी सरलता और व्यापकता के कारण, कई अनुप्रयोगों में कंसिस्टेंट हैशिंग के स्थान पर अब मिलनसार हैशिंग का उपयोग किया जा रहा है।
-यदि मुख्य मान हमेशा [[एकरस]] रूप से बढ़ेंगे, तो हैश टेबल#मोनोटोनिक कुंजियों का उपयोग करने वाला एक वैकल्पिक तरीका लगातार हैशिंग की तुलना में अधिक उपयुक्त हो सकता है।{{citation needed|date=October 2019}}
+यदि मुख्य मान हमेशा [[एकरस]] रूप से बढ़ेंगे, तो हैश टेबल#मोनोटोनिक कुंजियों का उपयोग करने वाला वैकल्पिक तरीका लगातार हैशिंग की तुलना में अधिक उपयुक्त हो सकता है।
 == जटिलता ==
@@ Line 75: / Line 76: @@
 |<math>O(\log N)</math>
 |}
-  <math>O(K/N)</math> h> चाबियों के पुनर्वितरण के लिए एक औसत लागत है और <math>O(\log N)</math> लगातार हैशिंग के लिए जटिलता इस तथ्य से आती है कि रिंग पर अगले नोड को खोजने के लिए नोड्स कोणों के बीच एक बाइनरी खोज एल्गोरिदम की आवश्यकता होती है।{{citation needed|date=October 2019}}
+  <math>O(K/N)</math> h> चाबियों के पुनर्वितरण के लिए औसत लागत है और <math>O(\log N)</math> लगातार हैशिंग के लिए जटिलता इस तथ्य से आती है कि रिंग पर अगले नोड को खोजने के लिए नोड्स कोणों के बीच बाइनरी खोज एल्गोरिदम की आवश्यकता होती है।
 == उदाहरण ==
@@ Line 95: / Line 96: @@
 * वोल्डेमॉर्ट में डेटा विभाजन (वितरित डेटा स्टोर)<ref>{{cite web|title=डिज़ाइन - वोल्डेमॉर्ट|url=http://www.project-voldemort.com/voldemort/design.html|website=www.project-voldemort.com/|accessdate=9 February 2015|archiveurl=https://web.archive.org/web/20150209164650/http://www.project-voldemort.com/voldemort/design.html|archivedate=9 February 2015|quote=Consistent hashing is a technique that avoids these problems, and we use it to compute the location of each key on the cluster.}}</ref>
 * [[अक्का (टूलकिट)]] का सुसंगत हैशिंग राउटर<ref name="akka-routing">{{cite web|url=http://doc.akka.io/docs/akka/snapshot/scala/routing.html|title=अक्का रूटिंग|access-date=2019-11-16|website=akka.io}}</ref>
-* रिआक, एक वितरित कुंजी-मूल्य डेटाबेस<ref name="riak-consistent-hashing">{{cite web|url=http://docs.basho.com/riak/1.4.8/theory/why-riak/|title=तरंग अवधारणाएँ|url-status=dead|access-date=2016-12-06|archive-url=https://web.archive.org/web/20150919042730/http://docs.basho.com/riak/1.4.8/theory/why-riak/|archive-date=2015-09-19}}</ref>
+* रिआक, वितरित कुंजी-मूल्य डेटाबेस<ref name="riak-consistent-hashing">{{cite web|url=http://docs.basho.com/riak/1.4.8/theory/why-riak/|title=तरंग अवधारणाएँ|url-status=dead|access-date=2016-12-06|archive-url=https://web.archive.org/web/20150919042730/http://docs.basho.com/riak/1.4.8/theory/why-riak/|archive-date=2015-09-19}}</ref>
-* [[ चमकीला ]], एक नेटवर्क-अटैच्ड स्टोरेज फ़ाइल सिस्टम<ref name="GlusterFS Algorithms: Distribution">{{cite web|title=GlusterFS Algorithms: Distribution|url=http://www.gluster.org/2012/03/glusterfs-algorithms-distribution/|date=2012-03-01|access-date=2019-11-16|website=gluster.org}}</ref>
+* [[ चमकीला ]], नेटवर्क-अटैच्ड स्टोरेज फ़ाइल सिस्टम<ref name="GlusterFS Algorithms: Distribution">{{cite web|title=GlusterFS Algorithms: Distribution|url=http://www.gluster.org/2012/03/glusterfs-algorithms-distribution/|date=2012-03-01|access-date=2019-11-16|website=gluster.org}}</ref>
 * अकामाई टेक्नोलॉजीज सामग्री वितरण नेटवर्क<ref>{{cite web|url=http://theory.stanford.edu/~tim/s16/l/l1.pdf|title=आधुनिक एल्गोरिथम टूलबॉक्स|access-date=2019-11-17|date=2016-03-28|first1=Tim|first2=Gregory|last2=Valiant|last1=Roughgarden|website=stanford.edu}}</ref>
 * डिस्कॉर्ड (सॉफ़्टवेयर) चैट एप्लिकेशन<ref name="how discord scaled elixir to 5,000,000 concurrent users">{{cite web|url=https://discord.com/blog/how-discord-scaled-elixir-to-5-000-000-concurrent-users|title=How Discord Scaled Elixir to 5,000,000 Concurrent Users|first1=Stanislav|last1=Vishnevskiy|date=2017-07-06|access-date=2022-08-16}}</ref>
@@ Line 120: / Line 121: @@
 == संदर्भ ==
 {{Reflist}}
-{{reflist|group=note}}
 *{{cite web|url=https://web.stanford.edu/class/cs168/l/l1.pdf|first1=Tim|last1=Roughgarden|first2=Gregory|last2=Valiant|publisher=[[Stanford University]]|title=The Modern Algorithmic Toolbox, Introduction to Consistent Hashing|date=28 March 2021|access-date=7 October 2021|archive-url=https://web.archive.org/web/20210725194111/https://web.stanford.edu/class/cs168/l/l1.pdf|archive-date=25 July 2021|url-status=live}}
 *{{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}}
@@ Line 145: / Line 145: @@
 ** [https://github.com/bradclawsie/Hash-Consistent Perl6]
-<!--Interwikies-->
 {{DEFAULTSORT:Consistent hashing}}

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:37, 19 July 2023

Contents

इतिहास

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

कार्यान्वयन

विचरण में कमी

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

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

जटिलता

उदाहरण

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 09:37, 19 July 2023

इतिहास

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

कार्यान्वयन

विचरण में कमी

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

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

जटिलता

उदाहरण

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories