16 ms·

A Conflict-Free Replicated JSON Datatype

132 points by DanielRibeiro 10y ago

jackweirdy 10y ago
Can't read the paper - is this an implementation of or just related to CRDTs?
- zbyte64 10y ago
  "The JSON datatype described in this paper is a kind of CRDT"
espadrine 10y ago
> Our principle of not losing input due to concurrent modifications appears reasonable, but as illustrated in Figure 4, it leads to merged document states that may be surprising to application programmers who are more familiar with sequential programs. That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string to a list without having any operation creating a list explicitly. > Moreover, garbage collection (tombstone removal) is required in order to prevent unbounded growth of the datastructure That is always the painful part of a CRDT system. Until that part is done, it cannot really be used in production. That said, previous work on CRDTs give me confidence that it can be implemented with minimal overhead. > In fact, we wrote the LATEX source text of this paper using an experimental collaborative text editor that is based on our implementation of this CRDT. We are making the character-by-character editing trace of this document available as supplemental data of this paper String editing is brushed over in the paper. I'd love to see their implementation. Does anyone know where it all is?
- vidarh 10y ago
  > That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string to a list without having any operation creating a list explicitly. It's hard to see good alternatives there. If you move from a single editor to concurrent edits without very strict ordering guarantees or a transactional system, you will need to deal with conflicts or lose data. Creating output that would be considered invalid unless the application is fixed to explicitly deal with it (or explicitly throw it away) seems quite reasonable.
  - adrianratnapala 10y ago
    For this you would want a type / schema that explicitly represented the conflicts at the right level of granularity and helped applications resolve them. Whereas producing an object the pretends to be conflict free, but has some fields that might or might not change type is the worst of both worlds.
    - disordinary 10y ago
      Exactly, if there are conflicts that have to be resolved then it's not conflict-free.
      - vidarh 10y ago
        It is conflict free in this sense if no change is rejected, and if the result eventually converges (e.g. if two parties receive the full set of changes, they will end up with the same result, but they may diverge locally until all changes have been synchronised to all replicas). This does mean sometimes producing something that have "application level conflicts" or something that a user will consider a conflict even if the application is perfectly fine with it. Depending on how good the heuristics for determining which changes to keep are, this may be obnoxious or appear perfectly reasonable. E.g. two users start with the same empty document. They each type a sentence. Merge happens. Did they intend the document to have just their sentence, or do they want both? User A wrote that their mutual boss is an idiot; user B wrote that their mutual boss is a genius. Now what do they want to remain? There's no way for software to resolve that automatically which doesn't have disturbing implications. But there certainly are some alternatives that are better than others. E.g. you'd probably prefer to retain both sentences, so you can agree on which to keep. You'd certainly prefer to keep at least one to deleting both.
    - vidarh 10y ago
      They are presenting an algorithm, not a product, so any implementation would be free to make it available in a different way. They specifically do address this point about how developers would deal with it in the conclusion of the paper.
- amelius 10y ago
  > String editing is brushed over in the paper. LaTeX source code is basically just a string. It would have been more interesting to see this applied to a hierarchical data-structure, such as HTML, where e.g. elements are nested inside markup nodes.
  - Kristine1975 10y ago
    LaTeX is also hierarchical, though. Some is explicit (environments) and some is implicit (\chapter, \section etc).
    - amelius 10y ago
      You already indicate that the LaTeX model is not a "clean" hierarchy. So I highly doubt they modeled it like that in JSON, but it could be possible.
      - wheresmypwd 10y ago
        It's a hierarchy like html, where p tags have implicit close tags.
    - nateps 10y ago
      This is true. To preserve document validity and user intent, an algorithm designed for collaborative string editing will not always work correctly when applied to a markup document such as LaTeX, HTML, or Markdown directly. It is similar to how you need a JSON type to represent the kinds of edits you can do to a JSON document rather than editing JSON text as a string. The kinds of edits done in text better map to editing a markup language like LaTeX or Markdown than JSON, so you are less likely to notice these issues right away. But if the type is designed specifically for the markup language, user intent will be better maintained through concurrent edits and the document will never end up in an invalid format.
      - amelius 10y ago
        The same holds for LaTeX stored in git, yet a lot of people use this combination without problems. It is a hack, in a sense, but one without serious consequences.
