क्रमणीयता: Difference between revisions

[[डेटाबेस]] के समवर्ती नियंत्रण <ref name=Bernstein87>[[Phil Bernstein|Philip A. Bernstein]], Vassos Hadzilacos, Nathan Goodman (1987): [http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx ''Concurrency Control and Recovery in Database Systems''] (free PDF download), Addison Wesley Publishing Company, {{ISBN|0-201-10715-5}}</ref><ref name=Weikum01>[[Gerhard Weikum]], Gottfried Vossen (2001): [http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description ''Transactional Information Systems''], Elsevier, {{ISBN|1-55860-508-8}}</ref> लेन-देन प्रसंस्करण (लेन-देन प्रबंधन) और विभिन्न डेटाबेस लेनदेन अनुप्रयोग (जैसे, लेनदेन संबंधी मेमोरी<ref name=Herlihy1993>[[Maurice Herlihy]] and J. Eliot B. Moss. ''Transactional memory: architectural support for lock-free data structures.'' Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.</ref> और [[सॉफ्टवेयर लेनदेन स्मृति]]), केंद्रीकृत और वितरित कंप्यूटिंग दोनों एक लेनदेन [[अनुसूची (कंप्यूटर विज्ञान)|सूची]]  में क्रमबद्ध है यदि इसका परिणाम (उदाहरण के लिए, परिणामी डेटाबेस स्थिति) क्रमिक रूप से निष्पादित लेनदेन समय में ओवरलैप किए बिना परिणाम के बराबर है। लेन-देन सामान्यतः समवर्ती रूप से निष्पादित होते हैं (वे ओवरलैप होते हैं), क्योंकि यह सबसे कुशल तरीका है। क्रमबद्धता समवर्ती लेनदेन के निष्पादन के लिए प्रमुख शुद्धता मानदंड है{{Citation needed|date=February 2018}}. इसे डेटाबेस लेनदेन के बीच उच्चतम स्तर का [[अलगाव (कंप्यूटर विज्ञान)|अलगाव]]  माना जाता है, और समवर्ती नियंत्रण में एक आवश्यक भूमिका निभाता है। जैसे कि यह सभी सामान्य प्रयोजन डेटाबेस प्रणाली में समर्थित है। [[दो चरण का ताला|स्ट्रॉन्ग स्ट्रिक्ट टू-फेज]]  अवरोध (SS2PL) एक लोकप्रिय क्रमिक क्रियाविधि है जिसका उपयोग 1970 के शुरुआती दिनों से अधिकांश डेटाबेस प्रणाली (विभिन्न रूपों में) में किया जाता है।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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