👨🏾‍🔧 👨🏿‍🤝‍👨🏾 🤵🏻 वास्तविक समय विषम प्रतिस्पर्धी डेटा प्रसंस्करण सख्ती से एक बार ⛵️ 🧗🏼 👩🏻‍💻

सहयोगी सॉसेज

अमूर्त

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

प्रस्तावित दृष्टिकोण लगातार गुप्त अवयवों और आवश्यक अवधारणाओं को प्रकट करेगा जो कि दो घटकों से शाब्दिक समवर्ती एक बार प्रसंस्करण को लागू करने के लिए अपेक्षाकृत आसान बनाते हैं।

परिचय

वितरित सिस्टम का डेवलपर कई चरणों से गुजरता है:

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

स्टेज 2: मल्टीथ्रेडिंग । इसके बाद, लोहे से अधिकतम दक्षता निकालने पर सवाल उठते हैं, इसमें मल्टीथ्रेडिंग, एसिंक्रोनसी, रेसिंग, डिबगिंग, स्ट्रेस, स्लीवलेस नाइट्स होते हैं ... कई इस स्तर पर अटक जाते हैं और यहां तक कि कुछ बिंदुओं पर एक अकथनीय रोमांच को पकड़ने लगते हैं। लेकिन वर्चुअल मेमोरी और मेमोरी मॉडल, लॉक-फ्री / वेट-फ्री एल्गोरिदम और विभिन्न एसिंक्रोनस मॉडल की वास्तुकला को समझने के लिए कुछ ही आते हैं। और लगभग कभी भी नहीं - बहु-थ्रेडेड कोड सत्यापन।

स्टेज 3: वितरण । यहाँ ऐसा कचरा हो रहा है कि न तो किसी परी कथा में और न ही वर्णन करने के लिए एक कलम।

ऐसा लगता है कि कुछ जटिल होगा। हम परिवर्तन करते हैं: कई थ्रेड -> कई प्रक्रियाएं -> कई सर्वर। लेकिन परिवर्तन का प्रत्येक चरण गुणात्मक परिवर्तन लाता है, और वे सभी सिस्टम पर गिरते हैं, इसे कुचलते हैं और इसे धूल में बदल देते हैं।

और यहाँ बिंदु त्रुटि हैंडलिंग डोमेन और साझा मेमोरी की उपलब्धता को बदलना है। यदि इससे पहले हमेशा स्मृति का एक टुकड़ा था जो प्रत्येक थ्रेड में उपलब्ध था, और यदि वांछित है, तो हर प्रक्रिया में, अब ऐसा कोई टुकड़ा नहीं है और नहीं हो सकता है। प्रत्येक अपने लिए, स्वतंत्र और गौरवशाली।

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

चाहे वह मल्टीथ्रेडिंग की बात हो: मैं म्यूटेक्स ले गया और खुशी के लिए साझा स्मृति को हिला दिया। ब्यूटी!

नतीजतन, हमारे पास यह है कि कुंजी और युद्ध-परीक्षण किए गए पैटर्न को हटा दिया गया था, और नए, उन्हें बदलने के लिए, किसी कारण से वितरित नहीं किया गया था, और यह एक मजाक की तरह निकला कि परी ने अपनी छड़ी कैसे लहराई और टॉवर ने टैंक को बंद कर दिया।

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

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

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

आदर्श रूप में, मैं यह बिल्कुल नहीं सोचना चाहूंगा कि हमारी प्रणाली वितरित और बहुपरत है, अर्थात्। 2 (मल्टीथ्रेडिंग + अतुल्यकालिक) और 3 डी (वितरण) के बारे में सोचने के बिना, 1 चरण (एल्गोरिदम) पर काम करते हैं। अमूर्त को अलग करने का यह तरीका लेखन कोड की सादगी, विश्वसनीयता और गति में काफी वृद्धि करेगा। दुर्भाग्य से, फिलहाल यह केवल सपनों में संभव है।

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

