Totally order sessions using a permslip-assigned timestamp #91

This is a writeup of an idea originally due to @andrewjstone, and an elaboration of its (simplifying!) consequences on sush, in particular how it can supersede and dissolve the vast majority of the complexity described in #79.

Everything that happens on the rack has to assume that there is no global total ordering on events, which stems from the fact that we need to be able to operate in the absence of NTP. This is partially ameliorated by several distinct mechanisms:

1. Jobs: within a session are totally ordered by their hash-chain, which ensures not only consistent linear execution ordering, but further that this order agrees not with the order in which the jobs were submitted to the rack, but the order in which the jobs were authorized by permission slip.
2. Other messages: within a causal "universe" established by Rumors, all messages have a comparable causal version, so every message can meaningfully be said to have happened before, after, or concurrently to every other message within that causal universe. Intra-rack network partitions, in particular those which occur from the moment of rack cold boot, can cause the rack to (temporarily) contain more than one such causal universe, because in a partitioned state, two (or more) separate Rumors gossip networks will bootstrap concurrently. Any messages sent while the rack is in such a state cannot be meaningfully compared with one another; their causal versions should be treated as always concurrent, because they have no common causal ancestor. As soon as such a partition is resolved, Rumors will collapse the two co-extant causal universes into one by obliterating the one which has the lesser number of events (to an approximation, see Version::min_ticks) and propagating the contents of the causal universe with the greater number of events to those other nodes.
3. Session starts in particular: the establishment of a session is represented by just such a message in the gossip set, and so sessions are ordered at most causally relative to one another, and in the presence of a network partition, may not be at all.

These properties induce a hierarchy of comparability, wherein cross-comparing jobs between causal universes is always concurrent (i.e. there is no ordering, not even partial), cross-comparing jobs between sessions in the same causal universe is potentially concurrent (i.e. there is a partial ordering between sessions, which means two jobs could be concurrent if they come from concurrent sessions), and comparing jobs from within the same session is never concurrent (i.e. there is a total ordering within a given session, given by the hash-chain assigned by permission slip).

This hierarchy makes it rather difficult to enforce the property "jobs execute at most once" by maintaining what we call a boundary file, because we should like such a file to both be (1) constant size, and (2) enforce this guarantee regardless of partition turbulence within the rack. The details of why this is difficult, and a potential complex solution to ameliorate these issues, are described at great length in #79, and I won't reiterate them here.

But the key thing to notice is that these difficulties are all directly or indirectly induced by the fact that we cannot establish a total ordering on all jobs, anywhere, ever. If we could, we could simply keep track of the last job we've executed (a constant size datum), and refuse to execute jobs before it, thus fulfilling in a very simple way the desiderata for our boundary file. Further notice that the reason we can't establish a total ordering on all jobs, anywhere, ever, is that we lack reliable timestamps in the rack, which means we cannot order all jobs relative to one another by timestamp.

Solution:

Outside the rack, however, we do have the ability to assign a timestamp reliably: permission slip absolutely has access to the current time, and it could include the current 64-bit Unix timestamp in the data hashed into the session ID. We do not need to timestamp every job, because jobs within a session are already totally ordered; we just need to order all sessions totally, regardless of their causal ordering within the rack — using permslip as an external timestamping authority achieves precisely this.

Alternatives considered:

• The original suggestion from @andrewjstone was not timestamps, but sequence numbers, which would work if there was only ever to be one canonical permslip instance. However, @emilyalbini brings up that we don't necessarily want this, because we may wish for sush to live in its own permslip, with its own separate administrative access and SLA, and @plotnick further notes that sequence numbering introduces a hazard in the case that the database is corrupted or restored from a backup: you need to ensure that you have a way to reliably roll forward past any previous sequence number you might have issued. Timestamping fixes both of these issues.
• Timestamping or sequence numbering every job as issued by permission slip would also give us a total ordering, but is excessive because we already have a total ordering on jobs due to hash-chaining by job ID. This would not add anything beyond ordering sessions, and would only be more information to communicate in the signed job request, which we strongly prefer to keep minimal, so it can be relayed out of band.

Drawbacks:

The possibility of negative leap-seconds or clock skew between permission slip servers could, in principle, allow coincident or inverted ordering of sessions. I do not consider this to be a realistic concern, because authorization happens at human timescales, and even if such an inversion occurred, in the worst case it could cause a session to fail to be accepted by the rack (because a "later" session is already in progress). Hitting this odd sharp edge not only requires multiple effectively concurrent support sessions within a tiny window of time, but also fails closed and can be harmlessly retried in that event.