5 ms·

RethinkDB internals: handling stack overflow on custom stacks

23 points by coffeemug 16y ago

cperciva 16y ago
I usually enjoy reading RethinkDB blog posts -- it's unusual for a company with such smart people to write about technical issues they come across -- but I got as far as the first sentence before being disappointed this time. On my computer, the callstack of a new process is around 10MB. 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 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. (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.)
- coffeemug 16y ago
  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: #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); } On our configuration (which is roughly what most customers are expected to run) the output is 8388608, or 8MB. According to the manual, pthread_attr_getstacksize returns the minimum size (in bytes) that will be allocated for threads created using the thread attributes object attr. Naturally the size can be changed manually (in the code or with ulimit), but it is the default minimum for newly created threads according to the manual. 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. 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.
  - cperciva 16y ago
    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.
    - coffeemug 16y ago
      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).
  - leif 16y ago
    > 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!
    - coffeemug 16y ago
      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.
- leif 16y ago
  > 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?
  - coffeemug 16y ago
    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 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).
- jrockway 16y ago
  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.
  - coffeemug 16y ago
    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.
- barrkel 16y ago
  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.
silvestrov 16y ago
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.
- littledanehren 16y ago
  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.

23 points by coffeemug 16y ago

I usually enjoy reading RethinkDB blog posts -- it's unusual for a company with such smart people to write about technical issues they come across -- but I got as far as the first sentence before being disappointed this time. On my computer, the callstack of a new process is around 10MB. 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 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. (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.)

coffeemug 16y ago
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: #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); } On our configuration (which is roughly what most customers are expected to run) the output is 8388608, or 8MB. According to the manual, pthread_attr_getstacksize returns the minimum size (in bytes) that will be allocated for threads created using the thread attributes object attr. Naturally the size can be changed manually (in the code or with ulimit), but it is the default minimum for newly created threads according to the manual. 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. 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.
- cperciva 16y ago
  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.
  - coffeemug 16y ago
    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).
- leif 16y ago
  > 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!
  - coffeemug 16y ago
    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.
leif 16y ago
> 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?
- coffeemug 16y ago
  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 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).
jrockway 16y ago
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.
- coffeemug 16y ago
  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.
barrkel 16y ago
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.

silvestrov 16y ago

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.

littledanehren 16y ago
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.