Libuv: making libuv thread safe

[trevnorris]

Before writing a LEP wanted to get feedback on the feasibility/acceptability of the idea to make libuv thread safe. A few basic components:

• Look into making the various queues (e.g. handle queue) thread safe without needing a lock.
• Each new thread that wants to operate on the event loop needs to register with the event loop. If nothing is registered then it bypasses all thread safe operations. Hopefully to remove any performance regression having multiple threads would cause.
• API calls use uv_thread_self() to manage where the result should be sent after the operation is complete.

I wrote the library https://github.com/nubjs/libnub to help make libuv thread safe a few years ago, but it works completely on locks. Causing a lot of overhead. I'll only pursue this if it's possible to not introduce performance regression when no additional threads are in use, and only very minor performance regression when they are in use.

So, thoughts?

[bnoordhuis]

Look into making the various queues (e.g. handle queue) thread safe without needing a lock.

That isn't necessary per se. Mutexes and lock-free structures are both based on the compare-and-swap primitive; they perform on par in the uncontended case.

Under contention traditional mutexes incur a hit because they suspend the thread but for short critical sections that can be avoided by using spinlocks.

For longer critical sections, suspension is usually the way to go because you end up wasting CPU cycles otherwise.

Mutexes and spinlocks have the benefit that they pretty much guarantee forward progress (outside of deadlocks), something that is usually much harder to reason about with lock-free structures.

API calls use uv_thread_self() to manage where the result should be sent after the operation is complete.

I think that is going to be the biggest challenge: devising a scalable way to send and deliver events across threads.

I haven't thought to deeply about it but off the top of my head:

1. There should probably be a way to deliver a single event to multiple threads so that two threads can both watch fd 42.

2. You probably don't want all threads to call epoll_wait() simultaneously because of kernel scalability and thundering herd problems.

[anton-malakhov]

Hi, I'm also extremely interested in how to use libuv in multi-threading mode efficiently. We need this to implement first-class multi-threading support for Julia-lang (https://github.com/JuliaLang/julia/pull/22631). This problem occupies my thoughts for few weeks already.
Basically I agree with the design approach of libuv that keeps it mostly thread-unsafe while implementing some minimal set of thread-safe functions. It helps to keep serial performance high which I confirmed with https://github.com/MagicStack/vmbench that shows it on par with go-lang. However, if the go-lang implementation in this bench is allowed to use threads, it shows about 4x speedup comparing to the single-threaded mode for simple tcp-echo server!

I tried to come-up with some designs which would use existing functionality of libuv in order to recover that performance but it looks like I need at least some additional extensions in libuv.

The closest approach with the current design is to use multiple event loops. However, since Julia is computational or even general-purpose language, it is very possible that callbacks might stuck in user code computing something heavily and thus blocking all the events on particular thread. Another problem is how to distribute handles and requests across the loops. I started to think that it might be possible to "steal" loops from threads or just having a pool of uv_loops where each is protected by its own spinlock so that any operation tries to lock a loop and if it is busy, it goes to another one. Unfortunately, this raises some other questions like complexity of tracking where each operation runs and waiting on all the loops at the same time (run in NOWAIT mode in round-robin? what's about some sleep?). It might still be feasible though, so I could submit a feature request, which suggests adding loop merging(+splitting) functionality or a way to transplant a handle (e.g. during a walk) to another loop if you like this approach.

Of course, the best solution is to stick with single event loop (like in go-lang) and to introduce support for adding requests from other threads and distribute its callbacks.
The first part here might be pretty simple and implemented as a separate functionality, e.g. it might be multiple-producer-single-consumer (or just locked for starters) queue that aggregates all the requests from other threads while a prepare_handle runs all the requests in a dedicated thread running uv_run() or under the lock which serializes execution of run(NOWAIT) calls from multiple threads.

The biggest problem arises with the callbacks. I could use additional level of callback wrappers in order to allow callbacks to be stored in a taskpool, which other threads could use to distribute the work. Unfortunately, it solves only problem with heavy user code and does not allow tcp-echo benchmark to scale because it spends the most time in read() and write() syscalls, here is the profile summary from my experiment:

Top Hotspots
Function    Module  CPU Time
__read  libpthread.so.0 2.280s
write   libpthread.so.0 2.279s
uv__read    run.exe 0.157s
__GI___libc_malloc  libc.so.6   0.091s
__GI_   libc.so.6   0.079s
[Others]        0.100s

So, to solve this problem efficiently, we need to allow delegation of uv__io_cb callbacks themselves. For example, libuv could introduce a special callback, which serves to run other callbacks. So, I could use that to distribute event processing across threads instead of direct calls. Unfortunately, this is not enough, since these internal callbacks and functions like uv__stream_io, uv_server_io, uv__read, and etc.. initiate other requests accessing loop structure. In order to make it thread-safe, some refactoring is indeed needed. For example, splitting these functions to separate out heavy parts like read/write syscalls would work well or implementing request queue at the internal level as suggested above.

Introducing fine-grain locking is another and probably simplest alternative of this refactoring. E.g. structures like loop and handle might have an optional lock callback. So, working with uv_loop would require to get the lock, while uv_run() could skip calling callbacks which belong to handles that are currently busy. Using profiling feedback, we can surgically isolate points of contention and release locks during these heavy OS operations.

So, two additional optional callbacks, which are not used in regular single-threaded setup, will not affect default use-cases while making scalable multi-threading possible.

Please point me to any other proposals made for multi-threading support in libuv and what makes the most sense for core developers across all these proposals.
Thanks!

[trevnorris]

@bnoordhuis

That isn't necessary per se. Mutexes and lock-free structures are both based on the compare-and-swap primitive; they perform on par in the uncontended case.

For simple operations like insert/head/remove it'd be possible to do them with only a memory barrier (I've only tested this on x64) but since operations like foreach are necessary that probably rules out the possibility of using a memory barrier.

