- collaborative software में hierarchical structure को साथ-साथ edit करने पर duplicate nodes, cycles, और deleted ancestor के child node को move करने जैसे tree conflicts पैदा होते हैं, और Loro इसे movable tree CRDT के रूप में implement करता है
- Martin Kleppmann वगैरह का तरीका create, delete, move को
Move t p m c में unify करता है, और delete को TRASH node में move करने के रूप में handle करके concurrent child node move को preserve करता है
- global order Lamport Timestamp और Peer ID से बनता है, और remote operation अगर मौजूदा order के बीच में आ जाए तो cycle से बचने के लिए undo-do-redo किया जाता है
- Loro sibling nodes को sort करने के लिए Fractional Index को combine करता है, और same position पर concurrent insert से indices overlap हों तो PeerID, jitter, और index reset से handle करता है
- benchmark में Loro Movable Tree ने 1000 nodes create करने के बाद 10000 random moves 28ms में किए, जिससे real-time collaboration और पुराने version checkout के लिए पर्याप्त performance दिखी
collaborative tree में होने वाले conflicts
- distributed systems और collaborative software में hierarchical relations manage करते समय अगर move को delete और insert के combination के रूप में model किया जाए, तो user expectations और conflict resolution method के बीच mismatch होना आसान है
- अगर same node अलग-अलग replicas में simultaneously अलग-अलग parents में move हो, तो एक node दो बार delete होकर दो parents के नीचे फिर से create हो सकता है, जिससे same content वाले duplicate nodes बन सकते हैं
- movable tree के basic operations तीन हैं: create, delete, move
- synchronization के समय मुख्य रूप से problem बनने वाली स्थितियां ये हैं
- same node delete होने के साथ-साथ move भी होता है
- same node अलग-अलग parents के नीचे move होता है
- अलग-अलग node moves merge होकर cycle बनाते हैं
- ancestor node delete होते समय child node move होता है
conflict type के हिसाब से handling
- same node के delete और move में conflict हो तो distributed system के timestamp या application requirements के आधार पर एक operation apply करके दूसरे को ignore किया जा सकता है
- same node अलग-अलग parents के नीचे move होने पर options application के हिसाब से बदलते हैं
- node को delete करने के बाद अलग-अलग parents के नीचे copies बनाई जाएं और उसके बाद उन्हें independently treat किया जाए
- एक node को दो parents की ओर point करने दिया जा सकता है, लेकिन इससे tree structure टूट जाता है, इसलिए आम तौर पर इसे accept करना मुश्किल है
- सभी operations को sort करके order में apply किया जाए तो सभी peers पर same result बनाया जा सकता है
- अगर अलग-अलग node moves cycle बनाते हैं, तो movable tree का conflict resolution खास तौर पर complex हो जाता है
- Matthew Weidner ने error handling, “time-out” area rendering, server-based rejection, topological sort के बाद cycle बनाने वाले operation को skip करना, rendering के समय किसी खास edge को hide करना, previous parent पर revert करना आदि को summarize किया है
- ancestor node delete होने के दौरान child node move होने वाली स्थिति भी आसानी से miss हो सकती है
- अगर ancestor के सभी child nodes तुरंत delete कर दिए जाएं, तो user गलतफहमी में पड़ सकता है कि उसका data loss हो गया है
Dropbox और Figma का approach
- Dropbox ने शुरुआत में file move को original location delete करने और फिर new location create करने के दो steps में handle किया था
- delete और create के बीच power outage या system crash हो जाए तो data loss का risk था
- अब जब कई लोग same file को simultaneously move और save करने की कोशिश करते हैं, तो यह conflict detect करता है, और आम तौर पर original file का एक version save करने के बाद किसी एक user के change के लिए “conflicted copy” बनाता है
- Figma tree structure को collaborative system का सबसे complex हिस्सा मानता है और हर element में
parent property रखता है
- central server कई user updates को monitor करता है, और अगर कोई operation cycle बना सकता है तो उस operation को reject कर देता है
- network delay की वजह से server के reject करने से पहले temporarily cycle बन सकता है
- ऐसी स्थिति में Figma cycle में शामिल elements को temporarily hide करता है, और server के officially operation reject करने तक state को preserve करता है
- संबंधित explanation Figma के multiplayer technology article में देखी जा सकती है
movable tree CRDT के दो approaches
- centralized solution के बजाय CRDT से collaborative tree structure handle किया जा सकता है
- शुरुआती CRDT-based tree algorithms implement करने में difficult थे और storage overhead बड़ा था, लेकिन optimization और improvements के बाद कुछ production environments के लिए suitable tree synchronization algorithms सामने आए
- representative CRDT-based approaches दो हैं
Kleppmann approach: सभी operations को Move में unify करना
- A highly-available move operation for replicated trees tree के create, delete, move को एक move operation में unify करता है
- move operation
Move t p m c के चार values से define होता है
t: Lamport timestamp जैसा unique और sortable timestampp: parent node IDm: node से जुड़ा metadatac: child node ID
- अगर tree में
c नहीं है, तो यह parent p के नीचे child c बनाने वाला create operation बन जाता है
- अगर
c पहले से है, तो यह existing parent से new parent p में ले जाने वाला move operation बन जाता है
- delete को specified
TRASH node में move करने के तरीके से handle किया जाता है
TRASH के सभी child nodes को deleted माना जाता है- लेकिन उन्हें memory में रखा जाता है ताकि concurrent editing उस node को किसी दूसरे node में move कर सके
- यह ancestor delete और child node move के simultaneously होने वाली स्थिति को handle करने की mechanism है
ordering और unsafe operation
- delete भी move operation के रूप में define होने से “same node delete और move” दो move operations के conflict में बदल जाता है
- बची हुई core problems दो हैं
- same node को अलग-अलग parents के नीचे move करना
- अलग-अलग nodes को move करके cycle बनाना
- Lamport timestamp और Peer ID से सभी operations को linear order में sort करने पर same node के concurrent moves भी ordered दो operations के रूप में represent होते हैं
- tree को सिर्फ move operations से model करने पर concurrent editing की exceptional situation cycle creation तक सीमित हो जाती है
- cycle बनाने वाला operation unsafe operation माना जाता है
- algorithm सभी move operations को timestamp order में sort करता है
- हर operation apply करने से पहले cycle detect करता है
- अगर cycle बनता है, तो सही tree structure बनाए रखने के लिए उस unsafe operation को ignore करता है
Lamport Timestamp और remote operations apply करना
- Lamport Timestamp distributed system events के causal order को judge करने देता है
- हर peer के पास 0 से शुरू होने वाला counter होता है
- local event होने पर counter को 1 बढ़ाकर उस value को timestamp के रूप में use किया जाता है
- peer
A जब B को message भेजता है, तो timestamp attach करता है
B अपनी logical clock और received timestamp compare करके बड़े value से update करता है
- global ordering पहले Lamport Timestamp compare करता है, और values same हों तो peer की unique ID को tie-breaker की तरह use करता है
- remote update अगर existing sorted operation sequence के बीच में आ जाए तो undo-do-redo की जरूरत होती है
- recent operation को undo किया जाता है
- new operation insert करके apply किया जाता है
- undone operation को फिर से apply किया जाता है
- move operation को जल्दी undo करने के लिए हर move apply करने से पहले target node का old parent cache किया जाता है
- unsafe operation का effect ignore करने पर भी record रखना जरूरी है
- operation की safety dynamically decide होती है
- बाद में अगर cycle trigger करने वाला कोई दूसरा node पहले delete होने वाला update receive हो, तो पहले unsafe रहा operation safe हो सकता है
- undo process में last effective operation के target parent को खोजने के लिए ineffective marking जरूरी है
undo-do-redo उदाहरण
- अगर कोई नया operation ऐसे operation पर निर्भर करता है जो local में मौजूद नहीं है, तो इसका मतलब है कि बीच की version update अभी missing है; इसलिए उसे अस्थायी रूप से cache करके missing update मिलने के बाद apply करना होगा
- अगर नया
opId सभी मौजूदा operations से बड़ा है, तो उसे तुरंत apply किया जा सकता है
- safe होने पर target node के current parent को old parent के रूप में record किया जाता है और move apply किया जाता है
- unsafe होने पर उसे ineffective के रूप में mark करके effect को ignore किया जाता है
- अगर नया
opId मौजूदा order के बीच में आता है, तो बाद के operations को एक-एक करके निकालकर undo किया जाता है, नया operation apply किया जाता है, और फिर undo किए गए operations को क्रम से फिर से apply किया जाता है
- उदाहरण flow में
Peer1 local तौर पर C को B के नीचे move करता है, फिर Peer0 द्वारा B को C के नीचे move करने वाला operation receive करता है
- Lamport timestamp order में
0:3, 1:3 से पहले आता है, इसलिए पहले 1:3 को undo करके C को old parent A पर वापस लाया जाता है
- इसके बाद
0:3 से B को C के नीचे move किया जाता है
- फिर
1:3 को redo करके C को B के नीचे move करने की कोशिश की जाती है, लेकिन cycle detect होने के कारण apply नहीं होता
- tree state बदले बिना undo-do-redo प्रक्रिया पूरी हो जाती है
Evan Wallace तरीका: पुराने parents को track करना
- Evan Wallace का CRDT: Mutable Tree Hierarchy हर node से उसके सभी पुराने parent nodes को track करवाता है
- हर record किए गए parent के साथ एक counter होता है
- नए parent की count value उस node के सभी पुराने parent counts से 1 ज्यादा होती है
- सबसे ज्यादा count वाला parent current parent बनता है
- synchronization के समय parent records भी साथ में sync होते हैं
- cycle होने पर heuristic algorithm cycle बनाने वाले node को उसके सबसे नज़दीकी ऐसे पुराने parent से फिर जोड़ता है जो cycle नहीं बनाता और root से connected है
- यह प्रक्रिया तब तक दोहराई जाती है जब तक सभी cyclic nodes फिर से tree में attach नहीं हो जाते, जिससे replicas के बीच tree structure sync हो जाता है
- इस तरीके में महंगी undo-do-redo प्रक्रिया की जरूरत नहीं होती, लेकिन remote move मिलने पर हर बार यह check करना पड़ता है कि सभी nodes root से connected हैं या नहीं, और cyclic nodes को फिर से attach करना पड़ता है; इसलिए बहुत सारे nodes होने पर performance खराब हो सकती है
- performance comparison के लिए अलग से benchmark बनाया गया है
Loro का Movable Tree implementation
- Loro, Martin Kleppmann आदि के A highly-available move operation for replicated trees algorithm को implement करता है
- यह algorithm ज्यादातर real-world scenarios में high performance देता है
- इसका मुख्य undo-do-redo process, Loro में Eg-walker(Event Graph Walker) द्वारा remote updates apply करने के तरीके से बहुत मिलता-जुलता है
- सिर्फ movable tree से sibling nodes के ordering problem का समाधान नहीं होता
- outline notes या graphic design software के layer management में child nodes को sort करना जरूरी होता है
- users को node order adjust करके उसे दूसरे collaborators या devices के साथ sync करना होता है
- Loro,
Fractional Index algorithm को integrate करके movable tree के child nodes को sortable बनाता है
Fractional Index और concurrent insertion conflicts
Fractional Index हर object को एक sortable value देता है
- दो objects के बीच नया insertion होने पर नए object का
Fractional Index left और right values के बीच होता है
- संबंधित explanation Figma blog और Evan blog में देखी जा सकती है
- distributed environment में अगर कई peers एक ही position पर नया node insert करते हैं, तो अलग-अलग content वाले nodes को वही
Fractional Index assign हो सकता है
- Loro समान
Fractional Index बनाए रखता है, और same index वाले items की relative order हर peer की unique ID, PeerID, से तय होती है
- अगर दोनों तरफ same
Fractional Index हो, तो उनके बीच नया Fractional Index नहीं बनाया जा सकता
- Loro इस समस्या को दो तरीकों से handle करता है
- generate होने वाले
Fractional Index में कुछ मात्रा में jitter जोड़कर same index बनने की संभावना काफी घटाता है
- उदाहरण के लिए 0 और 1 के बीच value मूल रूप से 0.5 हो, तो random jitter से यह
0.52712, 0.58312, 0.52834 जैसी value हो सकती है
- अगर
0.7@A और 0.7@B के बीच insert करना हो, तो 0.7 और 1 के बीच नए node और 0.7@B node को अलग-अलग नया Fractional Index देकर reset किया जा सकता है
encoding size और jitter setting
- Loro, drifting-in-space के
Vec<u8> आधारित Fractional Index implementation का उपयोग करता है
- यह implementation base 256 है
- default में आगे या पीछे लगातार 128 values insert करने पर ही
Fractional Index का byte size 1 बढ़ता है
- worst-case storage overhead तब होता है जब हर बार नई value को बारी-बारी से insert किया जाए
- उदाहरण के लिए
ab में a और b के बीच c डालना, फिर c और b के बीच d, और c और d के बीच e डालना
- ऐसे case में एक नया operation अतिरिक्त byte मांग सकता है, लेकिन यह बहुत rare situation है
- Loro ने original implementation में simple jitter solution जोड़ा है
Fractional Index में jitter value length जितने random bytes append किए जाते हैं- JavaScript में
doc.setFractionalIndexJitter(number) में positive number देकर jitter activate किया जा सकता है
- encoding size थोड़ा बढ़ता है, और हर
Fractional Index में jitter bytes जुड़ते हैं
- same position पर
Fractional Index बनाते समय 99% probability से conflict avoid करने के लिए jitter और maximum concurrent edits की संख्या n का संबंध इस प्रकार है
| jitter |
maximum concurrent edits |
| 1 |
3 |
| 2 |
37 |
| 3 |
582 |
- sorted बहुत सारे
Fractional Index में common prefix ज्यादा हो जाता है
- Loro encoding के समय पिछले value के साथ same prefix bit count और remaining bytes ही store करने वाली prefix optimization से overall encoding size घटाता है
संबंधित काम और चयन का कारण
Fractional Index के अलावा tree के sibling nodes को order करने वाले movable list CRDT भी मौजूद हैं- Martin Kleppmann का Moving Elements in List CRDTs, Loro की Movable List में use होता है
Fractional Index solution का implementation ज्यादा simple है- tree nodes को model करते समय अगर child nodes को stable position representation न दिया जाए, तो पूरी tree structure जरूरत से ज्यादा complex हो जाती है
Fractional Index में interleaving problem है
- Figma layer item या multi-level bookmark जैसे cases में, जहां सिर्फ relative order चाहिए और strict sequential semantics की जरूरत नहीं होती, यह acceptable है
बेंचमार्क परिणाम
- Loro ने Movable Tree implementation के लिए random node moves, पुराने versions पर switch करना, और बहुत गहरे tree structure की extreme-condition performance को benchmark किया
- परिणाम ऐसे स्तर के निकले कि real-time collaboration और पुराने versions का सहज checkout support किया जा सके
- Test environment M2 Max CPU है, और bench code tree.rs में है
| काम |
समय |
सेटिंग |
| 10000 random moves |
28ms |
पहले 1000 nodes बनाए गए |
| अलग-अलग versions पर 1000 switches |
153ms |
पहले 1000 nodes बनाए गए, फिर 1000 moves |
| depth 300 tree में अलग-अलग versions पर 1000 switches |
701ms |
नया node पिछले node का child |
उपयोग के उदाहरण और demo
loro-crdt का LoroTree node creation, position specify करके creation, move, root में move, दूसरे node के आगे-पीछे move, parent के भीतर index lookup, Fractional Index lookup, और node के data map तक access देता है
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
- Loro के साथ कई peers के बीच data synchronization simulate करने वाला Todo app demo बनाया गया
Movable Tree subtask relationship को दर्शाता हैMap task की कई properties को दर्शाता हैText task title को दर्शाता है- create, move, edit, delete के अलावा Loro-based version switching भी implement किया गया
- scrollbar को drag करके किए गए सभी पुराने versions के बीच switch किया जा सकता है
सार
- Movable Tree CRDT implementation concurrent moves, deletion, cycles, ancestor deletion और child move के combination की वजह से कठिन है
- Loro, Kleppmann आदि के high-availability move operation algorithm से tree hierarchy moves implement करता है
- child nodes के बीच move और ordering को drifting-in-space के
Fractional Index implementation को integrate करके handle किया जाता है
- यह combination विभिन्न collaborative application scenarios की जरूरतों को पूरा कर सकता है
1 टिप्पणियां
Hacker News की राय
काम/नोट्स के लिए एक नया multiplayer editor [1] बना रहा/रही हूँ, जो text और outliner operations दोनों को support करता है
बाहर से यह एक flat text document जैसा व्यवहार करता है, लेकिन outliner features की वजह से internally यह एक बड़ा tree बन जाता है। बदलावों को sync करने के लिए high-availability move operations से मिलती-जुलती approach इस्तेमाल होती है। tree बदलने वाला सिर्फ एक operation है:
insmov; और जब client online होता है, तो change set C को server के साथ sync करता है। अगर server पर remote changes हैं, तो वह आखिरी sync के बाद के सभी changes R को global linear order में लौटाता है, local changes C केinsmovको undo करता है, फिर R और वे नए changes फिर से apply करता है जो अभी sync नहीं हुए हैंfractional indexes का इस्तेमाल नहीं करता/करती;
insmovtuple में parent P के साथ-साथ previous siblingguidA भी शामिल होता है। सभी tree operations आखिरकार server द्वारा तय global linear order में apply होते हैं, इसलिए orderinginsmovoperation itself से ही handle होती है। ज्यादातर मामलों में undo की जरूरत नहीं पड़ती; सही क्रम में replay केवल तब चाहिए जब server पर ऐसाinsmovchange हो जिसके बारे में मुझे पता नहीं है और उसी समय मैं नयाinsmovभेज रहा/रही हूँ। लंबी flight के बाद Wi-Fi से दोबारा connect करते समय ऐसा हो सकता है, लेकिन online रहते हुए WebSocket से real-time push मिलने पर यह कम आम है, और text updates जैसे non-insmovoperations के लिए इसकी जरूरत नहीं होती[1] https://thymer.com
उदाहरण के लिए, Lamport timestamps के बजाय server order इस्तेमाल करने जैसा
[1] https://inria.hal.science/inria-00555588/
HN पर Thymer search किया तो 2009 का Show HN[1] मिला, और लगता है Thymer पिछले 15 सालों से private beta में था
0. https://news.ycombinator.com/item?id=40786425
यह लेख जरूर पढ़ना पड़ेगा। freelance client work में React Table Library [0] को open source किया था, और tree operations पर focus किया था
वे 100,000 nodes के scale वाले folder/file tree structure से deal करते हैं, और folder व file move, copy, top-level और nested levels पर lazy loading वगैरह को उसी table structure के अंदर handle करते हैं। project खत्म करने के बाद समझ आया कि Google Drive एक ही hierarchy level पर ही display और edits की अनुमति क्यों देता है। कई nodes वाले nested view में इसे implement करने के लिए बहुत सारी constraints का ध्यान रखना पड़ता है
[0] https://react-table-library.com/
सलाह चाहिए। multiplayer app तो नहीं है, लेकिन frontend में user profiles के रूप में इस्तेमाल होने वाले बड़े और आपस में जुड़े denormalized trees हैं
इसे tile-based layout जैसा सोचें: user tiles add/delete/resize करता है, हर tile slot में कई components जोड़ता है, और उन components के अपने profiles भी होते हैं। अलग-अलग tile arrangements वाले कई layouts मौजूद हो सकते हैं, और complexity यह भी है कि individual tiles global state के दूसरे हिस्सों को reference या share कर सकते हैं
सामान्य REST से safely update करना मुश्किल है। क्योंकि यह guarantee करनी होती है कि वही user दो tabs खोलकर tab 1 में update करे और फिर tab 2 में फिर update करे, तो पूरा profile invalid state में न चला जाए। कुल मिलाकर order भी important है। client में सही से apply हुआ update अगर server पर skip हो जाए, तो चीजें टूट सकती हैं
एक बहुत simple solution के तौर पर, मैंने किसी specific state piece को पूरी तरह overwrite करने के लिए minimum data भेजने और उसे queue के पीछे डालने का तरीका इस्तेमाल किया। आम तौर पर ठीक रहता है, लेकिन कभी-कभी असली change सिर्फ कुछ bytes का होता है और 50KB भेजना पड़ता है, जिससे waste होता है
आम तौर पर CRDT की जरूरत जिन कारणों से पड़ती है वे यहाँ नहीं हैं, लेकिन single user के लिए भी state management काफी आसान हो सकता है। पहले तो user के browser tabs के बीच sync हो जाएगा, और ज्यादा important यह कि frontend state को बस बदलने पर भरोसा किया जा सकेगा कि CRDT server के साथ सही coordination कर देगा। अब खुद handle नहीं करना पड़ेगा। जानना चाहता/चाहती हूँ कि क्या यह समझ में आता है, या multiplayer और local-first की जरूरत न होने पर Yjs जैसी चीज जोड़ने का overhead worth it नहीं है
हालांकि अगर profile editing सिर्फ single user के लिए है, तो CRDT लाना जरूरत से ज्यादा लगता है। ऊपर से देखने पर दो tabs खुले रखने वाला scenario सबसे बड़ा bug source दिखता है, इसलिए
BroadcastChannelसे update events बाकी सभी tabs को notify करने का तरीका इस्तेमाल किया जा सकता हैserver state के कुछ हिस्से को overwrite करने वाली REST calls से shared state maintain करना असल में fragile है, और यह सिर्फ flat data records के fields overwrite करने जैसे मामलों के लिए ही suitable है। साथ ही server-client state coordination को हमेशा सावधानी से सोचना पड़ता है, और normal flow से बाहर वाले paths में sync आसानी से बिगड़ जाता है
जैसा आपने कहा, अगर ऐसा CRDT बनाया जाए जो specify करे कि updates कैसे merge होते हैं, तो cognitive load काफी कम हो जाएगा
Google Docs या Zoho Writer जैसे rich text content में, list item को नीचे ले जाना या नया column जोड़ना, table/list operations मूल रूप से tree manipulation operations ही हैं
ऐसे मामलों में simultaneous conflicts को context-specific special handling के बिना converge कराना बेहद कठिन माना जाता है [1]. जिज्ञासा है कि क्या यह implementation ऐसे use cases के लिए भी कोई generalized solution देती है
शायद leaf nodes, यानी text blocks के लिए list या string CRDT इस्तेमाल किया जा सकता है, और structural nodes जैसे lists और tables के लिए इस tree CRDT को compose किया जा सकता है। लेकिन तब हर operation में 2D address
(parent-id, index_offset_into_that_parent)जोड़ना पड़ेगा[1] https://github.com/inkandswitch/peritext/issues/27
Text CRDT मूल रूप से character data रखने वाला list CRDT ही है। इसलिए embedded elements को string के बाकी items की तरह size 1 वाले special item, यानी embedded child node, के रूप में आसानी से model किया जा सकता है। सही approach इस्तेमाल करने पर जरूरत के हिसाब से tree के अंदर अलग-अलग CRDTs mix किए जा सकते हैं। उदाहरण के लिए rich text के अंदर एक table हो, और उसके किसी cell में image हो
हर operation में
parent-crdt-idfield लगाना अफसोसजनक है, लेकिन इससे बचना मुश्किल लगता है। अच्छी बात यह है कि ज्यादातर real-world use cases में consecutive operations का same parent CRDT share करना बहुत आम होगा, इसलिए ऐसे ID fields run-length encoding से अच्छी तरह compress हो सकेंगेहालांकि Seph ने जैसा कहा, same parent के नीचे consecutive operations को effectively compress किया जा सकता है, इसलिए ऐसे parent ID का amortized overhead आम तौर पर बड़ा नहीं होता
जानना चाहूंगा कि image pixels या 3D models जैसी high data density वाली applications के लिए कोई practical CRDT रहा है या नहीं
document का concrete representation data-intensive हो सकता है, फिर भी individual user edits और operations को encode करने का तरीका छोटा रह सकता है
मान लीजिए Photoshop जैसा image editor बनाया जा रहा है। channel के हिसाब से 16-bit color depth वाली uncompressed 102-megapixel image, जैसे Fujifilm GFX100 photo, TIFF में करीब 610MB होती है। अगर हर pixel को अलग last-write-wins register के रूप में represent करें तो overhead बड़ा होगा, लेकिन ऐसा representation user intent preserve करने के लिए सच में सही नहीं है। user के edits कुछ ऐसे होंगे: "image contrast 15% बढ़ाना" या "brush Q और color #000 से spline [(0,0), (1500, 1500)] paint करना"। अगर हर pixel को Lamport timestamp से synchronize किया जाए, तो user 1 का contrast change user 2 द्वारा paint किए गए pixels को छोड़कर सभी pixels पर लागू होगा, जिससे overpainted pixels अजीब दिख सकते हैं
इसके बजाय user intent को edit operation list के रूप में represent करना बेहतर है। यह 102MB pixel grid पूरी की तुलना में कहीं छोटा है। CRDT data structure ऐसे user intent को synchronize करने के संभावित technical mechanisms में से एक है, लेकिन structure output के concrete data layout के बजाय user intent की semantics के हिसाब से चुना जाना चाहिए
फिर भी
"add new layer namedbgbelow layerfgwith pixelsdata:(10mb of pixels)at (1500, 1500)"जैसे बड़े data वाले edit operations हो सकते हैं। लेकिन इस तरह के edit command का synchronization overhead बहुत कम होता है, और उसका size O(1) होता है, edit command के अंदर pixels की संख्या के proportional O(pixels) नहीं3D models अलग समस्या हैं, और मैंने market में कोई collaborative 3D modeling tool देखा नहीं है। हालांकि मैंने actively खोजा भी नहीं
मैंने खुद इसे बनाया नहीं है, और यह वास्तव में practical होगा या नहीं, इसका भी भरोसा नहीं। फिर भी कम से कम document की पूरी history preserve की जा सकती है
यह data को Yjs से represent करता है, लेकिन raw pixels store करने के बजाय transformations की पूरी history store करता है
https://digest.browsertech.com/archive/browsertech-digest-ho...
जिज्ञासा है कि क्या article को GPT से check कराया गया था। पहले paragraph में ChatGPT वाली style काफी मजबूत लगती है
This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.