डिस्ट्रिब्यूटेड हैश टेबल

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

चूंकि डीएचटी मूलभूत रूप से इसे बनाते हैं जिसका उपयोग अधिक समष्टि सेवाओं के निर्माण के लिए किया जा सकता है, जैसे एनीकास्ट, सहकारी वेब कैशिंग, वितरित फ़ाइल सिस्टम, डोमेन नाम प्रणाली, त्वरित संदेश, बहुस्त्र्पीय , और पीयर-टू-पीयर फ़ाइल साझाकरण और सामग्री वितरण प्रणाली भी। डीएचटी का उपयोग करने वाले उल्लेखनीय वितरित नेटवर्क में बिटटोरेंट (प्रोटोकॉल) का वितरित ट्रैकर, स्टॉर्म नेटवर्क, टॉक्स इंस्टेंट मैसेंजर, फ़्रीनेट, (प्रोटोकॉल), YaCy सर्च इंजन और इंटरप्लेनेटरी फ़ाइल सिस्टम सम्मिलित हैं। इस प्रकार से होलोचेन एक परियोजना है जिसका लक्ष्य घरेलू कंप्यूटर डीएचटी होस्टिंग प्रदान करना है।

वितरित हैश तालिका

इतिहास

डीएचटी अनुसंधान मूल रूप से, आंशिक रूप से, फ़्रीनेट, ग्नुटेला, बिटटोरेंट और नैप्स्टर जैसे पीयर-टू-पीयर (पी2पी) सिस्टम द्वारा प्रेरित था, जिसने एकल उपयोगी एप्लिकेशन प्रदान करने के लिए इंटरनेट पर वितरित संसाधनों का लाभ उठाया है । विशेष रूप से, उन्होंने फ़ाइल-साझाकरण सेवा प्रदान करने के लिए बढ़ी हुई बैंडविड्थ (कंप्यूटिंग) और हार्ड डिस्क क्षमता का लाभ उठाया है ।^[2]

इस प्रकार की प्रणालियाँ इस तथ्य में भिन्न थीं कि वे अपने सहकर्मी द्वारा उपयोग किए गए डेटा का पता कैसे लगाते हैं। और नैप्स्टर, पहले उच्च माप की पी2पी सामग्री वितरण प्रणाली, को केंद्रीय सूचकांक सर्वर की आवश्यकता होती है: इस प्रकार से प्रत्येक नोड, सम्मिलित होने पर, स्थानीय रूप से रखी गई फ़ाइलों की सूची सर्वर को भेजता है , जो खोज करके और प्रश्नों को उन नोड्स को संदर्भित करता है जो इसे धारण करते हैं। अर्थात परिणाम यह है, की केंद्रीय घटक ने सिस्टम को अटैक और स्तिथियों के प्रति संवेदनशील बना दिया है ।

किन्तु गुटेला और इसी प्रकार के नेटवर्क क्वेरी फ्लडिंग मॉडल में चले गए – संक्षेप में, प्रत्येक खोज के परिणामस्वरूप नेटवर्क में हर दूसरी मशीन पर संदेश प्रसारित की जाती है । और विफलता के बिंदु से बचते हुए, यह विधि नैप्स्टर की तुलना में अधिक कम कुशल थी। गुटेला क्लाइंट के पश्चात्के संस्करण गतिशील क्वेरी मॉडल में चले गए जिससे दक्षता में अधिक सुधार किया गया है ।^[3]

फ़्रीनेट पूर्ण रूप से वितरित है, किन्तु ह्यूरिस्टिक (कंप्यूटर विज्ञान) कुंजी-आधारित रूटिंग को नियोजित करता है जिसमें प्रत्येक फ़ाइल कुंजी से जुड़ी होती है, और समान कुंजी वाली फ़ाइलें नोड्स के समान सेट पर क्लस्टर होती हैं। अनेक सहकर्मी से मिलने की आवश्यकता के बिना प्रश्नों को नेटवर्क के माध्यम से ऐसे क्लस्टर में भेजे जाने की संभावना है।^[4] चूंकि , फ़्रीनेट ने यह प्रमाण नहीं दिया कि डेटा पुनः प्राप्त होगा।

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

2001 में, चार सिस्टम- सामग्री पतायोग्य नेटवर्क ,^[6] कॉर्ड (पीयर-टू-पीयर),^[7] पेस्ट्री (डीएचटी), और [[टेपेस्ट्री (डीएचटी)]]डीएचटी) - ने डीएचटी को लोकप्रिय शोध विषय के रूप में प्रज्वलित किया।

इंफ्रास्ट्रक्चर फॉर रेजिलिएंट इंटरनेट सिस्टम्स (आइरिस) नामक परियोजना को 2002 में यूनाइटेड स्टेट्स राष्ट्रीय विज्ञान संस्था से 12 मिलियन डॉलर के अनुदान द्वारा वित्त पोषित किया गया था।^[8]

शोधकर्ताओं में सिल्विया रत्नासामी, आयन स्टोइका, बालकृष्णन दिवस और स्कॉट शेन्कर सम्मिलित थे।^[9]

शिक्षा जगत के बाहर, डीएचटी तकनीक को बिटटोरेंट और कोरल कंटेंट डिस्ट्रीब्यूशन नेटवर्क के घटक के रूप में अपनाया गया है।

गुण

डीएचटी विशेष रूप से निम्नलिखित गुणों पर जोर देते हैं:

विकेंद्रीकृत कंप्यूटिंग: नोड्स बिना किसी केंद्रीय समन्वय के सामूहिक रूप से सिस्टम बनाते हैं।
दोष सहनशीलता: नोड्स के लगातार जुड़ने, छोड़ने और विफल होने पर भी सिस्टम विश्वसनीय (कुछ अर्थों में) होना चाहिए।^[10]
स्केल (कंप्यूटिंग): सिस्टम को हजारों या लाखों नोड्स के साथ भी कुशलतापूर्वक कार्य करना चाहिए।

इन लक्ष्यों को प्राप्त करने के लिए उपयोग की जाने वाली प्रमुख तकनीक यह है कि किसी भी नोड को सिस्टम में केवल कुछ अन्य नोड्स के साथ समन्वय करने की आवश्यकता होती है - आमतौर पर, एन प्रतिभागियों के बिग ओ अंकन (लॉग एन) (नीचे देखें) - ताकि केवल सीमित नोड हो सदस्यता में प्रत्येक परिवर्तन के लिए कितना कार्य करने की आवश्यकता है।

कुछ डीएचटी डिज़ाइन दुर्भावनापूर्ण प्रतिभागियों के विरुद्ध सुरक्षित संचार चाहते हैं^[11] और प्रतिभागियों को गुमनाम रहने की अनुमति देना, हालांकि यह कई अन्य पीयर-टू-पीयर (विशेष रूप से फ़ाइल साझाकरण) प्रणालियों की तुलना में कम आम है; अनाम पी2पी देखें।

संरचना

डीएचटी की संरचना को कई मुख्य घटकों में विघटित किया जा सकता है।^[12]^[13] आधार अमूर्त कीस्पेस (वितरित डेटा स्टोर) है, जैसे कि 160-बिट स्ट्रिंग (कंप्यूटर विज्ञान) का सेट। कीस्पेस विभाजन (डेटाबेस) योजना इस कीस्पेस के स्वामित्व को भाग लेने वाले नोड्स के मध्य विभाजित करती है। ओवरले नेटवर्क तब नोड्स को जोड़ता है, जिससे उन्हें कीस्पेस में किसी भी कुंजी के मालिक को ढूंढने की अनुमति मिलती है।

बार ये घटक स्थापित हो जाएं, तो भंडारण और पुनर्प्राप्ति के लिए डीएचटी का सामान्य उपयोग निम्नानुसार आगे बढ़ सकता है। मान लीजिए कि कीस्पेस 160-बिट स्ट्रिंग्स का सेट है। किसी फ़ाइल को दिए गए के साथ अनुक्रमित करने के लिए filename और $data$ डीएचटी में, SHA-1 हैश $filename$ 160-बिट कुंजी उत्पन्न करते हुए उत्पन्न होता है $k$ , और संदेश $put (k, data)$ डीएचटी में भाग लेने वाले किसी भी नोड को भेजा जाता है। संदेश को ओवरले नेटवर्क के माध्यम से नोड से नोड तक अग्रेषित किया जाता है जब तक कि यह कुंजी के लिए जिम्मेदार ल नोड तक नहीं पहुंच जाता $k$ जैसा कि कीस्पेस विभाजन द्वारा निर्दिष्ट किया गया है। वह नोड फिर कुंजी और डेटा संग्रहीत करता है। कोई अन्य क्लाइंट फिर से हैशिंग द्वारा फ़ाइल की सामग्री को पुनः प्राप्त कर सकता है $filename$ उत्पन्न करना $k$ और किसी भी डीएचटी नोड से संबद्ध डेटा ढूंढने के लिए कहना $k$ संदेश के साथ $get (k)$ . संदेश को फिर से ओवरले के माध्यम से जिम्मेदार नोड तक भेजा जाएगा $k$ , जो संग्रहीत के साथ उत्तर देगा $data$ .

अधिकांश डीएचटी के लिए सामान्य प्रमुख विचारों को पकड़ने के लक्ष्य के साथ कीस्पेस विभाजन और ओवरले नेटवर्क घटकों का वर्णन नीचे किया गया है; कई डिज़ाइन विवरण में भिन्न होते हैं।

कीस्पेस विभाजन

अधिकांश डीएचटी नोड्स की कुंजियों को मैप करने के लिए सुसंगत हैशिंग या मिलनसार हैशिंग के कुछ प्रकार का उपयोग करते हैं। ऐसा प्रतीत होता है कि वितरित हैश तालिका समस्या को हल करने के लिए दो एल्गोरिदम स्वतंत्र रूप से और साथ तैयार किए गए हैं।

सुसंगत हैशिंग और मिलन स्थल हैशिंग दोनों में आवश्यक संपत्ति है कि नोड को हटाने या जोड़ने से निकटवर्ती आईडी वाले नोड्स के स्वामित्व वाली चाबियों का सेट बदल जाता है, और अन्य सभी नोड्स अप्रभावित रह जाते हैं। इसकी तुलना पारंपरिक हैश तालिका से करें जिसमें बकेट को जोड़ने या हटाने से लगभग पूरे कीस्पेस को फिर से मैप किया जाता है। चूंकि स्वामित्व में कोई भी परिवर्तन आम तौर पर डीएचटी में संग्रहीत वस्तुओं के नोड से दूसरे नोड तक बैंडविड्थ-गहन आंदोलन से मेल खाता है, इसलिए मंथन दर (नोड आगमन और विफलता) की उच्च दरों का कुशलतापूर्वक समर्थन करने के लिए ऐसे पुनर्गठन को कम करना आवश्यक है।

