cola: रियल-टाइम collaborative editing के लिए टेक्स्ट CRDT तकनीक

 (nomad.foo)
1 पॉइंट द्वारा GN⁺ 2023-09-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • cola Rust में लिखा गया रियल-टाइम collaborative editing के लिए एक टेक्स्ट CRDT है, जिसका फोकस बिना किसी केंद्रीय coordinator के कई peers द्वारा एक साथ संशोधित दस्तावेज़ को उसी state में converge कराना है
  • दस्तावेज़ की position को साधारण offset की जगह ReplicaId.n रूप के Anchor से फिक्स किया जाता है, ताकि simultaneous editing के दौरान position का अर्थ बदलने की समस्या से बचा जा सके
  • insert conflict को Lamport timestamp और ReplicaId ordering से लगातार एक ही तरह resolve किया जाता है, और delete में वास्तविक removal की जगह tombstone और version vector से merge की शर्तों को मैनेज किया जाता है
  • implementation के स्तर पर EditRun आधारित RLE और Vec index से व्यक्त G-tree का उपयोग किया गया है, ताकि Rust के सुरक्षित ownership model के भीतर log-time search और insertion हासिल किए जा सकें
  • benchmark में cola की तुलना diamond-types, automerge, yrs से की गई, और upstream में यह diamond-types से 1.4~2 गुना तेज़ रहा जबकि downstream में भी बहुत तेज़ performance दिखी

cola जिन collaborative editing समस्याओं को संभालता है

  • cola Rust में लिखा गया एक text CRDT है, जिसे रियल-टाइम collaborative editing में बिना केंद्रीय authority के कई replicas को एक ही state में converge कराने के लिए डिज़ाइन किया गया है
  • network layer के बारे में सिर्फ इतना न्यूनतम assumption रखा गया है कि हर edit अंततः हर peer तक पहुँच जाएगा
    • edit कई बार transmit हो सकते हैं
    • edit किसी भी क्रम में पहुँच सकते हैं
    • हर peer को अंततः सभी edit मिलने चाहिए
  • लक्ष्य सिर्फ सभी edit मिलने के बाद दस्तावेज़ की state को समान बनाना नहीं है, बल्कि user के नज़रिए से परिणामस्वरूप दस्तावेज़ का रूप भी समझ में आने योग्य होना चाहिए

offset की जगह Anchor से position को फिक्स करना

  • insert "abc" at offset 8 जैसे offset-based edit में अगर कोई दूसरा peer आगे के हिस्से को एक साथ modify कर दे, तो उसका अर्थ बदल सकता है और replicas अलग हो सकते हैं
  • cola दस्तावेज़ की position को character content या offset से नहीं, बल्कि stable identifier से refer करता है
    • हर peer insert किए गए characters को बढ़ते हुए number देता है
    • peer के पास एक unique identifier होता है, ReplicaId
    • ReplicaId.n जोड़ी character की unique position identifier, Anchor, बनती है
  • n value को local counter बढ़ाकर unique रखा जा सकता है, लेकिन बिना केंद्रीय server के ReplicaId की global uniqueness सुनिश्चित करना कठिन है
    • cola यह मानकर चलता है कि UUID की तरह बहुत बड़े random integer का उपयोग किया जाएगा, जिनमें collision की संभावना नगण्य हो
  • insert में एक Anchor से position बताई जाती है, और delete में start और end, दो Anchor के जरिए range बताई जाती है

insert conflict को एक ही क्रम में sort करना

  • जब एक ही Anchor पर कई insert आते हैं, तो cola Lamport timestamp से उनका क्रम तय करता है
  • Lamport clock को इन नियमों से update किया जाता है
    • local में text insert करते समय clock को 1 बढ़ाया जाता है
    • remote insert मिलने पर इसे max(current, remote_timestamp) + 1 पर सेट किया जाता है
  • अगर कोई insert A, insert B को पहले से merge कर चुके environment में बनाया गया था, तो A का Lamport timestamp, B से बड़ा होगा
  • conflicting insert को Lamport timestamp के descending order में sort किया जाता है
  • अगर simultaneous insert में Anchor और Lamport timestamp दोनों समान हों, तो user के नज़रिए से कोई अधिक सही order नहीं होता, इसलिए peers के बीच consistency बनाए रखने के लिए ReplicaId के ascending order का उपयोग किया जाता है

