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

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

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

समस्याओं

जैसा कि पहले ही उल्लेख किया गया है, तार्किक घड़ी के साथ कई समस्याएं हैं:

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

निर्णय

क्रोनोस का एक 2014 का लेख : इवेंट ऑर्डरिंग सर्विस का डिज़ाइन और कार्यान्वयन एक प्रस्ताव पेश करता है - एक स्टैंड-अलोन सेवा जो घटनाओं में कारण-प्रभाव संबंधों को ध्यान में रखेगा।

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

न्यूनतम एपीआई को तरीकों के निम्नलिखित सेट द्वारा परिभाषित किया जा सकता है:

विधि	परिणाम	टिप्पणी
`create_event()`	`e`	क्रोनोस में एक नई घटना बनाता है
`query_order([(e_1, e_2), ...])`	`[<-, concurrent, ->, ...]`	अनुरोध की प्रत्येक जोड़ी के लिए, यह कारण-और-प्रभाव संबंध दिशा, या घटनाओं की एकरूपता लौटाता है
`assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...])`	`OK/FAIL`	अनुरोध के प्रत्येक जोड़े के लिए, कार्य-कारण की दिशा निर्धारित करता है
`acquire_ref(e)`	`OK`	इस घटना के लिए संदर्भ काउंटर बढ़ाता है।
`release_ref(e)`	`OK`	इस घटना के लिए संदर्भ संख्या घटाता है।

कार्यान्वयन

यह तर्कसंगत है कि सिस्टम घटनाओं के उन्मुख ग्राफ पर आधारित है, जिसमें घटनाओं के संबंध, विफलता के मामले में एक स्थिरता तंत्र, और कचरा संग्रह की जांच करने के लिए एक प्रभावी चौड़ाई-पहली खोज है।

जैसा कि एपीआई से देखा जा सकता है, assign_order अनुरोध assign_order एक कारण संबंध प्रकार को स्वीकार करता है: must या prefer must । कड़ाई से हमलावरों से मेल must - उदाहरण के लिए, _->_ , prefer नहीं किया जा सकता है अगर यह रिश्तों के साथ संघर्ष करता है। prefer का उपयोग करने का एक उदाहरण यह है कि पहले आए अनुरोध बेहतर तरीके से पहले से लिपटे हुए हैं, लेकिन यह शुद्धता को प्रभावित नहीं करता है।

प्रभावी बी.एफ.एस.

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

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

कचरा संग्रह

जैसा कि आप तालिका से देख सकते हैं, दो और विधियाँ हैं: acquire_ref और release_ref ।

क्रोनोस के अंदर, प्रत्येक घटना के लिए एक संदर्भ काउंटर संग्रहीत किया जाता है। हालांकि कुछ सेवा घटना को संसाधित करती है, या वर्तमान के बाद होने वाली नई घटनाओं को जोड़ने की क्षमता रखती है, यह लिंक को संग्रहीत करता है। जब यह आवश्यकता गायब हो जाती है, तो सेवा release_ref कॉल करती है।

क्रोनोस इवेंट को तब हटाएगा जब सभी शर्तें पूरी हो जाएंगी:

लिंक की संख्या शून्य तक पहुंच गई
इससे पहले होने वाली सभी घटनाओं को पहले ही ग्राफ से हटा दिया जाता है।

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

क्षुधा

वितरित लेनदेन के साथ की-वैल्यू स्टोरेज के उदाहरण का उपयोग करके सिस्टम के उपयोग पर विचार करें।

मान लीजिए कि कई सर्वर हैं, प्रत्येक सर्वर कुंजियों की एक श्रृंखला के लिए जिम्मेदार है।

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

यदि सभी ऐड डिपेंडेंसी ऑपरेशन सफलतापूर्वक पूरा हो गया है - इसका मतलब है कि लेन-देन होगा और यह किया जा सकता है। ग्राहक क्लाइंट से इस बारे में सीखते हैं और लेनदेन के कुछ हिस्सों को निष्पादित करना शुरू करते हैं।

ध्यान दें कि ऐसे लेनदेन ACID होंगे :

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

उत्पादकता

ऐसे केवी भंडारण को लागू करना वास्तव में प्रभावी हो सकता है। मूल लेख डेटा का हवाला देता है कि केवी-भंडारण का वर्णित कार्यान्वयन तालों के आधार पर लेनदेन की तुलना में 4 गुना तेज है।

इसके अलावा, MongoDB के साथ तुलना में, क्रोनोस के शीर्ष पर सिस्टम केवल 6% पीछे है, इस तथ्य के बावजूद कि MongoDB वितरित लेनदेन का उपयोग नहीं करता है।

के विश्लेषण

हालांकि, क्रोनोस के संचालन में कई नुकसान हैं।

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

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

निष्कर्ष

इसके बारे में, हम GoTo स्कूल में वितरित सिस्टम की दिशा में छात्रों और स्कूली बच्चों को पढ़ाते हैं।

और एल्गोरिदम और अनुप्रयोग , एप्लाइड प्रोग्रामिंग, जैव सूचना विज्ञान और डेटा विश्लेषण हैं

27 अक्टूबर को हमारे शरद ऋतु स्कूल में आओ - 4 नवंबर या जनवरी की शुरुआत में शीतकालीन स्कूल ।

और अगर आप एक छात्र या एक स्कूली छात्र नहीं हैं - सिखाने के लिए आते हैं ।

क्रोनोस: वितरित प्रणालियों में भी कोई समय यात्रा नहीं