Relay: pending optimistic updaters always run after local updaters

[mattkrick]

Simplest scenario:
let's say S0 = 1
then, i optimistically update it S1 = 2
then, i update it locally S2 = S1 * 2

the result should be 4, not 2.

the culprit is here RelayPublishQueue.prototype.run:

    this._commitData();
    this._commitUpdaters();
    this._applyUpdates();
    this._pendingBackupRebase = false;
    this._store.notify();

it's easy to see if you write it in transforms:

T1 = (state) => 1
T2 = (state) => 2
T3 = (state) => state * 2

the publish queue is running T1, T3, T2 that ain't right.

we should fix this before the client schema API leaves beta

[mattkrick]

While attempting a PR, I noticed relay implicitly only supports convergent data types. Why is that?

I didn't see this documented anywhere, but it's pretty huge. That means the updater method CANNOT create a new value based off of the value in store. In real life, this is critical for computing things like cursor offsets (and client caches :wink:).

For example, let's say your updater is a transform:
updater = (state) => state < 0 ? state * -1 : state + 10
If the mutations don't return in order, your state is borked!
let's say the above is called with 1, -1, -1 (primes denote optimistic responses):

S0 = 0
S1' = S0 + 10 = 10
S1 = S0 + 10 = 10
S2' = S1 * -1  = -10
S2 = S1 * -1 = -10 
S3' = S2 * -1 = 10
S3 = S2 * -1 = 10

That's pretty great! But what if the 3rd mutation returns first?

S0 = 0
S1' = S0 + 10 = 10
S2' = S1' * -1 = -10
S3' = S2' * -1 = 10
S3 = ((S0 * -1) + 10) * -1 = -10 // uh oh! we applied S3, then S1' then S2'
S1 = (S3 + 10) * -1 = -10
S2 = S1 * -10 = -10

We ended up with the wrong answer!

I propose computing the transforms in order :

S0 = 0
S1' = S0 + 10 = 10
S2' = S1' * -1 = -10
S3' = S2' * -1 = 10
S3 = S2' * -1 = 10
S1 = (S0 + 10) * -1 * -1 = 10
S2 = S1 * -1 * -1 = 10

The reason I typed out all the boring math is so you can see that not only is this accurate, but it comes at no performance penalty (add up the +,* symbols in each approach). We're not increasing memory or CPU cycles, we're just changing the order of operations. This is exactly how it's done in https://github.com/mattkrick/redux-optimistic-ui/blob/master/src/index.js

[mattkrick]

@dminkovsky OK now i'm intrigued. what exactly are you trying to do where you explicitly need to violate Lamport's happened-before relation? It's the foundation of distributed systems engineering, so saying it doesn't work for you is kinda a big deal! There are only 2 conditions that I can imagine where this could break your app:

• your updater method has a non-idempotent side effect
• your updater method has an explicit dependency requiring that it _not_ run in the order that it was called (eg you call an optimistic update, then call a local update 10 seconds later & not only expect the local update to occur first, _but expect the optimistic update to be based on the result of the local update_)

I'd hope that we can agree both are pretty bad ways to write code!
The above boring math proves that relay breaks both the laws of transitivity and antisymmetry. I don't think that's really up for debate, but we can certainly debate whether relay should fix it (I think they should :smile:)

Feel free to post what you're trying to accomplish & I'll walk you through how it would work with the queue proposed in #2482

[mattkrick]

Here's what your code should look like. No serializing to JSON on every keystroke, no using relay private internal methods. No 100 lines.

  update({to, body}) {
    commitLocalUpdate((store) => {
      const message = store.get(this._id)
      message.setValue(to, 'to')
      message.setValue(body, 'body')
    })
  }

  persist({to, body}) {
    this._environment._network.execute(mutation(), {to, body}, {force: true})
  }

note that since you're ignoring the server response, you actually don't even need this PR. I'm betting you wrote that bit of code before client schemas were a thing so you were basically using optimistic updates in place of local updates. Unless this is part of a collaborative editing. Then this PR will really help you since you'll be able to use lamport timestamps to merge edits from other collaborators.

[mattkrick]

but I am not sure how using a local schema would help me here

honestly, you're overcomplicating something that's pretty simple: it's just 2 controlled inputs. there should only ever exist 1 optimistic update for 1 server update. if that's not the case, you're doing it wrong.
just try using local updates.

[mattkrick]

you're adding or replacing an optimistic update every time update is called. yes, you only have 1 at a time, but you're using relay internals to create & replace it multiple times before a single server mutation is even triggered. That's not great.

Let's use a simple example. You've got a basic input field & its state is stored in relay. you persist it to the server every 5 seconds so the user don't lose their progress.
They're typing the word "Cat". They type a "C", then they type an "a", then they pause for 5 seconds, so it sends that off to the server, then they type "t", then the server replies with "Ca". If you accept the new state, then they those their "t". I _think_ that's the basic problem you're trying to solve.

S0 = ''
S1 = 'C'
S2 = 'Ca'
S3 = 'Cat'

Now let's break it into transforms (' denotes optimistic, * denotes local update)

