3 ms·

An interesting challenge in the CRDT era today, is that there isn't an ideal CRDT for rich text yet. I mean, not just simple boundary based formattings like bol

An interesting challenge in the CRDT era today, is that there isn't an ideal CRDT for rich text yet. I mean, not just simple boundary based formattings like bold/italics but also complex block based elements like tables and lists. While recent CRDTs like peritext has done an incredible job of focussing on this specific problem of rich text, even that project hasn't extended its types to cover table operations and list operations. I've been thinking about this problem deeply and my intuition is that anything that resembles semantic trees are tricky to deal with using a generic CRDT. For example a generic tree/json CRDT cannot be used for an AST tree - and it will most likely fail. I wrote about this a while back - https://news.ycombinator.com/item?id=29433896 https://news.ycombinator.com/item?id=29433896 If you have ideas on how to approach this problem, join us on this thread https://github.com/inkandswitch/peritext/issues/27#issuecomment-985299874 https://github.com/inkandswitch/peritext/issues/27#issuecomm...

samwillis 5y ago
I can't find a link right now but I believe Kevin is in the process of implementing "move" in Yjs, so that if you copy and paste from a section or split it, it is a move rather than a delete and insert. Agreed on tables, they are so much more complex and may need further operation types to ensure no dropped edits. Obviously with Peritext you are implementing a very rich text focused CRDT. The way I see it is there are general purpose and domain specific CRDTs, Yjs being more general purpose but with a concept of 'marks' on strings for formatting. Ultimately we need both and I like the concept of one that covers both bases so you can have a db document that contains rich text fields along with more traditional structured data. Without exactly domain specific CRDTs for your application you will always have to do some level of schema correction after merging documents.
- westurner 5y ago
  Re: inlined tabular data in CRDT distributed systems for collaboration on documents that may be required to validate: Atomicity: https://en.wikipedia.org/wiki/Atomicity_(database_systems) https://en.wikipedia.org/wiki/Atomicity_(database_systems) > An atomic transaction is an indivisible and irreducible series of database operations such that either all occurs, or nothing occurs.[1] A guarantee of atomicity prevents updates to the database occurring only partially, which can cause greater problems than rejecting the whole series outright. As a consequence, the transaction cannot be observed to be in progress by another database client. At one moment in time, it has not yet happened, and at the next it has already occurred in whole (or nothing happened if the transaction was cancelled in progress). > An example of an atomic transaction is a monetary transfer from bank account A to account B. It consists of two operations, withdrawing the money from account A and saving it to account B. Performing these operations in an atomic transaction ensures that the database remains in a consistent state, that is, money is neither lost nor created if either of those two operations fail. [2] IIRC, Apache Wave (Google Wave (2009)) solves for tables but is not built atop a CRDT, like Docs and Sheets? https://en.wikipedia.org/wiki/Google_Wave https://en.wikipedia.org/wiki/Google_Wave Jupyterlab/rtc - Jupyterlab, JupyterLite (WASM), - is built upon a CRDT for .ipynb JSON, at least. https://github.com/jupyterlab/rtc https://github.com/jupyterlab/rtc (URI-) Named Graphs as JSON-LD would work there, too. https://json-ld.org/playground/ https://json-ld.org/playground/ Does Dokieli have atomic table operations for ad-hoc inlined tables as RDF Linked Data? https://github.com/linkeddata/dokieli https://github.com/linkeddata/dokieli
  - samwillis 5y ago
    I think there is some confusion over "tables", the GP I believe was referring to typographic "rich text" tables, like you have in a word document, rather than a "data table" in a DB. The issue with "rich text" tables and CRDTs is that you effectively have two overlapping "blocks", columns and rows. Current CRDTs are good at managing a list of blocks, splitting them, reordering them. Most rich rich text tables are represented as a list of rows of cells. If you have two clients, one adds a new row (represented as a new row in rows list), and the other adds a new column (represented as a new cell in each row in the rows list), and then merge, you have a conflict where the new row and column meet. There is a missing cell, and so you end up with a row that is one cell too short. What is needed is a CRTD that has a concept of a table, or table like structure, so that when the documents are merged it knows to add that extra cell in the new row. This has nothing to do with Atomicity in the traditional DB transaction sense. Edit: Just thinking about this a little more, if you model the table as a list of maps, with each column having a unique id it would overcome the misalignment issue, and it potentially helps with other table conflicts too. You would however have to store the order of the columns somewhere and deleting columns could conflict.
    - westurner 5y ago
      > This has nothing to do with Atomicity in the traditional DB transaction sense. Partial application of conflicting additive schema modifications is an atomicity issue as much as it is a merge issue. If the [HTML] doesn't validate before other nodes are expected to synchronize with it, that changeset shouldn't apply at all; atomicity. It looks like Dokieli supports embedded tables. With RDF (and triplestores, and property graphs), you can just add "rows" and "columns" (rdfs:Class instances with rdfs:Property instances) without modifying the schema or the tabular data. Online schema migration is dangerous with SQL, too, because the singular db user account for the app shouldn't have [destructive] ALTER TABLE privileges. "CSV on the Web: A Primer" > "Validating CSVs" (CSVW Tabular Data) https://www.w3.org/TR/tabular-data-primer/#validating-csvs https://www.w3.org/TR/tabular-data-primer/#validating-csvs
