5 ms·

Time Goes On in Erlang

110 points by lelf 11y ago

lostcolony 11y ago
Awesome to see that ferd added the new time API stuff. I already read the API docs, and the key takeaway at the bottom is the same as there (i.e., when to use each of the new functions), but LYSE is easily the most popular Erlang intro out there.
jlouis 11y ago
One may wonder why all these changes in Erlang/OTP 18.0? The reason, as the chapter by ferd states, is lock contention. Often, when you enabled the `lcnt` subsystem to find lock conflicts in busy systems, you would run into the timer wheel lock. Removing that improves parallelism in the system considerably. And once you decide to take a stab at the time API, why not solve other problems around it as well, now you are working on fixing parts of it?
- derefr 11y ago
  Given how long the Erlang VM has been around and how much it's touted as having the best solutions to this-or-that concurrency problem, I never (naïvely) would have suspected it to have any low-hanging global-interpreter-lock type fruit. I suspect that this is a common-enough sentiment that there are a lot of VM optimization people (insofar as there exist a lot of VM optimization people) who would have been interested in working on this problem even years ago, if the halo effect didn't prevent them from realizing it was there. Certainly some of the people working on removing locks from Python, Ruby, the JVM, etc. would have been intrigued by hacking locks out of BEAM.
  - rdtsc 11y ago
    > I never (naïvely) would have suspected it to have any low-hanging global-interpreter-lock type fruit. The solution is elegant, but that doesn't necessarily mean it was low hanging. (Maybe it was for the authors, I can't speak for them). Sometimes you can't extrapolate the amount of work out of the complexity of final solution. The relationship is often inverse.
    - derefr 11y ago
      Well, not "low-hanging" meaning "easy to fix" so much as "low-hanging" meaning "really obvious high-ROI thing to fix."
  - toast0 11y ago
    You have to have a really big system to get to the point where the timer issues are a major problem. Even then, you can avoid a lot of the problem by making some small changes to your code. Once you get to that point, there are different ways you can go on fixing the problem (bigger timer wheels, more timer wheels), without coming up with a good, elegant solution that's now present in R18.
  - jlouis 11y ago
    It is ongoing work. Killing locks have been a major part of the BEAM VM optimization for the last 10 years, approximately. But doing so correctly takes time. So each part of the system is addressed based on what fruit is the lowest hanging. The contention on `erlang:now()` was irritating, but not impossible to work around.
- lostcolony 11y ago
  Does it count as removing it though? From the docs it looked like they just scaled it out so there's a timer wheel process on each scheduler, and it looks as though the 'common caveats' page still lists using send_after/start_timer instead. I don't know enough about the internal workings of timers vs send_after/start_timer to say for sure though. At any rate, these changes are very welcome.
  - jlouis 11y ago
    The 'timer' module is not the timer wheel in the BEAM VM. The 'timer' module is a slow, old, module which works really well for small developments, but fails in the large scale. The common caveat against its use still holds. The timer wheel is part of the VM and is not directly accessible by Erlang programs. Only through indirect use via a number of constructs/functions manipulating timers.
    - lostcolony 11y ago
      Did not know that; thanks!
- CMCDragonkai 11y ago
  How does the strict monotonic time/unique id generator work? Does it require a centralised lock across the entire Erlang cluster?
  - jlouis 11y ago
    `erlang:unique_integer(Opts)` is not cluster unique! It isn't even unique if a node restarts, but it is unique over a system instances lifetime. It's speed depends on what options you set. If you request `erlang:unique_integer([monotonic])` then you have to lock because you need to synchronize multiple cores (lock here means atomic updates on a 64bit integer, so "lock"). Without monotonic, each scheduler can have it's own ID and then you return (SchedID << 64) + Supply or something equivalent. If you need unique integers over node reboots, then you need to store something else on persistent storage which tells you what generation count your system is currently at. Thus, you can discriminate older integers from newer integers. If you don't need monotonic, you can just do: unique_id() -> ID = erlang:unique_integer(), Generation = read_generation(), Node = node(), {ID, Generation, Node}. and use the triple as your unique ID. Default ordering on tuples, which is lexicographic, then easily makes sure you can compare such ID's and you also obtain a total order on the ID's.
    - CMCDragonkai 11y ago
      When you say "it is unique over a system instances lifetime"? Do you mean an erlang node running on 1 machine? So every node has its own generation. Every generation starts at 1, and every time it restarts, you read the current generation and increment it? The `unique_integer` must be strictly monotonic when given the monotonic option right? When there's no monotonic, that just means the subsequent id can be higher or lower, but not the same. Given the triple {ID, Generation, Node}, is the Node id unique & different across restarts or the same?
rudiger 11y ago
Great stuff. I'd love to see the best parts of this series redone for Elixir.
Luc 11y ago
'A clock on a plane goes slower than a clock on the ground'. It's the other way around actually. I always mix them up too. See e.g. https://en.wikipedia.org/wiki/Gravitational_time_dilation https://en.wikipedia.org/wiki/Gravitational_time_dilation Imagine a mechanical clock battling gravity to get its hands to move. Voila, instant mnemonic.
- qbit 11y ago
  I think the author may have been referring to time dilation due to relative motion of the clocks as opposed to gravity. In that case, to an observer on the ground, the clock on the plane goes slower than a clock on the ground.
  - Luc 11y ago
    Yes, you're probably right. Now I'll need to figure out which effect has the upper hand. Maybe later. EDIT: Flying clocks around: https://en.wikipedia.org/wiki/Hafele%E2%80%93Keating_experiment https://en.wikipedia.org/wiki/Hafele%E2%80%93Keating_experim... If compared to a clock remaining on earth, then it depends on the direction the plane is flying which effect wins.
amelius 11y ago
Why doesn't the OS take care of this? It seems like the prototypical task for the OS.
- lostcolony 11y ago
  Because Erlang runs in a VM, and that VM provides certain useful guarantees that may or may not be provided by the underlying OS. Per the original announcement about the r18 release - If time correction is enabled, the Erlang runtime system will make use of both OS system time and OS monotonic time, in order to make adjustments of the frequency of the Erlang monotonic clock. You can check if your system has support for OS monotonic time by calling erlang:system_info(os_monotonic_time_source), and you can check if time correction is enabled on your system by calling erlang:system_info(time_correction). But that's not always enough, it isn't always available, and it's not always what you want, either. Per the end of the OP (and also the official release) - To find system time: erlang:system_time/0-1 To measure time differences: call erlang:monotonic_time/0-1 twice and subtract them To define an absolute order between events on a node: erlang:unique_integer([monotonic]) Measure time and make sure an absolute order is defined: {erlang:monotonic_time(), erlang:unique_integer([monotonic])} Create a unique name: erlang:unique_integer([positive]). Couple it with a node name if you want the value to be unique in a cluster, or try using UUIDv1
- scott_karana 11y ago
  I agree. System clocks should be based off of "International Atomic Time", TAI, which is also monotonic, and not subject to UTC's leap seconds, as UTC is calculated as an offset of TAI.
  - rvirding 11y ago
    Yes, but the VM clock guaranteed more, every time you access the clock using erlang:now() you would get a monotonically increasing value. Practical to be sure, but not scalable.
    - scott_karana 11y ago

110 points by lelf 11y ago

Awesome to see that ferd added the new time API stuff. I already read the API docs, and the key takeaway at the bottom is the same as there (i.e., when to use each of the new functions), but LYSE is easily the most popular Erlang intro out there.

jlouis 11y ago

One may wonder why all these changes in Erlang/OTP 18.0? The reason, as the chapter by ferd states, is lock contention. Often, when you enabled the `lcnt` subsystem to find lock conflicts in busy systems, you would run into the timer wheel lock. Removing that improves parallelism in the system considerably. And once you decide to take a stab at the time API, why not solve other problems around it as well, now you are working on fixing parts of it?

derefr 11y ago
Given how long the Erlang VM has been around and how much it's touted as having the best solutions to this-or-that concurrency problem, I never (naïvely) would have suspected it to have any low-hanging global-interpreter-lock type fruit. I suspect that this is a common-enough sentiment that there are a lot of VM optimization people (insofar as there exist a lot of VM optimization people) who would have been interested in working on this problem even years ago, if the halo effect didn't prevent them from realizing it was there. Certainly some of the people working on removing locks from Python, Ruby, the JVM, etc. would have been intrigued by hacking locks out of BEAM.
- rdtsc 11y ago
  > I never (naïvely) would have suspected it to have any low-hanging global-interpreter-lock type fruit. The solution is elegant, but that doesn't necessarily mean it was low hanging. (Maybe it was for the authors, I can't speak for them). Sometimes you can't extrapolate the amount of work out of the complexity of final solution. The relationship is often inverse.
  - derefr 11y ago
    Well, not "low-hanging" meaning "easy to fix" so much as "low-hanging" meaning "really obvious high-ROI thing to fix."
- toast0 11y ago
  You have to have a really big system to get to the point where the timer issues are a major problem. Even then, you can avoid a lot of the problem by making some small changes to your code. Once you get to that point, there are different ways you can go on fixing the problem (bigger timer wheels, more timer wheels), without coming up with a good, elegant solution that's now present in R18.
- jlouis 11y ago
  It is ongoing work. Killing locks have been a major part of the BEAM VM optimization for the last 10 years, approximately. But doing so correctly takes time. So each part of the system is addressed based on what fruit is the lowest hanging. The contention on `erlang:now()` was irritating, but not impossible to work around.
lostcolony 11y ago
Does it count as removing it though? From the docs it looked like they just scaled it out so there's a timer wheel process on each scheduler, and it looks as though the 'common caveats' page still lists using send_after/start_timer instead. I don't know enough about the internal workings of timers vs send_after/start_timer to say for sure though. At any rate, these changes are very welcome.
- jlouis 11y ago
  The 'timer' module is not the timer wheel in the BEAM VM. The 'timer' module is a slow, old, module which works really well for small developments, but fails in the large scale. The common caveat against its use still holds. The timer wheel is part of the VM and is not directly accessible by Erlang programs. Only through indirect use via a number of constructs/functions manipulating timers.
  - lostcolony 11y ago
    Did not know that; thanks!
CMCDragonkai 11y ago
How does the strict monotonic time/unique id generator work? Does it require a centralised lock across the entire Erlang cluster?
- jlouis 11y ago
  `erlang:unique_integer(Opts)` is not cluster unique! It isn't even unique if a node restarts, but it is unique over a system instances lifetime. It's speed depends on what options you set. If you request `erlang:unique_integer([monotonic])` then you have to lock because you need to synchronize multiple cores (lock here means atomic updates on a 64bit integer, so "lock"). Without monotonic, each scheduler can have it's own ID and then you return (SchedID << 64) + Supply or something equivalent. If you need unique integers over node reboots, then you need to store something else on persistent storage which tells you what generation count your system is currently at. Thus, you can discriminate older integers from newer integers. If you don't need monotonic, you can just do: unique_id() -> ID = erlang:unique_integer(), Generation = read_generation(), Node = node(), {ID, Generation, Node}. and use the triple as your unique ID. Default ordering on tuples, which is lexicographic, then easily makes sure you can compare such ID's and you also obtain a total order on the ID's.
  - CMCDragonkai 11y ago
    When you say "it is unique over a system instances lifetime"? Do you mean an erlang node running on 1 machine? So every node has its own generation. Every generation starts at 1, and every time it restarts, you read the current generation and increment it? The `unique_integer` must be strictly monotonic when given the monotonic option right? When there's no monotonic, that just means the subsequent id can be higher or lower, but not the same. Given the triple {ID, Generation, Node}, is the Node id unique & different across restarts or the same?

rudiger 11y ago

Great stuff. I'd love to see the best parts of this series redone for Elixir.

Luc 11y ago

'A clock on a plane goes slower than a clock on the ground'. It's the other way around actually. I always mix them up too. See e.g. https://en.wikipedia.org/wiki/Gravitational_time_dilation https://en.wikipedia.org/wiki/Gravitational_time_dilation Imagine a mechanical clock battling gravity to get its hands to move. Voila, instant mnemonic.

qbit 11y ago
I think the author may have been referring to time dilation due to relative motion of the clocks as opposed to gravity. In that case, to an observer on the ground, the clock on the plane goes slower than a clock on the ground.
- Luc 11y ago
  Yes, you're probably right. Now I'll need to figure out which effect has the upper hand. Maybe later. EDIT: Flying clocks around: https://en.wikipedia.org/wiki/Hafele%E2%80%93Keating_experiment https://en.wikipedia.org/wiki/Hafele%E2%80%93Keating_experim... If compared to a clock remaining on earth, then it depends on the direction the plane is flying which effect wins.

amelius 11y ago

Why doesn't the OS take care of this? It seems like the prototypical task for the OS.

lostcolony 11y ago
Because Erlang runs in a VM, and that VM provides certain useful guarantees that may or may not be provided by the underlying OS. Per the original announcement about the r18 release - If time correction is enabled, the Erlang runtime system will make use of both OS system time and OS monotonic time, in order to make adjustments of the frequency of the Erlang monotonic clock. You can check if your system has support for OS monotonic time by calling erlang:system_info(os_monotonic_time_source), and you can check if time correction is enabled on your system by calling erlang:system_info(time_correction). But that's not always enough, it isn't always available, and it's not always what you want, either. Per the end of the OP (and also the official release) - To find system time: erlang:system_time/0-1 To measure time differences: call erlang:monotonic_time/0-1 twice and subtract them To define an absolute order between events on a node: erlang:unique_integer([monotonic]) Measure time and make sure an absolute order is defined: {erlang:monotonic_time(), erlang:unique_integer([monotonic])} Create a unique name: erlang:unique_integer([positive]). Couple it with a node name if you want the value to be unique in a cluster, or try using UUIDv1
scott_karana 11y ago
I agree. System clocks should be based off of "International Atomic Time", TAI, which is also monotonic, and not subject to UTC's leap seconds, as UTC is calculated as an offset of TAI.
- rvirding 11y ago
  Yes, but the VM clock guaranteed more, every time you access the clock using erlang:now() you would get a monotonically increasing value. Practical to be sure, but not scalable.
  - scott_karana 11y ago