4 ms·

Well, two concurrent changes to the same property is basically a race condition and that can't be cleanly resolved in an automated way. You either pick a winner

Well, two concurrent changes to the same property is basically a race condition and that can't be cleanly resolved in an automated way. You either pick a winner or you do manual merging like Git, but I guess in applications of such data structures you don't want to do anything manually.

samwillis 5y ago
Within a string, most CRDTs will keep both changes effectively concatenating them. If you have something like a Int value and need to handle it more gracefully in your application than the arbitrary selection by the CRDT toolkit you can keep it within an array/list and then handle the merging yourself. So it starts off as [10], each user when changing it would delete the value and append a new one. That way if you have two users simultaneously change it, one to [15] and the other to [5]. The resulting synced value would be [15,5], you can then handle how to combine the values yourself (addition, average, etc) in a determinist way. I haven't looked into it but some CRDT toolkits may store Ints by keeping track of changes to it, but the above allows you to do it yourself.
noduerme 5y ago
No, this is not the way. The proper way to handle it is that each client trying to update the property tries to get a write lock on it; that write lock has to wait for any other write lock to complete, and if it can't get a lock it needs to let the client know it failed to update. At a bare minimum this is what has to happen to maintain any kind of data integrity. But by all means, if you think it's basically a race condition any time you have ten clients trying to update the same row in a database and you don't care which one wins, you should be able to write a very compelling and unusual poker website.
- samwillis 5y ago
  The whole point of CRDTs is that they work offline with no central authority and therefore no locks.
  - noduerme 5y ago
    Oh. This is just a local storage thing? Well what's the point of worrying about concurrency at all then? Just FWIW; I'm hostile to this notion because it breaks decades of best practice about data integrity and claims to solve issues that aren't actually issues in real databases; plus the people boosting it seem to not understand anything about concurrency. If it's just a replacement for indexedDB or sqlite or something, well, who cares...
    - samwillis 5y ago
      It's not a replacement for indexedDB or sqlite, and it's not about concurency. It's about merging conflicting changes. This is a good article explaining the concept and implementation of a CRDT: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
    - neoberg 5y ago
      Let's say you are developing a design application (think figma) which works in the browser. You don't want to lock the whole project just because someone needs to change a label somewhere. With CRDTs n people can open and edit the project at the same time and then push their changes and have them merged. Very similar to git. When working with git, you don't lock the file or line you are working on.
- aenario 5y ago
  It's a very narrow use-case of conflict-free data type. Sure if you are willing to wait for however long to get a lock before you can edit something. The main goal of CRDT is for long-split branch such as can happen in federated systems or with offline management. (think git)
  - noduerme 5y ago
    Bad design. Would you ever put something into production that couldn't tell if two people were trying to write the same object at the same time and roll one back?
    - lijogdfljk 5y ago
      Why would you ever put a hyper focused distributed system in a centralized architecture? You're choosing a sledge hammer for a screw. This is a database that can work when you're offline. Your central server has nothing to do with this and is entirely incapable of even working.
    - aenario 5y ago
      You seem to only conceive of the web as "html+JS frontend communicating in real time to some server" We have decades of distributed systems without a central server. Such as git, bit-torrent, Mastodon, Matrix, and the whole web3 mess. It's for these use-case that CRDT helps solve real problems.
- manigandham 5y ago
  You've posted a lot of negative comments but seem to not understand or have any experience with CRDTs. The whole point is that state modifications on the data structure by separate parties can converge to a final representation without any coordination. The math behind it is proven, however turning mathematical set-theory into a usable JSON interface is where the problem occurs. A free-form JSON doc can't be completely supported but these kind of edge-cases around property updates are easily handled by using an array to hold modifications instead. CRDTs even have state-based and operation-based usage models to handle different scenarios, and then there's an entirely separate but parallel tech called operational transforms for other situations. All of this is not only well-studied but widely used in many collaborative applications (eg: Google Docs).
  - mkl 5y ago
    Nitpick: Google Docs uses the server-mediated Operational Transformation (OT), not peer-to-peer CRDTs.
