Subject: [Jmap] Reverse-chronological ordering of pages of /changes?

From: Neil Jhaveri <[email-masked]>
Date: Wed, 4 Jul 2018 18:59:55 -0700

Continuing the discussion from the prior thread…

> On Jun 8, 2018, at 7:13 PM, Neil Jenkins wrote:
>> On Thu, May 31, 2018, at 13:46, Neil Jhaveri wrote:
>>> 4.2. /changes
>>> ...
>>> 
>>>    o  *newState*: "String" This is the state the client will be in after applying the set of changes to the old state.
>> If an offline client is resynchronizing after being disconnected and there are a lot of changes, the way that /changes is set up seems to imply that if the changes don’t all fit in 1 response, the sequence of responses will be ordered oldest-to-newest. Is that true?
> 
> It's technically not required, but it is most likely for ease of implementation, yes.
> 
>> If so, and assuming most clients are fairly naive and just immediately dispatch /get’s on IDs that they retrieve (perhaps by back-reference), that isn’t ideal for a UI that shows objects in newest-to-oldest order, potentially resulting in a user experience of “here are new objects from 5 days ago”, followed by “here are new objects from 4 days ago”, and so on. When really, the user ideally would prefer to see “here are objects from right now” as the first screen update — at least for e-mail, I think this is the case.
>> 
>> Have we had any discussion around handling pages of changes in a different way? For instance, the Gmail API <https://developers.google.com/gmail/api/v1/reference/users/history/list> has a Users.history : list resource, which takes a “startHistoryId” as well as a “pageToken”. The response includes a “nextPageToken”, or null if there are no additional pages. Clients only update their local “historyId” after fetching all pages.
> 
> Just to clarify, the Gmail API pages data in reverse chronological order here?

No, to my disappointment. I’m working on a project that uses it, and even with push, updates are often really big for desktops/laptops (which go into sleep and can remain disconnected for a long time), so the deficiencies of processing changes strictly chronologically becomes pretty apparent. It’s not as much of an issue in practice on mobile, since those devices don’t tend to actually disconnect. My interest in this behavior is specifically driven by past experience writing for desktop platforms. I just cited the Gmail API as one possible design that could allow for reverse-chronological paging of changes, even if their implementation doesn’t do it.

There is another production example — Microsoft’s Exchange Web Services Managed API return changes in reverse chronological order inside SyncFolderItems. It’s explicitly documented <https://docs.microsoft.com/en-us/exchange/client-developer/exchange-web-services/mailbox-synchronization-and-ews-in-exchange> that Microsoft made this change for Exchange Server 2010 and newer (previously, it was chronological). They added this functionality and didn’t change their API of just taking an opaque SyncState string (which can get quite long, so it’s probably encapsulating all information necessary to do this).

> If you do it in reverse order you might run into issues like a message being both modified and then deleted. If you see the deleted in one page then modified in a future one, you need to have kept track that the deleted is actually the most recent (so you must have kept some data around for the deleted item). That's a bit messy. 

I think this requirement could be avoided if the server coalesced changes before returning them from /changes, even if there are multiple pages. That could be a good optimization in general, because it’s probably common to see an addition followed by a modification (e.g. “message read” from a phone). Of course, that means the server has to do additional processing before returning changes.

> And of course there's also the problem of what happens if the state on the server changes while you are paging in the data. Not a problem if you are going in forward chronological order, you just keep going.

I’ll discuss this a bit more below in the proposal.

