टाइमस्टैम्प-आधारित समवर्ती नियंत्रण

कंप्यूटर विज्ञान में, टाइमस्टैम्प-बेस्ड कंकर्रेंसी कण्ट्रोल एल्गोरिदम एक गैर-लॉक कंकर्रेंसी कण्ट्रोल विधि है। टाइमस्टैम्प का उपयोग करके ट्रांसक्शन को सुरक्षित रूप से संभालने के लिए कुछ डेटाबेस में इसका उपयोग किया जाता है।

संचालन

धारणाएँ

• प्रत्येक टाइमस्टैम्प वैल्यू अद्वितीय है और समय में एक पल का सटीक रूप से प्रतिनिधित्व करता है।
• उच्च-मूल्य वाला टाइमस्टैम्प कम-मूल्य वाले टाइमस्टैम्प की तुलना में बाद के समय में होता है।

टाइमस्टैम्प उत्पन्न करना

टाइमस्टैम्प उत्पन्न करने के लिए कई अलग-अलग तरीकों का उपयोग किया गया है

• ट्रांसक्शन की आरंभ में सिस्टम की घड़ी के मूल्य का उपयोग टाइमस्टैम्प के रूप में करें।
• टाइमस्टैम्प के रूप में एक थ्रेड-सेफ शेयर्ड काउंटर का उपयोग करें जो ट्रांसक्शन की आरंभ में बढ़ाया जाता है।
• उपरोक्त दो विधियों का संयोजन।

औपचारिक

प्रत्येक ट्रांसक्शन ($T_{i}$) क्रियाओं की एक क्रमबद्ध सूची है ($A_{ix}$). ट्रांसक्शन अपनी पहली कार्रवाई करने से पहले ($A_{i1}$), इसे करंट टाइमस्टैम्प, या किसी अन्य कुल ऑर्डर अनुक्रम के साथ चिह्नित किया गया है: $TS(T_{i})=NOW()$. प्रत्येक ट्रांसक्शन को प्रारंभ में ट्रांसक्शन का एक एम्प्टी सेट भी दिया जाता है जिस पर यह निर्भर करता है, $DEP(T_{i})=[]$, और पुरानी ऑब्जेक्टओं का प्रारंभिक रूप से एम्प्टी सेट जिसे उसने अद्यतन किया, $OLD(T_{i})=[]$.

प्रत्येक ऑब्जेक्ट (कंप्यूटर विज्ञान) $(O_{j})$ डेटाबेस में दो टाइमस्टैम्प फ़ील्ड दिए गए हैं जिनका उपयोग कंकर्रेंसी कण्ट्रोल के अतिरिक्त अन्य नहीं किया जाता है: $RTS(O_{j})$ वह समय है जब ट्रांसक्शन में ऑब्जेक्ट का मूल्य अंतिम बार उपयोग किया गया था, $WTS(O_{j})$ वह समय है जब ट्रांसक्शन द्वारा ऑब्जेक्ट का मूल्य अंतिम बार अद्यतन किया गया था।

सभी के लिए $T_{i}$:

प्रत्येक क्रिया के लिए $A_{ix}$:

यदि $A_{ix}$ के वैल्यू का उपयोग करना चाहता है $O_{j}$:

यदि $WTS(O_{j})>TS(T_{i})$ फिर निरस्त करें (एक हालिया थ्रेड ने वैल्यू को अधिलेखित कर दिया है),

अन्यथा निर्भरता के सेट को अद्यतन करें $DEP(T_{i}).\mathrm {add} (WTS(O_{j}))$ और सेट करें $RTS(O_{j})=\max(RTS(O_{j}),TS(T_{i}))$;

यदि $A_{ix}$ का वैल्यू अद्यतन करना चाहता है $O_{j}$:

यदि $RTS(O_{j})>TS(T_{i})$ फिर निरस्त करें (एक हालिया थ्रेड पहले से ही पुराने मूल्य पर निर्भर है),

यदि $WTS(O_{j})>TS(T_{i})$ फिर छोड़ें (थॉमस लिखें नियम),

अन्यथा पिछले वैल्यूों को संग्रहित करें, $OLD(T_{i}).\mathrm {add} (O_{j},WTS(O_{j}))$, तय करना $WTS(O_{j})=TS(T_{i})$, और का वैल्यू अद्यतन करें $O_{j}$.

जबकि इसमें ट्रांसक्शन हो रहा है $DEP(T_{i})$ वह समाप्त नहीं हुआ है: स्टॉप

