समय खंडित है; वितरित सिस्टम और एक कमजोर मेमोरी मॉडल की समानता के बारे में थोड़ा सा

सभी को नमस्कार!

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

कंप्यूटर विज्ञान में केवल एक वास्तविक समस्या है: यह स्वीकार करना कि कैश अमान्य त्रुटियों को गलत नाम दिया गया है। ये केवल समय के उपयोग से संबंधित इकाई त्रुटियां हैं।

- अज्ञात लेखक

समय बड़ी अजीब चीज है।

यह समय बहुत अजीब है, क्योंकि हम वास्तव में, वास्तव में विश्वास करना चाहते हैं कि यह पूरी तरह से सुव्यवस्थित है। यह हमें लगता है कि 15.00 बजे कोई भी घटना घटती है (जैसा कि हम कहेंगे) 16.00 बजे किसी भी घटना से पहले - बिना किसी अपवाद, तर्क या समझौते के।

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

क्यों? तथ्य यह है कि हम इसे नहीं जानते हैं, क्योंकि अमूर्तता का स्तर जिसके ऊपर हम मौजूद हैं, इस प्रश्न का उत्तर प्रदान नहीं करता है। यह आकस्मिक है या नहीं, हमारे कम्प्यूटेशनल अमूर्त प्रक्रिया के बारे में गारंटी नहीं देते हैं। घटनाओं को पुन: व्यवस्थित करने की स्वतंत्रता अक्सर आपको बहुत अधिक उत्पादक और सस्ती प्रणाली बनाने की अनुमति देती है।

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

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

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

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

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

लेकिन समय खंडित है - इसलिए, इस तरह के प्रश्न को उठाना आवश्यक है।

संगति मॉडल - मेरा मतलब है, स्मृति मॉडल

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

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

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

हम पहले से ही कल्पना करते हैं कि यह कितना भ्रमित हो सकता है। क्या करें?

एक इकाई के रूप में समय का विवरण, आंशिक आदेश के दो से आठ प्रकार से कहीं न कहीं

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

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

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

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

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

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

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

अंतत: सुसंगतता

किसी विशेष घटना के लिए, अनिश्चित काल तक कई आयोजन नहीं हो सकते हैं जो इसे नहीं देखते हैं। यही है, कोई भी घटना अंततः सिस्टम को दिखाई देती है।

तार्किक रूप से कमजोर मेमोरी मॉडल वाले सिस्टम में ऐसी स्थितियां बनाना कुछ अधिक कठिन होना चाहिए: यह तर्क दिया जाना चाहिए कि किसी विशेष रिकॉर्ड के लिए अनंत संख्या में रीड ऑपरेशंस नहीं हो सकते हैं जो इस रिकॉर्ड या पिछले रिकॉर्ड्स (संशोधन क्रम में) को नहीं पढ़ेंगे।

C ++ 11 विनिर्देश में, इस स्वयंसिद्ध के अनुपालन की गारंटी नहीं है, हालांकि व्यवहार में यह प्रतिधारण को खोजना मुश्किल है।

ईथर की संगति

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

बर्कहार्ट एट अल। इंगित करें कि यह स्वयंसिद्ध C ++ 11 विनिर्देश में "पुष्टि नहीं" है, और यह स्पष्ट नहीं है कि "मान्य नहीं है" क्या "संतोषजनक चक्र" व्यवहार में देखे जा सकते हैं।

सशर्तता की अभिव्यक्ति

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

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

WFR और MW के मूल संस्करण यादृच्छिकता और दृश्यता के लिए दो संस्करणों में मौजूद हैं; पूर्णांक के लिए रजिस्टरों की तुलना में अधिक जटिल डेटा कोशिकाओं के साथ काम करते समय यह केवल महत्वपूर्ण है।