- ergl 10y ago
  About garbage collection, there is some research done in that direction: Logoot [0] is a collaborative text editor that doesn't depend on tombstones. [0]: https://hal.archives-ouvertes.fr/inria-00336191/ https://hal.archives-ouvertes.fr/inria-00336191/
- jpallen 10y ago
  >> In fact, we wrote the LATEX source text of this paper using an experimental collaborative text editor that is based on our implementation of this CRDT. We are making the character-by-character editing trace of this document available as supplemental data of this paper If anyone else wants to feel at the cutting edge of science, you can write your LaTeX paper collaboratively at https://www.sharelatex.com https://www.sharelatex.com :P I can't pretend we've got any original algorithms (we lean on ShareJS a lot, which is operational transform based), but we've got a few years and billions of key strokes of experience in making it robust and practical.
- nkohari 10y ago
  I've been doing some tinkering in this area lately, and I was also looking for an explanation of the string editing mechanics in this algorithm. The hardest part there is retaining the intent of the simultaneous edits -- the I in the "PCI Consistency model" as described by the WOOT paper. Previous algorithms (LSEQ, WOOT, Doctree, Logoot, etc.) devoted to simultaneous conflict-free editing of text have solved this through relatively complex key generation strategies. I've only done a cursory read of this paper, but this algorithm doesn't seem to implement an alternative solution.
  - vidarh 10y ago
    It's not trying to do string editing at all. It's operating on JSON de-serialized to maps and lists. String editing isn't a valid operation on the data model they specify. You can replace a string value with another. Section 3.3 outlines the allowed operations, which basically allows you to obtain an iterator, move it, insert, delete and retrieve keys and values. You could certainly model string editing in it, by putting each character into it as a separate value, but then as you point out it'd probably not do very well because it doesn't contain heuristics to model intent of text editing, but to model changes to a JSON object hierarchy while avoiding loss of data. You could use this algorithm combined with one intended for string-editing to improve on it for values where partial edits of the values matters, certainly.
    - nicolagreco 10y ago
      wouldn't a string just be a list of chars?
- nateps 10y ago
  We've been developing ShareDB (https://github.com/share/sharedb https://github.com/share/sharedb), a JSON OT system, and using it in production at Lever for 3 years now. CRDT has some strong advantages in decentralized applications with a need to avoid a central server. But in practice, web apps today do generally have a central server. I think the core advantages of OT over CRDTs are actually these practical concerns: being able to design transformations that are more intuitive to application developers, easily cleaning up old operation history, and real world production use and examples of the technology already. One thing OT has enabled us to do that you cannot do as easily in a CRDT is to support turning off publishing of operations when we do large migrations and create huge numbers of ops at once. Because ops have a strict ordering and versioning, clients can lazy get the ops that they have missed if needed later because they submitted a modification on a document or see an even newer op and need the intermediate ops. In a CRDT, you have to make sure that all the clients get all the ops in order to converge. It sounds simple but can be complex in practice. Another practical issue I'd add is that these algorithms sometimes place the burden of resolving the outcome of concurrent edits at read time vs. write time. With OT, you generally do a lot of complex work to figure out how to transform ops at write time, but when you read, you just read the already fully updated document in its native format. CRDT systems often store the document in a format that can be written to very cheaply as it is commutative, but the work gets pushed to read time when you have to collapse a tree full of all its history into a different data structure, such as a string for text editing. One is not strictly better than the other, but many production systems are vastly more read heavy than write heavy, so less obvious tradeoffs like this can become extremely important in production use.
  - arj 10y ago
    That last part is a good summary of CRDT versus OT. Also nice project. I think a section on conflict handling would be a good addition to your README on github. It is the first thing I look for when looking at systems in this space :)
  - tracnar 10y ago
    Have you read the SwiftCloud paper? https://pages.lip6.fr/Marek.Zawirski/papers/SwiftCloud-RR-8347.pdf https://pages.lip6.fr/Marek.Zawirski/papers/SwiftCloud-RR-83... It's about using a centralized cloud infrastructure in conjunction with CRDTs. This allows to fix some of the issues you mention (pruning of operation history, stricter versioning, no need to push operations, ...). Of course it complicates the implementation but it's quite interesting.
- eternalban 10y ago
  > [Garbage collection] is always the painful part of a CRDT system. This is not unique to CRDTs: a temporal datastructure will accumulate garbage. Blockchain (e.g. Git); MVCC (e.g. Postgresql).
