Change avoidance

[rnewman]

I wanted to spend a little time to thoroughly address an issue that we've briefly covered in the past.

We can call this "change avoidance". In short: how does a client in a client-server sync system avoid seeing its own changes without having to track per-client changes on the server, or switch to a replicated-truth system?

Let's introduce some very rough terminology. D[0], U[1] are server timestamps returned from downloads and uploads. C is the client's incremental window; on each sync it fetches changes since C.

A client either fetches changes first, then uploads its own, or it uploads then fetches. These are equivalent if you consider multiple syncs:

   UD   UD   UD   UD
    DU   DU   DU   DU

In either case, the next incremental download needs a starting point. That's the sentinel (effectively a timestamp) returned by the server on the last download.

The problem: the changes uploaded since that last download will have a stamp later than the sentinel.

So how do we avoid seeing those changes? More importantly, how do we avoid seeing those changes without missing changes uploaded by another client between our download and next upload?

There are a few options, which we can nickname: the ostrich, the chain, exclusion, and indication.

Firefox Sync takes the "ostrich" approach — head in the sand. It simply assumes that there are no racing changes, and fast-forwards its sentinel to the end of the upload. Any records changed between the end of the download and the end of its upload are missed.

    C = D[0]
                             # <<< Changes here are missed entirely.
    C = U[1]

The "chain": each write returns both the previous and current stamp. If the previous change stamp in the upload matches the client's download stamp, then the client knows it hasn't missed any changes, and can fast-forward. If it doesn't, then a range fetch can be done.

    C[d] = D[0]
    C[u], C[p] = U[1]

    if (C[d] != C[p])
      fetch(C[d], C[u])      # () range; fetch missing changes.

    C = C[u]                 # Fast-forward.

"Indication": in the results of an upload, the server returns some indication of changes that the client missed, or the changes themselves. This obviously requires that the client pass in C on each upload.

This is effectively the same approach as chaining but server-driven, much like our approach to pagination: the server checks to see if any changes happened between C and now, and indicates that in the response, rather than passing back the timestamps and requiring the client to figure it out.

You can effectively model this as upload = write + get.

"Exclusion": we know that each write returns a unique position on the monotonically increasing server clock. Because they're unique, we can exclude those in the next fetch.

    C[d] = D[0]
    C[u] = U[1]
    C[d] = fetch(C[d], exclude=C[u])

Note that this relies on the server returning records in the response to a write: otherwise a change from another device that we overwrite will never be detected.

Any of these last three would work for me. What do you folks think?

[rnewman]

A disadvantage of "strong indication" (i.e., return actual changes since) is that it's potentially surprising to a client to issue a small incremental write and get a large set of changes as a response.

[almet]

Richard, thanks for starting this discussion. The "chain" or "indication" methods sounds like the ones I would favor.

"Exclusion" seems a bit painful, and would require all the items to be stored at the exact same timestamp on the server side, which may not be what we do, depending on the backend. It also seem to be harder to understand / implement than the other approaches, so I would avoid it if possible.

The "strong indication" technique has, as you're describing, one shortcoming: it asks clients to do store something back when they actually are sending data, which is a bit counter intuitive.

The "chain" technique seems to be the most promising one: it requires the API to support range queries, but that's something we should provide anyway. We probably can mix these two approaches by returning an indication about the number of new items since the last C: this could help the client to display an indication on the client UX (like twitter does for instance).

[rfk]

Using If-Unmodified-Since to fail the upload if the client isn't up-to-date seems like a simplified version of the "chain" approach. IMHO this would be much simpler to implement on the client.

Theoretical downside: clients may be indefinitely blocked from writing if there's a huge burst of concurrent changes and they never manage to catch up. I'm not convinced this would ever be a problem in practice.

[rnewman]

Thanks for pointing out another option, Ryan!

An IMS-style approach seems less desirable to me; I'll try to explain why. Apologies for rambling.

I don't want to force a client to have to complete a full download in order to successfully issue a write. I expect the current Android client to do so, but I don't expect the iOS client to be able to do that.

Almost every operation in this API is non-conflicting, both due to the nature of the data and because the server resolves conflicts. That's bought us a high probability of success when writing.

Most clients, most of the time, will be either marking something as read, or adding a new item, and both of those will almost always succeed.

Having those operations fail and require a full download and re-upload because of a change to an independent record is kinda Sync-like, in a bad way — Sync expects you have to be finished downloading before you can upload, because that's the only way to handle conflicts (particularly structural ones), and you don't know if you have a conflict unless you download everything.

Here we expect almost fire-and-forget writes to the server, with records being totally independent and genuine conflicts rare. With the exception of tracking own-write windows (the subject of this issue), upload and download could be completely decoupled, and doing so is kinda desirable — even more so when we have push.

Something like indication — "add this range of clock values to your fetch list" — allows us to do just a small amount of bookkeeping, and otherwise write new items straight to the service. Boom!

[Natim]

This has been fixed here: mozilla-services/cliquet#432

So basically, when you are pushing records with the BATCH endpoint (and with a If-Match header) you can exclude the records ids for the following collection_get (with the If-Match header)

This prevent you from downloading changes you've just POST to the server.