Enforcing delivery order of payloads

[robrichard]

Context

A naive implementation of defer/stream could simply race all available upcoming payloads and return the first one that is ready. This could lead to results where a payload is sent with a path that references a field the client has not received yet.

Decision

It was discussed in the 2021-07-01 WG meeting and 2021-12-02 WG meeting and the group agreed that responses like this must be ordered to ensure payload paths do not reference fields that have not been sent yet. Similarly, a streamed field result must not be sent before a result with a lower index.

Discussed again in the 2022-02-03 WG meeting and there was general agreement on the approach outlined below. This feels like the most conservative approach. There may be scenarios where we may be trading performance for making client digestion of payloads easier, but we could potentially look at that later.

Implementation

tl;dr: When executing a deferred fragment or streamed field, a reference will be passed around. Any downstream deferred fragments or streamed fields must wait for the parent to complete its execution before it can be completed itself. Additionally, subsequent items in streamed fields must wait for the prior item to complete its execution.

---

The GraphQL spec defines execution of a selection set via the ExecuteSelectionSet algorithm. In ExecuteSelectionSet, a group of fields are gathered using the CollectFields algorithm, before executing each collected field using the ExecuteField and CompleteValue algorithms.

Defer

Our proposal updates the CollectFields algorithm to detect fragments with @defer and separately execute their selection set by calling ExecuteSelectionSet with the selection set from the deferred fragment. Additionally a reference to the deferred fragment will now be passed to ExecuteSelectionSet, ExecuteField, and CompleteValue.

If a new deferred fragment is detected while executing the selection set from a previously detected deferred fragment, the execution of this new deferred fragment must not complete until the execution of the previous deferred fragment is complete.

This ensures results are delivered in a hierarchal order. It also ensures that it is not possible to receive a payload that contains a path reference to an object that has not yet been delivered.

Stream

Our proposal also updates the CompleteValue algorithm to detect list fields with the @stream directive. Values yielded by the underlying iterator on a streamed field are resolved with an additional call to CompleteValue.

If a deferred fragment reference is passed to CompleteValue, the first streamed value must not complete its execution until the execution from the deferred fragment reference is complete. Similarly, all subsequent streamed values must not complete their execution until the prior streamed value is complete.

This ensures the first streamed result is not delivered before the payload containing the list the streamed result belongs to. It also ensures that any subsequent streamed results are not delivered before prior streamed results.

Example A

query {
  person(personID: "3") {
    name
    ...TopFragment @defer(label: "DeferTop")
  }
}
fragment TopFragment on Person {
  homeworld {
    name
  }
  species {
    ...NestedFragment @defer(label: "DeferNested")
  }
}
fragment NestedFragment on Species {
  title
}

Let's say that that the person.homeworld field take longer to resolve than the person.species field. The result would be:

{
  "data": {
    "person": {
      "name": "R2-D2"
    }
  },
  "hasNext": true
},
{
  "data": {
    "title": "Droid"
  },
  "path": ["person", "species"],
  "label": "DeferNested",
  "hasNext": true
},
{
  "data": {
    "homeworld": {
      "name": "Naboo"
    },
    "species": {}
  },
  "path": ["person"],
  "label": "DeferTop",
  "hasNext": false
}

This means the client would receive a payload with the path ["person", "species"] before the species field is returned to the client.

In this case, a reference to the execution of ...TopFragment @defer(label: "DeferTop") will be passed to ExecuteSelectionSet and CollectFields when ...NestedFragment @defer(label: "DeferNested") is encountered. The execution of ...NestedFragment @defer(label: "DeferNested") will use this reference to ensure it is not resolved until TopFragment is complete.

Example B: deferred fragments that do not have a direct tree dependency

In this case, if NestedFragment is ready before TopFragment, it will not wait for TopFragment to be sent first. When CollectFields analyzes the selection set of person(personID: "3"), it will recursively traverse the fragment spreads. Therefore ...TopFragment @defer(label: "DeferTop") and ...NestedFragment @defer(label: "DeferNested") can be resolved in parallel.

query {
  person(personID: "3") {
    name
    ...TopFragment @defer(label: "DeferTop")
  }
}
fragment TopFragment on Person {
  homeworld {
    name
  }
  ...NestedFragment @defer(label: "DeferNested")
}
fragment NestedFragment on Person {
  species {
    title
  }
}

Example C - parent dependency can be resolved via another fragment

What if NestedFragment is ready before TopFragment, but after UnrelatedTopFragment? In this case, CollectFields will trigger execution of ...TopFragment @defer(label: "DeferTop") and ...UnrelatedTopFragment @defer(label: "DeferUnrelatedTop") in parallel, since they are siblings. CollectFields will encounter ...NestedFragment @defer(label: "DeferNested") only while executing ...TopFragment @defer(label: "DeferTop"), therefore the payload from this fragment will be its only dependency.

query {
  person(personID: "3") {
    name
    ...TopFragment @defer(label: "DeferTop")
    ...UnrelatedTopFragment @defer(label: "DeferUnrelatedTop")
  }
}
fragment TopFragment on Person {
  homeworld {
    name
  }
  species {
    ...NestedFragment @defer(label: "DeferNested")
  }
}
fragment NestedFragment on Species {
  title
}
fragment UnrelatedTopFragment on Person {
  species {
    id
  }
}

Example D - Stream payloads should be sent after parent deferred fragment

In this case, the field friends @stream(initialCount: 0) will be executed by CollectFields originating from a call to ExecuteSelectionSet for ...DeferFragment @defer. The first result from this streamed field must be returned after the payload for ...DeferFragment @defer.

