23 ms·

CRDTs are the future

1181 points by lewisjoe 6y ago

indrax 6y ago
>I’m no longer convinced OT - and all the work I’ve done on it - will still be around. I feel really sad about that. Don't be sad. What you did was a huge inspiration to me and I think a lot of people. It showed the possibilities even if it wasn't "optimal". Commenting here in hope you'll see it. I skim to read most things, I only completed reading this article because I noticed 'I worked on Google Wave'.
stephc_int13 6y ago
When dealing with this type of discussion I always try to remember that making design decisions is a tradeoff, an arbitrage highly dependent on your knowledge of the field, but also context and taste. Believing there is a silver bullet is a fool errand. From what I've read about CRDTs, it seems difficult to escape the overengineering trap when dealing with them.
- tabtab 6y ago
  I tend to agree. Each team, project, and organization has different needs, preferences, and cultures. One-size-fits-all is a really tall order. I believe it's better to focus on kits of parts--API's and/or self-contained functions--that can be combined or ignored as needed, along with a variety of reference application samples. Having lots of ways to easily filter and sort content is also very useful. For example, filtering and/or sorting annotations by person, group, date, content (sub-strings) is very useful. A query-by-example kind of interface is nice for this.
bigfish24 6y ago
Great summary. CRDTs are a better fit for generalized data. Having previously worked on an OT system, the central server stickiness and merge complexity simply did not scale. There are trade-offs with CRDTs, especially metadata, but as the post mentions compression techniques are far more solvable in real-world scenarios than a fundamental performance bottleneck at the core.
macintux 6y ago
The title sounds like it could be fanboy clickbait but it’s actually a thoughtful look at how far CRDTs have come from the viewpoint of an expert and skeptic. A good read.
taeric 6y ago
I hate that I am skeptical on this. I suspect wave just left that bad of a taste behind. So much hubris in what was claimed to be possible. The ideas do look nice. And I suspect it has gotten farther than I give credit. However, sequencing the edits of independent actors is likely not something you will solve with a data structure. Take the example of a doc getting overwhelmed. Let's say you can make it so that you don't have a server to coordinate. Is it realistic to think hundreds of people can edit a document in real time at the same time and come up with something coherent? Best I can currently imagine is it works if they are editing hundreds of pages. But, that is back to the basic wiki structure working fine. So, help me fix my imagination. Why is this the future?
- archagon 6y ago
  In the case of a text document, concurrent edits form branches of a tree in many string CRDTs: http://archagon.net/blog/2018/03/24/data-laced-with-history/ http://archagon.net/blog/2018/03/24/data-laced-with-history/ So yes, hundreds of people can edit a string and produce a coherent result at the end. Contiguous runs of characters will stick together and interleave with concurrent edits.
  - omgtehlion 6y ago
    I upvote for the link alone. This article (data-laced-with-history) is the best source if you are starting your journey into CRDTs.
  - deegles 6y ago
    What if the document starts empty and syncing doesn't happen until everyone presses submit? Will it CRDTs produce a valid document? Yes. Will it make any sense? Who knows. I think that's what OP is getting at.
    - archagon 6y ago
      I read it as a question regarding OT vs. CRDTs, which I believe would produce similar results even under heavy concurrency. In terms of larger edits or refactors, you’d probably need to do something else, e.g. lock the document or section, unshare the document, use some sort of higher-level CRDT that ships your changes atomically and forces a manual merge on concurrent edits, etc. None of these necessarily require a central server, though they may require an active session between participants. I should also note that even if you use regular merge, and the end state of a text document is a complete mess after a refactor + concurrent edits, there’s enough data in the tree to simply pull out any concurrent contributions. They could then be reapplied manually if needed. Perhaps the app could even notice this automatically and provide an optional UI for this process. Similarly, it would be possible for the concurrent editors to remove the refactor edits and thus “fork” their document.
SirensOfTitan 6y ago
So CRDTs are the future, but what about today for real, production products? I'm just about to really dive into collaborative editing features for our product, and OT still seems to me to be a much safer bet unless you're dealing with a more obscure environment.
- omgtehlion 6y ago
  Yes, starting with OT looks easy. You can make 99% work in almost no time. But the last 1% will bite you in the rear really hard... Actually, CRDT is not a single data structure or even algorithm. It is a term for several families of data structures and different algorithms on them. If your task is not editing text, you may find a simple and already implemented CRDT for your case.
- toomim 6y ago
  > So CRDTs are the future, but what about today for real, production products? Try Y.js: https://github.com/yjs/yjs https://github.com/yjs/yjs
crawshaw 6y ago
I have been consistently at odds with myself comparing CRDTs vs. OT. One the one hand, CRDTs have a nicer core formalism. On the other hand, OT works, and is closer to the actual driving events of text editing. The core argument of this article: that CRDTs now work and distributed is better than centralized I question. I certainly want more distribution than "everything is run on a google server" but do I really foresee a need for distributing a single document? One server with an optimal OT implementation can probably handle near a million active connections. In practice, that's plenty. Each piece of data having one owner is quite reasonable. There are lots of pieces of data. I remain on the fence for collaborative text editing. Though it's great to see all the work pushing CRDTs forward!
- josephg 6y ago
  Blog author here. I've been having this conversation with a lot of folks over the last few weeks and I hear you. Does it make sense for us as an opensource community to invest our time and energy making one really good CRDT (with implementations in a few languages). Or does it make sense for us to distribute that energy between a bunch of CRDT and OT implementations, with different performance tradeoffs? My take is that its been hugely beneficial to us all that JSON is a standard, because I can use it from every language, and have confidence that the implementations are fast and good quality. I think we have an opportunity to make that for a good CRDT too. Even if OT would work fine in your architecture, if we have a great, capable, fast CRDT kicking around, it could be a reasonable default for most people. And my claim is that the performance difference between CRDTs and OT is smaller than the difference between high and low quality implementations. (I expect a well written CRDT in wasm will outperform my OT code in javascript.)
omgtehlion 6y ago
CRDTs are hip and cool. But right now I'm trying to find an implementation for desktop software, not some web-framework in-electron. And could not find a concise and correct codebase. All the implementations are: 1. javascript or 2. dependent on their chosen method of synchronisation or 3. incorrect. The result of a two week long search is that I'm reimplementing the stuff myself...
- WhatIsDukkha 6y ago
  https://github.com/automerge/automerge-rs https://github.com/automerge/automerge-rs I can't speak to its usability as I'm waiting on a 1.0
  - omgtehlion 6y ago
    yeah... you better wait for 1.0...
  - memorythought 6y ago
    Im one of the authors of this. Right now the code is very unstable as we're tracking the performance branch of the JS implementation. Once the JS version hits 1.0 I'll be putting a bunch of effort into making the API cleaner and more rusty and documenting things. It does work and can actually be used as a backend for the JS implementation if you use the wasm backend we've built. In fact, this is how we have tested it, by compiling to WASM and running the JS test script against it.
csours 6y ago
If you don't use CRDTs, you may be doomed to re-invent them. Reading about them just now I realized that I spent the last year developing a CRDT with LWW and OR characteristics. edit: updated 'you are doomed' to 'you may be doomed'.
xwdv 6y ago
CRDT stands for conflict-free replicated data type.
- contravariant 6y ago
  Thanks, I had to look it up as well. It's not the first article I read on CRDTs but I definitely didn't recall what they were from just the acronym.
lewisjoe 6y ago
I'm part of the team that makes Zoho Writer (a Google Docs alternative) - https://writer.zoho.com https://writer.zoho.com We went with OT for our real-time syncing of edits in 2010 and a decade later, we are still sticking with OT for reasons I already stated sometime back - https://news.ycombinator.com/item?id=24186883 https://news.ycombinator.com/item?id=24186883 However, in the spirit of "There are no solutions, only trade-offs" CRDTs are absolutely necessary for certain type of syncing - like syncing a set of database nodes. But for systems which already mandate a central server (SaaS/Cloud) and especially for a complex problem like rich-text editing (i.e semantic trees) I still think OT provides better trade-offs than CRDT. I respect Joseph's conviction on CRDTs being the future, so I guess we'll figure this out sometime soon.
- cordite 6y ago
  What does OT stand for? In the link, OT is aliased to "Operational Transformations"
  - dwb 6y ago
    Have you not answered your own question? OT does indeed stand for Operational Transformation. https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation
  - mjhirn 6y ago
    "Operation Transformation" = "a system that supports collaboration functionalities by separating the high-level transformation (or integration) control from the low-level transformation functions" Source: OT's Wikipedia article But I felt the same. Never heard of "Operation Transformation" before and both OT and its alias were equally opaque to me.
- RangerScience 6y ago
  Interesting. I might be adding real-time edit syncing to a hobby project sometime soon. Can you share more about the trade-offs?
blackgirldev 6y ago
Doesn't Redis implement CRDT's in production? https://redislabs.com/blog/diving-into-crdts/ https://redislabs.com/blog/diving-into-crdts/
- zegl 6y ago
  Riak as well, I've used it very successfully on projects in the past. https://docs.riak.com/riak/kv/latest/developing/data-types/index.html https://docs.riak.com/riak/kv/latest/developing/data-types/i...
