10 ms·

An interactive intro to CRDTs

922 points by jakelazaroff 3y ago

ChrisMarshallNY 3y ago
Thanks, Jake. That's nicely done.
danielvaughn 3y ago
This is absolutely lovely, well done. I've worked with CRDT's a couple times and it's always mind-bending trying to understand the data flow; these interactive demos make it so much clearer.
insanitybit 3y ago
So far this is probably the best "intro to CRDTs for a developer" I've read. I built a product around CRDTs, essentially, and my god was it painful trying to engage with. Showing actual code, explaining that `merge` is the fundamental operation, etc, is really all a developer needs to know IMO. Also, the fact that we always use text editing as the de-facto solution is so weird to me since that problem is both niche and extremely complex. IMO a better example would be something like "Can this person drink alcohol?". Age moves in one direction so it has a simple merge function: def set_age(self, new_age: int): self.age = max(self.age, new_age) A property of this is that if I query your age and if you're 21 I can cache that age forever. You'll only ever be >= 21, after all. If I add new queries that care about you being 25 (for a hotel) I can satisfy the "drinking age" queries from a stale cache and then retrieve the true value (<25) when I need to check if you can book a hotel. This means you can have distributed caches without invalidation logic. A pretty amazing property since cache invalidation is a hugely complex problem and has seriously negative performance/ storage implications. It also means you can drop writes. If my system gets information that a person was 18, but that information is out of date, I can drop that write, and I can do so by examining the cache and viewing stale information, only checking the real value if the cache value is < 18. This whole thing lets you push computation to the edge, drop expensive writes, ignore any cache invalidation logic, cache values forever, potentially answer queries from stale cache values, etc. Anyway, kudos for the writeup. I skimmed the second half but the first half was great and the second half looked legit.
- hmottestad 3y ago
  I really like this somewhat old video by Microsoft https://www.youtube.com/watch?v=oyUHd894w18 https://www.youtube.com/watch?v=oyUHd894w18 it was my first intro to CRDTs.
- whalesalad 3y ago
  I realize this is a straw man argument/example - but it feels hairy to me. So much fuss about age and cache invalidation ... age should not be persisted anywhere. When you make age a calculated property from birthday it is never inaccurate or stale or wrong. "set age" should not be a possible operation in any system imho.
  - insanitybit 3y ago
    Even if you persist a timestamp like 'birth date' into a database it doesn't matter - you can still cache the resulting 'age' calculations as CRDTs. But yes, it is a made up example. Another might be 'first/last observed time' for an IP address.
    - rahkiin 3y ago
      For GDPR it is better to store ‘is legal drinking age’ instead of age or forbid even the birthdate
      - neilellis 3y ago
        Until the legal drinking age changes :-)
        actionfromafar 3y ago
        That’s why you need the SAAS, for compliance and i18n!
        rahkiin 3y ago
        Ideally you only verify at time of purchase and do not care afterwards until next purchase. Bare minimum to hold to laws
deleted 3y ago
[deleted]
endisneigh 3y ago
CRDTs seem like one of these things that are mentioned on here frequently, but I haven't seen that many popular apps that use them. Any examples?
- cdmckay 3y ago
  I believe Notion uses them.
  - endisneigh 3y ago
    really? you have a link to a blog post or something? last I heard they explicitly did not use them.
    - ko_pivot 3y ago
      In production, they don’t. This is evident when two users try to edit the same block at the same time — its last writer wins right now, not merging. They have hired some engineers to work on a CRDT text editor implementation though.
      - jakelazaroff 3y ago
        No idea whether Notion uses CRDTs, but last writer wins is a (naive) strategy for editing text. You can see this in the article — if you edit the LWW Map, for example, even though the keys are merged, each value will be taken from one peer or the other. Once you get to that last “primitive” CRDT — the register holding each map value — updates are atomic. So Notion may be using CRDTs for e.g. the order of blocks in a page, but not (yet?) using them to merge text.
  - auggierose 3y ago
    No, Notion uses OT (operational transform).
  - jitl 3y ago
    Notion doesn't use OT or CRDT in production. Most things are last-write-wins, but we have operations that merge like list re-ordering or permission changes. Today our text is last-write-wins, but we're developing a CRDT solution – if that sounds like something you'd like to work on, shoot me an email jake@makenotion.com or apply https://boards.greenhouse.io/notion/jobs/5602426003 https://boards.greenhouse.io/notion/jobs/5602426003
ooterness 3y ago
For reference: CRDT = Conflict-free Replicated Data Type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- uxp8u61q 3y ago
  It's the first sentence under the heading "What is a CRDT?" in the linked article.
  - aierou 3y ago
    Frankly, it needs to be in the very first sentence of the article. Acronyms Seriously Suck.
totetsu 3y ago
What’s the font on the code snipits? Asking for a friend.
- lelandfe 3y ago
  Cartograph CF: https://connary.com/cartograph.html https://connary.com/cartograph.html
  - deleted 3y ago
    [deleted]
- denvaar 3y ago
  I know, right? I just bought it.