ये गुण हमारे सामान्य ज्ञान के अनुरूप, सशर्तता की धारणाओं को दर्शाते हैं; हालांकि, वे सबसे दिलचस्प याद करते हैं। विशेष रूप से, जब एक कमजोर मेमोरी मॉडल का विश्लेषण करते हैं, तो ऐसी स्थिति की स्थिति प्रवाह / प्रतिकृति / सत्र और विशिष्ट सेल / ऑब्जेक्ट की सीमा तक सीमित होती है जहां प्रवेश किया जाता है: बर्कहार्ट एट अल द्वारा एक लेख में । इस मामले में यह "ऑब्जेक्ट-बाय-कंडीशनल कंडीशनल विजिबिलिटी" और "ऑब्जेक्ट-बाय-कंडीशनल आर्बिट्रल आर्बिट्रेशन" के बारे में कहा जाता है। 23. ये घटनाएं सिस्टम के व्यवहार को पूरी तरह से सीमित नहीं करती हैं जब विभिन्न धाराएं विभिन्न कोशिकाओं को जानकारी लिखती हैं।

फिर क्रॉस-ऑब्जेक्ट कंडीशनिंग के स्वयंसिद्ध विभिन्न वस्तुओं / स्मृति कोशिकाओं के स्तर पर कारण-प्रभाव संबंधों के प्रभाव का वर्णन करते हैं।

• सीओसीवी (क्रॉस-ऑब्जेक्ट कंडिशनल विजिबिलिटी): आरवाईडब्ल्यू जैसा ही मामला, लेकिन इस शर्त के बिना कि अंतिम रीड को एक ही थ्रेड / रेप्लिका / सेशन में किया जाना चाहिए। किसी ऑब्जेक्ट से रीडिंग जो इस ऑब्जेक्ट में रिकॉर्ड की तुलना में बाद में होती हैं, रिकॉर्डिंग के दौरान दर्ज किए गए डेटा से कम प्रासंगिक नहीं होना चाहिए।

C ++ 11 विनिर्देश इन गुणों को दर्शाता है। कृपया ध्यान दें: उन्हें इस तरह से परिभाषित किया गया है कि दृश्यता की रिकॉर्डिंग पर प्रतिबंध और संशोधन आदेश की मनमानी इन परिभाषाओं पर बहुत अधिक प्रतिबिंबित नहीं करती है।

लेकिन यह बाद की संपत्ति पर लागू नहीं होता है।

• COCA (क्रॉस-ऑब्जेक्ट कंडिशनल आर्बिटवर्ल्ड): मोनोलिथिक रिकॉर्ड्स के समान, लेकिन COCV के समान विभिन्न धाराओं पर लागू होता है - यह विभिन्न धाराओं के लिए RYW है। हालाँकि, संशोधन आदेश केवल एक वस्तु में रिकॉर्ड को प्रभावित करता है, एक कमजोर मेमोरी मॉडल के लिए सूत्रीकरण प्रणाली को विभिन्न वस्तुओं में रिकॉर्डिंग घटनाओं के असंगत वितरण की अनुमति देता है, और रिकॉर्ड या तो रीडिंग या स्ट्रीम के अंदर ऑर्डर के अनुरूप नहीं हो सकते हैं।

विशेष रूप से, एक कमजोर मेमोरी मॉडल में COCA एक बहुत कमजोर संपत्ति है। यही कारण है कि एक कमजोर मेमोरी मॉडल के साथ, निम्न कोड {x ≡ 0, y ≡ 0} वापस आ सकता है।

Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return y

प्रत्येक स्ट्रीम के भीतर ऑर्डर ऑब्जेक्ट-बाय-ऑर्डर ऑर्डर और संशोधन ऑर्डर के साथ असंगत हो सकता है। कृपया ध्यान दें: RYW के साथ कोई x := 0 → x := 1 नहीं है x := 0 → x := 1 संशोधन क्रम में और y समान है; इस प्रकार, संशोधन क्रम में x := 1 → x := 0 और y := 1 → y := 0 । इस प्रकार, संशोधन आदेश स्पष्ट रूप से प्रवाह के क्रम में एक चक्र बनाता है।
कमजोर मेमोरी मॉडल के साथ COCA में इस तरह के लूप की अनुमति है। ऐसा नहीं है कि धाराओं / रीड्स का क्रम संशोधन के आदेश के विपरीत है, लेकिन यह कि प्रत्येक धारा एक सुसंगत रिकॉर्ड इतिहास देखती है। ये कहानियाँ अन्य प्रवाह की कहानियों के अनुरूप हैं यदि हम उद्देश्यपूर्ण रूप से उनके आवेदन के दायरे को सीमित करते हैं।

इस सबका क्या मतलब है?

समय खंडित है।

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

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

समय खंडित है। शायद हमें बस इसकी आदत डालने की जरूरत है।