लगातार हैशिंग

लगातार हैशिंग फ़ंक्शन को नियोजित करती है $\delta (k_{1},k_{2})$ यह कुंजियों के मध्य की दूरी की अमूर्त धारणा को परिभाषित करता है $k_{1}$ और $k_{2}$ , जो भौगोलिक दूरी या नेटवर्क विलंबता से असंबंधित है। प्रत्येक नोड को कुंजी सौंपी जाती है जिसे उसका पहचानकर्ता (आईडी) कहा जाता है। आईडी के साथ नोड $i_{x}$ सभी चाबियों का स्वामी है $k_{m}$ जिसके लिए $i_{x}$ निकटतम आईडी है, जिसके अनुसार मापा जाता है $\delta (k_{m},i_{x})$ .

उदाहरण के लिए, कॉर्ड (पीयर-टू-पीयर) लगातार हैशिंग का उपयोग करता है, जो नोड्स को सर्कल पर बिंदुओं के रूप में मानता है, और $\delta (k_{1},k_{2})$ वृत्त के चारों ओर दक्षिणावर्त यात्रा करने वाली दूरी है $k_{1}$ को $k_{2}$ . इस प्रकार, वृत्ताकार कुंजीस्थान सन्निहित खंडों में विभाजित हो जाता है जिनके समापन बिंदु नोड पहचानकर्ता होते हैं। अगर $i_{1}$ और $i_{2}$ दो आसन्न आईडी हैं, जिनकी दक्षिणावर्त दूरी कम है $i_{1}$ को $i_{2}$ , फिर आईडी वाला नोड $i_{2}$ मध्य में पड़ने वाली सभी कुंजियों का स्वामी है $i_{1}$ और $i_{2}$ .

मिलन स्थल हैशिंग

मिलन स्थल हैशिंग में, जिसे उच्चतम यादृच्छिक वजन (एचआरडब्ल्यू) हैशिंग भी कहा जाता है, सभी क्लाइंट समान हैश फ़ंक्शन का उपयोग करते हैं $h()$ (समय से पहले चुना गया) किसी कुंजी को उपलब्ध सर्वरों में से किसी से संबद्ध करने के लिए। प्रत्येक ग्राहक के पास पहचानकर्ताओं की समान सूची होती है ${S 1, S 2, ..., S n}$ , प्रत्येक सर्वर के लिए । कुछ कुंजी k दिए जाने पर, ग्राहक n हैश भार की गणना करता है $w 1 = h (S 1, k), w 2 = h (S 2, k), ..., w n = h (S n, k)$ . क्लाइंट उस कुंजी को उस कुंजी के उच्चतम हैश भार के अनुरूप सर्वर के साथ जोड़ता है। आईडी वाला सर्वर $S_{x}$ सभी चाबियों का स्वामी है $k_{m}$ जिसके लिए हैश वजन $h(S_{x},k_{m})$ उस कुंजी के लिए किसी अन्य नोड के हैश भार से अधिक है।

स्थानीयता-संरक्षण हैशिंग

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

ओवरले नेटवर्क

प्रत्येक नोड अन्य नोड्स (इसके पड़ोसी या रूटिंग तालिका) के लिए आंकड़ा कड़ी का सेट बनाए रखता है। ये लिंक मिलकर ओवरले नेटवर्क बनाते हैं।^[16] नोड अपने पड़ोसियों को निश्चित संरचना के अनुसार चुनता है, जिसे नेटवर्क टोपोलॉजी|नेटवर्क की टोपोलॉजी कहा जाता है।

सभी डीएचटी टोपोलॉजी सबसे आवश्यक संपत्ति के कुछ प्रकार साझा करते हैं: किसी भी कुंजी के लिए $k$ , प्रत्येक नोड के पास या तो नोड आईडी होती है जिसका स्वामी होता है $k$ या उस नोड का लिंक है जिसकी नोड आईडी करीब है $k$ , ऊपर परिभाषित कीस्पेस दूरी के संदर्भ में। फिर किसी भी कुंजी के स्वामी को संदेश भेजना आसान हो जाता है $k$ निम्नलिखित लालची एल्गोरिदम का उपयोग करना (जो आवश्यक रूप से विश्व स्तर पर इष्टतम नहीं है): प्रत्येक चरण पर, उस पड़ोसी को संदेश अग्रेषित करें जिसकी आईडी निकटतम है $k$ . जब ऐसा कोई पड़ोसी नहीं है, तो हम निकटतम नोड पर पहुंच गए होंगे, जिसका मालिक है $k$ जैसा कि ऊपर परिभाषित किया गया है। रूटिंग की इस शैली को कभी-कभी कुंजी-आधारित रूटिंग भी कहा जाता है।

मूलभूत रूटिंग शुद्धता से परे, टोपोलॉजी पर दो महत्वपूर्ण बाधाएं यह गारंटी देना है कि किसी भी रूट (रूट लंबाई) में हॉप (नेटवर्किंग) की अधिकतम संख्या कम है, ताकि अनुरोध जल्दी से पूरा हो जाए; और किसी भी नोड के पड़ोसियों की अधिकतम संख्या (अधिकतम नोड डिग्री (ग्राफ सिद्धांत)) कम है, ताकि रखरखाव ओवरहेड अत्यधिक न हो। बेशक, छोटे मार्गों के लिए उच्च अधिकतम डिग्री की आवश्यकता होती है। अधिकतम डिग्री और मार्ग की लंबाई के लिए कुछ सामान्य विकल्प इस प्रकार हैं, जहां $n$ बिग ओ नोटेशन का उपयोग करते हुए डीएचटी में नोड्स की संख्या है:

Max. degree	Max route length	Used in	Note
$O(1)$	$O(n)$		Worst lookup lengths, with likely much slower lookups times
$O(1)$	$O(\log n)$	Koorde (with constant degree)	More complex to implement, but acceptable lookup time can be found with a fixed number of connections
$O(\log n)$	$O(\log n)$	Chord Kademlia Pastry Tapestry	Most common, but not optimal (degree/route length). Chord is the most basic version, with Kademlia seeming the most popular optimized variant (should have improved average lookup)
$O(\log n)$	$O(\log n/\log(\log n))$	Koorde (with optimal lookup)	More complex to implement, but lookups might be faster (have a lower worst case bound)
$O({\sqrt {n}})$	$O(1)$		Worst local storage needs, with much communication after any node connects or disconnects

सबसे आम विकल्प, $O(\log n)$ डिग्री/रूट लंबाई, डिग्री/रूट लंबाई ट्रेडऑफ़ के संदर्भ में इष्टतम नहीं है, किन्तु ऐसी टोपोलॉजी आमतौर पर पड़ोसियों की पसंद में अधिक लचीलेपन की अनुमति देती है। कई डीएचटी उस लचीलेपन का उपयोग उन पड़ोसियों को चुनने के लिए करते हैं जो भौतिक अंतर्निहित नेटवर्क में विलंबता के मामले में करीब हैं। सामान्य तौर पर, सभी डीएचटी नौगम्य लघु-विश्व नेटवर्क टोपोलॉजी का निर्माण करते हैं, जो मार्ग की लंबाई बनाम नेटवर्क डिग्री का व्यापार करते हैं।^[17]

अधिकतम मार्ग की लंबाई व्यास (ग्राफ़ सिद्धांत) से निकटता से संबंधित है: नोड्स के मध्य किसी भी सबसे छोटे पथ में हॉप्स की अधिकतम संख्या। स्पष्ट रूप से, नेटवर्क की सबसे खराब स्थिति में मार्ग की लंबाई कम से कम उसके व्यास जितनी बड़ी है, इसलिए डीएचटी डिग्री/व्यास ट्रेडऑफ़ द्वारा सीमित हैं^[18] यह ग्राफ़ सिद्धांत में मौलिक है। मार्ग की लंबाई व्यास से अधिक हो सकती है, क्योंकि लालची रूटिंग एल्गोरिदम सबसे छोटा पथ नहीं ढूंढ सकता है।^[19]

ओवरले नेटवर्क के लिए एल्गोरिदम

रूटिंग के अलावा, ऐसे कई एल्गोरिदम मौजूद हैं जो डीएचटी में सभी नोड्स, या नोड्स के सबसेट को संदेश भेजने के लिए ओवरले नेटवर्क की संरचना का फायदा उठाते हैं।^[20] इन एल्गोरिदम का उपयोग अनुप्रयोगों द्वारा ओवरले मल्टीकास्ट, रेंज क्वेरीज़ या आंकड़े त्र करने के लिए किया जाता है। इस दृष्टिकोण पर आधारित दो प्रणालियाँ हैं स्ट्रक्चरेला,^[21] जो पेस्ट्री ओवरले पर फ्लडिंग और यादृच्छिक चाल को लागू करता है, और डीक्यू-डीएचटी, जो कॉर्ड नेटवर्क पर गतिशील क्वेरी खोज एल्गोरिदम को लागू करता है।^[22]

सुरक्षा

डीएचटी के विकेंद्रीकरण, दोष सहनशीलता और मापनीयता के कारण, वे केंद्रीकृत प्रणाली की तुलना में शत्रुतापूर्ण हमलावर के खिलाफ स्वाभाविक रूप से अधिक लचीले होते हैं।

वितरित डेटा भंडारण के लिए खुली प्रणालियाँ जो उच्च माप पर शत्रुतापूर्ण हमलावरों के खिलाफ मजबूत हों, संभव हैं।^[23]

डीएचटी प्रणाली जिसे बीजान्टिन दोष सहनशीलता के लिए सावधानीपूर्वक डिज़ाइन किया गया है, सुरक्षा कमजोरी से बचाव कर सकती है, जिसे सिबिल हमले के रूप में जाना जाता है, जो अधिकांश मौजूदा डीएचटी डिज़ाइनों को प्रभावित करता है।^[24]^[25] व्हानाउ डीएचटी है जिसे सिबिल अटैक के प्रति प्रतिरोधी बनाने के लिए डिज़ाइन किया गया है।^[26]

कैडेमलिया के मूल लेखकों में से , पेटार मेमौनकोव ने सिस्टम डिज़ाइन में सामाजिक विश्वास संबंधों को सम्मिलित करके सिबिल हमले की कमजोरी को दूर करने का तरीका प्रस्तावित किया है।^[27] नई प्रणाली, जिसका कोडनेम टोनिका है या जिसे इसके डोमेन नाम 5ttt के नाम से भी जाना जाता है, एल्गोरिदम डिज़ाइन पर आधारित है जिसे इलेक्ट्रिक रूटिंग के रूप में जाना जाता है और गणितज्ञ जोनाथन केल्नर के साथ सह-लेखक है।^[28] मेमौनकोव ने अब इस नई प्रणाली का व्यापक कार्यान्वयन प्रयास शुरू किया है। चूंकि , सिबिल अटैक के खिलाफ प्रभावी बचाव में अनुसंधान को आम तौर पर खुला प्रश्न माना जाता है, और हर साल शीर्ष सुरक्षा अनुसंधान सम्मेलनों में विभिन्न प्रकार के संभावित बचाव प्रस्तावित किए जाते हैं।

