988631 - User records should be sorted by (generation, created_at, uid) rather than just (created_at, uid)

Status: RESOLVED FIXED

(Cloud Services Graveyard :: Server: Token, defect)

Description

[Ryan Kelly [:rfkelly]]

We currently resolve any user-record-creation races by sorting on (created_at, uid) and picking the first row as current.  Hypothetically, a particularly bad combination of client- and server-side races could produce a situation like this:

    uid | generation | client_state | created_at | replaced_at
    ----------------------------------------------------------
     21         1201           bbbb         5678          NULL
     22         1200           aaaa         5679          NULL


Here a client with an old generation number races a client with a new generation number and happens to win.  The updated client_state value is now recorded as having been previously seen, but not current.  The next time an up-to-date client goes to sync, it will get an invalid-client-state error and there's nothing it can do to dig itself out, short of resetting the account.

We should prioritize generation number over created_at timestamp when ordering the rows.

I could just add it to the index and ORDER BY clause, but that makes the index bigger for a case that's vanishingly unlikely in practice.

An alternative may be to re-sort the list of rows in the app, ensuring the newer generation numbers get put in front.  This would add a bit of runtime overhead but will be approximately linear in the usual case, because:

  * the rows will almost always be in the correct order already, and
  * python's sort function is linear on already-sorted lists, and besides
  * we slurp in at most 20 rows anyway

Comment 1

[Toby Elliott [:telliott]]

Per the previous bug, you already have tools to detect the double-non-replaced_at records. It should be trivial in that situation to simply pick max(generation) as the one to not fix.

Comment 2

[Ryan Kelly [:rfkelly]]

*nod*

Yeah, resolving this in the app seems better than trying to enforce it with extra columns in the index.

Comment 3

[Ryan Kelly [:rfkelly]]

Note to self: we may also need to adjust the REPLACE_USER_ROWS queries so that they don't mark rows as replaced if they have a greater generation number than the newly-inserted row.

Comment 4

[Ryan Kelly [:rfkelly]]

Attachment: ts-sort-by-generation-number.diff

I considered a few shortcuts here, e.g. only resolving the non-replaced rows based on generation number.  It doesn't feel safe to me once you throw something like node re-assignment into the mix, which can mark rows replaced without client intervention.  Even when *all* rows are marked as replaced, we need the higher generation numbers to win out.

Ultimately, we expect generation number to be a temporal ordering over client states and we should treat it as such.  We can do it at the app level like this patch, or by adding another column to the db index.  But IMHO we need to do it properly one way or the other.

Comment 5

[Ryan Kelly [:rfkelly]]

Attachment: ts-sort-by-generation-number.diff

Updating the patch with a second test-case that throws a node-reassignment into the mix.

Comment 6

[Ryan Kelly [:rfkelly]]

https://github.com/mozilla-services/wimms/commit/de9af42d45f66348a9b2d50a887a7ca629502aa2