क्रमणीयता

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

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

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

शुद्धता

क्रमबद्धता

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

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

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

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

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

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

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

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

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

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

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

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