स्थानांतरित किए जा सकने वाले tree CRDT और Loro का इम्प्लीमेंटेशन

• Movable tree CRDTs and Loro's implementation

• पृष्ठभूमि

  • distributed systems और collaborative software में hierarchical relationships को मैनेज करना जटिल है
  • data structures में delete और insert को जोड़कर move को मॉडल करने पर conflict resolution और user expectations को पूरा करना कठिन होता है
  • उदाहरण के लिए, एक ही node को अलग-अलग parents के पास एक साथ move करने पर एक ही content वाले duplicate nodes बन सकते हैं

• स्थानांतरित किए जा सकने वाले tree में conflicts

  • movable tree की मुख्य operations: create, delete, move
  • concurrent operations को sync करते समय होने वाले संभावित conflicts:
    • एक ही node delete भी हो और move भी हो
    • एक ही node अलग node के नीचे move हो
    • दूसरे nodes move होकर cycle बना दें
    • ancestor node delete हो रहा हो जबकि descendant node move हो रहा हो

• एक ही node का delete और move

  • तुलनात्मक रूप से हल करना आसान है
  • distributed system के timestamp या application की specific requirements के अनुसार एक operation लागू किया जाता है और दूसरे को ignore किया जाता है

• एक ही node को अलग parent के नीचे move करना

  • concurrent move operations को merge करना अधिक जटिल है
  • application के अनुसार अलग-अलग approaches अपनाई जा सकती हैं:
    • node को delete करके दूसरे parent node के नीचे उसकी copy बनाना
    • node को दो parents से linked रहने देना (आमतौर पर अनुमति नहीं होती)
    • सभी operations को sort करके sequentially apply करना

• अलग nodes की movement से cycle बनना

  • concurrent move operations से बनी cycle को resolve करना जटिल है
  • कई समाधान मौजूद हैं:
    • error उत्पन्न करना
    • cyclic node को विशेष "timeout" area में render करना
    • server पर move operations को process करना
    • topological sort का उपयोग करना
    • cycle पैदा करने वाले edge को hide करना

• ancestor node का delete और descendant node का move

  • ancestor node delete होने पर descendant node का move आसानी से नजरअंदाज हो सकता है
  • सभी descendant nodes को सीधे delete कर देने से data loss जैसा लग सकता है

• लोकप्रिय applications में conflict handling के तरीके

  • Dropbox: file move को delete के बाद create की तरह handle किया, लेकिन data loss का जोखिम था
  • Figma: central server cycle detect करके operation को reject करता है, जिससे consistency बनी रहती है

• movable tree CRDTs

  • centralized solution की जगह CRDTs का उपयोग
  • शुरुआती CRDT-आधारित algorithms को implement करना कठिन था और storage overhead बड़ा था
  • लगातार optimization के कारण कुछ CRDT-आधारित tree sync algorithms production environment के लिए उपयुक्त बन गए

• replicated tree के लिए high-availability move operations

  • tree की तीन operations (create, delete, move) को move operation में एकीकृत किया जाता है
  • move operation को Move t p m c के रूप में परिभाषित किया जाता है
  • node deletion को TRASH node में move करके handle किया जाता है

• globally sorted logical timestamps

  • Lamport timestamps का उपयोग करके distributed systems में events के causal order का निर्धारण किया जाता है
  • छोटा अंक पहले event को दर्शाता है

• remote operations लागू करना

  • operation की safety इस पर निर्भर करती है कि apply करते समय tree की state क्या है
  • remote updates को handle करते समय हाल की operations को rollback करके नई operation insert की जाती है, फिर rollback की गई operations को दोबारा apply किया जाता है

• CRDT: mutable tree hierarchy

  • हर node सभी historical parent nodes को track करता है और उन्हें counter देता है
  • sync के दौरान cycle बनने पर उसे सबसे नजदीकी historical parent node से फिर जोड़ा जाता है

• Loro में movable tree CRDTs का इम्प्लीमेंटेशन

  • Martin Kleppmann के algorithm को implement करके उच्च performance प्रदान की गई है
  • child nodes को sort करने के लिए Fractional Index algorithm को integrate किया गया है

• child node sorting में संभावित conflicts

  • एक ही position पर कई nodes insert करने पर एक जैसा Fractional Index assign हो सकता है
  • समान Fractional Index वाले nodes की relative order तय करने के लिए PeerID का उपयोग किया जाता है

• इम्प्लीमेंटेशन और encoding size

  • Fractional Index node order प्रदान करता है
  • worst case में encoding size के लिए अतिरिक्त bytes की जरूरत पड़ सकती है, लेकिन यह दुर्लभ स्थिति है

• संबंधित कार्य

  • Fractional Index के अलावा movable list CRDT भी मौजूद हैं
  • Fractional Index का implementation सरल है और जब केवल relative order की जरूरत हो तब यह उपयोगी है

• benchmarks

  • Loro के movable tree implementation की performance benchmarking की गई
  • real-time collaboration और seamless historical version checkout को support किया जा सकता है

• सारांश

  • movable tree CRDTs के implementation की कठिनाइयों और दो innovative algorithms का परिचय
  • Loro, Martin Kleppmann के algorithm और Fractional Index को integrate करके विभिन्न application scenarios को पूरा करता है

• GN⁺ की संक्षिप्त प्रस्तुति

  • movable tree CRDTs distributed systems में hierarchical data structures को मैनेज करने में महत्वपूर्ण भूमिका निभाते हैं
  • Loro उच्च performance और efficient conflict resolution प्रदान करता है, इसलिए यह real-time collaboration applications के लिए उपयुक्त है
  • Fractional Index का उपयोग child node ordering की समस्या को हल करता है
  • समान सुविधाओं वाले अन्य projects में Figma और Dropbox शामिल हैं

[GN⁺]

Hacker News की राय

• एक नया multiplayer editor विकसित कर रहा/रही हूँ

  • text और outliner काम को support करता है
  • document को एक बड़े tree structure में बदला जाता है
  • sync के लिए insmov (move या insert) operation का उपयोग करता है
  • जब server बदलाव भेजता है, तो client उन्हें फिर से apply करता है
  • ज़्यादातर मामलों में operations को undo करने की ज़रूरत नहीं होती
  • real-time updates के दौरान लगभग कोई समस्या नहीं होती

• React Table Library को open source के रूप में उपलब्ध कराया है

  • folder/file tree structure को handle करता है
  • folder/file move, copy, lazy loading आदि को support करता है
  • इससे समझ आया कि Google Drive केवल उसी hierarchy level पर display और edit क्यों करता है

• सलाह माँग रहा/रही हूँ

  • frontend में एक बड़ा denormalized tree इस्तेमाल कर रहा/रही हूँ
  • user profiles को tile layout में manage करता/करती हूँ
  • safe updates के लिए केवल न्यूनतम data भेजता/भेजती हूँ
  • लगता है कि CRDT इस्तेमाल करने से state management बहुत आसान हो जाएगा
  • browser tabs के बीच sync संभव हो जाएगा

• Google Docs/Zoho Writer जैसे formatted text content के साथ काम करते समय tree manipulation की ज़रूरत होती है

  • concurrent conflicts की समस्या सुलझाना मुश्किल है
  • लगता है list CRDT और tree CRDT को जोड़ा जा सकता है
  • हर operation में 2-dimensional address जोड़ना पड़ेगा

• सोच रहा/रही हूँ कि image (pixel) और 3D model जैसे data-dense applications के लिए कोई practical CRDT है या नहीं

• लगता है कि पहला paragraph ChatGPT की आवाज़ जैसा है