आलेख क्रमिक रूप से वितरित वितरित स्केलेबल रीयल-टाइम सिस्टम का निर्माण करने के लिए लॉक-फ्री एल्गोरिदम के उपयोग का खुलासा करता है, अर्थात। 2-चरण की लॉक-फ्री उपलब्धियां 3 के कार्यान्वयन में मदद करती हैं, 1 चरण के एकल-थ्रेडेड एल्गोरिदम के लिए कार्य को कम करती है।

समस्या का बयान

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

कार्य: वास्तविक समय स्ट्रीमिंग डेटा प्रोसेसिंग ।

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

प्रारंभिक

हम इस समस्या की कुछ विशेषताओं पर ध्यान देते हैं।

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

यह सब, जैसा कि नीचे दिखाया गया है, उपयोग किए जाने वाले उपकरणों और संभावित कार्यान्वयन विधियों को गंभीरता से प्रभावित करता है।

यह कार्य के लिए एक छोटा सा स्पर्श जोड़ने के लिए रहता है, जो तुरंत कार्य को जटिलता से परे के क्षेत्र से असंभव में स्थानांतरित करता है: एक समवर्ती बिल्कुल-एक बार गारंटी की आवश्यकता होती है।

वास्तव में-एक बार

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

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

इस प्रकार, हमें इस तथ्य के लिए तैयार रहना चाहिए कि हैंडलर गिर सकता है, और दूसरे हैंडलर को पहले से किए गए काम को चुनना चाहिए और प्रसंस्करण जारी रखना चाहिए।

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

समकालिक-एक बार

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

ऐसी आवश्यकता होने के परिणामों के बारे में नीचे चर्चा की जाएगी।

लेन-देन संबंधी

ताकि पाठक और भी अधिक गहराई से उत्पन्न हो जाए, जो कि इस तरह की प्रणाली को विकसित करते समय विभिन्न बुरे परिदृश्यों को ध्यान में रखना चाहिए। हम एक सामान्य दृष्टिकोण का उपयोग करने का भी प्रयास करेंगे जो हमें अपनी आवश्यकताओं को ध्यान में रखते हुए उपरोक्त समस्या को हल करने की अनुमति देगा।

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

विचार

हैंडलर का निम्न भोली कार्यान्वयन किसी प्रकार के डेटा वेयरहाउस का उपयोग करके उत्पन्न होता है। इस स्तर पर, रिपॉजिटरी के विशिष्ट गुण हमारे लिए महत्वपूर्ण नहीं होंगे। हम विचार का वर्णन करने के लिए Pseco भाषा का उपयोग करेंगे (Pseco: = pseudo कोड):

handle(input_queues, output_queues, state): #    input_indexes = storage.get_input_indexes() #      while true: #         items, new_input_indexes = input_queues.get_from(input_indexes) #    state.queue.push(items) #     duration state.queue.trim_time_window(duration) avg = state.queue.avg() need_update_counter = state.queue.size() > size_boundary # (A)      output_queues[0].push(avg) if need_update_counter: # (B)      db.increment_counter() # (C)     storage.save_state(state) # (D)    storage.save_queue_indexes(new_input_indexes) # (E)    input_indexes = new_input_indexes

यहां एक सरल एकल-थ्रेडेड एल्गोरिथ्म है जो इनपुट धाराओं से डेटा पढ़ता है और ऊपर वर्णित कार्य के अनुसार वांछित मान लिखता है।

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

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

आश्चर्य

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

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

प्रतिस्पर्धात्मक प्रतिक्रिया

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

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

इसके अलावा, समानांतर प्रोसेसर की संख्या में वृद्धि के साथ, यह अचानक पता चला है कि उनमें से सभी विफलताओं के अभाव में भी समान रूप से अच्छी तरह से काम नहीं करते हैं। कभी-कभी कुंद हो जाते हैं, जिससे प्रसंस्करण में भी देरी होती है। ऐसे कुंदों का कारण विविध हो सकता है:

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

