4 ms·

> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe... He's using it relatively, ie. if (stop time -

> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe... He's using it relatively, ie. if (stop time - start time <= $got_lock_fast_enough) { continue... } Is this not legit?

pygy_ 11y ago
In a virtualized environment, system time and wall clock time can vary widely. Imagine a VM that's paused and restored.
- derefr 11y ago
  I would assume that introducing a VM that has "time-travelled" (especially the restore-from-previous-state case someone mentioned above) into a distributed system would inherently break that distributed system, no matter what it's doing. It's a really crazy thing to do, much crazier than a regular network partition. Personally, though, I don't see why it's so hard to just say "this distributed lock system requires that soft real-time guarantees can be made of the host platform. If the platform misses the algorithm's scheduling deadline, the system breaks. If the platform has no way of providing for a soft real-time deadline (because e.g. it's running in a VM that can be paused), the software will detect this and fail to start."
  - jsprogrammer 11y ago
    Because you don't want the system to break.
    - derefr 11y ago
      But it wouldn't, because the surrounding infrastructure would be guaranteeing that. My point is that distributed systems engineers are assuming too few things about the hardware and OS. A much wider space of distributed algorithms become useful if you have full control over your stack. Do you think NASA quibbles about how to make a perfect consensus bit-coding algorithm between the fault-tolerant processors of a mars probe? No; they just use hardware+firmware that provides a hard real-time platform, allowing the algorithm itself to be simple.
      - baruch 11y ago
        It doesn't require a VM pause to cause a system freeze, an SMI interrupt can do that as well. It doesn't take a lot to have backwards time travel, NTP can do that for you as well in some bad configurations. It's very hard to rely on time in a distributed system. If you want a simple algorithm just don't rely on time at all, use it for logs so a human can correlate things when debugging an issue but don't assume time will flow at the same rate for all systems. Do use a monotonic clock always for internal timers, time does move backwards in systems.
        ahoka 11y ago
        I have seen SMI pauses for almost 5 seconds!
carllerche 11y ago
What if the system freezes between reading the current time from the hardware and the stead_time function returning? In short, you CANNOT rely on time in any way shape or form for safety. You can only use it as advice & to get liveliness. Martin's point is that Redlock pays the cost of other safe locking algorithms w/o the benefit of safety.
- jodah 11y ago
  This, usually. It's fair to point out that very specialized clocks, such as Google uses with Spanner, can allow you to achieve some consistency without coordination/locks, but for pretty much anyone else the rule you stated very much applies.
  - newman314 11y ago
    FWIW, I went digging for more recent info about TrueTime and found the following. http://www.cse.buffalo.edu/~demirbas/publications/augmentedTime.pdf http://www.cse.buffalo.edu/~demirbas/publications/augmentedT...

pygy_ 11y ago

In a virtualized environment, system time and wall clock time can vary widely. Imagine a VM that's paused and restored.

derefr 11y ago
I would assume that introducing a VM that has "time-travelled" (especially the restore-from-previous-state case someone mentioned above) into a distributed system would inherently break that distributed system, no matter what it's doing. It's a really crazy thing to do, much crazier than a regular network partition. Personally, though, I don't see why it's so hard to just say "this distributed lock system requires that soft real-time guarantees can be made of the host platform. If the platform misses the algorithm's scheduling deadline, the system breaks. If the platform has no way of providing for a soft real-time deadline (because e.g. it's running in a VM that can be paused), the software will detect this and fail to start."
- jsprogrammer 11y ago
  Because you don't want the system to break.
  - derefr 11y ago
    But it wouldn't, because the surrounding infrastructure would be guaranteeing that. My point is that distributed systems engineers are assuming too few things about the hardware and OS. A much wider space of distributed algorithms become useful if you have full control over your stack. Do you think NASA quibbles about how to make a perfect consensus bit-coding algorithm between the fault-tolerant processors of a mars probe? No; they just use hardware+firmware that provides a hard real-time platform, allowing the algorithm itself to be simple.
    - baruch 11y ago
      It doesn't require a VM pause to cause a system freeze, an SMI interrupt can do that as well. It doesn't take a lot to have backwards time travel, NTP can do that for you as well in some bad configurations. It's very hard to rely on time in a distributed system. If you want a simple algorithm just don't rely on time at all, use it for logs so a human can correlate things when debugging an issue but don't assume time will flow at the same rate for all systems. Do use a monotonic clock always for internal timers, time does move backwards in systems.
      - ahoka 11y ago
        I have seen SMI pauses for almost 5 seconds!

carllerche 11y ago

What if the system freezes between reading the current time from the hardware and the stead_time function returning? In short, you CANNOT rely on time in any way shape or form for safety. You can only use it as advice & to get liveliness. Martin's point is that Redlock pays the cost of other safe locking algorithms w/o the benefit of safety.

jodah 11y ago
This, usually. It's fair to point out that very specialized clocks, such as Google uses with Spanner, can allow you to achieve some consistency without coordination/locks, but for pretty much anyone else the rule you stated very much applies.
- newman314 11y ago
  FWIW, I went digging for more recent info about TrueTime and found the following. http://www.cse.buffalo.edu/~demirbas/publications/augmentedTime.pdf http://www.cse.buffalo.edu/~demirbas/publications/augmentedT...