Kademlia DHT: मूल बातें

आपका स्वागत है!
इस लेख में, जैसा कि मैं निम्नलिखित में आशा करता हूं, मैं आधुनिक संरचित सहकर्मी से सहकर्मी नेटवर्क में से एक के बारे में बात करना चाहता हूं। इस सामग्री में प्रलेखन, विवरण और विषय पर पाए गए लेखों का मेरा प्रसंस्करण शामिल है। एक परिचय के रूप में, P2p नेटवर्क का एक सामान्य संक्षिप्त सिद्धांत, DHT प्रस्तुत किया गया है, और उसके बाद ही मुख्य भाग, जिसके लिए नोट समर्पित है, निम्नानुसार है।

1. सामान्य पी 2 पी सिद्धांत

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

केंद्रीयकरण की डिग्री के अनुसार, निम्न प्रकार के पी 2 पी नेटवर्क को प्रतिष्ठित किया जा सकता है:

• केंद्रीकृत
• संकर
• पूरी तरह से विकेंद्रीकृत

सेंट्रलाइज़्ड - वे नेटवर्क जो रूटिंग और खोज के लिए एक या अधिक सर्वर का उपयोग करते हैं। कुख्यात नेपस्टर एक केंद्रीकृत पी 2 पी नेटवर्क का एक उत्कृष्ट उदाहरण है।

इस प्रकार के नेटवर्क के विपक्ष:

• सर्वर एक नेटवर्क टोंटी का प्रतिनिधित्व करता है। विफलता से सिस्टम प्रदर्शन का पूर्ण नुकसान होता है।
• सर्वर विधायी भेद्यता
• नेटवर्क की आबादी में उल्लेखनीय वृद्धि के साथ, सर्वर एक प्रकार का DDoS हमला करेगा, जिससे इसकी विफलता हो जाएगी।

पेशेवरों:

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

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

विपक्ष और पेशेवरों "संकरता" की डिग्री पर निर्भर करते हैं - जो इसे केंद्रीयकृत से विरासत में मिला है और जो विकेंद्रीकृत से (जो बाद में चर्चा की जाएगी)।

विकेंद्रीकृत - इस प्रकार के नेटवर्क का अर्थ है सर्वरों की पूर्ण कमी। यह नेटवर्क से अड़चन को दूर करता है।

विपक्ष:

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

पेशेवरों:

• सर्वर अपवर्जन नेटवर्क को गलती से सहिष्णु होने की अनुमति देता है, यहां तक ​​कि प्रतिभागियों की तेजी से बढ़ती / गिरती संख्या के साथ।
• बृहत् सेंसरशिप सुरक्षा

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

संरचित नेटवर्क के टोपोलॉजी और प्रोटोकॉल डिजाइन करते समय, निम्नलिखित संबंधों को इष्टतम माना जाता है:
- प्रत्येक नोड पर रूटिंग टेबल का आकार: O (लॉग (n))
- खोज कठिनाई: O (लॉग (n))

2. DHT

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

3. कमंडलिया

मीट्रिक

इस टोपोलॉजी के रचनाकार पेटार मेमोउनकोव और डेविड माज़िएरेस हैं। प्रोटोकॉल और टेबल बिल्डिंग एक XOR मीट्रिक के माध्यम से नोड्स के बीच की दूरी को निर्धारित करने पर आधारित हैं:
d (x, y) = x XOR y। यह ध्यान रखना महत्वपूर्ण है कि दूरी एक्सओआर ऑपरेशन का परिणाम है, एक संख्या के रूप में व्याख्या की गई है, न कि विभिन्न बिट्स की संख्या (यह मानदंड कुंजी / पहचानकर्ता अंतरिक्ष में एक मीट्रिक भी उत्पन्न कर सकता है)। यानी 4 बिट्स की प्रमुख लंबाई के साथ: d (2,5) = 0010 XOR 0101 = 0111 = 7।
XOR मीट्रिक मीट्रिक के सभी स्वयंसिद्धों को संतुष्ट करता है:

1. d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //
2. d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //
3. d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //
4. d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //

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

रूटिंग टेबल

राउटिंग टेबल के निर्माण के लिए एक एल्गोरिथ्म नोड्स के बीच की दूरी की गणना करने पर आधारित है (अपने पहचानकर्ताओं को मीट्रिक लागू करके)।
तालिका का प्रत्येक i-th स्तंभ 2 ^ (i + 1) से 2 ^ i की दूरी पर नोड्स के बारे में जानकारी संग्रहीत करने के लिए जिम्मेदार है। इस प्रकार, नोड 0111 के अंतिम कॉलम में किसी भी नोड्स 1xxx के बारे में जानकारी हो सकती है, नोड्स 00xx के बारे में एक और यहां तक ​​कि एक स्तर के करीब - नोड्स 010x के बारे में जानकारी हो सकती है।

बेशक, एक वास्तविक नेटवर्क में, कुंजी लंबाई आमतौर पर 128, या 160 बिट्स पर लागू होती है। कार्यान्वयन पर निर्भर करता है।

इसके अलावा, प्रत्येक स्तर पर संग्रहीत नोड्स की संख्या पर प्रतिबंध लगाया जाता है। के। इसलिए, इस तरह के K तक सीमित तालिका के स्तंभों को K-buckets कहा जाता है (दुर्भाग्य से, रूसी समकक्ष पूरी तरह से असंगत हैं)।

