How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Kelet

Posted Thu, 06 Feb 2014 19:24:40 GMT

Hello,

I'm new to both asynchronous i/o and fibers. I'm trying to grok on a high-level how fiber scheduling works in vibe-d.

As I understand, Fibers in DLang must be called, and then somewhere within the Fiber it must yield or naturally end if it wants to relinquish control back to the caller. The idea is that a Fiber scheduler could take some aggregate of Fibers and run them in an efficient way.

I'm interested in studying vibe-d's approach to this fiber scheduling problem. However, I'm a bit hazy even after reading the source code – it seems to be above my head.

My understanding, which is most definitely flawed (feel free to correct!), is that

There is a queue of Fibers (or some derivative of Fibers)
If a Fiber issues a vibe sleep(), a driver timer (say libevent) is created, and during the sleep time, events are processed (the event loop goes through some iterations). When the timer goes off, the Fiber is called again and resumes. Perhaps some other blocking operations are similar.
If a Fiber yields or ends, events are processed and the next Fiber in the queue is called. If it was a yield, it is placed in the back of the queue. If it ended, it is removed from the queue.
Each Thread probably has its own Fiber scheduler.

And some things I can't figure out:

When and where are the new Fibers added to the Fiber 'queue'?
Why is there so much timer code in the drivers? I can't think of much use except for making a timer for when Fibers sleep.
Does each Thread have its own Fiber queue so to speak?
How are Fibers balanced between Threads when worker threads are enabled?

Now obviously I'm not looking for an exacting in-depth technical description, just a high-level description or psuedocode with the major points, because I feel like I'm really missing out on some fundamental understanding. I'm currently more interested in fiber scheduling because as it stands, I know I'm missing some significant chunks.

Regards,
Kelet

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Stefan Koch

Posted Fri, 07 Feb 2014 07:20:02 GMT in reply to Kelet

Hi,
I can answer just one question, as I have not that much experience in vibe.d

Does each Thread have its own Fiber queue so to speak?

Yes fibers are thread-local by default (if there were shared, what would be the point).

Have you programmed asynchronously before ?
If not, please read the paper linked below
http://cs.brown.edu/courses/cs196-5/f12/handouts/async.pdf

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Sönke Ludwig

Posted Fri, 07 Feb 2014 10:51:52 +0100 in reply to Kelet

Am 06.02.2014 20:24, schrieb Kelet:

Hello,

I'm new to both asynchronous i/o and fibers. I'm trying to grok on a high-level how fiber scheduling works in vibe-d.

As I understand, Fibers in DLang must be called, and then somewhere within the Fiber it must yield or naturally end if it wants to relinquish control back to the caller. The idea is that a Fiber scheduler could take some aggregate of Fibers and run them in an efficient way.

I'm interested in studying vibe-d's approach to this fiber scheduling problem. However, I'm a bit hazy even after reading the source code – it seems to be above my head.

My understanding, which is most definitely flawed (feel free to correct!), is that

There is a queue of Fibers (or some derivative of Fibers)

If a Fiber issues a vibe sleep(), a driver timer (say libevent) is created, and during the sleep time, events are processed (the event loop goes through some iterations). When the timer goes off, the Fiber is called again and resumes. Perhaps some other blocking operations are similar.

If a Fiber yields or ends, events are processed and the next Fiber in the queue is called. If it was a yield, it is placed in the back of the queue. If it ended, it is removed from the queue.

Each Thread probably has its own Fiber scheduler.

Sounds all about right.

And some things I can't figure out:

When and where are the new Fibers added to the Fiber 'queue'?

They are basically added only when yield() is explicitly called by the
user. As long as only blocking operations cause a task/fiber to yield,
it's the OS/event loop which determines which fiber will be resumed in
which order.

Why is there so much timer code in the drivers? I can't think of much use except for making a timer for when Fibers sleep.

The code guarantees that each timer uses up a minimum amount of memory
(only one OS timer is used), so that it can be guaranteed that timers
are light-weight and can be used safely in large numbers.

Does each Thread have its own Fiber queue so to speak?

Yes, also, as Stefan already said, a fiber is always exclusive to the
thread in which it was created, so fibers are never transferred between
threads. This is necessary to not break D's threading model (shared
and thread-local storage).

How are Fibers balanced between Threads when worker threads are enabled?

It depends. For the normal runWorkerTask, the first worker thread that
becomes idle will pick up the task an process it, so that usually all
threads will have a similar workload. In case of thread-distributed HTTP
request processing (HTTPServerOption.distribute), it's again the
OS/event loop which decides what thread will accept each incoming
connection.

