DHT पर फ़ेलसेफ़ संसाधन आवंटनकर्ता

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

एपीआई

वास्तव में, आइए हमारे "आवंटनकर्ता" के एपीआई को स्पष्ट करके शुरू करें। जैसा कि ऊपर उल्लेख किया गया है, वर्तमान एपीआई गलत है - इसका उपयोग वितरित प्रणाली में नहीं किया जा सकता है, क्योंकि कॉलिंग कोड किसी विशेष पूल तत्व की विशेष स्थिति को समझने में हमेशा सक्षम नहीं होगा।

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

सामान्यतया, इन एपीआई समस्याओं को हल करने के कई तरीके हैं।

सबसे सरल और काफी सार्वभौमिक है, हम संसाधनों के प्रत्येक आवंटन के लिए एक टैग संलग्न करते हैं, जो कि आवंटित / मुक्त संचालन के प्रत्येक जोड़े के लिए अद्वितीय चुना जाता है।

यही है, विधि हस्ताक्षर को int आवंटित (T t) और मुक्त (int id, T t) में बदल दिया जाता है। कोई फर्क नहीं पड़ता कि किस प्रकार का टी, यह महत्वपूर्ण है कि उस पर एक निश्चित तुल्यता संबंध मौजूद है, और यह कि हम ऊपर वर्णित दो समस्याओं को हल कर सकते हैं। सबसे पहले, नि: शुल्क विधि को बेरोजगार बनाया जा सकता है। दूसरे, हम "फैंटम" पहचानकर्ताओं को हटाने के लिए एक अपेक्षाकृत सरल प्रक्रिया पेश कर सकते हैं जो आवंटित किए गए थे, लेकिन जो हमें पुरानी जानकारी नहीं मिली थी (समस्या 1 देखें)। लेख को न बढ़ाने के लिए हमने इस पर ध्यान नहीं दिया।

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

अब थोड़ा और, यह समझना बाकी है कि "आंशिक" निष्पादन के मामले में कैसे आवंटित और मुक्त व्यवहार होता है, जो बदले में, यह समझेगा कि हम कॉलिंग कोड कैसे लिखते हैं, और क्या इसे लिखना संभव है।

जाहिर है, सामान्य स्थिति में, कॉलिंग कोड को पता नहीं चल सकता है कि आवंटन निष्पादित किया गया था या नहीं। तो कॉलिंग कोड के लिए पहला नियम पढ़ा जाएगा

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

ठीक है, चलो कार्यान्वयन के लिए आगे बढ़ें।

कार्यान्वयन

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

अपने आप में, DHT में ऑपरेशन परमाणु हैं (यह DHT के कार्यान्वयन के कई तरीकों से पूरी तरह से समर्थित है)।

हालांकि, DHT में चुनौतियों के बीच कोई भी परमाणु नहीं है, और हमें इस भाग को ध्यान में रखना चाहिए और इसके कार्यान्वयन में समर्थन करना चाहिए।

तो कार्यान्वयन

जाहिर है, DHT में हमारे पास फॉर्म id-> t (या इसके विपरीत) के कुछ प्रकार के नक्शे होंगे। समस्या यह है कि सभी व्यस्त नोड्स के माध्यम से जाने के बिना पहली मुफ्त आईडी कैसे प्राप्त करें?

ऐसा समाधान प्रस्तावित है। आइए बाइनरी इंटरवल ट्री का निर्माण करें
• पेड़ की जड़ - अंतराल [0, N)
• गैर-पत्ती नोड एक्स [ए, बी] के तहत, दो नोड्स [ए, सी) और [सी, बी) हैं, जहां सी को चुना जाता है ताकि इन अंतरालों की लंबाई बराबर हो
• और रूप के अंतराल [आईडी, आईडी + 1) - पेड़ के पत्ते हैं।
जाहिर है, ऐसे पेड़ में एन शीट होते हैं, जिनमें से प्रत्येक को रूट से एनएन (एन) संक्रमण तक पहुंचा जा सकता है।

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

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

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

अब, "जादुई" अंतराल संरचना है जो हमारे फैले हुए पेड़ को कोड कर सकती है, मामला छोटा है।
आवंटित करने में, हमें कुछ गैर-रिक्त शीट का चयन करना होगा और उसमें एक टैग लिखना होगा, और फिर चयनित शीट से ऊपर जाकर उनके मूल्यों को अपडेट करना होगा। दो चीजों को याद रखना महत्वपूर्ण है।
• टैग को परमाणु ऑपरेशन putIfAbsent द्वारा सूची में जोड़ा जाता है
• गैर-पत्ती नोड्स में मूल्यों को लूप के माध्यम से अद्यतन-संशोधित-परमाणु-परमाणु के साथ अद्यतन किया जाता है। अर्थात्, हम अद्यतन नोड से मूल्य पढ़ते हैं, बाल नोड्स में मूल्य पढ़ते हैं, परमाणु के माध्यम से बच्चों के योग को अद्यतन नोड में लिखते हैं। यदि परमाणु प्रतिस्थापित नहीं हुआ, तो ऑपरेशन दोहराएं।
• भले ही हम DHT से पढ़ते हैं कि नोड के उप-पेड़ में मुफ्त पत्तियां हैं, इसका मतलब यह नहीं है कि वे वास्तव में वहां हैं।
इसलिए, एक खाली शीट को खोजने और अद्यतन करने के लिए हमारी आबंटन को "सफलता तक" के रूप में लिखा जाएगा। ध्यान दें कि पेड़ का पहला संशोधन जो हम करते हैं, वह शीट को अपडेट कर रहा है, और उसके बाद ही - मूल नोड्स को अपडेट कर रहा है। यह आवश्यक है क्योंकि आवंटन किसी भी समय पूरा हो सकता है।

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

कार्य करना

वास्तव में, वादा किया गया () फ़ंक्शन। यह ध्यान देने योग्य है कि बाएं (), दाएं () और ऊपर () की वर्तनी बहुत सरल है यदि हम सहमत हैं कि शीर्ष-स्तरीय अंतराल की लंबाई 2 ^ n है। फिर पेड़ में किसी अन्य अंतराल की लंबाई 2 ^ n होगी, इसके अलावा, पेड़ के समान "स्तर" पर अंतराल की लंबाई समान होगी। सामान्यतया, सभी तीन sabj फ़ंक्शन को एक मनमाने ढंग से शीर्ष-स्तरीय अंतराल के लिए लिखा जा सकता है (लेकिन फिर, "वर्तमान" अंतराल के अलावा, आपको हमेशा ऊपरी-स्तरीय अंतराल जानने की आवश्यकता होगी)। लेकिन यह असुविधाजनक है, और 2 ^ n तक सामान्यीकरण कुछ भी नुकसान नहीं पहुंचाता है।

इस प्रकार, अंतराल की लंबाई के साथ 2 ^ n, बाएं () और दाएं () तुच्छ रूप से लिखे गए हैं, और ऊपर () के लिए आपको केवल यह निर्धारित करने की आवश्यकता है कि वर्तमान अंतराल अपने माता-पिता के अंतराल के लिए "सही" या "बाएं" है या नहीं। यह एक सरल नियम द्वारा निर्धारित किया जाता है - "बाएं" अंतराल पर, प्रारंभिक मूल्य को अंतराल के बिना दो बार की लंबाई से विभाजित किया जाता है। तदनुसार, अंतराल के बारे में जानना, चाहे वह बाएं () या दाएं () फ़ंक्शन से प्राप्त किया गया था, विपरीत क्रिया को लागू करना और ऊपरी स्तर का अंतराल प्राप्त करना आसान है।