- dnautics 6y ago
  Yes, as does riak. There are plenty of simple crdts and the theory, while recent, has all of it's fundamentals fleshed out. We know what property makes data structures crdts, and how to compose them, and how to prove they are crdts. Currently we are in the "discovery of new crdts" and "engineering and implementing of older crdts reliably" phase, and in some cases "discovering when not to use crdts". The crux of the this issue is that crdts that play nice with human expectations in regards to collaborative document editing are not known, possibly excepting automerge (yjs). As it's a 'softer' concept will no good axioms, there is no solid theory on how to combine the theoretical requirements of crdts with human expectations.
- einpoklum 6y ago
  It looks like it's basically biasing in favor of some operations over others. In the link they talk about CRDT sets, saying at some point: > 1. Adding wins over deleting. yeah, so, _maybe_ you can remove elements from your set. If you're lucky. I dunno about all that...
  - samatman 6y ago
    That's an overly pessimistic way to put it. I think it's more accurate to say that maybe you can remove elements from your set... unless another actor wants them in the set. That's not always the behavior you want. But if it is, it's great.
mhale 6y ago
I'm working on a project with some offline data synchronization needs, but haven't started implementation yet. I've been following CRDTs with interest. I also saw many of the same downsides mentioned in the OP, e.g. bloat (which apparently are being addressed remarkably well). Beyond OT, another approach I've run across that looks very promising is Differential Synchronization[1] by Neil Fraser. While it also relies on a centralized server, it allows for servers to be chained in such a way that seems to address many of the downsides of OT. I wonder why I rarely ever see Differential Synchronization mentioned here on HN? Is it due to lack of awareness or because of use-case fit issues or some fatal flaw I haven't seen? Or something else? [1] https://www.youtube.com/watch?v=S2Hp_1jqpY8 https://www.youtube.com/watch?v=S2Hp_1jqpY8
- archagon 6y ago
  I devoted some time to Differential Synchronization in my article on CRDTs, if you're interested: http://archagon.net/blog/2018/03/24/data-laced-with-history/#differential-synchronization http://archagon.net/blog/2018/03/24/data-laced-with-history/... My sense is that it's not a particularly flexible approach, and falters under adverse network conditions, even though it feels very tempting.
dustingetz 6y ago
A problem w/ e.g. CRDT datasync in web apps is data security, HTTP resources impose control points where you know "why" the client is asking for e.g. this chunk of social graph, it's /profile/friendlist so the UI can ask for a very controlled and tightly specified data projection for that particular UI and consumed by tightly controlled javascript. Datasync is NOT for scraper bots, arbitrary read patterns or any notion of general access. Immutability makes data control way harder ...
benrbray 6y ago
CRDTs seem very promising, but we still have a long way to go. The most exciting work in this area is being done by Ink&Switch [0]. They have a number of interesting real-world app prototypes based on CRDTs. - An interesting case where CRDTs failed is Xi-editor, where they tried to use CRDTs as the basis for a plugin system [1,2]. - One of the biggest problems with CRDTs is the overhead needed to keep track of the full document history. The automerge [3] project has been working on efficient compression of CRDTs for JSON datatypes. - The idea of monotonic updates is really appealing at first, but I was disappointed when I realized there's no good solution to handle deletions. Tombstones, to me, seem like kind of a hack, albeit a necessary one. Practically, CRDTs aren't the silver bullet they might seem like at first. - Another lesson learned is that when ten people are editing the same paragraph, there's not really a right answer. I think the key to implementing CRDTs is doing it at the correct level of granularity. - ProseMirror intentionally chose NOT to use CRDTs [4]. - Some more good references are [5,6,7] [0] https://inkandswitch.com/ https://inkandswitch.com/ [1] https://github.com/xi-editor/xi-editor/issues/1187#issuecomment-491473599 https://github.com/xi-editor/xi-editor/issues/1187#issuecomm... [2] https://news.ycombinator.com/item?id=19886883 https://news.ycombinator.com/item?id=19886883 [3] https://github.com/automerge https://github.com/automerge and https://github.com/automerge/pushpin https://github.com/automerge/pushpin [4] https://marijnhaverbeke.nl/blog/collaborative-editing.html https://marijnhaverbeke.nl/blog/collaborative-editing.html [5] Kleppmann 2020, "CRDTs: The Hard Parts" https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw with HN Discussion: https://news.ycombinator.com/item?id=23802208 https://news.ycombinator.com/item?id=23802208 [6] Kleppmann 2019, "Interleaving Anomalies in Text Editors" https://martin.kleppmann.com/papers/interleaving-papoc19.pdf https://martin.kleppmann.com/papers/interleaving-papoc19.pdf [7] https://abishov.com/xi-editor/docs/crdt-details.html https://abishov.com/xi-editor/docs/crdt-details.html
- yawrp 6y ago
  You might enjoy this piece, covers a few of the tradeoffs you mention https://hex.tech/blog/a-pragmatic-approach-to-live-collaboration https://hex.tech/blog/a-pragmatic-approach-to-live-collabora...
deleted 6y ago
[deleted]
stblack 6y ago
It takes over 800 words, and several mentions of the CRDT acronym, before the acronym is expanded for the reader. Don't write like this. Respect your readers and help them comprehend. Expand acronyms as early as you can, ideally at the first mention.
- samatman 6y ago
  As I tirelessly mention whenever this comes up on HN, which is often: we have a specific technology that is designed precisely for this situation. It's called the link. All an author has to do is link the first instance of an acronym or piece of jargon to some authoritative description, and you get the best of both worlds: readers familiar with e.g. CRDTs[0] can just keep reading, and the rest can click the link and find out. [0]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
  - thesuitonym 6y ago
    Even better, just use the abbr tag. It's well supported and doesn't rely on an outside source to tell your readers what you're talking about.
    - JeremyBanks 6y ago
      Merely expanding an abbreviation is less useful than explaining it.
    - dllthomas 6y ago
      Better in some ways, worse in others. Better than either, I think, is both.
    - taywrobel 6y ago
      “It’s well supported”, yet on latest mobile Safari, it doesn’t appear to work at all. This w3 demo code does not show me the full name anywhere in the rendered content -https://www.w3schools.com/tags/tryit.asp?filename=tryhtml_abbr_test https://www.w3schools.com/tags/tryit.asp?filename=tryhtml_ab...
santiagobasulto 6y ago
If you're a young technical entrepreneur looking for a 10-100M startup opportunity and with a very interesting technical challenge behind it: Create a collaborative replacement of Jupyter Notebooks. There's already some effort done in JupyterLab fork if you're interested [0], but with no significant advancements. So yes, I agree that CDRTs are indeed a promising endeavor. [0] https://github.com/jupyterlab/jupyterlab/issues/5382 https://github.com/jupyterlab/jupyterlab/issues/5382
- darkhorse13 6y ago
  Is it really such a good idea to entice young people like this? Shouldn't someone at least be interested and have domain knowledge in CRDTs and real-time collaboration before diving into building a startup like this?
  - santiagobasulto 6y ago
    Well, yes, of course. But my comment assumes the person might be interested in the subject.
  - TheDong 6y ago
    There's no need to gatekeep building something on already having knowledge. If someone has time and energy and desire, not knowing anything about document editing or CRDTs is not a blocker. Those things can be learned in a week to a month by someone who dedicates time to it. Very few parts of software are inaccessible to someone with basic CS knowledge. It's a great idea for people to try something, regardless of their background, and if they fail but learn something, that's still a fine outcome.
  - colesantiago 6y ago
    Worked for Figma, right? I'm sure they fall into the collaborative software space, utilise CRDTs and the founders are less than 40 years of age. This seems like gatekeeping no?
- fancy_pantser 6y ago
  Domino Data Lab has been around for a while and closed another $43M in funding earlier this year. They have a boatload of tools around collaborative notebooks. They go even further and have data science manager-level dashboards to track the notebooks, their resources, and who is working on what. There are others, but I'm calling this company out specifically because they've shown great traction and I've spent a little time with the cofounders when they were still at a shared incubator space.