कार्यान्वयन

डीएचटी कार्यान्वयन के व्यावहारिक उदाहरणों में सामने आए सबसे उल्लेखनीय अंतरों में कम से कम निम्नलिखित सम्मिलित हैं:

पता स्थान डीएचटी का पैरामीटर है। कई वास्तविक दुनिया के डीएचटी 128-बिट या 160-बिट कुंजी स्थान का उपयोग करते हैं।
कुछ वास्तविक दुनिया के डीएचटी SHA-1 के अलावा अन्य हैश फ़ंक्शन का उपयोग करते हैं।
वास्तविक दुनिया में कुंजी k सामग्री-पता योग्य भंडारण प्रदान करने के लिए फ़ाइल के नाम के हैश के बजाय फ़ाइल की सामग्री का हैश हो सकता है, ताकि फ़ाइल का नाम बदलने से उपयोगकर्ताओं को इसे ढूंढने से न रोका जा सके।
कुछ डीएचटी विभिन्न प्रकार की वस्तुओं को भी प्रकाशित कर सकते हैं। उदाहरण के लिए, कुंजी k नोड हो सकता है ID और संबंधित डेटा यह बता सकता है कि इस नोड से कैसे संपर्क किया जाए। यह उपस्थिति की जानकारी के प्रकाशन की अनुमति देता है और अक्सर आईएम अनुप्रयोगों आदि में उपयोग किया जाता है। सबसे सरल मामले में, ID केवल यादृच्छिक संख्या है जिसे सीधे कुंजी के रूप में उपयोग किया जाता है k (तो 160-बिट डीएचटी में ID 160-बिट संख्या होगी, जिसे आमतौर पर यादृच्छिक रूप से चुना जाता है)। कुछ डीएचटी में, डीएचटी संचालन को अनुकूलित करने के लिए नोड्स आईडी के प्रकाशन का भी उपयोग किया जाता है।
विश्वसनीयता में सुधार के लिए अतिरेक को जोड़ा जा सकता है। वह (k, data) कुंजी युग्म को कुंजी के अनुरूप से अधिक नोड में संग्रहित किया जा सकता है। आमतौर पर, केवल नोड का चयन करने के बजाय, वास्तविक दुनिया डीएचटी एल्गोरिदम का चयन करते हैं i उपयुक्त नोड्स, के साथ i डीएचटी का कार्यान्वयन-विशिष्ट पैरामीटर है। कुछ डीएचटी डिज़ाइनों में, नोड्स निश्चित कीस्पेस रेंज को संभालने के लिए सहमत होते हैं, जिसका आकार हार्ड-कोड के बजाय गतिशील रूप से चुना जा सकता है।
कैडेमलिया जैसे कुछ उन्नत डीएचटी उपयुक्त नोड्स के सेट का चयन करने और भेजने के लिए पहले डीएचटी के माध्यम से पुनरावृत्त लुकअप करते हैं put(k, data) संदेश केवल उन्हीं नोड्स को भेजे जाते हैं, जिससे बेकार ट्रैफ़िक में भारी कमी आती है, क्योंकि प्रकाशित संदेश केवल उन नोड्स को भेजे जाते हैं जो कुंजी संग्रहीत करने के लिए उपयुक्त लगते हैं k; और पुनरावृत्त लुकअप संपूर्ण डीएचटी के बजाय केवल नोड्स के छोटे सेट को कवर करते हैं, जिससे बेकार अग्रेषण कम हो जाता है। ऐसे डीएचटी में, अग्रेषित करना put(k, data) संदेश केवल स्व-उपचार एल्गोरिथ्म के भाग के रूप में हो सकते हैं: यदि कोई लक्ष्य नोड प्राप्त करता है put(k, data) संदेश, किन्तु उस पर विश्वास करता है k अपनी प्रबंधित सीमा से बाहर है और करीबी नोड (डीएचटी कीस्पेस के संदर्भ में) ज्ञात है, संदेश उस नोड पर अग्रेषित किया जाता है। अन्यथा, डेटा स्थानीय रूप से अनुक्रमित किया जाता है। इससे कुछ हद तक स्व-संतुलित डीएचटी व्यवहार होता है। बेशक, ऐसे एल्गोरिदम के लिए नोड्स को डीएचटी में अपनी उपस्थिति डेटा प्रकाशित करने की आवश्यकता होती है ताकि पुनरावृत्त लुकअप किया जा सके।
चूंकि अधिकांश मशीनों पर संदेश भेजना स्थानीय हैश तालिका ्सेस की तुलना में बहुत अधिक महंगा है, इसलिए किसी विशेष नोड से संबंधित कई संदेशों को ही बैच में बंडल करना समझ में आता है। यह मानते हुए कि प्रत्येक नोड में स्थानीय बैच है जिसमें अधिकतम सम्मिलित है b संचालन, बंडलिंग प्रक्रिया इस प्रकार है। प्रत्येक नोड पहले ऑपरेशन के लिए जिम्मेदार नोड के पहचानकर्ता द्वारा अपने स्थानीय बैच को सॉर्ट करता है। बाल्टी प्रकार का उपयोग करके, यह किया जा सकता है O(b + n), कहाँ n डीएचटी में नोड्स की संख्या है। जब बैच के भीतर ही कुंजी को संबोधित करने वाले कई ऑपरेशन होते हैं, तो बैच को बाहर भेजे जाने से पहले संघनित किया जाता है। उदाहरण के लिए, ही कुंजी के ाधिक लुकअप को में घटाया जा सकता है या ही ऐड ऑपरेशन में ाधिक वृद्धि को कम किया जा सकता है। इस कमी को अस्थायी स्थानीय हैश तालिका की सहायता से कार्यान्वित किया जा सकता है। अंत में, ऑपरेशन संबंधित नोड्स को भेजे जाते हैं।^[29]

उदाहरण

डीएचटी प्रोटोकॉल और कार्यान्वयन

अपाचे कैसेंड्रा
बैटन ओवरले
मेनलाइन डीएचटी - बिटटोरेंट द्वारा उपयोग किया जाने वाला मानक डीएचटी (खशमीर द्वारा प्रदान किए गए कैडेमलिया पर आधारित)^[30]
सामग्री पतायोग्य नेटवर्क (CAN)
कॉर्ड (डीएचटी)
कोर्डे
कडेमलिया
पेस्ट्री (डीएचटी)
पी-ग्रिड
लहर
टेपेस्ट्री (डीएचटी)
टॉमपी2पी
वोल्डेमॉर्ट (वितरित डेटा स्टोर)

डीएचटी का उपयोग करने वाले अनुप्रयोग

BTDigg: बिटटोरेंट डीएचटी सर्च इंजन
कोडीन: वेब कैशिंग
फ़्रीनेट: सेंसरशिप-प्रतिरोधी अनाम नेटवर्क
ग्लस्टरएफएस: वितरित फ़ाइल सिस्टम जिसका उपयोग स्टोरेज वर्चुअलाइजेशन के लिए किया जाता है
जीएनयूनेट: डीएचटी कार्यान्वयन सहित फ्रीनेट जैसा वितरण नेटवर्क
I2P: ओपन-सोर्स अनाम पीयर-टू-पीयर नेटवर्क
I2P | I2P-Bote: सर्वर रहित सुरक्षित अनाम ईमेल
इंटरप्लेनेटरी फाइल सिस्टम: कंटेंट-एड्रेसेबल, पीयर-टू-पीयर हाइपरमीडिया वितरण प्रोटोकॉल
JXTA: ओपन-सोर्स पी2पी प्लेटफॉर्म
LBRY: ब्लॉकचेन-आधारित सामग्री साझाकरण प्रोटोकॉल जो सामग्री वितरण के लिए कैडेमलिया-प्रभावित डीएचटी प्रणाली का उपयोग करता है
ओरेकल सुसंगतता : जावा डीएचटी कार्यान्वयन के शीर्ष पर निर्मित इन-मेमोरी डेटा ग्रिड
परफेक्ट डार्क (पी2पी): जापान का पीयर-टू-पीयर फ़ाइल साझा करना एप्लिकेशन
पुनः साझाकरण : मित्र-से-मित्र नेटवर्क^[31]
जामी (सॉफ्टवेयर): गोपनीयता-संरक्षण आवाज, वीडियो और चैट संचार मंच, जो कैडेमलिया-जैसे डीएचटी पर आधारित है
टॉक्स (प्रोटोकॉल): त्वरित संदेश प्रणाली जिसका उद्देश्य स्काइप प्रतिस्थापन के रूप में कार्य करना है
ट्विस्टर (सॉफ्टवेयर): माइक्रोब्लॉगिंग पीयर-टू-पीयर प्लेटफॉर्म
YaCy: वितरित वेब खोज इंजन

यह भी देखें

काउचबेस सर्वर: मेम्केच्ड प्रोटोकॉल के साथ संगत सतत, प्रतिकृति, क्लस्टर्ड वितरित ऑब्जेक्ट स्टोरेज सिस्टम।
मेमकैच्ड: उच्च-प्रदर्शन, वितरित मेमोरी ऑब्जेक्ट कैशिंग सिस्टम।
उपसर्ग हैश ट्री: डीएचटी पर परिष्कृत क्वेरी।
मर्केल वृक्ष: वह पेड़ जिसमें प्रत्येक गैर-पत्ती नोड को उसके बच्चों के नोड्स के लेबल के हैश के साथ लेबल किया जाता है।
अधिकांश वितरित डेटा स्टोर लुकअप के लिए किसी न किसी रूप में डीएचटी का उपयोग करते हैं।
डीएचटी को लागू करने के लिए ग्राफ़ छोड़ें ़ कुशल डेटा संरचना है।

संदर्भ

↑ Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review. 31 (4): 149. doi:10.1145/964723.383071. A value can be an address, a document, or an arbitrary data item.
↑ Liz, Crowcroft; et al. (2005). "पीयर-टू-पीयर ओवरले नेटवर्क योजनाओं का सर्वेक्षण और तुलना" (PDF). IEEE Communications Surveys & Tutorials. 7 (2): 72–93. CiteSeerX 10.1.1.109.6124. doi:10.1109/COMST.2005.1610546. S2CID 7971188.
↑ Richter, Stevenson; et al. (2009). "क्लाइंट-सर्वर संबंधों पर गतिशील क्वेरी मॉडल के प्रभाव का विश्लेषण". Trends in Modern Computing: 682–701.
↑ Searching in a Small World Chapters 1 & 2 (PDF), retrieved 2012-01-10
↑ "Section 5.2.2" (PDF), A Distributed Decentralized Information Storage and Retrieval System, retrieved 2012-01-10
↑ Ratnasamy; et al. (2001). "एक स्केलेबल कंटेंट-एड्रेसेबल नेटवर्क" (PDF). In Proceedings of ACM SIGCOMM 2001. Retrieved 2013-05-20. {{cite journal}}: Cite journal requires |journal= (help)
↑ Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in P2P systems. In Communications of the ACM, February 2003.
↑ David Cohen (October 1, 2002). "New P2P network funded by US government". New Scientist. Retrieved November 10, 2013.
↑ "एमआईटी, बर्कले, आईसीएसआई, एनवाईयू और राइस ने आईआरआईएस प्रोजेक्ट लॉन्च किया". Press release. MIT. September 25, 2002. Archived from the original on September 26, 2015. Retrieved November 10, 2013.
↑ R Mokadem, A Hameurlain and AM Tjoa. Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems. Proc. iiWas, 2010
↑ Guido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys 43(2), January 2011.
↑ Moni Naor and Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003.
↑ Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table Archived 2004-09-10 at the Wayback Machine. Ph. D. Thesis (Stanford University), August 2004.
↑ Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (2010-02-01). "विषम वातावरण के लिए संरचित ओवरले". ACM Transactions on Autonomous and Adaptive Systems. 5 (1): 1–25. doi:10.1145/1671948.1671950. ISSN 1556-4665. S2CID 13218263.
↑ Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (October 2010). "Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems". IEEE/ACM Transactions on Networking. 18 (5): 1651–1664. doi:10.1109/TNET.2010.2046745. S2CID 14797120.
↑ Galuba, Wojciech; Girdzijauskas, Sarunas (2009), "Peer to Peer Overlay Networks: Structure, Routing and Maintenance", in LIU, LING; ÖZSU, M. TAMER (eds.), Encyclopedia of Database Systems (in English), Springer US, pp. 2056–2061, doi:10.1007/978-0-387-39940-9_1215, ISBN 9780387399409
↑ Girdzijauskas, Sarunas (2009). पीयर-टू-पीयर डिज़ाइन करना एक छोटी दुनिया के परिप्रेक्ष्य को दर्शाता है. {{cite book}}: |website= ignored (help)
↑ The (Degree,Diameter) Problem for Graphs, Maite71.upc.es, archived from the original on 2012-02-17, retrieved 2012-01-10
↑ Gurmeet Singh Manku, Moni Naor, and Udi Wieder. "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks". Proc. STOC, 2004.
↑ Ali Ghodsi (22 May 2007). "Distributed k-ary System: Algorithms for Distributed Hash Tables". Archived from the original on 4 January 2007. {{cite web}}: |archive-date= / |archive-url= timestamp mismatch (help). KTH-Royal Institute of Technology, 2006.
↑ Castro, Miguel; Costa, Manuel; Rowstron, Antony (1 January 2004). "Should we build Gnutella on a structured overlay?" (PDF). ACM SIGCOMM Computer Communication Review. 34 (1): 131. CiteSeerX 10.1.1.221.7892. doi:10.1145/972374.972397. S2CID 6587291.
↑ Talia, Domenico; Trunfio, Paolo (December 2010). "वितरित हैश तालिकाओं पर गतिशील क्वेरी सक्षम करना". Journal of Parallel and Distributed Computing. 70 (12): 1254–1265. doi:10.1016/j.jpdc.2010.08.012.
↑ Baruch Awerbuch, Christian Scheideler. "Towards a scalable and robust DHT". 2006. doi:10.1145/1148109.1148163
↑ Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary".
↑ Natalya Fedotova; Giordano Orzetti; Luca Veltri; Alessandro Zaccagnini. "Byzantine agreement for reputation management in DHT-based peer-to-peer networks". doi:10.1109/ICTEL.2008.4652638
↑ Whanau: A Sybil-proof Distributed Hash Table https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf
↑ Chris Lesniewski-Laas. "एक सिबिल-प्रूफ वन-हॉप DHT" (PDF): 20. {{cite journal}}: Cite journal requires |journal= (help)
↑ Jonathan Kelner, Petar Maymounkov (2009). "इलेक्ट्रिक रूटिंग और समवर्ती प्रवाह कटिंग". arXiv:0909.2859. Bibcode:2009arXiv0909.2859K. {{cite journal}}: Cite journal requires |journal= (help)
↑ Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox (in English). Springer International Publishing. ISBN 978-3-030-25208-3.
↑ Tribler wiki Archived December 4, 2010, at the Wayback Machine retrieved January 2010.
↑ Retroshare FAQ retrieved December 2011

बाहरी संबंध

Distributed Hash Tables, Part 1 by Brandon Wiley.
Distributed Hash Tables links Carles Pairot's Page on डीएचटी and P2P research
kademlia.scs.cs.nyu.edu Archive.org snapshots of kademlia.scs.cs.nyu.edu
Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). "IEEE Survey on overlay network schemes". CiteSeerX 10.1.1.111.4197: covering unstructured and structured decentralized overlay networks including डीएचटीs (Chord, Pastry, Tapestry and others).
Mainline डीएचटी Measurement at Department of Computer Science, University of Helsinki, Finland.

Template:BitTorrent

[StoicaEtAl2001-1] Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review. 31 (4): 149. doi:10.1145/964723.383071. A value can be an address, a document, or an arbitrary data item.

[2] Liz, Crowcroft; et al. (2005). "पीयर-टू-पीयर ओवरले नेटवर्क योजनाओं का सर्वेक्षण और तुलना" (PDF). IEEE Communications Surveys & Tutorials. 7 (2): 72–93. CiteSeerX 10.1.1.109.6124. doi:10.1109/COMST.2005.1610546. S2CID 7971188.

[3] Richter, Stevenson; et al. (2009). "क्लाइंट-सर्वर संबंधों पर गतिशील क्वेरी मॉडल के प्रभाव का विश्लेषण". Trends in Modern Computing: 682–701.

[4] Searching in a Small World Chapters 1 & 2 (PDF), retrieved 2012-01-10

[5] "Section 5.2.2" (PDF), A Distributed Decentralized Information Storage and Retrieval System, retrieved 2012-01-10

[Ratnasamy01-6] Ratnasamy; et al. (2001). "एक स्केलेबल कंटेंट-एड्रेसेबल नेटवर्क" (PDF). In Proceedings of ACM SIGCOMM 2001. Retrieved 2013-05-20. {{cite journal}}: Cite journal requires |journal= (help)

[7] Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in P2P systems. In Communications of the ACM, February 2003.

[8] David Cohen (October 1, 2002). "New P2P network funded by US government". New Scientist. Retrieved November 10, 2013.

[9] "एमआईटी, बर्कले, आईसीएसआई, एनवाईयू और राइस ने आईआरआईएस प्रोजेक्ट लॉन्च किया". Press release. MIT. September 25, 2002. Archived from the original on September 26, 2015. Retrieved November 10, 2013.

[10] R Mokadem, A Hameurlain and AM Tjoa. Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems. Proc. iiWas, 2010

[11] Guido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys 43(2), January 2011.

[12] Moni Naor and Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003.

[13] Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table Archived 2004-09-10 at the Wayback Machine. Ph. D. Thesis (Stanford University), August 2004.

[14] Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (2010-02-01). "विषम वातावरण के लिए संरचित ओवरले". ACM Transactions on Autonomous and Adaptive Systems. 5 (1): 1–25. doi:10.1145/1671948.1671950. ISSN 1556-4665. S2CID 13218263.

[15] Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (October 2010). "Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems". IEEE/ACM Transactions on Networking. 18 (5): 1651–1664. doi:10.1109/TNET.2010.2046745. S2CID 14797120.

[16] Galuba, Wojciech; Girdzijauskas, Sarunas (2009), "Peer to Peer Overlay Networks: Structure, Routing and Maintenance", in LIU, LING; ÖZSU, M. TAMER (eds.), Encyclopedia of Database Systems (in English), Springer US, pp. 2056–2061, doi:10.1007/978-0-387-39940-9_1215, ISBN 9780387399409

[17] Girdzijauskas, Sarunas (2009). पीयर-टू-पीयर डिज़ाइन करना एक छोटी दुनिया के परिप्रेक्ष्य को दर्शाता है. {{cite book}}: |website= ignored (help)

[18] The (Degree,Diameter) Problem for Graphs, Maite71.upc.es, archived from the original on 2012-02-17, retrieved 2012-01-10

[19] Gurmeet Singh Manku, Moni Naor, and Udi Wieder. "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks". Proc. STOC, 2004.

[20] Ali Ghodsi (22 May 2007). "Distributed k-ary System: Algorithms for Distributed Hash Tables". Archived from the original on 4 January 2007. {{cite web}}: |archive-date= / |archive-url= timestamp mismatch (help). KTH-Royal Institute of Technology, 2006.

[21] Castro, Miguel; Costa, Manuel; Rowstron, Antony (1 January 2004). "Should we build Gnutella on a structured overlay?" (PDF). ACM SIGCOMM Computer Communication Review. 34 (1): 131. CiteSeerX 10.1.1.221.7892. doi:10.1145/972374.972397. S2CID 6587291.

[22] Talia, Domenico; Trunfio, Paolo (December 2010). "वितरित हैश तालिकाओं पर गतिशील क्वेरी सक्षम करना". Journal of Parallel and Distributed Computing. 70 (12): 1254–1265. doi:10.1016/j.jpdc.2010.08.012.

[23] Baruch Awerbuch, Christian Scheideler. "Towards a scalable and robust DHT". 2006. doi:10.1145/1148109.1148163

[24] Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary".

[25] Natalya Fedotova; Giordano Orzetti; Luca Veltri; Alessandro Zaccagnini. "Byzantine agreement for reputation management in DHT-based peer-to-peer networks". doi:10.1109/ICTEL.2008.4652638

[26] Whanau: A Sybil-proof Distributed Hash Table https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf

[27] Chris Lesniewski-Laas. "एक सिबिल-प्रूफ वन-हॉप DHT" (PDF): 20. {{cite journal}}: Cite journal requires |journal= (help)

[28] Jonathan Kelner, Petar Maymounkov (2009). "इलेक्ट्रिक रूटिंग और समवर्ती प्रवाह कटिंग". arXiv:0909.2859. Bibcode:2009arXiv0909.2859K. {{cite journal}}: Cite journal requires |journal= (help)

[29] Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox (in English). Springer International Publishing. ISBN 978-3-030-25208-3.

[30] Tribler wiki Archived December 4, 2010, at the Wayback Machine retrieved January 2010.

[31] Retroshare FAQ retrieved December 2011

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

Anonymous

Search

डिस्ट्रिब्यूटेड हैश टेबल

Namespaces

More

Page actions

Contents

इतिहास

गुण