और यह किसी भी तरह से समस्याओं की एक विस्तृत सूची नहीं है जो हैंडलर को धीमा कर सकती है।

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

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

यह वास्तुकला आपको एक साथ कई समस्याओं को हल करने की अनुमति देता है:

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

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

संभाव्यता मूल्यांकन

आइए प्रदर्शन के दोहराव के लाभों का मूल्यांकन करने का प्रयास करें। मान लीजिए कि हैंडलर के साथ हर दिन औसतन कुछ होता है: या तो जीसी विस्फोट हो गया है, या नोड झूठ बोल रहा है, या कंटेनर कैंसर हो गया है। यह भी मान लीजिए कि हम 10 सेकंड में डेटा पैकेट तैयार करते हैं।

तब संभावना है कि पैक के निर्माण के दौरान कुछ होगा 10 / (24 · 3600) ≃ 1e-4 ।

यदि आप समानांतर में दो हैंडलर चलाते हैं, तो संभावना है कि दोनों मक्खियां ≃ 1e-8 । तो यह घटना 23 साल में आ जाएगी! हां, सिस्टम उतना नहीं रहता है, जिसका अर्थ है कि यह कभी नहीं होगा!

इसके अलावा, अगर पैक की तैयारी का समय और भी कम हो जाएगा और / या कुंद भी कम बार होगा, तो यह आंकड़ा केवल बढ़ेगा।

इस प्रकार, हम यह निष्कर्ष निकालते हैं कि विचाराधीन दृष्टिकोण हमारे पूरे सिस्टम की विश्वसनीयता को काफी बढ़ाता है। यह केवल इस तरह के एक छोटे से प्रश्न को हल करने के लिए बनी हुई है: जहां एक समवर्ती बिल्कुल एक बार प्रणाली बनाने के बारे में पढ़ना है। और जवाब सरल है: आपको यहां पढ़ना होगा।

आधा लेन-देन

आगे की चर्चा के लिए, हमें एक आधे लेनदेन की अवधारणा की आवश्यकता है। इसे समझाने का सबसे आसान तरीका एक उदाहरण है।

एक बैंक खाते से दूसरे खाते में धनराशि स्थानांतरित करने पर विचार करें। Pseco भाषा में लेनदेन का उपयोग करने वाले पारंपरिक दृष्टिकोण को निम्नानुसार वर्णित किया जा सकता है:

 transfer(from, to, amount): tx = db.begin_transaction() amount_from = tx.get(from) if amount_from < amount: return error.insufficient_funds tx.set(from, amount_from - amount) tx.set(to, tx.get(to) + amount) tx.commit() return ok

हालाँकि, अगर ये लेनदेन हमारे लिए उपलब्ध नहीं हैं, तो क्या होगा? ताले का उपयोग करना, यह निम्नानुसार किया जा सकता है:

 transfer(from, to, amount): #         lock_from = db.lock(from) lock_to = db.lock(to) amount_from = db.get(from) if amount_from < amount: return error.insufficient_funds db.set(from, amount_from - amount) db.set(to, db.get(to) + amount) return ok

इस दृष्टिकोण से गतिरोध पैदा हो सकता है, जैसा कि समानांतर में विभिन्न अनुक्रमों में ताले लिए जा सकते हैं। इस व्यवहार को ठीक करने के लिए, यह एक फ़ंक्शन को पेश करने के लिए पर्याप्त है जो एक साथ एक नियतकालिक अनुक्रम में कई ताले लेता है (उदाहरण के लिए, कुंजी द्वारा सॉर्ट), जो संभव गतिरोध को पूरी तरह से समाप्त कर देता है।

हालाँकि, कार्यान्वयन कुछ हद तक सरल किया जा सकता है:

 transfer(from, to, amount): lock_from = db.lock(from) amount_from = db.get(from) if amount_from < amount: return error.insufficient_funds db.set(from, amount_from - amount) lock_from.release() #   , # .. db.set(db.get...)     lock_to = db.lock(to) db.set(to, db.get(to) + amount) return ok