> 
>> A client could do a /query to get the absolute most recent page of items, merge that into it’s cache, and then handle /changes normally in order, but this seems a little less efficient.
> 
> For a client with partial cache (e.g. online client, probably most mobile clients) you will be using /query  to determine the subset of messages you are interested in. When a change occurs (you get a push notification), the strategy I'm currently using on our FastMail JMAP UI that's in development is the following:
> * Email/queryChanges the current list in view, max-changes 25
> * Fetch the threads/messages in the "added" response of the /queryChanges result using back references.
> * Email/changes
> * Thread/changes
> * Mailbox/changes + fetch changed using back references.
> This is all bundled in a single JMAP request. This allows new messages to be shown and deleted ones removed, and mailbox unread counts to be updated all in a single round trip. A second round trip fetches any flag or mailbox changes for messages in view that the /changes response indicated are out of date. This is a much smaller visual change and generally a little less important than new mail, so delaying one round trip is reasonable, and allows you to not fetch changes for messages you don't care about.
> 
> If there have been more than 25 changes (the max I specified), the /queryChanges fails and I retry again this time with a much higher max changes, but without the backreferences fetching the messages/threads. Once my list is up to date, I can then fetch exactly the messages I need in the visible section: total time 3 round trips (including the failed initial /queryChanges), but for a rare case (especially because we have push, most updates are small).
> 
> If you have a complete cache offline, you would instead probably use a slightly different strategy. To do the initial sync I would start with a single /query with a filter of null, sorted date descending. This is your list of all messages in the account. To do your initial sync, you would fetch the list, probably a page of say 500 ids at a time, and simultaneously start fetching the messages in order (so you get the newest ones first), until you have a complete set. 
> 
> When a change occurs (you get a push notification), you can then do:
> * Email/changes (max-changes 25) + back references to fetch the email headers of the added/modified messages
> * Mailbox/changes + fetch changed using back references.
> * Email/query filter=null sort=date-descending position=0 limit=50
> This will return all the changes to the emails if fewer than 25 have changed. If there are more changes, you can just keep repeating the /changes call until you have them all. To make sure you present the newest stuff quickly though, the /query fetches the list of the newest 50 Email ids.. You can look at these and start fetching from the top any that you don't have before you get to them in the /changes. It's a little more work, but not that much more work (depending on your data store architecture I suppose).

> Does this sound reasonable to you?

Yeah, this is the strategy I was mentioned as an alternative. It works, and I agree it wouldn’t be that hard for a client to do this, but there are some downsides without server support:
1. The /query response is ultimately wasted and redundant with ID’s (eventually) returned by /changes, either in the same or a subsequent call.
2. I don’t see a way to execute this strategy and also fetch the first page of messages in a single round trip to the server. If you fetch the results of the /query with backreferences, you may waste bandwidth fetching unnecessary messages (e.g. if there’s only 1 new message). If you fetch the results of /changes with backreferences, those may be old messages that aren’t the top priority. If you bandwidth is a concern, you have to do it in 2 round trips.

I think in practice, this is more of a concern for the desktop-platform clients. Mobile platforms tend to always be connected, while desktop platforms are frequently disconnected for days. 

>  If not, or if it's just suboptimal, can you detail more what you want to be able to do (and maybe what that might look like at the API level)?

To support this, a call to /changes will need to encapsulate:
1. What state the client is coming from
2. What partial state the client has already consumed (so a server can figure out what’s already been sent to the client)

There’s many ways it could be done, but I like the idea of making it very explicit, and suggest the following API changes (along with a note mandating the newest—>oldest behavior):

1. Add *untilState*=“String”|null to the /changes argument list.
2. Add *pageNumber*=“Number” to the /changes argument list. 
3. Replace *hasMoreChanges* with *pageCount*.

This is how the synchronization flow might work:
- When a client makes a request, it makes it with sinceState=x, untilState=null, and pageNumber=1. 
- The server then loads all of the relevant changes between x and the most current state, orders & coalesces them, and returns the first page, along with a newState property.
- When a client receives a /changes response, the *newState* property is echo’d back in subsequent /changes calls as the *untilState* parameter, with pageNumber=2 (if applicable). The server loads the changes in the [x, newState] range, repeats the ordering/coalescing process, and returns the second page of changes. Or more ideally it draws the page from a cache.

This strategy would allow a client to fetch the first page of changes, ordered newest—>oldest, and also fetch those items by back reference, all in a single round trip — executing highly effective/relevant first round trip in the case that the client has been disconnected for a while and there are many changes.

One issue with this approach, which you noted above, is how to optimally receive new changes while the client is in the process of paging in changes. Right now, if a push is received while a client is currently paging in changes reverse-chronologically, the client would have to just wait until it finished paging the changes it was working on, and then request new changes. That’s unfortunate, but actually not any worse than just consuming changes chronologically. I can’t think of a solution that isn’t terribly complex at the API level, and since it seems pretty rare, I would suggest we just live with it.

This definitely adds complexity, though. I’m curious if anybody else thinks this is sufficiently valuable to justify the complexity?

---

