क्रमणीयता

This article is about serializability of database transactions. For serialization of objects in object-oriented languages, see serialization.

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

'क्रमबद्धता सिद्धांत' क्रमबद्धता और इसकी तकनीकों के बारे में तर्क और विश्लेषण करने के लिए औपचारिक ढांचा प्रदान करता है। यद्यपि यह प्रकृति गणित में है, इसके मूल सिद्धांतों को अनौपचारिक रूप से (बिना गणित अंकन के) नीचे प्रस्तुत किया गया है।

शुद्धता

क्रमबद्धता

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

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

क्रमबद्धता के पीछे तर्क निम्नलिखित है:

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

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

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

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

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

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

आराम से क्रमबद्धता

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

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

नतीजतन, आशावादी प्रतिकृति (आलसी प्रतिकृति) का सामान्यतः उपयोग किया जाता है (उदाहरण के लिए, Google, Amazon.com, Yahoo, और इसी तरह के कई उत्पादों और सेवाओं में), जबकि क्रमबद्धता को आराम दिया जाता है और अंतिम स्थिरता के लिए समझौता किया जाता है। फिर से, इस मामले में, केवल उन अनुप्रयोगों के लिए छूट दी जाती है जिन्हें इस तकनीक से नुकसान होने की उम्मीद नहीं है।

सूचीयों के वर्गों को आराम से क्रमिकता गुणों द्वारा परिभाषित किया गया है या तो क्रमबद्धता वर्ग सम्मिलित है, या इसके साथ अतुलनीय हैं।

देखें और विरोध क्रमबद्धता

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

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

एक सूची की 'व्यू-क्रमबद्धता' को समान लेन-देन के साथ एक क्रमिक सूची (कोई ओवरलैपिंग लेनदेन नहीं) के समतुल्य द्वारा परिभाषित किया गया है, जैसे कि दो सूची में संबंधित लेनदेन समान डेटा मान पढ़ते और लिखते हैं (समान डेटा मान देखें)।

एक सूची की 'कॉन्फ्लिक्ट-क्रमबद्धता' एक ही लेन-देन के साथ एक क्रमिक सूची (कोई ओवरलैपिंग लेन-देन नहीं) के समतुल्यता द्वारा परिभाषित की जाती है, जैसे कि दोनों सूची में संबंधित कालानुक्रमिक रूप से परस्पर विरोधी संचालन के जोड़े के समान सेट होते हैं (संबंधित परस्पर विरोधी के समान पूर्वता संबंध) संचालन)।

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

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

लेन-देन परस्पर विरोधी ऑपरेशन जारी / अनुरोध कर सकता है और दूसरे लेनदेन के साथ संघर्ष में हो सकता है, जबकि इसके परस्पर विरोधी संचालन में (उदाहरण के लिए, एक लॉक द्वारा अवरुद्ध) विलंबित और निष्पादित नहीं होती है । केवल निष्पादित (संतृप्त) परस्पर विरोधी संचालन संघर्ष क्रमबद्धता के लिए प्रासंगिक हैं (नीचे अधिक देखें)।

विरोध क्रमबद्धता लागू करना

परीक्षण संघर्ष क्रमबद्धता

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

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

'टिप्पणी:' कई पाठ्य पुस्तकों में केवल प्रतिबद्ध लेन-देन ही अग्रता ग्राफ में सम्मिलित हैं। बाद की चर्चाओं में सुविधा के लिए यहां सभी लेनदेन सम्मिलित किए गए हैं।

निम्नलिखित अवलोकन 'संघर्ष क्रमिकता का प्रमुख लक्षण वर्णन' है:

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

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

क्रमिकता-प्रवर्तन क्रियाविधि सामान्यतः डेटा संरचना के रूप में एक पूर्वता ग्राफ को बनाए नहीं रखते हैं, बल्कि चक्र को पूरी तरह से रोकते हैं या तोड़ते हैं (उदाहरण के लिए, नीचे SS2PL)।

सामान्य क्रियाविधि — SS2PL

Main article: Two-phase locking

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

SS2PL परिणामी सूची गुण का भी नाम है, जिसे कठोरता भी कहा जाता है। SS2PL दो-चरण अवरोध (2PL) का एक विशेष मामला (उचित उपसमुच्चय) है ।

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

अन्य लागू करने वाली तकनीक

अन्य ज्ञात क्रियाविधि में सम्मिलित हैं:

• वरीयता ग्राफ (या क्रमांकन ग्राफ, संघर्ष ग्राफ) चक्र उन्मूलन
• टू-फेज अवरोध (2PL)
• टाइमस्टैम्प आधारित समवर्ती नियंत्रण (TO)
• स्नैपशॉट आइसोलेशन आइसोलेशन को क्रमिक करने योग्य बनाना (क्रमिक करने योग्य एसआई)

