Google.com पेज हिट कैसे गिनें? और बहुत लोकप्रिय उपयोगकर्ताओं की पसंद के काउंटर को कैसे स्टोर करें? इस लेख में CRDT (कंफ्लिक्ट-फ्री रेप्लिकेटेड डेटा टाइप्स का उपयोग करके इन समस्याओं को हल करने पर विचार करने का प्रस्ताव है, जो रूसी में मोटे तौर पर कॉन्फ्लिक्ट-फ्री रेप्लिकेटेड डेटा टाइप्स के रूप में अनुवादित हैं) और अधिक सामान्य स्थिति में, कई प्रमुख नोड्स के साथ एक वितरित सिस्टम में प्रतिकृति सिंक्रनाइज़ेशन कार्यों को दोहराता है।

1. परिचय

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

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

2. मजबूत अंतिम स्थिरता

हाल ही में, बहुत सारे काम लिखे गए हैं और अंततः निरंतरता के क्षेत्र में बहुत सारे शोध किए गए हैं। मेरी राय में, अब एक निरंतरता के लिए विभिन्न विकल्पों के लिए मजबूत स्थिरता से विभिन्न विकल्पों के लिए एक बदलाव की ओर रुझान है, जो मौजूदा स्थितियों को पुनर्विचार करने के लिए लागू करने के लिए स्थितियों / प्रणालियों के लिए अधिक लाभदायक है, जिसमें स्थिरता। यह कुछ भ्रम की ओर जाता है, उदाहरण के लिए, जब कुछ कार्यों के लेखक, स्थिरता के बारे में बात करते हैं, तो कुछ अतिरिक्त संपत्ति के साथ अंतिम सुसंगतता, और अन्य लेखक इसके लिए कुछ शब्दावली का उपयोग करते हैं।

किसी एक लेख के लेखकों द्वारा उठाया गया प्रश्न अंततः सुसंगतता की वर्तमान परिभाषा की आलोचना करता है: इसके अनुसार, यदि आपका सिस्टम हमेशा सभी अनुरोधों का "42" जवाब देता है, तो सब कुछ ठीक है, यह अंततः सुसंगत है।

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

• मजबूत स्थिरता (एससी): सभी लिखने के संचालन को कड़ाई से आदेश दिया जाता है, किसी भी प्रतिकृति पर पढ़ने का अनुरोध समान, अंतिम रिकॉर्ड किए गए परिणाम देता है। संघर्षों को हल करने के लिए वास्तविक समय की आम सहमति की आवश्यकता होती है (आगामी परिणामों के साथ), n / 2 - 1 नोड्स में गिरावट का सामना कर सकता है।
• अंततः स्थिरता (ईसी): डेटा को स्थानीय रूप से अपडेट करें, अपडेट को आगे भेजें। विभिन्न प्रतिकृतियों पर पढ़ने से बासी डेटा वापस आ सकता है। संघर्ष के मामले में, हम या तो वापस रोल करते हैं, या किसी तरह तय करते हैं कि क्या करना है। इस प्रकार आम सहमति की जरूरत है, लेकिन अब वास्तविक समय में नहीं ।
• मजबूत अंतिम स्थिरता (एसईसी): ईसी + संघर्षों को हल करने के लिए, प्रतिकृतियों में एक पूर्वनिर्धारित एल्गोरिदम है। इस प्रकार आम सहमति की आवश्यकता नहीं है , यह n - 1 नोड्स के लिए एक बूंद का सामना कर सकता है।

ध्यान दें कि SEC (जैसा भी था) CAP प्रमेय की समस्या को हल करता है: तीनों गुण संतुष्ट हैं।

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

3. पसंद और हिट के बारे में कार्य

निस्संदेह, ऐसी समस्याओं को हल करने के लिए कई एल्गोरिदम हैं। CRDT एक बहुत ही सुंदर और आसान तरीका प्रदान करता है।

Google.com हिट गणना:

