सहयोगी टेक्स्ट एडिटिंग: CRDT या OT के बिना इसे लागू करना

 (mattweidner.com)
4 पॉइंट द्वारा GN⁺ 2025-05-23 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • सहयोगी टेक्स्ट एडिटिंग की समस्या को हल करने के लिए एक नया दृष्टिकोण पेश किया गया है, जिसे जटिल एल्गोरिद्म के बिना भी लागू किया जा सकता है
  • यह मौजूदा CRDT और OT तरीकों की जटिलता और सीमाओं से बचते हुए, एक सरल ID-आधारित insert तरीका इस्तेमाल करता है
  • इस तरीके में सर्वर को सीधे यह निर्देश मिलता है कि क्या कहाँ insert करना है, इसलिए लचीलापन अधिक है
  • optimistic local updates के लिए server reconciliation strategy का उपयोग कर state synchronization की समस्या हल की जाती है
  • scalability और समझने में आसानी वाला यह तरीका, मौजूदा collaborative apps के विकास में सीधे लागू किए जा सकने वाला एक विकल्प प्रस्तुत करता है

Collaborative Text Editing without CRDTs or OT

समस्या का प्रस्तुतीकरण

  • टेक्स्ट collaborative editing एक बहुत कठिन फीचर है, खासकर simultaneous editing के दौरान text index के बिगड़ने की समस्या(index rebasing) पैदा होती है
  • मौजूदा तरीके CRDT(conflict-free replicated data type) और OT(operational transformation) दोनों जटिल गणितीय मॉडल पर आधारित हैं
    • CRDT: हर character को ID से track करना और tree-based sorting
    • OT: दूसरे उपयोगकर्ताओं के input को reflect करने के लिए index को dynamically readjust करना
  • दोनों तरीकों में library dependency अधिक होती है और developer-specific customization कठिन होती है

नया दृष्टिकोण

मुख्य विचार

  • हर character को एक unique ID(UUID) से चिह्नित किया जाता है, और client server को "किस ID के बाद कौन-सा character insert करना है" जैसा command भेजता है
  • उदाहरण: "insert ' the' after f1bdb70a" → f1bdb70a insert target character की ID है
  • server इसे जैसा है वैसा समझकर insert करता है, जिससे conflict से बचा जाता है

delete प्रोसेसिंग

  • character delete करने पर भी उसकी ID internal list में बनी रहती है और isDeleted flag से उसे संभाला जाता है
  • यह वास्तविक user text में दिखाई नहीं देती, लेकिन reference बना रहता है ताकि आगे के operations संभव हों

client processing और optimistic updates

  • user को input के तुरंत बाद परिणाम दिखना चाहिए, इसलिए server response से पहले local में reflect किया जाता है (optimistic update)
  • server reconciliation strategy का उपयोग करके:
    1. सभी local unconfirmed operations को rollback किया जाता है
    2. server operations लागू किए जाते हैं
    3. फिर local operations को दोबारा apply करके final synchronized state हासिल की जाती है

मौजूदा तरीकों से अंतर

  • CRDT में automatic ID sorting एल्गोरिद्म शामिल होता है, लेकिन इस तरीके में server को सिर्फ explicit insertion position भेजी जाती है
  • परिणामस्वरूप यह अधिक सरल है और स्पष्ट व्यवहार सुनिश्चित करता है

simultaneous insert को संभालना

  • उदाहरण: "My name is" में दो user एक ही समय पर एक ही स्थान पर " Charlie" और " Dave" insert करते हैं
    • server जिस क्रम में उन्हें प्राप्त करता है, उसके अनुसार परिणाम "My name is Dave Charlie" बनता है
  • इसे स्वाभाविक व्यवहार माना जाता है, और कुछ CRDT तरीकों की तरह character-level interleaving नहीं होता

लचीले operations का समर्थन

  • basic insert/delete के अलावा कई अन्य operations भी समर्थित किए जा सकते हैं:
    • insert-before
    • शर्त-आधारित insert (जैसे, "color" मौजूद होने पर ही "u" जोड़ना)
    • drag & drop के समय position readjustment आदि
  • यह लचीलापन पूर्वनिर्धारित गणितीय गुणों से बंधा नहीं है

rich text का समर्थन

  • range को ID-आधारित तरीके से परिभाषित कर formatting लागू की जा सकती है (जैसे, "ID X से ID Y तक bold")
  • ProseMirror जैसे editor के साथ integration करने पर सरल तरीके से conflict resolution संभव है
  • मूल संरचना को बनाए रखते हुए rich text features जोड़े जा सकते हैं

distributed version (Decentralized)

  • केंद्रीय server के बिना भी Lamport timestamp-आधारित operation ordering के जरिए यह वही तरीके से काम कर सकता है
  • इस स्थिति में RGA, Peritext, Fugue जैसे CRDTs के समान परिणाम दिखाई देते हैं
  • tree या गणितीय proof के बिना भी CRDT-स्तर की consistency हासिल की जा सकती है

