4 ms·

Thanks for the details! BTW, this sounds similar to the pseudotime ideas from David Reed (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.8053&rep=

Thanks for the details! BTW, this sounds similar to the pseudotime ideas from David Reed (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.8053&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126...), where you 'compute' a transaction timestamp and use it for ordering. My question was more about how, of if, this 'feature' is usable externally? Guarantees made in terms of synthesized time are theoretically not useful to the callers, who are in a different 'real' time. I.e. when the doc says 'X happens after Y', it's talking about synthesized time, how does this translate in terms of 'real' time? E.g. is the synthesized time returned to the caller, which can then be uses to make subsequent queries?

sriram_malhar 9y ago
In pseudotime, a timestamp is a <<siteid, clock time at that site>>. The clock time only has meaning within that site; just because t1 < t2 does not mean that an event at t1 actually happened before t2, because the second server may have a higher id, or may be running faster. While the mechanism permits all servers to unambiguously order the two events in the same way, the actual time cannot be taken too seriously unless they are well outside the uncertainty interval of the clock sync algorithm. But a client does not know what the uncertainty interval is, so one can only make an educated guess. Google's spanner makes that uncertainty a first-class entity; all timestamps are (equivalent to) a pair of <<start,end>>, where the actual real time is guaranteed to be somewhere within that interval. There is no siteid to disambiguate timestamps. The time is globally meaningful, which makes it trivial to make time-oriented queries, or instant global snapshots ("give me the values of these 20 objects at 10:02 am"). In that sense, the times are not really "synthesized". The coordinator picks a time to associate with the transaction, and that time is meaningful globally.
- shalabhc 9y ago
  You can make time-oriented queries on snapshots using pseudo-time as well - given that all transactions are ordered. Timestamps are roughly ordered by real time, because NTP will synchronize to a few ms accuracy. IIUC within the margin of error, transactions will be arbitrarily ordered, but they'll be consistent - i.e. all readers will see the exact same order of previously applied transactions. I'm trying to identify use cases where Spanner works better. Lets say, in Spanner, t1.end < t2.start for a pair of transactions - this still does not mean that t1 'happened' before t2, does it? All it means is that the t1 request arrived at a spanner server before the t2 arrived at a spanner server. But what does it mean about the event itself (going back to my original example of users interacting with their device)? Is ordering transactions by their arrival time on Spanner servers a more useful external property than an arbitrarily chosen (but consistent) order based on site id and millisecond level resolution?
  - sriram_malhar 9y ago
    Oh yes, that's precisely Spanner's guarantee. If t1.end < t2.start, it is _defined_ as t1 < t2, and t1 definitely happened before t2. t1's effects will always be observable before t2's to any observer. The notion of arrival time isn't important really. It is quite possible that the second one arrived at a server before the first one, but the first one's participants responded earlier. At that point, t1's commit time is picked. If t2 is also committed at the same server, then t2's time will be selected to be later than t1 (non-overlapping intervals). If t2 is committed at a different server, and if t1 just happens to be < than t2, then one can be guaranteed that causality is preserved. There is no way t2 could have affected t1. This latter property (external consistency) cannot be guaranteed by pseudotime. In PT it is possible to have t2 affect t1 in an external way (without involving the db, say by making a phone call), and yet get a smaller timestamp. From the db's point of view, t2 happened first, but that's not what really happened in reality, in an externally observable sense.
    - shalabhc 9y ago
      Oh I think I see what you mean. The specific scenario is: 1. External actor A1 sends a request t1 to Spanner 2. Spanner responds with a message m1 confirming t1 is committed 3. Based on receiving m1, A1 sends a private message to external actor A2 4. A2 then initiates a request t2, which affects a set of objects completely disjoint from the set affected by t1. t2 is committed. Now Spanner guarantees that the timestamp for t2 > timestamp for t1. If the set of objects affected by t1 and t2 overlap then PT and Spanner provide the same guarantees (each object can only move 'forward' in PT). But if they affect disjoint sets of objects, then Spanner provides stronger guarantees. Is that correct?
      - sriram_malhar 9y ago
        Yes, correct.

sriram_malhar 9y ago

In pseudotime, a timestamp is a <<siteid, clock time at that site>>. The clock time only has meaning within that site; just because t1 < t2 does not mean that an event at t1 actually happened before t2, because the second server may have a higher id, or may be running faster. While the mechanism permits all servers to unambiguously order the two events in the same way, the actual time cannot be taken too seriously unless they are well outside the uncertainty interval of the clock sync algorithm. But a client does not know what the uncertainty interval is, so one can only make an educated guess. Google's spanner makes that uncertainty a first-class entity; all timestamps are (equivalent to) a pair of <<start,end>>, where the actual real time is guaranteed to be somewhere within that interval. There is no siteid to disambiguate timestamps. The time is globally meaningful, which makes it trivial to make time-oriented queries, or instant global snapshots ("give me the values of these 20 objects at 10:02 am"). In that sense, the times are not really "synthesized". The coordinator picks a time to associate with the transaction, and that time is meaningful globally.

shalabhc 9y ago
You can make time-oriented queries on snapshots using pseudo-time as well - given that all transactions are ordered. Timestamps are roughly ordered by real time, because NTP will synchronize to a few ms accuracy. IIUC within the margin of error, transactions will be arbitrarily ordered, but they'll be consistent - i.e. all readers will see the exact same order of previously applied transactions. I'm trying to identify use cases where Spanner works better. Lets say, in Spanner, t1.end < t2.start for a pair of transactions - this still does not mean that t1 'happened' before t2, does it? All it means is that the t1 request arrived at a spanner server before the t2 arrived at a spanner server. But what does it mean about the event itself (going back to my original example of users interacting with their device)? Is ordering transactions by their arrival time on Spanner servers a more useful external property than an arbitrarily chosen (but consistent) order based on site id and millisecond level resolution?
- sriram_malhar 9y ago
  Oh yes, that's precisely Spanner's guarantee. If t1.end < t2.start, it is _defined_ as t1 < t2, and t1 definitely happened before t2. t1's effects will always be observable before t2's to any observer. The notion of arrival time isn't important really. It is quite possible that the second one arrived at a server before the first one, but the first one's participants responded earlier. At that point, t1's commit time is picked. If t2 is also committed at the same server, then t2's time will be selected to be later than t1 (non-overlapping intervals). If t2 is committed at a different server, and if t1 just happens to be < than t2, then one can be guaranteed that causality is preserved. There is no way t2 could have affected t1. This latter property (external consistency) cannot be guaranteed by pseudotime. In PT it is possible to have t2 affect t1 in an external way (without involving the db, say by making a phone call), and yet get a smaller timestamp. From the db's point of view, t2 happened first, but that's not what really happened in reality, in an externally observable sense.
  - shalabhc 9y ago
    Oh I think I see what you mean. The specific scenario is: 1. External actor A1 sends a request t1 to Spanner 2. Spanner responds with a message m1 confirming t1 is committed 3. Based on receiving m1, A1 sends a private message to external actor A2 4. A2 then initiates a request t2, which affects a set of objects completely disjoint from the set affected by t1. t2 is committed. Now Spanner guarantees that the timestamp for t2 > timestamp for t1. If the set of objects affected by t1 and t2 overlap then PT and Spanner provide the same guarantees (each object can only move 'forward' in PT). But if they affect disjoint sets of objects, then Spanner provides stronger guarantees. Is that correct?
    - sriram_malhar 9y ago
      Yes, correct.