ianstormtaylor 10y ago
Related: does anyone know any other good resources for architecting and building OT/CRDT for nested data structures like HTML or JSON? Ideally projects with working examples even?
- amelius 10y ago
  I'm looking for a good 3-way merge for strings implemented in Javascript.
- clemensnk 10y ago
  We do OT on HTML (or rather the DOM) in the Webstrates (http://www.webstrates.net http://www.webstrates.net) project. We use ShareJS (now ShareDB) and represent and store the DOM as a JSON document.
- nateps 10y ago
  Author of ShareDB (https://github.com/share/sharedb https://github.com/share/sharedb) here. ShareDB is a stable production JSON OT system that powers the entire backend for Lever (https://www.lever.co/ https://www.lever.co/). All of Lever's apps, backend services, migration scripts, etc. go through ShareDB. It scales horizontally; over 1000 companies use Lever, including companies with 1000s of employees, like Netflix and Yelp. There are some simple examples in the repo to get you started. Please let us know if you have any questions getting going!
jondubois 10y ago
It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate - Incorrect data will creep in from time to time (but at least the incorrect data will be consistent across all nodes). The root of the problem is that the system cannot understand the collaborative intent of concurrent users - If you have 2 users who made a change at the same time (without being aware of each other); you have to account for the fact that maybe UserB would have behaved differently if they had been aware of UserA's input (which happened at the same time while one or both users were offline). If the user has been offline for a while - Many such conflicts could arise (maybe by the time the internet comes back on, the user is looking at a completely different page than the one they made the change on) and it's tedious to make the user resolve them all manually. Also with this approach, it tends to force you to keep a copy/cache of all the data in your entire app (for that logged-in user) on the frontend - If you have a big app with lots of pages, that could consume a lot of memory. There are cases where the best solution is to simply tell the user "Sorry, you do not have an internet connection at the moment, so you cannot modify this data" rather than giving them a false sense that the data are correctly backed up in the cloud. I think with CRDTs, it's really important to inform the user when they are offline and when their data are not synced/backed up in the cloud (so they don't get any bad surprises when the internet suddenly comes back on). CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). One could argue that they improve the user experience, but at the core, developers like them because they make life easier.
- pjc50 10y ago
  CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). It's interesting you say that given that banking invented eventual consistency with manual reconciliation of exceptions, in the form of the cheque.
- jorangreef 10y ago
  "It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate [...] The root of the problem is that the system cannot understand the collaborative intent of concurrent users" CRDTs are usually designed to model user intent. You just need to pick the right CRDT for your use-case. From there, the CRDT will resolve conflicts automatically and accurately. Your statement regarding impossibility would be true of operational transformation, but certainly not of CRDTs.
btrask 10y ago
I developed a "general purpose" JSON-based CRDT[1] as a part of my content addressing system project. The idea was to have an "append-only tree", where subtrees could be used by individual applications for different purposes, for example as counters or mutable sets. In retrospect, it didn't need to support recursion. A single-level append-only set is enough to be fully general and easier to perform indexing on. Using JSON was also overkill, since too much flexibility is bad for content-addressing. [1] https://github.com/btrask/stronglink/blob/master/client/README.md#meta-files https://github.com/btrask/stronglink/blob/master/client/READ...
cwmma 10y ago
so from reading the comments, am I correct that with an object like this {"key":1} if one user changes it to be {"key":2} while the other at the same time changes it to be {"key":3} and another user changes it to {"key":[2, 3]} it's impossible to tell if there was a conflict between the first 2 users or the third user just made an update
marknadal 10y ago
I am the author of a CRDT database that can store JSON. Here are Kyle Kingsbury's (Aphyr) thoughts on it: https://twitter.com/aphyr/status/646302398575587332 https://twitter.com/aphyr/status/646302398575587332 . In response to the OT comments here in the thread, people should be aware that OT is not P2P or decentralized. The algorithm in the paper is, however, and so is GUN (https://github.com/amark/gun https://github.com/amark/gun) . Probably more important to the discussion, is that it IS possible to implement collaborative rich text editing on top of P2P CRDT systems. Although I do not know of any yet, I am working towards one which uses a linked-list DAG, early demo: https://www.youtube.com/watch?v=rci89p0o2wQ https://www.youtube.com/watch?v=rci89p0o2wQ .

