एक वितरित हैश तालिका (डीएचटी)

Question

की सरल बुनियादी व्याख्या क्या कोई भी डीएचटी कैसे काम करता है इस पर स्पष्टीकरण दे सकता है?

कुछ भी भारी नहीं, बस मूल बातें।

Answer 1

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

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

एक उदाहरण डीएचटी जो इन समस्याओं में से कुछ को हल करता है, एन नोड्स की तार्किक अंगूठी है, प्रत्येक कुंजीपटल के 1/एन की ज़िम्मेदारी लेता है। एक बार जब आप नेटवर्क में नोड जोड़ते हैं, तो यह दो अन्य नोड्स के बीच बैठने के लिए अंगूठी पर एक जगह पाता है, और अपने भाई नोड्स में कुछ चाबियों की ज़िम्मेदारी लेता है। इस दृष्टिकोण की सुंदरता यह है कि अंगूठी में अन्य नोड्स में से कोई भी प्रभावित नहीं होता है; केवल दो भाई नोड्स को कुंजी को फिर से वितरित करना होगा।

उदाहरण के लिए, तीन नोड रिंग में कहें कि पहले नोड में 0-10, दूसरा 11-20 और तीसरा 21-30 है। यदि चौथा नोड साथ आता है और नोड्स 3 और 0 के बीच खुद को सम्मिलित करता है (याद रखें, वे एक अंगूठी में हैं), तो यह 3 की चाबी स्पेस के आधे हिस्से के लिए जिम्मेदारी ले सकता है, इसलिए अब यह 21 और 21 के साथ नोड 3 सौदों से संबंधित है -25।

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

विकिपीडिया पेज पढ़ें, और यदि आप वास्तव में गहराई से जानना चाहते हैं, तो हार्वर्ड में यह coursepage देखें, जिसमें एक बहुत व्यापक पठन सूची है।

Answer 2

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

http://en.wikipedia.org/wiki/Distributed_hash_table

Answer 3

चेक बाहर this Wikipedia article या इस powerpoint slide

Answer 4

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

Answer 5

मैं हेनरीआर के उपयोगी उत्तर में जोड़ना चाहता हूं क्योंकि मुझे लगातार हैशिंग में अंतर्दृष्टि थी। एक सामान्य/बेवकूफ हैश लुकअप दो चर का एक कार्य है, जिसमें से एक बाल्टी की संख्या है। लगातार हैशिंग की सुंदरता यह है कि हम समीकरण से बाल्टी "एन" की संख्या को खत्म करते हैं।

बेवकूफ हैशिंग में, पहली चर तालिका में संग्रहीत करने के लिए ऑब्जेक्ट की कुंजी है। हम कुंजी "एक्स" कॉल करेंगे।दूसरा चर बाल्टी की संख्या है, "एन"। तो, यह निर्धारित करने के लिए कि ऑब्जेक्ट किस बाल्टी/मशीन में संग्रहीत है, आपको गणना करना होगा: हैश (x) mod (n)। इसलिए, जब आप बाल्टी की संख्या बदलते हैं, तो आप उस पते को भी बदलते हैं जिस पर लगभग हर ऑब्जेक्ट संग्रहित होता है।

इसकी तुलना लगातार हैशिंग से करें। चलो एक हैश फ़ंक्शन की सीमा के रूप में "आर" को परिभाषित करते हैं। आर कुछ स्थिर है। लगातार हैशिंग में, किसी ऑब्जेक्ट का पता हैश (x)/R पर स्थित है। चूंकि हमारा लुकअप अब बाल्टी की संख्या का कार्य नहीं है, इसलिए जब हम बाल्टी की संख्या बदलते हैं तो हम कम रीमेपिंग के साथ समाप्त होते हैं।

http://michaelnielsen.org/blog/consistent-hashing/