- dboreham 5y ago
  A distributed lock. Amazing.

samwillis 5y ago

Within a string, most CRDTs will keep both changes effectively concatenating them. If you have something like a Int value and need to handle it more gracefully in your application than the arbitrary selection by the CRDT toolkit you can keep it within an array/list and then handle the merging yourself. So it starts off as [10], each user when changing it would delete the value and append a new one. That way if you have two users simultaneously change it, one to [15] and the other to [5]. The resulting synced value would be [15,5], you can then handle how to combine the values yourself (addition, average, etc) in a determinist way. I haven't looked into it but some CRDT toolkits may store Ints by keeping track of changes to it, but the above allows you to do it yourself.

noduerme 5y ago

No, this is not the way. The proper way to handle it is that each client trying to update the property tries to get a write lock on it; that write lock has to wait for any other write lock to complete, and if it can't get a lock it needs to let the client know it failed to update. At a bare minimum this is what has to happen to maintain any kind of data integrity. But by all means, if you think it's basically a race condition any time you have ten clients trying to update the same row in a database and you don't care which one wins, you should be able to write a very compelling and unusual poker website.

samwillis 5y ago
The whole point of CRDTs is that they work offline with no central authority and therefore no locks.
- noduerme 5y ago
  Oh. This is just a local storage thing? Well what's the point of worrying about concurrency at all then? Just FWIW; I'm hostile to this notion because it breaks decades of best practice about data integrity and claims to solve issues that aren't actually issues in real databases; plus the people boosting it seem to not understand anything about concurrency. If it's just a replacement for indexedDB or sqlite or something, well, who cares...
  - samwillis 5y ago
    It's not a replacement for indexedDB or sqlite, and it's not about concurency. It's about merging conflicting changes. This is a good article explaining the concept and implementation of a CRDT: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
  - neoberg 5y ago
    Let's say you are developing a design application (think figma) which works in the browser. You don't want to lock the whole project just because someone needs to change a label somewhere. With CRDTs n people can open and edit the project at the same time and then push their changes and have them merged. Very similar to git. When working with git, you don't lock the file or line you are working on.
aenario 5y ago
It's a very narrow use-case of conflict-free data type. Sure if you are willing to wait for however long to get a lock before you can edit something. The main goal of CRDT is for long-split branch such as can happen in federated systems or with offline management. (think git)
- noduerme 5y ago
  Bad design. Would you ever put something into production that couldn't tell if two people were trying to write the same object at the same time and roll one back?
  - lijogdfljk 5y ago
    Why would you ever put a hyper focused distributed system in a centralized architecture? You're choosing a sledge hammer for a screw. This is a database that can work when you're offline. Your central server has nothing to do with this and is entirely incapable of even working.
  - aenario 5y ago
    You seem to only conceive of the web as "html+JS frontend communicating in real time to some server" We have decades of distributed systems without a central server. Such as git, bit-torrent, Mastodon, Matrix, and the whole web3 mess. It's for these use-case that CRDT helps solve real problems.
manigandham 5y ago
You've posted a lot of negative comments but seem to not understand or have any experience with CRDTs. The whole point is that state modifications on the data structure by separate parties can converge to a final representation without any coordination. The math behind it is proven, however turning mathematical set-theory into a usable JSON interface is where the problem occurs. A free-form JSON doc can't be completely supported but these kind of edge-cases around property updates are easily handled by using an array to hold modifications instead. CRDTs even have state-based and operation-based usage models to handle different scenarios, and then there's an entirely separate but parallel tech called operational transforms for other situations. All of this is not only well-studied but widely used in many collaborative applications (eg: Google Docs).
- mkl 5y ago
  Nitpick: Google Docs uses the server-mediated Operational Transformation (OT), not peer-to-peer CRDTs.
dboreham 5y ago
A distributed lock. Amazing.