Now obviously I'm not looking for an exacting in-depth technical description, just a high-level description or psuedocode with the major points, because I feel like I'm really missing out on some fundamental understanding. I'm currently more interested in fiber scheduling because as it stands, I know I'm missing some significant chunks.

Regards,
Kelet

A final note that hasn't been mentioned, each fiber can be reused for
multiple tasks in sequence. So whenever a task has finished, the
corresponding fiber will be yielded and then can be reused later for
another task.

In the end the concept is really quite simple. But I'll also write up a
small article about how this works (it has been planned for a long
time), but the time currently doesn't really permit that and there are
still a few unknowns that I'd like to carve out first (mostly w.r.t
WinRT) before finally fully committing to a certain model (it's already
99% certain, though).

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Kelet

Posted Fri, 07 Feb 2014 19:05:16 GMT in reply to Sönke Ludwig

Thank you Sönke and Stefan for the replies!

I guess my thoughts are that compared to just throwing function pointers or delegates into a queue to be ran would come to similar performance (if not better) for a certain case of situations. Is this true? Basically, if sleep is unused, and yields are unused (let us assume that the functions all execute fast and thus don't need yield), then just maintaining a queue of function pointers/delegates would be faster? Or am I misunderstanding.

Is this strength of this approach having access to yield and knowing that things will be done during sleeps?

On Fri, 07 Feb 2014 10:51:52 +0100, Sönke Ludwig wrote:

In the end the concept is really quite simple. But I'll also write up a
small article about how this works (it has been planned for a long
time), but the time currently doesn't really permit that and there are
still a few unknowns that I'd like to carve out first (mostly w.r.t
WinRT) before finally fully committing to a certain model (it's already
99% certain, though).

I would be very interested in reading it.

Regards,
Kelet

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Sean Kelly

Posted Fri, 07 Feb 2014 19:29:27 GMT in reply to Kelet

On Fri, 07 Feb 2014 19:05:16 GMT, Kelet wrote:

Thank you Sönke and Stefan for the replies!

