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

{{Short description|If a transaction schedule's outcome is unchanged when executed concurrently or serially}}डेटाबेस के '''क्रमणीयता''' नियंत्रण <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> और सॉफ्टवेयर आदान-प्रदान मेमोरी) दोनों केंद्रीकृत और वितरित है,आदान-प्रदान [[अनुसूची (कंप्यूटर विज्ञान)|सूची]] में क्रमबद्ध है यदि इसका परिणाम (उदाहरण के लिए, परिणामी डेटाबेस स्थिति) क्रमिक रूप से निष्पादित आदान-प्रदान समय में ओवरलैप किए बिना परिणाम के बराबर है। आदान-प्रदान सामान्यतः क्रमणीयता रूप से निष्पादित होते हैं (वे ओवरलैप होते हैं), क्योंकि यह सबसे कुशल विधि है। क्रमबद्धता क्रमणीयता आदान-प्रदान के निष्पादन के लिए प्रमुख शुद्धता मानदंड है. इसे डेटाबेस आदान-प्रदान के बीच उच्चतम स्तर का [[अलगाव (कंप्यूटर विज्ञान)|पृथक्रकरण]]  माना जाता है, और क्रमणीयता नियंत्रण में एक आवश्यक भूमिका निभाता है। जैसे कि यह सभी सामान्य प्रयोजन डेटाबेस प्रणाली में समर्थित है। [[दो चरण का ताला|स्ट्रॉन्ग स्ट्रिक्ट टू-फेज]]  लॉकिंग (SS2PL) एक लोकप्रिय क्रमिक क्रियाविधि है जिसका उपयोग 1970 के प्रारंभ दिनों से अधिकांश डेटाबेस प्रणाली (विभिन्न रूपों में) में किया जाता है।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

सूची के प्रतिबद्ध आदान-प्रदान के लिए संघर्ष अ