6 ms·

> Spanner’s external consistency invariant is that for any two transactions, T1 and T2 (even if on opposite sides of the globe):if T2 starts to commit after T1

> Spanner’s external consistency invariant is that for any two transactions, T1 and T2 (even if on opposite sides of the globe):if T2 starts to commit after T1 finishes committing, then the timestamp for T2 is greater than the timestamp for T1. This is impressive. But what exact point in time is when 'T2 starts to commit'? Is it when the user pushes the submit button on their device? When the request reaches a Google server? When it reaches a Spanner server within Google? The point I'm getting at is given the uncertain 'delay' between the time the user interacts with the system and the 'time of commit', is time based linearizability a useful property? Could it be made simpler with actor based linearizability? Or revision based?

mgraczyk 9y ago
The way the timestamp is chosen depends on properties of the transaction. In the worst cases, servers must wait until the true time interval has passed an older commit before assigning a timestamp.
wwarner 9y ago
I agree that this is the best line in the paper. I interpret it to mean that while a second transaction is in progress, if a commit log comes in it's an extremely cheap operation to check the timestamp and ignore it.
pishpash 9y ago
There is no global time and no simultaneity. What is this notion that T2 is greater than T1 when they are separated by some significant distance? The sentence doesn't even make sense.
- jasonwatkinspdx 9y ago
  We synthesize idealized ephemeris time via a cohort of atomic clocks. Google's TrueTime tracks this along with the local uncertainty. This allows Spanner to explicitly wait out uncertainty windows, establishing a single externally consistent order to all possible observers, even in the presence of hidden communication channels. This is the whole point of the system, and what the article covers. What you're saying about time isn't even exactly true in the general case where we need account for relativity. While observers of clocks in different locations may not agree on clocks alone, they will agree on the total spacetime interval. In any case, accounting for relativity is only necessary in high precision radio frequency systems operating between ground and orbit like GPS. And even then we can still track the frequency and phase offsets of the oscillators in real time and establish their relationship to idealized ephemeris time. So yes, the sentences in the article DO make sense. EDIT: at least the ones concerning time and consistent orders due. The words about effectively CA are ... not great.
  - pishpash 9y ago
    They may agree on the spacetime interval but that is of no consequence, since they will still not agree on the ordering. Establishing a single externally consistent order of events for all possible observers is physically impossible, unless the spacetime interval separating them is timelike, a condition that is rarely true of distributed transactions that are happening independently: e.g. Abel puts in money in Spain, Beth removes it in Australia -- do you charge an overdraft fee/interest? (N.B., Abel and Beth may be names of HFT algorithms.) "Spanner for causal transactions" would be more accurate. P.S. Not sure what you mean by "hidden communication channels."
    - jasonwatkinspdx 9y ago
      > Establishing a single externally consistent order of events for all possible observers is physically impossible No, it is not. It does however require communication. Additionally, what's true in an absolute physical sense, is somewhat removed from what's practical engineered product. For example, we cannot literally make a physical part that is perfectly 1 meter in length. This has not stopped us from making everything from microchips to spacecraft. > Abel puts in money in Spain, Beth removes it in Australia -- do you charge an overdraft fee/interest? (N.B., Abel and Beth may be names of HFT algorithms.) Spanner handles this by using two phase commit over sets of independent consensus replication groups. By using TrueTime's ability to provide absolute intervals, it can wait out uncertainty windows to enforce the total order. > P.S. Not sure what you mean by "hidden communication channels." Schemes such as lamport and vector clocks require all messages exchanged to include clock data. If two clients establish their own communication channel using some other protocol, they may not agree on the same event order, because the system has no way to know it needs to advance the logical clocks based on this hidden communication. Spanner in combination with TrueTime avoids this limitation. External observers will see the same commit order in real time, regardless of how they communicate. Please read and understand the papers to get what you're missing.