यदि कोई ट्रांसक्शन है $DEP(T_{i})$ वह अबोर्ट हो गया तो अबोर्ट हो गया

अन्यथा: प्रतिबद्ध.

अबोर्ट के लिए:

प्रत्येक के लिए $(\mathrm {old} O_{j},\mathrm {old} WTS(O_{j}))$ में $OLD(T_{i})$

यदि $WTS(O_{j})$ के बराबर होती है $TS(T_{i})$ फिर पुनर्स्थापित करें $O_{j}=\mathrm {old} O_{j}$ और $WTS(O_{j})=\mathrm {old} WTS(O_{j})$

अनौपचारिक

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

डेटाबेस में प्रत्येक ऑब्जेक्ट में एक रीड टाइमस्टैम्प होता है, जिसे ऑब्जेक्ट के डेटा को रीडिंग पर अपडेट किया जाता है, और एक राइट टाइमस्टैम्प होता है, जो ऑब्जेक्ट के डेटा को बदलने पर अपडेट किया जाता है।

यदि कोई ट्रांसक्शन किसी ऑब्जेक्ट को रीड चाहता है

• परन्तु ट्रांसक्शन ऑब्जेक्ट के राइट टाइमस्टैम्प से पहले प्रारंभ हुआ, इसका अर्थ है कि ट्रांसक्शन प्रारंभ होने के बाद किसी चीज़ ने ऑब्जेक्ट के डेटा को बदल दिया। इस स्थिति में, ट्रांसक्शन रद्द कर दिया गया है और इसे फिर से प्रारंभ किया जाना चाहिए।
• और ट्रांसक्शन ऑब्जेक्ट के राइट टाइमस्टैम्प के बाद प्रारंभ हुआ, इसका अर्थ है कि ऑब्जेक्ट को रीड सुरक्षित है। इस मामले में, यदि ट्रांसक्शन टाइमस्टैम्प ऑब्जेक्ट के रीड टाइमस्टैम्प के बाद है, तो रीड टाइमस्टैम्प को ट्रांसक्शन टाइमस्टैम्प पर सेट किया जाता है।

यदि कोई ट्रांसक्शन किसी ऑब्जेक्ट को राइट चाहता है,

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

पुनर्प्राप्ति

For रेटरीएवब्ले (RC), कैस्केडिंग अबोर्ट से बचा जाता है (ACA) और सख्त (ST) शब्दों की व्याख्या, see शेड्यूल (कंप्यूटर विज्ञान).

ध्यान दें कि अपने मूल रूप में टाइमस्टैम्प ऑर्डर पुनर्प्राप्ति योग्य इतिहास उत्पन्न नहीं करता है। उदाहरण के लिए ट्रांसक्शन के निम्नलिखित इतिहास पर विचार करें $T_{1}$ और $T_{2}$:

$W_{1}(x)\;R_{2}(x)\;W_{2}(y)\;C_{2}\;R_{1}(z)\;C_{1}$

इसे टीओ शेड्यूलर द्वारा तैयार किया जा सकता है, परन्तु यह पुनर्प्राप्त करने योग्य नहीं है $T_{2}$ एक अप्रतिबद्ध ट्रांसक्शन से रीडिंग के अतिरिक्त भी प्रतिबद्ध है। यह सुनिश्चित करने के लिए कि यह पुनर्प्राप्त करने योग्य इतिहास तैयार करता है, एक शेड्यूलर प्रत्येक ट्रांसक्शन से पढ़े गए अन्य ट्रांसक्शन की एक सूची रख सकता है, और इस सूची में केवल प्रतिबद्ध ट्रांसक्शन शामिल होने से पहले किसी ट्रांसक्शन को प्रतिबद्ध नहीं होने दे सकता है। कैस्केडिंग अबोर्ट से बचने के लिए, शेड्यूलर अनकमिटेड ट्रांसक्शन द्वारा लिखे गए डेटा को गंदे के रूप में टैग कर सकता है, और अनटैग किए जाने से पहले ऐसे डेटा आइटम पर कभी भी रीड ऑपरेशन प्रारंभ नहीं होने देता। सख्त इतिहास प्राप्त करने के लिए, अनुसूचक को गंदी ऑब्जेक्टओं पर किसी भी संचालन की अनुमति नहीं देनी चाहिए।

कार्यान्वयन मुद्दे

टाइमस्टैम्प रिज़ॉल्यूशन

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

टाइमस्टैम्प लॉकिंग

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

यह भी देखें

• बहुसंस्करण कंकर्रेंसी कण्ट्रोल
• टाइमस्टैम्पिंग (कंप्यूटिंग)