yoyohello13 3y ago
[flagged]
auggierose 3y ago
I swear, HN somehow tracks what I am doing. The last few days I also looked into CRDTs, Automerge, etc, and here we go. Happens so often, it is uncanny. Here is a good overview article, which has pointers to other articles: https://cacm.acm.org/magazines/2022/11/265835-research-for-practice-convergence/abstract https://cacm.acm.org/magazines/2022/11/265835-research-for-p... To me it seems that while state-based CRDTs are easy to understand, operation-based CRDTs are actually what is used in practice. Furthermore, it seems to me the difference between operation-based Automerge, and operational transform (OT) is actually not that big.
- kortex 3y ago
  Have you heard about the Baader-Meinhoff phenomenon before? You will now. https://en.m.wikipedia.org/wiki/Frequency_illusion https://en.m.wikipedia.org/wiki/Frequency_illusion
  - codeulike 3y ago
    I just read about that yesterday
  - dangoodmanUT 3y ago
    I was literally just reading about this >.>
  - strbean 3y ago
    I'd bet there's a dose of this, as well as a bit of the same factors that lead to multiple discover[0]. Seems like conditions may be right for a boom in the application of CRDTs. 0: https://en.wikipedia.org/wiki/Multiple_discovery https://en.wikipedia.org/wiki/Multiple_discovery
  - squidsoup 3y ago
    Nah, it's definitely the Noosphere.
- alephnan 3y ago
  It’s also possible that the cycles of tech employment means programmers are exploring similar topics over time.