- TheDong 9y ago
  The paper is not talking about time, in the abstract, or simultaneity / ordering in the abstract (which indeed don't exist), but rather with reference to "timestamps". "Timestamps" are not abstract time, and as such may be ordered, compared, be simultaneous, etc. Your comment is irrelevant and pointless since the paper is talking about timestamps.
  - pishpash 9y ago
    No amount of sophistry will help the matter at hand. Spanner considers a true spacelike interval to be some kind of fuzzy clock measurement error (or "uncertainty"). Call it timestamp all you want, whatever shall you stamp when you should have one node on Earth and another on Mars?
    - jasonwatkinspdx 9y ago
      > whatever shall you stamp when you should have one node on Earth and another on Mars? Again, if you were familiar with the content of the papers, you could answer this yourself. How it would work is establishing a phase locked loop between the oscillator on earth and the oscillator on mars, and then running a TrueTime style interval protocol. The downside of "Mars Spanner" is the very long round trip time would make the two phase commit protocol unacceptably long latency. However, the basic properties would still hold. I don't know how else to explain it to you: a communicating distributed system can establish a single, canonical, total order on events. This is not a physical impossibility.
      - pishpash 9y ago
        "Can establish a ... total order on events" is somewhat vacuous, the point is how it corresponds to the actual observed ordering. Otherwise you can just label arbitrarily, 1, 2, 3, ... that's also an ordering. I'm saying there is no such correspondence that is globally correct. It doesn't matter what protocol you run. You cannot synchronize two clocks that are apart. You can only synchronize them when they are in the same place. I perfectly understand that with communication you can establish (read: impose) any arbitrary ordering you want and get nodes to agree to that. That's not really a useful resolution except in a narrow sense of "sometimes we really don't care about strict observed ordering," which may or may not be true. The larger point is, Spanner doesn't solve any distributed database problem. It simply notices that on the timescale that today's workload appears to operate at, all the nodes can still be approximated as being collocated. There is, after all, a clock inside a computer as well, and this just extends it a little further.
zAy0LfpBZLC8mAC 9y ago
I would think that is simply the statement that the ordering of timestamps preserves causality? What the "actual point in time" of anything is isn't really relevant--the question is whether you can show that a given transaction started after another committed, and if so, then you are guaranteed that timestamps assigned to those transactions preserve that ordering.
sriram_malhar 9y ago
Ordinarily (and as indicated by your expectation), a timestamp records the time at which an event occurred. In most databases, the tranasction time is either the start of the transaction or the time at which the transaction coordinator initiates commit. In spanner, there is a twist. The timestamp is decided by its transaction coordinator. Notice the word "decided". It means that the coordinator picks/computes a timestamp, not merely record an event's real time. The timestamp given to a transaction is the largest of: (1) timestamps from the various participants (other servers that may have been touched by that transaction) (2) its own latest clock time, and is strictly greater than any previously committed transactions. (Bonus material:) Having picked this timestamp, it is possible that it (the timestamp) is greater than the coordinating machine's clock. A spanner server does not reflect the transaction's modifications to concurrent queries until the server's clock is past the transaction's commit timestamp. This is called "commit wait".
- shalabhc 9y ago
  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.

mgraczyk 9y ago

The way the timestamp is chosen depends on properties of the transaction. In the worst cases, servers must wait until the true time interval has passed an older commit before assigning a timestamp.

wwarner 9y ago

I agree that this is the best line in the paper. I interpret it to mean that while a second transaction is in progress, if a commit log comes in it's an extremely cheap operation to check the timestamp and ignore it.

pishpash 9y ago

There is no global time and no simultaneity. What is this notion that T2 is greater than T1 when they are separated by some significant distance? The sentence doesn't even make sense.

jasonwatkinspdx 9y ago
We synthesize idealized ephemeris time via a cohort of atomic clocks. Google's TrueTime tracks this along with the local uncertainty. This allows Spanner to explicitly wait out uncertainty windows, establishing a single externally consistent order to all possible observers, even in the presence of hidden communication channels. This is the whole point of the system, and what the article covers. What you're saying about time isn't even exactly true in the general case where we need account for relativity. While observers of clocks in different locations may not agree on clocks alone, they will agree on the total spacetime interval. In any case, accounting for relativity is only necessary in high precision radio frequency systems operating between ground and orbit like GPS. And even then we can still track the frequency and phase offsets of the oscillators in real time and establish their relationship to idealized ephemeris time. So yes, the sentences in the article DO make sense. EDIT: at least the ones concerning time and consistent orders due. The words about effectively CA are ... not great.
- pishpash 9y ago
  They may agree on the spacetime interval but that is of no consequence, since they will still not agree on the ordering. Establishing a single externally consistent order of events for all possible observers is physically impossible, unless the spacetime interval separating them is timelike, a condition that is rarely true of distributed transactions that are happening independently: e.g. Abel puts in money in Spain, Beth removes it in Australia -- do you charge an overdraft fee/interest? (N.B., Abel and Beth may be names of HFT algorithms.) "Spanner for causal transactions" would be more accurate. P.S. Not sure what you mean by "hidden communication channels."
  - jasonwatkinspdx 9y ago
    > Establishing a single externally consistent order of events for all possible observers is physically impossible No, it is not. It does however require communication. Additionally, what's true in an absolute physical sense, is somewhat removed from what's practical engineered product. For example, we cannot literally make a physical part that is perfectly 1 meter in length. This has not stopped us from making everything from microchips to spacecraft. > Abel puts in money in Spain, Beth removes it in Australia -- do you charge an overdraft fee/interest? (N.B., Abel and Beth may be names of HFT algorithms.) Spanner handles this by using two phase commit over sets of independent consensus replication groups. By using TrueTime's ability to provide absolute intervals, it can wait out uncertainty windows to enforce the total order. > P.S. Not sure what you mean by "hidden communication channels." Schemes such as lamport and vector clocks require all messages exchanged to include clock data. If two clients establish their own communication channel using some other protocol, they may not agree on the same event order, because the system has no way to know it needs to advance the logical clocks based on this hidden communication. Spanner in combination with TrueTime avoids this limitation. External observers will see the same commit order in real time, regardless of how they communicate. Please read and understand the papers to get what you're missing.
TheDong 9y ago
The paper is not talking about time, in the abstract, or simultaneity / ordering in the abstract (which indeed don't exist), but rather with reference to "timestamps". "Timestamps" are not abstract time, and as such may be ordered, compared, be simultaneous, etc. Your comment is irrelevant and pointless since the paper is talking about timestamps.
- pishpash 9y ago
  No amount of sophistry will help the matter at hand. Spanner considers a true spacelike interval to be some kind of fuzzy clock measurement error (or "uncertainty"). Call it timestamp all you want, whatever shall you stamp when you should have one node on Earth and another on Mars?
  - jasonwatkinspdx 9y ago
    > whatever shall you stamp when you should have one node on Earth and another on Mars? Again, if you were familiar with the content of the papers, you could answer this yourself. How it would work is establishing a phase locked loop between the oscillator on earth and the oscillator on mars, and then running a TrueTime style interval protocol. The downside of "Mars Spanner" is the very long round trip time would make the two phase commit protocol unacceptably long latency. However, the basic properties would still hold. I don't know how else to explain it to you: a communicating distributed system can establish a single, canonical, total order on events. This is not a physical impossibility.
    - pishpash 9y ago
      "Can establish a ... total order on events" is somewhat vacuous, the point is how it corresponds to the actual observed ordering. Otherwise you can just label arbitrarily, 1, 2, 3, ... that's also an ordering. I'm saying there is no such correspondence that is globally correct. It doesn't matter what protocol you run. You cannot synchronize two clocks that are apart. You can only synchronize them when they are in the same place. I perfectly understand that with communication you can establish (read: impose) any arbitrary ordering you want and get nodes to agree to that. That's not really a useful resolution except in a narrow sense of "sometimes we really don't care about strict observed ordering," which may or may not be true. The larger point is, Spanner doesn't solve any distributed database problem. It simply notices that on the timescale that today's workload appears to operate at, all the nodes can still be approximated as being collocated. There is, after all, a clock inside a computer as well, and this just extends it a little further.

zAy0LfpBZLC8mAC 9y ago

I would think that is simply the statement that the ordering of timestamps preserves causality? What the "actual point in time" of anything is isn't really relevant--the question is whether you can show that a given transaction started after another committed, and if so, then you are guaranteed that timestamps assigned to those transactions preserve that ordering.

sriram_malhar 9y ago

Ordinarily (and as indicated by your expectation), a timestamp records the time at which an event occurred. In most databases, the tranasction time is either the start of the transaction or the time at which the transaction coordinator initiates commit. In spanner, there is a twist. The timestamp is decided by its transaction coordinator. Notice the word "decided". It means that the coordinator picks/computes a timestamp, not merely record an event's real time. The timestamp given to a transaction is the largest of: (1) timestamps from the various participants (other servers that may have been touched by that transaction) (2) its own latest clock time, and is strictly greater than any previously committed transactions. (Bonus material:) Having picked this timestamp, it is possible that it (the timestamp) is greater than the coordinating machine's clock. A spanner server does not reflect the transaction's modifications to concurrent queries until the server's clock is past the transaction's commit timestamp. This is called "commit wait".

shalabhc 9y ago
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.