132 points by DanielRibeiro 10y ago

jackweirdy 10y ago

Can't read the paper - is this an implementation of or just related to CRDTs?

zbyte64 10y ago
"The JSON datatype described in this paper is a kind of CRDT"

espadrine 10y ago

> Our principle of not losing input due to concurrent modifications appears reasonable, but as illustrated in Figure 4, it leads to merged document states that may be surprising to application programmers who are more familiar with sequential programs. That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string to a list without having any operation creating a list explicitly. > Moreover, garbage collection (tombstone removal) is required in order to prevent unbounded growth of the datastructure That is always the painful part of a CRDT system. Until that part is done, it cannot really be used in production. That said, previous work on CRDTs give me confidence that it can be implemented with minimal overhead. > In fact, we wrote the LATEX source text of this paper using an experimental collaborative text editor that is based on our implementation of this CRDT. We are making the character-by-character editing trace of this document available as supplemental data of this paper String editing is brushed over in the paper. I'd love to see their implementation. Does anyone know where it all is?

vidarh 10y ago
> That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string to a list without having any operation creating a list explicitly. It's hard to see good alternatives there. If you move from a single editor to concurrent edits without very strict ordering guarantees or a transactional system, you will need to deal with conflicts or lose data. Creating output that would be considered invalid unless the application is fixed to explicitly deal with it (or explicitly throw it away) seems quite reasonable.
- adrianratnapala 10y ago
  For this you would want a type / schema that explicitly represented the conflicts at the right level of granularity and helped applications resolve them. Whereas producing an object the pretends to be conflict free, but has some fields that might or might not change type is the worst of both worlds.
  - disordinary 10y ago
    Exactly, if there are conflicts that have to be resolved then it's not conflict-free.
    - vidarh 10y ago
      It is conflict free in this sense if no change is rejected, and if the result eventually converges (e.g. if two parties receive the full set of changes, they will end up with the same result, but they may diverge locally until all changes have been synchronised to all replicas). This does mean sometimes producing something that have "application level conflicts" or something that a user will consider a conflict even if the application is perfectly fine with it. Depending on how good the heuristics for determining which changes to keep are, this may be obnoxious or appear perfectly reasonable. E.g. two users start with the same empty document. They each type a sentence. Merge happens. Did they intend the document to have just their sentence, or do they want both? User A wrote that their mutual boss is an idiot; user B wrote that their mutual boss is a genius. Now what do they want to remain? There's no way for software to resolve that automatically which doesn't have disturbing implications. But there certainly are some alternatives that are better than others. E.g. you'd probably prefer to retain both sentences, so you can agree on which to keep. You'd certainly prefer to keep at least one to deleting both.
  - vidarh 10y ago
    They are presenting an algorithm, not a product, so any implementation would be free to make it available in a different way. They specifically do address this point about how developers would deal with it in the conclusion of the paper.
amelius 10y ago
> String editing is brushed over in the paper. LaTeX source code is basically just a string. It would have been more interesting to see this applied to a hierarchical data-structure, such as HTML, where e.g. elements are nested inside markup nodes.
- Kristine1975 10y ago
  LaTeX is also hierarchical, though. Some is explicit (environments) and some is implicit (\chapter, \section etc).
  - amelius 10y ago
    You already indicate that the LaTeX model is not a "clean" hierarchy. So I highly doubt they modeled it like that in JSON, but it could be possible.
    - wheresmypwd 10y ago
      It's a hierarchy like html, where p tags have implicit close tags.
  - nateps 10y ago
    This is true. To preserve document validity and user intent, an algorithm designed for collaborative string editing will not always work correctly when applied to a markup document such as LaTeX, HTML, or Markdown directly. It is similar to how you need a JSON type to represent the kinds of edits you can do to a JSON document rather than editing JSON text as a string. The kinds of edits done in text better map to editing a markup language like LaTeX or Markdown than JSON, so you are less likely to notice these issues right away. But if the type is designed specifically for the markup language, user intent will be better maintained through concurrent edits and the document will never end up in an invalid format.
    - amelius 10y ago
      The same holds for LaTeX stored in git, yet a lot of people use this combination without problems. It is a hack, in a sense, but one without serious consequences.
