TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Movable tree CRDTs and Loro's implementation

286 点作者 czx11133110 个月前

6 条评论

wim10 个月前
We&#x27;re building a new multiplayer editor for tasks&#x2F;notes [1] which supports both text and outliner operations. Although it behaves like a flat text document, the outliner features essentially turn the document into a large tree under the hood. We do something similar to the highly-available move operation to sync changes:<p>There is one operation to change the tree, called insmov (move-or-insert). Whenever a client is online it can sync changes C to a server. Whenever the server has remote changes for us, it will send us back a list R of all changes since our last sync in a global linear order. We then undo any of the insmovs in our changeset C, and (re)apply all changes in R + any new changes we didn&#x27;t sync yet.<p>We don&#x27;t use any fractional indices though. Instead, our insmov tuple not only contains a parent P, but also a previous sibling guid A. Because all tree ops will eventually be applied in the global linear order as determined by the server, &quot;sorting&quot; is handled by just using the insmov operation.<p>Most of the time the undo&#x27;ing of operations is not needed though. Only when the server has insmov changes we don&#x27;t know about while we are sending new insmovs ourselves do we need to ensure we replay the operations in the correct order. That&#x27;s likely to happen when you reconnect to wifi after a long flight, but not so likely when updates are pushed in real-time over websocket when you&#x27;re online (plus it&#x27;s not needed for non-insmov operations, like updating text).<p>[1] <a href="https:&#x2F;&#x2F;thymer.com" rel="nofollow">https:&#x2F;&#x2F;thymer.com</a>
评论 #41101314 未加载
评论 #41100751 未加载
评论 #41100761 未加载
rwieruch10 个月前
Wow I have to read this! For a freelance client of mine, I have open sourced React Table Library [0] with the focus on tree operations. They are handling a folder&#x2F;file tree structure of 100 thousands nodes where it is possible to move folders&#x2F;files, clone them, lazy load them on a top and nested level, etc. And all of it in the same table structure.<p>After I finished the project, I kinda knew why Google Drive only allows to display and modify on the same hierarchical level. There are so many constraints that you have to consider when implementing this in a nested view with many nodes.<p>[0] <a href="https:&#x2F;&#x2F;react-table-library.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;react-table-library.com&#x2F;</a>
评论 #41104032 未加载
koromak10 个月前
Asking for advice: I do not have a multiplayer app, but I have some large, interconnected, denormalized trees on my frontend as user profiles. Think like a tiled layout, where a user can add&#x2F;remove&#x2F;resize tiles, and then add a number of components into each tiled slot, each of those having their own profiles too. Multiple &quot;layouts&quot; can exist with different arrangements of tiles, and theres some other complexity with individual tiles referencing and sharing other pieces of state globally.<p>Making safe updates via regular REST is difficult, as you have to make sure someone with two tabs open isn&#x27;t going to make an update on tab 1, then another on tab 2 which puts the overall profile into an invalid state. And in general, ordering matters. Skipping an update serverside that was properly applied clientside could break things.<p>The dumb-as-rocks solution I came up with is to just send the minimal amount of data over that can completely overwrite a particular chunk of state, and place it behind a queue. Usually thats fine, but sometimes thats a lot of wasted data, 50KB when the actual change was only a couple bytes.<p>I don&#x27;t need CRDTs for any of the regular reasons, but it seems like it would make state management a million times easier, even for a single user. For one, I&#x27;d get syncing between a user&#x27;s browser tabs, which is good. But moreover, I can just make simple changes to frontend state, and trust that the CRDT is going to negotiate it properly with the server. I no longer have to deal with it myself.<p>Does this make sense? Or is the overhead required to make something like Yjs work not worth it when I don&#x27;t even need multiplayer and local-first.
评论 #41100709 未加载
评论 #41103768 未加载
lewisjoe10 个月前
When working with formatted text content like in Google Docs &#x2F; Zoho Writer: moving a list item down or adding a new column or any table&#x2F;list operation is essentially a tree manipulation op.<p>Concurrent conflicts in such cases are notoriously hard to converge without contextual special handling [1]. Does this implementation generalize a solution for such use-cases?<p>I guess it should be possible to combine a list(or string) CRDT for leaf nodes (i.e text blocks) and use this tree CRDT for structural nodes (lists &amp; tables).<p>But that will make augmenting every op with two-dimensional address (parent-id, index_offset_into_that_parent)<p>[1] <a href="https:&#x2F;&#x2F;github.com&#x2F;inkandswitch&#x2F;peritext&#x2F;issues&#x2F;27">https:&#x2F;&#x2F;github.com&#x2F;inkandswitch&#x2F;peritext&#x2F;issues&#x2F;27</a>
评论 #41100436 未加载
评论 #41100909 未加载
billconan10 个月前
I wonder if there has been any practical CRDT for data dense applications, such as images (pixels) and 3D models?
评论 #41102366 未加载
评论 #41101107 未加载
评论 #41100641 未加载
评论 #41103224 未加载
评论 #41102320 未加载
评论 #41100632 未加载
curtisblaine10 个月前
Did you use a GPT to check your article? The first paragraph has a strong ChatGPT voice IMHO.
评论 #41104461 未加载