Will Erlang Scheduler make process causing re-queue problem?

Question

Background: I'm confuse with Erlang's scheduler for a long time until have a look at The Beam Book. I had do some research on async/non-blocking programming in some language(Elixir/Erlang, Scala/Java, Golang) which include Actor pattern, Future/Promise, coroutine mainly. Coroutine and Actor pattern is similarly in term of they can both think as lightweight process.

The Problem
I'm find a weakness of the async programming: It will cause a lightweight-process(or a task) re-queue to the end of the scheduler Ready Queue if it invoke any of the block operation. The block operation will not block OS-Thread but it occurred mainly because of invoke a async action such as 'aio_read'.
re-queue means the process will be put at the end of Scheduler even if the process is just scheduled.In server-side programming, it will make a client request delay with a relatively long time compare with it should process time.The Beam Book give a detail description:

A processs trying to do a receive on an empty mailbox or on a mailbox with no matching messages will yield and go into the waiting state.
When a message is delivered to an inbox the sending process will check whether the receiver is sleeping in the waiting state, and in that case it will wake the process, change its state to runable, and put it at the end of the appropriate ready queue.

The affect could be see in many benchmark test: More request, more response time for every request.
A good scheduler should make the response time nearly the real process time of the request if ignore OS-Thread Context Switch.

I haven't seem others discuss the aspect yet.

As a conclusion, there are two question:
1. I want make a confirm whether re-queue problem really exist in async-programming world.
2. Besides, Is Erlang really has the problem if it handle tens of thousands of the process, especially use many GenServer.call in a request-response-chain?

Unknown Unknown · Accepted Answer · 2018-12-24T23:33:43

Your answers are here: https://hamidreza-s.github.io/erlang/scheduling/real-time/preemptive/migration/2016/02/09/erlang-scheduler-details.html

Reposting it here, allowing edits.

Erlang Scheduling

Erlang as a real-time platform for multitasking uses Preemptive Scheduling. The responsibility of an Erlang scheduler is selecting a Process and executing their code. It also does Garbage Collection and Memory Management. The factor of selecting a process for execution is based on their priority level which is configurable per process and in each priority level processes are scheduled in a round robin fashion. On the other hand the factor of preempting a process from execution is based on a certain number of Reductions since the last time it was selected for execution, regardless of its priority level. The reduction is a counter per process that is normally incremented by one for each function call. It is used for preempting processes and context switching them when the counter of a process reaches the maximum number of reductions. For example in Erlang/OTP R12B this maximum number was 2000 reductions.

The scheduling of tasks in Erlang has a long history. It has been changing over the time. These changes were affected by the changes in SMP (Symmetric Multi-Processing) feature of Erlang.

Scheduling Before R11B

Before R11B Erlang did not have SMP support, so just one scheduler was run in the main OS process’s thread and accordingly just one Run Queue existed. The scheduler picked runnable Erlang processes and IO tasks from the run queue and executed them.

                        Erlang VM

+--------------------------------------------------------+
|                                                        |
|  +-----------------+              +-----------------+  |
|  |                 |              |                 |  |
|  |    Scheduler    +-------------->     Task # 1    |  |
|  |                 |              |                 |  |
|  +-----------------+              |     Task # 2    |  |
|                                   |                 |  |
|                                   |     Task # 3    |  |
|                                   |                 |  |
|                                   |     Task # 4    |  |
|                                   |                 |  |
|                                   |     Task # N    |  |
|                                   |                 |  |
|                                   +-----------------+  |
|                                   |                 |  |
|                                   |    Run Queue    |  |
|                                   |                 |  |
|                                   +-----------------+  |
|                                                        |
+--------------------------------------------------------+

This way there was no need to lock data structures but the written application couldn’t take advantage of parallelism.

Scheduling In R11B and R12B

SMP support was added to Erlang VM so it could have 1 to 1024 schedulers each was run in one OS process’s thread. However, in this version schedulers could pick runnable tasks from just one common run queue.

       Erlang VM