उपरोक्त (संघर्ष) क्रमिकता तकनीक अपने सामान्य रूप में पुनर्प्राप्ति योग्यता प्रदान नहीं करती है। पुनर्प्राप्ति योग्यता जोड़ने के लिए विशेष संवर्द्धन की आवश्यकता है।

आशावादी बनाम निराशावादी तकनीक

समवर्ती नियंत्रण तकनीक प्रमुख तीन प्रकार की हैं

1. निराशावादी: निराशावादी समवर्ती नियंत्रण में, एक लेन-देन संघर्षों पर अन्य लेनदेन के डेटा एक्सेस संचालन को अवरुद्ध करता है, और अवरोधन को हटाए जाने तक तक विरोध अ-संतृप्त होते हैं असंतृप्त होते हैं। यह सुनिश्चित करने के लिए किया जाता है कि संचालन जो क्रमबद्धता का उल्लंघन कर सकते हैं (और अभ्यास में भी पुनर्प्राप्ति योग्यता) नहीं होते हैं।
2. आशावादी: आशावादी समवर्ती नियंत्रण में, अन्य लेन-देन के डेटा एक्सेस ऑपरेशंस संघर्षों पर अवरुद्ध नहीं होते हैं, और संघर्ष तुरंत संतृप्त हो जाते हैं। जब लेन-देन तैयार अवस्था में पहुँच जाता है, यानी, इसकी चालू अवस्था पूरी हो चुकी होती है, तो लेन-देन के संचालन (अन्य चल रहे लेन-देन के सापेक्ष) द्वारा संभावित क्रमिकता (और व्यवहार में भी पुनर्प्राप्ति) के उल्लंघन की जाँच की जाती है: यदि उल्लंघन हुआ है, तो लेनदेन सामान्यतः होता है निरस्त किया गया (कभी-कभी क्रमिकता उल्लंघन को संभालने के लिए किसी अन्य लेनदेन को रद्द करना पसंद किया जाता है)। अन्यथा, यह प्रतिबद्ध है।
3. अर्ध-आशावादी: क्रियाविधि जो कुछ स्थितियों में अवरोधन को अन्य स्थितियों में अवरुद्ध नहीं करते हैं और संतृप्त और अ-संतृप्त संघर्ष दोनों को नियोजित करते हैं।

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

जब तक सूची क्लास स्वाभाविक रूप से अवरुद्ध नहीं होते हैं (यानी, उन्हें डेटा-एक्सेस ऑपरेशंस ब्लॉक किए बिना लागू नहीं किया जा सकता है; उदाहरण के लिए, 2PL, SS2PL और SCO ऊपर; चार्ट देखें), उन्हें आशावादी तकनीकों (जैसे, क्रमबद्धता, रिकवरेबिलिटी) का उपयोग करके भी लागू किया जा सकता है।

क्रमबद्ध बहु-संस्करण समवर्ती नियंत्रण

बहुसंस्करण समवर्ती नियंत्रण (आंशिक कवरेज) और स्नैपशॉट आइसोलेशन भी देखें स्नैपशॉट आइसोलेशन में क्रमबद्ध स्नैपशॉट आइसोलेशन

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

एमवीसीसी आजकल आराम से क्रमबद्धता (ऊपर देखें) विधि स्नैपशॉट आइसोलेशन (एसआई) के माध्यम से विशेष रूप से लोकप्रिय है, जो कि अधिकांश ज्ञात क्रमबद्धता क्रियाविधि (कुछ मामलों में संभावित क्रमबद्धता उल्लंघन की कीमत पर) से बेहतर प्रदर्शन प्रदान करता है।SerializableSI, जो इसे क्रमिक बनाने के लिए SI का एक कुशल संवर्द्धन है, का उद्देश्य एक कुशल क्रमिक समाधान प्रदान करना है। SerializableSI का विश्लेषण [5] [6] MVCC के एक सामान्य सिद्धांत के माध्यम से किया गया है।

वितरित क्रमबद्धता

अवलोकन

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

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

यह भी देखें

• दो-चरण अवरोध | मजबूत सख्त दो-चरण अवरोध (SS2PL या कठोरता)।
• स्नैपशॉट आइसोलेशन # स्नैपशॉट आइसोलेशन को क्रमिक करने योग्य बनानास्नैपशॉट अलगाव में।
• वैश्विक क्रमिकता, जहां वैश्विक क्रमिकता समस्या और इसके प्रस्तावित समाधान वर्णित हैं।
• रेखीयता, समवर्ती कंप्यूटिंग में एक अधिक सामान्य अवधारणा।

संदर्भ

• Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987): Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, ISBN 0-201-10715-5
• Gerhard Weikum, Gottfried Vossen (2001): Transactional Information Systems, Elsevier, ISBN 1-55860-508-8