5 ms·

I posted this comment in Julia's blog 5 hours ago, currently pending. I'm not sure if it will be accepted, but I'm reporting it here: Hello Julia, the kind of

by antirez 11y ago

I posted this comment in Julia's blog 5 hours ago, currently pending. I'm not sure if it will be accepted, but I'm reporting it here: Hello Julia, the kind of skew that is a problem for Redlock, or other algorithms that would rely on the same clock assumptions, is not when the computer "logical" clocks skew, for example by getting a wrong time from NTP. By using the monotonically increasing clock API we only need to care about failures that cause the clock to go faster / slower even if never modified. Also note that there is no issues with clocks of different processes to be at a totally different absolute times, as long as they continue to count the time approximately at the same speed. If you restrict the failures to this class of issues, then to see it in the practice becomes not impossible but extremely rare. Most real world systems out there using proven algorithms, have to do the same assumptions on the fact that the system works in a mostly expected way. For example disk corruptions or network packets corruptions can cause the same issues, even if they are rarely checksummed at application level, or checked with a checksum length that does not make collisions impossible in the long run. Btw kudos for trying to reason with your head instead of trusting other people's or my words.

alblue 11y ago
"If you restrict the failures to this class of issues" is exactly where the assumption that clocks behave is hiding in this paragraph. It's a bit like saying "as long as you ignore false, all booleans can be assumed to be true".
- antirez 11y ago
  If you use the monotonic time API the issues are restricted to this subclass of hardware failures. All the others will be irrelevant, like ntpd setting a random time or alike.
  - querulous 11y ago
    how does using the monotonic api protect against time discontinuity as seen when a vm is migrated from one hypervisor to another for example?
    - jschwartzi 11y ago
      Monotonic clocks are guaranteed never to go backwards, for one. In POSIX it would be a major violation of the API, although implementations are free to substitute clock sources if the monotonic source is not provided.
      - derefr 11y ago
        Or, to put it more bluntly: a hypervisor that allows its VMs to be paused SHOULD NOT expose a monotonic time source to said VMs. (In the RFC meaning of "SHOULD NOT".) Enabling monotonic time should disable the ability to pause/migrate/snapshot the VMs, and vice-versa.
    - antirez 11y ago
      In this case, even in a broken implementation, the time freezes during the migration and is restored immediately after. This is bad since it makes even softwares using the monotonic API not able to count time reliably, however the result is that the time is over-counted, and never under-counted. If the algorithm is designed so that we want to count "at least 5 seconds" it is safe even during VM migrations. This is true for Redlock for example, but in general if one wants to exploit this system model, and can setup the algorithm so that over counting is harmless (if not for liveness), is a good idea. Btw this problems could be mitigated by changing the majority. For instance in the case of a distributed lock, it's possible to acquire the lock in 50% + 2 instances in order to consider the lock valid, so that in one instance the clock can misbehave safely.
- dpark 11y ago
  He's talking about literally restricting the failures to a specific class by preventing errors outside that class, not just restricting consideration of errors to that class.
andrewflnr 11y ago
...as long as they continue to count the time approximately at the same speed. But according to the people Julia talked to, this assumption is also unreliable. Is that just a risk you feel you have to take?
- jschwartzi 11y ago
  If you can characterize the latency involved in messaging between domains, it stands to reason that you can provide a reasonable bound on how close both systems are to an ideal shared clock source. If it's good enough, who cares if it's perfect?
georgeaf99 11y ago
This is a really important point that a lot of people seem to have missed. A common assumption that stems from monotonously increasing clocks is that: all computers can guarantee the causality of their own internal events. Which is a critical assumption for a wide variety of distributed algorithms.
cyphar 11y ago
I'm wondering if you read the article. Mainly because she only mentions an NTP paper about local clock skew causing servers to serve incorrect times. I don't know why you don't want to admit the existence of certain failure modes, it's probably a pride thing.

by antirez 11y ago

alblue 11y ago

"If you restrict the failures to this class of issues" is exactly where the assumption that clocks behave is hiding in this paragraph. It's a bit like saying "as long as you ignore false, all booleans can be assumed to be true".

antirez 11y ago
If you use the monotonic time API the issues are restricted to this subclass of hardware failures. All the others will be irrelevant, like ntpd setting a random time or alike.
- querulous 11y ago
  how does using the monotonic api protect against time discontinuity as seen when a vm is migrated from one hypervisor to another for example?
  - jschwartzi 11y ago
    Monotonic clocks are guaranteed never to go backwards, for one. In POSIX it would be a major violation of the API, although implementations are free to substitute clock sources if the monotonic source is not provided.
    - derefr 11y ago
      Or, to put it more bluntly: a hypervisor that allows its VMs to be paused SHOULD NOT expose a monotonic time source to said VMs. (In the RFC meaning of "SHOULD NOT".) Enabling monotonic time should disable the ability to pause/migrate/snapshot the VMs, and vice-versa.
  - antirez 11y ago
    In this case, even in a broken implementation, the time freezes during the migration and is restored immediately after. This is bad since it makes even softwares using the monotonic API not able to count time reliably, however the result is that the time is over-counted, and never under-counted. If the algorithm is designed so that we want to count "at least 5 seconds" it is safe even during VM migrations. This is true for Redlock for example, but in general if one wants to exploit this system model, and can setup the algorithm so that over counting is harmless (if not for liveness), is a good idea. Btw this problems could be mitigated by changing the majority. For instance in the case of a distributed lock, it's possible to acquire the lock in 50% + 2 instances in order to consider the lock valid, so that in one instance the clock can misbehave safely.
dpark 11y ago
He's talking about literally restricting the failures to a specific class by preventing errors outside that class, not just restricting consideration of errors to that class.

andrewflnr 11y ago

...as long as they continue to count the time approximately at the same speed. But according to the people Julia talked to, this assumption is also unreliable. Is that just a risk you feel you have to take?

jschwartzi 11y ago
If you can characterize the latency involved in messaging between domains, it stands to reason that you can provide a reasonable bound on how close both systems are to an ideal shared clock source. If it's good enough, who cares if it's perfect?

georgeaf99 11y ago

This is a really important point that a lot of people seem to have missed. A common assumption that stems from monotonously increasing clocks is that: all computers can guarantee the causality of their own internal events. Which is a critical assumption for a wide variety of distributed algorithms.

cyphar 11y ago

I'm wondering if you read the article. Mainly because she only mentions an NTP paper about local clock skew causing servers to serve incorrect times. I don't know why you don't want to admit the existence of certain failure modes, it's probably a pride thing.