यह दृष्टिकोण अंतिम स्थिति को भी सुसंगत बनाता है, धन के अत्यधिक व्यय को रोकने के प्रकारों द्वारा आक्रमणकारियों को संरक्षित करना। पिछले दृष्टिकोण से मुख्य अंतर यह है कि इस तरह के कार्यान्वयन में हमारे पास एक निश्चित अवधि है जिसमें खाते असंगत स्थिति में हैं। अर्थात्, इस तरह के एक ऑपरेशन का अर्थ है कि खातों में धन की कुल स्थिति नहीं बदलती है। इस स्थिति में, lock_from.release() और db.lock(to) बीच समय अंतराल है, जिसके दौरान डेटाबेस असंगत मूल्य दे सकता है: कुल राशि सही एक नीचे से भिन्न हो सकती है।

वास्तव में, हम पैसे को दो आधे लेनदेन में स्थानांतरित करने के लिए एक लेनदेन को विभाजित करते हैं:

पहला आधा लेन-देन एक चेक बनाता है और खाते से आवश्यक राशि काटता है।
दूसरे आधे लेन-देन की आहरण राशि दूसरे खाते में लिखती है।

यह स्पष्ट है कि लेन-देन को छोटे लोगों में विभाजित करना, आम तौर पर बोलना, लेनदेन व्यवहार का उल्लंघन करता है। और उपरोक्त उदाहरण कोई अपवाद नहीं है। हालांकि, यदि श्रृंखला में सभी आधे लेनदेन पूरी तरह से पूरे होते हैं, तो परिणाम सभी आक्रमणकारियों के साथ संगत होगा जो संरक्षित हैं। यह ठीक वही है जो एक आधा लेन-देन श्रृंखला की एक महत्वपूर्ण संपत्ति है।

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

एक वैध सवाल उठता है: वितरित प्रणालियों में अर्ध-ट्रान्स को कैसे लागू किया जाए और रेक नहीं? इस समस्या को हल करने के लिए, आपको लॉक-फ्री दृष्टिकोण पर विचार करने की आवश्यकता है।

ताला मुक्त

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

कुछ डेवलपर्स कभी-कभी समझ में नहीं आते हैं कि लॉक-फ्री क्या है। संकीर्ण विचारधारा का कहना है कि यह परमाणु प्रोसेसर निर्देशों से संबंधित है। यहां यह समझना महत्वपूर्ण है कि लॉक-फ्री का अर्थ है "परमाणुओं" का उपयोग, विपरीत सच नहीं है, अर्थात सभी "एटॉमिक्स" लॉक-फ्री व्यवहार नहीं देते हैं।

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

कम से कम एक धागे की प्रगति की स्थिति की अनुपस्थिति एक लॉक-फ्री एल्गोरिथ्म की अवधारणा को क्यों नकारती है? तथ्य यह है कि इस मामले में सामान्य स्पिनलॉक भी लॉक-फ़्री होगा। वास्तव में, जिसने ताला लिया वह प्रगति करेगा। क्या प्रगति के साथ एक धागा है => लॉक-फ़्री?

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

लेकिन किसने कहा कि लॉक-फ्री दृष्टिकोण विशेष रूप से बहु-थ्रेडेड सिस्टम पर लागू होता है? विभिन्न नोड्स पर प्रक्रियाओं के साथ एक ही नोड पर एक ही प्रक्रिया में थ्रेड्स को प्रतिस्थापित करना, और साझा वितरित स्टोरेज के साथ थ्रेड्स की साझा मेमोरी, हमें लॉक-फ्री वितरित एल्गोरिदम मिलता है।

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

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

कैस

