search

automerge / automerge-classic

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
http://automerge.org/
MIT License
14.75k stars 466 forks source link

[Question] Merge semantics for Table #388

Closed yann-achard closed 3 years ago

yann-achard commented 3 years ago

Hello, I'm trying to understand what the Table CRDT provides compared to the JSON CRDT. I understand the part about generating row IDs being non-trivial, but I'm not clear about foreign key integrity guarantees.

Does Table make any such guarantees? If so, what are they? (I can imagine "insertions that reference the ID of a concurrently deleted row are ignored" or "deletions of a row that is (concurrently or not) referred to by other entities are ignored")

Or does Table make no such guarantees? In which case, do I understand correctly that any dereferencing (e.g. doc.myTable.byId(...)) can fail? Does Automerge expose extension points such that one could enforce such guarantees? How would that work?

Thank you!

ept commented 3 years ago

Hi @yann-achard, the ID of a table row is really just a random UUID. We encourage the use of Table simply because otherwise people might be tempted to use sequential integers as IDs, and that would not be safe (because different users may concurrently generate the same ID; with UUIDs such a collision is extremely unlikely).

The Table datatype does not make any foreign key guarantees (in fact, it doesn't even have a way of declaring foreign key constraints). Even if we ensure on insert/update that the row referenced by a key exists, another user could concurrently delete the row being referenced, and then the constraint is violated. Thus, you need to check at read time whether the referenced row actually exists.

However, Automerge does have a causality guarantee: that is, if row A is inserted, and then row B (which references A) is inserted, then all users will see the insertion of A before the insertion of B. There will not be any users who see B before A. Therefore, if you guarantee that A is never deleted, then foreign key integrity is ensured.

Since Automerge is designed to allow any two users to update a document arbitrarily, even while they are offline, I think the only way of preventing foreign key violations is to prohibit deletions from a table. Hope that answers your question.