- jitl 5y ago
  Joe started an interesting discussion about block and table CRDTs on the Peritext github that you will find interesting: https://github.com/inkandswitch/peritext/issues/27 https://github.com/inkandswitch/peritext/issues/27 My perspective from working on a centralized collaborative editor (Notion) is that last-write-wins semantics in some places often fine; I wouldn’t stress out about column split/join for that reason. I proposed a CRDT for tables that handles the rest of the features reasonably well in the GitHub thread, we use a similar structure for Notion’s “simple tables” feature.

samwillis 5y ago

I can't find a link right now but I believe Kevin is in the process of implementing "move" in Yjs, so that if you copy and paste from a section or split it, it is a move rather than a delete and insert. Agreed on tables, they are so much more complex and may need further operation types to ensure no dropped edits. Obviously with Peritext you are implementing a very rich text focused CRDT. The way I see it is there are general purpose and domain specific CRDTs, Yjs being more general purpose but with a concept of 'marks' on strings for formatting. Ultimately we need both and I like the concept of one that covers both bases so you can have a db document that contains rich text fields along with more traditional structured data. Without exactly domain specific CRDTs for your application you will always have to do some level of schema correction after merging documents.

westurner 5y ago
Re: inlined tabular data in CRDT distributed systems for collaboration on documents that may be required to validate: Atomicity: https://en.wikipedia.org/wiki/Atomicity_(database_systems) https://en.wikipedia.org/wiki/Atomicity_(database_systems) > An atomic transaction is an indivisible and irreducible series of database operations such that either all occurs, or nothing occurs.[1] A guarantee of atomicity prevents updates to the database occurring only partially, which can cause greater problems than rejecting the whole series outright. As a consequence, the transaction cannot be observed to be in progress by another database client. At one moment in time, it has not yet happened, and at the next it has already occurred in whole (or nothing happened if the transaction was cancelled in progress). > An example of an atomic transaction is a monetary transfer from bank account A to account B. It consists of two operations, withdrawing the money from account A and saving it to account B. Performing these operations in an atomic transaction ensures that the database remains in a consistent state, that is, money is neither lost nor created if either of those two operations fail. [2] IIRC, Apache Wave (Google Wave (2009)) solves for tables but is not built atop a CRDT, like Docs and Sheets? https://en.wikipedia.org/wiki/Google_Wave https://en.wikipedia.org/wiki/Google_Wave Jupyterlab/rtc - Jupyterlab, JupyterLite (WASM), - is built upon a CRDT for .ipynb JSON, at least. https://github.com/jupyterlab/rtc https://github.com/jupyterlab/rtc (URI-) Named Graphs as JSON-LD would work there, too. https://json-ld.org/playground/ https://json-ld.org/playground/ Does Dokieli have atomic table operations for ad-hoc inlined tables as RDF Linked Data? https://github.com/linkeddata/dokieli https://github.com/linkeddata/dokieli
- samwillis 5y ago
  I think there is some confusion over "tables", the GP I believe was referring to typographic "rich text" tables, like you have in a word document, rather than a "data table" in a DB. The issue with "rich text" tables and CRDTs is that you effectively have two overlapping "blocks", columns and rows. Current CRDTs are good at managing a list of blocks, splitting them, reordering them. Most rich rich text tables are represented as a list of rows of cells. If you have two clients, one adds a new row (represented as a new row in rows list), and the other adds a new column (represented as a new cell in each row in the rows list), and then merge, you have a conflict where the new row and column meet. There is a missing cell, and so you end up with a row that is one cell too short. What is needed is a CRTD that has a concept of a table, or table like structure, so that when the documents are merged it knows to add that extra cell in the new row. This has nothing to do with Atomicity in the traditional DB transaction sense. Edit: Just thinking about this a little more, if you model the table as a list of maps, with each column having a unique id it would overcome the misalignment issue, and it potentially helps with other table conflicts too. You would however have to store the order of the columns somewhere and deleting columns could conflict.
  - westurner 5y ago
    > This has nothing to do with Atomicity in the traditional DB transaction sense. Partial application of conflicting additive schema modifications is an atomicity issue as much as it is a merge issue. If the [HTML] doesn't validate before other nodes are expected to synchronize with it, that changeset shouldn't apply at all; atomicity. It looks like Dokieli supports embedded tables. With RDF (and triplestores, and property graphs), you can just add "rows" and "columns" (rdfs:Class instances with rdfs:Property instances) without modifying the schema or the tabular data. Online schema migration is dangerous with SQL, too, because the singular db user account for the app shouldn't have [destructive] ALTER TABLE privileges. "CSV on the Web: A Primer" > "Validating CSVs" (CSVW Tabular Data) https://www.w3.org/TR/tabular-data-primer/#validating-csvs https://www.w3.org/TR/tabular-data-primer/#validating-csvs
jitl 5y ago
Joe started an interesting discussion about block and table CRDTs on the Peritext github that you will find interesting: https://github.com/inkandswitch/peritext/issues/27 https://github.com/inkandswitch/peritext/issues/27 My perspective from working on a centralized collaborative editor (Notion) is that last-write-wins semantics in some places often fine; I wouldn’t stress out about column split/join for that reason. I proposed a CRDT for tables that handles the rest of the features reasonably well in the GitHub thread, we use a similar structure for Notion’s “simple tables” feature.