delete को tombstone और version vector से संभालना

  • delete में start/end offset को Anchor में बदलकर दूसरे peers तक propagate किया जाता है
  • अगर दो peer एक ही area को एक साथ delete करें, तो undo को न मानें तो परिणाम एक बार delete करने जैसा ही होता है
    • cola अभी delete undo को support नहीं करता
  • delete handling में तीन कठिनाइयाँ हैं
    • अगर deleted text को पूरी तरह हटा दिया जाए, तो अभी तक नहीं पहुँचे edits के Anchor उस area के भीतर हो सकते हैं
    • अगर remote delete को बहुत जल्दी merge कर दिया जाए, तो delete बनाने वाले peer ने जो content देखा था और receiving peer का content अलग हो सकता है, जिससे replicas diverge हो सकते हैं
    • delete range के भीतर वे characters delete नहीं किए जाने चाहिए जिन्हें delete बनाने वाले peer ने अभी तक देखा ही नहीं था
  • पहली समस्या tombstone से हल होती है
    • deleted characters दस्तावेज़ में बने रहते हैं, लेकिन deleted के रूप में mark कर दिए जाते हैं
    • इससे memory usage बढ़ता है
  • बाकी समस्याएँ delete message में version vector शामिल करके हल की जाती हैं
    • key है ReplicaId, और value वह latest character timestamp है जिसे delete बनाने वाले peer ने उस समय देखा था
    • receiving peer तब तक delete merge होने का इंतज़ार करता है जब तक उसका version vector, delete message के version vector से कम न रहे
    • delete version vector के timestamp से बड़े characters को deletion target से skip किया जाता है
  • cola में version vector को version map कहा जाता है

Replica और text buffer का अलगाव

  • हर peer की local document state को cola में Replica से व्यक्त किया जाता है
  • cola के CRDT algorithm को वास्तविक string content जानने की ज़रूरत नहीं होती
    • API functions string को argument के रूप में नहीं लेते
    • cola दस्तावेज़ की content नहीं, बल्कि सिर्फ numeric blocks को संभालता है
  • यह design CRDT mechanism और वास्तविक text buffer implementation को अलग करता है

RLE और EditRun से metadata कम करना

  • अगर हर character के साथ metadata जोड़ दिया जाए, तो high-performance implementation बनाना कठिन हो जाता है, इसलिए cola लगातार timestamp वाले blocks को run-length encoding से group करता है
  • उदाहरण के लिए Wikipedia के Manhattan Project पेज को पूरा paste करने पर 107,000 blocks की जगह उसे एक block के रूप में व्यक्त किया जा सकता है
  • cursor को move या delete किए बिना अगर sentence को एक-एक character टाइप किया जाए, तब भी हर key input पर block बनाने के बजाय उसे एक run के रूप में व्यक्त किया जा सकता है
  • cola में ऐसे continuous blocks को EditRun कहा जाता है
    • एक बार टूट जाने के बाद EditRun दस्तावेज़ के जीवनकाल भर fixed रहता है और फिर expand नहीं होता
    • जो run अभी तक नहीं टूटा है, वह active state में होता है
  • अगर किसी मौजूदा EditRun के बीच में text insert किया जाए, तो run को दो हिस्सों में बाँटकर बीच में नया text रखा जाता है
  • text delete करने पर संबंधित हिस्से को run से अलग करके tombstone mark कर दिया जाता है
    • deleted run को भी उसी तरीके से RLE किया जा सकता है, जिससे tombstone का memory overhead कम होता है

linked list से B-tree तक

  • local edit की upstream path वह प्रक्रिया है जिसमें offset-based edit को ऐसे edit में बदला जाता है जिसे दूसरे peers को भेजा जा सके
    • insert और delete दोनों में उस run को खोजना होता है जिसमें offset शामिल है, ताकि Anchor बनाया जा सके
    • ज़रूरत पड़ने पर run को insert में अधिकतम 2 और delete में अधिकतम 3 हिस्सों में बाँटा जाता है
  • linked list में run split करना O(1) है, लेकिन offset वाला run खोजने के लिए शुरुआत से scan करना पड़ता है, इसलिए linear time लगता है
  • अगर current active run और उसके offset को cache किया जाए, तो उसी position पर बार-बार edit करते समय यह तेज़ हो सकता है, लेकिन worst case फिर भी linear ही रहता है
  • cola worst-case में log-time performance के लिए B-tree structure पर विचार करता है
    • run को B-tree के leaf के रूप में दर्शाया जाता है
    • inode अपने children और उनके combined length को store करता है
    • tombstone run length में 0 का योगदान देते हैं
    • root की length पूरे document length के बराबर होती है
  • B-tree search और insertion को O(log n) में कर सकता है, इसलिए local edits को log-time में process किया जा सकता है
  • लेकिन remote edit में Anchor -> run conversion को efficient बनाने के लिए, उस leaf को खोजना ज़रूरी है जिसमें Anchor मौजूद है

