RethinkDB internals: handling stack overflow on custom stacks(rethinkdb.com)
rethinkdb.com
RethinkDB internals: handling stack overflow on custom stacks
http://www.rethinkdb.com/blog/2010/12/handling-stack-overflow-on-custom-stacks/
2 comments
Hi Colin! I don't necessarily disagree with you, but I feel like your arguments address semantics/linguistics and not the actual issue.
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:
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.
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.
I don't necessarily disagree with you, but I feel like your arguments address semantics/linguistics and not the actual issue.
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.
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.
But as a philosophy professor of my acquaintance likes to remark, "clear thinking requires clear language"
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).
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).
> The point wasn't that you couldn't change this value, it's that for our purposes (lots of green threads, shallow stacks) a much smaller default stack size is more sensible.
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!
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!
WHY is a smaller default stack size more sensible?
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.
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.
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.
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.
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.
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.
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.
Oh dear god.
You have my sincere and profound sympathies.
You have my sincere and profound sympathies.
It's pretty unusual for databases to delegate something as vital to performance as caching to the OS.
Sure, a database needs to cache. But it doesn't automatically need to cache at that level -- usually they can get away with caching data rather than pages.
If you have your own cache and you don't use direct I/O i.e., they go through the OS page cache, don't have you have the issue of the OS page cache and the database "fighting" each other?
> I can't imagine what sort of thinking produced this sentence.
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?
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?
Regarding userland threads [...] there are several implementations on linux by different names that accomplish the same goal
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).
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).
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?
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.
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.
Yep, that's basically what we do. User-level threads are called 'coroutines' and they're scheduled cooperatively, so they don't incur the overhead of user-level preemption. Cooperative scheduling is fine for us because we can ensure that a single coroutine won't hog the CPU or issue blocking system calls.
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.
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.
Oh, I thought you were talking about one particular implementation, my mistake.
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.
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.
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.)
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.)
Awfully pedantic, don't you think? This is a casual blog post, not an IEEE standard. Everyone that wasn't a computer program knew what he meant; "I start a process, the stack looks like it's about 10MB". And the size wasn't even the issue he was discussing, but rather what happens when you use all the space. Comment in passing; relax a little.
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.
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.
I am not sure why they are writing their own library
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.
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.
I think you're being way too harsh on the computer thing; I read "my computer" as "my box", i.e. "my specific configuration of hardware and software".
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.
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.
Use 64-bit and all problems with 10 MB stacks go away. 64 KB is surprisingly small when you call a library function or if the OS uses the userspace stack for OS calls.
This is something which will be good to look into in the future. It may be that, in certain system configurations, that's fine. But if there are 10,000 coroutines each with 10 MB stacks, and memory overcommitting is turned off or configured to be relatively conservative (as some system administrators like to do), you'll need to reserve 100GB of physical memory + swap just for coroutine stacks. This may be problematic, but it may not. In the system I've implemented, the stack size is a parameter which can be varied when the database is launched, so this is something which we can easily benchmark in the future.
I can't imagine what sort of thinking produced this sentence.
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
(Random side note: You guys have heard of userland threads, right? You seem to be doing an awful lot of wheel-reinventing here -- not necessarily a bad thing, of course, but I didn't find your "threads are too expensive" line particularly convincing.)