दो आदेशित सूचियों को सिंक्रनाइज़ करें

Question

हमारे पास दो ऑफ़लाइन सिस्टम हैं जो आम तौर पर एक दूसरे के साथ संवाद नहीं कर सकते हैं। दोनों सिस्टम वस्तुओं की एक ही आदेशित सूची बनाए रखते हैं। सूची में सिंक्रनाइज़ करने के लिए वे शायद ही कभी एक दूसरे के साथ संवाद करने में सक्षम होंगे।

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

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

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

अधिमानतः, हम डेटा संरचना या एल्गोरिदम का उपयोग करना चाहते हैं जहां केवल नए डाले गए आइटम को सिंक्रनाइज़ करने की आवश्यकता है। क्या ऐसी डेटा संरचना मौजूद है?

संपादित करें: हमें किसी मौजूदा आइटम को एक अलग स्थिति में स्थानांतरित करने में सक्षम होने की आवश्यकता है!

Answer 1

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

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

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

Answer 2

आप "लेंस" पर एक नज़र डाल सकते हैं, जो कि बिडरेक्शनल प्रोग्रामिंग अवधारणा है। उदाहरण के लिए, आपकी समस्या को this paper में वर्णित मेरे "मिलान लेंस" को हल किया गया प्रतीत होता है।

Answer 3

मुझे लगता है कि यहां उपयुक्त डेटास्ट्रक्चर order statistic tree है। सांख्यिकीय वृक्ष के क्रम में आपको अन्य डेटा के साथ उपट्री के आकार को बनाए रखने की भी आवश्यकता है, आकार क्षेत्र रैंक द्वारा तत्व को ढूंढने में आसान बनाता है जैसा आपको इसकी आवश्यकता है। रैंक, डिलीट, चेंज पोजिशन, डालने जैसे सभी ऑपरेशंस O(logn) हैं।

Answer 4

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

Let हम दोनों सिस्टम पर निम्नलिखित प्रारंभिक अवस्था है:

|1| |2| 
--- --- 
|A| |A| 
|B| |B| 
|C| |C| 
|D| |D| 

के बाद पहली प्रणाली हटाने के लिए तत्व A के निशान और दूसरी प्रणाली तत्व BC सम्मिलित करता B और C के बीच कि:

|1   | |2   | 
------------ -------------- 
|A   | |A   | 
|B[deleted]| |B   | 
|C   | |BC[inserted]| 
|D   | |C   | 
       |D   | 

दोनों सिस्टम accou में प्रसंस्करण जारी रखते हैं एनटी स्थानीय परिवर्तन, सिस्टम 1 तत्व B को अनदेखा करता है और सिस्टम 2 तत्व तत्व BC सामान्य तत्व के रूप में व्यवहार करता है।

जब तुल्यकालन होती है:

मैं समझता हूँ के रूप में, प्रत्येक प्रणाली अन्य प्रणाली से सूची स्नैपशॉट प्राप्त करता है और दोनों प्रणालियों प्रसंस्करण फ्रीज जब तक तुल्यकालन समाप्त कर दिया जाएगा।

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

|1 pre-sync|    |2-SNAPSHOT | |1 result| 
------------    -------------- ---------- 
|A   | <the same> |A   | |A  | 
|B[deleted]| <delete B> |B   | 
      <insert BC> |BC[inserted]| |BC  | 
|C   | <same>  |C   | |C  | 
|D   | <same>  |D   | |D  | 

सिस्टम जगा और प्रसंस्करण जारी है।

आइटम सम्मिलन आदेश द्वारा क्रमबद्ध किए जाते हैं, चलती एक साथ हटाने और सम्मिलन के रूप में कार्यान्वित किया जा सकता है। साथ ही मुझे लगता है कि पूरे सूची के आकार को स्थानांतरित करना संभव नहीं होगा, लेकिन वास्तव में उन वस्तुओं की सूची जो वास्तव में संशोधित की गई थीं।

Answer 5

मुझे लगता है कि, व्यापक रूप से, Operational Transformation आप जिस समस्या का वर्णन कर रहे हैं उससे संबंधित हो सकता है। उदाहरण के लिए, रीयल-टाइम सहयोगी पाठ संपादन की समस्या पर विचार करें।

हमारे पास अनिवार्य रूप से वस्तुओं (शब्दों) की एक क्रमबद्ध सूची है जिसे सिंक्रनाइज़ किया जाना चाहिए, और जिसे सूची में यादृच्छिक रूप से जोड़ा/संशोधित/हटाया जा सकता है। मैं देखता हूं कि एकमात्र बड़ा अंतर सूची में संशोधन की आवधिकता में है। (आप कहते हैं कि यह अक्सर नहीं होता है)

परिचालन परिवर्तन अच्छी तरह से अध्ययन किया जाने वाला क्षेत्र होता है। मैं this blog article पॉइंटर्स और परिचय दे सकता था। इसके अलावा, Google वेव की सभी समस्याओं के लिए, उन्होंने वास्तव में ऑपरेशनल ट्रांसफॉर्म के डोमेन में महत्वपूर्ण प्रगति की। this out. देखें। इस विषय पर बहुत सारे साहित्य उपलब्ध हैं। इस stackoverflow thread पर देखें, और लगभग Differential Synchronisation