G-tree: Vec index से व्यक्त B-tree

  • सामान्य B-tree leaf के pointer भर से यह जानना कठिन होता है कि top-down insertion process में leaf तक कैसे पहुँचना है
  • bottom-up operations के लिए हर node का parent pointer चाहिए होता है, और Rust के safe ownership model में इसके लिए Rc<RefCell<_>> जैसी structure की ज़रूरत पड़ सकती है, जो धीमी और जटिल हो सकती है
  • cola सभी nodes को Vec जैसी dynamic array में store करता है, और nodes के बीच references को pointer की जगह index से व्यक्त करता है
    • vector सभी nodes का owner होता है
    • हर node parent index store कर सकता है
    • unsafe code के बिना bidirectional traversal संभव हो जाता है
  • यह structure इस assumption पर निर्भर करती है कि node index नहीं बदलेंगे
    • नए nodes vector के end में append होते हैं
    • cola run को remove नहीं करता, बल्कि tombstone mark करता है, इसलिए index invalidation की समस्या नहीं आती
  • ऐसे grow-only tree-in-a-vector structure को cola में G-tree कहा जाता है
  • G-tree Rust code B-tree की parent-child structure को बनाए रखते हुए सिर्फ memory representation बदलता है

G-tree से बनने वाली performance characteristics

  • G-tree, B-tree की तरह, top-down search और insertion को log-time में करता है
  • leaf के vector index LeafIdx को stable leaf identifier के रूप में इस्तेमाल किया जा सकता है
  • current active run को pointer की जगह LeafIdx से cache किया जा सकता है
    • अगर उसी cursor position पर बार-बार edit हो, तो active run को expand किया जा सकता है और सिर्फ ancestors की length को root तक update करना पड़ता है
    • इसे tree traversal और नई allocation के बिना कुछ integer comparison और 2~4 integer addition से संभाला जा सकता है
  • cola का G-tree branching factor 32 का उपयोग करता है, और inode की average occupancy लगभग 20 children होती है
    • सिर्फ 4 levels में आम तौर पर लगभग 160k अलग-अलग EditRun store किए जा सकते हैं
    • automerge-paper edit trace process करने के बाद cola के G-tree में लगभग 15k EditRun होते हैं
    • उस trace में 260k edits शामिल हैं और यह कई दिनों में रिकॉर्ड किया गया था
  • G-tree में nodes पहले से linear memory में store होते हैं, इसलिए serialization और deserialization भी सरल हो जाते हैं

Anchor को LeafIdx में बदलना

  • remote edit की downstream path वह प्रक्रिया है जिसमें insert 2.3..7 at 1.2, delete between 3.4 and 2.2 जैसे Anchor-based edit को local document offset edit में बदला जाता है
  • G-tree में ऊपर और नीचे दोनों दिशाओं में traversal संभव है, इसलिए अगर उस run का LeafIdx पता हो जिसमें कोई Anchor मौजूद है, तो संबंधित offset निकाला जा सकता है
  • मुख्य बिंदु है Anchor -> LeafIdx conversion
  • एक simple design यह है कि एक auxiliary G-tree या B-tree रखा जाए, जिसमें leaf में ReplicaId, temporal range, और main G-tree का LeafIdx store हो
    • leaf पूरी तरह ReplicaId और temporal range order में sort रहते हैं
    • Anchor के आधार पर tree में नीचे उतरकर इच्छित LeafIdx पाया जा सकता है
    • search और insertion दोनों O(log n) हैं
  • असली cola source code इस auxiliary G-tree approach को ज्यों का त्यों इस्तेमाल नहीं करता
    • वास्तविक implementation में search और insertion O(log f) हैं
    • f उस fragment count को दर्शाता है जिनमें Anchor वाला EditRun समय के साथ विभाजित हुआ है
    • f हमेशा n से कम या बराबर होता है और आम तौर पर उससे बहुत छोटा होता है