T1* = (state) => state + 'C' 
T2* = (state) => state + 'a'
T2' = () => 'Ca' // 5 seconds is up! send it to the server
T3* = (state) => state + 't'
T2 = () => 'Ca' // server responded!

Using relay today, server data runs first, then local, then optimistic. Let's see how that plays out:

• T2' gets reverted
• T2 runs = 'Ca'
• Then T1* runs = ' CaC'
• Then T2* runs = 'Caca'
• Then T3* runs = 'CaCat'

Using my PR, let's see what happens:

• T2' gets replaced by T2
• T1 runs = 'C'
• T2* runs = 'Ca'
• T2 runs = 'Ca'
• T3 runs = 'Cat'

You get exactly what you wanted, and you didn't have to hack the relay internals to do it. I really hope that makes sense!

[mattkrick]

BONUS:
What I implemented is not new or novel. To learn more, you can read up on communicative data types:
https://github.com/ljwagerfield/crdt
http://jtfmumm.com/blog/2015/11/17/crdt-primer-1-defanging-order-theory/
http://digitalfreepen.com/2017/10/06/simple-real-time-collaborative-text-editor.html

The bulk of the PR is only ~200 LOCs: you seem to know your stuff about how the current publish queue works, so it should be pretty easy to grok: https://github.com/mattkrick/relay/blob/6b1196a52efccbc89d5743345c92aa779b61bca2/packages/relay-runtime/store/RelayPublishQueue.js

Alternatively, here's how optimistic updates are handled in redux in just 70 lines: https://github.com/mattkrick/redux-optimistic-ui/blob/master/src/index.js#L20-L93

[kassens]

I need to find more time to read through all the comments here, but I think the current issue is in documentation rather then behavior.

• commitUpdate sends a mutation request to the server.
  
  
  
  • If it has an optimistic update, we use that to present a best guess to the client for a request that's still in flight to the server.
  
  
  • on server response, the optimistic update is dropped, we now apply the actual response to the client as source of truth
  
  
• commitLocalUpdate: just writes a value as source of truth. It can be used for client schema extensions or cases where maybe a non-GraphQL request was made to to update the server in some integration case with a legacy system.

Now, if a client sends 2 mutations to the server that are both increasing a counter, one +2 and another +3, these requests are both in flight the optimistic updates are stacked as +2, +3. If either of them returns, the optimistic changes are rolled back, the server response is applied as the source of truth and the other update is re-applied as the best guess on top of the new confirmed server value.

Now, there are situations where the end result depends on what is applied first. The easiest example is "set to 1" and "set to 2" mutations. If the client sends both of them in parallel, we might not even know what's the correct end result in case one mutation takes longer somewhere!

Relay Classic used to have a "mutation queue" and a "collision key" that queued up mutations that might change conflicting data. This didn't make it into the simplified modern impleentation as the "correct" solution really depends on the product. What if an intermediate mutation fails? Should subsequent mutations still apply? Should mutations in the middle maybe be dropped (could be useful if it's updating the most recent saved state)?

The hope here with the modern redesign was that the API offers enough primitives to build an abstraction on top of that. If you have a use case that queues up mutations in some way, maybe that could be expressed as a sharable utility module?

Sorry it's getting late, but I hope this helps folks here understand some of this design. We should see if we can incorporate some of this into the docs!

[mattkrick]

hey @kassens thanks for the input!

Here's where there be dragons:

If the client sends both of them in parallel, we might not even know what's the correct end result in case one mutation takes longer somewhere!

it's javascript, things don't happen in parallel, 1 thing always happens first. Even if 2 mutations are sent in the same batched payload, 1 will get called before the other, and as a front-end developer, I get to decide which! In my PR, that order is preserved. so if operation A' happens, then operation B', then operation B returns before operation A, you should apply A', then apply B, then when A returns, you can commit them both. No "best guess" needed!

when you get the time, please check out PR #2482. feel free to reach out by email or video chat if you wanna discuss offline. I'll be in SF tomorrow & thursday if in-person is easier.

[kassens]

Network requests do happen in parallel:

• send request A: set to "foo"
• send request B: set to "bar"
• request B returns with "value is bar now"
• request A returns with "value is foo now"
  What is the real value in the end that the client should display? In Relay newer values override older values, but that might not be correct here. The only way to be sure is to wait with sending B when A completed.

[mattkrick]

The only way to be sure is to wait with sending B when A completed.

Not necessarily! You don't need to wait, you simply need to wait to commit. Lamport's happened-before relation guarantees it.

In Relay newer values override older values

Yes yes yes 100% yes. Relay has a built-in race condition. Now that we agree on that, let's kill it!

Using your example, here is how you fix it:

• send request A => apply A
• send request B => apply B
• request B returns => apply A, apply B
• request A returns -> commit A, commit B

Please continue to ask any questions or reach out if you'd like to do a live code review of #2482. Once you grok how it works, it'll make working with distributed systems much, much easier.

[dminkovsky]

@mattkrick hey thanks for your feedback. I removed my comments to clean up the thread.

[mattkrick]

@dminkovsky sounds good! if you like the PR feel free to make some noise on it, it's been stonewalled for a couple months now :disappointed:.

[josephsavona]

I've replied extensively on the associated PR, so I'm going to close this issue just to consolidate discussion.