RethinkDB internals: handling stack overflow on custom stacks
rethinkdb.com
rethinkdb.com
On my computer, the callstack of a new process is around 10MB.
First, this limit isn't set by his computer. His computer might affect the limit; but the value is also likely to be affected by his choice of operating systems, his login.conf settings, whether he is root, and possibly environment variables.
Second, processes don't have stacks. Threads have stacks. And often the first thread gets more room than later threads.
Third, the stack starts out small -- like, a few hundred bytes or so, depending on the amount of bloat in his platform's crt1.o (or equivalent). It can grow, of course; but the size of something is not equivalent to its maximum permitted size -- you would never say "a newly created file is 2^64 bytes" just because that's the maximum possible size.
I'd suggest replacing the first sentence with
On my computer / OS / login environment, the default maximum permitted size of
the primary thread's stack in a new process is around 10 MB.
First, this limit isn't set by his computer.
Obviously the size of the stack depends on a number of variables (including the hardware architecture, the kernel, how the kernel was compiled, various settings, etc.), but on Dan's configuration it's roughly 10MB, as verified by the program at the end of the blog post. Here is a program that confirms it by computing the number in a different way:
#include <pthread.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
size_t stacksize;
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_getstacksize (&attr, &stacksize);
printf("Default stack size = %lu\n", stacksize);
}
Second, processes don't have stacks. Threads have stacks.
Certainly, but this is a question of terminology. On Linux threads are special-case processes (with address-space sharing and a few other changes). For example, when calling strace you have to pass -f to see syscalls from all the threads instead of just the main one.
Third, the stack starts out small -- like, a few hundred bytes or so.
Again, not according to the manual (see above).
You guys have heard of userland threads, right?
When we get the chance we'll post benchmarks between GNU Pth, NPTL, and our coroutine implementation. I can assure you that NPTL is much slower than what we're doing. GNU Pth is a real contender, but there are some issues associated with using it (mainly the fact that we need to be able to move coroutines between native kernel threads, and it's not clear how well GNU Pth can handle that). The coroutines implementation won't be making it into the first release - ultimately we'll test all three alternatives and pick the best one, but it will take some time before that happens.
It might be that, yes. But as a philosophy professor of my acquaintance likes to remark, "clear thinking requires clear language" (the irony of this phrase coming from a philosopher's mouth seems to be lost on him). Using unclear language both misleads the audience and makes it unclear whether the speaker understands what he's talking about.
(I find the same is true of code -- the clarity of some code seems very highly correlated with how well its author understands the problem space in question.)
Between us we're using three different definitions of "stack size" -- the size of the actual stack, the amount of RAM allocated, and the amount of VM space allocated; needless to say, I think the first definition makes the most sense. ;-)
When we get the chance we'll post benchmarks between GNU Pth, NPTL, and our coroutine implementation.
I recommend trying other operating systems too. Linux is famously bad at threading, and only survives in benchmarks because most applications which run on Linux are equally bad in how they use threads. What you really want (and seem to be implementing) is an M:N threading system, which is considerably more performant than either 1:1 or M:1.
I think you need to balance that with taking some shortcuts, or you'll never get to the essence (or at least your readers won't).
Slava, you're better than that. WHY is a smaller default stack size more sensible? If this is all you need, and you can change it manually, do that!
Because if you have a large number of threads on an architecture with a small address space, you take away memory space from the buffer cache which can have catastrophic effects on performance.
If this is all you need, and you can change it manually, do that!
This needs to be understood in the context of the previous posts. The issue with NPTL is significantly lower performance on large number of threads due to context switching. Dan implemented a solution that uses coroutines to address that problem. This post deals with the over-provisioning issue described above, and it starts out by describing the default configuration for pthreads. Adjusting this to a smaller number on the NPTL implementation isn't enough, we needed to adjust it for the coroutines implementation.
Say again?
Address space exhaustion is a problem, sure, but it has nothing to do with the buffer cache. The kernel's address space is completely separate from any particular process' address space.
For various reasons we don't use the kernel's cache, we have our own cache implementation that's in the same address space as the rest of the process.
You have my sincere and profound sympathies.
Probably, readability. Daniel probably assumed that his readers either a) wouldn't get why those distinctions need to be made, and would therefore be put off by such a bludgeon of an opener or b) would just read on already to see these details explained.
First, the login environment is really tangential to the discussion here. He's trying to talk about the fact that their threads' stacks were taking up too much reserved space for memory protection and how they slimmed those down. Precisely how big they are and why that is doesn't really matter, all that's important is that they're a couple orders of magnitude larger than they need to be (whether this is a real issue I leave for later ;-).
Second, if you read on, you see that the whole article is about threads and it soon doesn't matter that he said "process" in the first sentence. Maybe just replacing it with "thread" would be good, but it's really not a big enough deal to get bent out of shape over.
I really don't know about your third point, I've never run in to this particular issue and I don't know if spawning tons of threads actually wastes physical memory for this protection (doubt it), destroys the page table (this would be my guess), or something else (somewhere, I can imagine the sound of something thrashing). [EDIT: on re-reading, it appears the concern was virtual memory, and the page table is definitely where I heard that thrashing sound earlier. I now clearly see where they had performance problems with 10MB stacks, even on a 64-bit architecture] It sounds like there actually was a bottleneck, and I trust that these guys didn't just imagine it (though they could've explained the problem a bit better, I think). I agree with you that I wasn't convinced by "threads are too expensive" but I think I trust this is a fault of omission, not of research.
For my part, I can't get my head around your rewrite. Certainly those details are important, but they don't belong in such high density in the first sentence of a blog post, even a highly technical one. It's a matter of writing style, and I think Daniel made the right choice.
Regarding userland threads, I don't think these guys are developing (or probably testing at this point, though I'd be glad to hear if they were) on freebsd. That's the only place I know of with something actually called "userland threads"; there are several implementations on linux by different names that accomplish the same goal, but I don't recall seeing any with that name. Which threading scheme in particular were you referring to?
This is a really good list: http://www.gnu.org/software/pth/related.html Many of these projects are dead or unmaintained, but there are a few worth paying attention to (notably Gnu Pth itself). In any case, the problem isn't too difficult - it took Dan a month to do it, and that includes patching various open source components to fix performance issues and adapting our existing codebase to use proper programming style (this took a significant chunk of the time).
I said "userland threads" to distinguish it from kernel threads, which are (as they noticed) rather expensive.
What RethinkDB really want, and seem to be headed towards, is a proper M:N threading model: Launch one kernel thread per CPU (N), then spread M userland threads between those.
It'd be nice if some pthread implementation gave us what we need, but I don't think they do. They probably are too heavy an abstraction, even if implemented in user space, providing too strong guarantees for context switching and scheduling. For example, we're never going to set individual signal handlers on different coroutines, but pthreads guarantee this capability. So even user-level pthreads which don't support preemption will require a system call on context switches, just as ucontext.h's swapcontext does for similar reasons. But as Slava points out, the performance penalty is something that we need to verify in the future with benchmarks.
What would be really nice is if the OS, or at least a standard application framework usable from C++, supported this. But it doesn't, so we build our own.
Yep, I think so too. I don't know of anything that does that on linux, sadly.
Man, I gotta dust off that freebsd partition again.
Just spin up a FreeBSD instance in EC2. :-)
(And while you have it running, please run your favourite stress tests and try to find bugs. I think it's starting to get decently stable now, but it needs lots more testing.)
I agree that they are doing a bit of wheel-reinventing. I have used a couple existing coroutine libraries (libcoro from the Coro perl module, and libtask), and they both do a good job of conserving memory nicely. It's easy to write 10 lines of "threaded" Perl that can manage 30,000 slow HTTP connections with minimal overhead (a few k per fd).
I am not sure why they are writing their own library, but I do know that I have never used existing libraries for CPU-intensive purposes, only for IO-intensive purposes. I don't think they are doing a ton of socket IO, so perhaps that is where their need to reinvent comes from.
We aren't, our code is based on a slightly modified version of libcoroutine. We've just added a few bells and whistles here and there to do a little bit more than what the library offers out of the box.
I don't think they are doing a ton of socket IO, so perhaps that is where their need to reinvent comes from.
Our real-world load can easily change between between disk bound, network bound, and CPU bound, so we need to support both IO bound and CPU bound workloads really well.
Secondly, when meaning to be precise when talking about memory usage, you need to specify what kind of memory: paged vs non-paged, reserved vs committed, shared vs non-shared (private), backed by a file vs backed by swap, in Windows-land whether the memory is part of the working set or not, etc. It's not clear to me what you mean by the memory usage of stacks, but when Daniel talks about it I know what he means: with memory as a bottleneck in the context of thread stacks, it's clear that the relevant metric is reserved space - i.e. virtual address space. This is what kills you quite early on in 32-bit processes in particular.