यदि हम बाइनरी सर्च ट्री को देखते हैं, जिनमें से शीट में नोड्स के पहचानकर्ता होते हैं, तो यह स्पष्ट हो जाता है कि इस तरह की के-बकेट संरचना यादृच्छिक नहीं है: प्रत्येक नोड (110 के उदाहरण में) प्रत्येक सबट्री के कम से कम एक सदस्य का ज्ञान प्राप्त करता है (भरे हुए अंडाकार के साथ 110 के लिए)। इस प्रकार, प्रत्येक के-बकेट नोड के कनेक्शन को दर्शाता है जो कि स्तर i पर उप-वर्ग के K प्रतिभागियों से अधिक नहीं है।

प्रोटोकॉल

Kademlia प्रोटोकॉल में 4 प्रकार के संदेश शामिल हैं:

• PING
• स्टोर
• FIND_VALUE
• FIND_NODE

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

अधिक अनुरोध जो आपको किसी दिए गए नोड पर जानकारी रखने की अनुमति देता है। STORE को अंजाम देने से पहले, नोड को K को उन मानों को खोजना होगा जो इसे प्रकाशित करने जा रहे हैं, और उसके बाद ही कुंजी और इसके निर्देशांक के साथ प्रत्येक STORE को भेजें। K नोड पर तुरंत संग्रहण आपको सूचना की उपलब्धता बढ़ाने की अनुमति देता है।

FIND_VALUE क्वेरी, जिसे अक्सर पुनरावृति बनाने के लिए दोहराया जाता है, जिससे आप कुंजी द्वारा मान ज्ञात कर सकते हैं। नेटवर्क में एक मान खोज को लागू करता है। यह वांछित डेटा को संग्रहीत करने वाले नोड की उपलब्धि के आधार पर, निकटतम नोड्स के या तो, या स्वयं मान देता है। जब मूल्य वापस किया जाता है (सफलता), या जब के नोड्स पहले से ही प्रदूषित हो जाते हैं, तो Iterations रुक जाते हैं (नेटवर्क में कोई मूल्य नहीं है)।

FIND_NODE एक क्वेरी है जिसका उपयोग किसी दिए गए पहचानकर्ता के निकटतम K को खोजने के लिए किया जाता है (व्यवहार FIND_VALUE के समान है, केवल कभी भी कोई मान नहीं देता है, हमेशा नोड!)। उदाहरण के लिए, निम्न योजना के अनुसार नेटवर्क से नोड कनेक्ट करते समय इसका उपयोग किया जाता है:
- बूटस्ट्रैप नोड से संपर्क करें
- इसके नोड के लिए एक पहचानकर्ता के साथ एक FIND_NODE अनुरोध भेजना, आगे पुनरावृति भेजना
- के-बाल्टी अपडेट करें (इस मामले में, नए नोड के दोनों के-बाल्टी अपडेट किए गए हैं, साथ ही सभी अनुरोधों को पारित कर दिया गया है (यहां XOR मीट्रिक की समरूपता हाथ में है)

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

4. कार्यान्वयन

सबसे पहले, सबसे प्रसिद्ध शिक्षा-आधारित नेटवर्क कद नेटवर्क है, जो एमुले / ई - मेल पर उपलब्ध है। बूटस्ट्रैप के लिए, eDonkey में मौजूदा नोड्स का उपयोग किया जाता है।
खशमीर - बिटेलोरेंट में इस्तेमाल किए जाने वाले केमलिया पायथन कार्यान्वयन
वर्तमान में विकसित और सक्रिय पुस्तकालयों में से, मैं भी ध्यान देना होगा
maidsafe-dht - UDT और NAT Traversal के समर्थन के साथ C ++ अवसंरचना कार्यान्वयन।
मोजिटो - लाइमवायर से जावा पुस्तकालय।

5. आगे क्या?

मैं इस बारे में टिप्पणी प्राप्त करना चाहूंगा कि क्या अधिक विस्तार से चित्रित किया जाना चाहिए, जैसा कि लेख बेहद सतही है। रुचि जगाने के लिए, और मेज पर एक बार में सभी कार्ड नहीं रखे। मैं खुद सुरक्षा के मुद्दों, हमलों और उनकी रोकथाम के बारे में बात करने के लिए Kademlia के बारे में अगले लेख में योजना बना रहा हूं।

6. सामग्री और लिंक

• पी 2 पी (इंग्लैंड विकिपीडिया)
• DHT (इंग्लैंड विकिपीडिया)
• Kademlia (इंग्लैंड विकिपीडिया)
• Kademlia: एक डिजाइन विशिष्टता
• Kademlia: एक सहकर्मी से सहकर्मी सूचना प्रणाली XOR मीट्रिक के आधार पर
• थोटोकिस, स्पिनेलिस। पीयर-टू-पीयर कंटेंट डिस्ट्रीब्यूशन टेक्नोलॉजीज का एक सर्वेक्षण
• पीयर-टू-पीयर कम्प्यूटिंग। सिद्धांत और अनुप्रयोग। // स्प्रिंगर, 2010