I believe one should not confine event-driven only to applications that don't do synchronisation, that's part of the misconception that leads to thinking event-driven has higher performance. This is due to the fact that part of the problem with threads (as you mentioned) is synchronisation, but this is the same problem with event-driven applications. We have a web server experiment that shows comparable performance to an event-driven web server (ulib) with its various hacks to make it faster and is always on the top list on tech-empower.
Regarding memcached, the first reference you posted is from 2015, yes in 2015 memcached was in a very bad shape in terms of synchronisation and things have significantly changed from that version with locks per hash bucket rather than a global lock, avoiding try_lock and .... So those results are too old to rely on. Seastar moves network stack to user-level and if I remember correctly the scheduler consisted of multiple ever looping threads even if there was no work to do. Considering in our experiments 40-60% of the memcached overhead were coming from network I/O, there is no surprise about their results. I would call this a hack for sure.
I have not read the Anna paper to be able to comment, but it seems that they are creating a key-value store using the actor model. I briefly schemed through the paper, and I did not find anything that points to "killing any possibility for shared memory multi-threading as a concurrency model"; this is a very bold claim and if they do claim that, they should have really strong results.
But my guess is anna's whole actor model was implemented on top of threads and shared memory multi-threading? Which will be in contrast of that bold claim. I worked with actor models and implemented one as well, it is a perfect fit for many use cases but threads at least for now are the bread and butter of multicore programming.
Having said that, all these models have their respective place in the software world. What we are trying to show in our paper , through thorough experiments, is that the misconception that event-driven has higher performance than thread programming is not fundamentally true. Therefore, falling into asynchronous programming and create hard to maintain applications [1] only due to better performance has no merit.
The results of our to be published paper clearly confirm the claims of this paper and shows that if implemented well, threads can perform and scale as good as events with not much memory overhead.
I worked on this subject during my Phd, and the result is a paper that will be published in sigmetrics2020.
We developed an M:N user-level threading library and exhaustively tested it against event-based alternatives and pthread based solutions.
We used both memcached and webservers to test it on 32 core and 64 core servers.
Even connection/pthread looks promising in terms of performance.
I think it was the "flash boys" by Michael Lewis, that mentioned a Russian programmer that was very good at programming with pen and paper, and the reason was in old days there were not many computers around or you had to use punch cards to program. So the only option was to have the ability to write the code on paper and make sure everything is well thought of before you run the code on an actual computer.
It only makes sense if the interview process followed the same pattern in those days. The difference is there were not much information to remember, most probably if you knew few data structures and algorithms that was enough.
I feel the tech interview process, like so many other things, is still stuck in the past. Seems that the monks are still tying the cat to the tree without knowing why. Everyone seems unhappy about this but nothing changes.
Since IO Multiplexing in go is based on Edge-triggered epoll, you always need to do a write/read syscall (it happens underneath) before blocking the goroutine to arm the epoll to poll that specific FD. Also this approach relies on parking/unparking the goroutine and there is no way around it, since it is part of the runtime.
One way go can make it nonblocking is to do the read/write and return the result immediately, but this kind of call requires a call back function to be provided, so instead of parking/unparking the goroutine, the call back function is called (either directly or by "go cb_function"), It can be tricky to make it work, since the initial goroutine might not be allowed to call read on FD anymore (maybe exit from the goroutine if the read was unsuccessful). In addition, you still need to provide a buffer to read from, the 1 byte trick works though, but the buffer management can be done either if the read was successful or in the call back function. Also this approach makes the programming asynchronous and similar to event programming.
> I was also assuming a single kernel thread performs I/O via epoll/kqueue/etc. and either has its own queue from which other threads steal, or simply pushes results onto a random queue when requested I/O are complete. This accomplishes the migration I believe you were describing.
> When I/O needs to be done, you enqueue the uthread on the I/O queue and invoke a reserved file descriptor to notify the I/O thread, which then reshuffles its file descriptors and again calls epoll/kqueue.
If I remember correctly, what you described is similar to how golang perform I/O polling since they are using work stealing, except there is no dedicated poller thread, and threads take turn to do the polling whenever they become idle.
Also, with epoll/kqueue there is no need to enqueue uThreads and you can simply store a pointer(a struct that has reader/writer pointers to uThreads) with the epoll event that you create and recover it later from the notification, this way you can set the pointer when need to do I/O.
I agree a single poller thread does not scale as well as per kthread epoll instance, and that requires some meditation to provide a low overhead solution that does not sacrifice performance over scalability.
I am not sure if you are referring to the runQueue being used in Linux or the whole approach. I try to answer both:
Run queues can be part of any scheduler, they are queues with runnable tasks.
But as why the approach is worth while in user space, it has to do with low cost of operations (context switches) in user space, and also using cooperative scheduling instead of preemptive. Cooperative scheduling provides more control to the user over the tasks, and also has lower overhead since there is no need to manage a quantum for each taks (thread).
Well on the surface, yes! when I started I expected the same. For now there is no work stealing among kThreads. But let me dig into the problem a bit deeper so you get an idea why it might not be very straight forward (also it very much depends on the use case).
Usually these libraries either provide their own queue or rely on underlying event system e.g. epoll/kqueue to manage the state of the light weight threads. Also, the other main part is IO multiplexing, which can be done using select/poll/epoll/kqueue ...
Lets say if they are using some sort of queue, since there is no other thread in the system, thus no synchronization required and its as simple as pushing to the tail of queue and pulling from the head. Now, if I add more threads, now I have to think how I want to synchronize among threads. The straight forward way of doing this is using the same queue and multiplex among kernel threads and use Mutex and CV. However, Mutex has high overhead and is not very scalable (pthread_mutex does not scale well under contention in Linux). What about N-kernel-thread-local queues along with Mutex? Well, if you see the documentation this approach does better but has high overhead as well. What is next? remove the queue and add some sort of lock-free queue, either MPMC, MPSC, or SPSC. This requires some work to determine which one has lower overhead, in my case I have not tested SPSC, and for now settled with MPSC. So the queue part is totally gone, since they probably did not care about all this and used a simple queue.
Next, comes the IO multiplexing. Relying on an epoll instance per kernel-thread is absolutely fine specially for cases where uThreads stick to the same kernel thread, but as soon as I introduce the notion of migration then moving from on kernel-thread to another kenrel-thread means issuing at least two system calls (in case of epoll, deregister from current epoll instance and register to the new one). This has high overhead, so I need to provide some sort of common poller that do multiplexing over multiple kernel threads, but due to having more than one kernel thread, it means connections should be properly synchronized as more than one thread might try to access a connection. Also, it has to be done in a way with low overhead as migrations for my research require to have very low overhead. Thus, the IO multiplexing part should be replaced.
So the main parts are required to be changed, and I believe the effort required to make fundamental changes to an existing system might be more than the efforts required for writing it from scratch. Also for each part implemented, I did performance optimisations and build on top of that which helped to keep the performance at an acceptable level, it would be hard to do the same with an existing system as it requires to isolate various parts and optimise each part, which requires additional effort.
Thanks for mentioning this, it is indeed very related and very interesting. I am not sure why not me or people around me were aware of Qthread, it has very good support for various architectures and provides many interesting features. It has many similarities with I have in mind for a concurrent library, and even some research goals seems to be very close to mine. Specially the notion of affinity and locality is what I am focusing on in uThreads. I am going through the papers and the source code at the moment to see what are the similarities and differences.
uThreads is still a work in progress and I have specific plans for it in the future that might differ of what Qthreads is trying to accomplish. For now my focus is more on providing auto tuning of Clusters based on the workload. I also will try to explore the pros and cons of uThread migration based on Cluster placement (NUMA and cache locality), and from the 2008 paper it seems that it is what you are trying to study as well. I am open to collaboration if there is an ongoing study around this topic.
Seems like a very mature library, I can't answer your question before I go through their documentation and code. Also, I find your question a bit abstract, since I am not aware of the details of the problem you are trying to solve, I cannot reason why any library or tool can be better over other libraries. In your case, TBB might fit your requirements and it might be hard to give a reason to switch to another library.
I have seen this before. Those are very good points, and I am trying to move this library towards supporting a SEDA type architecture with dynamic control and auto tuning runtime parameters.
Do you have anything specific in mind? The only code I found similar to this is uC++ [1], which has way more features and more sophisticated scheduler. I am using this as part of my research and wanted to have sth very simple.
For all N:1 mappings, since there is only a single process, there is no need for synchronization, also there is no need for any scheduler as a simple queue suffice. But as soon as multiple threads are introduced, there is a need for orchestration among threads and it also changes all other aspects of the code. Of course, I could develop on top of an existing codebase, but I suspect I had to change so much that it is better to start from scratch anyway.
Good idea, I probably write a blog post on this later. If you take a look at [1], I explain the difference between N:1 and M:N mappings. StateThreads uses a N:1 mapping which means you can multiplex many fibers over a single thread and to take advantage of multi-processors you can have M processes that do N:1 mapping, which is a common practice (libmill, libdill, ...). But with uThreads you can multiplex many fibers over many kernel threads.
In libdill approach, you are probably limited to only multiplex connections over multiple kernel threads. And when a connection is accepted over a kernel thread it has to perform all further instructions over that kernel thread. So it gives you a bit of control over which cores to be utilized but after that you do not have control over what part of the code should be executed on each core.
Using uThreads you can decide what part of the code should be executed over each kernel thread and, if taskset is used, which core to execute your code. You can do this by creating Clusters and using migration or uThread creating in runtime. Thus you can decide which thread is used to multiplex connections and which one is used to run CPU bound code in addition to having a thread pool for example to do the disk IO asynchronously. Ultimately, one can create a SEDA[1] like architecture using uTrheads. Also you can always use uThread as a single threaded application.
You are right, I have access to machines with higher number of cores, but they have multiple sockets and at some point I need to address the cross NUMA cost which adds a whole new level of complexity and design decisions.
For sure at some point the poller thread will be saturated and the program will not scale past a certain number of threads. I used to have a poller thread per cluster for better scalability, but that would add overhead for migrations between clusters, thus I had to remove it for now until I can somehow find a low overhead solution. uThreads is a work in progress and all these need to be carefully considered in the future :) Thanks for your feedback
Right, however segmented stacks are have high overhead and stack copying is not very easy in C/C++. Thus, for now uThreads only support fixed size stacks, I know it makes it harder to be used in production, and in the future I might provide optional segmented stacks.
As for why not using `boost::context`, I am implementing uThreads as part of my research in uwaterloo, I wanted to have full control over the code and be able to optimize for performance as much as I can. Thus, tried to avoid relying on any third party code when I started :)
Regarding memcached, the first reference you posted is from 2015, yes in 2015 memcached was in a very bad shape in terms of synchronisation and things have significantly changed from that version with locks per hash bucket rather than a global lock, avoiding try_lock and .... So those results are too old to rely on. Seastar moves network stack to user-level and if I remember correctly the scheduler consisted of multiple ever looping threads even if there was no work to do. Considering in our experiments 40-60% of the memcached overhead were coming from network I/O, there is no surprise about their results. I would call this a hack for sure.
I have not read the Anna paper to be able to comment, but it seems that they are creating a key-value store using the actor model. I briefly schemed through the paper, and I did not find anything that points to "killing any possibility for shared memory multi-threading as a concurrency model"; this is a very bold claim and if they do claim that, they should have really strong results.
But my guess is anna's whole actor model was implemented on top of threads and shared memory multi-threading? Which will be in contrast of that bold claim. I worked with actor models and implemented one as well, it is a perfect fit for many use cases but threads at least for now are the bread and butter of multicore programming.
Having said that, all these models have their respective place in the software world. What we are trying to show in our paper , through thorough experiments, is that the misconception that event-driven has higher performance than thread programming is not fundamentally true. Therefore, falling into asynchronous programming and create hard to maintain applications [1] only due to better performance has no merit.
[1] https://cacm.acm.org/magazines/2017/4/215032-attack-of-the-k...