कैस या तुलना-और-अदला-बदली ताला-मुक्त और प्रतीक्षा-मुक्त एल्गोरिदम के लिए मुख्य और महत्वपूर्ण सिंक्रनाइज़ेशन आदिम है। इसका सार निम्नलिखित Pseco द्वारा दर्शाया जा सकता है:

 CAS(var, expected, new): # ,   atomic,   atomic: if var.get() != expected: return false var.set(new) return true

कभी-कभी, अनुकूलन के लिए, वे true या false नहीं लौटाते हैं, लेकिन पिछले मूल्य, क्योंकि बहुत बार इस तरह के ऑपरेशन एक लूप में किए जाते हैं, और expected मूल्य प्राप्त करने के लिए, आपको पहले इसे पढ़ना चाहिए:

 CAS_optimized(var, expected, new): # ,   atomic,   atomic: current = var.get() if current == expected: var.set(new) return current #  CAS   CAS_optimized CAS(var, expected, new): return var.CAS_optimized(expected, new) == expected

यह दृष्टिकोण एक पढ़ने को बचा सकता है। हमारी समीक्षा के भाग के रूप में, हम CAS एक सरल रूप का उपयोग करेंगे, क्योंकि यदि वांछित है, तो इस तरह के अनुकूलन को स्वतंत्र रूप से किया जा सकता है।

वितरित प्रणालियों के मामले में, प्रत्येक परिवर्तन का संस्करण होता है। यानी पहले हम स्टोर से मूल्य पढ़ते हैं, डेटा का वर्तमान संस्करण प्राप्त करते हैं। और फिर हम यह लिखने की कोशिश करते हैं, उम्मीद करते हैं कि डेटा का संस्करण नहीं बदला है। इस स्थिति में, हर बार डेटा अपडेट होने पर संस्करण बढ़ जाता है:

 CAS_versioned(var, expected_version, new): atomic: if var.get_version() != expected_version: return false var.set(new, expected_version + 1) return true

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

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

यह वह संपत्ति है जो CAS_versioned कार्रवाई CAS_versioned । वास्तव में, इस ऑपरेशन को अंतहीन दोहराया जा सकता है जब तक कि प्राप्तकर्ता से वास्तविक प्रतिक्रिया वापस नहीं आती है। जो, बदले में, नेटवर्क इंटरैक्शन से संबंधित त्रुटियों की एक पूरी कक्षा को फेंक देता है।

उदाहरण

आइए देखें कि कैसे, CAS_versioned और आधे लेनदेन के आधार पर, एक खाते से दूसरे खाते में स्थानांतरित करने के लिए, जो कि, उदाहरण के लिए, Etcd की विभिन्न प्रतियों में हैं। यहाँ, मुझे लगता है कि CAS_versioned फ़ंक्शन पहले CAS_versioned ही दिए गए API के आधार पर लागू किया गया है।

 withdraw(from, amount): # CAS- while true: #     version_from, amount_from = from.get_versioned() if amount_from < amount: return error.insufficient_funds if from.CAS_versioned(version_from, amount_from - amount): break return ok deposit(to, amount): # CAS- while true: version_to, amount_to = to.get_versioned() if to.CAS_versioned(version_to, amount_to + amount): break return ok transfer(from, to, amount): #   if withdraw(from, amount) is ok: #     , #    deposit(to, amount)

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

बारी

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

कतार में संचालन की एक जोड़ी शामिल होगी:

कतार के अंत में एक संदेश जोड़ें।
निर्दिष्ट सूचकांक पर कतार से एक संदेश प्राप्त करना।

इस संदर्भ में, मैं कई कारणों से कतार से संदेशों को हटाने पर विचार नहीं करता:

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

तत्वों को संग्रहीत करने और प्रभावी ढंग से इसके अतिरिक्त कार्यान्वयन के लिए, हमें आवश्यकता है:

वर्तमान सूचकांक के साथ मूल्य। यह सूचकांक वस्तुओं को जोड़ने के लिए कतार के अंत की ओर इशारा करता है।
, .

lock-free

: . :

CAS .
.

, , .