1. There should probably be a way to deliver a single event to multiple threads so that two threads can both watch fd 42.

I hadn't considered this case, and tbh i'm not sure how it'd be possible to do something like allow two different threads to call uv_read_start() on the same stream. My initial pass was to cover something much simpler.

1. You probably don't want all threads to call epoll_wait() simultaneously because of kernel scalability and thundering herd problems.

Think we have a different idea of what thread-safe libuv implies. I was thinking the API calls themselves would be thread safe, and the event loop would proceed normally. Unless you're referring to having every API call from other threads cause the event loop to flip.

I was thinking along the lines of adding an additional field uv_thread_t handle_thread to UV_HANDLE_FIELDS. Then on a call like uv_tcp_init() it would assign handle_thread = uv_thread_self(). This "registers" the handle with the thread responsible for the *_init() call. Then a call to something like uv_write() will use that information to determine which thread should run the callback.

There's also something about transferring ownership of a handle between threads. Though one goal was figuring out how this could be done in a way that has the least possible impact to the current API.

@anton-malakhov On the point of not blocking the event loop with CPU intensive tasks, would doing something like having a server open on one thread and then passing each new connection to another thread to be handled sound along the lines of what you were thinking?

[anton-malakhov]

@trevnorris not exactly. I'm solving general problem here, not specific to a web-server. In this setup we have multiple worker threads of the language runtime that pick available work according to a scheduling algorithm, which also can include checking/processing of I/O events at any time - dynamically. Besides for blocking calls, I'd go with a system without dedicated thread for running event loop. Instead, all the worker threads are allowed to query for events and run the callbacks because any user callback can block for unrestricted amount of time. Blocking calls run on additional threads (like in libuv) which does not contribute to over-subscription (that kills compute performance) because they are mostly sleeping in the OS. This is how I/O is implemented in Go-lang runtime for example.

I'm working on implementation of one idea for libuv that is close to what I described in the message above w.r.t. the delegation of uv__io_cb callbacks but even simpler - no delegation is needed, no locks are needed inside libuv. Instead, I introduced 'unlocking' callback which allows releasing a user-managed lock while calling to the heavy-loaded syscalls like write() and read(). This comes from the same idea supported by benchmarks profile that internal bookkeeping of libuv is lightweight enough to allow scaling even with a single lock while the most time is spent in these OS calls, which are doing the real work (mostly copying data) - even if configured in non-blocking mode.

So, the idea is to allow running heavy syscalls in parallel marking them via callbacks while avoiding any additional atomic operations or locks inside libuv itself.

Unfortunately, it's not that simple. libuv is already designed with some sort of concurrency in mind where any user callback can call almost any uv function, which means that the state of internal structures can be modified after returning from the callbacks. This needs to be extended to this additional callback and these points of potential parallelism where it is applied. And this is the hardest part for me since I'm not expert in libuv implementation. Nevertheless, I managed to prototype this approach for Linux relatively fast by adding sometimes ugly shortcuts into libuv's logic. But if you guys like this idea overall, I might use your help in order to make it complete and production-ready. The modified tcp_pump100 benchmark shows some promising speedups, despite not being quite stable yet (including the original one?):

[10:52:17 fxsatlin01 libuv] (multithreading/bench)$ out/Debug/run-benchmarks tcp_pump100_client
ok 1 - tcp_pump100_client
# tcp_pump10_server: 32.7 gbit/s
# tcp_pump10_client: 32.7 gbit/s
[10:55:33 fxsatlin01 libuv] (multithreading/bench)$ out/Debug/run-benchmarks tcp_pump100_threads_client
ok 1 - tcp_pump100_threads_client
# tcp_pump10_server: 52.7 gbit/s
# Thread 0x7f21deeb5f40 finished 4498174 roundtrips
# Thread 0x7f21e06b8f40 finished 4519404 roundtrips
# Thread 0x7f21df6b6f40 finished 4485044 roundtrips
# Thread 0x7f21dfeb7f40 finished 4468678 roundtrips
# Thread 0x7ffcf22bfda0 finished 4515856 roundtrips
# Unlock calls = 9539936
# tcp_pump10_client: 52.7 gbit/s
# Thread 0x7fc15e195f40 finished 1433 roundtrips
# Thread 0x7fc15e996f40 finished 11 roundtrips
# Thread 0x7fc15f197f40 finished 3020 roundtrips
# Thread 0x7fc15d994f40 finished 4 roundtrips
# Thread 0x7ffc5e7f0dc0 finished 46 roundtrips
# Unlock calls = 41407060

Though it is not stable enough yet and not 4x faster like in the case of Go version, but I hope it looks good enough to attracts you attention and keep discussing this idea.

[anton-malakhov]

@trevnorris Hi, any feedback on the idea above?

[b-xiang]

making libuv thread safe? This is my thought:
Only separate xxx_init into two function:one is xxx_init that init handle whitout loop, the other is xxx_register that register handle with loop in loop thread.
First make uv_async_t is thread safe: modify uv_async_init only init uv_async_t without loop, new uv_async_t and call uv_async_init in one thread, and call uv_async_send(loop,uv_async_t) to send uv_async_t into the other thread, then in this thread register uv_async_t to loop, so we can call uv_async safely.
Next ,we modify other handles. We can new handle in one thread,and put them into the other thread by uv_async.
This's all.How do you think?

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.