From: Neil Jenkins <[email-masked]>
Date: Thu, 05 Jul 2018 20:14:55 -0400

> 2. What partial state the client has already consumed (so a server can figure out what’s already been sent to the client)

You're right, this is not actually difficult to do. Thinking about this, because the state string is opaque to the client there's really nothing to stop a server doing this without making any changes to the API. (It can still be a very short state string too; I've no idea what MS does to end up with apparently several kilobytes long state strings sometimes with Exchange!) I've created a pull request <https://github.com/jmapio/jmap/pull/225> to add the following section to the /changes description:

---

If a record has been created AND updated since the old state, the server SHOULD just return the id in the *created* list, but MAY return it in the *updated* list as well.

If a record has been updated AND destroyed since the old state, the server SHOULD just return the id in the *destroyed* list, but MAY return it in the *updated* list as well.

If a record has been created AND destroyed since the old state, the server SHOULD remove the id from the response entirely, but MAY include it in the *destroyed* list, and if so MAY also include it in the *created* list.

If a *maxChanges* is supplied, or set automatically by the server, the server MUST ensure the number of ids returned across *created*, *updated* and *destroyed* does not exceed this limit. If there are more changes than this between the client's state and the current server state, the server SHOULD generate an update to take the client to an intermediate state, from which the client can continue to call *Foo/changes* until it is fully up to date. If it is unable to calculate an intermediate state, it MUST return a `cannotCalculateChanges` error response instead.

When generating intermediate states, the server may choose how to divide up the changes. For many types it will provide a better user experience to return the more recent changes first, as this is more likely to be what the user is most interested in. The client can then continue to page in the older changes while the user is viewing the newer data. For example, suppose a server went through the following states:

    A -> B -> C -> D -> E

And a client asks for changes from state `B`. The server might first get the ids of records created, updated or destroyed between states D and E, returning them with:

    state: "B-D-E"
    hasMoreChanges: true

The client will then ask for the change from state `B-D-E`, and the server can return the changes between states C and D, returning:

    state: "B-C-E"
    hasMoreChanges: true

Finally the client will request the changes from `B-C-E` and the server can return the changes between states B and C, returning:

    state: "E"
    hasMoreChanges: false

Should the state on the server be modified in the middle of all this (to `F`), the server still does the same but now when the update to state `E` is returned, it would indicate that it still has more changes for the client to fetch.

Where multiple changes to a record are split across different intermediate states, the server MUST NOT return a record as created in a later response than one which gives it as updated or destroyed, and MUST NOT return a record as destroyed before a response that gives it as created or updated. The server may have to coalesce multiple changes to a record to satisfy this requirement.

---

I prefer this to adding extra arguments to /changes as it keeps the API (and client implementation) simpler, while giving servers more flexibility (for example, if Gmail were to implement JMAP I'd imagine it would be easier for them to do so in a way that's closer to their proprietary API). For some types, it may also actually make for a better experience to return oldest changes first.

Does this look like reasonable to you? Describing this clearly is hard, so any suggestions for improving the text are welcome!

Neil.

---

From: Neil Jhaveri <[email-masked]>
Date: Thu, 5 Jul 2018 19:45:23 -0700

> On Jul 5, 2018, at 5:14 PM, Neil Jenkins <[email-masked]> wrote:
> 
> You're right, this is not actually difficult to do. Thinking about this, because the state string is opaque to the client there's really nothing to stop a server doing this without making any changes to the API. (It can still be a very short state string too; I've no idea what MS does to end up with apparently several kilobytes long state strings sometimes with Exchange!)

Okay, that certainly works, and after reading the exact text, I agree it’s the best way forward. It’s very simple, is consistent with what EWS is already doing,  and it leaves the possibility for a highly motivated server to solve the “new update after the client has already started paging in old changes” problem, as well, by encoding the exact consumed content into the state string. So that is good, and I’m very happy with this approach.

> I've created a pull request <https://github.com/jmapio/jmap/pull/225> to add the following section to the /changes description:
> 
> ---
> 

I think that covers all of the coalescing cases nicely.

> Does this look like reasonable to you? Describing this clearly is hard, so any suggestions for improving the text are welcome!

Yeah! I think this language works really well and read very cleanly to me. 

Thanks, Neil!

> 
> Neil._______________________________________________
> Jmap mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/jmap