lock-free . , , . Lock-free? ! , 2 : . lock-free, — ! , , , . . , .. , .
. , . .

, lock-free .

Lock-free

, , : , .. , :

 push(queue, value): #      index = queue.get_current_index() while true: #  ,    #    var = queue.at(index) #  = 0   , ..   # ,         if var.CAS_versioned(0, value): #   ,    queue.update_index(index + 1) break #   , .   index = max(queue.get_current_index(), index + 1) update_index(queue, index): while true: #     cur_index, version = queue.get_current_index_versioned() #      , #  , .   if cur_index >= index: # -     , #        break if queue.current_index_var().CAS_versioned(version, index): #      ,   break # -  . # ,      ,

. , ( — , , ). lock-free . ?

, push , ! , , .

. : . , - , - . , , .. . . ? , .. , , .

, , . यानी . , , . , .

, . , . , , . , .

, , , .

. .

, :

, .. stateless.
, — .

, , concurrent exactly-once .

 handle(input, output): index = 0 while true: value = input.get(index) output.push(value) index += 1

. :

 handle(input, output, state): #   index = state.get() while true: value = input.get(index) output.push(value) index += 1 #   state.set(index)

exactly-once . , , , .

exactly-once , , . .., , , , , — :

 #       get_next_index(queue): index = queue.get_index() #     while queue.has(index): #    queue.push index = max(index + 1, queue.get_index()) return index #      . #  true    push_at(queue, value, index): var = queue.at(index) if var.CAS_versioned(0, value): #   queue.update_index(index + 1) return true return false handle(input, output, state): #   #    {PREPARING, 0} fsm_state = state.get() while true: switch fsm_state: case {PREPARING, input_index}: #   :   , #        output_index = output.get_next_index() fsm_state = {WRITING, input_index, output_index} case {WRITING, input_index, output_index}: value = input.get(input_index) if output.push_at(value, output_index): #  ,     input_index += 1 #    ,  push_at  false, #        fsm_state = {PREPARING, input_index} state.set(fsm_state)

push_at ? , . , , , . , . . - , lock-free .

, :

: .
, : .

: concurrent exactly-once .

? :

, , push_at false. .
, . , , .

concurrent exactly-once ? , , . , . .

 #     ,  ,     # ..       true, #      true. #       false push_at_idempotent(queue, value, index): return queue.push_at(value, index) or queue.get(index) == value handle(input, output, state): version, fsm_state = state.get_versioned() while true: switch fsm_state: case {PREPARING, input_index}: #   ,   , #        output_index = output.get_next_index() fsm_state = {WRITING, input_index, output_index} case {WRITING, input_index, output_index}: value = input.get(input_index) #   , #       if output.push_at_idempotent(value, output_index): input_index += 1 fsm_state = {PREPARING, input_index} #     if state.CAS_versioned(version, fsm_state): version += 1 else: #   ,    version, fsm_state = state.get_versioned()

सरल

, . , .

kernel panic, , .. . . : , . , .

, , .

: .

: , , , , :

 #  : # - input_queues -   # - output_queues -   # - state -    # - handler -    : state, inputs -> state, outputs handle(input_queues, output_queues, state, handler): #        version, fsm_state = state.get_versioned() while true: switch fsm_state: # input_indexes       case {HANDLING, user_state, input_indexes}: #       inputs = [queue.get(index) for queue, index in zip(input_queues, input_indexes)] #   ,    next_indexes = next(inputs, input_indexes) #    #     user_state, outputs = handler(user_state, inputs) #      , #     fsm_state = {PREPARING, user_state, next_indexes, outputs, 0} case {PREPARING, user_state, input_indexes, outputs, output_pos}: #  ,      #    output_index = output_queues[output_pos].get_next_index() #     fsm_state = { WRITING, user_state, input_indexes, outputs, output_pos, output_index } case { WRITING, user_state, input_indexes, outputs, output_pos, output_index }: value = outputs[output_pos] #       if output_queues[output_pos].push_at_idempotent( value, output_index ): #  ,      output_pos += 1 #    ,      PREPARING. #     #     fsm_state = if output_pos == len(outputs): #   , #       {HANDLING, user_state, input_indexes} else: #       #   , #         {PREPARING, user_state, input_indexes, outputs, output_pos} if state.CAS_versioned(version, fsm_state): version += 1 else: #   ,    version, fsm_state = state.get_versioned()