query { 
  person(personID: "3") {
    ...DeferFragment @defer
  }
}
fragment DeferFragment on Person {
  slowField
  friends @stream(initialCount: 0) {
    name
  }
}

Example E - Stream payloads must not be sent out of order

Subsequent payloads from a @stream directive must not be sent before prior payloads from the same stream.

// Payload 1
{
  "data": { "id": "0" },
  "path": ["products", 0],
  "hasNext": true
}

// Payload 2
{
  "data": { "id": "1" },
  "path": ["products", 1],
  "hasNext": true
}

Status

• defined in spec
• implemented in graphql-js

[robrichard]

from @michaelstaib https://discord.com/channels/625400653321076807/862834364718514196/908330498441511033

we have anyway a different approach to execution than most GraphQL server. We have a two phase compilation of queries ...

So the query compilation will come up with a query execution plan that is being executed. So when we compile the query we essentially come up with separate queries for the execution engine that get inputs fed in ... essentially like functions.

While we might detect that a sub tree does not really have dependencies on the parent we will still keep the order in this case.

The question in these cases is if we could have a better perfomance if we executed and delivered it early to the client.

[yaacovCR]

graphql-executor, the customizable graphql executor based on graphql-js, now supports incremental delivery with preservation of payload order for defer (a) and stream (d), allowing early send with nested non dependent defer (b) but not for resolution of field from another branch as in (c).

[robrichard]

defer-stream branch does the same

[BoD]

A related question: does this also mean that for @stream we should always expect payloads to be ordered in respect to list indices? That is, for instance, the following sequence would not be permitted?

Payload 1:

{
  "data": {
    "id": "1"
  },
  "path": [
    "products",
    1
  ],
  "hasNext": true
}

Payload 2:

{
  "data": {
    "id": "0"
  },
  "path": [
    "products",
    0
  ],
  "hasNext": false
}

(receiving products.1 before products.0)

[robrichard]

Yes, I updated the description with an example of this

[BoD]

HI! I am experimenting with @defer with graphql-helix, which uses graphql-js version 16.0.0-experimental-stream-defer.5, and I am receiving payloads in an unexpected order, e.g. first ["computers",0,"screen"] and then ["computers",0].

• Am I correctly understanding that it should not happen?
• Kind of a tangent but I thought to try with a more recent version of graphql-js, in case this was implemented later. The latest I can see is 16.1.0-experimental-stream-defer.6 but with it I'm getting Unknown directive "@defer" 🤔

[robrichard]

Yes, i think this was fixed after 16.0.0-experimental-stream-defer.5 was published. We haven't been publishing new experimental-stream-defer releases but npm install --save graphql@canary-pr-2839 should get you the latest

[BoD]

Thanks a lot! However with this I'm also getting Unknown directive "@defer". I must confess I'm not well versed with npm at all - but just triple checked and with 16.0.0-experimental-stream-defer.5 I don't get this error but I do with canary-pr-2839. Any idea?

[robrichard]

@BoD is the code public somewhere that I can troubleshoot locally? It's possible there's a bug or a case that I missed.

[BoD]

Yes, I've just pushed what I'm testing with on this repo. Thanks a lot!

[robrichard]

@BoD There was a bug where it was not being ordered correctly with synchronous data. I pushed up a fix and a test case to the defer-stream branch.

Unfortunately, it doesn't seem like the canary builds are working at the moment, so I'm not able to publish a new version to npm.

If you want to apply the fix locally to unblock yourself, update this at the bottom of node_modules/graphql/execution/execute.js,

-if ((0, _isPromise.isPromise)(parentData)) {
-  return parentData.then(() => this.data);
-}
+if (parentData) {
+  return Promise.resolve(parentData).then(() => this.data);
+}

[BoD]

Glad to hear it! Thanks a lot for the follow-up and quick fix!

[hwillson]

@IvanGoncharov is looking into the canary stuff 👍

[quinndev4]

@robrichard great write up here. I think this completely makes sense for the defer and stream directives to ensure parents have been delivered before an incremental update is delivered.

However, I have some questions on this part:

Similarly, a streamed field result must not be sent before a result with a lower index.
...
It also ensures that any subsequent streamed results are not delivered before prior streamed results.

This helps to explain a "problem" I was running into. I was under the assumption that the @stream directive would deliver list items to the client whenever all necessary fields were resolved. So the order of the list seen by the client would be the order of resolution on the server side. Here is an example illustrating what I am talking about:

const resolvers = {
  Query: {
    slowUsers: () => {
      // Simulate slow response for testing @stream

      return users.map(
        (user, index) =>
          new Promise((resolve) => {
            setTimeout(() => resolve(user), index === 0 ? 20000 : index * 1000);
          })
      );
    },
  },
};    

In this example, the @stream directive is effectively useless since the first item will take 20 seconds to resolve even though subsequent items will resolve much quicker. Why can't whatever item is ready first be sent with index 0? Then the next ready item is sent with index 1 and so on until the first item resolves at the last index. The client doesn't know anything about the order of the array anyways, for all we know it could be randomly sorted on the server before returning.

Im just curious on why the list order must be preserved when using @stream. Is there something I am missing here?

Side note: Any tips on how to implement the desired functionality that I discussed (returning items to the client in resolve order and not the arbitrarily defined array order) would be greatly appreciated.

[robrichard]

@quinndev4 I think there are many cases where array order is significant and if the GraphQL server reordered lists, the client would be losing that important information.

If in your case list order is not important, I think what you're describing could be achieved in application code, perhaps with something like Promise.race() in a loop in an async generator function?