hinkley 6y ago
A question that's been in my mind for a while is why Version Control and Collaborative Editing work at such cross purposes with each other when they are essentially solving the same problem? The biggest difference is that one works interactively and the other favors a CLI. Beyond that, how much of the distinction is artificial? In particular I've been wondering about the space between CRDTs and the 'theory of patches' such as we discussed with Pijul the other day. I have a collaborative editing project that's been sitting in my in-box for a long time now because I don't want to write my own edit history code and existing tools don't have enough ability to reason about the contents as structured data. The target audience is technology-averse, so no 'dancing bears' are going to interest them. It's not enough for it to work, it has to work very well.
- PaulDavisThe1st 6y ago
  line-oriented data formats vs everything else. Why ? Because of "patching theory". If you don't understand the the data describes objects and doesn't have line-by-line semantics, it is hard to get merges correct. Version control works wonders with line-oriented stuff, which covers more or less every programming language in existence. It doesn't do so well with non-line-oriented structured formats such as XML (not sure how JSON or TOML) fits in here). Given that collaborative editing typically works with non-line-oriented data formats, you can see the issue, I think.
  - samatman 6y ago
    That's what I refer to as "grammar-aware diffing" in the sibling comment, and it's one of the low-hanging fruits here. Even git allows for pluggable diffing, and doesn't force line orientation. What's missing is the concept of moving something, as distinct from deleting lines/chunks and then inserting lines/chunks which just happen to be the same. This is not a problem which CRDTs have, to put it mildly. I believe pijul understands it as well. A lot of this stuff is right out on the cutting edge, and as it matures it will become practical to connect the edges, such as a CRDT which collaborates with a parser to produce grammar-aware patches which are automagically fed to pijul or something like it. This comes with a host of problems, mostly that we're not used to dealing with a history which has this level of granularity, most of which we don't want to see, most of the time. But they would be nice problems to have.