google.com दुनिया भर से प्रति सेकंड लगभग 150,000 अनुरोधों को संसाधित करता है। जाहिर है, काउंटर को अतुल्यकालिक रूप से अपडेट करने की आवश्यकता है। कतारें आंशिक रूप से समस्या को हल करती हैं - उदाहरण के लिए, यदि हम इस मूल्य को प्राप्त करने के लिए एक बाहरी एपीआई प्रदान करते हैं, तो हमें प्रतिकृति करना होगा ताकि पढ़ने के अनुरोधों के साथ भंडार न डालें। और अगर वहाँ पहले से ही प्रतिकृति है, शायद वैश्विक कतारों के बिना?

उपयोगकर्ता पसंद की गणना:

कार्य पिछले एक के समान है, केवल अब आपको अद्वितीय हिट गिनने की आवश्यकता है।

4. शब्दावली

लेख की अधिक संपूर्ण समझ के लिए, आपको निम्नलिखित शर्तों के बारे में जानना होगा:

1. idempotency
   कहते हैं कि कई बार ऑपरेशन को लागू करने से परिणाम नहीं बदलता है।
   उदाहरण - शून्य के साथ ऑपरेशन या जोड़: $$$f (x) = x + 0$
   
2. commutativity
   $$$f (x, y) = f (y, x)$
   
3. आंशिक आदेश
   रिफ्लेक्सिटि + ट्रांज़िटिविटी + एंटीसिमेट्री
   
4. semilattice
   आंशिक रूप से ऑर्डर किए गए सटीक ऊपरी (निचले) चेहरे के साथ
   
5. संस्करण वेक्टर
   एक आयाम वेक्टर नोड्स की संख्या के बराबर है, और प्रत्येक नोड, जब एक निश्चित घटना होती है, तो वेक्टर में इसके मूल्य में वृद्धि होती है। सिंक्रनाइज़ेशन के दौरान, डेटा इस वेक्टर के साथ प्रेषित होता है और यह एक ऑर्डर रिलेशन पेश करता है, जो आपको यह निर्धारित करने की अनुमति देता है कि किस प्रतिकृति में पुराने / नए डेटा हैं।

5. सिंक मॉडल

राज्य आधारित (हालत तुल्यकालन):

इसे निष्क्रिय सिंक्रोनाइज़ेशन भी कहा जाता है, यह संमिलित प्रतिकृति डेटा प्रकार - CvRDT बनाता है।
इसका उपयोग एनएफएस, एएफएस, कोडा और केवी-स्टोरेज रीक, डायनामो जैसी फाइल सिस्टम में किया जाता है
इस स्थिति में, प्रतिकृतियां सीधे राज्यों को बताती हैं, प्राप्त प्रतिकृति अपने वर्तमान स्थिति के साथ प्राप्त स्थिति को मिला देती है।


इस सिंक्रनाइज़ेशन का उपयोग करके प्रतिकृतियों का अभिसरण करना, यह आवश्यक है कि:

• डेटा ने एक अर्धविराम का गठन किया
• मर्ज फ़ंक्शन ने एक सटीक ऊपरी बाउंड का उत्पादन किया
• प्रतिकृतियों ने एक जुड़ा हुआ ग्राफ बनाया।

एक उदाहरण:

• डेटासेट: प्राकृतिक संख्या $$$\ mathbb {N}$
• न्यूनतम आइटम: $$$- \ infty$
• $$$मर्ज (x, y) = अधिकतम (x, y)$

इस तरह की आवश्यकताएं हमें एक कम्यूटेटिव और बेमिसाल मर्ज फंक्शन प्रदान करती हैं जो किसी दिए गए डेटा सेट पर एकात्मक रूप से बढ़ता है :


यह सुनिश्चित करता है कि प्रतिकृतियां जल्द या बाद में अभिसरण करती हैं और आपको डेटा ट्रांसफर प्रोटोकॉल के बारे में चिंता करने की अनुमति नहीं देती हैं - हम एक नए राज्य के साथ संदेश खो सकते हैं, उन्हें कई बार भेज सकते हैं, और उन्हें किसी भी क्रम में भेज सकते हैं ।

ऑपरेशन के आधार पर (तुल्यकालन संचालन):