टेक्स्ट एडिटर्स - Ropes में उपयोग की जाने वाली डेटा संरचना एक और समानांतर है। तो यदि आपके पास ऑपरेशन का लॉग है, तो कहें, "इंडेक्स 5 हटा दिया गया", "इंडेक्स 6 एबीसी में संशोधित", "इंडेक्स 8 डाला गया", अब आपको सिस्टम से किए गए परिवर्तनों का लॉग ट्रांसमिट करना है ए सिस्टम बी के लिए, और फिर दूसरी तरफ अनुक्रमिक रूप से संचालन का पुनर्निर्माण करें।

अन्य "व्यावहारिक अभियंता" की पसंद सिस्टम बी में पूरी तरह से सिस्टम बी पर पुनर्निर्माण करना होगा जब सिस्टम ए बदलता है। वास्तविक आवृत्ति और परिवर्तनों के आकार के आधार पर, यह उतना बुरा नहीं हो सकता जितना लगता है।

Answer 6

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

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

Answer 7

इंटरपोलेटेड रैंक दृष्टिकोण के साथ वास्तव में कोई समस्या नहीं है। बस अपनी खुद की संख्या प्रणाली को परिवर्तनीय लंबाई बिट वैक्टरों के आधार पर परिभाषित करें जो 0 और 1 के बीच बाइनरी भिन्नताओं का प्रतिनिधित्व नहीं करते हैं। द्विआधारी बिंदु पहले अंक के बाईं ओर है।

इस प्रणाली की एकमात्र असुविधा यह है कि न्यूनतम बिट वेक्टर द्वारा न्यूनतम संभव कुंजी 0 दी गई है। इसलिए आप इसका उपयोग केवल तभी करते हैं जब आप सकारात्मक हों, संबंधित आइटम हमेशा के लिए पहली सूची तत्व होगा। आम तौर पर, केवल पहला आइटम कुंजी 1 दें। यह 1/2 के बराबर है, इसलिए श्रेणी (0..1) में यादृच्छिक सम्मिलन बिट उपयोग को कम करने के लिए प्रवृत्त होंगे। पहले और बाद में एक आइटम को जोड़ करने के लिए,

01 < newly interpolated = 1/4 
1 
11 < newly interpolated = 3/4 

फिर अंतर्वेशन के लिए:

001 < newly interpolated = 1/8 
01 
011 < newly interpolated = 3/8 
1 
101 < newly interpolated = 5/8 
11 
111 < newly interpolated = 7/8 

ध्यान दें कि यदि आप चाहें तो आप अंतिम 1 भंडारण छोड़ सकते हैं! सभी कुंजियां (0 को छोड़कर जिन्हें आप आम तौर पर उपयोग नहीं करेंगे) 1 में समाप्त होता है, इसलिए इसे संग्रहीत करना उचित है।

बाइनरी अंशों की तुलना लेक्सिकल तुलना की तरह बहुत अधिक है:1 और बाएं से दाएं स्कैन में पहला अंतर अंतर आपको बताता है कि कौन सा है। यदि कोई मतभेद नहीं होता है, यानी एक वेक्टर दूसरे का सख्त उपसर्ग है, तो छोटा छोटा होता है।

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

उपरोक्त उदाहरण में, विलोपन के साथ हमें छोड़ दिया था, तो:

01 
111 

और हम, इन अंतर्वेशन 1.001 प्राप्त करने के लिए 01(0) और और 111 जोड़ने की जरूरत है, तो 1001 पाने के लिए बदलाव। यह एक interpolant के रूप में ठीक काम करता है। लेकिन ध्यान दें कि अंतिम 1 अनावश्यक रूप से इसे किसी भी ऑपरेंड से अधिक लंबा बनाता है। 1 प्राप्त करने के लिए पीछे की ओर शून्य के साथ अंतिम 1 बिट को छोड़ना एक आसान अनुकूलन है। निश्चित रूप से पर्याप्त, 1 हम उम्मीद करेंगे के बीच लगभग आधा रास्ता है।

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

अलावा

हालांकि मैं इसे करने की कोशिश नहीं की है, Postgres bit string type कुंजी मैं का वर्णन किया है के लिए पर्याप्त लगता है। जिस चीज को मुझे सत्यापित करने की आवश्यकता होगी वह यह है कि संयोजन आदेश सही है।

इसके अलावा, वही तर्क किसी भी k>=2 के लिए बेस-के अंकों के साथ ठीक काम करता है। पहला आइटम कुंजी k/2 प्राप्त करता है। एक सरल अनुकूलन भी है जो लम्बाई ओ (एन) की कुंजी के कारण क्रमशः अंत और मोर्चे पर तत्वों को जोड़ने और तैयार करने के बहुत आम मामलों को रोकता है। यह उन मामलों के लिए ओ (लॉग एन) को बनाए रखता है (हालांकि उसी स्थान पर डालने से आंतरिक रूप से पी प्रविष्टियों के बाद ओ (पी) कुंजी उत्पन्न हो सकती है)। मैं आपको यह काम करने दूँगा। के = 256 के साथ, आप अनिश्चित लंबाई बाइट तारों का उपयोग कर सकते हैं। एसक्यूएल में, मुझे विश्वास है कि आप varbinary(max) चाहते हैं। एसक्यूएल सही लेक्सिकोग्राफिक सॉर्ट ऑर्डर प्रदान करता है। यदि आपके पास जावा के समान BigInteger पैकेज है तो इंटरपोलेशन ऑप्स का कार्यान्वयन आसान है। यदि आपको मानव-पठनीय डेटा पसंद है, तो आप बाइट स्ट्रिंग को उदा। हेक्स स्ट्रिंग्स (0-9 ए-एफ) और उनको स्टोर करें। फिर सामान्य यूटीएफ 8 स्ट्रिंग सॉर्ट ऑर्डर सही है।