Behaviour of concurrently created objects under the same key

[ept]

After some discussion around #1, I've been thinking about what the "minimally confusing" semantics for nested maps/objects should be.

Scenario: Several users have a shared Trellis document. The current version of Trellis does not have any configuration settings, it only stores cards and their positions. However, users have been demanding customisation, and so the developers of Trellis reluctantly release a new version that supports two configuration options for customising the theme of a project: a logo, and a background colour.

User Alice installs the new release, plays around with the configuration, and configures the app to have a custom logo. The code internally does the following:

// On Alice's device
if (!trellis.root.config) trellis.root.config = {};
trellis.root.config.logo_url = "https://example.com/logo.png";

Alice then goes offline. Later, Bob comes online, also installs the app update, and also plays around with the configuration. Since Alice is not online, he doesn't receive the config change made by Alice, so in his view of the data the configuration is still empty. He sets the background colour:

// On Bob's device
if (!trellis.root.config) trellis.root.config = {};
trellis.root.config.background = "blue";

Now Alice comes back online, and the two synchronise. What should happen? It seems like the two most reasonable outcomes are:

1. The app arbitrarily picks one of the two configurations, i.e. either config: {logo_url: "https://example.com/logo.png"} or config: {background: "blue"}, and stashes away the other configuration under conflicts (where it will probably be ignored).
2. The app merges together the two sets of configurations, which works fine in this case because Alice and Bob changed two different keys in the config object: config: {background: "blue", logo_url: "https://example.com/logo.png"}.

The current behaviour of Tesseract is (1), except that Tesseract chooses behaviour (2) for the root object. That is, if you used top-level keys rather than a nested config object, Tesseract would retain both:

// On Alice's device
trellis.root.config_logo_url = "https://example.com/logo.png";

// On Bob's device
trellis.root.config_background = "blue";

// Merged outcome:
trellis.root == {config_logo_url: "https://example.com/logo.png", config_background = "blue"}

To me, this merging behaviour seems more intuitive than the choose-one-or-the-other behaviour (1), and it seems strange to treat the root object differently from nested objects, as discussed in #1. Riak also chooses this merging behaviour. However, applying this merging behaviour systematically results in some weird edge-cases, as discussed in our paper:

I am now trying to figure out what a sensible middle ground might look like. Here is an idea, and I would love to hear what you think.

I suggest that within a map, when a key is assigned an object for the first time time (that key did not previously exist), we record the fact that it was a first-time assignment. If several such first-time assignments occur concurrently, we merge the assigned objects recursively:

// On Alice's device
if (!trellis.root.config) trellis.root.config = {logo_url: "https://example.com/logo.png"};

// Concurrently, on Bob's device
if (!trellis.root.config) trellis.root.config = {background: "blue"};

// Merged outcome:
trellis.root == {config: {logo_url: "https://example.com/logo.png", background: "blue"}, ...}

However, deletions of a higher tree node take precedence over edits within the deleted subtree:

// Initially:
trellis.root == {config: {logo_url: "https://example.com/logo.png", background: "blue"}, ...}

// Alice resets to factory settings
delete trellis.root['config'];

// Concurrently, Bob changes a setting:
trellis.root.config.background = "red";

// Merged outcome, Bob's change having been lost:
trellis.root.config === undefined

Also, insertions of new objects into arrays are always independent from each other:

// Alice:
trellis.root.cards.push({title: "Collect underpants"})

// Bob:
trellis.root.cards.push({title: "Profit!"})

// Merged outcome: either
trellis.root.cards == [{title: "Collect underpants"}, {title: "Profit!"}]
// or
trellis.root.cards == [{title: "Profit!"}, {title: "Collect underpants"}]
// but never merging the two insertions

Unfortunately, merging objects may not always make sense, because the fields of an object may not be independent of each other. For example:

// Alice:
trellis.root.billing_address = {
  org: "Ink & Switch",
  city: "San Francisco",
  state: "CA",
  country: "United States"}

// Bob:
trellis.root.billing_address = {
  org: "Computer Laboratory",
  road: "15 JJ Thomson Avenue",
  city: "Cambridge",
  country: "United Kingdom"}

// Merged outcome, with two addresses nonsensically spliced together:
trellis.root.billing_address == {
  org: "Ink & Switch",
  road: "15 JJ Thomson Avenue",
  city: "San Francisco",
  state: "CA",
  country: "United Kingdom"}

Moreover, it is possible that rather than assigning a value of a single field within an object, a user may update a copy of an object and assign the entire copy. Should this be treated as equivalent to single-field assignment?

// Bob changes a setting by assigning a single field in an object
trellis.root.config.background = "red";

// Is this equivalent to updating a copy of the object?
let config = Object.assign({}, trellis.root.config);
config.background = "red";
trellis.root.config = config;

In a single-user scenario, these two ways of updating the state would be almost equivalent, but in the current Tesseract implementation the second example would overwrite any concurrent configuration updates by other users. Should assigning an object maybe examine the differences between the old and the new object, and translate the change into the assignment of only those fields that have changed?

Sorry for the rambling — I don't really know how best to resolve this, just wanted to start a discussion with a few examples. We don't have to answer it right now, but it would be good to keep this question in the back of our minds while working on Trellis, and so I thought it would be useful to have it written up.

[adamwiggins]

Great write-up, and thanks for the excellent concrete examples :)

From my perspective the answer to all of these scenarios is that Tesseract needs to expose data types that lets the app developer model their data in a way that clearly communicates intent. If what should happen in a merge is unclear, then the app developer didn't pick the right data type, or we need to add a new data type to Tesseract.

I strongly suspect this will mean going beyond the traditional [number,string,list,map] set of types, as hinted at by CBaquero's work.

Taking each of your items in turn...

Config example

As an app developer I'd want the merging behavior of Alice's logo added to Bob's background color. Maybe that looks weird but maybe Alice and Bob need to chat about it, not clobber each other's changes.

In this case an ID-less map which always merges is what I want.

Cards

On the other hand, cards are objects that have a unique ID. There's always a clear "someone made this card" create operation, and then people might mutate it over time. So even if this is modeled as a map, it's a different kind of map. I'd probably call it a record, equivalent to a record in a schemaless NoSQL database.

Billing address

The intent here is to create each address as a record with a unique ID. When I add a new billing address it's similar to adding a new shipping address in Amazon. Maybe I can track many at once, maybe the system only lets me have one — but you'd never merge two addresses with different unique IDs.

So maybe that looks like:

// Alice
trellis.root.billing_addresses.push({ org: "Ink & Switch", city: "Miami" })

// Bob
trellis.root.billing_addresses.push({ org: "Computer Laboratory", city: "Cambridge" })

// Merged outcome
trellis.root.billing_addresses == [
  { org: "Computer Laboratory", city: "Cambridge" },
  { org: "Ink & Switch", city: "Miami" }
]

If Alice wants to edit her entry:

// Alice
record = trellis.root.billing_addresses.push({ org: "Ink & Switch", city: "Miami" })
record.city = "Boca Raton"
record.save

Not sure if that's quite right, but somehow indicating the intent of updating an existing record vs creating a new one.

[rboulton]

I read through this a couple of weeks ago and have been pondering it with some experiments I'm doing. I've not written much code around this yet, though, so take all these musings as fairly uninformed.

Firstly, I think it will be a strong cause of confusion and bugs if the behaviour of the root object with regard to merging is different from that of sub-objects, so I think a design which doesn't meet that aim is undesirable.

I think that developers will need to have a reasonable mental model of the merging behaviour in order to produce the correct results - the amount the Automerge hides is definitely desirable, but as @adamwiggins says there's at least a distinction between a map which always merges, and one which is much more "atomic". If developers know that map always merges, they can code with this in mind - the simpler the mental model they need to have, the better.

Looking at the examples, though, there seem to be good ways to model things with only a map that always merges, but an array that allows access to an individual item - I don't see a need for new data types here (though it's possible that some new data types to model intent would make things clearer and less likely to be buggy).

Config

As discussed above, this is straightforward if map always merges.

Cards

Cards should have an id, and the create operation should assign the ID. I can see two ways of modelling this:

1. Assign a UUID to the card when creating it, and store the cards in a map keyed by these UUIDs. If an ordering of the cards is needed, a separate array holding the UUIDs of the cards could be used (... but would integrity of this array and the keys in the map be preserved over all merges of operations?).

2. Use an array to hold the cards, push each new card onto the array, modify cards in place (... assuming that accessing cards like this is safe with regards to merges).

Billing addresses

Could be modelled as an array of maps as suggested by @adamwiggins.

If the application requires there to be only one address, the application could handle this whenever it notices that the array has a length of greater than 1. It could for example prompt the user to pick one, or just delete all but one of them using whatever policy it likes. So, application developers could make the choice of what to do.

It seems to me that it might be possible to build most of the higher-level data types on top of the existing automerge data types, and that there is a lot to be said for keeping Automerge's model as simple as possible. I could imagine a higher-level layer, perhaps based on a schema being defined for the data, being built on top of Automerge, to help developers communicate the intent of their data model more clearly, and avoid having to think about the details of the merging behaviour they want - but I think this layer is often going to need to have ways to indicate conflicts to the application to ask for the best way to resolve them.

[ept]

I just remembered that last October I wrote up another discussion of this question as a separate document, after a discussion with Peter van Hardenberg, and Jeff Peterson. Copying it here for future reference…

At the moment, there is no special handling of initialisation operations for Automerge documents: every document starts off empty, and any data structures required in the document need to be created by the application.

This works well as long as the initialisation happens only when the document is first created, and before it is shared. However, sometimes there is a need to perform initialisation on an existing document that is already shared between multiple devices or users. For example, consider the case of a PDF card in an application that initially does not support handwritten annotations of the PDF document. Later, a feature is added that enables handwritten annotations. To store those annotations, the document is extended to contain a list of pen strokes:

pdfCard = Automerge.change(pdfCard, doc => {
  doc.strokes = []
  doc.strokes.push(...)
})

However, if two users concurrently install the version of the application that supports pen strokes, these users may concurrently perform the change above, each assigning an empty list to the key strokesand then adding data to the list. Automerge handles this by treating the concurrently created list objects as distinct objects with different objectIds, and registers a conflict between the assignments of those objects to the key strokes:

// After merging concurrent creations of the strokes list:
pdfCard.strokes // strokes list created by actor1
pdfCard._conflicts.strokes.actor2 // strokes list created by actor2

This is awkward for the application to handle, since it would need to render strokes from more than one list object. A better approach would be for Automerge to somehow know that doc.strokes = [] is an initialisation, and to merge the concurrent initialisations rather than making a conflict.

Moreover, initialisation is not limited to empty objects. For example, an application may want to initialise the strokes list with some default strokes that read “you can scribble here!” or suchlike — serving as a kind of user tutorial that may be edited or deleted by the user. In that case, each instance of the application that creates the strokes list may also create the default strokes, but when we merge the concurrently created strokes lists, we only want to keep one copy of the default strokes, not duplicate them for each application instance that performed the initialisation.

How to do this? We don’t have a clear plan yet, but here are some initial thoughts:

• When creating an initialisation object, we don’t generate a random objectId as we normally do, but rather use a fixed objectId (so that all instances of the application create an object with the same objectId, and we then simply deduplicate the object creations with the same ID). This fixed ID could be the name of the key (here strokes), or a hash of that name, or some constant UUID that is hard-coded in the application. The default stroke objects would likewise need to be given such a predefined objectId. However, the application developer would need to take care not to accidentally reuse the same objectId for different purposes.
• What should the API look like? One option is to detect when we are assigning a new object to a constant path in the document (in the above example, the path is the constant key strokes under the root object; in other cases the assignment may occur in a nested object) and treating such assignment as initialisation. However, the default strokes are created under a non-constant path (since list element IDs are dynamically allocated), so some other mechanism would be needed to recognise default strokes as being part of an initialisation. Perhaps list elements that appear in the list literal are treated as initialisation, e.g. doc.strokes = [default_stroke1, default_stroke2] treats those two default strokes as initialisation.
• Another option for the API would be to treat initialisation explicitly differently from a regular change, e.g. by using a different function Automerge.initData() instead of Automerge.change(). However, application developers would need to learn when to use which function.

[HerbCaudill]

My intuition when starting to play with Automerge was that I could pass a starting value to Automerge.init:

const DEFAULTS = { strokes: [] }
const pdfCard = Automerge.init(DEFAULTS)

This would seem a lot more natural to me than having a separate initData method.

[ept]

@HerbCaudill Unfortunately this will not help in the case where the initialization needs to be performed on an existing document, since Automerge.init() is only called once, right at the beginning of a document's lifetime.

[lightsprint09]

@ept I could imaging that upgrading a document depends on an event like version bump. So as a developer I want to give this action a name eg

document = //
document = Automerge.upgradeToVersion("MyNextVersion", document, doc => {
  doc.strokes = [defaultStroke, defaultStroke2 ]
})

I would expect the multiple users could apply this change whit out getting duplicated version upgrades

[schickm]

I was thinking about the example that @ept gave of "strokes". What follows is how I think of the issue.

One way to generalize this problem is that parts of the document are data and other parts are schema. Schema is us wanting to express "this document has a key named 'strokes' that is a map", and the data is what's actually kept inside of that map.

All of the existing merging rules seem to work fine for data, but the stumbling block here is that people are looking for different merging rules when dealing with schema. The Table Custom CRDT type has already begun to model this separation a little with it's columns property. What columns a table has is really schema and therefore needs to be handled a little differently.

I don't have any concrete answers here, but this is just how I think about the difference here. It could be argued that considerations of schema is a higher order problem that maybe should be handled by some wrapper-library. Or, maybe schema is some enhancement that could be added to the document itself, similar to the columns in Table. Something like Automerge.changeSchema():

sharedRootDocument = //

// Alice
doc1 = Automerge.changeSchema(sharedRootDocument, doc => {
  doc.strokes = [];
})

doc1 = Automerge.change(doc1, doc => {
  doc.strokes.push([stroke1, stroke2]);
})

// Bob
doc2 = Automerge.changeSchema(sharedRootDocument, doc => {
  doc.strokes = [];
})

doc2 = Automerge.change(doc, doc => {
  doc.strokes.push([stroke3, stroke4]);
})

// And we merge
mergedDoc = Automerge.merge(doc1, doc2);
// and now we have this
// { strokes: [stroke1, stroke2, stroke3, stroke4]}

[ept]

@schickm Good thinking, I like the idea of treating initial setup as schema, and handling it differently from the data. Food for thought.

[mweidner037]

Yicheng Zhang, myself, and Heather Miller ran a programmer user study (https://doi.org/10.1184/R1/22277341.v1) where we observed a related issue: to make a "schema" {"cat": {}}, participants would start their app with

const doc = Automerge.from({"cat": {}});

or similar. But then each new device that joined would overwrite the existing state:

---

My own thoughts on the above discussion (not directly related to the user study):

General

I'm generally in favor of a rule that the object/array at a key implicitly "always exists" and can be used without first creating it. E.g., starting from doc = {}, you should be able to do

doc.animals.push("fido")

to yield the state { animals: ["fido"] }. If multiple users do so concurrently, it will merge their changes, since they're all changing "the same" array CRDT. So this implements the "merging behavior" described by @ept (https://github.com/automerge/automerge-classic/issues/4#issue-227073969).

Two problems with this rule:

1. Each object key now has multiple values: an object, an array, and potentially a primitive value. When we render the state to JSON, we need to know which of these to show (or nothing).
2. You don't always want the merging behavior; sometimes you do want to create objects/arrays explicitly, with LWW Register behavior - in case of concurrent creations, pick one.

Idea 1: Schema

One solution to the rule's problems is to use a schema that specifies the type at each tree node: (merging) object, (merging) array, LWW Register with object value, LWW Register with array value, LWW Register with primitive value, or nothing. You could then throw errors for operations that don't make sense. E.g. if doc.animals is a merging array, don't allow any of

doc.animals = []; // Can't create - always exists
delete doc["animals"]; // Can't delete - always exists
doc.animals = ["garfield"]; // Can't overwrite - mutate the existing array instead
doc.animals = 7; // Wrong type

(It does still make sense to delete merging objects/arrays that are list elements instead of values at an object key. In this case, I'm in favor of permanent deletion, ignoring concurrent operations, to avoid the JSON paper's weird example. Another perspective is that the deleted list element's CRDTs still exist, they just aren't rendered in the JSON state, since you skip them when looping over the list. If you "restore" the list element later, e.g. by undo, the CRDT will reappear in its old state + concurrent operations.)

Idea 2: Syntactic Sugar and Boxes

A second solution to the rule's problems, which doesn't require a separate schema, is as follows:

• Treat "create" operations like doc.animals = [] as syntactic sugar for "set the type of doc.animals to 'merging array'". That is, each key still has (1)'s multiple values, but there is a hidden LWW Register controlling which one to render. Likewise, delete doc["animals"] means "set the type of doc.animals to 'nothing'", so that it's no longer rendered (but the array CRDT still exists in its old state).
• If a dev instead wants (2)'s LWW Register behavior, they have to put the object/array value in a "box": doc.animals = boxed([]). Internally, the box would be treated like a primitive value, and each boxed() call would create a unique new object/array CRDT (like Automerge's current behavior).
• Alternately, instead of supporting (2)'s LWW Register behavior explicitly, teach devs how to emulate it using merging objects/arrays. E.g. in the billing_address example, JSON-encode the address object before storing it, so that one address wins atomically. Or, if you want the addresses to be internally mutable, use an array of objects like @adamwiggins suggested.

This solution feels more natural and makes it easier to change the "schema". However, it has some weird behaviors:

// Ex 1
doc.animals = [];
doc.animals.push("fido");
doc.animals = []; // Still { animals: ["fido"] } - you've just (redundantly) set the type to "array"

// Ex 2
doc.animals = ["fido"]; // Syntactic sugar for: set the type to "array", then push "fido"
doc.animals = ["garfield"]; // Now it's { animals: ["fido", "garfield"] }: set-type was redundant; pushed to existing array

// Ex 3
doc.animals = [];
doc.animals.push("fido"); // { animals: ["fido"] }
doc.animals = {}; // Changes type to object
doc.animals = []; // Now it's { animals: ["fido"] }: you've only set the type to array, revealing the old state

Perhaps it's less confusing to replace the syntactic sugar with an explicit setType function, e.g. doc.setType("animals", []). Then doc.animals = [] no longer means anything and can throw an error:

doc.animals = []; // Error: did you mean doc.setType("animals", []), or doc.animals = boxed([])?

doc.setType("animals", []); // Sets the type to "array", with merging behavior.
// Alt syntax idea:
// doc.animals = schema([]);

doc.animals = boxed([]); // Okay, but this won't merge with concurrently-set arrays.
                         // Maybe print a warning if you do it on the root object.

You can also give doc.animals = [] its current meaning again (LWW Register set). But then you'll run into the bug at the top of this post.