क्रमणीयता

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 नया है, हालांकि) संघर्ष क्रमबद्धता और अनुसूची (कंप्यूटर विज्ञान) दोनों को लागू करने के लिए #Strict ( पुनर्प्राप्ति योग्यता का एक विशेष मामला जो किसी शेड्यूल की विफलता से प्रभावी डेटाबेस पुनर्प्राप्ति की अनुमति देता है)। इस तंत्र के तहत, प्रत्येक डाटाम को लेनदेन तक पहुंचने से पहले लॉक किया जाता है (किसी भी पढ़ने या लिखने के संचालन में): आइटम को एक निश्चित प्रकार के लॉक (कंप्यूटर साइंस) द्वारा चिह्नित किया जाता है और ऑपरेशन के आधार पर किया जाता है (और विशिष्ट लेन-देन कार्यान्वयन; विभिन्न प्रकार के लॉक वाले विभिन्न मॉडल मौजूद हैं; कुछ मॉडलों में, लेन-देन के जीवन के दौरान ताले प्रकार बदल सकते हैं)। नतीजतन, किसी अन्य लेन-देन द्वारा पहुंच को अवरुद्ध किया जा सकता है, आम तौर पर एक विरोध पर (ताला देरी या पूरी तरह से संघर्ष को भौतिक होने से रोकता है और विरोधाभासी संचालन को अवरुद्ध करके पूर्ववर्ती ग्राफ में परिलक्षित होता है), लॉक प्रकार और अन्य लेनदेन के आधार पर एक्सेस ऑपरेशन प्रकार। SS2PL तंत्र को नियोजित करने का अर्थ है कि लेन-देन की ओर से डेटा पर सभी ताले केवल लेन-देन समाप्त होने (या तो प्रतिबद्ध या निरस्त) के बाद जारी किए जाते हैं।

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

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

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

अन्य ज्ञात तंत्रों में शामिल हैं:

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

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

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

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

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

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

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

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

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

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

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

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

अवलोकन

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

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

यह भी देखें

• दो-चरण लॉकिंग | मजबूत सख्त दो-चरण लॉकिंग (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