angelmm 3y ago
I love interactive introductions to complex topics. They are the best way to learn and consolidate their concepts. Great resource!
kruhft 3y ago
Relevant: http://burton.samograd.ca/Blog/the-eth-papers--2022/eth0004--CRDTS--2018.pdf http://burton.samograd.ca/Blog/the-eth-papers--2022/eth0004-... My take years ago on a simple ERC-20 token (source) for a "SpaceX" (sic, should have been SpaceBit) token. Pretty obvious name though.
braden-lk 3y ago
I’ve built a successful business from a TTRPG campaign manager (LegendKeeper) using CRDTs, specifically the Yjs kind. It’s been great, and the UX of CRDT-powered stuff is excellent. Zero latency, eventually consistent; overall users love the performance and offline capability. That said, there are a lot of trade offs. Some things that are easy in a traditional server-client model become difficult in the local-first context that CRDTs provide. Role based authorization is hard, data model changes must be done additive (never mutative), and knowing what state a client is in when debugging is tough too, without a lot of “full-surveillance”-level tooling. Also with the automatic , bidirectional syncing a lot of CRDT architectures afford you, a bug in production that corrupts data can virally propagate and cause a huge headache. Investor-funded services like Liveblocks are starting to pop up that promise to make this stuff easier, but as an indie I find them expensive; I’m sure they’re a great value for big corps or funded teams though. Rolling my own infrastructure for Yjs has been taxing, but I’ve learned a lot, and have been able to tailor it exactly to my needs.
- paulgb 3y ago
  > knowing for sure what state a user’s client is in when debugging is tough too My team has built an open-source debugger for Yjs that might interest you (docs: https://y-sweet.cloud/advanced/debugger https://y-sweet.cloud/advanced/debugger) You mention the investor-funded services that pop up to make this stuff easier -- our goal with Y-Sweet is to build the same type of DX you’d get from those services, but build it on a fully open-source (MIT) platform with Yjs at the core: https://github.com/drifting-in-space/y-sweet https://github.com/drifting-in-space/y-sweet
  - braden-lk 3y ago
    Ooh hell yeah; excited to check this out.
  - janesconference 3y ago
    A couple of questions about y-sweet, based on the experiences I had with CRDTs: 1) Does the server keeps in memory the "active" documents? In other words, does the server need to open a document and keep it in RAM while clients are connected to it (I assume there's a websocket connection somewhere in the client that keeps it hot)? Or is the server stateless - just connects to the store when needed? I found the latter very hard to do. 2) Does the client persist entries using indexeddb? If yes, does opening many tabs cause redundant writes as they all sync with the server? If not, does the client need to fully re-sync with the server anytime it wakes up? 3) Is it possible to observe updates on the client as they come? One of the major use cases of CRDTs is to index data on the client - then you can have a dumb server that just syncs data between clients and a smart client that does search, graphs, visualizations etc. on the data it receives. To do that, the client needs to observe updates one by one and process them to create secondary indexes. Is it possible to do with y-sweet without forking its source code? I remember getting updates yn Y.js being quite inefficient as you need to replay them all or something similar, but that was a couple of years ago.
matlin 3y ago
Evan Wallace (co-founder of Figma) has one of the best visualizations of CRDTs in action https://madebyevan.com/algos/crdt-fractional-indexing/ https://madebyevan.com/algos/crdt-fractional-indexing/ In practice, most apps will only need Last-Writer-Wins registers and not the more complicated sequence CRDT's that you find in Y.js and Automerge. We've built a auto-syncing database that uses CRDTs under the hood but never exposes them through the API. So if you want all of the benefits of CRDTs e.g. offline-first user experience, checkout our project, Triplit!
- danielvaughn 3y ago
  Yep. I figured this out the hard way. Spent a year or so investigating CRDTs before I came across Figma's blog post and realized they fit my use case exactly, and I really didn't need to bang my head against the desk for so long because the solution actually isn't so bad for tree-based editing.
- jakelazaroff 3y ago
  Author here — Evan Wallace's visualizations were a big inspiration!
- AlexErrant 3y ago
  Dumb question time - why didn't/don't you build Triplit on cr-sqlite? I'm guessing cr-sqlite wasn't on your radar when you started the company, but now that it exists... it would give you joins and access to the whole SQLite ecosystem.
  - matlin 3y ago
    Not a dumb question at all! We're aware of cr-sqlite and I've talked to the author, Matt, a few times. Short answer: SQLite has serious shortcomings when it comes to reactivity and we think we can be as fast as SQLite for the application-type queries we aim to support. The long answer would be about supporting all of features we don't need in SQLite and all of the quirks that come with it like having null as a primary key[1]. We also recently came up with a relational-style querying system without joins! https://twitter.com/triplit_dev/status/1707509447789043760 https://twitter.com/triplit_dev/status/1707509447789043760 [1] https://twitter.com/tantaman/status/1702677401291903116 https://twitter.com/tantaman/status/1702677401291903116
bafe 3y ago
Thank you, very cool work. A small note: the first example doesn't work on mobile devices. If I drag, it will just scroll the page instead of drawing
splashdown5 3y ago
We used CRDTs to build Pennant notebooks (think Jupyter Notebooks with collaborative Google Docs features https://pennant-notebook.github.io/ https://pennant-notebook.github.io/). Getting Yjs to behave for a multi-editor environment took some doing. I highly recommend building your own interface/library for interacting with Yjs and never touching Yjs directly in React itself. The state management and event handler cascade can be incredibly fussy if you don't have a good handle on the whole system. We've found most multi-user apps running over websocket experience significant degradation in performance in the high teen and low twenties. Beyond that we were able to update nested CRDTs and all presence/user data in one connection with the backend. TipTap has a great backend called HocusPocus with well documented API. Y-websocket backend is already quite good but the support for user tokens isn't there natively. We were actually able to be backend provider agnostic for well into the project. It's a fun ecosystem.
- aboodman 3y ago
  High teen and low twenty ... whats? Users on a single document?
zubairq 3y ago
One of the best CRDT tutorials I have tried, well done!
rahimnathwani 3y ago
I love that, on a phone with multi-touch, you can draw on both canvases at the same time.
jimmySixDOF 3y ago
Big shout out to tldraw and whatever they do under the hood to keep it as lightweight and open to integrations - it just handles a tonne of content in group sessions without complaining somehow it's like the perfect mix of simplicity and power features.
thoughtlede 3y ago
I have studied CRDTs at a deeper level for a few weeks and implemented several small prototypes. They are fascinating. As an eventual consistency model for data management, CRDT inspired techniques (op-based or state-based) are useful. However, for building user-facing applications with CRDTs, their importance is unclear. The question with CRDTs and local-first paradigms has always been the pressing need (or the lack thereof). The only one plausible 'need' that CRDTs serve is real-time collaboration and that too with a squinting eye. Real-time collaboration support translates, in practice, to text-editing and picture-editing collaboration. Google docs and the ilk have solved that problem (using central solutions). A CRDT-inspired central-solution like Figma is inspiring, and maybe that's the only place CRDTs fit in their survival quest when combating against central-solutions. The rest of the claimed advantages seem to not withstand the test of times. This articles talks about 7 features of CRDTs [1]. Fast: Things are already fast with central solutions. Multi-device: There is multi-device support with almost all solutions (if you decouple the real-time collaboration aspect). Offline: It's rare, at least in first world countries, to be in a need for offline access (except maybe in airplanes). Longevity: As can be seen from another comment here, longevity is actually a problem with CRDTs because data model updates are not easy. Privacy: With BYOK encryption pattern, privacy is not as much an issue. User control: Even with CRDTs, user is not in control of their data - other peers can mess with your data. [1] https://www.inkandswitch.com/local-first/ https://www.inkandswitch.com/local-first/
- ochiba 3y ago
  I agree. We had similar conclusions around the implementation of PowerSync (sync engine enabling offline-first applications). Instead of CRDTs we went with the architecture of a central server authority and a form of server reconciliation [1] for consistency. [1] https://www.gabrielgambetta.com/client-side-prediction-server-reconciliation.html#server-reconciliation https://www.gabrielgambetta.com/client-side-prediction-serve...
- jakelazaroff 3y ago
  Author here! I think if you're just concerned with efficiency (speed/low overhead/etc) centralized solutions will always beat decentralized ones. The key advantage you can get with CRDTs — and, more generally, decentralized applications — is stability. By which I mean: Figma and Google Docs are great, but they can go out of business or delete your account or up their prices, and everything you've poured your time and energy into making just vanishes. It's not just this way for collaboration software. Servers make everything more brittle. A few years ago, I tried to restore every website I've ever made. Static files were easy, things that relied on old versions of server-side languages were harder and anything stored on a server or in a database was just gone. That sucks. I want us to be able to keep our memories forever, not lose them because we stopped paying a hosting bill.
infogulch 3y ago
Martin Kleppmann gave a great talk about text editing CRDTs at Strange Loop last month: https://www.youtube.com/watch?v=Mr0a5KyD6BU https://www.youtube.com/watch?v=Mr0a5KyD6BU | HN Submission: https://news.ycombinator.com/item?id=37770541 https://news.ycombinator.com/item?id=37770541
rishabhkaul1 3y ago
Partykit is a nice open source tool that is trying to make this stuff easier around creating multiplayer applications https://github.com/partykit/partykit https://github.com/partykit/partykit - built by ex core react team / cloudflare engineer
deleted 3y ago
[deleted]
raybb 3y ago
Seems like your blog isn't working on Mastodon right now? https://mstdn.social/@blog@jakelazaroff.com https://mstdn.social/@blog@jakelazaroff.com
- jakelazaroff 3y ago
  Hm odd, it works on mastodon.social — https://mastodon.social/@blog@jakelazaroff.com https://mastodon.social/@blog@jakelazaroff.com Will look into it, thanks!
tgsovlerkhgsel 3y ago
"Conflict-free Replicated Data Type", if you don't want to have to read through an entire page of text before knowing what the article is about.
nwroot 3y ago
Colors are horrible on this page
dangoodmanUT 3y ago
Wow the first CRDT post I actually was engaged with! Kept me interested through the end, and very well written!... is this the fly.io font?
jongjong 3y ago
Something important to mention when discussing CRDTs is that they are particularly suited for scenarios where clients may go offline often and where it makes sense to resolve conflicts automatically. Not every kind of data lends itself well to automatic conflict resolution as the merged state may not be desirable when all parts are constructed independently without real-time collaborative feedback. For example, if I have a field which is "color" and one person writes red and the other writes blue, there is no way to automatically resolve that conflict when they both become reconnected. It's physically impossible since the intent cannot be established without the ability to read the minds of both participants. You can't just merge the letters into the word "reblued" nor can you allow one to completely overwrite the other while letting both participants believe that their change was settled when in fact, only one made it through. Often, it's desirable that both participants must be online and better to show one an error message if they're not so that they are not mislead into thinking that they're actually changing the system state when in fact their change hasn't been persisted. I've worked on realtime systems which don't rely on CRDTs. This was a suitable approach in my case since accuracy of the data was paramount and each section of the data was well isolated from one another and offline editing was not required.
- lelanthran 3y ago
  > For example, if I have a field which is "color" and one person writes red and the other writes blue, there is no way to automatically resolve that conflict when they both become reconnected. It's physically impossible since the intent cannot be established without the ability to read the minds of both participants. You can't just merge the letters into the word "reblued" nor can you allow one to completely overwrite the other while letting both participants believe that their change was settled when in fact, only one made it through. This, for me, is the crux of the issue that I can not understand - a general CRDT library simply cannot work, as the changes are in context of what is being edited. IOW, I cannot think of a situation where conflicts can be resolved automatically. I think it might be best for the application (which does have context) to display the conflicted state (like the way git does), marking it as a conflict and requiring manual intervention to resolve. In this example, perhaps the application can display the field? If the field is displayed as text, then display "Conflict: {[joe:~blue~][bob:~red~]}". If the field is being displayed as a colored element in an image, the conflict must be displayed with (for example) an overlay on the conflicted part as a red-outlined box, with the snippet of both changes to the image displayed on mouse-over, or on click (or similar). It makes no sense, to me, to approach CRDTs as a general mechanism - it'll be a CRDT for text, a different mechanism for rasterised images, another one for vector graphics, another for video, for sound, etc.
wikiwong 3y ago
great article, thanks for sharing!
xmcqdpt2 3y ago
Something I just thought about: On a Last-Write-Wins CRDTs, can I just set my computer's time to like 100 years in the future, and thus make changes that can never be reverted by anyone?
- dgellow 3y ago
  What I’ve been doing for a personal project is that clients use a local id for their events, and the server adds a timestamp and its own id as soon as it receives them. So a client time doesn’t have any influence.
- nsonha 3y ago
  Timestamps are written by server, problem solved.
  - xmcqdpt2 3y ago
    So say I go offline for a day, make a change at 12:00, someone else makes a conflicting change at 18:00, I reconnect at 19:00, my change will take precedence? That seems wrong. Maybe one should take the larger of the server and client times?
    - nsonha 3y ago
      I know nothing about this topic, but the server also has the version id of the last state (that you fetch) before disconnect. Your update can then be placed on top of that version and not some version far in the future when you reconnect.
- jamil7 3y ago
  A lot of implementations would favour something like a lamport clock or counter instead of a timestamp for a few different reasons. You can tamper with it, and it will increment predictably. You don't really need to worry about timestamps if you're only interested in the relative order of the events in the CRDT.
rwoerz 3y ago
I find that "conflict-free" a little overpromising. If two users simulatiously update the same piece of data to different values, then they have still to agree on a common value manually. CRDTs just provide a common interface for automatic synchronization of replicated data and uses metadata (timestamps etc.) to resolve conflicts in a best-effort manner. With CRDTs, you still have to accept that cases may occur where the conflict resolution does not reflect the intersubjective intention of all participating users. Depending on the use case this may work well, e.g., in simultaneous collaborative editing where you can loose just some of you last keystrokes or mouse clicks but less in others like banking applications.

922 points by jakelazaroff 3y ago

Thanks, Jake. That's nicely done.

This is absolutely lovely, well done. I've worked with CRDT's a couple times and it's always mind-bending trying to understand the data flow; these interactive demos make it so much clearer.

insanitybit 3y ago

So far this is probably the best "intro to CRDTs for a developer" I've read. I built a product around CRDTs, essentially, and my god was it painful trying to engage with. Showing actual code, explaining that `merge` is the fundamental operation, etc, is really all a developer needs to know IMO. Also, the fact that we always use text editing as the de-facto solution is so weird to me since that problem is both niche and extremely complex. IMO a better example would be something like "Can this person drink alcohol?". Age moves in one direction so it has a simple merge function: def set_age(self, new_age: int): self.age = max(self.age, new_age) A property of this is that if I query your age and if you're 21 I can cache that age forever. You'll only ever be >= 21, after all. If I add new queries that care about you being 25 (for a hotel) I can satisfy the "drinking age" queries from a stale cache and then retrieve the true value (<25) when I need to check if you can book a hotel. This means you can have distributed caches without invalidation logic. A pretty amazing property since cache invalidation is a hugely complex problem and has seriously negative performance/ storage implications. It also means you can drop writes. If my system gets information that a person was 18, but that information is out of date, I can drop that write, and I can do so by examining the cache and viewing stale information, only checking the real value if the cache value is < 18. This whole thing lets you push computation to the edge, drop expensive writes, ignore any cache invalidation logic, cache values forever, potentially answer queries from stale cache values, etc. Anyway, kudos for the writeup. I skimmed the second half but the first half was great and the second half looked legit.

hmottestad 3y ago
I really like this somewhat old video by Microsoft https://www.youtube.com/watch?v=oyUHd894w18 https://www.youtube.com/watch?v=oyUHd894w18 it was my first intro to CRDTs.
whalesalad 3y ago
I realize this is a straw man argument/example - but it feels hairy to me. So much fuss about age and cache invalidation ... age should not be persisted anywhere. When you make age a calculated property from birthday it is never inaccurate or stale or wrong. "set age" should not be a possible operation in any system imho.
- insanitybit 3y ago
  Even if you persist a timestamp like 'birth date' into a database it doesn't matter - you can still cache the resulting 'age' calculations as CRDTs. But yes, it is a made up example. Another might be 'first/last observed time' for an IP address.
  - rahkiin 3y ago
    For GDPR it is better to store ‘is legal drinking age’ instead of age or forbid even the birthdate
    - neilellis 3y ago
      Until the legal drinking age changes :-)
      - actionfromafar 3y ago
        That’s why you need the SAAS, for compliance and i18n!
      - rahkiin 3y ago
        Ideally you only verify at time of purchase and do not care afterwards until next purchase. Bare minimum to hold to laws

deleted 3y ago

[deleted]

endisneigh 3y ago

CRDTs seem like one of these things that are mentioned on here frequently, but I haven't seen that many popular apps that use them. Any examples?

cdmckay 3y ago
I believe Notion uses them.
- endisneigh 3y ago
  really? you have a link to a blog post or something? last I heard they explicitly did not use them.
  - ko_pivot 3y ago
    In production, they don’t. This is evident when two users try to edit the same block at the same time — its last writer wins right now, not merging. They have hired some engineers to work on a CRDT text editor implementation though.
    - jakelazaroff 3y ago
      No idea whether Notion uses CRDTs, but last writer wins is a (naive) strategy for editing text. You can see this in the article — if you edit the LWW Map, for example, even though the keys are merged, each value will be taken from one peer or the other. Once you get to that last “primitive” CRDT — the register holding each map value — updates are atomic. So Notion may be using CRDTs for e.g. the order of blocks in a page, but not (yet?) using them to merge text.
- auggierose 3y ago
  No, Notion uses OT (operational transform).
- jitl 3y ago
  Notion doesn't use OT or CRDT in production. Most things are last-write-wins, but we have operations that merge like list re-ordering or permission changes. Today our text is last-write-wins, but we're developing a CRDT solution – if that sounds like something you'd like to work on, shoot me an email jake@makenotion.com or apply https://boards.greenhouse.io/notion/jobs/5602426003 https://boards.greenhouse.io/notion/jobs/5602426003

ooterness 3y ago

For reference: CRDT = Conflict-free Replicated Data Type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

uxp8u61q 3y ago
It's the first sentence under the heading "What is a CRDT?" in the linked article.
- aierou 3y ago
  Frankly, it needs to be in the very first sentence of the article. Acronyms Seriously Suck.

totetsu 3y ago

What’s the font on the code snipits? Asking for a friend.

lelandfe 3y ago
Cartograph CF: https://connary.com/cartograph.html https://connary.com/cartograph.html
- deleted 3y ago
  [deleted]
denvaar 3y ago
I know, right? I just bought it.

yoyohello13 3y ago

[flagged]

auggierose 3y ago

I swear, HN somehow tracks what I am doing. The last few days I also looked into CRDTs, Automerge, etc, and here we go. Happens so often, it is uncanny. Here is a good overview article, which has pointers to other articles: https://cacm.acm.org/magazines/2022/11/265835-research-for-practice-convergence/abstract https://cacm.acm.org/magazines/2022/11/265835-research-for-p... To me it seems that while state-based CRDTs are easy to understand, operation-based CRDTs are actually what is used in practice. Furthermore, it seems to me the difference between operation-based Automerge, and operational transform (OT) is actually not that big.

kortex 3y ago
Have you heard about the Baader-Meinhoff phenomenon before? You will now. https://en.m.wikipedia.org/wiki/Frequency_illusion https://en.m.wikipedia.org/wiki/Frequency_illusion
- codeulike 3y ago
  I just read about that yesterday
- dangoodmanUT 3y ago
  I was literally just reading about this >.>
- strbean 3y ago
  I'd bet there's a dose of this, as well as a bit of the same factors that lead to multiple discover[0]. Seems like conditions may be right for a boom in the application of CRDTs. 0: https://en.wikipedia.org/wiki/Multiple_discovery https://en.wikipedia.org/wiki/Multiple_discovery
- squidsoup 3y ago
  Nah, it's definitely the Noosphere.
alephnan 3y ago
It’s also possible that the cycles of tech employment means programmers are exploring similar topics over time.

angelmm 3y ago

I love interactive introductions to complex topics. They are the best way to learn and consolidate their concepts. Great resource!

kruhft 3y ago

Relevant: http://burton.samograd.ca/Blog/the-eth-papers--2022/eth0004--CRDTS--2018.pdf http://burton.samograd.ca/Blog/the-eth-papers--2022/eth0004-... My take years ago on a simple ERC-20 token (source) for a "SpaceX" (sic, should have been SpaceBit) token. Pretty obvious name though.

braden-lk 3y ago

I’ve built a successful business from a TTRPG campaign manager (LegendKeeper) using CRDTs, specifically the Yjs kind. It’s been great, and the UX of CRDT-powered stuff is excellent. Zero latency, eventually consistent; overall users love the performance and offline capability. That said, there are a lot of trade offs. Some things that are easy in a traditional server-client model become difficult in the local-first context that CRDTs provide. Role based authorization is hard, data model changes must be done additive (never mutative), and knowing what state a client is in when debugging is tough too, without a lot of “full-surveillance”-level tooling. Also with the automatic , bidirectional syncing a lot of CRDT architectures afford you, a bug in production that corrupts data can virally propagate and cause a huge headache. Investor-funded services like Liveblocks are starting to pop up that promise to make this stuff easier, but as an indie I find them expensive; I’m sure they’re a great value for big corps or funded teams though. Rolling my own infrastructure for Yjs has been taxing, but I’ve learned a lot, and have been able to tailor it exactly to my needs.

paulgb 3y ago
> knowing for sure what state a user’s client is in when debugging is tough too My team has built an open-source debugger for Yjs that might interest you (docs: https://y-sweet.cloud/advanced/debugger https://y-sweet.cloud/advanced/debugger) You mention the investor-funded services that pop up to make this stuff easier -- our goal with Y-Sweet is to build the same type of DX you’d get from those services, but build it on a fully open-source (MIT) platform with Yjs at the core: https://github.com/drifting-in-space/y-sweet https://github.com/drifting-in-space/y-sweet
- braden-lk 3y ago
  Ooh hell yeah; excited to check this out.
- janesconference 3y ago
  A couple of questions about y-sweet, based on the experiences I had with CRDTs: 1) Does the server keeps in memory the "active" documents? In other words, does the server need to open a document and keep it in RAM while clients are connected to it (I assume there's a websocket connection somewhere in the client that keeps it hot)? Or is the server stateless - just connects to the store when needed? I found the latter very hard to do. 2) Does the client persist entries using indexeddb? If yes, does opening many tabs cause redundant writes as they all sync with the server? If not, does the client need to fully re-sync with the server anytime it wakes up? 3) Is it possible to observe updates on the client as they come? One of the major use cases of CRDTs is to index data on the client - then you can have a dumb server that just syncs data between clients and a smart client that does search, graphs, visualizations etc. on the data it receives. To do that, the client needs to observe updates one by one and process them to create secondary indexes. Is it possible to do with y-sweet without forking its source code? I remember getting updates yn Y.js being quite inefficient as you need to replay them all or something similar, but that was a couple of years ago.

matlin 3y ago

Evan Wallace (co-founder of Figma) has one of the best visualizations of CRDTs in action https://madebyevan.com/algos/crdt-fractional-indexing/ https://madebyevan.com/algos/crdt-fractional-indexing/ In practice, most apps will only need Last-Writer-Wins registers and not the more complicated sequence CRDT's that you find in Y.js and Automerge. We've built a auto-syncing database that uses CRDTs under the hood but never exposes them through the API. So if you want all of the benefits of CRDTs e.g. offline-first user experience, checkout our project, Triplit!

danielvaughn 3y ago
Yep. I figured this out the hard way. Spent a year or so investigating CRDTs before I came across Figma's blog post and realized they fit my use case exactly, and I really didn't need to bang my head against the desk for so long because the solution actually isn't so bad for tree-based editing.
jakelazaroff 3y ago
Author here — Evan Wallace's visualizations were a big inspiration!
AlexErrant 3y ago
Dumb question time - why didn't/don't you build Triplit on cr-sqlite? I'm guessing cr-sqlite wasn't on your radar when you started the company, but now that it exists... it would give you joins and access to the whole SQLite ecosystem.
- matlin 3y ago
  Not a dumb question at all! We're aware of cr-sqlite and I've talked to the author, Matt, a few times. Short answer: SQLite has serious shortcomings when it comes to reactivity and we think we can be as fast as SQLite for the application-type queries we aim to support. The long answer would be about supporting all of features we don't need in SQLite and all of the quirks that come with it like having null as a primary key[1]. We also recently came up with a relational-style querying system without joins! https://twitter.com/triplit_dev/status/1707509447789043760 https://twitter.com/triplit_dev/status/1707509447789043760 [1] https://twitter.com/tantaman/status/1702677401291903116 https://twitter.com/tantaman/status/1702677401291903116

bafe 3y ago

Thank you, very cool work. A small note: the first example doesn't work on mobile devices. If I drag, it will just scroll the page instead of drawing

splashdown5 3y ago

We used CRDTs to build Pennant notebooks (think Jupyter Notebooks with collaborative Google Docs features https://pennant-notebook.github.io/ https://pennant-notebook.github.io/). Getting Yjs to behave for a multi-editor environment took some doing. I highly recommend building your own interface/library for interacting with Yjs and never touching Yjs directly in React itself. The state management and event handler cascade can be incredibly fussy if you don't have a good handle on the whole system. We've found most multi-user apps running over websocket experience significant degradation in performance in the high teen and low twenties. Beyond that we were able to update nested CRDTs and all presence/user data in one connection with the backend. TipTap has a great backend called HocusPocus with well documented API. Y-websocket backend is already quite good but the support for user tokens isn't there natively. We were actually able to be backend provider agnostic for well into the project. It's a fun ecosystem.

aboodman 3y ago
High teen and low twenty ... whats? Users on a single document?

zubairq 3y ago

One of the best CRDT tutorials I have tried, well done!

rahimnathwani 3y ago

I love that, on a phone with multi-touch, you can draw on both canvases at the same time.

jimmySixDOF 3y ago

Big shout out to tldraw and whatever they do under the hood to keep it as lightweight and open to integrations - it just handles a tonne of content in group sessions without complaining somehow it's like the perfect mix of simplicity and power features.

thoughtlede 3y ago

I have studied CRDTs at a deeper level for a few weeks and implemented several small prototypes. They are fascinating. As an eventual consistency model for data management, CRDT inspired techniques (op-based or state-based) are useful. However, for building user-facing applications with CRDTs, their importance is unclear. The question with CRDTs and local-first paradigms has always been the pressing need (or the lack thereof). The only one plausible 'need' that CRDTs serve is real-time collaboration and that too with a squinting eye. Real-time collaboration support translates, in practice, to text-editing and picture-editing collaboration. Google docs and the ilk have solved that problem (using central solutions). A CRDT-inspired central-solution like Figma is inspiring, and maybe that's the only place CRDTs fit in their survival quest when combating against central-solutions. The rest of the claimed advantages seem to not withstand the test of times. This articles talks about 7 features of CRDTs [1]. Fast: Things are already fast with central solutions. Multi-device: There is multi-device support with almost all solutions (if you decouple the real-time collaboration aspect). Offline: It's rare, at least in first world countries, to be in a need for offline access (except maybe in airplanes). Longevity: As can be seen from another comment here, longevity is actually a problem with CRDTs because data model updates are not easy. Privacy: With BYOK encryption pattern, privacy is not as much an issue. User control: Even with CRDTs, user is not in control of their data - other peers can mess with your data. [1] https://www.inkandswitch.com/local-first/ https://www.inkandswitch.com/local-first/

ochiba 3y ago
I agree. We had similar conclusions around the implementation of PowerSync (sync engine enabling offline-first applications). Instead of CRDTs we went with the architecture of a central server authority and a form of server reconciliation [1] for consistency. [1] https://www.gabrielgambetta.com/client-side-prediction-server-reconciliation.html#server-reconciliation https://www.gabrielgambetta.com/client-side-prediction-serve...
jakelazaroff 3y ago
Author here! I think if you're just concerned with efficiency (speed/low overhead/etc) centralized solutions will always beat decentralized ones. The key advantage you can get with CRDTs — and, more generally, decentralized applications — is stability. By which I mean: Figma and Google Docs are great, but they can go out of business or delete your account or up their prices, and everything you've poured your time and energy into making just vanishes. It's not just this way for collaboration software. Servers make everything more brittle. A few years ago, I tried to restore every website I've ever made. Static files were easy, things that relied on old versions of server-side languages were harder and anything stored on a server or in a database was just gone. That sucks. I want us to be able to keep our memories forever, not lose them because we stopped paying a hosting bill.

infogulch 3y ago

Martin Kleppmann gave a great talk about text editing CRDTs at Strange Loop last month: https://www.youtube.com/watch?v=Mr0a5KyD6BU https://www.youtube.com/watch?v=Mr0a5KyD6BU | HN Submission: https://news.ycombinator.com/item?id=37770541 https://news.ycombinator.com/item?id=37770541

rishabhkaul1 3y ago

Partykit is a nice open source tool that is trying to make this stuff easier around creating multiplayer applications https://github.com/partykit/partykit https://github.com/partykit/partykit - built by ex core react team / cloudflare engineer

deleted 3y ago

[deleted]

raybb 3y ago

Seems like your blog isn't working on Mastodon right now? https://mstdn.social/@blog@jakelazaroff.com https://mstdn.social/@blog@jakelazaroff.com

jakelazaroff 3y ago
Hm odd, it works on mastodon.social — https://mastodon.social/@blog@jakelazaroff.com https://mastodon.social/@blog@jakelazaroff.com Will look into it, thanks!

tgsovlerkhgsel 3y ago

"Conflict-free Replicated Data Type", if you don't want to have to read through an entire page of text before knowing what the article is about.

nwroot 3y ago

Colors are horrible on this page

dangoodmanUT 3y ago

Wow the first CRDT post I actually was engaged with! Kept me interested through the end, and very well written!... is this the fly.io font?

jongjong 3y ago

Something important to mention when discussing CRDTs is that they are particularly suited for scenarios where clients may go offline often and where it makes sense to resolve conflicts automatically. Not every kind of data lends itself well to automatic conflict resolution as the merged state may not be desirable when all parts are constructed independently without real-time collaborative feedback. For example, if I have a field which is "color" and one person writes red and the other writes blue, there is no way to automatically resolve that conflict when they both become reconnected. It's physically impossible since the intent cannot be established without the ability to read the minds of both participants. You can't just merge the letters into the word "reblued" nor can you allow one to completely overwrite the other while letting both participants believe that their change was settled when in fact, only one made it through. Often, it's desirable that both participants must be online and better to show one an error message if they're not so that they are not mislead into thinking that they're actually changing the system state when in fact their change hasn't been persisted. I've worked on realtime systems which don't rely on CRDTs. This was a suitable approach in my case since accuracy of the data was paramount and each section of the data was well isolated from one another and offline editing was not required.

lelanthran 3y ago
> For example, if I have a field which is "color" and one person writes red and the other writes blue, there is no way to automatically resolve that conflict when they both become reconnected. It's physically impossible since the intent cannot be established without the ability to read the minds of both participants. You can't just merge the letters into the word "reblued" nor can you allow one to completely overwrite the other while letting both participants believe that their change was settled when in fact, only one made it through. This, for me, is the crux of the issue that I can not understand - a general CRDT library simply cannot work, as the changes are in context of what is being edited. IOW, I cannot think of a situation where conflicts can be resolved automatically. I think it might be best for the application (which does have context) to display the conflicted state (like the way git does), marking it as a conflict and requiring manual intervention to resolve. In this example, perhaps the application can display the field? If the field is displayed as text, then display "Conflict: {[joe:~blue~][bob:~red~]}". If the field is being displayed as a colored element in an image, the conflict must be displayed with (for example) an overlay on the conflicted part as a red-outlined box, with the snippet of both changes to the image displayed on mouse-over, or on click (or similar). It makes no sense, to me, to approach CRDTs as a general mechanism - it'll be a CRDT for text, a different mechanism for rasterised images, another one for vector graphics, another for video, for sound, etc.

wikiwong 3y ago

great article, thanks for sharing!

xmcqdpt2 3y ago

Something I just thought about: On a Last-Write-Wins CRDTs, can I just set my computer's time to like 100 years in the future, and thus make changes that can never be reverted by anyone?

dgellow 3y ago
What I’ve been doing for a personal project is that clients use a local id for their events, and the server adds a timestamp and its own id as soon as it receives them. So a client time doesn’t have any influence.
nsonha 3y ago
Timestamps are written by server, problem solved.
- xmcqdpt2 3y ago
  So say I go offline for a day, make a change at 12:00, someone else makes a conflicting change at 18:00, I reconnect at 19:00, my change will take precedence? That seems wrong. Maybe one should take the larger of the server and client times?
  - nsonha 3y ago
    I know nothing about this topic, but the server also has the version id of the last state (that you fetch) before disconnect. Your update can then be placed on top of that version and not some version far in the future when you reconnect.
jamil7 3y ago
A lot of implementations would favour something like a lamport clock or counter instead of a timestamp for a few different reasons. You can tamper with it, and it will increment predictably. You don't really need to worry about timestamps if you're only interested in the relative order of the events in the CRDT.

rwoerz 3y ago

I find that "conflict-free" a little overpromising. If two users simulatiously update the same piece of data to different values, then they have still to agree on a common value manually. CRDTs just provide a common interface for automatic synchronization of replicated data and uses metadata (timestamps etc.) to resolve conflicts in a best-effort manner. With CRDTs, you still have to accept that cases may occur where the conflict resolution does not reflect the intersubjective intention of all participating users. Depending on the use case this may work well, e.g., in simultaneous collaborative editing where you can loose just some of you last keystrokes or mouse clicks but less in others like banking applications.