क्रमणीयता: Difference between revisions
No edit summary |
No edit summary |
||
| (24 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|If a transaction schedule's outcome is unchanged when executed concurrently or serially}} | {{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 | |||
|author = Gray, J. | |author = Gray, J. | ||
|author2 = Helland, P. | |author2 = Helland, P. | ||
| Line 43: | Line 39: | ||
|author-link = Jim Gray (computer scientist) | |author-link = Jim Gray (computer scientist) | ||
}}{{dead link|date=May 2018 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> | }}{{dead link|date=May 2018 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> | ||
परिणामस्वरूप, [[आशावादी प्रतिकृति]] (आलसी प्रतिकृति) का सामान्यतः उपयोग किया जाता है (उदाहरण के लिए, [[Google]], Amazon.com, [[Yahoo]], और इसी तरह के कई उत्पादों और सेवाओं में), जबकि क्रमबद्धता को आराम दिया जाता है और [[अंतिम स्थिरता]] के लिए समझौता किया जाता है। फिर से, इस स्थिति में, केवल उन अनुप्रयोगों के लिए छूट दी जाती है जिन्हें इस तकनीक से क्षति होने की उम्मीद नहीं है। | |||
सूचीयों के वर्गों को आराम से क्रमिकता गुणों द्वारा परिभाषित किया गया है या तो क्रमबद्धता वर्ग सम्मिलित है, या इसके साथ अतुलनीय हैं। | |||
== देखें और विरोध क्रमबद्धता == | == देखें और विरोध क्रमबद्धता == | ||
क्रमिकता को लागू करने वाले | क्रमिकता को लागू करने वाले क्रियाविधि को [[रीयल-टाइम कंप्यूटिंग|वास्तविक -समय]] में या लगभग वास्तविक समय में निष्पादित करने की आवश्यकता होती है, जबकि आदान-प्रदान उच्च दर पर चल रहे होते हैं। इस आवश्यकता को पूरा करने के लिए, क्रमबद्धता के विशेष स्थिति, क्रमबद्धता के लिए पर्याप्त अनुबंध जिन्हें प्रभावी ढंग से लागू किया जा सकता है, का उपयोग किया जाता है। | ||
क्रमबद्धता के दो प्रमुख प्रकार दृश्य-अनुक्रमणीयता, और संघर्ष-अनुक्रमणीयता उपस्थित हैं । दृश्य-अनुक्रमणीयता ऊपर दी गई क्रमबद्धता की सामान्य परिभाषा से मेल खाती है। संघर्ष-क्रमबद्धता एक व्यापक विशेष स्थिति है, यानी, कोई भी सूची जो संघर्ष-अनुक्रमणीय है, वह भी दृश्य-अनुक्रमणीय है, लेकिन जरूरी नहीं कि इसके विपरीत हो। संघर्ष-अनुक्रमणीयता का व्यापक रूप से उपयोग किया जाता है क्योंकि दृश्य-अनुक्रमणीय सूचीयों के एक बड़े हिस्से को निर्धारित करना और कवर करना आसान होता है। सूची की व्यू-क्रमबद्धता का निर्धारण एक एनपी-पूर्ण समस्या है (समस्याओं का एक वर्ग जिसमें केवल जटिल-से-गणना, अत्यधिक समय लेने वाले ज्ञात समाधान हैं)। | |||
सूची की '''<nowiki/>'व्यू-क्रमबद्धता'''' को समान आदान-प्रदान के साथ क्रमिक सूची (कोई ओवरलैपिंग आदान-प्रदान नहीं) के समतुल्य द्वारा परिभाषित किया गया है, जैसे कि दो सूची में संबंधित आदान-प्रदान समान डेटा मान पढ़ते और लिखते हैं (समान डेटा मान देखें)। | |||
: | : सूची की '''<nowiki/>'कॉन्फ्लिक्ट-क्रमबद्धता'''<nowiki/>' एक ही आदान-प्रदान के साथ क्रमिक सूची (कोई ओवरलैपिंग आदान-प्रदान नहीं) के समतुल्यता द्वारा परिभाषित की जाती है, जैसे कि दोनों सूची में संबंधित कालानुक्रमिक रूप से परस्पर विरोधी संचालन के जोड़े के समान सेट होते हैं (संबंधित परस्पर विरोधी के समान पूर्वता संबंध संचालन)। | ||
डेटा पर संचालन पढ़ा या लिखा | डेटा पर संचालन पढ़ा या लिखा (लेखन,सन्निवेश ,अपडेट करें या हटाएं) जाता है । दो ऑपरेशन परस्पर विरोधी हैं यदि वे एक ही डेटम (डेटा आइटम) पर अलग-अलग आदान-प्रदान के हैं, और उनमें से कम से कम एक लेख है। परस्पर विरोधी संचालन की प्रत्येक जोड़ी में एक संघर्ष प्रकार होता है यह या तो पढ़ने-लिखने, या लिखने-पढ़ने, या लिखने-लिखने का संघर्ष है। समरूप में दूसरे ऑपरेशन के आदान-प्रदान को पहले ऑपरेशन के आदान-प्रदान के विरोध में कहा जाता है। परस्पर विरोधी कार्यों की एक अधिक सामान्य परिभाषा (जटिल संचालन के लिए भी, जिसमें प्रत्येक में कई सरल पढ़ने/लिखने के संचालन सम्मिलित हो सकते हैं) के लिए आवश्यक है कि वे अनुक्रमिक हों (उनके क्रम को बदलने से उनके संयुक्त परिणाम भी बदल जाते हैं)। [[अविनिमेय]]िटी चेक के लिए एक ऑपरेशन माना जाने के लिए इस तरह के प्रत्येक ऑपरेशन को स्वयं (उचित प्रणाली समर्थन का उपयोग करके) परमाणु होना चाहिए। उदाहरण के लिए, पढ़ना-पढ़ना संक्रिया क्रमविनिमेय हैं (पढ़ने-लिखने और अन्य संभावनाओं के विपरीत) और इस प्रकार पढ़ना-पढ़ना कोई विरोध नहीं है। एक और अधिक जटिल उदाहरण के लिए काउंटर के संचालन में वृद्धि और कमी दोनों लेखन कार्य हैं (दोनों काउंटर को संशोधित करते हैं), लेकिन परस्पर विरोधी होने की आवश्यकता नहीं है (लेखन-लेखन संघर्ष प्रकार) क्योंकि वे कम्यूटिव हैं (इस प्रकार वेतन वृद्धि-कमी नहीं है) संघर्ष; उदाहरण के लिए, पहले से ही पुराने IBM सूचना प्रबंधन प्रणाली | IBM के IMS फास्ट पाथ में समर्थित किया गया है)। परस्पर विरोधी (अ-कम्यूटेटिव) संचालन के जोड़े में केवल पूर्वता (समय क्रम) एक क्रमिक सूची के समतुल्यता की जांच करते समय महत्वपूर्ण है, क्योंकि अलग-अलग आदान-प्रदान के संचालन के बीच ऑर्डर बदलकर एक ही आदान-प्रदान वाले अलग-अलग सूची को एक से दूसरे में बदला जा सकता है ( अलग-अलग आदान-प्रदान 'इंटरलीविंग), और चूंकि कम्यूटेटिव ऑपरेशंस (अ-परस्पर विरोधी) के बदलते ऑर्डर समग्र ऑपरेशन अनुक्रम परिणाम को नहीं बदलते हैं, यानी, एक सूची परिणाम (परिणाम को अ-विरोधी संचालन के बीच ऑर्डर परिवर्तन के माध्यम से संरक्षित किया जाता है, लेकिन सामान्यतः नहीं जब परस्पर विरोधी संचालन परिवर्तन क्रम)। इसका तात्पर्य यह है कि यदि किसी सूची को परस्पर विरोधी संचालन के आदेशों को बदले बिना किसी भी क्रमिक सूची में बदला जा सकता है (लेकिन अ-विरोधी के बदलते आदेश, प्रत्येक आदान-प्रदान के अंदर ऑपरेशन ऑर्डर को संरक्षित करते हुए) दोनों सूची का परिणाम समान होता है और सूची परिभाषा के अनुसार संघर्ष-क्रमबद्ध है। | ||
संघर्ष | संघर्ष आदान-प्रदान में देरी (अ-संतृप्त संघर्ष) को अवरुद्ध करने या क्रमबद्धता उल्लंघन रोकथाम के कारण आदान-प्रदान को रद्द करने का कारण हैं। दोनों संभावनाएं प्रदर्शन को कम करती हैं। इस प्रकार संघर्षों की संख्या को कम करना, उदाहरण के लिए, कम्यूटेटिविटी (जब संभव हो) द्वारा, प्रदर्शन को बढ़ाने का एक विधि है। | ||
आदान-प्रदान परस्पर विरोधी ऑपरेशन जारी / अनुरोध कर सकता है और दूसरे आदान-प्रदान के साथ संघर्ष में हो सकता है, जबकि इसके परस्पर विरोधी संचालन में (उदाहरण के लिए, एक लॉक द्वारा अवरुद्ध) विलंबित और निष्पादित नहीं होती है । केवल निष्पादित (संतृप्त) परस्पर विरोधी संचालन संघर्ष क्रमबद्धता के लिए प्रासंगिक हैं (नीचे अधिक देखें)। | |||
== विरोध क्रमबद्धता लागू करना == | == विरोध क्रमबद्धता लागू करना == | ||
=== परीक्षण संघर्ष क्रमबद्धता === | === परीक्षण संघर्ष क्रमबद्धता === | ||
सूची के प्रतिबद्ध आदान-प्रदान के लिए संघर्ष अनुक्रमिकता के साथ सूची अनुपालन को प्राथमिकता ग्राफ (क्रमबद्धता ग्राफ, क्रमांकन ग्राफ, संघर्ष ग्राफ) के साथ परीक्षण किया जा सकता है। यह एक [[निर्देशित ग्राफ]] है जो सूची में आदान-प्रदान की पूर्वता का प्रतिनिधित्व करता है, जैसा कि आदान-प्रदान में परस्पर विरोधी संचालन की पूर्वता से परिलक्षित होता है। | |||
: '[[पूर्वता ग्राफ]]' में | : '[[पूर्वता ग्राफ]]' में आदान-प्रदान नोड होते हैं और पूर्वता संबंध निर्देशित किनारे होते हैं। पहले आदान-प्रदान से दूसरे आदान-प्रदान तक बढ़त उपस्थितहै, अगर दूसरा आदान-प्रदान पहले के साथ संघर्ष में है (ऊपर संघर्ष क्रमबद्धता देखें), और संघर्ष 'संतृप्त' (यानी, यदि अनुरोधित परस्पर विरोधी ऑपरेशन वास्तव में निष्पादित किया गया है: में कई मामलों में एक आदान-प्रदान द्वारा अनुरोधित/जारी किए गए परस्पर विरोधी ऑपरेशन में देरी होती है और यहां तक कि कभी भी निष्पादित नहीं किया जाता है, सामान्यतः ऑपरेशन के ऑब्जेक्ट पर लॉक (कंप्यूटर साइंस) द्वारा, किसी अन्य आदान-प्रदान द्वारा आयोजित, या जब आदान-प्रदान के अस्थायी निजी कार्यक्षेत्र में लिखा जाता है और संतृप्त रूप से कॉपी किया जाता है प्रतिबद्ध होने पर डेटाबेस स्वयं; जब तक एक अनुरोधित/जारी किए गए विरोधाभासी ऑपरेशन को डेटाबेस पर ही निष्पादित नहीं किया जाता है, तब तक संघर्ष ''''अ-संतृप्त'''<nowiki/>' होता है अ-संतृप्त विरोधों को पूर्ववर्ती ग्राफ में किनारे से नहीं दर्शाया जाता है) हो गया है । | ||
:'''<nowiki/>'टिप्पणी:'''' कई पाठ्य पुस्तकों में केवल प्रतिबद्ध आदान-प्रदान ही अग्रता ग्राफ में सम्मिलित हैं। बाद की चर्चाओं में सुविधा के लिए यहां सभी आदान-प्रदान सम्मिलित किए गए हैं। | |||
: | निम्नलिखित अवलोकन '''<nowiki/>'संघर्ष क्रमिकता का प्रमुख लक्षण वर्णन'''<nowiki/>' है: | ||
: सूची संघर्ष-क्रमबद्ध है यदि और केवल यदि प्रतिबद्ध आदान-प्रदान का पूर्ववर्ती ग्राफ (जब केवल प्रतिबद्ध आदान-प्रदान माना जाता है) विश्वकोश है। इसका तात्पर्ययह है कि प्रतिबद्ध आदान-प्रदान से युक्त एक चक्र केवल (सामान्य) पूर्वता ग्राफ में उत्पन्न होता है, यदि और केवल यदि संघर्ष-क्रमबद्धता का उल्लंघन किया जाता है। | |||
सभी आदान-प्रदान के पूर्ववर्ती ग्राफ में प्रत्येक चक्र पर एक अनिर्णीत (न तो प्रतिबद्ध, न ही निरस्त) आदान-प्रदान को समाप्त करके प्रतिबद्ध आदान-प्रदान के चक्र को रोका जा सकता है, अन्यथा जो प्रतिबद्ध आदान-प्रदान के चक्र में (और प्रतिबद्ध आदान-प्रदान को निरस्त नहीं किया जा सकता है) बदल सकता है . प्रति चक्र निरस्त किया गया एक आदान-प्रदान चक्र को समाप्त करने के लिए आवश्यक और पर्याप्त संख्या में दोनों है (कुछ क्रियाविधि के तहत अधिक निरस्तता संभव हो सकते हैं, लेकिन क्रमबद्धता के लिए अनावश्यक हैं) दोनों है। चक्र निर्माण की संभावना सामान्यतः कम है, फिर भी, ऐसी स्थिति को सामान्यतः काफी मात्रा में ओवरहेड के साथ सावधानी से संभाला जाता है, क्योंकि शुद्धता सम्मिलित होती है। क्रमबद्धता के उल्लंघन की रोकथाम के कारण रद्द किए गए आदान-प्रदान को फिर से शुरू किया जाता है और तुरंत फिर से निष्पादित किया जाता है। | |||
क्रमिकता-प्रवर्तन क्रियाविधि सामान्यतः डेटा संरचना के रूप में एक पूर्वता ग्राफ को बनाए नहीं रखते हैं, बल्कि चक्र को पूरी तरह से रोकते हैं या तोड़ते हैं (उदाहरण के लिए, नीचे SS2PL)। | |||
=== सामान्य क्रियाविधि — SS2PL === | |||
{{main|Two-phase locking}} | |||
मजबूत स्ट्रिक्ट टू-फेज लॉकिंग (SS2PL) 1970 के दशक के प्रारंभ दिनों से डेटाबेस प्रणाली में उपयोग किया जाने वाला (यद्यपि SS2PL नाम का SS नया है) संघर्ष क्रमबद्धता और सख्ती दोनों को लागू करने के लिए (एक विशेष स्थिति पुनर्प्राप्ति योग्यता जो किसी सूची की विफलता से प्रभावी डेटाबेस पुनर्प्राप्ति की अनुमति देती है) एक सामान्य क्रिया विधि है। इस क्रियाविधि के तहत,प्रत्येक डेटा को आदान-प्रदान द्वारा एक्सेस करने से पहले (किसी भी पढ़ने या लिखने के संचालन में) लॉक कर दिया जाता है , आइटम को एक निश्चित प्रकार के लॉक द्वारा चिह्नित किया जाता है और ऑपरेशन के आधार पर किया जाता है (और विशिष्ट आदान-प्रदान कार्यान्वयन विभिन्न प्रकार के लॉक वाले विभिन्न मॉडल उपस्थित हैं कुछ मॉडलों में, आदान-प्रदान के जीवन के दौरान लॉकिंग प्रकार बदल सकते हैं)। परिणामस्वरूप, किसी अन्य आदान-प्रदान द्वारा पहुंच को अवरुद्ध किया जा सकता है, सामान्यतः एक विरोध पर (ताला देरी या पूरी तरह से संघर्ष को संतृप्त होने से रोकता है और विरोधाभासी संचालन को अवरुद्ध करके पूर्ववर्ती ग्राफ में परिलक्षित होता है), लॉक प्रकार और अन्य आदान-प्रदान के आधार पर एक्सेस ऑपरेशन प्रकार। SS2PL क्रियाविधि को नियोजित करने का अर्थ है कि आदान-प्रदान की ओर से डेटा पर सभी लॉकिंग केवल आदान-प्रदान समाप्त होने (या तो प्रतिबद्ध या निरस्त) के बाद जारी किए जाते हैं। | |||
मजबूत | |||
SS2PL परिणामी | SS2PL परिणामी सूची गुण का भी नाम है, जिसे कठोरता भी कहा जाता है। SS2PL दो-चरण लॉकिंग (2PL) का एक विशेष स्थिति (उचित उपसमुच्चय) है । | ||
आदान-प्रदान के बीच पारस्परिक रुकावट के परिणामस्वरूप गतिरोध होता है, जहाँ इन आदान-प्रदान का निष्पादन ठप हो जाता है और कोई पूर्णता नहीं हो सकती है। इस प्रकार इन आदान-प्रदान के निष्पादन को पूरा करने और संबंधित कंप्यूटिंग संसाधनों को जारी करने के लिए गतिरोधों को हल करने की आवश्यकता है। एक गतिरोध पूर्वता ग्राफ में एक संभावित चक्र का प्रतिबिंब है जो बिना लॉकिंग के घटित होता है जब विरोध संतृप्त होता है। इस तरह के संभावित चक्र से जुड़े आदान-प्रदान को समाप्त करके और चक्र को तोड़कर गतिरोध का समाधान किया जाता है। यह सामान्यतःप्रतीक्षा-के लिए ग्राफ़ का उपयोग करके पता लगाया जाता है (लॉकिंग द्वारा संतृप्त होने से लॉकिंगित संघर्षों का एक ग्राफ़; इसे अ-संतृप्त संघर्षों के ग्राफ़ के रूप में भी परिभाषित किया जा सकता है; संतृप्त नहीं होने वाले विरोधों को पूर्ववर्ती ग्राफ़ में प्रतिबिंबित नहीं किया जाता है और प्रभावित नहीं होता है क्रमबद्धता), जो इंगित करता है कि कौन सा आदान-प्रदान एक से अधिक लॉकिंग के जारी होने की प्रतीक्षा कर रहा है जिसके द्वारा अन्य आदान-प्रदान और इस ग्राफ में एक चक्र का अर्थ गतिरोध है। चक्र को तोड़ने के लिए प्रति चक्र एक आदान-प्रदान को रद्द करना पर्याप्त है। गतिरोध समाधान के कारण रद्द किए गए आदान-प्रदान को फिर से शुरू किया जाता है और तुरंत फिर से निष्पादित किया जाता है। | |||
=== अन्य लागू करने वाली तकनीक === | === अन्य लागू करने वाली तकनीक === | ||
अन्य ज्ञात | अन्य ज्ञात क्रियाविधि में सम्मिलित हैं | ||
* वरीयता ग्राफ (या क्रमांकन ग्राफ, संघर्ष ग्राफ) चक्र उन्मूलन | * '''वरीयता ग्राफ''' (या क्रमांकन ग्राफ, संघर्ष ग्राफ) '''चक्र उन्मूलन''' | ||
* टू-फेज लॉकिंग (2PL) | * '''टू-फेज लॉकिंग''' (2PL) | ||
* टाइमस्टैम्प आधारित | * '''टाइमस्टैम्प आधारित क्रमणीयता नियंत्रण''' (TO) | ||
* स्नैपशॉट आइसोलेशन | * '''स्नैपशॉट आइसोलेशन आइसोलेशन को क्रमिक करने योग्य बनाना<ref name="Cahill08">Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): [http://portal.acm.org/citation.cfm?id=1376690 "Serializable isolation for snapshot databases"], ''Proceedings of the 2008 ACM SIGMOD international conference on Management of data'', pp. 729-738, Vancouver, Canada, June 2008, {{ISBN|978-1-60558-102-6}} (SIGMOD 2008 best paper award)</ref>''' (क्रमिक करने योग्य एसआई) | ||
उपरोक्त (संघर्ष) क्रमिकता तकनीक अपने सामान्य रूप में पुनर्प्राप्ति योग्यता प्रदान नहीं करती है। पुनर्प्राप्ति योग्यता जोड़ने के लिए विशेष संवर्द्धन की आवश्यकता है। | उपरोक्त (संघर्ष) क्रमिकता तकनीक अपने सामान्य रूप में पुनर्प्राप्ति योग्यता प्रदान नहीं करती है। पुनर्प्राप्ति योग्यता जोड़ने के लिए विशेष संवर्द्धन की आवश्यकता है। | ||
==== आशावादी बनाम निराशावादी तकनीक ==== | ==== आशावादी बनाम निराशावादी तकनीक ==== | ||
क्रमणीयता नियंत्रण तकनीक प्रमुख तीन प्रकार की होती हैं | |||
# निराशावादी | # '''निराशावादी''' निराशावादी क्रमणीयता नियंत्रण में, एक आदान-प्रदान संघर्षों पर अन्य आदान-प्रदान के डेटा एक्सेस संचालन को अवरुद्ध करता है, और लॉकिंगन को हटाए जाने तक तक विरोध अ-संतृप्त होते हैं। यह सुनिश्चित करने के लिए किया जाता है कि संचालन जो क्रमबद्धता का उल्लंघन कर सकते हैं (और अभ्यास में भी पुनर्प्राप्ति योग्यता) नहीं होते हैं। | ||
# आशावादी | # '''आशावादी''' आशावादी क्रमणीयता नियंत्रण में, अन्य आदान-प्रदान के डेटा एक्सेस ऑपरेशंस संघर्षों पर अवरुद्ध नहीं होते हैं, और संघर्ष तुरंत संतृप्त हो जाते हैं। जब आदान-प्रदान तैयार अवस्था में पहुँच जाता है, यानी, इसकी चालू अवस्था पूरी हो चुकी होती है, तो आदान-प्रदान के संचालन (अन्य चल रहे आदान-प्रदान के सापेक्ष) द्वारा संभावित क्रमिकता (और व्यवहार में भी पुनर्प्राप्ति) के उल्लंघन की जाँच की जाती है: यदि उल्लंघन हुआ है, तो आदान-प्रदान सामान्यतः होता है निरस्त किया गया (कभी-कभी क्रमिकता उल्लंघन को संभालने के लिए किसी अन्य आदान-प्रदान को रद्द करना पसंद किया जाता है)। अन्यथा, यह प्रतिबद्ध है। | ||
# अर्ध-आशावादी | # '''अर्ध-आशावादी''' क्रियाविधि जो कुछ स्थितियों में लॉकिंग को अन्य स्थितियों में अवरुद्ध नहीं करते हैं और संतृप्त, अ-संतृप्त संघर्ष दोनों को नियोजित करते हैं। | ||
तकनीक प्रकारों के बीच मुख्य अंतर उनके द्वारा उत्पन्न संघर्ष प्रकार हैं। एक निराशावादी पद्धति संघर्ष पर | तकनीक प्रकारों के बीच मुख्य अंतर उनके द्वारा उत्पन्न संघर्ष प्रकार हैं। एक निराशावादी पद्धति संघर्ष पर आदान-प्रदान के संचालन को अवरुद्ध करती है और अ-संतृप्त संघर्ष उत्पन्न करती है, जबकि एक आशावादी पद्धति ब्लॉक नहीं करती है और संतृप्त संघर्ष उत्पन्न करती है। एक अर्ध-आशावादी पद्धति दोनों संघर्ष प्रकार उत्पन्न करती है। दोनों संघर्ष प्रकार कालानुक्रमिक क्रम से उत्पन्न होते हैं जिसमें आदान-प्रदान के संचालन को संघर्ष के प्रकार से स्वतंत्र रूप से लागू किया जाता है। पूर्ववर्ती ग्राफ (संघर्ष ग्राफ) में प्रतिबद्ध आदान-प्रदान (संतृप्त संघर्षों के साथ) का एक चक्र क्रमिकता उल्लंघन का प्रतिनिधित्व करता है, और क्रमबद्धता बनाए रखने के लिए इससे बचा जाना चाहिए। वेट-फॉर ग्राफ़ में (अ-संतृप्त) संघर्षों का एक चक्र गतिरोध की स्थिति का प्रतिनिधित्व करता है, जिसे चक्र को तोड़कर हल किया जाना चाहिए। दोनों चक्र प्रकार संघर्षों से उत्पन्न होते हैं और इन्हें तोड़ा जाना चाहिए। किसी भी प्रकार की तकनीक के तहत, संतृप्त और अ-संतृप्त विरोध दोनों के लिए समान ओवरहेड के साथ संघर्षों का पता लगाया जाना चाहिए और विचार किया जाना चाहिए (सामान्यतः लॉकिंग जैसे क्रियाविधिका उपयोग करके, या तो लॉकिंग के लिए अवरुद्ध करना या अवरुद्ध नहीं करना, लेकिन संतृप्त विरोधों के लिए रिकॉर्डिंग संघर्ष)। अवरुद्ध करने की विधि में, सामान्यतः एक [[संदर्भ स्विच|संदर्भ स्विचिंग]] संघर्ष पर होता है, जिसमें (अतिरिक्त) उपरिव्यय होता है। अन्यथा, अवरुद्ध आदान-प्रदान से संबंधित कंप्यूटिंग संसाधन निष्क्रिय, अनुपयोगी रहते हैं, जो एक बदतर विकल्प हो सकता है। जब संघर्ष बार-बार नहीं होते हैं, तो आशावादी तरीकों का विशेष रूप से लाभ होता है। विभिन्न आदान-प्रदान भार (आदान-प्रदान प्रकारों के मिश्रण) के साथ एक तकनीक प्रकार (यानी, या तो आशावादी या निराशावादी) दूसरे की सादृश्य में उत्तम प्रदर्शन प्रदान कर सकता है। | ||
जब तक | जब तक सूची क्लास स्वाभाविक रूप से अवरुद्ध नहीं होते हैं (अर्थार्थ, उन्हें डेटा-एक्सेस ऑपरेशंस ब्लॉक किए बिना लागू नहीं किया जा सकता है उदाहरण के लिए, 2PL, SS2PL और SCO ऊपर; चार्ट देखें), उन्हें आशावादी तकनीकों (जैसे, क्रमबद्धता, रिकवरेबिलिटी) का उपयोग करके भी लागू किया जा सकता है। | ||
==== क्रमबद्ध बहु-संस्करण | ==== क्रमबद्ध बहु-संस्करण क्रमणीयता नियंत्रण ==== | ||
: [[बहुसंस्करण समवर्ती नियंत्रण]] (आंशिक कवरेज) और | : [[बहुसंस्करण समवर्ती नियंत्रण|बहुसंस्करण क्रमणीयता नियंत्रण]] (आंशिक कवरेज) और '''स्नैपशॉट आइसोलेशन में''' '''क्रमबद्ध स्नैपशॉट आइसोलेशन''' भी देखें | ||
बहु-संस्करण | '''बहु-संस्करण क्रमणीयता नियंत्रण (एमवीसीसी)''' आज एक सामान्य प्रक्रिया है , सूची पद्धति के आधार पर जो प्रत्येक बार ऑब्जेक्ट लिखे जाने पर डेटाबेस ऑब्जेक्ट का एक नया संस्करण उत्पन्न करके और कई अंतिम प्रासंगिक संस्करणों (प्रत्येक ऑब्जेक्ट के) के आदान-प्रदान को पढ़ने के संचालन की अनुमति देकर क्रमणीयता और प्रदर्शन को बढ़ाने का एक सामान्य विधि है। MVCC को ऊपर सूचीबद्ध सभी क्रमिकता तकनीकों (SerializableSI को छोड़कर, जो मूल रूप से MVCC- आधारित है) के साथ जोड़ा जा सकता है। इसका उपयोग अधिकांश सामान्य-उद्देश्य वाले DBMS उत्पादों में किया जाता है। | ||
एमवीसीसी आजकल आराम से क्रमबद्धता (ऊपर देखें) विधि स्नैपशॉट आइसोलेशन (एसआई) के माध्यम से विशेष रूप से लोकप्रिय है, जो कि अधिकांश ज्ञात क्रमबद्धता | एमवीसीसी आजकल आराम से क्रमबद्धता (ऊपर देखें) विधि स्नैपशॉट आइसोलेशन (एसआई) के माध्यम से विशेष रूप से लोकप्रिय है, जो कि अधिकांश ज्ञात क्रमबद्धता क्रियाविधि (कुछ मामलों में संभावित क्रमबद्धता उल्लंघन की कीमत पर) से उत्तम प्रदर्शन प्रदान करता है।SerializableSI, जो इसे क्रमिक बनाने के लिए SI का एक कुशल संवर्द्धन है, का उद्देश्य एक कुशल क्रमिक समाधान प्रदान करना है। SerializableSI का विश्लेषण MVCC के एक सामान्य सिद्धांत के माध्यम से किया गया है। | ||
== वितरित क्रमबद्धता == | == वितरित क्रमबद्धता == | ||
=== अवलोकन === | === अवलोकन === | ||
वितरित क्रमबद्धता | वितरित क्रमबद्धता आदान-प्रदान [[वितरित प्रणाली]] (उदाहरण के लिए, [[वितरित डेटाबेस]] प्रणाली) की सूची की क्रमबद्धता है। इस तरह की प्रणाली "वितरित आदान-प्रदान" (जिसे "वैश्विक आदान-प्रदान" भी कहा जाता है) की विशेषता है, अर्थात, आदान-प्रदान जो कंप्यूटर प्रक्रियाओं (कंप्यूटिंग वातावरण के आधार पर सामान्य अर्थ में पृथक्करण उदाहरण के लिए, [[ऑपरेटिंग सिस्टम|ऑपरेटिंग प्रणाली]] का [[धागा (कंप्यूटर विज्ञान)|धागा]]) और संभवतः नेटवर्क नोड्स का विस्तार करते हैं। वितरित आदान-प्रदान में ''एक से अधिक'' 'स्थानीय उप-आदान-प्रदान'' यद्यपि होते हैं, डेटाबेस आदान-प्रदान के लिए ऊपर वर्णित प्रत्येक के पास स्थिति है। स्थानीय उप-आदान-प्रदान में एकल प्रक्रिया, या अधिक प्रक्रियाएँ सम्मिलित होती हैं जो सामान्यतः एक साथ विफल (उदाहरण के लिए, [[प्रोसेसर कोर]] में) होती हैं'' ।'' वितरित आदान-प्रदान को प्रतिबद्ध या निरस्त करने के बारे में अपने स्थानीय उप आदान-प्रदान के बीच आम सहमति तक पहुंचने के लिए [[परमाणु प्रतिबद्ध]] प्रोटोकॉल की आवश्यकता होती है। इस तरह के प्रोटोकॉल विफलता के अधिक जटिल मामलों (जैसे, प्रक्रिया, नोड, संचार, आदि विफलता) को संभालने के लिए दो-चरण की प्रतिबद्धता जैसे अधिक परिष्कृत प्रोटोकॉल के लिए एक साथ विफल होने वाली प्रक्रियाओं के बीच एक सरल (एक-चरण) हैंडशेक से भिन्न हो सकते हैं। वितरित क्रमबद्धता शुद्धता के लिए [[वितरित समवर्ती नियंत्रण|वितरित क्रमणीयता नियंत्रण]] का एक प्रमुख लक्ष्य है। इंटरनेट, [[ क्लाउड कम्प्यूटिंग | क्लाउड कम्प्यूटिंग]] , [[ग्रिड कंप्यूटिंग]], और छोटे पोर्टेबल, शक्तिशाली कंप्यूटिंग उपकरणों (जैसे, [[स्मार्टफोन]]) के प्रसार के साथ, वितरित अनुप्रयोगों में और बीच में शुद्धता सुनिश्चित करने के लिए प्रभावी वितरित क्रमिकता तकनीकों की आवश्यकता बढ़ रही है।'' | ||
वितरित क्रमबद्धता ज्ञात केंद्रीकृत तकनीकों के वितरित संस्करणों को लागू करके प्राप्त की जाती है।<ref name=Bernstein87 /><ref name=Weikum01 />सामान्यतः, ऐसे सभी वितरित संस्करणों में संघर्ष की जानकारी ( | वितरित क्रमबद्धता ज्ञात केंद्रीकृत तकनीकों के वितरित संस्करणों को लागू करके प्राप्त की जाती है।<ref name=Bernstein87 /><ref name=Weikum01 />सामान्यतः, ऐसे सभी वितरित संस्करणों में संघर्ष की जानकारी (संतृप्त या अ-संतृप्त संघर्ष, या, समतुल्य, आदान-प्रदान की पूर्वता या अवरुद्ध जानकारी; संघर्ष क्रमबद्धता का सामान्यतः उपयोग किया जाता है) का उपयोग करने की आवश्यकता होती है, जो स्थानीय रूप से नहीं, बल्कि विभिन्न प्रक्रियाओं में, और दूरस्थ स्थानों में उत्पन्न होता है। इस प्रकार सूचना वितरण (उदाहरण के लिए, पूर्वता संबंध, लॉक जानकारी, टाइमस्टैम्प या टिकट) की आवश्यकता है । जब वितरित प्रणाली अपेक्षाकृत छोटे पैमाने की होती है और पूरे प्रणाली में संदेश विलंब छोटा होता है, तो तो केंद्रीकृत क्रमणीयता नियंत्रण विधियों का उपयोग अपरिवर्तित किया जा सकता है, जबकि प्रणाली में कुछ प्रक्रियाएँ या नोड संबंधित एल्गोरिदम का प्रबंधन करते हैं। यद्यपि, एक बड़े पैमाने की प्रणाली (जैसे, ग्रिड और क्लाउड) में, इस तरह की जानकारी के वितरण के कारण, पर्याप्त प्रदर्शन अर्थदंड सामान्यतः लगाया जाता है, तब भी जब विधियों के वितरित संस्करण (बनाम केंद्रीकृत वाले) का उपयोग किया जाता है, मुख्य रूप से कंप्यूटर और संचार [[विलंबता (इंजीनियरिंग)|विलंबता]] के कारण है। साथ ही, जब ऐसी जानकारी वितरित की जाती है, संबंधित तकनीकें सामान्यतः अच्छी तरह से स्केल नहीं करती हैं। स्केलेबिलिटी समस्याओं के संबंध में एक प्रसिद्ध उदाहरण एक वितरित लॉकिंग प्रबंधक है, जो लॉकिंग तकनीकों को लागू करने के लिए वितरित प्रणाली में लॉकिंग (अ-संतृप्त विरोध) जानकारी वितरित करता है। | ||
== यह भी देखें == | == यह भी देखें == | ||
* दो-चरण लॉकिंग | * दो-चरण लॉकिंग | ||
* स्नैपशॉट आइसोलेशन | * स्नैपशॉट आइसोलेशन क्रमिक करने योग्य बनाना<ref name=Cahill08 /> स्नैपशॉट पृथक्रकरण में है। | ||
* वैश्विक क्रमिकता, जहां वैश्विक क्रमिकता समस्या और इसके प्रस्तावित समाधान वर्णित हैं। | * वैश्विक क्रमिकता, जहां वैश्विक क्रमिकता समस्या और इसके प्रस्तावित समाधान वर्णित हैं। | ||
* रेखीयता, [[समवर्ती कंप्यूटिंग]] में एक अधिक सामान्य अवधारणा। | * रेखीयता, [[समवर्ती कंप्यूटिंग|क्रमणीयता कंप्यूटिंग]] में एक अधिक सामान्य अवधारणा। | ||
== टिप्पणियाँ == | == टिप्पणियाँ == | ||
| Line 129: | Line 127: | ||
== संदर्भ == | == संदर्भ == | ||
<!--Supposed sources for most of the material about centralized (vs. distributed) serializability:--> | <!--Supposed sources for most of the material about centralized (vs. distributed) serializability:--> | ||
* [[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''], Addison Wesley Publishing Company, {{ISBN|0-201-10715-5}} | * [[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''], Addison Wesley Publishing Company, {{ISBN|0-201-10715-5}} | ||
* [[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}} | * [[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}} | ||
[[el:Σειριοποιησιμότητα Συγκρούσεων]] | [[el:Σειριοποιησιμότητα Συγκρούσεων]] | ||
[[Category:All articles lacking in-text citations]] | |||
[[Category:All articles with dead external links]] | |||
[[Category: | [[Category:All articles with unsourced statements]] | ||
[[Category:Articles lacking in-text citations from November 2011]] | |||
[[Category:Articles with dead external links from May 2018]] | |||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category:Articles with permanently dead external links]] | |||
[[Category:Articles with unsourced statements from February 2018]] | |||
[[Category:Articles with unsourced statements from July 2018]] | |||
[[Category:Created On 26/05/2023]] | [[Category:Created On 26/05/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:डेटा प्रबंधन]] | |||
[[Category:डेटाबेस]] | |||
[[Category:लेनदेन प्रक्रिया]] | |||
[[Category:वितरित कंप्यूटिंग समस्याएं]] | |||
[[Category:समरूपता नियंत्रण]] | |||
Latest revision as of 12:12, 12 September 2023
डेटाबेस के क्रमणीयता नियंत्रण [1][2] आदान-प्रदान प्रसंस्करण (आदान-प्रदान प्रबंधन) और विभिन्न डेटाबेस आदान-प्रदान अनुप्रयोग (जैसे, आदान-प्रदान मेमोरी[3] और सॉफ्टवेयर आदान-प्रदान मेमोरी) दोनों केंद्रीकृत और वितरित है,आदान-प्रदान सूची में क्रमबद्ध है यदि इसका परिणाम (उदाहरण के लिए, परिणामी डेटाबेस स्थिति) क्रमिक रूप से निष्पादित आदान-प्रदान समय में ओवरलैप किए बिना परिणाम के बराबर है। आदान-प्रदान सामान्यतः क्रमणीयता रूप से निष्पादित होते हैं (वे ओवरलैप होते हैं), क्योंकि यह सबसे कुशल विधि है। क्रमबद्धता क्रमणीयता आदान-प्रदान के निष्पादन के लिए प्रमुख शुद्धता मानदंड है. इसे डेटाबेस आदान-प्रदान के बीच उच्चतम स्तर का पृथक्रकरण माना जाता है, और क्रमणीयता नियंत्रण में एक आवश्यक भूमिका निभाता है। जैसे कि यह सभी सामान्य प्रयोजन डेटाबेस प्रणाली में समर्थित है। स्ट्रॉन्ग स्ट्रिक्ट टू-फेज लॉकिंग (SS2PL) एक लोकप्रिय क्रमिक क्रियाविधि है जिसका उपयोग 1970 के प्रारंभ दिनों से अधिकांश डेटाबेस प्रणाली (विभिन्न रूपों में) में किया जाता है।
'क्रमबद्धता सिद्धांत' क्रमबद्धता और इसकी तकनीकों के बारे में तर्क और विश्लेषण करने के लिए औपचारिक ढांचा प्रदान करता है। यद्यपि यह प्रकृति गणित में है, इसके मूल सिद्धांतों को अनौपचारिक रूप से (बिना गणित अंकन के) नीचे प्रस्तुत किया गया है।
शुद्धता
क्रमबद्धता
क्रमबद्धता का उपयोग डेटा आइटम में डेटा को एक सुसंगत स्थिति में रखने के लिए किया जाता है। क्रमबद्धता आदान-प्रदान सूची (इतिहास) का अधिकार है। यह डेटाबेस आदान-प्रदान के पृथक्रकरण (डेटाबेस प्रणाली) अधिकार से संबंधित है।
- सूची की क्रमबद्धता का अर्थ समान आदान-प्रदान के साथ 'क्रमिक सूची' (यानी, समय में बिना किसी आदान-प्रदान के ओवरलैप के साथ अनुक्रमिक) के लिए समानता (परिणाम , डेटाबेस स्थिति, डेटा मान में) है। यह क्रमणीयता आदान-प्रदान की सूची की शुद्धता के लिए प्रमुख मानदंड है, और इस प्रकार सभी सामान्य प्रयोजन डेटाबेस प्रणाली में समर्थित है।[citation needed]
- क्रमबद्धता के पीछे तर्क निम्नलिखित है:
- यदि प्रत्येक आदान-प्रदान अपने आप में सही है, अर्थात कुछ पूर्णता अनुबंध को पूरा करता है, तो एक सूची जिसमें इन आदान-प्रदान का कोई भी 'क्रमिक' निष्पादन सम्मिलित है सही है (इसके आदान-प्रदान अभी भी उनकी अनुबंध को पूरा करते हैं)। क्रमिक का अर्थ है कि आदान-प्रदान समय पर ओवरलैप नहीं होता और न हीं हो सकता है, एक दूसरे के साथ हस्तक्षेप, यानी एक दूसरे के बीच पूर्ण पृथक्रकरण मौजूद है। आदान-प्रदान का कोई भी आदेश वैध है, यदि उनके बीच कोई निर्भरता मौजूद नहीं है, जिसे मान लिया गया है (नीचे टिप्पणी देखें)। परिणामस्वरूप, सूची जिसमें इन आदान-प्रदान के किसी भी क्रमिक निष्पादन के बराबर (इसके परिणाम में) कोई निष्पादन (जरूरी नहीं कि क्रमिक हो) सम्मिलित है, सही है।
सूचीयां जो क्रमबद्ध नहीं हैं, गलत परिणाम उत्पन्न करने की संभावना होती है। प्रसिद्ध उदाहरण लेन-देन के साथ जो पैसे के साथ डेबिट और क्रेडिट गणना करना हैं यदि संबंधित सूची क्रमबद्ध नहीं हैं, तो धन की कुल राशि को संरक्षित नहीं किया जा सकता है पैसा लुप्त हो सकता है, या कहीं से उत्पन्न हो सकता है। यह संभावित रूप से आवश्यक अपरिवर्तनीय संरक्षणों का उल्लंघन आदान-प्रदान लेखन, "स्टेपिंग ऑन" और डेटाबेस में स्थायी होने से पहले किसी अन्य आदान-प्रदान द्वारा लिखे गए को मिटाने के कारण होता है। यदि क्रमबद्धता बनी रहती है तो ऐसा नहीं होता है।
यदि किसी आवेदन द्वारा कुछ आदान-प्रदान के बीच किसी विशिष्ट आदेश का अनुरोध किया जाता है, तो इसे अंतर्निहित क्रमबद्धता क्रियाविधि से स्वतंत्र रूप से लागू किया जाता है। ये क्रियाविधि सामान्यतः किसी विशिष्ट आदेश के प्रति उदासीन होते हैं, और कुछ अप्रत्याशित आंशिक आदेश उत्पन्न करते हैं जो सामान्यतः इन आदान-प्रदान के कई क्रमिक आदेश के साथ संगत होते हैं। यह आंशिक आदेश क्रमणीयता आदान-प्रदान के डेटा एक्सेस ऑपरेशंस के सूची ऑर्डर से उत्पन्न होता है, जो कई कारकों पर निर्भर करता है।
डेटाबेस आदान-प्रदान की एक प्रमुख विशेषता परमाणुता है, जिसका अर्थ है कि या तो यह प्रतिबद्ध है, यानी, इसके सभी संचालन 'परिणाम डेटाबेस में प्रभावी होते हैं, या निरस्त (लुढ़के हुए), इसके सभी परिचालनों के परिणामों का डेटाबेस पर कोई प्रभाव नहीं पड़ता है (आदान-प्रदान के शब्दार्थ "सभी या कुछ नहीं")। सभी वास्तविक प्रणालियों में आदान-प्रदान कई कारणों से निरस्त हो सकता है, और शुद्धता के लिए क्रमबद्धता अपने आप में पर्याप्त नहीं है। सूचियों को पुनर्प्राप्ति योग्यता (लॉकिंग से) संपत्ति रखने की भी आवश्यकता है।। पुनर्प्राप्ति योग्यता का अर्थ है कि प्रतिबद्ध आदान-प्रदान ने निरस्त किए गए आदान-प्रदान द्वारा लिखे गए डेटा को नहीं पढ़ा है (जिसका प्रभाव परिणामी डेटाबेस स्थिति में उपस्थित नहीं है)। यद्यपि वर्तमान में उत्तम प्रदर्शन के लिए कई अनुप्रयोगों में क्रमबद्धता के उद्देश्य से समझौता किया गया है (केवल ऐसे मामलों में जब आवेदन की शुद्धता को क्षति नहीं पहुंचाया जाता है), पुनर्प्राप्ति से समझौता करने से डेटाबेस की पूर्णता का उल्लंघन होगा, साथ ही आदान-प्रदान के परिणाम डेटाबेस से बाहर हो जाएंगे। पुनर्प्राप्ति योग्यता गुण (एक पुनर्प्राप्ति योग्य सूची) के साथ सूची अपने आप निरस्त होने से ठीक हो जाता है, अर्थात, लॉकिंग इसके प्रतिबद्ध आदान-प्रदान और परिणामी डेटाबेस की पूर्णता को क्षति नहीं पहुंचाता है। पुनर्प्राप्ति योग्यता के बिना यह झूठा है, जहां संभावित पूर्णता उल्लंघन (जिसके परिणामस्वरूप गलत डेटाबेस डेटा) को डेटाबेस में विशेष, सामान्यतः नियमावली, सुधारात्मक कार्यों की आवश्यकता होती है।
अपने सामान्य रूप में पुनर्प्राप्ति को लागू करने से 'व्यापक लॉकिंग' हो सकता है: एक आदान-प्रदान को समाप्त करने के परिणामस्वरूप दूसरे आदान-प्रदान को निरस्त करने की आवश्यकता हो सकती है, और फिर तीसरा, और इसी तरह बाकि सब। यह पहले से ही आंशिक रूप से निष्पादित आदान-प्रदान की बर्बादी का परिणाम है, और इसके परिणामस्वरूप प्रदर्शन अर्थदंड भी हो सकता 'व्यापक लॉकिंग से बचना (एसीए, या कैस्केडलेसनेस) से बचना पुनर्प्राप्ति का एक विशेष स्थिति है जो वास्तव में ऐसी घटनाओं को रोकता है। सामान्यतः व्यवहार में ACA के एक विशेष स्थिति का उपयोग किया जाता है: कठोरता कुशल डेटाबेस पुनर्प्राप्ति को विफलता से अनुमति देती है।
ध्यान दें कि यदि कोई डेटाबेस विफल नहीं होता है तो भी पुनर्प्राप्ति गुण की आवश्यकता होता है और विफलता से कोई डेटाबेस पुनर्प्राप्ति की आवश्यकता नहीं होती है। इसके के स्थान पर, स्वचालित रूप से लॉकिंग को सही ढंग से संभालने की आवश्यकता है, जो डेटाबेस विफलता और विफलता से पुनर्प्राप्ति से संबंधित नहीं हो सकता है।
आराम से क्रमबद्धता
कई अनुप्रयोगों में, वित्त के विपरीत पूर्ण शुद्धता की आवश्यकता नहीं होती है। उदाहरण के लिए, विनिर्देश के अनुसार उत्पादों की सूची प्राप्त करते समय, अधिकतर मामलों में इससे कोई अंतर नहीं पड़ता है कि कोई उत्पाद, जिसका डेटा थोड़े समय पहले अद्यतन किया गया था सूची में प्रकट नहीं होता है, भले ही वह विनिर्देश को पूरा करता हो। कुछ समय बाद पुन: प्रयास करने पर यह सामान्यतः ऐसी सूची में दिखाई देगा। वाणिज्यिक डेटाबेस पृथक्रकरण(कंप्यूटर विज्ञान) पृथक्रकरणस्तरों की एक पूरी श्रृंखला के साथ क्रमणीयता नियंत्रण प्रदान करते हैं जो उच्च प्रदर्शन प्राप्त करने के लिए वास्तव में (नियंत्रित) क्रमबद्धता उल्लंघन हैं। उच्च प्रदर्शन का तात्पर्यउत्तम आदान-प्रदान निष्पादन दर और कम औसत आदान-प्रदान प्रतिक्रिया समय (आदान-प्रदान की अवधि) है। स्नैपशॉट पृथक्रकरण एक लोकप्रिय, व्यापक रूप से उपयोग की जाने वाली कुशल रिलैक्स क्रमबद्धता पद्धति का एक उदाहरण है जिसमें पूर्ण क्रमबद्धता की कई विशेषताएं हैं, लेकिन फिर भी कुछ से कम है, और कई स्थितियों में अनुपयुक्त है।
वितरित क्रमबद्धता रिलैक्सेशन (नीचे देखें) के लिए आजकल एक और सामान्य कारण इंटरनेट उत्पादों और इंटरनेट सेवा प्रदाता की उपलब्धता की आवश्यकता है। इस आवश्यकता का सामान्यतः बड़े पैमाने पर डेटा प्रतिकृति (कंप्यूटर विज्ञान) द्वारा उत्तर दिया जाता है। एक ही डेटाबेस ऑब्जेक्ट की प्रतिकृतियों के अद्यतनों को सिंक्रनाइज़ करने का सीधा समाधान इन सभी अद्यतनों को एकल परमाणु वितरित आदान-प्रदान में सम्मिलित करना है। हालाँकि, कई प्रतिकृतियों के साथ ऐसा आदान-प्रदान बहुत बड़ा है, और कई कंप्यूटरों और संगणक संजाल के लिए पर्याप्त हो सकता है कि उनमें से कुछ के अनुपलब्ध होने की संभावना है। इस प्रकार इस तरह के आदान-प्रदान के समाप्त होने की संभावना है और इसका उद्देश्य चूक जाएगा।[4]
परिणामस्वरूप, आशावादी प्रतिकृति (आलसी प्रतिकृति) का सामान्यतः उपयोग किया जाता है (उदाहरण के लिए, Google, Amazon.com, Yahoo, और इसी तरह के कई उत्पादों और सेवाओं में), जबकि क्रमबद्धता को आराम दिया जाता है और अंतिम स्थिरता के लिए समझौता किया जाता है। फिर से, इस स्थिति में, केवल उन अनुप्रयोगों के लिए छूट दी जाती है जिन्हें इस तकनीक से क्षति होने की उम्मीद नहीं है।
सूचीयों के वर्गों को आराम से क्रमिकता गुणों द्वारा परिभाषित किया गया है या तो क्रमबद्धता वर्ग सम्मिलित है, या इसके साथ अतुलनीय हैं।
देखें और विरोध क्रमबद्धता
क्रमिकता को लागू करने वाले क्रियाविधि को वास्तविक -समय में या लगभग वास्तविक समय में निष्पादित करने की आवश्यकता होती है, जबकि आदान-प्रदान उच्च दर पर चल रहे होते हैं। इस आवश्यकता को पूरा करने के लिए, क्रमबद्धता के विशेष स्थिति, क्रमबद्धता के लिए पर्याप्त अनुबंध जिन्हें प्रभावी ढंग से लागू किया जा सकता है, का उपयोग किया जाता है।
क्रमबद्धता के दो प्रमुख प्रकार दृश्य-अनुक्रमणीयता, और संघर्ष-अनुक्रमणीयता उपस्थित हैं । दृश्य-अनुक्रमणीयता ऊपर दी गई क्रमबद्धता की सामान्य परिभाषा से मेल खाती है। संघर्ष-क्रमबद्धता एक व्यापक विशेष स्थिति है, यानी, कोई भी सूची जो संघर्ष-अनुक्रमणीय है, वह भी दृश्य-अनुक्रमणीय है, लेकिन जरूरी नहीं कि इसके विपरीत हो। संघर्ष-अनुक्रमणीयता का व्यापक रूप से उपयोग किया जाता है क्योंकि दृश्य-अनुक्रमणीय सूचीयों के एक बड़े हिस्से को निर्धारित करना और कवर करना आसान होता है। सूची की व्यू-क्रमबद्धता का निर्धारण एक एनपी-पूर्ण समस्या है (समस्याओं का एक वर्ग जिसमें केवल जटिल-से-गणना, अत्यधिक समय लेने वाले ज्ञात समाधान हैं)।
सूची की 'व्यू-क्रमबद्धता' को समान आदान-प्रदान के साथ क्रमिक सूची (कोई ओवरलैपिंग आदान-प्रदान नहीं) के समतुल्य द्वारा परिभाषित किया गया है, जैसे कि दो सूची में संबंधित आदान-प्रदान समान डेटा मान पढ़ते और लिखते हैं (समान डेटा मान देखें)।
- सूची की 'कॉन्फ्लिक्ट-क्रमबद्धता' एक ही आदान-प्रदान के साथ क्रमिक सूची (कोई ओवरलैपिंग आदान-प्रदान नहीं) के समतुल्यता द्वारा परिभाषित की जाती है, जैसे कि दोनों सूची में संबंधित कालानुक्रमिक रूप से परस्पर विरोधी संचालन के जोड़े के समान सेट होते हैं (संबंधित परस्पर विरोधी के समान पूर्वता संबंध संचालन)।
डेटा पर संचालन पढ़ा या लिखा (लेखन,सन्निवेश ,अपडेट करें या हटाएं) जाता है । दो ऑपरेशन परस्पर विरोधी हैं यदि वे एक ही डेटम (डेटा आइटम) पर अलग-अलग आदान-प्रदान के हैं, और उनमें से कम से कम एक लेख है। परस्पर विरोधी संचालन की प्रत्येक जोड़ी में एक संघर्ष प्रकार होता है यह या तो पढ़ने-लिखने, या लिखने-पढ़ने, या लिखने-लिखने का संघर्ष है। समरूप में दूसरे ऑपरेशन के आदान-प्रदान को पहले ऑपरेशन के आदान-प्रदान के विरोध में कहा जाता है। परस्पर विरोधी कार्यों की एक अधिक सामान्य परिभाषा (जटिल संचालन के लिए भी, जिसमें प्रत्येक में कई सरल पढ़ने/लिखने के संचालन सम्मिलित हो सकते हैं) के लिए आवश्यक है कि वे अनुक्रमिक हों (उनके क्रम को बदलने से उनके संयुक्त परिणाम भी बदल जाते हैं)। अविनिमेयिटी चेक के लिए एक ऑपरेशन माना जाने के लिए इस तरह के प्रत्येक ऑपरेशन को स्वयं (उचित प्रणाली समर्थन का उपयोग करके) परमाणु होना चाहिए। उदाहरण के लिए, पढ़ना-पढ़ना संक्रिया क्रमविनिमेय हैं (पढ़ने-लिखने और अन्य संभावनाओं के विपरीत) और इस प्रकार पढ़ना-पढ़ना कोई विरोध नहीं है। एक और अधिक जटिल उदाहरण के लिए काउंटर के संचालन में वृद्धि और कमी दोनों लेखन कार्य हैं (दोनों काउंटर को संशोधित करते हैं), लेकिन परस्पर विरोधी होने की आवश्यकता नहीं है (लेखन-लेखन संघर्ष प्रकार) क्योंकि वे कम्यूटिव हैं (इस प्रकार वेतन वृद्धि-कमी नहीं है) संघर्ष; उदाहरण के लिए, पहले से ही पुराने IBM सूचना प्रबंधन प्रणाली | IBM के IMS फास्ट पाथ में समर्थित किया गया है)। परस्पर विरोधी (अ-कम्यूटेटिव) संचालन के जोड़े में केवल पूर्वता (समय क्रम) एक क्रमिक सूची के समतुल्यता की जांच करते समय महत्वपूर्ण है, क्योंकि अलग-अलग आदान-प्रदान के संचालन के बीच ऑर्डर बदलकर एक ही आदान-प्रदान वाले अलग-अलग सूची को एक से दूसरे में बदला जा सकता है ( अलग-अलग आदान-प्रदान 'इंटरलीविंग), और चूंकि कम्यूटेटिव ऑपरेशंस (अ-परस्पर विरोधी) के बदलते ऑर्डर समग्र ऑपरेशन अनुक्रम परिणाम को नहीं बदलते हैं, यानी, एक सूची परिणाम (परिणाम को अ-विरोधी संचालन के बीच ऑर्डर परिवर्तन के माध्यम से संरक्षित किया जाता है, लेकिन सामान्यतः नहीं जब परस्पर विरोधी संचालन परिवर्तन क्रम)। इसका तात्पर्य यह है कि यदि किसी सूची को परस्पर विरोधी संचालन के आदेशों को बदले बिना किसी भी क्रमिक सूची में बदला जा सकता है (लेकिन अ-विरोधी के बदलते आदेश, प्रत्येक आदान-प्रदान के अंदर ऑपरेशन ऑर्डर को संरक्षित करते हुए) दोनों सूची का परिणाम समान होता है और सूची परिभाषा के अनुसार संघर्ष-क्रमबद्ध है।
संघर्ष आदान-प्रदान में देरी (अ-संतृप्त संघर्ष) को अवरुद्ध करने या क्रमबद्धता उल्लंघन रोकथाम के कारण आदान-प्रदान को रद्द करने का कारण हैं। दोनों संभावनाएं प्रदर्शन को कम करती हैं। इस प्रकार संघर्षों की संख्या को कम करना, उदाहरण के लिए, कम्यूटेटिविटी (जब संभव हो) द्वारा, प्रदर्शन को बढ़ाने का एक विधि है।
आदान-प्रदान परस्पर विरोधी ऑपरेशन जारी / अनुरोध कर सकता है और दूसरे आदान-प्रदान के साथ संघर्ष में हो सकता है, जबकि इसके परस्पर विरोधी संचालन में (उदाहरण के लिए, एक लॉक द्वारा अवरुद्ध) विलंबित और निष्पादित नहीं होती है । केवल निष्पादित (संतृप्त) परस्पर विरोधी संचालन संघर्ष क्रमबद्धता के लिए प्रासंगिक हैं (नीचे अधिक देखें)।
विरोध क्रमबद्धता लागू करना
परीक्षण संघर्ष क्रमबद्धता
सूची के प्रतिबद्ध आदान-प्रदान के लिए संघर्ष अनुक्रमिकता के साथ सूची अनुपालन को प्राथमिकता ग्राफ (क्रमबद्धता ग्राफ, क्रमांकन ग्राफ, संघर्ष ग्राफ) के साथ परीक्षण किया जा सकता है। यह एक निर्देशित ग्राफ है जो सूची में आदान-प्रदान की पूर्वता का प्रतिनिधित्व करता है, जैसा कि आदान-प्रदान में परस्पर विरोधी संचालन की पूर्वता से परिलक्षित होता है।
- 'पूर्वता ग्राफ' में आदान-प्रदान नोड होते हैं और पूर्वता संबंध निर्देशित किनारे होते हैं। पहले आदान-प्रदान से दूसरे आदान-प्रदान तक बढ़त उपस्थितहै, अगर दूसरा आदान-प्रदान पहले के साथ संघर्ष में है (ऊपर संघर्ष क्रमबद्धता देखें), और संघर्ष 'संतृप्त' (यानी, यदि अनुरोधित परस्पर विरोधी ऑपरेशन वास्तव में निष्पादित किया गया है: में कई मामलों में एक आदान-प्रदान द्वारा अनुरोधित/जारी किए गए परस्पर विरोधी ऑपरेशन में देरी होती है और यहां तक कि कभी भी निष्पादित नहीं किया जाता है, सामान्यतः ऑपरेशन के ऑब्जेक्ट पर लॉक (कंप्यूटर साइंस) द्वारा, किसी अन्य आदान-प्रदान द्वारा आयोजित, या जब आदान-प्रदान के अस्थायी निजी कार्यक्षेत्र में लिखा जाता है और संतृप्त रूप से कॉपी किया जाता है प्रतिबद्ध होने पर डेटाबेस स्वयं; जब तक एक अनुरोधित/जारी किए गए विरोधाभासी ऑपरेशन को डेटाबेस पर ही निष्पादित नहीं किया जाता है, तब तक संघर्ष 'अ-संतृप्त' होता है अ-संतृप्त विरोधों को पूर्ववर्ती ग्राफ में किनारे से नहीं दर्शाया जाता है) हो गया है ।
- 'टिप्पणी:' कई पाठ्य पुस्तकों में केवल प्रतिबद्ध आदान-प्रदान ही अग्रता ग्राफ में सम्मिलित हैं। बाद की चर्चाओं में सुविधा के लिए यहां सभी आदान-प्रदान सम्मिलित किए गए हैं।
निम्नलिखित अवलोकन 'संघर्ष क्रमिकता का प्रमुख लक्षण वर्णन' है:
- सूची संघर्ष-क्रमबद्ध है यदि और केवल यदि प्रतिबद्ध आदान-प्रदान का पूर्ववर्ती ग्राफ (जब केवल प्रतिबद्ध आदान-प्रदान माना जाता है) विश्वकोश है। इसका तात्पर्ययह है कि प्रतिबद्ध आदान-प्रदान से युक्त एक चक्र केवल (सामान्य) पूर्वता ग्राफ में उत्पन्न होता है, यदि और केवल यदि संघर्ष-क्रमबद्धता का उल्लंघन किया जाता है।
सभी आदान-प्रदान के पूर्ववर्ती ग्राफ में प्रत्येक चक्र पर एक अनिर्णीत (न तो प्रतिबद्ध, न ही निरस्त) आदान-प्रदान को समाप्त करके प्रतिबद्ध आदान-प्रदान के चक्र को रोका जा सकता है, अन्यथा जो प्रतिबद्ध आदान-प्रदान के चक्र में (और प्रतिबद्ध आदान-प्रदान को निरस्त नहीं किया जा सकता है) बदल सकता है . प्रति चक्र निरस्त किया गया एक आदान-प्रदान चक्र को समाप्त करने के लिए आवश्यक और पर्याप्त संख्या में दोनों है (कुछ क्रियाविधि के तहत अधिक निरस्तता संभव हो सकते हैं, लेकिन क्रमबद्धता के लिए अनावश्यक हैं) दोनों है। चक्र निर्माण की संभावना सामान्यतः कम है, फिर भी, ऐसी स्थिति को सामान्यतः काफी मात्रा में ओवरहेड के साथ सावधानी से संभाला जाता है, क्योंकि शुद्धता सम्मिलित होती है। क्रमबद्धता के उल्लंघन की रोकथाम के कारण रद्द किए गए आदान-प्रदान को फिर से शुरू किया जाता है और तुरंत फिर से निष्पादित किया जाता है।
क्रमिकता-प्रवर्तन क्रियाविधि सामान्यतः डेटा संरचना के रूप में एक पूर्वता ग्राफ को बनाए नहीं रखते हैं, बल्कि चक्र को पूरी तरह से रोकते हैं या तोड़ते हैं (उदाहरण के लिए, नीचे SS2PL)।
सामान्य क्रियाविधि — SS2PL
मजबूत स्ट्रिक्ट टू-फेज लॉकिंग (SS2PL) 1970 के दशक के प्रारंभ दिनों से डेटाबेस प्रणाली में उपयोग किया जाने वाला (यद्यपि SS2PL नाम का SS नया है) संघर्ष क्रमबद्धता और सख्ती दोनों को लागू करने के लिए (एक विशेष स्थिति पुनर्प्राप्ति योग्यता जो किसी सूची की विफलता से प्रभावी डेटाबेस पुनर्प्राप्ति की अनुमति देती है) एक सामान्य क्रिया विधि है। इस क्रियाविधि के तहत,प्रत्येक डेटा को आदान-प्रदान द्वारा एक्सेस करने से पहले (किसी भी पढ़ने या लिखने के संचालन में) लॉक कर दिया जाता है , आइटम को एक निश्चित प्रकार के लॉक द्वारा चिह्नित किया जाता है और ऑपरेशन के आधार पर किया जाता है (और विशिष्ट आदान-प्रदान कार्यान्वयन विभिन्न प्रकार के लॉक वाले विभिन्न मॉडल उपस्थित हैं कुछ मॉडलों में, आदान-प्रदान के जीवन के दौरान लॉकिंग प्रकार बदल सकते हैं)। परिणामस्वरूप, किसी अन्य आदान-प्रदान द्वारा पहुंच को अवरुद्ध किया जा सकता है, सामान्यतः एक विरोध पर (ताला देरी या पूरी तरह से संघर्ष को संतृप्त होने से रोकता है और विरोधाभासी संचालन को अवरुद्ध करके पूर्ववर्ती ग्राफ में परिलक्षित होता है), लॉक प्रकार और अन्य आदान-प्रदान के आधार पर एक्सेस ऑपरेशन प्रकार। SS2PL क्रियाविधि को नियोजित करने का अर्थ है कि आदान-प्रदान की ओर से डेटा पर सभी लॉकिंग केवल आदान-प्रदान समाप्त होने (या तो प्रतिबद्ध या निरस्त) के बाद जारी किए जाते हैं।
SS2PL परिणामी सूची गुण का भी नाम है, जिसे कठोरता भी कहा जाता है। SS2PL दो-चरण लॉकिंग (2PL) का एक विशेष स्थिति (उचित उपसमुच्चय) है ।
आदान-प्रदान के बीच पारस्परिक रुकावट के परिणामस्वरूप गतिरोध होता है, जहाँ इन आदान-प्रदान का निष्पादन ठप हो जाता है और कोई पूर्णता नहीं हो सकती है। इस प्रकार इन आदान-प्रदान के निष्पादन को पूरा करने और संबंधित कंप्यूटिंग संसाधनों को जारी करने के लिए गतिरोधों को हल करने की आवश्यकता है। एक गतिरोध पूर्वता ग्राफ में एक संभावित चक्र का प्रतिबिंब है जो बिना लॉकिंग के घटित होता है जब विरोध संतृप्त होता है। इस तरह के संभावित चक्र से जुड़े आदान-प्रदान को समाप्त करके और चक्र को तोड़कर गतिरोध का समाधान किया जाता है। यह सामान्यतःप्रतीक्षा-के लिए ग्राफ़ का उपयोग करके पता लगाया जाता है (लॉकिंग द्वारा संतृप्त होने से लॉकिंगित संघर्षों का एक ग्राफ़; इसे अ-संतृप्त संघर्षों के ग्राफ़ के रूप में भी परिभाषित किया जा सकता है; संतृप्त नहीं होने वाले विरोधों को पूर्ववर्ती ग्राफ़ में प्रतिबिंबित नहीं किया जाता है और प्रभावित नहीं होता है क्रमबद्धता), जो इंगित करता है कि कौन सा आदान-प्रदान एक से अधिक लॉकिंग के जारी होने की प्रतीक्षा कर रहा है जिसके द्वारा अन्य आदान-प्रदान और इस ग्राफ में एक चक्र का अर्थ गतिरोध है। चक्र को तोड़ने के लिए प्रति चक्र एक आदान-प्रदान को रद्द करना पर्याप्त है। गतिरोध समाधान के कारण रद्द किए गए आदान-प्रदान को फिर से शुरू किया जाता है और तुरंत फिर से निष्पादित किया जाता है।
अन्य लागू करने वाली तकनीक
अन्य ज्ञात क्रियाविधि में सम्मिलित हैं
- वरीयता ग्राफ (या क्रमांकन ग्राफ, संघर्ष ग्राफ) चक्र उन्मूलन
- टू-फेज लॉकिंग (2PL)
- टाइमस्टैम्प आधारित क्रमणीयता नियंत्रण (TO)
- स्नैपशॉट आइसोलेशन आइसोलेशन को क्रमिक करने योग्य बनाना[5] (क्रमिक करने योग्य एसआई)
उपरोक्त (संघर्ष) क्रमिकता तकनीक अपने सामान्य रूप में पुनर्प्राप्ति योग्यता प्रदान नहीं करती है। पुनर्प्राप्ति योग्यता जोड़ने के लिए विशेष संवर्द्धन की आवश्यकता है।
आशावादी बनाम निराशावादी तकनीक
क्रमणीयता नियंत्रण तकनीक प्रमुख तीन प्रकार की होती हैं
- निराशावादी निराशावादी क्रमणीयता नियंत्रण में, एक आदान-प्रदान संघर्षों पर अन्य आदान-प्रदान के डेटा एक्सेस संचालन को अवरुद्ध करता है, और लॉकिंगन को हटाए जाने तक तक विरोध अ-संतृप्त होते हैं। यह सुनिश्चित करने के लिए किया जाता है कि संचालन जो क्रमबद्धता का उल्लंघन कर सकते हैं (और अभ्यास में भी पुनर्प्राप्ति योग्यता) नहीं होते हैं।
- आशावादी आशावादी क्रमणीयता नियंत्रण में, अन्य आदान-प्रदान के डेटा एक्सेस ऑपरेशंस संघर्षों पर अवरुद्ध नहीं होते हैं, और संघर्ष तुरंत संतृप्त हो जाते हैं। जब आदान-प्रदान तैयार अवस्था में पहुँच जाता है, यानी, इसकी चालू अवस्था पूरी हो चुकी होती है, तो आदान-प्रदान के संचालन (अन्य चल रहे आदान-प्रदान के सापेक्ष) द्वारा संभावित क्रमिकता (और व्यवहार में भी पुनर्प्राप्ति) के उल्लंघन की जाँच की जाती है: यदि उल्लंघन हुआ है, तो आदान-प्रदान सामान्यतः होता है निरस्त किया गया (कभी-कभी क्रमिकता उल्लंघन को संभालने के लिए किसी अन्य आदान-प्रदान को रद्द करना पसंद किया जाता है)। अन्यथा, यह प्रतिबद्ध है।
- अर्ध-आशावादी क्रियाविधि जो कुछ स्थितियों में लॉकिंग को अन्य स्थितियों में अवरुद्ध नहीं करते हैं और संतृप्त, अ-संतृप्त संघर्ष दोनों को नियोजित करते हैं।
तकनीक प्रकारों के बीच मुख्य अंतर उनके द्वारा उत्पन्न संघर्ष प्रकार हैं। एक निराशावादी पद्धति संघर्ष पर आदान-प्रदान के संचालन को अवरुद्ध करती है और अ-संतृप्त संघर्ष उत्पन्न करती है, जबकि एक आशावादी पद्धति ब्लॉक नहीं करती है और संतृप्त संघर्ष उत्पन्न करती है। एक अर्ध-आशावादी पद्धति दोनों संघर्ष प्रकार उत्पन्न करती है। दोनों संघर्ष प्रकार कालानुक्रमिक क्रम से उत्पन्न होते हैं जिसमें आदान-प्रदान के संचालन को संघर्ष के प्रकार से स्वतंत्र रूप से लागू किया जाता है। पूर्ववर्ती ग्राफ (संघर्ष ग्राफ) में प्रतिबद्ध आदान-प्रदान (संतृप्त संघर्षों के साथ) का एक चक्र क्रमिकता उल्लंघन का प्रतिनिधित्व करता है, और क्रमबद्धता बनाए रखने के लिए इससे बचा जाना चाहिए। वेट-फॉर ग्राफ़ में (अ-संतृप्त) संघर्षों का एक चक्र गतिरोध की स्थिति का प्रतिनिधित्व करता है, जिसे चक्र को तोड़कर हल किया जाना चाहिए। दोनों चक्र प्रकार संघर्षों से उत्पन्न होते हैं और इन्हें तोड़ा जाना चाहिए। किसी भी प्रकार की तकनीक के तहत, संतृप्त और अ-संतृप्त विरोध दोनों के लिए समान ओवरहेड के साथ संघर्षों का पता लगाया जाना चाहिए और विचार किया जाना चाहिए (सामान्यतः लॉकिंग जैसे क्रियाविधिका उपयोग करके, या तो लॉकिंग के लिए अवरुद्ध करना या अवरुद्ध नहीं करना, लेकिन संतृप्त विरोधों के लिए रिकॉर्डिंग संघर्ष)। अवरुद्ध करने की विधि में, सामान्यतः एक संदर्भ स्विचिंग संघर्ष पर होता है, जिसमें (अतिरिक्त) उपरिव्यय होता है। अन्यथा, अवरुद्ध आदान-प्रदान से संबंधित कंप्यूटिंग संसाधन निष्क्रिय, अनुपयोगी रहते हैं, जो एक बदतर विकल्प हो सकता है। जब संघर्ष बार-बार नहीं होते हैं, तो आशावादी तरीकों का विशेष रूप से लाभ होता है। विभिन्न आदान-प्रदान भार (आदान-प्रदान प्रकारों के मिश्रण) के साथ एक तकनीक प्रकार (यानी, या तो आशावादी या निराशावादी) दूसरे की सादृश्य में उत्तम प्रदर्शन प्रदान कर सकता है।
जब तक सूची क्लास स्वाभाविक रूप से अवरुद्ध नहीं होते हैं (अर्थार्थ, उन्हें डेटा-एक्सेस ऑपरेशंस ब्लॉक किए बिना लागू नहीं किया जा सकता है उदाहरण के लिए, 2PL, SS2PL और SCO ऊपर; चार्ट देखें), उन्हें आशावादी तकनीकों (जैसे, क्रमबद्धता, रिकवरेबिलिटी) का उपयोग करके भी लागू किया जा सकता है।
क्रमबद्ध बहु-संस्करण क्रमणीयता नियंत्रण
- बहुसंस्करण क्रमणीयता नियंत्रण (आंशिक कवरेज) और स्नैपशॉट आइसोलेशन में क्रमबद्ध स्नैपशॉट आइसोलेशन भी देखें
बहु-संस्करण क्रमणीयता नियंत्रण (एमवीसीसी) आज एक सामान्य प्रक्रिया है , सूची पद्धति के आधार पर जो प्रत्येक बार ऑब्जेक्ट लिखे जाने पर डेटाबेस ऑब्जेक्ट का एक नया संस्करण उत्पन्न करके और कई अंतिम प्रासंगिक संस्करणों (प्रत्येक ऑब्जेक्ट के) के आदान-प्रदान को पढ़ने के संचालन की अनुमति देकर क्रमणीयता और प्रदर्शन को बढ़ाने का एक सामान्य विधि है। MVCC को ऊपर सूचीबद्ध सभी क्रमिकता तकनीकों (SerializableSI को छोड़कर, जो मूल रूप से MVCC- आधारित है) के साथ जोड़ा जा सकता है। इसका उपयोग अधिकांश सामान्य-उद्देश्य वाले DBMS उत्पादों में किया जाता है।
एमवीसीसी आजकल आराम से क्रमबद्धता (ऊपर देखें) विधि स्नैपशॉट आइसोलेशन (एसआई) के माध्यम से विशेष रूप से लोकप्रिय है, जो कि अधिकांश ज्ञात क्रमबद्धता क्रियाविधि (कुछ मामलों में संभावित क्रमबद्धता उल्लंघन की कीमत पर) से उत्तम प्रदर्शन प्रदान करता है।SerializableSI, जो इसे क्रमिक बनाने के लिए SI का एक कुशल संवर्द्धन है, का उद्देश्य एक कुशल क्रमिक समाधान प्रदान करना है। SerializableSI का विश्लेषण MVCC के एक सामान्य सिद्धांत के माध्यम से किया गया है।
वितरित क्रमबद्धता
अवलोकन
वितरित क्रमबद्धता आदान-प्रदान वितरित प्रणाली (उदाहरण के लिए, वितरित डेटाबेस प्रणाली) की सूची की क्रमबद्धता है। इस तरह की प्रणाली "वितरित आदान-प्रदान" (जिसे "वैश्विक आदान-प्रदान" भी कहा जाता है) की विशेषता है, अर्थात, आदान-प्रदान जो कंप्यूटर प्रक्रियाओं (कंप्यूटिंग वातावरण के आधार पर सामान्य अर्थ में पृथक्करण उदाहरण के लिए, ऑपरेटिंग प्रणाली का धागा) और संभवतः नेटवर्क नोड्स का विस्तार करते हैं। वितरित आदान-प्रदान में एक से अधिक 'स्थानीय उप-आदान-प्रदान यद्यपि होते हैं, डेटाबेस आदान-प्रदान के लिए ऊपर वर्णित प्रत्येक के पास स्थिति है। स्थानीय उप-आदान-प्रदान में एकल प्रक्रिया, या अधिक प्रक्रियाएँ सम्मिलित होती हैं जो सामान्यतः एक साथ विफल (उदाहरण के लिए, प्रोसेसर कोर में) होती हैं । वितरित आदान-प्रदान को प्रतिबद्ध या निरस्त करने के बारे में अपने स्थानीय उप आदान-प्रदान के बीच आम सहमति तक पहुंचने के लिए परमाणु प्रतिबद्ध प्रोटोकॉल की आवश्यकता होती है। इस तरह के प्रोटोकॉल विफलता के अधिक जटिल मामलों (जैसे, प्रक्रिया, नोड, संचार, आदि विफलता) को संभालने के लिए दो-चरण की प्रतिबद्धता जैसे अधिक परिष्कृत प्रोटोकॉल के लिए एक साथ विफल होने वाली प्रक्रियाओं के बीच एक सरल (एक-चरण) हैंडशेक से भिन्न हो सकते हैं। वितरित क्रमबद्धता शुद्धता के लिए वितरित क्रमणीयता नियंत्रण का एक प्रमुख लक्ष्य है। इंटरनेट, क्लाउड कम्प्यूटिंग , ग्रिड कंप्यूटिंग, और छोटे पोर्टेबल, शक्तिशाली कंप्यूटिंग उपकरणों (जैसे, स्मार्टफोन) के प्रसार के साथ, वितरित अनुप्रयोगों में और बीच में शुद्धता सुनिश्चित करने के लिए प्रभावी वितरित क्रमिकता तकनीकों की आवश्यकता बढ़ रही है।
वितरित क्रमबद्धता ज्ञात केंद्रीकृत तकनीकों के वितरित संस्करणों को लागू करके प्राप्त की जाती है।[1][2]सामान्यतः, ऐसे सभी वितरित संस्करणों में संघर्ष की जानकारी (संतृप्त या अ-संतृप्त संघर्ष, या, समतुल्य, आदान-प्रदान की पूर्वता या अवरुद्ध जानकारी; संघर्ष क्रमबद्धता का सामान्यतः उपयोग किया जाता है) का उपयोग करने की आवश्यकता होती है, जो स्थानीय रूप से नहीं, बल्कि विभिन्न प्रक्रियाओं में, और दूरस्थ स्थानों में उत्पन्न होता है। इस प्रकार सूचना वितरण (उदाहरण के लिए, पूर्वता संबंध, लॉक जानकारी, टाइमस्टैम्प या टिकट) की आवश्यकता है । जब वितरित प्रणाली अपेक्षाकृत छोटे पैमाने की होती है और पूरे प्रणाली में संदेश विलंब छोटा होता है, तो तो केंद्रीकृत क्रमणीयता नियंत्रण विधियों का उपयोग अपरिवर्तित किया जा सकता है, जबकि प्रणाली में कुछ प्रक्रियाएँ या नोड संबंधित एल्गोरिदम का प्रबंधन करते हैं। यद्यपि, एक बड़े पैमाने की प्रणाली (जैसे, ग्रिड और क्लाउड) में, इस तरह की जानकारी के वितरण के कारण, पर्याप्त प्रदर्शन अर्थदंड सामान्यतः लगाया जाता है, तब भी जब विधियों के वितरित संस्करण (बनाम केंद्रीकृत वाले) का उपयोग किया जाता है, मुख्य रूप से कंप्यूटर और संचार विलंबता के कारण है। साथ ही, जब ऐसी जानकारी वितरित की जाती है, संबंधित तकनीकें सामान्यतः अच्छी तरह से स्केल नहीं करती हैं। स्केलेबिलिटी समस्याओं के संबंध में एक प्रसिद्ध उदाहरण एक वितरित लॉकिंग प्रबंधक है, जो लॉकिंग तकनीकों को लागू करने के लिए वितरित प्रणाली में लॉकिंग (अ-संतृप्त विरोध) जानकारी वितरित करता है।
यह भी देखें
- दो-चरण लॉकिंग
- स्नैपशॉट आइसोलेशन क्रमिक करने योग्य बनाना[5] स्नैपशॉट पृथक्रकरण में है।
- वैश्विक क्रमिकता, जहां वैश्विक क्रमिकता समस्या और इसके प्रस्तावित समाधान वर्णित हैं।
- रेखीयता, क्रमणीयता कंप्यूटिंग में एक अधिक सामान्य अवधारणा।
टिप्पणियाँ
- ↑ 1.0 1.1 Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987): Concurrency Control and Recovery in Database Systems (free PDF download), Addison Wesley Publishing Company, ISBN 0-201-10715-5
- ↑ 2.0 2.1 Gerhard Weikum, Gottfried Vossen (2001): Transactional Information Systems, Elsevier, ISBN 1-55860-508-8
- ↑ 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.
- ↑ Gray, J.; Helland, P.; O’Neil, P.; Shasha, D. (1996). The dangers of replication and a solution (PDF). Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. pp. 173–182. doi:10.1145/233269.233330.[permanent dead link]
- ↑ 5.0 5.1 Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): "Serializable isolation for snapshot databases", Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 729-738, Vancouver, Canada, June 2008, ISBN 978-1-60558-102-6 (SIGMOD 2008 best paper award)
संदर्भ
- 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
