Feature request: `amend` argument to mutation registration

[aboodman]

Problem

When writing realtime applications against Replicache, you frequently need to process mutations very very rapidly. For example, in response to mouse movements, where they events can come at a rate of 16/s or more.

I theorize that Replicache can actually do this fine without API changes (we will have to design an in-memory cache layer).

The problem comes when sending these events to the server. We end up sending tons of mutations that each have a tiny effect over the wire to the push handler.

The mutations will get gzipped presumably in the push request, and the push handler can dedupe them, or process them in a single transaction, so it's not entirely terrible. But it sure feels weird. And it's extra work (both for all the computers involved, and for the human who has to write code to dedupe events server-side) that isn't really serving any useful purpose.

Proposal

Add a new, optional amend function to register, so that it looks like this:

register<Return, Args>(
    name: string,
    mutatorImpl: (tx: WriteTransaction, args: Args) => MaybePromise<Return>,
    amend?: (a1: Args, a2: Args) => ?Args,
): (args: Args) => Promise<Return>

Usage

type MoveArgs {
  id: string,
  dx: number,
  dy: number,
};

register("moveShape", async (tx: WriteTransaction,  {id, dx, dy}: MoveArgs => {
  const shape = await tx.get(id);
  shape.dx += dx;
  shape.dy += dy;
  await tx.put(id, shape);
}, (a1: MoveArgs, a2: MoveArgs) => {
  if (a1.id != a2.id) {
    return null;
  }
  return {
    id: a1.id,
    dx: a1.dx + a2.dx,
    dy: a1.dy + a2.dy,
  }
});

Details

The amend function is optional. If specified, it takes same two sets of the same args that mutatorImpl takes and attempts to combine them. The function is only allowed to work synchronously, it doesn't have access to the db. The amending must be a function of only the two sets of arguments.

It is allowed for an amender to return undefined. In that case, it means amending could not be done.

It is up to the discretion of Replicache whether to call the amender at all. Typically this will be done for events very close in time to each other and between pushes.

The amender will never be called for mutations of different types. It will never be called for any two mutations except for two exactly sequential events on the main branch.

Processing Model

When Replicache sees a new mutation come in, it decides if it is a candidate for amending:

• happened on main branch?
• has an amend fn registered?
• happened very shortly after last mutation?
• last mutation is same type?

If a mutation is amendable, Replicache calls the registered amender with the two sets of args. If the amender function returns a new value, then Replicache removes the previous commit from history and replaces it with the mutation that was being processed except with its args replaced with the result of the amend function.

[aboodman]

This was a bad idea and I feel bad about it.

[aboodman]

To add more detail as to why this was discarded:

It's easy to see how this could be helpful for long strings of simple mutations. For example, if you have a mutation like moveShape(destX, destY) and you get two in a row, the correct impl for amend is just taking the second value. Similarly if moveShape() is defined to take deltaX and deltaY you can add the deltas as the summary suggests.

The reason we discarded this was that we quickly found a real world use case that didn't end up having strings of the same mutation: when drag and dropping an element in Replidraw, the mutation history looks like:

moveCursor
moveShape
moveCursor
moveShape
...

So amend as defined here wouldn't fire. A more complex definition of amend that fired in this circumstance would also be more complex for developer.

We have also seen since then other examples in customer apps that run multiple mutations in a single mouse move handler.

It's possible that if we had this optimization it would inceltivize developers to build mutators like dragShape that combined multiple logical operations into a single mutation, but then again, the impl gets more complicated.

Overall it didn't seem like enough of a win over just collapsing by running the mutations in sequence against memory on server-side, at least for now.

[aboodman]

(If we get to a point where this is shown to be blocking some design goal objectively I'd definitely reconsider)

[tslocke]

I'd really like to see this feature added.

I would like the API to provide my function with an array of all not-pushed mutations, and allow me to return a collapsed array.

I already have a mutation type that applies an arbitrary set of creates/updates/deletes of keyed values, so the implementation of this hook is essentially the same code that would collapse mutations on the server. It makes so much more sense to do it on the client.

A super common situation for many apps will be typing text. In most apps I would bet that typing triggers one mutation per keystroke, and that these are trivial to combine.

IMO good API design is make easy things easy, make hard things possible. You don't lose anything by adding this hook. Anyone can ignore it and be in the same situation as you're proposing above (gzip, collapse on server). In my case the cost/benefit of this optimisation is a very clear win, but right now it's impossible.

The caveats above could be included in the docs for this hook.

[tslocke]

It occurred to me that this is almost just the pusher hook.

But not quite, because that hook happens a little late in the process. The argument you get, if I'm understanding correctly, is an HTTP request that already has the push data bundled up in it. I feel like this hook would be a lot more useful if it was passed the push data and a function to post the data. i.e. the no-op implementation would be

pusher(data, postFn) {
  return postFn(data)
}

That would allow me to munge the data before posting, post it some other way than http, etc.

But I guess this is a breaking change...

[aboodman]

We want to change pusher to have the signature you propose, but that alone wouldn't suffice for amend.

Say the user typed "a", "b", "c" in mutations 1,2,3 respectively. At push time you can't collapse this to just mutation 1 because the client will assign 4 to the next mutation and the protocol relies on mutations being sequential, we can't skip any. You can't collapse to just mutation 3 for same reason.

You also can't edit the mutations (for example, to make 1-2 no-ops, and put a combined op in 3) because the server might have already seen mutations 1-3 on a previous failed push. Changing the meaning of a mutation after it has been created and possibly seen by the server would break other core invariants - user changes might run twice, or not at all. The protocol fundamentally relies on mutations being immutable.

In order for amend to work it has to run much earlier, before a mutation is shared with any other process. Now that I think about this, I'm actually not sure under what circumstances it would be safe to amend. Since this bug was originally written, we have several new parallel processes going on in Replicache that might see mutations after they are created - push (to server), persist (to disk), rebase, maybe others? Have to think through what it would mean to change a mutation in each of those circumstances very carefully.

I think this might be one of those cross-cutting changes that is complex because it touches everything and changes a fundamental assumption of the system - that the sequence of mutations is immutable.

===

Stepping back, for text, I am not so sure that amending is what you want at a product level. All the text CRDTs I have seen (eg peritext, yjs, etc) work by communicating each individual operation. That is how you get the best merge behavior. The more complex the operations, the more difficult to reason about merging them.

I think it makes a lot of sense to preserve each individual user intent and communicate them all separately. Applying a bunch of keystrokes against memory on the server is not expensive. HTTP compression will largely deduplicate the metadata, leaving just the user data -- same data that would be sent if you amend.

We have already used this system with e.g., Replidraw, which processes events at a rate of up to 120/s, and seen it work quite well. So it seems like it should work for your use case too.

[tslocke]

OK I buy all this. Thanks.

I realise the real solution for me is elsewhere in my stack. I am currently surfacing text edits as a stream of new blocks to replace old ones. What I should be doing is surfacing a stream of edit operations.

It's gets gnarly, because edits can cut across block and formatting boundaries in arbitrary ways. ProseMirror has great built in solutions for all this, but complexities in my app mean I can't use them out of the box. Something else for the to-do list : )