12 ms·
Making the Tokio scheduler 10x faster
- bhauer 7y agoAwesome work! FWIW: Hyper is among several that are bandwidth-limited by the 10-gigabit Ethernet in our (TechEmpower) Plaintext test. We hope to increase the available network bandwidth in the future to allow these to higher-performance platforms an opportunity to really show off.
- carllerche 7y agoThat makes sense to me :) Excited to see that happen!
- GonzaloQuero 7y agoThis might be slightly off topic, but what are the others in this same space?
- nicoburns 7y agoPresumably everything at the top of the list: https://www.techempower.com/benchmarks/#section=data-r18&hw=ph&test=plaintext https://www.techempower.com/benchmarks/#section=data-r18&hw=...
- bhauer 7y agoIn the Round 18 Plaintext results that the OP linked to [1], you can see a pretty clear convergence at ~7 million requests per second, which I've screen captured in [2]. [1] https://www.techempower.com/benchmarks/#section=data-r18&hw=ph&test=plaintext https://www.techempower.com/benchmarks/#section=data-r18&hw=... [2] https://www.techempower.com/images/misc/converge.png https://www.techempower.com/images/misc/converge.png
- GonzaloQuero 7y agoThanks!
- jxcl 7y agoHow can you tell how each test is bottlenecked? Is it something as simple as saying that if the processor isn't at 100% utilization then the bottleneck is somewhere else? I read a long time ago about how the linux kernel handled incoming packets in a really inefficient way that led to the network stack being the bottleneck in high performance applications. Is that no longer true? I'd love to learn more about this whole area if anyone has any good links.
- wmf 7y agoIn this case you'd want to discover a network bottleneck by looking at network utilization directly using a command like `sar n DEV 1`. (from http://www.brendangregg.com/Articles/Netflix_Linux_Perf_Analysis_60s.pdf http://www.brendangregg.com/Articles/Netflix_Linux_Perf_Anal... ) It's generally possible to go 3x-10x faster than Linux if you make some tradeoffs like dedicating cores to polling. See https://www.usenix.org/node/186147 https://www.usenix.org/node/186147 and https://wiki.fd.io/view/VPP/What_is_VPP%3F https://wiki.fd.io/view/VPP/What_is_VPP%3F Moore's Law excuses a lot of sins, however, so on the latest servers Linux is probably adequate up to 100 Gbps for most use cases.
- pnako 7y agoWell, to start with you can actually compute the optimal number of packets per second, if you know the bit rate and the packet size. https://packet.company/ethernet-statistics https://packet.company/ethernet-statistics So the theoretical optimum is 14.88 Mpps (millions of packets per second). That's with the smallest possible payload. You need to divide that by two because the test involves both a request and a response, which gives you 7.44 million requests per second as the theoretical maximum. The best tests max out around 7 M rps. This gives an implied overhead of about 6%, which corresponds to the HTTP overhead.
- Hikikomori 7y agoWhy would you divide by two? Tx/Rx are separate.
- 7y ago
- fulafel 7y agoOut of curiosity, are there any that saturate 100GBE? We should be long past 10GBE by now imo.
- Matthias247 7y agoThe benchmarks test something very specific: A ton of tiny requests on keepalive connections. Those tiny requests are not very IO efficient, and therefore 10GBit/s is already a lot. However if you would add a benchmarks to download 10MB static files the network utilization would likely go a lot up - even if the same frameworks are used.
- erikpukinskis 7y agoThank you for the detailed write up! Why are their many processors? If it’s all one thread, why not just use one processor?
- carllerche 7y agoThere is one processor per thread. Sorry, the article must not have been clear. If you can point out where in the article you got the impression there were multiple processors per thread, I can try to update the article to fix.
- erikpukinskis 7y agoI just got a bit into the “One queue, many processors” section and that’s where I got confused. Knowing it’s one processor per CPU is the information I needed. Thanks!
- carllerche 7y agoFrom that section. > There are multiple processors, each running on a separate thread. It's probably easy to miss, do you have thoughts on where else this can be clarified?
- mopierotti 7y agoNot OP, but I had to go back and double check that this was true when I saw that the Hyper benchmark at the bottom only used 1 thread. Wouldn't you want to test on multiple?
- carllerche 7y agoThe Hyper benchmark uses multiple threads. When I ran the benchmark, I modified the version found in Hyper's github to use both the old multi-threaded scheduler and the new multi-threaded scheduler. I probably should make that clear in the article.
- bluejekyll 7y ago
- cormacrelf 7y agoYou should sign your name under the blog post. So many references to "I" and I didn't know who to be impressed by until I clicked through to the PR.
- deleted 7y ago[deleted]
- carllerche 7y agoAuthor here. I'll be watching the comments and can answer any questions! I do want to make clear that most of the optimizations discussed are implemented in the Go scheduler, which is where I discovered them. I wrote the article to call them out as they were not easy to discover.
- networkimprov 7y agoThe Go team is working on an update of its scheduler to make it preemptive. Will Tokio follow suit? https://github.com/golang/go/issues/24543 https://github.com/golang/go/issues/24543
- carllerche 7y agoMy understanding of that PR is it relates to how the Go compiler does code generation. Rust takes a different approach and is about to ship `async / await` which is a different strategy. Preemption is out of scope for Tokio as we are focusing on a runtime to power Rust async functions. So, for the foreseeable, Tokio will using "cooperative preemption" via `await` points.
- deleted 7y ago[deleted]
- 15155 7y agoIIRC: one of the issues with the original Rust stdlib greenthread implementation was that it's extremely difficult to preempt execution in a systems language. It's also quite difficult to add userland execution preemption without incurring significant performance penalties. How do you preempt syscalls or FFI calls? (Go will almost certainly also have this issue with cgo modules) I would be very surprised if preemptible Futures are something Tokio can or would implement.
- wbl 7y agoWhat does systems mean here? There is a dirty trick with a NOP and self rewriting code that's quite cheap when not triggered. I think java does it that way.
- williamallthing 7y agoReally cool. Tokio is the core of Linkerd (https://linkerd.io https://linkerd.io) and I am really excited to see exactly what kind of impact this will have on Linkerd performance. A super fast, super light userspace proxy is key to service mesh performance.
- earhart 7y agoI thought this was super interesting; it's great to see a solid writeup. The consumer-side mutex works pretty well, until you take an interrupt while holding it; then, you need to make sure you're using an unfair mutex, or you'll get a lock convoy. The non-blocking version isn't hard to write, though. IIRC, for the Windows threadpool, I used https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.... for the implementation. I'm really impressed by the concurrency analysis tool; again for the threadpool, we used model-based-testing to write tests for every permutation of API calls, but we never got down to the level of testing thread execution permutations; that's amazingly good to see, and really builds confidence in their implementation.
- carllerche 7y agoThanks! I agree with your assessment of the Mutex. Improving that is included in the follow up work. I could have kept working on this for many more months... but my collaborators were starting to get grumpy and telling me to ship already :)
- tmail 7y agoTIL about lock convoys, thanks for sending me down this rabbit hole^^
- karmakaze 7y agoHowdy, I'm not familiar with Tokio (or Rust much). Is Tokio sort of like Node for Rust (packaged as a library rather than executable)? Or maybe more like Scala Akka Futures?
- lijogdfljk 7y agoI don't know Scala Futures.. but I'd guess those. Tokio is a runtime for managing Rust's Futures. Aka, the schedule that manages the various jobs (Futures) to run and etc.
- carllerche 7y ago"Node for Rust" is a good way to think about it! From what I know about Akka, I believe Akka does more than Tokio. For example, Akka manages a supervision tree. I believe Akka is trying to be more of an actor system where as Tokio is just trying to provide an asynchronous runtime for Rust.
- karmakaze 7y agoYes, it's confusing that Akka does both Futures and Actors (that it's well-known for). I've used and really liked Akka Futures so would probably much like Tokio.
- AtlasBarfed 7y agoIsn't node a single threaded event loop, while this and Go use multiple threads and queues to support multiple threads and processors? They even went into that with the comparison with Seastar. If this is better than Seastar, someone should start on porting ScyllaDB to Rust. Does Rust have a userspace TCPIP stack like Seastar? I think that is the other major advance Seastar uses for speedup.
- karmakaze 7y agoNode (like browsers now) have Worker Threads though I haven't used the Node ones myself.
- 7y ago
- zzzcpan 7y ago"Many processors, each with their own run queue" "Because synchronization is almost entirely avoided, this strategy can be very fast. However, it’s not a silver bullet. Unless the workload is entirely uniform, some processors will become idle while other processors are under load, resulting in resource underutilization. This happens because tasks are pinned to a specific processor. When a bunch of tasks on a single processor are scheduled in a batch, that single processor is responsible for working through the spike even if other procesors are idle." The trade off of this is high performance over uniform utilization, which is a better goal than loading cores evenly. And all you have to do to make use of it is a bit of thought about your load distribution, but you also have plenty of thought budget here by not having to think about synchronization. Stealing work from other queues is not going to be faster, it's going to be wasted on synchronization and non-locality overhead and would require you to do synchronization everywhere, not a good direction to pursue.
- lpghatguy 7y agoOther parts of the Rust ecosystem have had great luck using work-stealing queues. There's a talk about how Rayon did this[1] and a good article about using it in Stylo[2], a new CSS engine written by Mozilla. [1] https://www.youtube.com/watch?v=gof_OEv71Aw https://www.youtube.com/watch?v=gof_OEv71Aw [2] https://hacks.mozilla.org/2017/08/inside-a-super-fast-css-engine-quantum-css-aka-stylo/ https://hacks.mozilla.org/2017/08/inside-a-super-fast-css-en...
- hinkley 7y agoThe thesis of Practical Parallel Rendering was that any useful task distribution strategy requires a work stealing mechanism because you are leaving serious amounts of responsiveness on the table if you don't. With an infinite queue, the same number of tasks per second happen either way, but the delay until the last task you care about finishes can be pretty substantial.
- carllerche 7y agoYes! Rayon is the perfect use case for the Chase-Lev queue!
- FpUser 7y agoWarning, since I've never written line of Rust code never mind working with Tokio I might be just full of it. If that's the case please forgive me ;) From a short glance my understanding of Tokio is that at high level it is an execution environment that basically implements data exchange protocols based on asynchronous io. Then they say the following: Tokio is built around futures. Futures aren’t a new idea, but the way Tokio uses them is unique. Unlike futures from other languages, Tokio’s futures compile down to a state machine So the question here is why not to expose generic state machine framework (FSM/HSM) which can deal with those protocols but is also very useful for many other tasks as well?
- carllerche 7y ago> So the question here is why not to expose generic state machine framework (FSM/HSM) which can deal with those protocols but is also very useful for many other tasks as well? Short answer is: you can. Tokio is more like "node.js for Rust" or "the Go runtime for Rust". The bit about Tokio & futures is how you use Tokio today. Tasks are defined as futures, and Rust futures are FSMs. So, a protocol can be implemented as a FSM completely independently of Tokio / futures and then used from Tokio. In Tokio's next major release (coming soon), it will work with Rust's async fn feature (which is also about to hit stable). Hope that clarifies things.
- FpUser 7y agoSo, a protocol can be implemented as a FSM completely independently of Tokio / futures and then used from Tokio But that was the point of my question. Since you've already built that FSM framework inside, why not to expose it? Or I guess it might be too specialized for your particular case.
- woah 7y agoMy guess is that they don't want to have to maintain a separate stable public API for what is currently some internal mechanics. Maybe in a few years when the FSM is more or less set in stone, someone will expose it.
- 7y ago
- SloopJon 7y agoFrom a QA perspective, I feel like you buried the lede on this Loom tool. Benchmarks are nice, but confidence is an elusive thing when it comes to non-trivial concurrency. I'll be spending some time on the CDSChecker and dynamic partial-order reduction papers.
- carllerche 7y agoTrue... correctness is very important! I made mention of loom for correctness in the intro at least. The goal for this article was primarily to focus on scheduler design. I'm hoping to get posts dedicated to loom soon. It's been an indispensable tool.
- snowAbstraction 7y agoYes loom seems very important. I would interested to know how it compares with similar tools like nidhugg[1][2] for the C and C++. [1] https://github.com/nidhugg/nidhugg https://github.com/nidhugg/nidhugg [2] https://uu.diva-portal.org/smash/get/diva2:1324003/FULLTEXT01.pdf https://uu.diva-portal.org/smash/get/diva2:1324003/FULLTEXT0...
- carllerche 7y agoI skimmed the paper and it looks similar to loom. Specifically they cite CHESS and Cdschecker as prior art. Both of those are what loom is based on. I guess 2019 is the year of concurrency checking :-)
- jumpingmice 7y agoThe result is pretty impressive. Go's scheduler is not this good. When my Go GRPC servers get up near 100,000 RPS their profiles are totally dominated by `runqsteal` and `findrunnable`.
- typical182 7y agoProbably worth filing an issue, if you haven’t already? Some chance you might be hitting some pathological behavior that could be fixed or tweaked.
- hu3 7y agoWeird. In one of my Go explorations I wrote a naive trade algo backtracker which ingested 100,000 datapoints per second from SQLite on commodity hardware. I'd expect something highly specialized such as GRPC server to perform better.
- tozeur 7y agoHow did Go perform compared to a language like python? I thought the db would be the bottleneck?
- hu3 7y agoPython is awesome. It's fast as long you're mosty calling libraries. Not so fast if Python itself is doing most of the work.
- jumpingmice 7y agoReading 100k rows per second from sqlite sounds WAY easier than serving 100k HTTP/2 queries in the same time.
- hu3 7y agoTrue. But in my case the code also distributes these datapoints to multiple threads, computes technical indicators and simulates tradings while gathering statistics to finetunne parameters. The only optimization I've done was to ditch maps wherever I could. They were dominating flamegraphs. This is why I expected GRPC to perform better. But I agree it depends heavily on what's being done.
- jmakov 7y agoAlso it would be interesting to have a benchmark to compare different approaches to multicore e.g. https://parsec.cs.princeton.edu/overview.htm https://parsec.cs.princeton.edu/overview.htm
- throwaway13000 7y agoDoes anyone know how to print the blog post. Storing it as a pdf only saves first page, not the entire conent.
- liamdiprose 7y agoIf you enable readability mode in Firefox first, the entire article shows up in the PDF.
- r873436 7y agoDoes this new scheduler require a dedicated thread pool for CPU intensive futures, as the current scheduler does? (Thank you for your hard work on Tokio!)
- carllerche 7y agoThanks, I appreciate it! The new scheduler will still require using a special API to run CPU intensive futures: `tokio_executor::blocking::run(|| cpu_intensive())`
- qznc 7y agoEven though I don't use Rust myself, I still admire the Rust community for the awesome technical blog posts they produce all the time.
- carllerche 7y agoThanks! I appreciate it.
- cogman10 7y agoOh man, I really wish ya'll had chosen a name other than "Loom" for your permutation tool. Loom is also the name of a project to bring fibers to the JVM.
- Sawamara 7y agoThank you for posting articles like these. I feel a bit relieved seeing how its not demigods with decades of in-domain experience who create sometimes huge, monumental modules or building blocks of whole languages, but instead: actual human beings who might have been short on options, time or bought into some technical debt in the process of creating something useful.
- ncmncm 7y agoNot to be snarky, but the easiest way to get a 10x speedup is to make the previous one 10x too slow. 10x feels pretty good until you find out it was really 40x too slow. I say this only because getting 100x improvements on naive designs has led me to be suspicious of 10x improvements. The principle is that where 10x was available, more is there. The writeup doesn't mention design choices in Grand Central Dispatch. Is that because we have moved on from GCT, or because it's not known?
- xiphias2 7y agoYou should look at the http server benchmarks before writing this. Hint: tokio based web servers are the fastest.
- Arnavion 7y agoAlso worth noting that the 10x improvement is for tokio's own benchmarks, and even there only in one of the four. The hyper benchmark saw "only" a 34% improvement.
- ncmncm 7y agoGetting downvoted for asking a serious question tells me all I needed to know.
- xiphias2 7y agoI wasn't downviting you, but I'm sure it was the first part of your comment with unchecked facts, not your question that got you downvoted.
- ncmncm 7y agoThere were no unchecked facts in the original post. It is a fact that I have got 100x speedups, and it is my personal experience that 10x speedups rarely come close to exhausting the opportunities. It is a fact that I did not notice any reference in the article to GCD or the techniques that have made it a success.
- lilyball 7y agoTiny comment: In "A better run queue" the second code block has self.tail.store(tail + 1, Release); Should this not instead look like the following? self.tail.store(tail.wrapping_add(1), Release); --- Another comment: > The first load can most likely be done safely with Relaxed ordering, but there were no measurable gains in switching. This code is using an Acquire/Release pair, except it's Acquire/Release on different memory slots, which means there's no actual happens-before edge. This makes the Acquire/Release pair somewhat confusing (which tripped me up too in the first version of this comment). Furthermore, I don't see anything in here that relies on the head load here being an Acquire. This Acquire would synchronize with the Release store on head in the pop operation, except what's being written in the pop is the fact that we don't care about the memory anymore, meaning we don't need to be able to read anything written by the pop (except for the head pointer itself). This suggests to me that the head load/store should be Relaxed (especially because in the load literally all we care about for head is the current pointer value, for the length comparison, as already explained by the article). The tail of course should remain Release on the push, and I assume there's an Acquire there on the work-stealing pop (since you only list the local-thread pop code, which is doing an unsynced load here as an optimization). I don't promise that this is correct but this is my impression after a few minutes of consideration.
- carllerche 7y agoAh thanks! You are correct! Perhaps you should also review the PR? (a tiny bit longer) :)
- lilyball 7y agoI'm not done with the article yet ;) (BTW I just updated my comment, not sure if you saw the first "another comment" addendum but I got it wrong and rewrote it) If I have the time tonight I'll try to look over the PR. No promises though.
- carllerche 7y agoI saw your edit. Your summary of why `Relaxed` matches my reasoning. The code should probably be switched to `Relaxed`.
- gpderetta 7y agoFirst of all, great article! Lots of interesting details and great explaination. A few questions: Did you consider work sharing or work requesting instead of work stealing (the global queue is a form of work sharing of course)? With work requesting you can avoid the required store/load on the pop path. Of course work requesting is not appropriate if the scheduler need to protect against the occasional long running job that doesn't yield to the scheduler in time to service a work request with appropriate frequency, but assuming this is rare enough, an expensive last resort work stealing path could be done via asymmetric synchronization (i.e. sys_membarrier or similar), keeping the pop fast path, well, fast. Is there any way to make (groups of) tasks be constrained to a specific scheduler? This is particularly useful if they all need to access specific resources as there is no need of mutual exclusion; this works well in applications were executors are eterogeneous and have distinct responsibilities. Because of the global queue and the work-stealing behaviour, absolutely no ordering is guaranteed for any task, is that correct? I find surprising that you need to reference count a task explicitly. Having implemented a similar scheduler (albeit in C++), I haven't found the need of refcounting: normally the task is owned by either a scheduler queue or a single wait queue (but obviously never both). In case the task is waiting for any of multiple events, on first wake-up it will unregister itself from all remaining events (tricky but doable); only in the case were is waiting for N events you need an (atomic) count of the events delivered so far (and only if you want to avoid having to wake up to immediately go to sleep waiting for the next event). Also this increment comes for free if you need an expensive synchronization in the wake-up path. That's all so far, I'm sure I'll come up with more questions later. Again great job and congratulations on the performance improvements.
- Matthias247 7y agoTo answer one question: > I find surprising that you need to reference count a task explicitly. This is likely due to how the task and waker system is defined in Rust. A Waker is kind of a handle to the task, whose lifetime is indefinite. Some code can have a handle/Waker to a task which already has finished long ago. One way to make sure the handle is still valid is to reference count it. Since in the Tokio system the Waker/handle and the tasks internal state are actually the same object, this means the combined state gets a reference count.
- kwonkicker 7y agoStop naming your product to a common word, you babies.