lisper 6y ago
CRDT = Conflict-Free Replicated Data Types. Think git for data structures instead of directory trees.
deleted 6y ago
[deleted]
yawrp 6y ago
Interesting piece from last week comparing OT, CRDT, and Figma's hybrid approach (good explainers of each too): https://hex.tech/blog/a-pragmatic-approach-to-live-collaboration https://hex.tech/blog/a-pragmatic-approach-to-live-collabora...
zemo 6y ago
I use CRDTs in production at Jackbox for audience functionality and honestly I don't know why the only thing that people talk about when it comes to CRDTs is collaborative text editing. Like, sure, cool, but that's literally a single problem domain and like, Google Docs already exists and works well for the majority of users so how many developers actually need to create a collaborative text editor? CRDTs are an incredibly abstract and versatile concept; collaborative text editing is a tiny problem domain. I would really like to see more writing about CRDTs that is NOT about collaborative text editing.
- rhencke 6y ago
  Would you consider being the writer of one of those articles?
  - zemo 6y ago
    well I really walked into that question huh
    - gen220 6y ago
      I'd read this article. Or, if you'd rather not, can you share some examples of problem domains, that we at home can search for?
      - zemo 6y ago
        a lot of other use cases are interested in using CRDTs for complex mutations with a relatively small number of users. Most collaborative editing sessions will be a small handful of users. Our use cases are things more like "three thousand people are presented with a multiple-choice question simultaneously and answer it simultaneously and we have to show the results on an xbox and the entire thing has to happen in under 15 seconds". We mostly just use the standard g-counter and pn-counter types. We have a thing that's like ... a high score list for a trivia game that doesn't have a well known type (it's kinda like ... having a zset where only the top N items in the zset are replicated) and a CRDT implementation of a ring buffer of strings for audience comments in ... Quiplash 2, iirc. I'm a bit tied up since we have a new pack coming out October 15th, but I might have time to write some stuff up after that.
aazaa 6y ago
The video linked in the first sentence is well worth the time to understand the background. https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw
arendtio 6y ago
I wonder why OT is restricted to a central server. In 2016/2017 I wrote a Progressive Web App (PWA) for myself which uses an algorithm which probably fits the category of OT. It uses a WebDAV server for synchronization between devices. Yes, this is a centralized server, but when some super slow & dumb WebDAV server can serve this purpose, it should probably be possible to build it on top of S3, a blockchain or something federated. My biggest issues at the time were around CORS as with a PWA you can't simply use every server the user enters, as the same-origin-policy keeps getting in your way.
- jlokier 6y ago
  OT isn't restricted to one server. Any time you see mention of "a server", you can in fact replace it with "a synchronised collection of servers acting as one". OT involves logic on the server, not just storage, so it's not really OT as generally meant, if using S3 and a collection of peer clients only running client logic. S3 doesn't have enough interesting logic for that. However, if you try the thought experiment of stretching "a synchronised collection of servers" to be all of the peers, no S3 even required, and then do OT with that, you can! The result behaves exactly like OT in terms of things like document editing, conflict resolution and history garbage collection, rather than behaving like a CRDT. It has different timing and reliability characteristics from single-server OT though. Those characteristics depend on how the virtual server is implemented on top of the synchronised peers, and especially how it implements peers coming and going. If that sounds like OT-on-p2p has similarities to CRDT-on-p2p - they do, and they are not the same. Roughly speaking, CRDT-on-p2p has lower latency relaying updates between interested peers, because it doesn't need to globally synchronise. However with some fancy techniques you can make OT-on-p2p fast most of the time as well, and retain some of the OT benefits. Those two behave differently but there are some common characteristics. Once you have the cluster idea, it's not out of the question to mix and match bits of OT, CRDT and other kinds of Distributed Transaction on a per-operation basis for different ops on the same data, depending on the characteristics you want them to have. There are many trade-offs in the characteristics. If you squint a lot, that's sort of, kind of, what realtime network games do implicitly, without a clear theory underlying it. They also add predictions and interpolations.
clarkmoody 6y ago
[CRDTs] would let us write software that treats users as digital citizens, not as digital serfs Amen, brother.
yavi 6y ago
If you're interested in building collaborative apps but not the architectural overhead of implementing CRDTs I'd recommend checking out roomservice.dev [1]. They've begun to power some other collaborative apps such as Tella.tv [2] - realtime browser-based video editing. [1] https://roomservice.dev https://roomservice.dev [2] https://news.ycombinator.com/item?id=24158509 https://news.ycombinator.com/item?id=24158509 Disclaimer: I've invested in roomservice.dev (and very excited about what they're building!). No affiliation with Tella.
- rememberlenny 6y ago
  +1 Roomservice. CRDT as a service.
lpage 6y ago
The three most recent HN discussions on CRDTs are all worth perusing. [1] is an excellent tutorial that assumes no initial familiarity with CRDTs or the math that underpins them. It walks you through both the formalisms and the implementation, which is pretty key to understanding why making real-world CRDTs flexible enough to handle things like rich text editing is hard. [2] is a talk that goes more in-depth on the hard parts [3] goes deeper on OT vs. CRDT It's worth noting that many of the CRDT discussions focus on collaborative text editing. That's a really hard problem. CRDTs are (and have been for some time) a useful primitive for building distributed systems. [1] https://news.ycombinator.com/item?id=23737639 https://news.ycombinator.com/item?id=23737639 [2] https://news.ycombinator.com/item?id=23802208 https://news.ycombinator.com/item?id=23802208 [3] https://news.ycombinator.com/item?id=22039950 https://news.ycombinator.com/item?id=22039950
- sashachepurnoi 6y ago
  Thank you for the links!
- regulation_d 6y ago
  Perhaps also of interest is Raph Levien's retrospective on the choice of CRDT as the collab technology for Xi. https://news.ycombinator.com/item?id=19886883 https://news.ycombinator.com/item?id=19886883
- yen223 6y ago
  Adding to the list, I found this article to be one of the more approachable introduction to CRDTs in general: https://news.ycombinator.com/item?id=17221221 https://news.ycombinator.com/item?id=17221221
rsync 6y ago
"It was a general purpose medium (like paper). Unlike a lot of other tools, it doesn’t force you into its own workflow. You could use it to do anything from plan holidays, make a wiki, play D&D with your friends, schedule a meeting, etc." So, sort of like email ?
Splizard 6y ago
No, peer2peer lockstep is the future. No central server, no speed penalty. No storage penalty. Has been used in RTS games to synchronize 1000s of units across low-bandwidth connections. Input may be delayed by latency which can be mitigated with client-side prediction. Cosmic bit-shifts & indeterminism can be a challenge in longer sessions but peers can sync with eachother when there is an OOS.
- iamwil 6y ago
  Do you have links that would tell me more about peer2peer lockstep?
  - just-ok 6y ago
    As the parent commenter mentioned, this technique comes from RTS games, so you could start here: https://www.gamasutra.com/view/feature/131503/1500_archers_on_a_288_network_.php https://www.gamasutra.com/view/feature/131503/1500_archers_o...
    - iamwil 6y ago
      much thanks
- onionjake 6y ago
  Usually in games you have some sort of mechanism for determining what is the 'truth' in terms of game state. I agree that if everyone is online while editing or only briefly offline then what you suggest would probably be much better. If someone was offline for long periods of time and made extensive edits they would essentially have to be discarded. I think in practice what you would do (if your use case allowed it) is use CRDTs, but periodically checkpoint and trim them when you know everyone has synced. That gives you very similar properties to the video game world and still has the features of not losing peoples edits when they make them offline.
alangibson 6y ago
Anyone wanting more info on CRDTs can check out the index I'm maintaining at https://github.com/alangibson/awesome-crdt https://github.com/alangibson/awesome-crdt
natural20s 6y ago
Ahhhh Google Wave. I was an early adopter and shed a tear when it went away. The closest I've felt to that product is Slack but find Slack too noisy. With Wave I felt like I was IN my work not in a "sidebar" application that was pulling my attention from my work. I suppose there were so many ways to use Wave and so many ways to use Slack that your experience could be completely different than mine. But RIP Google Wave.
- hughw 6y ago
  I just never thought email needed fixing, and I suspected "worse is better" [1] would apply to Wave adoption. [1] https://en.wikipedia.org/wiki/Worse_is_better https://en.wikipedia.org/wiki/Worse_is_better
  - TillE 6y ago
    Nobody uses email anymore! It's a last resort. If properly nurtured, Google Wave easily could have become Slack and more. It was pointing in that direction.
    - rhizome 6y ago
      Yes, nobody uses email anymore. That's why 99% of websites have an email signup blocker for discounts, or a newsletter, or just for the heck of it. But they do want that email address.
basicplus2 6y ago
CRDTs (Conflict-Free Replicated data types)
ffhhj 6y ago
I'm looking for a solution to implement collaborative editing in my visual programming node editor. Are CRDTs useful in this case?
anne_biene 6y ago
It is wonderful to see so much enthusiasm about this technology. I have been working on CRDTs since 2012 and it has been quite a ride. For those looking for more information, have a look at the information collected at http://crdt.tech/ http://crdt.tech/ (Disclaimer: I am involved, though Martin did the bulk load of the work.) If you are into CRDTs for collaborative gaming, we are looking for partners and investors: https://concordant.io https://concordant.io (Disclaimer: I am technical advisor in its team.)
jakobmartz3 6y ago
are they tho
tpurves 6y ago
For all those wondering. CRDTs appear to be unrelated to some revival in Cathode Ray Tubes.
deepsun 6y ago
Are there any other applications or examples of CRDT not involving text editing?
corytheboyd 6y ago
I'm going to come clean, I am a shitty software engineer. I'd like to have things like CRDTs under my radar to pull from when architecting technical solutions. But I don't. I have been coddled by the bullshit of "just-good-enough" web development for nearly a decade, and I feel like I will be haunted by it forever at this point. I WANT to employ mathematically proven solutions, but not only has it been 10+ years since studying computer science (and with it, the relevant mathematics) but I never even graduated. So here I am, another under-educated over-paid GED holding Rails engineer putting together shit solutions I know will eventually leak. So, having said all of that, is there hope for adding things like this to my toolbelt? And where do I even start? I feel like going back to school full-time is out of the question, because I have a life now. Maybe online classes? I'm curious to hear thoughts from people who maybe came from a similar pit of despair, or otherwise understand what I am talking about. It's just... sad to know enough that I produce less than optimal work but don't know enough to confidently prevent it from happening over and over and over again. Is this just the profession I have locked myself into?
- rememberlenny 6y ago
  Check out http://www.roomservice.dev http://www.roomservice.dev Turns your front end app multiplayer with a library. They manage the hard part and give you a simple API to get the benefits of realtime/syncing/diffing.
  - mentat 6y ago
    > The major downside of having an “always syncable” data structure is that it gets really big, really quick Perhaps it would be prudent to read the actual article before tossing off this sort of comment since it's indeed the whole point?
    - btilly 6y ago
      Normally I would downvote a comment that amounts to "read the article", except that this one is entirely on point. One of the classic problems was size and performance. However both problems have now disappeared. Operations are `O(log(n))` and the size overhead is a factor of 1.5-2.0. That's quite workable.
mrfusion 6y ago
CRDTs?
rw 6y ago
Operational Transformation and Conflict-Free Replicated Datatypes are very different from each other. As the author explains, OT relies on some ordering of system events, and CRDTs don't. That means CRDTs need to be commutative (and probably associative), and OT doesn't. So, OT is less scalable but more powerful, and CRDTs are more scalable but less powerful (in theory). It's sort of like comparing Paxos/Raft to Bittorrent. (I am not an expert on OT.)
AnthonBerg 6y ago
CRDTs just are. Following the golden rule, I always post a link to a series of papers comparing the theoretical properties of CRDTs and OT – here's the latest one: Real Differences between OT and CRDT under a General Transformation Framework for Consistency Maintenance in Co-Editors Proceedings of the ACM on Human-Computer Interaction 2020 Chengzheng Sun, David Sun, Agustina Ng, Weiwei Cai, Bryden Cho It’s an evolutionary series, here’s the rest I believe: https://arxiv.org/search/cs?query=Sun%2C+Chengzheng&searchtype=author&abstracts=show&order=-announced_date_first&size=50 https://arxiv.org/search/cs?query=Sun%2C+Chengzheng&searchty...
RileyJames 6y ago
>>> Philosophically, if I modify a google doc my computer is asking Google for permission to edit the file. (You can tell because if google’s servers say no, I lose my changes.) In comparison, if I git push to github, I’m only notifying github about the change to my code. My repository is mine. I own all the bits, and all the hardware that houses them. This is how I want all my software to work. I also long for this future. I want all software to work in this manner. Interesting to know how CRDTs are enabling this, or how the limitations of OTs have restricted development of these tools (although git and GitHub exist regardless)
nukemandan 6y ago
Gotta say, a link towards the end of this article is really really good: https://www.inkandswitch.com/local-first.html https://www.inkandswitch.com/local-first.html Referenced as a reason why CRDTs are a good way to enable this.
durgag 6y ago
I think CRDTs will play a bigger role in future. We built a multi-model (KV, Docs, Graphs, Search) realtime database service leveraging CRDTs underneath. If anyone interested, they can read more about the tech here...https://www.macrometa.co/technology https://www.macrometa.co/technology
cutler 6y ago
Please include the expanded version of your acronym in post titles. Not everyone knows what you're talking about.
xyproto 6y ago
When sick, listen to the doctor. Don't listen to the carpenter. IMO, when looking for predictions of the future, listen to the ones that have a track record of accurate predictions.
- CamperBob2 6y ago
  That leaves you vulnerable to selection bias, of course... the best example (IMHO) being the Wall Street "binary search" stock prediction scam.
  - xyproto 6y ago
    Yes, maybe it's better formulated as "don't listen to predictions from people with a record of inaccurate predictions".
    - xpe 6y ago
      This is an interesting set of questions. To some extent, I see the value in "don't listen to predictions from people with a record of inaccurate predictions". On the other hand, people who make a lot of inaccurate predictions are, at least, taking a chance by saying out loud what they are thinking. They know their predictions might be wrong, and hopefully they learn and update their methods along the way. It is a nice way to grow. Back in my Austin road cycling days, there was an amazingly talented junior rider who had a reputation for crashing hard and often. Some of us wondered how many pieces his frame could be split into. He survived the crashes, best I can tell. I'm pretty sure his confidence, resilience, and bike handling skills got better with every crash. Pushing the limits and being wrong in these kinds of situations may not be everyone's style, but it can work.
      - xyproto 6y ago
        Well, then I would not follow his advice if I didn't want to crash while riding a bike.
anilgulecha 6y ago
Collaboration is the killer app of the next gen of software. What we need is a community set of peer relay nodes, on top of which data structures can be synced. Infra companies are well setup to provide this firebase like store layer on top, but for any generic data structures (lists, dicts, array, etc) With this, any saas application is at a disadvantage, because data is no longer tied to the application!
kn8 6y ago
I recently blogged about using CRDTs in building privacy focused software, e.g. how would one approach building an end-to-end encrypted Google Docs: https://www.kn8.lt/blog/building-privacy-focused-collaborative-software/ https://www.kn8.lt/blog/building-privacy-focused-collaborati... The nice thing about CRDTs is that each individual message can be end-to-end encrypted (like WhatsApp messages), and then re-merged by all the clients locally. A local-first database with such an encrypted sync property would would be amazing for building lots of apps with the ability to sync data between users or between your devices seamlessly. The challenge I ran into my initial experiments is that CRDTs need to be compacted/merged in various ways to stay efficient, but encryption gets in the way of that a little when considering server backups / high availability.
erichanson 6y ago
Has anybody seen any work where CRDTs get insight into conflict resolution using the underlying grammar of whatever text is being written (aka English, Javascript, regex, etc.)? Seems like the conflict resolution could do a better job if it knew the EBNF of the text that was being edited. Also, any prior art on CRDTs over relational data? I suppose each single field would potentially be an "editable space", but on a long document (say a Javascript code block), updating the whole thing in the db by overwriting it with each edit would not be very efficient. Seems like there could be a datatype that was a little smarter than "text", that could handle more granular updates, that implemented a CRDT index under the hood? I'm working on a VCS for relational data [1] which is more on the not-so-realtime-collaborative-editing end of the spectrum, but would really like to figure out how to handle real-time collaborative editing in this space. Maybe over WebRTC? I found a little bit of prior art w.r.t. CRDT over WebRTC. [2] [1]: https://github.com/aquametalabs/aquameta/tree/master/src/pg-extension/bundle https://github.com/aquametalabs/aquameta/tree/master/src/pg-... [2]: https://github.com/mattkrick/rich https://github.com/mattkrick/rich
avocade 6y ago
Google Wave is such a bitter sweet memory for me still. Such a great vision, such a great team. Such a sad company.

1181 points by lewisjoe 6y ago

>I’m no longer convinced OT - and all the work I’ve done on it - will still be around. I feel really sad about that. Don't be sad. What you did was a huge inspiration to me and I think a lot of people. It showed the possibilities even if it wasn't "optimal". Commenting here in hope you'll see it. I skim to read most things, I only completed reading this article because I noticed 'I worked on Google Wave'.

stephc_int13 6y ago

When dealing with this type of discussion I always try to remember that making design decisions is a tradeoff, an arbitrage highly dependent on your knowledge of the field, but also context and taste. Believing there is a silver bullet is a fool errand. From what I've read about CRDTs, it seems difficult to escape the overengineering trap when dealing with them.

tabtab 6y ago
I tend to agree. Each team, project, and organization has different needs, preferences, and cultures. One-size-fits-all is a really tall order. I believe it's better to focus on kits of parts--API's and/or self-contained functions--that can be combined or ignored as needed, along with a variety of reference application samples. Having lots of ways to easily filter and sort content is also very useful. For example, filtering and/or sorting annotations by person, group, date, content (sub-strings) is very useful. A query-by-example kind of interface is nice for this.

bigfish24 6y ago

Great summary. CRDTs are a better fit for generalized data. Having previously worked on an OT system, the central server stickiness and merge complexity simply did not scale. There are trade-offs with CRDTs, especially metadata, but as the post mentions compression techniques are far more solvable in real-world scenarios than a fundamental performance bottleneck at the core.

macintux 6y ago

The title sounds like it could be fanboy clickbait but it’s actually a thoughtful look at how far CRDTs have come from the viewpoint of an expert and skeptic. A good read.

taeric 6y ago

I hate that I am skeptical on this. I suspect wave just left that bad of a taste behind. So much hubris in what was claimed to be possible. The ideas do look nice. And I suspect it has gotten farther than I give credit. However, sequencing the edits of independent actors is likely not something you will solve with a data structure. Take the example of a doc getting overwhelmed. Let's say you can make it so that you don't have a server to coordinate. Is it realistic to think hundreds of people can edit a document in real time at the same time and come up with something coherent? Best I can currently imagine is it works if they are editing hundreds of pages. But, that is back to the basic wiki structure working fine. So, help me fix my imagination. Why is this the future?

archagon 6y ago
In the case of a text document, concurrent edits form branches of a tree in many string CRDTs: http://archagon.net/blog/2018/03/24/data-laced-with-history/ http://archagon.net/blog/2018/03/24/data-laced-with-history/ So yes, hundreds of people can edit a string and produce a coherent result at the end. Contiguous runs of characters will stick together and interleave with concurrent edits.
- omgtehlion 6y ago
  I upvote for the link alone. This article (data-laced-with-history) is the best source if you are starting your journey into CRDTs.
- deegles 6y ago
  What if the document starts empty and syncing doesn't happen until everyone presses submit? Will it CRDTs produce a valid document? Yes. Will it make any sense? Who knows. I think that's what OP is getting at.
  - archagon 6y ago
    I read it as a question regarding OT vs. CRDTs, which I believe would produce similar results even under heavy concurrency. In terms of larger edits or refactors, you’d probably need to do something else, e.g. lock the document or section, unshare the document, use some sort of higher-level CRDT that ships your changes atomically and forces a manual merge on concurrent edits, etc. None of these necessarily require a central server, though they may require an active session between participants. I should also note that even if you use regular merge, and the end state of a text document is a complete mess after a refactor + concurrent edits, there’s enough data in the tree to simply pull out any concurrent contributions. They could then be reapplied manually if needed. Perhaps the app could even notice this automatically and provide an optional UI for this process. Similarly, it would be possible for the concurrent editors to remove the refactor edits and thus “fork” their document.

SirensOfTitan 6y ago

So CRDTs are the future, but what about today for real, production products? I'm just about to really dive into collaborative editing features for our product, and OT still seems to me to be a much safer bet unless you're dealing with a more obscure environment.

omgtehlion 6y ago
Yes, starting with OT looks easy. You can make 99% work in almost no time. But the last 1% will bite you in the rear really hard... Actually, CRDT is not a single data structure or even algorithm. It is a term for several families of data structures and different algorithms on them. If your task is not editing text, you may find a simple and already implemented CRDT for your case.
toomim 6y ago
> So CRDTs are the future, but what about today for real, production products? Try Y.js: https://github.com/yjs/yjs https://github.com/yjs/yjs

crawshaw 6y ago

I have been consistently at odds with myself comparing CRDTs vs. OT. One the one hand, CRDTs have a nicer core formalism. On the other hand, OT works, and is closer to the actual driving events of text editing. The core argument of this article: that CRDTs now work and distributed is better than centralized I question. I certainly want more distribution than "everything is run on a google server" but do I really foresee a need for distributing a single document? One server with an optimal OT implementation can probably handle near a million active connections. In practice, that's plenty. Each piece of data having one owner is quite reasonable. There are lots of pieces of data. I remain on the fence for collaborative text editing. Though it's great to see all the work pushing CRDTs forward!

josephg 6y ago
Blog author here. I've been having this conversation with a lot of folks over the last few weeks and I hear you. Does it make sense for us as an opensource community to invest our time and energy making one really good CRDT (with implementations in a few languages). Or does it make sense for us to distribute that energy between a bunch of CRDT and OT implementations, with different performance tradeoffs? My take is that its been hugely beneficial to us all that JSON is a standard, because I can use it from every language, and have confidence that the implementations are fast and good quality. I think we have an opportunity to make that for a good CRDT too. Even if OT would work fine in your architecture, if we have a great, capable, fast CRDT kicking around, it could be a reasonable default for most people. And my claim is that the performance difference between CRDTs and OT is smaller than the difference between high and low quality implementations. (I expect a well written CRDT in wasm will outperform my OT code in javascript.)

omgtehlion 6y ago

CRDTs are hip and cool. But right now I'm trying to find an implementation for desktop software, not some web-framework in-electron. And could not find a concise and correct codebase. All the implementations are: 1. javascript or 2. dependent on their chosen method of synchronisation or 3. incorrect. The result of a two week long search is that I'm reimplementing the stuff myself...

WhatIsDukkha 6y ago
https://github.com/automerge/automerge-rs https://github.com/automerge/automerge-rs I can't speak to its usability as I'm waiting on a 1.0
- omgtehlion 6y ago
  yeah... you better wait for 1.0...
- memorythought 6y ago
  Im one of the authors of this. Right now the code is very unstable as we're tracking the performance branch of the JS implementation. Once the JS version hits 1.0 I'll be putting a bunch of effort into making the API cleaner and more rusty and documenting things. It does work and can actually be used as a backend for the JS implementation if you use the wasm backend we've built. In fact, this is how we have tested it, by compiling to WASM and running the JS test script against it.

csours 6y ago

If you don't use CRDTs, you may be doomed to re-invent them. Reading about them just now I realized that I spent the last year developing a CRDT with LWW and OR characteristics. edit: updated 'you are doomed' to 'you may be doomed'.

xwdv 6y ago

CRDT stands for conflict-free replicated data type.

contravariant 6y ago
Thanks, I had to look it up as well. It's not the first article I read on CRDTs but I definitely didn't recall what they were from just the acronym.

lewisjoe 6y ago

I'm part of the team that makes Zoho Writer (a Google Docs alternative) - https://writer.zoho.com https://writer.zoho.com We went with OT for our real-time syncing of edits in 2010 and a decade later, we are still sticking with OT for reasons I already stated sometime back - https://news.ycombinator.com/item?id=24186883 https://news.ycombinator.com/item?id=24186883 However, in the spirit of "There are no solutions, only trade-offs" CRDTs are absolutely necessary for certain type of syncing - like syncing a set of database nodes. But for systems which already mandate a central server (SaaS/Cloud) and especially for a complex problem like rich-text editing (i.e semantic trees) I still think OT provides better trade-offs than CRDT. I respect Joseph's conviction on CRDTs being the future, so I guess we'll figure this out sometime soon.

cordite 6y ago
What does OT stand for? In the link, OT is aliased to "Operational Transformations"
- dwb 6y ago
  Have you not answered your own question? OT does indeed stand for Operational Transformation. https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation
- mjhirn 6y ago
  "Operation Transformation" = "a system that supports collaboration functionalities by separating the high-level transformation (or integration) control from the low-level transformation functions" Source: OT's Wikipedia article But I felt the same. Never heard of "Operation Transformation" before and both OT and its alias were equally opaque to me.
RangerScience 6y ago
Interesting. I might be adding real-time edit syncing to a hobby project sometime soon. Can you share more about the trade-offs?

blackgirldev 6y ago

Doesn't Redis implement CRDT's in production? https://redislabs.com/blog/diving-into-crdts/ https://redislabs.com/blog/diving-into-crdts/

zegl 6y ago
Riak as well, I've used it very successfully on projects in the past. https://docs.riak.com/riak/kv/latest/developing/data-types/index.html https://docs.riak.com/riak/kv/latest/developing/data-types/i...
dnautics 6y ago
Yes, as does riak. There are plenty of simple crdts and the theory, while recent, has all of it's fundamentals fleshed out. We know what property makes data structures crdts, and how to compose them, and how to prove they are crdts. Currently we are in the "discovery of new crdts" and "engineering and implementing of older crdts reliably" phase, and in some cases "discovering when not to use crdts". The crux of the this issue is that crdts that play nice with human expectations in regards to collaborative document editing are not known, possibly excepting automerge (yjs). As it's a 'softer' concept will no good axioms, there is no solid theory on how to combine the theoretical requirements of crdts with human expectations.
einpoklum 6y ago
It looks like it's basically biasing in favor of some operations over others. In the link they talk about CRDT sets, saying at some point: > 1. Adding wins over deleting. yeah, so, _maybe_ you can remove elements from your set. If you're lucky. I dunno about all that...
- samatman 6y ago
  That's an overly pessimistic way to put it. I think it's more accurate to say that maybe you can remove elements from your set... unless another actor wants them in the set. That's not always the behavior you want. But if it is, it's great.

mhale 6y ago

I'm working on a project with some offline data synchronization needs, but haven't started implementation yet. I've been following CRDTs with interest. I also saw many of the same downsides mentioned in the OP, e.g. bloat (which apparently are being addressed remarkably well). Beyond OT, another approach I've run across that looks very promising is Differential Synchronization[1] by Neil Fraser. While it also relies on a centralized server, it allows for servers to be chained in such a way that seems to address many of the downsides of OT. I wonder why I rarely ever see Differential Synchronization mentioned here on HN? Is it due to lack of awareness or because of use-case fit issues or some fatal flaw I haven't seen? Or something else? [1] https://www.youtube.com/watch?v=S2Hp_1jqpY8 https://www.youtube.com/watch?v=S2Hp_1jqpY8

archagon 6y ago
I devoted some time to Differential Synchronization in my article on CRDTs, if you're interested: http://archagon.net/blog/2018/03/24/data-laced-with-history/#differential-synchronization http://archagon.net/blog/2018/03/24/data-laced-with-history/... My sense is that it's not a particularly flexible approach, and falters under adverse network conditions, even though it feels very tempting.

dustingetz 6y ago

A problem w/ e.g. CRDT datasync in web apps is data security, HTTP resources impose control points where you know "why" the client is asking for e.g. this chunk of social graph, it's /profile/friendlist so the UI can ask for a very controlled and tightly specified data projection for that particular UI and consumed by tightly controlled javascript. Datasync is NOT for scraper bots, arbitrary read patterns or any notion of general access. Immutability makes data control way harder ...

benrbray 6y ago

CRDTs seem very promising, but we still have a long way to go. The most exciting work in this area is being done by Ink&Switch [0]. They have a number of interesting real-world app prototypes based on CRDTs. - An interesting case where CRDTs failed is Xi-editor, where they tried to use CRDTs as the basis for a plugin system [1,2]. - One of the biggest problems with CRDTs is the overhead needed to keep track of the full document history. The automerge [3] project has been working on efficient compression of CRDTs for JSON datatypes. - The idea of monotonic updates is really appealing at first, but I was disappointed when I realized there's no good solution to handle deletions. Tombstones, to me, seem like kind of a hack, albeit a necessary one. Practically, CRDTs aren't the silver bullet they might seem like at first. - Another lesson learned is that when ten people are editing the same paragraph, there's not really a right answer. I think the key to implementing CRDTs is doing it at the correct level of granularity. - ProseMirror intentionally chose NOT to use CRDTs [4]. - Some more good references are [5,6,7] [0] https://inkandswitch.com/ https://inkandswitch.com/ [1] https://github.com/xi-editor/xi-editor/issues/1187#issuecomment-491473599 https://github.com/xi-editor/xi-editor/issues/1187#issuecomm... [2] https://news.ycombinator.com/item?id=19886883 https://news.ycombinator.com/item?id=19886883 [3] https://github.com/automerge https://github.com/automerge and https://github.com/automerge/pushpin https://github.com/automerge/pushpin [4] https://marijnhaverbeke.nl/blog/collaborative-editing.html https://marijnhaverbeke.nl/blog/collaborative-editing.html [5] Kleppmann 2020, "CRDTs: The Hard Parts" https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw with HN Discussion: https://news.ycombinator.com/item?id=23802208 https://news.ycombinator.com/item?id=23802208 [6] Kleppmann 2019, "Interleaving Anomalies in Text Editors" https://martin.kleppmann.com/papers/interleaving-papoc19.pdf https://martin.kleppmann.com/papers/interleaving-papoc19.pdf [7] https://abishov.com/xi-editor/docs/crdt-details.html https://abishov.com/xi-editor/docs/crdt-details.html

yawrp 6y ago
You might enjoy this piece, covers a few of the tradeoffs you mention https://hex.tech/blog/a-pragmatic-approach-to-live-collaboration https://hex.tech/blog/a-pragmatic-approach-to-live-collabora...

deleted 6y ago

[deleted]

stblack 6y ago

It takes over 800 words, and several mentions of the CRDT acronym, before the acronym is expanded for the reader. Don't write like this. Respect your readers and help them comprehend. Expand acronyms as early as you can, ideally at the first mention.

samatman 6y ago
As I tirelessly mention whenever this comes up on HN, which is often: we have a specific technology that is designed precisely for this situation. It's called the link. All an author has to do is link the first instance of an acronym or piece of jargon to some authoritative description, and you get the best of both worlds: readers familiar with e.g. CRDTs[0] can just keep reading, and the rest can click the link and find out. [0]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- thesuitonym 6y ago
  Even better, just use the abbr tag. It's well supported and doesn't rely on an outside source to tell your readers what you're talking about.
  - JeremyBanks 6y ago
    Merely expanding an abbreviation is less useful than explaining it.
  - dllthomas 6y ago
    Better in some ways, worse in others. Better than either, I think, is both.
  - taywrobel 6y ago
    “It’s well supported”, yet on latest mobile Safari, it doesn’t appear to work at all. This w3 demo code does not show me the full name anywhere in the rendered content -https://www.w3schools.com/tags/tryit.asp?filename=tryhtml_abbr_test https://www.w3schools.com/tags/tryit.asp?filename=tryhtml_ab...

santiagobasulto 6y ago

If you're a young technical entrepreneur looking for a 10-100M startup opportunity and with a very interesting technical challenge behind it: Create a collaborative replacement of Jupyter Notebooks. There's already some effort done in JupyterLab fork if you're interested [0], but with no significant advancements. So yes, I agree that CDRTs are indeed a promising endeavor. [0] https://github.com/jupyterlab/jupyterlab/issues/5382 https://github.com/jupyterlab/jupyterlab/issues/5382

darkhorse13 6y ago
Is it really such a good idea to entice young people like this? Shouldn't someone at least be interested and have domain knowledge in CRDTs and real-time collaboration before diving into building a startup like this?
- santiagobasulto 6y ago
  Well, yes, of course. But my comment assumes the person might be interested in the subject.
- TheDong 6y ago
  There's no need to gatekeep building something on already having knowledge. If someone has time and energy and desire, not knowing anything about document editing or CRDTs is not a blocker. Those things can be learned in a week to a month by someone who dedicates time to it. Very few parts of software are inaccessible to someone with basic CS knowledge. It's a great idea for people to try something, regardless of their background, and if they fail but learn something, that's still a fine outcome.
- colesantiago 6y ago
  Worked for Figma, right? I'm sure they fall into the collaborative software space, utilise CRDTs and the founders are less than 40 years of age. This seems like gatekeeping no?
fancy_pantser 6y ago
Domino Data Lab has been around for a while and closed another $43M in funding earlier this year. They have a boatload of tools around collaborative notebooks. They go even further and have data science manager-level dashboards to track the notebooks, their resources, and who is working on what. There are others, but I'm calling this company out specifically because they've shown great traction and I've spent a little time with the cofounders when they were still at a shared incubator space.

hinkley 6y ago

A question that's been in my mind for a while is why Version Control and Collaborative Editing work at such cross purposes with each other when they are essentially solving the same problem? The biggest difference is that one works interactively and the other favors a CLI. Beyond that, how much of the distinction is artificial? In particular I've been wondering about the space between CRDTs and the 'theory of patches' such as we discussed with Pijul the other day. I have a collaborative editing project that's been sitting in my in-box for a long time now because I don't want to write my own edit history code and existing tools don't have enough ability to reason about the contents as structured data. The target audience is technology-averse, so no 'dancing bears' are going to interest them. It's not enough for it to work, it has to work very well.

PaulDavisThe1st 6y ago
line-oriented data formats vs everything else. Why ? Because of "patching theory". If you don't understand the the data describes objects and doesn't have line-by-line semantics, it is hard to get merges correct. Version control works wonders with line-oriented stuff, which covers more or less every programming language in existence. It doesn't do so well with non-line-oriented structured formats such as XML (not sure how JSON or TOML) fits in here). Given that collaborative editing typically works with non-line-oriented data formats, you can see the issue, I think.
- samatman 6y ago
  That's what I refer to as "grammar-aware diffing" in the sibling comment, and it's one of the low-hanging fruits here. Even git allows for pluggable diffing, and doesn't force line orientation. What's missing is the concept of moving something, as distinct from deleting lines/chunks and then inserting lines/chunks which just happen to be the same. This is not a problem which CRDTs have, to put it mildly. I believe pijul understands it as well. A lot of this stuff is right out on the cutting edge, and as it matures it will become practical to connect the edges, such as a CRDT which collaborates with a parser to produce grammar-aware patches which are automagically fed to pijul or something like it. This comes with a host of problems, mostly that we're not used to dealing with a history which has this level of granularity, most of which we don't want to see, most of the time. But they would be nice problems to have.

lisper 6y ago

CRDT = Conflict-Free Replicated Data Types. Think git for data structures instead of directory trees.

deleted 6y ago

[deleted]

yawrp 6y ago

Interesting piece from last week comparing OT, CRDT, and Figma's hybrid approach (good explainers of each too): https://hex.tech/blog/a-pragmatic-approach-to-live-collaboration https://hex.tech/blog/a-pragmatic-approach-to-live-collabora...

zemo 6y ago

I use CRDTs in production at Jackbox for audience functionality and honestly I don't know why the only thing that people talk about when it comes to CRDTs is collaborative text editing. Like, sure, cool, but that's literally a single problem domain and like, Google Docs already exists and works well for the majority of users so how many developers actually need to create a collaborative text editor? CRDTs are an incredibly abstract and versatile concept; collaborative text editing is a tiny problem domain. I would really like to see more writing about CRDTs that is NOT about collaborative text editing.

rhencke 6y ago
Would you consider being the writer of one of those articles?
- zemo 6y ago
  well I really walked into that question huh
  - gen220 6y ago
    I'd read this article. Or, if you'd rather not, can you share some examples of problem domains, that we at home can search for?
    - zemo 6y ago
      a lot of other use cases are interested in using CRDTs for complex mutations with a relatively small number of users. Most collaborative editing sessions will be a small handful of users. Our use cases are things more like "three thousand people are presented with a multiple-choice question simultaneously and answer it simultaneously and we have to show the results on an xbox and the entire thing has to happen in under 15 seconds". We mostly just use the standard g-counter and pn-counter types. We have a thing that's like ... a high score list for a trivia game that doesn't have a well known type (it's kinda like ... having a zset where only the top N items in the zset are replicated) and a CRDT implementation of a ring buffer of strings for audience comments in ... Quiplash 2, iirc. I'm a bit tied up since we have a new pack coming out October 15th, but I might have time to write some stuff up after that.

aazaa 6y ago

The video linked in the first sentence is well worth the time to understand the background. https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw

arendtio 6y ago

I wonder why OT is restricted to a central server. In 2016/2017 I wrote a Progressive Web App (PWA) for myself which uses an algorithm which probably fits the category of OT. It uses a WebDAV server for synchronization between devices. Yes, this is a centralized server, but when some super slow & dumb WebDAV server can serve this purpose, it should probably be possible to build it on top of S3, a blockchain or something federated. My biggest issues at the time were around CORS as with a PWA you can't simply use every server the user enters, as the same-origin-policy keeps getting in your way.

jlokier 6y ago
OT isn't restricted to one server. Any time you see mention of "a server", you can in fact replace it with "a synchronised collection of servers acting as one". OT involves logic on the server, not just storage, so it's not really OT as generally meant, if using S3 and a collection of peer clients only running client logic. S3 doesn't have enough interesting logic for that. However, if you try the thought experiment of stretching "a synchronised collection of servers" to be all of the peers, no S3 even required, and then do OT with that, you can! The result behaves exactly like OT in terms of things like document editing, conflict resolution and history garbage collection, rather than behaving like a CRDT. It has different timing and reliability characteristics from single-server OT though. Those characteristics depend on how the virtual server is implemented on top of the synchronised peers, and especially how it implements peers coming and going. If that sounds like OT-on-p2p has similarities to CRDT-on-p2p - they do, and they are not the same. Roughly speaking, CRDT-on-p2p has lower latency relaying updates between interested peers, because it doesn't need to globally synchronise. However with some fancy techniques you can make OT-on-p2p fast most of the time as well, and retain some of the OT benefits. Those two behave differently but there are some common characteristics. Once you have the cluster idea, it's not out of the question to mix and match bits of OT, CRDT and other kinds of Distributed Transaction on a per-operation basis for different ops on the same data, depending on the characteristics you want them to have. There are many trade-offs in the characteristics. If you squint a lot, that's sort of, kind of, what realtime network games do implicitly, without a clear theory underlying it. They also add predictions and interpolations.

clarkmoody 6y ago

[CRDTs] would let us write software that treats users as digital citizens, not as digital serfs Amen, brother.

yavi 6y ago

If you're interested in building collaborative apps but not the architectural overhead of implementing CRDTs I'd recommend checking out roomservice.dev [1]. They've begun to power some other collaborative apps such as Tella.tv [2] - realtime browser-based video editing. [1] https://roomservice.dev https://roomservice.dev [2] https://news.ycombinator.com/item?id=24158509 https://news.ycombinator.com/item?id=24158509 Disclaimer: I've invested in roomservice.dev (and very excited about what they're building!). No affiliation with Tella.

rememberlenny 6y ago
+1 Roomservice. CRDT as a service.

lpage 6y ago

The three most recent HN discussions on CRDTs are all worth perusing. [1] is an excellent tutorial that assumes no initial familiarity with CRDTs or the math that underpins them. It walks you through both the formalisms and the implementation, which is pretty key to understanding why making real-world CRDTs flexible enough to handle things like rich text editing is hard. [2] is a talk that goes more in-depth on the hard parts [3] goes deeper on OT vs. CRDT It's worth noting that many of the CRDT discussions focus on collaborative text editing. That's a really hard problem. CRDTs are (and have been for some time) a useful primitive for building distributed systems. [1] https://news.ycombinator.com/item?id=23737639 https://news.ycombinator.com/item?id=23737639 [2] https://news.ycombinator.com/item?id=23802208 https://news.ycombinator.com/item?id=23802208 [3] https://news.ycombinator.com/item?id=22039950 https://news.ycombinator.com/item?id=22039950

sashachepurnoi 6y ago
Thank you for the links!
regulation_d 6y ago
Perhaps also of interest is Raph Levien's retrospective on the choice of CRDT as the collab technology for Xi. https://news.ycombinator.com/item?id=19886883 https://news.ycombinator.com/item?id=19886883
yen223 6y ago
Adding to the list, I found this article to be one of the more approachable introduction to CRDTs in general: https://news.ycombinator.com/item?id=17221221 https://news.ycombinator.com/item?id=17221221

rsync 6y ago

"It was a general purpose medium (like paper). Unlike a lot of other tools, it doesn’t force you into its own workflow. You could use it to do anything from plan holidays, make a wiki, play D&D with your friends, schedule a meeting, etc." So, sort of like email ?

Splizard 6y ago

No, peer2peer lockstep is the future. No central server, no speed penalty. No storage penalty. Has been used in RTS games to synchronize 1000s of units across low-bandwidth connections. Input may be delayed by latency which can be mitigated with client-side prediction. Cosmic bit-shifts & indeterminism can be a challenge in longer sessions but peers can sync with eachother when there is an OOS.

iamwil 6y ago
Do you have links that would tell me more about peer2peer lockstep?
- just-ok 6y ago
  As the parent commenter mentioned, this technique comes from RTS games, so you could start here: https://www.gamasutra.com/view/feature/131503/1500_archers_on_a_288_network_.php https://www.gamasutra.com/view/feature/131503/1500_archers_o...
  - iamwil 6y ago
    much thanks
onionjake 6y ago
Usually in games you have some sort of mechanism for determining what is the 'truth' in terms of game state. I agree that if everyone is online while editing or only briefly offline then what you suggest would probably be much better. If someone was offline for long periods of time and made extensive edits they would essentially have to be discarded. I think in practice what you would do (if your use case allowed it) is use CRDTs, but periodically checkpoint and trim them when you know everyone has synced. That gives you very similar properties to the video game world and still has the features of not losing peoples edits when they make them offline.

alangibson 6y ago

Anyone wanting more info on CRDTs can check out the index I'm maintaining at https://github.com/alangibson/awesome-crdt https://github.com/alangibson/awesome-crdt

natural20s 6y ago

Ahhhh Google Wave. I was an early adopter and shed a tear when it went away. The closest I've felt to that product is Slack but find Slack too noisy. With Wave I felt like I was IN my work not in a "sidebar" application that was pulling my attention from my work. I suppose there were so many ways to use Wave and so many ways to use Slack that your experience could be completely different than mine. But RIP Google Wave.

hughw 6y ago
I just never thought email needed fixing, and I suspected "worse is better" [1] would apply to Wave adoption. [1] https://en.wikipedia.org/wiki/Worse_is_better https://en.wikipedia.org/wiki/Worse_is_better
- TillE 6y ago
  Nobody uses email anymore! It's a last resort. If properly nurtured, Google Wave easily could have become Slack and more. It was pointing in that direction.
  - rhizome 6y ago
    Yes, nobody uses email anymore. That's why 99% of websites have an email signup blocker for discounts, or a newsletter, or just for the heck of it. But they do want that email address.

basicplus2 6y ago

CRDTs (Conflict-Free Replicated data types)

ffhhj 6y ago

I'm looking for a solution to implement collaborative editing in my visual programming node editor. Are CRDTs useful in this case?

anne_biene 6y ago

It is wonderful to see so much enthusiasm about this technology. I have been working on CRDTs since 2012 and it has been quite a ride. For those looking for more information, have a look at the information collected at http://crdt.tech/ http://crdt.tech/ (Disclaimer: I am involved, though Martin did the bulk load of the work.) If you are into CRDTs for collaborative gaming, we are looking for partners and investors: https://concordant.io https://concordant.io (Disclaimer: I am technical advisor in its team.)

jakobmartz3 6y ago

are they tho

tpurves 6y ago

For all those wondering. CRDTs appear to be unrelated to some revival in Cathode Ray Tubes.

deepsun 6y ago

Are there any other applications or examples of CRDT not involving text editing?

corytheboyd 6y ago

I'm going to come clean, I am a shitty software engineer. I'd like to have things like CRDTs under my radar to pull from when architecting technical solutions. But I don't. I have been coddled by the bullshit of "just-good-enough" web development for nearly a decade, and I feel like I will be haunted by it forever at this point. I WANT to employ mathematically proven solutions, but not only has it been 10+ years since studying computer science (and with it, the relevant mathematics) but I never even graduated. So here I am, another under-educated over-paid GED holding Rails engineer putting together shit solutions I know will eventually leak. So, having said all of that, is there hope for adding things like this to my toolbelt? And where do I even start? I feel like going back to school full-time is out of the question, because I have a life now. Maybe online classes? I'm curious to hear thoughts from people who maybe came from a similar pit of despair, or otherwise understand what I am talking about. It's just... sad to know enough that I produce less than optimal work but don't know enough to confidently prevent it from happening over and over and over again. Is this just the profession I have locked myself into?

rememberlenny 6y ago
Check out http://www.roomservice.dev http://www.roomservice.dev Turns your front end app multiplayer with a library. They manage the hard part and give you a simple API to get the benefits of realtime/syncing/diffing.
- mentat 6y ago
  > The major downside of having an “always syncable” data structure is that it gets really big, really quick Perhaps it would be prudent to read the actual article before tossing off this sort of comment since it's indeed the whole point?
  - btilly 6y ago
    Normally I would downvote a comment that amounts to "read the article", except that this one is entirely on point. One of the classic problems was size and performance. However both problems have now disappeared. Operations are `O(log(n))` and the size overhead is a factor of 1.5-2.0. That's quite workable.

mrfusion 6y ago

CRDTs?

rw 6y ago

Operational Transformation and Conflict-Free Replicated Datatypes are very different from each other. As the author explains, OT relies on some ordering of system events, and CRDTs don't. That means CRDTs need to be commutative (and probably associative), and OT doesn't. So, OT is less scalable but more powerful, and CRDTs are more scalable but less powerful (in theory). It's sort of like comparing Paxos/Raft to Bittorrent. (I am not an expert on OT.)

AnthonBerg 6y ago

CRDTs just are. Following the golden rule, I always post a link to a series of papers comparing the theoretical properties of CRDTs and OT – here's the latest one: Real Differences between OT and CRDT under a General Transformation Framework for Consistency Maintenance in Co-Editors Proceedings of the ACM on Human-Computer Interaction 2020 Chengzheng Sun, David Sun, Agustina Ng, Weiwei Cai, Bryden Cho It’s an evolutionary series, here’s the rest I believe: https://arxiv.org/search/cs?query=Sun%2C+Chengzheng&searchtype=author&abstracts=show&order=-announced_date_first&size=50 https://arxiv.org/search/cs?query=Sun%2C+Chengzheng&searchty...

RileyJames 6y ago

>>> Philosophically, if I modify a google doc my computer is asking Google for permission to edit the file. (You can tell because if google’s servers say no, I lose my changes.) In comparison, if I git push to github, I’m only notifying github about the change to my code. My repository is mine. I own all the bits, and all the hardware that houses them. This is how I want all my software to work. I also long for this future. I want all software to work in this manner. Interesting to know how CRDTs are enabling this, or how the limitations of OTs have restricted development of these tools (although git and GitHub exist regardless)

nukemandan 6y ago

Gotta say, a link towards the end of this article is really really good: https://www.inkandswitch.com/local-first.html https://www.inkandswitch.com/local-first.html Referenced as a reason why CRDTs are a good way to enable this.

durgag 6y ago

I think CRDTs will play a bigger role in future. We built a multi-model (KV, Docs, Graphs, Search) realtime database service leveraging CRDTs underneath. If anyone interested, they can read more about the tech here...https://www.macrometa.co/technology https://www.macrometa.co/technology

cutler 6y ago

Please include the expanded version of your acronym in post titles. Not everyone knows what you're talking about.

xyproto 6y ago

When sick, listen to the doctor. Don't listen to the carpenter. IMO, when looking for predictions of the future, listen to the ones that have a track record of accurate predictions.

CamperBob2 6y ago
That leaves you vulnerable to selection bias, of course... the best example (IMHO) being the Wall Street "binary search" stock prediction scam.
- xyproto 6y ago
  Yes, maybe it's better formulated as "don't listen to predictions from people with a record of inaccurate predictions".
  - xpe 6y ago
    This is an interesting set of questions. To some extent, I see the value in "don't listen to predictions from people with a record of inaccurate predictions". On the other hand, people who make a lot of inaccurate predictions are, at least, taking a chance by saying out loud what they are thinking. They know their predictions might be wrong, and hopefully they learn and update their methods along the way. It is a nice way to grow. Back in my Austin road cycling days, there was an amazingly talented junior rider who had a reputation for crashing hard and often. Some of us wondered how many pieces his frame could be split into. He survived the crashes, best I can tell. I'm pretty sure his confidence, resilience, and bike handling skills got better with every crash. Pushing the limits and being wrong in these kinds of situations may not be everyone's style, but it can work.
    - xyproto 6y ago
      Well, then I would not follow his advice if I didn't want to crash while riding a bike.

anilgulecha 6y ago

Collaboration is the killer app of the next gen of software. What we need is a community set of peer relay nodes, on top of which data structures can be synced. Infra companies are well setup to provide this firebase like store layer on top, but for any generic data structures (lists, dicts, array, etc) With this, any saas application is at a disadvantage, because data is no longer tied to the application!

kn8 6y ago

I recently blogged about using CRDTs in building privacy focused software, e.g. how would one approach building an end-to-end encrypted Google Docs: https://www.kn8.lt/blog/building-privacy-focused-collaborative-software/ https://www.kn8.lt/blog/building-privacy-focused-collaborati... The nice thing about CRDTs is that each individual message can be end-to-end encrypted (like WhatsApp messages), and then re-merged by all the clients locally. A local-first database with such an encrypted sync property would would be amazing for building lots of apps with the ability to sync data between users or between your devices seamlessly. The challenge I ran into my initial experiments is that CRDTs need to be compacted/merged in various ways to stay efficient, but encryption gets in the way of that a little when considering server backups / high availability.

erichanson 6y ago

Has anybody seen any work where CRDTs get insight into conflict resolution using the underlying grammar of whatever text is being written (aka English, Javascript, regex, etc.)? Seems like the conflict resolution could do a better job if it knew the EBNF of the text that was being edited. Also, any prior art on CRDTs over relational data? I suppose each single field would potentially be an "editable space", but on a long document (say a Javascript code block), updating the whole thing in the db by overwriting it with each edit would not be very efficient. Seems like there could be a datatype that was a little smarter than "text", that could handle more granular updates, that implemented a CRDT index under the hood? I'm working on a VCS for relational data [1] which is more on the not-so-realtime-collaborative-editing end of the spectrum, but would really like to figure out how to handle real-time collaborative editing in this space. Maybe over WebRTC? I found a little bit of prior art w.r.t. CRDT over WebRTC. [2] [1]: https://github.com/aquametalabs/aquameta/tree/master/src/pg-extension/bundle https://github.com/aquametalabs/aquameta/tree/master/src/pg-... [2]: https://github.com/mattkrick/rich https://github.com/mattkrick/rich

avocade 6y ago

Google Wave is such a bitter sweet memory for me still. Such a great vision, such a great team. Such a sad company.