I guess my thoughts are that compared to just throwing function pointers or delegates into a queue to be ran would come to similar performance (if not better) for a certain case of situations. Is this true? Basically, if sleep is unused, and yields are unused (let us assume that the functions all execute fast and thus don't need yield), then just maintaining a queue of function pointers/delegates would be faster? Or am I misunderstanding.

Simply throwing function pointers in the queue is faster. Or if not faster it certainly uses less memory. But it's a much harder model to program to, and making sense of someone else's code written this way is tricky. You're basically creating a state machine as a stand-in for not having a persistent stack to store state on, and either this ends up being a gigantic switch statement (unmaintainable but easy to follow the program flow) or a bunch of loosely related function pointers (super flexible but difficult to follow and with next to no context info when an error occurs).

The real advantage of using fibers like vibe.d does is that it dramatically lowers the barrier for entry, while still maintaining comparable performance. You'll probably end up with more cache misses since each fiber has its own stack, but backtraces are suddenly possible and you can have people who don't understand async programming working on the code.

One thing I'm not entirely sure of is how vibe.d handles outbound connections. Like say I get a request from the user. This request comes across some client connection and so is backed by its own fiber. Now what if I need to issue a request to some other service while processing this transaction? Any IO on the secondary connection needs to yield and return to that client connection's stack. I imagine vibe.d manages this automatically, but it's a bit further than I've gotten in my own experimentation. I suppose an alternative would be to spawn the outbound connection in its own fiber and use message passing to mediate between them. Then the client connection would block on receive() until that secondary request completes and sends its response.

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Etienne

Posted Sat, 08 Feb 2014 02:22:50 GMT in reply to Sean Kelly

On Fri, 07 Feb 2014 19:29:27 GMT, Sean Kelly wrote:

On Fri, 07 Feb 2014 19:05:16 GMT, Kelet wrote:

Thank you Sönke and Stefan for the replies!

Before working with vibe.d I was quite into boost::asio which uses the fibers concept also but they're called strands, co-routines and the stack is saved in a yield context and so on. The coroutines can be stackful or stackless. I think it's a nice learning experience to see how they do it as well.

http://www.boost.org/doc/libs/1540/doc/html/boost_asio/overview/core/coroutine.html

One thing I'm not entirely sure of is how vibe.d handles outbound connections. Like say I get a request from the user. This request comes across some client connection and so is backed by its own fiber. Now what if I need to issue a request to some other service while processing this transaction? Any IO on the secondary connection needs to yield and return to that client connection's stack. I imagine vibe.d manages this automatically, but it's a bit further than I've gotten in my own experimentation. I suppose an alternative would be to spawn the outbound connection in its own fiber and use message passing to mediate between them. Then the client connection would block on receive() until that secondary request completes and sends its response.

When vibe.d receives a new connection, it picks an unused fiber or creates one. Any fiber that yielded already has some stack data thus aren't candidates to receiving a new connection.
When vibe.d receives or sends data from an existing connection, it'll load it in the fiber that owns the connection. Every fiber has an ID number and the connection is attached to this ID, so any activity through this connection will return data to the yielded fiber that owns it.
Which brings me to when vibe.d creates a new connection. The ID of the fiber that creates the connection is saved and sent to libevent, which will provide it back to vibe.d through any activity in the callback functions : buffereventsetcb(bufevent, &onSocketRead, &onSocketWrite, &onSocketEvent, cctx); (libevent2.d line 272)

So, the fibers aren't segmented by connection per se ; you'll find it's not limited to 1 connection per fiber.

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Kelet

Posted Sat, 08 Feb 2014 03:18:36 GMT in reply to Etienne

On Sat, 08 Feb 2014 02:22:50 GMT, Etienne wrote:

Before working with vibe.d I was quite into boost::asio which uses the fibers concept also but they're called strands, co-routines and the stack is saved in a yield context and so on. The coroutines can be stackful or stackless. I think it's a nice learning experience to see how they do it as well.

http://www.boost.org/doc/libs/1540/doc/html/boost_asio/overview/core/coroutine.html

https://github.com/olk/boost-fiber was proposed to Boost recently, although it failed (for now). It includes a Fiber scheduler and some convenience things on top of Boost's coroutines. I wonder how it compares to the stuff inside of vibe-d.

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Sönke Ludwig

Posted Sat, 08 Feb 2014 10:08:42 +0100 in reply to Sean Kelly

Am 07.02.2014 20:29, schrieb Sean Kelly:

One thing I'm not entirely sure of is how vibe.d handles outbound connections. Like say I get a request from the user. This request comes across some client connection and so is backed by its own fiber. Now what if I need to issue a request to some other service while processing this transaction? Any IO on the secondary connection needs to yield and return to that client connection's stack. I imagine vibe.d manages this automatically, but it's a bit further than I've gotten in my own experimentation. I suppose an alternative would be to spawn the outbound connection in its own fiber and use message passing to mediate between them. Then the client connection would block on receive() until that secondary request completes and sends its response.

Each fiber can (usually) only have one connection active at the same
time, that's true. However, a connection only "owned" by a single
fiber/task while it is in one of its blocking methods, such as read or
write. When nothing is done on the connection, it is not owned by any
fiber and any events in that time will more or less be ignored.

The only exception here is that for any accepted incoming connection a
task is created to invoke the handler callback and this task will
automatically close the connection once the callback returns. But this
just to avoid dangling connections when uncaught exceptions occur and is
not really related to the ownership in the event processing sense.

BTW a nice property of (non-worker) tasks is that since they run in the
same thread, it's often possible to save the overhead of message passing
completely and simply use stack/thread local vars. For example to do
multiple outgoing requests in parallel:

void showClusterStats(HTTPServerRequest req, HTTPServerResponse res)
{
     Task[] tasks;
     string[] stats;
     foreach (node; m_cluster) {
         tasks ~= runTask({
             requestHTTP(node.url ~ "/status",
                 (scope req) {}
                 (scope res) {
                     // safely access variable of the outer scope
                     stats ~= res.bodyReader.readAllUTF8();
                 }
             );
         });
     }

     // wait for all tasks to finish
     foreach (t; tasks) t.join();

     // write response
     res.writeBody(...);
}

Re: How does fiber scheduling/fiber-thread mapping work?

Permalink: HTTP NNTP

Ľudovít Lučenič

Posted Wed, 26 Apr 2017 17:33:17 GMT in reply to Sönke Ludwig

On Fri, 07 Feb 2014 10:51:52 +0100, Sönke Ludwig wrote:

... But I'll also write up a
small article about how this works (it has been planned for a long
time), ...

Sönke, have you managed to publish that article somewhere in the meanwhile? I am studying the threading/fiber/task implementation in vibe.d and there are some fundamental questions about the whole concept or architectural aspects that I cannot find answers to. For example, how can technically happen that a Task is being resumed in a foreign thread? Is it that a Task can be moved to another or can have changed its associated Fiber/CoreTask ?