वर्तमान परिपक्वता और बाकी काम

  • cola का design convergence, intention preservation और performance को लक्ष्य बनाकर एक मजबूत आधार देता है
  • production-ready होने के लिए undo/redo support और कुछ अतिरिक्त काम अभी बाकी हैं

Rust CRDT benchmark

  • cola की तुलना 3 Rust-आधारित CRDT से की गई
  • benchmark वास्तविक character-by-character edit trace को process करने में लगने वाले समय को मापता है
    • Rust benchmarking library criterion का उपयोग किया गया
    • upstream और downstream दोनों दिशाओं को मापा गया
    • benchmark code crdt-benches में है
  • graph में cola performance के 100x को baseline रखा गया है, और cola से 100x से अधिक धीमे measurements को नहीं दिखाया गया
  • execution environment 2018 MacBook Pro, 2.2GHz 6-Core Intel Core i7 था
    • दूसरी machine पर numbers बदल सकते हैं, लेकिन relative performance लगभग समान रहने की उम्मीद है

benchmark परिणाम

  • upstream direction में yrs और automerge baseline से ऊपर चले जाते हैं
  • upstream में cola, diamond-types से 1.4~2 गुना तेज़ है
  • downstream direction में diamond-types हर trace पर crash हो गया, इसलिए measurement नहीं मिल सका
    • यह भी जोड़ा गया है कि अगर library का उपयोग गलत किया गया हो तो result update किए जाएँगे
  • downstream में cola पहले की तुलना में लगभग 2 गुना धीमा है
    • क्योंकि remote edit merge करना आम तौर पर local edit generate करने से अधिक महँगा होता है, इसलिए यह अपेक्षित परिणाम है
  • cola दोनों दिशाओं में तेज़ rope libraries के बराबर या उनसे भी बेहतर स्तर पर काम करता है, और इसे वर्तमान में सबसे तेज़ text CRDT implementation माना जाता है

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