ergl 10y ago
About garbage collection, there is some research done in that direction: Logoot [0] is a collaborative text editor that doesn't depend on tombstones. [0]: https://hal.archives-ouvertes.fr/inria-00336191/ https://hal.archives-ouvertes.fr/inria-00336191/
jpallen 10y ago
>> In fact, we wrote the LATEX source text of this paper using an experimental collaborative text editor that is based on our implementation of this CRDT. We are making the character-by-character editing trace of this document available as supplemental data of this paper If anyone else wants to feel at the cutting edge of science, you can write your LaTeX paper collaboratively at https://www.sharelatex.com https://www.sharelatex.com :P I can't pretend we've got any original algorithms (we lean on ShareJS a lot, which is operational transform based), but we've got a few years and billions of key strokes of experience in making it robust and practical.
nkohari 10y ago
I've been doing some tinkering in this area lately, and I was also looking for an explanation of the string editing mechanics in this algorithm. The hardest part there is retaining the intent of the simultaneous edits -- the I in the "PCI Consistency model" as described by the WOOT paper. Previous algorithms (LSEQ, WOOT, Doctree, Logoot, etc.) devoted to simultaneous conflict-free editing of text have solved this through relatively complex key generation strategies. I've only done a cursory read of this paper, but this algorithm doesn't seem to implement an alternative solution.
- vidarh 10y ago
  It's not trying to do string editing at all. It's operating on JSON de-serialized to maps and lists. String editing isn't a valid operation on the data model they specify. You can replace a string value with another. Section 3.3 outlines the allowed operations, which basically allows you to obtain an iterator, move it, insert, delete and retrieve keys and values. You could certainly model string editing in it, by putting each character into it as a separate value, but then as you point out it'd probably not do very well because it doesn't contain heuristics to model intent of text editing, but to model changes to a JSON object hierarchy while avoiding loss of data. You could use this algorithm combined with one intended for string-editing to improve on it for values where partial edits of the values matters, certainly.
  - nicolagreco 10y ago
    wouldn't a string just be a list of chars?
nateps 10y ago
We've been developing ShareDB (https://github.com/share/sharedb https://github.com/share/sharedb), a JSON OT system, and using it in production at Lever for 3 years now. CRDT has some strong advantages in decentralized applications with a need to avoid a central server. But in practice, web apps today do generally have a central server. I think the core advantages of OT over CRDTs are actually these practical concerns: being able to design transformations that are more intuitive to application developers, easily cleaning up old operation history, and real world production use and examples of the technology already. One thing OT has enabled us to do that you cannot do as easily in a CRDT is to support turning off publishing of operations when we do large migrations and create huge numbers of ops at once. Because ops have a strict ordering and versioning, clients can lazy get the ops that they have missed if needed later because they submitted a modification on a document or see an even newer op and need the intermediate ops. In a CRDT, you have to make sure that all the clients get all the ops in order to converge. It sounds simple but can be complex in practice. Another practical issue I'd add is that these algorithms sometimes place the burden of resolving the outcome of concurrent edits at read time vs. write time. With OT, you generally do a lot of complex work to figure out how to transform ops at write time, but when you read, you just read the already fully updated document in its native format. CRDT systems often store the document in a format that can be written to very cheaply as it is commutative, but the work gets pushed to read time when you have to collapse a tree full of all its history into a different data structure, such as a string for text editing. One is not strictly better than the other, but many production systems are vastly more read heavy than write heavy, so less obvious tradeoffs like this can become extremely important in production use.
- arj 10y ago
  That last part is a good summary of CRDT versus OT. Also nice project. I think a section on conflict handling would be a good addition to your README on github. It is the first thing I look for when looking at systems in this space :)
- tracnar 10y ago
  Have you read the SwiftCloud paper? https://pages.lip6.fr/Marek.Zawirski/papers/SwiftCloud-RR-8347.pdf https://pages.lip6.fr/Marek.Zawirski/papers/SwiftCloud-RR-83... It's about using a centralized cloud infrastructure in conjunction with CRDTs. This allows to fix some of the issues you mention (pruning of operation history, stricter versioning, no need to push operations, ...). Of course it complicates the implementation but it's quite interesting.
eternalban 10y ago
> [Garbage collection] is always the painful part of a CRDT system. This is not unique to CRDTs: a temporal datastructure will accumulate garbage. Blockchain (e.g. Git); MVCC (e.g. Postgresql).