जिसे एक्टिव सिंक्रोनाइज़ेशन भी कहा जाता है, यह कम्यूटेटिव रेप्लिकेटेड डेटा टाइप - CmRDT बनाता है।
बेऊ, रोवर, आइसक्यूब, टेलेक्स जैसी सहकारी प्रणालियों में उपयोग किया जाता है।

इस स्थिति में, प्रतिकृतियां राज्य अद्यतन कार्रवाई का आदान-प्रदान करती हैं। डेटा अपडेट करते समय, मूल प्रतिकृति:

• उत्पन्न () विधि को कॉल करता है, जो प्रभावकारक () विधि को शेष प्रतिकृतियों पर क्रियान्वित करता है। दूसरे शब्दों में, प्रभावकारक () शेष प्रतिकृतियों की स्थिति को बदलने के लिए बंद है।
• एक स्थानीय राज्य के लिए एक असरदार लागू करना
• अन्य सभी प्रतिकृतियों के लिए प्रभावकारिता भेजता है

प्रतिकृतियों के अभिसरण करने के लिए, निम्नलिखित शर्तों को पूरा करना होगा:

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

डेल्टा आधारित:

राज्य / ऑप आधारित को देखते हुए, यह नोटिस करना आसान है कि यदि कोई अपडेट केवल राज्य का एक हिस्सा बदलता है, तो इससे पूरे राज्य को भेजने का कोई मतलब नहीं है, और यदि बड़ी संख्या में परिवर्तन एक राज्य को प्रभावित करते हैं (उदाहरण के लिए, एक काउंटर), तो आप एक, एकत्रित परिवर्तन, और सभी कार्यों को नहीं भेज सकते हैं। बदल जाते हैं।

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

अगला अनुकूलन विधि op- आधारित लॉग को संपीड़ित करने के लिए है, यदि विलंब की अनुमति है।

शुद्ध संचालन-आधारित:

Op- आधारित सिंक्रोनाइज़ेशन में opector बनाने में देरी होती है। कुछ प्रणालियों में यह स्वीकार्य नहीं हो सकता है, फिर आपको प्रोटोकॉल को जटिल करने और मेटाडेटा की अतिरिक्त राशि की लागत पर मूल परिवर्तन बाहर भेजना होगा।

मानक उपयोग दृष्टिकोण:

• यदि सिस्टम में अपडेट तुरंत भेजा जाना है, तो राज्य-आधारित एक बुरा विकल्प होगा, क्योंकि पूरे राज्य को भेजने के लिए सिर्फ एक अपडेट ऑपरेशन की तुलना में अधिक महंगा है। डेल्टा-आधारित बेहतर काम करता है, लेकिन इस विशेष मामले में, राज्य-आधारित के साथ अंतर छोटा होगा।
• यदि आपको विफलता के बाद प्रतिकृति को सिंक्रनाइज़ करने की आवश्यकता है, तो राज्य-आधारित और डेल्टा-आधारित सही विकल्प हैं। यदि आपको op-based का उपयोग करना है, तो विकल्प हैं:
  
  1) विफलता के क्षण से सभी मिस्ड ऑपरेशन को रोल करें
  2) प्रतिकृतियों में से एक की एक पूरी प्रतिलिपि और मिस्ड ऑपरेशन के रोलबैक
• जैसा कि ऊपर उल्लेख किया गया है, ऑप-आधारित की आवश्यकता है कि अपडेट प्रत्येक प्रतिकृति के ठीक एक बार वितरित किए जाएं। डिलीवरी की आवश्यकता केवल एक बार छोड़ी जा सकती है, यदि प्रभावकारक बेकार है। व्यवहार में, पहले को दूसरे की तुलना में लागू करना बहुत आसान है।

ओप-आधारित और राज्य-आधारित के बीच संबंध:

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

6. CRDT

६.१ काउंटर

एक पूर्णांक जो दो संचालन का समर्थन करता है: इंक और डिक। एक उदाहरण के रूप में, op- आधारित और राज्य-आधारित सिंक्रनाइज़ेशन के लिए संभावित कार्यान्वयन पर विचार करें:

Op- आधारित काउंटर:

स्पष्ट रूप से पर्याप्त है, बस अपडेट भेज रहा है। Inc के लिए उदाहरण:

function generator() { return function (counter) { counter += 1 } } 

राज्य-आधारित काउंटर:

कार्यान्वयन अब इतना स्पष्ट नहीं है, क्योंकि यह स्पष्ट नहीं है कि मर्ज फ़ंक्शन कैसा दिखना चाहिए।

निम्नलिखित विकल्पों पर विचार करें:

नीरस रूप से बढ़ता हुआ काउंटर (वृद्धि केवल काउंटर, जी-काउंटर):

डेटा को नोड्स (संस्करण वेक्टर) की संख्या के बराबर आयाम के वेक्टर के रूप में संग्रहीत किया जाएगा और प्रत्येक प्रतिकृति अपनी आईडी के साथ स्थिति में मूल्य में वृद्धि करेगी।

मर्ज फ़ंक्शन संबंधित स्थितियों में अधिकतम लेगा, और अंतिम मान वेक्टर के सभी तत्वों का योग है

$$

$$\ start {align} inc () &: V [id ()] = V [id ()] + 1 \\ मान () और: \ sum_ {i = 0} ^ {n} V [i] \\ मर्ज (C_1, C_2) और: i \ में [1..n] \ _ परिणाम [i] = अधिकतम (C_1.V [i], C_2.V [i] \ अंत {संरेखित}$$

आप जी-सेट का उपयोग भी कर सकते हैं (नीचे देखें)

आवेदन:

• क्लिक / हिट (sic!) की गिनती

वेतन वृद्धि समर्थन (पीएन-काउंटर) के साथ काउंटर

हम दो जी-काउंटर शुरू करते हैं - एक वेतन वृद्धि संचालन के लिए, दूसरा - वेतन वृद्धि के लिए

आवेदन:

• पी 2 पी नेटवर्क में लॉग-इन उपयोगकर्ताओं की संख्या, जैसे स्काइप

गैर-नकारात्मक काउंटर

एक साधारण कार्यान्वयन अभी तक मौजूद नहीं है। टिप्पणियों में अपने विचारों का सुझाव दें, चर्चा करें।

6.2 रजिस्टर

दो ऑपरेशन के साथ एक मेमोरी सेल - असाइन (लेखन) और मूल्य (पढ़ें)।
समस्या यह है कि असाइनमेंट कम्यूटेटिव नहीं है। इस समस्या को हल करने के लिए दो दृष्टिकोण हैं:

अंतिम-लिखें-जीत रजिस्टर (LWW- रजिस्टर):

हम प्रत्येक ऑपरेशन (उदाहरण के लिए टाइमस्टैम्प) के लिए अद्वितीय आईडी की पीढ़ी के माध्यम से पूर्ण आदेश दर्ज करते हैं।

सिंक्रोनाइज़ेशन का एक उदाहरण है जोड़े का आदान-प्रदान (मूल्य, आईडी):


आवेदन:

• कैसेंड्रा में कॉलम
• एनएफएस - पूरे या आंशिक रूप से फ़ाइल

कई मूल्यों के साथ रजिस्टर (मल्टी-वैल्यू रजिस्टर, एमवी-रजिस्टर):

दृष्टिकोण जी-काउंटर के समान है - हम सेट (मूल्य, संस्करण वेक्टर) को संग्रहीत करते हैं। रजिस्टर मूल्य - सभी मान, जब विलय - एलडब्ल्यूडब्ल्यू वेक्टर में प्रत्येक मूल्य के लिए अलग से।


आवेदन:

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

अमेज़न में बग की व्याख्या:

6.3 बहुत

सेट कंटेनर, नक्शे और ग्राफ़ के निर्माण के लिए मूल प्रकार है और संचालन - ऐड और आरएमवी का समर्थन करता है, जो कि कम्यूटेटिव नहीं हैं।

ऑप-आधारित सेट के अनुभवहीन कार्यान्वयन पर विचार करें, जिसमें ऐड और आरएमवी निष्पादित होते हैं जैसे वे आते हैं (एक ही समय में 1 और 2 प्रतिकृतियां आती हैं, फिर आरएमवी 1 पर जाता है)


जैसा कि आप देख सकते हैं, प्रतिकृतियां अंततः छितरी हुई हैं। संघर्ष-मुक्त सेटों के निर्माण के विभिन्न विकल्पों पर विचार करें:

बढ़ते सेट (जी-सेट):

सबसे आसान उपाय है कि आइटम को डिलीट होने से रोका जाए। जो कुछ बचता है वह ऐड ऑपरेशन है, जो कम्यूटेटिव है। मर्ज फ़ंक्शन सेट का संघ है।

दो चरण सेट (2P- सेट):

हम आपको हटाने की अनुमति देते हैं, लेकिन आप इसे हटाने के बाद फिर से नहीं जोड़ सकते। लागू करने के लिए, हम दूरस्थ G- सेट तत्वों का एक अलग सेट बनाते हैं (इस तरह के सेट को एक समाधि का पत्थर सेट कहा जाता है)
राज्य-आधारित के लिए उदाहरण:

$$

$$\ start {align} लुकअप (e) &: e \ _ A \ land e \ not में R \\ add (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ मर्ज (S_1, S_2) और: \\ Res & ult.A = S_1.A \ कप S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {संरेखित}$$

LWW- तत्व सेट:

संघर्ष-मुक्त सेट को लागू करने का अगला तरीका एक पूर्ण आदेश पेश करना है, विकल्पों में से एक प्रत्येक तत्व के लिए अद्वितीय टाइमस्टैम्प उत्पन्न करना है।

हमें दो सेट मिलते हैं - ऐड-सेट और रिमूव-सेट, जब ऐड () कहा जाता है, ऐड (एलिमेंट, यूनीक_ड ()), जब चेक करते हैं कि सेट में कोई एलिमेंट है - देखो जहां टाइमस्टैम्प अधिक है - रिमूव-सेट में या ऐड-सेट में

पी एन-सेट:

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

दिलचस्प प्रभाव पर ध्यान दें - तीसरे प्रतिकृति में, एक तत्व जोड़ने से इसकी उपस्थिति नहीं होती है।

अवलोकन-निकालें सेट, OR- सेट, ऐड-विन सेट:

इस प्रकार में, ऐड हटाने पर पूर्वता लेता है। कार्यान्वयन उदाहरण: प्रत्येक नए जोड़े गए तत्व को एक अद्वितीय टैग (तत्व के सापेक्ष, और संपूर्ण सेट नहीं) सौंपा गया है। Rmv सेट से एक तत्व निकालता है और हटाने के लिए सभी देखे गए जोड़े (तत्व, टैग) को प्रतिकृतियों में भेजता है।

निकालें-सेट जीत:

पिछले एक के समान है, लेकिन एक ही समय में / rmv rmv जीतता है।

6.4 ग्राफ

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

• RemoveVertex प्राथमिकता, इस शीर्ष पर सभी किनारों की घटना को हटा दिया जाता है
• AddEdge प्राथमिकता, हटाए गए कोने हटाए गए
• जब तक सभी एक साथ addEdge निष्पादित नहीं हो जाते हैं, तब तक हम removeVertex के निष्पादन में देरी करते हैं।

सबसे आसान विकल्प पहला है, इसके कार्यान्वयन के लिए (2P2P- ग्राफ़) दो 2P- सेट प्राप्त करने के लिए पर्याप्त है, एक कोने के लिए, दूसरा किनारों के लिए

6.5 मानचित्र

शाब्दिक मानचित्र:

हल करने के लिए दो समस्याएं:

• एक साथ संचालन के साथ क्या करना है? काउंटरों के साथ समानता से, आप LWW या MV शब्दार्थ चुन सकते हैं
• एक साथ पुट / rmv का क्या करें? सेट के साथ सादृश्य से, आप या तो जीत, या rmv-win, या अंतिम-पुट-जीत शब्दार्थ डाल सकते हैं।

CRDT मैपिंग (CRDT का मानचित्र):

एक और दिलचस्प मामला है, क्योंकि आपको नेस्टेड मैपिंग बनाने की अनुमति देता है। हम नेस्टेड प्रकार को बदलने के मामलों पर विचार नहीं करते हैं - यह नेस्टेड CRDT द्वारा ही तय किया जाना चाहिए।

निकालें-के रूप में पुनरावर्ती-रीसेट नक्शा

निकालें ऑपरेशन "रीसेट" एक निश्चित प्रारंभिक अवस्था के प्रकार के मूल्य। उदाहरण के लिए, एक काउंटर के लिए, यह एक शून्य मान है।

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


निकालें-जीतता नक्शा

ऑपरेशन rmv पूर्वता लेता है।

उदाहरण: एक ऑनलाइन गेम में, एक ऐलिस खिलाड़ी के पास 10 सिक्के और एक हथौड़ा होता है। फिर एक साथ दो घटनाएं घटती हैं: प्रतिकृति ए पर, उसने एक कील का उत्पादन किया, और प्रतिकृति बी पर, उसके चरित्र को सभी वस्तुओं को हटाने के साथ हटा दिया गया है:



ध्यान दें कि हटाने-पुनरावृत्ति का उपयोग करते समय, एक कील अंततः बनी रहेगी, जो चरित्र को हटाए जाने पर सही स्थिति नहीं है।

अद्यतन-जीतता नक्शा

अद्यतनों में पूर्ववर्ती स्थिति होती है, या यों कहें, साथ-साथ rmv को हटाने के लिए पिछले ऑपरेशनों को रद्द करें।

उदाहरण: एक ऑनलाइन गेम में, प्रतिकृति B पर ऐलिस वर्ण निष्क्रियता के कारण हटा दिया जाता है, लेकिन एक ही समय में प्रतिकृति A पर गतिविधि होती है। जाहिर है, डिलीट ऑपरेशन रद्द होना चाहिए।


इस तरह के कार्यान्वयन के साथ काम करते समय एक दिलचस्प प्रभाव होता है - मान लीजिए कि हमारे पास दो प्रतिकृतियां हैं, ए और बी, और वे कुछ कुंजी के द्वारा सेट को स्टोर करते हैं। फिर, यदि A कुंजी k का मान हटाता है, और B सेट के सभी तत्वों को हटा देता है, तो अंत में प्रतिकृतियां कुंजी k के साथ एक खाली सेट छोड़ देंगी।

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

सूची (सूची)

इस प्रकार के साथ समस्या यह है कि अलग-अलग प्रतिकृतियों पर आइटम सूचकांक स्थानीय सम्मिलित / हटाने के संचालन के बाद अलग-अलग होंगे। इस समस्या को हल करने के लिए, संचालन परिवर्तन दृष्टिकोण लागू किया जाता है - प्राप्त परिवर्तन को लागू करते समय, मूल प्रतिकृति में तत्व के सूचकांक को ध्यान में रखा जाना चाहिए।

7. रिआक

एक उदाहरण के रूप में, RiD में CRDT पर विचार करें:

• काउंटर: पीएन-काउंटर
• सेट: OR- सेट
• मानचित्र: CRDTs का अपडेट-विन मैप
• (बुलियन) ध्वज: OR-Set जहां अधिकतम 1 तत्व
• रजिस्टर: जोड़े (मूल्य, टाइमस्टैम्प)

8. CRDT का उपयोग कौन करता है

विकि अनुभाग में अच्छे उदाहरण हैं।

9. सन्दर्भ

• की-सीआरडीटी स्टोर्स
• एक संघर्ष-मुक्त प्रतिकृति JSON डेटाटाइप
• अभिसरण और Commutative प्रतिकृति डेटा प्रकारों का एक व्यापक अध्ययन
• अभिसरण और Commutative प्रतिकृति डेटा प्रकार
• संघर्ष-मुक्त प्रतिकृति डेटा प्रकार
• एक Bluffers गाइड RiD में CRDTs के लिए
• CRDTs: एक अद्यतन (या सिर्फ एक अंक)
• संघर्ष-मुक्त प्रतिकृति डेटा प्रकार: एक अवलोकन
• मजबूत अंततः संगति और संघर्ष-मुक्त डेटा प्रकार
• आखिरकार-लगातार डेटा संरचनाएं