+--------------------------------------------------------+
|                                                        |
|  +-----------------+              +-----------------+  |
|  |                 |              |                 |  |
|  |  Scheduler # 1  +-------------->     Task # 1    |  |
|  |                 |    +--------->                 |  |
|  +-----------------+    |    +---->     Task # 2    |  |
|                         |    |    |                 |  |
|  +-----------------+    |    |    |     Task # 3    |  |
|  |                 |    |    |    |                 |  |
|  |  Scheduler # 2  +----+    |    |     Task # 4    |  |
|  |                 |         |    |                 |  |
|  +-----------------+         |    |     Task # N    |  |
|                              |    |                 |  |
|  +-----------------+         |    +-----------------+  |
|  |                 |         |    |                 |  |
|  |  Scheduler # N  +---------+    |    Run Queue    |  |
|  |                 |              |                 |  |
|  +-----------------+              +-----------------+  |
|                                                        |
+--------------------------------------------------------+

Because of the resulting parallelism of this method, all shared data structures are protected with locks. For example the run queue itself is a shared data structure which must be protected. Although the lock can provide performance penalty, the performance improvements which was achieved in multi-core processors systems was interesting.

Some known bottlenecks in this version was as follows:

The common run queue becomes a bottleneck when the number of schedulers increases. Increasing the involved lock of ETS tables which also affects Mnesia. Increasing the lock conflicts when many processes are sending messages to the same process. A process waiting to get a lock can block its scheduler. However, separating run queues per scheduler was picked to solve these bottleneck issues in next versions.

Scheduling After R13B

In this version each scheduler has its own run queue. It decreases the number of lock conflicts in systems with many schedulers on many cores and also improves the overall performance.

      Erlang VM

+--------------------------------------------------------+
|                                                        |
|  +-----------------+-----------------+                 |
|  |                 |                 |                 |
|  |  Scheduler # 1  |  Run Queue # 1  <--+              |
|  |                 |                 |  |              |
|  +-----------------+-----------------+  |              |
|                                         |              |
|  +-----------------+-----------------+  |              |
|  |                 |                 |  |              |
|  |  Scheduler # 2  |  Run Queue # 2  <----> Migration  |
|  |                 |                 |  |     Logic    |
|  +-----------------+-----------------+  |              |
|                                         |              |
|  +-----------------+-----------------+  |              |
|  |                 |                 |  |              |
|  |  Scheduler # N  |  Run Queue # N  <--+              |
|  |                 |                 |                 |
|  +-----------------+-----------------+                 |
|                                                        |
+--------------------------------------------------------+

This way the locking conflicts when accessing the run queue is solved but introduces some new concerns:

How fair is the process of dividing tasks among run queues? What if one scheduler gets overloaded with tasks while others are idle? Based on what order a scheduler can steal tasks from an overloaded scheduler? What if we started many schedulers but there all so few tasks to do? These concerns lead the Erlang team to introduce a concept for making scheduling fair and efficient, the Migration Logic. It tries to control and balance run queues based on the statistics that collects from the system.

However we should not depend on the scheduling to remain exactly as it is today, because it is likely to be changed in future releases in order to get better.

As a conclusion, there are two question: 1. I want make a confirm whether re-queue problem really exist in async-programming world. 2. Besides, Is Erlang really has the problem if it handle tens of thousands of the process, especially use many GenServer.call in a request-response-chain?

Depending which Erlang version are you talking about there are different tradeoffs. Since there are multiple queues in newer Erlang versions your problem does not exist in the form you are specifying it.
I have seen Erlang (and its VM) handle millions of Erlang processes just fine, also used an Erlang based system to handle 100.000+ clients with really tight SLA on the latency. Not sure about the details of your problem, but a reasonably written Erlang/Elixir service can handle the workload you specified unless there is something you left out.

Will Erlang Scheduler make process causing re-queue problem?

1 Answers