ianstormtaylor 10y ago

Related: does anyone know any other good resources for architecting and building OT/CRDT for nested data structures like HTML or JSON? Ideally projects with working examples even?

amelius 10y ago
I'm looking for a good 3-way merge for strings implemented in Javascript.
clemensnk 10y ago
We do OT on HTML (or rather the DOM) in the Webstrates (http://www.webstrates.net http://www.webstrates.net) project. We use ShareJS (now ShareDB) and represent and store the DOM as a JSON document.
nateps 10y ago
Author of ShareDB (https://github.com/share/sharedb https://github.com/share/sharedb) here. ShareDB is a stable production JSON OT system that powers the entire backend for Lever (https://www.lever.co/ https://www.lever.co/). All of Lever's apps, backend services, migration scripts, etc. go through ShareDB. It scales horizontally; over 1000 companies use Lever, including companies with 1000s of employees, like Netflix and Yelp. There are some simple examples in the repo to get you started. Please let us know if you have any questions getting going!

jondubois 10y ago

It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate - Incorrect data will creep in from time to time (but at least the incorrect data will be consistent across all nodes). The root of the problem is that the system cannot understand the collaborative intent of concurrent users - If you have 2 users who made a change at the same time (without being aware of each other); you have to account for the fact that maybe UserB would have behaved differently if they had been aware of UserA's input (which happened at the same time while one or both users were offline). If the user has been offline for a while - Many such conflicts could arise (maybe by the time the internet comes back on, the user is looking at a completely different page than the one they made the change on) and it's tedious to make the user resolve them all manually. Also with this approach, it tends to force you to keep a copy/cache of all the data in your entire app (for that logged-in user) on the frontend - If you have a big app with lots of pages, that could consume a lot of memory. There are cases where the best solution is to simply tell the user "Sorry, you do not have an internet connection at the moment, so you cannot modify this data" rather than giving them a false sense that the data are correctly backed up in the cloud. I think with CRDTs, it's really important to inform the user when they are offline and when their data are not synced/backed up in the cloud (so they don't get any bad surprises when the internet suddenly comes back on). CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). One could argue that they improve the user experience, but at the core, developers like them because they make life easier.

pjc50 10y ago
CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). It's interesting you say that given that banking invented eventual consistency with manual reconciliation of exceptions, in the form of the cheque.
jorangreef 10y ago
"It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate [...] The root of the problem is that the system cannot understand the collaborative intent of concurrent users" CRDTs are usually designed to model user intent. You just need to pick the right CRDT for your use-case. From there, the CRDT will resolve conflicts automatically and accurately. Your statement regarding impossibility would be true of operational transformation, but certainly not of CRDTs.

btrask 10y ago

I developed a "general purpose" JSON-based CRDT[1] as a part of my content addressing system project. The idea was to have an "append-only tree", where subtrees could be used by individual applications for different purposes, for example as counters or mutable sets. In retrospect, it didn't need to support recursion. A single-level append-only set is enough to be fully general and easier to perform indexing on. Using JSON was also overkill, since too much flexibility is bad for content-addressing. [1] https://github.com/btrask/stronglink/blob/master/client/README.md#meta-files https://github.com/btrask/stronglink/blob/master/client/READ...

cwmma 10y ago

so from reading the comments, am I correct that with an object like this {"key":1} if one user changes it to be {"key":2} while the other at the same time changes it to be {"key":3} and another user changes it to {"key":[2, 3]} it's impossible to tell if there was a conflict between the first 2 users or the third user just made an update

marknadal 10y ago

I am the author of a CRDT database that can store JSON. Here are Kyle Kingsbury's (Aphyr) thoughts on it: https://twitter.com/aphyr/status/646302398575587332 https://twitter.com/aphyr/status/646302398575587332 . In response to the OT comments here in the thread, people should be aware that OT is not P2P or decentralized. The algorithm in the paper is, however, and so is GUN (https://github.com/amark/gun https://github.com/amark/gun) . Probably more important to the discussion, is that it IS possible to implement collaborative rich text editing on top of P2P CRDT systems. Although I do not know of any yet, I am working towards one which uses a linked-list DAG, early demo: https://www.youtube.com/watch?v=rci89p0o2wQ https://www.youtube.com/watch?v=rci89p0o2wQ .