अंतिम

: HANDLING . , .., , . , . , PREPARING WRITING , . , HANDLING .

, , , . , . , .

. . .

अंतिम

 my_handler(state, inputs): #      state.queue.push(inputs) #    duration state.queue.trim_time_window(duration) #   avg = state.queue.avg() need_update_counter = state.queue.size() > size_boundary return state, [ avg, if need_update_counter: true else: # none      none ]

, , concurrent exactly-once handle .

 handle_db(input_queue, db): while true: #      tx = db.begin_transaction() #     . #      , #      index = tx.get_current_index() #    tx.write_current_index(index + 1) #      value = intput_queue.get(index) if value: #    tx.increment_counter() tx.commit() #   ,      , #

. क्योंकि , , , , concurrent exactly-once . .

— . , , .

, , . , , .

. , . क्योंकि , . . .

— . , , . , - , , . , .. , , .

. , , . , , .

. , . : , . , .

, , :

, . .
. , .
. , . , , . यानी . : .

, , -, , -, .

, . :

 transfer(from, to, amount): #   if withdraw(from, amount) is ok: #     , #    deposit(to, amount)

withdraw , , deposit : ? deposit - (, , ), . , , , , ? , , - , .

, , , . , , , . , . , , . क्योंकि , , . , : , — .

, .

: , , , , . , - :

. , , , , .
. .

, , .

, , .. , , . , .

: lock-free , . , .. , .

CAS . , :

 #     ,    handle(input, output, state): # ... while true: switch fsm_state: case {HANDLING, ...}: #      fsm_state = {PREPARING, ...} case {PREPARING, input_index}: #   ... output_index = ...get_next_index() fsm_state = {WRITING, output_index, ...} case {WRITING, output_index, ...}: #  ,  output_index

, . . :

PREPARING . , .
WRITING . . , PREPARING .

, . , , — . :

. , , .. , .
, .. . , .

, lock-free , , .

, . , Stale Read , . — CAS: . :

Distributed single register — (, etcd Zookeeper):
1. Linearizability
2. Sequential consistency
Transactional — (, MySQL, PostgreSQL ..):
1. Serializability
2. Snapshot Isolation
3. Repeatable Read
4. Read Committed
Distributed Transactional — NewSQL :
1. Strict Consistency

: ? , , . , , CAS . , , Read My Writes .

निष्कर्ष

exactly-once . , .. , , , . , , , , .. , .

lock-free .

: .
: .
: : exactly-once .
Concurrent : .
Real-time : .
Lock-free : , .
Deadlock free : , .
Race condition free : .
Hot-hot : .
Hard stop : .
No failover : .
No downtime : .
: , .
: .
: .
: .

, . लेकिन वह एक और कहानी है।

प्रकाश

Concurrent exactly-once.
Semi-transactions .
Lock-free two-phase commit, .

.
lock-free .
.

साहित्य

[1] : ABA.
[2] Blog: You Cannot Have Exactly-Once Delivery
[3] : .
[4] : 3: .
[5] : .

वास्तविक समय विषम प्रतिस्पर्धी डेटा प्रसंस्करण सख्ती से एक बार

अमूर्त

परिचय

समस्या का बयान

वास्तव में-एक बार

समकालिक-एक बार

लेन-देन संबंधी

प्रतिस्पर्धात्मक प्रतिक्रिया

संभाव्यता मूल्यांकन

आधा लेन-देन

ताला मुक्त

कैस

उदाहरण

बारी

lock-free

Lock-free

निष्कर्ष

साहित्य

More articles: