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

From Vigyanwiki

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

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

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

इतिहास

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

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

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

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

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

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

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

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

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

गुण

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

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

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

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

संरचना

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

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

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

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

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

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

निरंतर हैशिंग

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

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

रेनडेज़वोअस हैशिंग

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

प्रत्येक ग्राहक के पास पहचानकर्ताओं की समान सूची {S1, S2, ..., Sn } होती है , प्रत्येक सर्वर के लिए गणना करता है ।

w1 = h(S1, k), w2 = h(S2, k), ..., wn = h(Sn, k) कुछ कुंजी k दिए जाने पर, ग्राहक n हैश भार की गणना करता है .

क्लाइंट उस कुंजी को उस कुंजी के उच्चतम हैश भार के अनुरूप सर्वर के साथ जोड़ता है।

आईडी वाला सर्वर सभी कुंजियों का स्वामित्व है जिसके लिए हैश वजन उस कुंजी के लिए किसी अन्य नोड के हैश भार से अधिक है।

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

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

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

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

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

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

अधिकतम. डिग्री अधिकतम मार्ग लंबाई में उपयोग किया टिप्पणी
अधिक व्यर्थ लुकअप लंबाई, संभवतः अधिक धीमी लुकअप समय के साथ
कूर्डे (निरंतर डिग्री के साथ) कार्यान्वयन के लिए अधिक समष्टि , किन्तु स्वीकार्य लुकअप समय निश्चित संख्या में कनेक्शन के साथ पाया जा सकता है
कॉर्ड
कैडेमलिया
पेस्ट्री
टेपेस्ट्री
अधिक सामान्य , किन्तु इष्टतम नहीं (डिग्री/मार्ग लंबाई)। कॉर्ड अधिक मूलभूत संस्करण है, कैडेमलिया अधिक लोकप्रिय अनुकूलित संस्करण प्रतीत होता है (औसत लुकअप में सुधार होना चाहिए)
कूर्डे (इष्टतम लुकअप के साथ) प्रयुक्त करने के लिए अधिक जटिल, किन्तु लुकअप तीव्र हो सकता है (अधिक व्यर्थ स्थिति कम होनी चाहिए)
किसी भी नोड के कनेक्ट या डिस्कनेक्ट होने केपश्चात बहुत अधिक संचार के साथ अधिक व्यर्थ स्थानीय संचयन की आवश्यकता होती है

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

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

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

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

सुरक्षा

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

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

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

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

कार्यान्वयन

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

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

उदाहरण

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

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

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

यह भी देखें

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

संदर्भ

  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
  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

बाहरी संबंध

Template:BitTorrent