1 टिप्पणियां

 
GN⁺ 2023-09-04
Hacker News पर राय

  • मुझे G-tree अब भी parent pointer जोड़े गए B-tree जैसा ही लगता है
    array में store होना सिर्फ representation का मामला है, इससे structure बुनियादी तौर पर नहीं बदलता
    यह अब भी pointers store करता है, बस byte के हिसाब से नहीं बल्कि node size के हिसाब से, और address space की शुरुआत के बजाय पहले array element के सापेक्ष relative position होती है
    उदाहरण के लिए, बिना explicit references के array में store किया गया complete binary tree भी, जहाँ index x के बच्चे 2x + 1 और 2x + 2 पर होते हैं, सिर्फ एक implicit representation है; फिर भी हम उसे binary tree ही कहते हैं

    • फिर भी representation पर बात करना उपयोगी है
      खासकर उन languages में जो absolute references के बजाय relative और self-managed references की ओर प्रेरित करती हैं
      मैंने जिन tree representations को रोचक पाया, उनमें से एक nodes को depth-first traversal order में flat array में store करना है
      अगर यह read-only हो और reader वैसे भी depth-first तरीके से traverse करने वाला हो, तो यह काफी efficient हो सकता है
      S-expression और HTML याद आते हैं

  • अगर मैंने API में कुछ मिस नहीं किया है, तो यह bold/italic जैसी formatting ranges को support नहीं करता लगता
    मेरी जानकारी में rich text CRDT algorithms में अभी Peritext state-of-the-art है https://www.inkandswitch.com/peritext/
    अच्छा होगा अगर यह project Peritext algorithm की rich text capabilities भी अपना ले

    • CRDT क्षेत्र में थोड़ी दिलचस्पी रखने वाले के तौर पर, मैं हमेशा सोचता रहा हूँ कि क्या ज्यादा generic structured data CRDT बनाया जा सकता है
      यानी ऐसा तरीका जिसमें user कोई model या schema define करे जो semantically valid states को describe करे
      उदाहरण के लिए JSON को यूँ ही merge करने पर syntax के हिसाब से valid, लेकिन semantics के हिसाब से बेकार state बन सकती है
      जैसे Peritext algorithm जानता है कि bold/italic/underline additive operations हैं और highlight color वैसा नहीं है, वैसे ही अच्छा होगा अगर user schema में declare कर सके कि state: notStarted और completionDate: 2023-09-04 साथ-साथ valid नहीं हैं
    • सवाल: article में कहा गया है कि Cola unknown data types के लिए conflict-free editing ही handle करता है, और असल में character stream और positions ही handle करता है
      तो क्या HTML की तरह formatting को text के अंदर ही represent नहीं किया जा सकता?
      मैं दूसरे rich text representations को अच्छी तरह नहीं जानता, इसलिए पक्का नहीं कह सकता
      साथ ही, ऊपर linked Peritext document देखा तो वह ठीक इसी RTF-specific मुश्किल को address कर रहा था, और पढ़ने में काफी दिलचस्प लगा

  • Automerge या Y.js/Yrs की तुलना में performance या features में क्या फर्क है?

    • article का “third part” इस तरह शुरू होता है कि “Rust में implement किए गए तीन अन्य CRDTs, diamond-types, automerge, yrs और cola को benchmark किया”
      यह cola library operation speed के मामले में काफी फायदे में दिखती है
      memory usage भी जानना चाहूँगा

  • Ian Piumarta के इसी नाम वाले काम से इसे confuse नहीं करना चाहिए
    https://www.piumarta.com/software/cola/
    https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

    • या Cache Oblivious Lookahead Arrays भी हैं, जिन्हें कभी MergeTree(LSM) का alternative माना जाता था, लेकिन अब इस्तेमाल में नहीं हैं https://github.com/giannitedesco/cola
    • coda.io नाम का Notion clone-style app भी है

  • काम अच्छा है, लेकिन यह fair benchmark जैसा नहीं दिखता
    यह operations को compute करके store भी नहीं करता और actual text भी store नहीं करता
    इस पर delta updates support करने वाला text CRDT बनाना हो तो user को अलग structure में OpID => Text store करना पड़ेगा, और यह cost सस्ती नहीं है

  • slotmap crate(https://docs.rs/slotmap/latest/slotmap/) इस्तेमाल करने पर index move होने या “index” के किसी और value की ओर point करने की चिंता किए बिना deletion support किया जा सकता है
    slotmap में इसे key कहते हैं, और key में version number भी शामिल होता है

    • क्या यह CRDT context में भी काम करेगा?
      order तय करना मुश्किल है और version सिर्फ local तौर पर meaningful हो सकता है, इसलिए जिज्ञासा है

  • जिस project को Etherpad और Word संभाल नहीं पाए थे, उसमें इसे एक बार आज़माने की सोच रहा हूँ

  • अगर मान लें कि सभी connected clients को सभी edits मिलते हैं, तो offset और insert/delete/replace commands से पहले existing text state का expected hash क्यों न रख दिया जाए?
    इससे लगभग guarantee मिल सकती है कि edit सिर्फ सही state पर ही apply होगा, और बाद के changes को “जिस data state पर apply होने की उम्मीद है उसके hash” को key बनाकर dictionary में जमा किया जा सकता है
    बेशक, same data पर hash operations बार-बार compute करने पड़ेंगे, इसलिए cost बड़ी होगी, लेकिन समझना और implement करना बहुत simple है

    • उस तरीके में asynchronous edits कभी apply नहीं होंगे
      अगर मैं document में local edit करूँ और आप remote edit करें, तो आपका “expected state” hash आगे भी मेरे document state से कभी match नहीं करेगा
      क्योंकि मैं पहले ही local change कर चुका हूँ
      CRDT को convergence guarantee करने के लिए सभी clients को सभी edits मिलना जरूरी है, यह सही है, लेकिन updates को किसी खास order में apply करने की जरूरत न होना real-world distributed use cases में एक important property है

  • जानना चाहता हूँ कि browser में form co-editing आसानी से enable करने का कोई तरीका है या नहीं
    अच्छा होगा कि अगर दो लोग same page या form खोलें, तो दिखे कि दूसरा अभी कौन-सा input field edit कर रहा है, और text input fields में text CRDT इस्तेमाल हो
    Yjs से कुछ ऐसा implement करने की कोशिश की थी, लेकिन यह काफी मुश्किल था और ठीक से काम नहीं किया

    • जिज्ञासा है कि Yjs कहाँ fit नहीं हुआ
      उस use case के लिए तो यह बिल्कुल सही लगता है