सहायक लाइब्रेरी: Articulated

  • Array<{ id, isDeleted }> रूप को कुशलतापूर्वक संभालने के लिए एक लाइब्रेरी
  • UUID की जगह { bunchId, counter } संरचना का उपयोग कर memory optimization
  • B+Tree-आधारित संरचना से तेज़ ID lookup और insertion का समर्थन
  • persistent data structure होने के कारण server reconciliation के साथ इसकी अच्छी संगति है

निष्कर्ष

  • CRDT/OT की तुलना में यह तरीका समझने में आसान है और सीधे लागू किया जा सकता है
  • विभिन्न editing features, permissions, constraints, formatting आदि को स्वतंत्र रूप से लागू किया जा सकता है, इसलिए व्यावहारिक collaborative editor implementation के लिए यह अधिक अनुकूल है
  • Articulated लाइब्रेरी इस दृष्टिकोण को व्यावहारिक बनाने में मदद करने वाले tool के रूप में उपलब्ध है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-05-23
Hacker News राय

  • यह algorithm काफ़ी बढ़िया लगता है। इसमें हर character को एक globally unique ID (जैसे UUID) दी जाती है ताकि उसे कभी भी consistent तरीके से refer किया जा सके, client server को बताता है कि किसी खास ID के बाद character insert करना है, और server उस position पर insertion कर देता है। delete किए गए character स्क्रीन से छिपा दिए जाते हैं, लेकिन position reference के लिए अंदरूनी तौर पर बने रहते हैं। कल्पना की गई कि यह तरीका सिर्फ text editing ही नहीं बल्कि game world synchronization जैसे दूसरे क्षेत्रों में भी काम आ सकता है।

    • यह मूल रूप से एक simplified CRDT जैसा लगता है, और tie-breaking तथा central server का उपयोग Google Wave के दौर की संरचना जैसा है।
    • सवाल उठाया गया कि क्या यह बताया गया तरीका वास्तव में CRDT ही नहीं है।
    • प्रतिक्रिया आई कि इसमें वास्तव में बहुत नई बात नहीं है; distributed systems को serialize करने के लिए central process का उपयोग एक पारंपरिक तरीका है, और network partition (CAP आदि) या single point of failure जैसी समस्याएँ फिर भी बनी रहती हैं। साथ ही पूछा गया कि क्या लेख में performance पर कोई चर्चा है।
    • ctrl+a, ctrl+x, ctrl+v जैसे bulk select/copy/paste operations के लिए शुभकामनाएँ कहकर मज़ाक किया गया।

  • यह नज़रिया साझा किया गया कि CRDT से इसका अंतर इस बात में है कि central server ordering जैसी synchronization की भूमिका निभाता है, इसलिए actual data structure में पहले से तय order देना ज़रूरी नहीं होता। क्योंकि communication सिर्फ client और server के बीच है, server client की सारी local operations process करने के बाद remote updates भेज सकता है।

  • यह राय आई कि dict/map जैसे दूसरे data structures या arbitrary type arrays की चर्चा न होना हैरान करने वाला है। असल apps में pure text collaborative editing से ज़्यादा तरह-तरह के collaborative data structures की ज़रूरत होती है। data validation, partial loading, higher-level operations जैसे दिलचस्प उदाहरण हैं, लेकिन Yjs आदि में इनके न होने का कारण शायद CRDT खुद नहीं बल्कि यह है कि ये features मूल रूप से implement करना कठिन हैं।

    • कई data structures वाली बात से गहरी सहमति जताई गई। कहा गया कि “atomic” object array बनाते समय अगर object properties बदल नहीं सकतीं, तो string की जगह बस type बदलना काफ़ी है, और object के अंदर बदलाव tree traversal/storage की समस्या होने के कारण थोड़ा अधिक जटिल है। साथ ही उम्मीद जताई गई कि helper library के users अपनी खुद की 'semantic model' logic को hook की तरह जोड़ सकें ताकि गलत states (जैसे एक todo में isDone: true और state: inProgress दोनों होना) रोकी जा सकें। यह linked post में बताए गए rich text formatting जैसे संदर्भ से मिलता-जुलता है।

    • CRDT conflict होने पर merge के लिए consistently एक side चुनता है, लेकिन समस्या यह है कि इससे data loss या invalid data निकल सकता है। इसे ऐसे समझाया गया जैसे git merge conflict को हमेशा सिर्फ एक पक्ष चुनकर सुलझाना—अधिकांश मामलों में इससे गलत result या compile error आएगा। इशारा किया गया कि सिर्फ automated resolution से data की originality और semantics ठीक से सुरक्षित नहीं रह सकतीं, और शायद यही वजह है कि CRDT अभी तक व्यापक रूप से इस्तेमाल नहीं हो पाया।

  • इस approach पर लिखा गया लेख दिलचस्प लगा, और टिप्पणी करने वाले ने कहा कि वह भी पहले से यही तरीका इस्तेमाल करता रहा है; यह बात अजीब लगी कि academia में इसका लगभग कोई ज़िक्र नहीं मिलता। उसने यह भी कहा कि उसने इसे decentralized environment में CRDT के रूप में implement किया था ताकि mergeability, immutability, interchangeability जैसी properties बनी रहें।

    • पूछा गया कि अगर इसे CRDT के विकल्प के रूप में विकसित किया गया था, तो वास्तव में क्या फ़ायदा मिला।

  • लेख का संदेश इस तरह संक्षेप में समझने की कोशिश की गई कि क्या जटिल CRDT/OT वास्तव में सिर्फ तब ज़रूरी होते हैं जब central server न हो।

    • राय दी गई कि central server न होने पर भी, अगर distributed तरीके में operations के global order पर सहमति बनाकर उसे लागू करने का तरीका हो, तो CRDT/OT की complexity से बचा जा सकता है। linked लेख का परिचय दिया गया। हालाँकि यह भी CRDT का ही एक रूप है (एक generalized form), लेकिन undo/replay implement करना आसान नहीं है, और जब पारंपरिक CRDT/OT structures ज़्यादा जटिल लगें तब इसे विकल्प के रूप में सोचा जा सकता है।

    • यह भी कहा गया कि OT (Operational Transformation) को central server की ज़रूरत होती है।

  • कहा गया कि मूल रूप से यह भी CRDT ही है, बस दस्तावेज़ पर लागू होने वाले operations का order central server तय करता है। Google Docs और Zoho Writer भी OT + central server मॉडल इस्तेमाल करते हैं। माना गया कि प्रस्तावित तरीका CRDT-style का है, लेकिन central server आधारित service में यह वास्तव में अधिक practical हो सकता है।

  • यह राय दी गई कि Automerge जैसे CRDT से मुख्य अंतर server arbitration में है। Automerge concurrent inserts को sequence number और agent ID के predefined order से sort करता है, जबकि यह तरीका server पर जिस क्रम में चीज़ें पहुँचती हैं उसी क्रम में process करता है। संदर्भित लेख की पंक्ति उद्धृत की गई: “किसी fancy algorithm की ज़रूरत नहीं, इसलिए यह सरल है।” कई services वैसे भी central server इस्तेमाल करेंगी, इसलिए यह तरीका practical लगता है, लेकिन server arbitration के दौरान local edits के undo/redo की ज़रूरत पड़ती है, इसलिए वास्तव में यह कितना ज़्यादा simple है, इस पर पूरा भरोसा नहीं।

    • “rewind/replay” को भी एक fancy approach बताया गया, और कहा गया कि Persistent B+Tree भी इतना simple नहीं है।

    • समझाया गया कि Automerge भी अंततः internal रूप से total order बना सकता है, लेकिन व्यवहार में वह text operations के लिए पारंपरिक CRDT (जैसे RGA) तरीका इस्तेमाल करता है, क्योंकि undo/replay आसान नहीं है।

  • यह एक unoptimized CRDT जैसा लगा; मज़ाक में कहा गया कि क्या यह बस max set size=1 करके इस्तेमाल करने जैसा नहीं है।

    • जवाब में कहा गया कि उल्टा, complexity को इस तरह घटाना अच्छा लगता है क्योंकि यह वास्तव में होने वाले operations के काफ़ी करीब है; optimized न होने पर भी इसमें आकर्षण है।

  • अगर server reconciliation का उपयोग किया जाए, तो client side पर merge की समस्या और कठिन हो सकती है। सवाल पूछा गया कि जब server updates क्रम से आते रहें तो editor UX को smooth कैसे रखा जाएगा। उदाहरण के लिए, अगर insertion request fail हो जाए तो क्या retry होगा, और तब तक दूसरे updates आ जाएँ तो क्या किया जाएगा। एक सुझाया गया तरीका था edit history को rewind करके फिर से apply करना, या wait करके queue flush करना। frontend नज़रिए से बहुत से UI/UX edge cases ऐसे लगते हैं जिनका स्पष्ट ज़िक्र नहीं है, और शायद इसी वजह से CRDT उल्टा ज़्यादा simple हो सकता है। खासकर unstable network connection (जैसे metro में) के दौरान user experience कैसा होगा, यह जानने की उत्सुकता जताई गई।

    • समझाया गया कि ProseMirror और नया CodeMirror document changes को step units में manage करते हैं और हर step पर position map update करके buffer के steps को document पर apply करने लायक data structures बनाते हैं। ज़ोर दिया गया कि यह collaborative editing में व्यावहारिक रूप से अच्छी तरह काम करता है, और संदर्भ सामग्री का लिंक साझा किया गया।

  • सुझाव दिया गया कि कोई LLM (जैसे 4b model आदि) का उपयोग करके, जटिल CRDT या OT के बिना भी, simple cases से आगे के merge conflicts को सुलझाने की कोशिश करे तो कैसा रहेगा। energy efficiency कम हो सकती है, लेकिन संभव है कि यह उम्मीद से बेहतर काम करे।

    • उदाहरण के तौर पर, My name is में is के बाद Charlie और Dave को अलग-अलग insert करने वाले conflict को LLM कैसे merge करेगा, इस पर सवाल उठाया गया।