10 Million Concurrent Connections – The Kernel is the Problem
highscalability.com
highscalability.com
I had an epiphany one day when I realized that the kernel is nothing but a library with an expensive calling convention.
The only reason we bother calling the kernel at all is because it has privileges that userspace programs don't have, and it uses those privileges to control/mediate access to shared resources.
The downside of the kernel is that there's no way around it. You can't "opt out" of any of its decisions. With any normal library, if had an O(n^2) algorithm somewhere, or wasn't optimized for your use case, or just generally got in the way, you could choose not to link against it. User-space libraries are democratic in this respect; you vote with your linker line. But with the kernel, it's "my way or the highway." The kernel is the only way to the hardware.
Here's an unfortunate example: O_DIRECT is one of those few ways that you can sidestep the kernel. With O_DIRECT you can bypass the kernel's page cache, which there are very good reasons for wanting to do. But Linus's opinion is that "I should have fought back harder": https://lkml.org/lkml/2007/1/10/233 He thinks it's unfortunate that you can sidestep the kernel, because "You need a buffer whatever IO you do, and it might as well be the page cache."
But what if you want better memory accounting, or better isolation between users, or a different data structure, or any number of other tweaks to the page cache implementation? Well thankfully we have O_DIRECT. Otherwise, your only choice would be to try to convince the Linux kernel maintainers to integrate your change, after you've tweaked it so that it's suitable for absolutely everyone else that uses Linux, and given it an interface that Linux is willing to support forever. Good luck with that.
The kernel has always been the problem. User-space is where it's at.
http://en.wikipedia.org/wiki/Exokernel
http://en.wikipedia.org/wiki/Microkernel
http://en.wikipedia.org/wiki/Tanenbaum%E2%80%93Torvalds_deba...
There are good reasons why they have not caught on, performance being the most salient one.
"The kernel is just a library" isn't exactly the same sentiment as "the kernel should be as small as possible" -- I believed the latter before I fully understood the former. "The kernel is just a library" means that all of the experience we have designing and factoring userspace APIs carries over into kernel design. Furthermore it means that the kernel is a strictly less flexible library than userspace libraries, with a strictly more expensive calling convention, and that its only advantage is that it can protect and mediate access to hardware.
> There are good reasons why they have not caught on, performance being the most salient one.
Most of the received wisdom about microkernels is based on outdated designs like Mach, and not modern designs like L4. L4 is significantly more efficient than Mach.
L4 was also one of a kind endeavor extremely optimized for the specific architecture. I can't really imagine that something like this could be achievable for a commercial OS.
It has another advantage, which is that it acts as a trusted third party that can allow two mutually untrusting users/program to share a software-implemented resource - for example, a disk cache or a TCP stack.
Security and isolation might be provided by other means like virtualization.
Not saying it's a better way, it's just an alternative to writing time critical drivers in user-space as TFA proposes. I suspect that if you have to handle 10 million connections, you don't really need a full featured multiuser desktop system and you can manage this component to have specific deployment requirements.
Gain: no user-kernel process switches; no kernel call to poll completion; no data copying between processes; no interrupt transition. This was the idea behind InfiniBand but virtual hardware is older than that.
AFAIK that's may be implemented on existing Linux system using Intel DPDK or PF_RING (routing packets directly from NIC to mmap'ed memory in userspace), "maxcpus=" Linux boot directive (to run Linux kernel on one or two cores only), and "pthread_setaffinity_np()" call in user process (to run the process on other cores which will never be imterrupted by Linux kernel).
Thinking in those terms, the benefits of the "privileged lib" are:
- has a lot of functionality (support for hardware X, Y etc, good implementations of important, difficult algorithms)
- interoperability and network effects, if you use this library you can conveniently interoperate with other applications using it.
You can also get around the "strictly more expensive calling convention" by writing your code to run as a loadable kernel module. Obviously that's inconvenient, but that's kind of the point of this - trading convenience for performance.
For example, think of LLVM. GCC has a lot of functionality, and implements a lot of important, difficult algorithms. But because GCC is in userspace, LLVM/Clang have been able to get better and better until they can realistically challenge GCC in this space. People are starting to use LLVM more and more; it offers really compelling new tools like ASAN (http://clang.llvm.org/docs/AddressSanitizer.html), Clang Static Analyzer (http://clang-analyzer.llvm.org/), and LLDB. LLVM is also offering an embeddable and modular architecture, which GCC has opposed on philosophical grounds for years.
Because this is in user-space, LLVM was able to form and grow alongside GCC. People didn't have to make a big switch just to try out LLVM; it's not intrusive like it would be to switch from Linux to FreeBSD or anything like that. That's why I think the network effects of user-space are better. In the kernel it's "get merged or die." In user-space, similar projects can compete and people can vote with their linker lines.
There are tons of examples of this. In the last 10 years we've seen a lot of displacement in userspace, where next-gen technologies have made a lot of inroads against the incumbents:
- Apache has been challenged by nginx
- Perl has been challenged by Python/Ruby
- screen has been challenged by tmux
We'll never get to find out what might have happened if Con could have realistically offered his work as an alternative. The scheduler is in the kernel, which means that Linus picks winners and losers. In userspace, no one has that power.
The vast majority of people don't run a Linus kernel. They run a distro kernel. Distros can (and do) ship multiple kernels with different sets of patches and options. They have a default, but they also have a default web server and C compiler.
The kernel is abused by all kinds of different workloads. Distros choosing to offer kernels with more "speculative" patches will have to support them. The kernel is a risk-averse environment. I think that's the reason, not fiat by Linus.
Also note, a good counterexample to your main point is the android kernel. Linus-kernel:Android-kernel is quite close to gcc:llvm.
Replacing big chunk of functionality takes a lot of resources, so it helps to be apple (LLVM) or google (android kernel).
Also, don't underestimate kernel modules either. If you want to, say, expose page table information that "linux doesn't let you", you can write a module to do so.
[edit - removed Con Kolivas related part of response. Don't want to drag up old flamewar.]
In Snabb Switch (http://snabb.co/snabbswitch/) we take large blocks of RAM (HugeTLB) and whole PCI device access (mmap via sysfs) from Linux and then do everything else ourselves in userspace. The kernel is more like a BIOS in that sense: it gets you up and running and takes care of the details you really don't care about.
EDIT: Extremely early draft ahem detailed design document: http://snabb.co/misc/snabbswitch-07may2013.pdf
Well, you can sidestep most of it. For example, re the c10k/c10m problem, you can the transport protocol impl to userspace. See example here how they did it with SCTP: http://www.cs.ubc.ca/labs/dsg/mpi-sctpuserspace_ICCCN2012.pd... - you could do the same with TCP if you don't care about having a TCP-enabled kernel.
The other example of course is all the protocols built on top of UDP.
This still has the NIC driver shoveling at least the raw IP packets via the kernel driver, but you could sidestep that too by using the hypervisor interface to route the NIC pci space and interrupts to your program (like Xen uses).
Oh, I don't know, you could always write your own kernel module. Considering I used to work on a kernel module that hooked the IRQ calls to implement hard RT, I'm not convinced that the kernel is that constraining. If you really feel constrained by the kernel, you could do without and go bare metal. Even if you don't want to do that, you've still got tons of other possibilities (the BSDs, any of the OSS microkernels, etc, etc). At least you've got those options with FLOSS kernels; I'd like to see how far you can get with changes to a closed source kernel, or worse, some hardware that's locked down to "keep you safe from malicious code".
As for the approval process of Linux patches, there's good reason for that, and other FLOSS kernels are just as (if not more) picky. The truth is, the Linux kernel has probably had more use cases thrown at it than any other software, ever. It's not perfect, nor heavily optimized towards any particular configuration; but it's highly configurable, and with a bit of tweaking (which would take less time and be less error prone than going bare metal), you can almost always get an acceptable solution to your problem.
Some cases where routing around the kernel are of genuine interest and necessary; most of the time, though, I far too often hear of programmers blaming others for performance problems that they haven't run a profiler on (if they've even heard of profiling).
And a difficult debugging environment.
Incidentally, game programmers have been spreading the gospel on this issue for several years now. See for more:
http://macton.smugmug.com/gallery/8936708_T6zQX#!i=593426709...
http://research.scee.net/files/presentations/gcapaustralia09...
http://www.altdevblogaday.com/2011/11/07/an-example-in-data-...
For example, suggestion #33, to shift by a constant amount instead of a variable amount. You see, it only looks like you're shifting by a variable amount. This is one of those things that compilers have been optimizing for years and are very good at: strength reduction wrt variables that depend on the loop variable.
You'll also see game programmers do things like "x >> 4" instead of "x/16", because "x >> 4" is faster. It is faster in assembly language, but your compiler already knows that and you are just making the code harder to read every time you do a micro-optimization.
Game programmers spread the gospel on lots of premature optimization nonsense, in my opinion, and are mostly inexperienced when it comes to writing mantainable code. It's a kind of hazard of the industry. Performance problems means cutting beloved features, and rather than doing any maintenance you just start a new game from scratch. (Not universally, of course. There are a few programmers professionally working on engines.)
Mostly. Just like any other average guys in any industry.
But game industry is continuously bringing back many interesting technologies, especially performance-related. Like LuaJIT, rapidly becoming mainstream and widely used, GPU-assisted calculation, used even in PostgreSQL - https://wiki.postgresql.org/wiki/PGStrom - and so much more.
I don't think it's fair to generalize game programmers for premature optimization nonsense. Game development certainly has much stricter requirements on performance than say, Joe's Ruby on Rails website, and so I would be much more inclined to trust them for optimization tips. That being said though, yes, a lot of them have no idea what they are talking about.
I have been on both sides of the fence. I have worked with people who attempt to optimize every single instruction, and with people who gladly misinterpret "premature optimization is the root of all evil." Both of them are obviously toxic in their own ways.
What are the other bogus suggestions? The overall thrust of the slides seems to me valid: know what's expensive (branches, memory access, mini-pitfalls like the micrododed thing), pick a strategy that avoids all of that, and don't throw away performance. Performance always ends up being an issue; you don't have to carefully preserve every last cycle, but that's no excuse for just pissing away cycles doing pointless stuff.
Not explicitly stated, but apparent from comparing the suggested approach to the original one, is that you can't always just leave this stuff to the last minute, when you've had the profiler tell you what's a bottleneck and what isn't. The requisite changes might have far-reaching consequences, and so it's worth giving a bit of thought to performance matters when you start and things are a bit more in flux.
A bit of domain knowledge also won't hurt. I bet if this function were ten times worse, but called "PostDeserializeFromDVD", it wouldn't attract very much attention.
Yes there is - maintainable code, programmer time and effort. What are you worried about, a large power bill due to your cpu doing what is supposed to be doing?
On an unrelated note this kind of attitude is the first thing I test for during a programmer interview, and is my strongest case for eliminating potential candidates. I made the mistake once of letting one through - his first task was a relatively straightforward modification to a large C program. A week later I was a bit worried he hadn't reported back done, so I went to check up on him and it turns out he was busy changing every line of code to adjust formatting and variable names, not to mention these kinds of pointless micro-optimizations. And he hadn't even checked in once, he was saving the checkin itself for another multiple day effort. Sigh. I tried using the "premature optimization is the root of all evil" line on him to get my point across (and see if he had heard of it), and it was when I saw his eyes flare up in anger I knew he had to go. Sad really because he was otherwise quite bright.
Now I basically put C++/game programmer applications in a "special pile" to be considered as a last resort. I just dont need this kind of arrogance and cowbow mentality wrecking the place. Its like sending a bull into a china shop.
So, armed with a few simple rules of thumb about what is particularly expensive (let's say: memory accesses, branching, indirect jumps, square root/trig/pow/etc., integer division), and a bit of experience about which parts tend to cause problems that can be rather intrusive to fix (and object culling is one of these), one might reasonably put in a bit of forethought and try to structure things in a way that means they're relatively efficient from the start. Better that than just producing something that's likely to be a bottleneck, but written in a way that means it is never going to be efficient, whatever you do to it, without a ground-up rewrite. And that's the sort of approach the slide deck appears to be advocating.
Seems uncontroversial, to my mind. Some (and I'd agree) might even just call this planning ahead. Seems that when you plan ahead by drawing up diagrams of classes and objects, because you've been burned by having people just diving in and coming up with a big ball of spaghetti, that's good planning ahead. But when you plan ahead by trying to ensure that the code executes in an efficient manner, because you've been burned by having people come up with slothful code that wastes half its execution time and requires redoing because of that, that's premature optimisation, and a massive waste of time.
As with any time you make plans for the future, sometimes you get it wrong. Ars longa vita brevis, and all that.
Video games are real-time. There's a hard limit on the number of cycles you can make use of per frame.
11 cycles spent mispredicting a branch is 11 cycles you can't use for better-looking IK or smarter pathfinding.
Does your compiler not generate assembly? Does your platform not have objdump or a similar tool you can use as a disassembler? I suppose asking you to profile is too much, but you can at least look.
That's not the issue here. It doesn't matter if the variable shift has to get its results by carrier pigeon from a monk in Tennessee, because the variable shift is eliminated by the compiler. When the programmer is manually doing work that has already been automated, your process is inefficient.
I also tried gcc (OS X, x64) and llvm (OS X, x64/ARM) and they didn't do the transformation either. (I'm not sure I would expect this for ARM anyway, but for x64 the variable shift code looked a bit more involved than I was expecting. Perhaps a transformation into a fixed-width shift would be beneficial in that case as well.)
Test code:
float f(const float *f,unsigned mask){
unsigned i;
float t=0.f;
for(i=0;i<32;++i){
if(mask&(1<<i))
t+=f[i];
}
return t;
}
float f2(const float *f,unsigned mask){
unsigned i,m;
float t=0.f;
for(i=0,m=1;i<32;++i,m<<=1){
if(mask&m)
t+=f[i];
}
return t;
}
Still, I would stand by my maxim even if the data in this case were against me. It's the winning strategy. Why rely on the compiler's ability to second-guess your intentions, when you could just tell it what you want, straight up?
While, I'm normally of the school of thought to let the compiler do the optimization. Modern compilers often miss what would seem like rather trivial optimizations, And often due to assumptions that the language spec won't allow that the programmer otherwise can make.
I'm honestly surprised that the variable shift didn't get fixed. This strength reduction will happen if you use a multiply instead of a shift: the multiply will get reduced to an addition. I had assumed that the same would hold for variable and fixed width shifts.
I would file this as a bug against the compilers in question. I don't think it would take very long to fix.
int main(int argc,char *argv[])
{
int x = strtol(argv[1],NULL,10);
printf("result is %d\n",x/16);
return 0;
}
I think it really depends upon the compiler.
int div_by_2(int x) {return x/2;}
div_by_2:
movl %edi, %eax
shrl $31, %eax
addl %edi, %eax
sarl %eax
ret
unsigned int div_by_2(unsigned int x) {return x/2;}
div_by_2:
movl %edi, %eax
shrl %eax
ret
movl %eax, %esi
sarl $31, %esi ; ESI = FFFFFFFF (-) / 00000000 (+)
shrl $28, %esi ; ESI = 0000000F (-) / 00000000 (+)
addl %eax, %esi ; offset to cancel invalid values
sarl $4, %esi ; shift
Then it adds this to the original value. This is the cunning part - well I think so anyway. It ensures that for the values where x>>4 would give the wrong value (i.e., -15<=x<0), x is made positive and smaller than 16, so that x>>4 gives the correct value of zero. For all other values, the bottom 4 bits don't affect the result of the division, so it's fine to offset them as well.
(Don't think I've ever seen VC++ generate anything like this, but I'd pretty much always have an explicit shift rather than a divide by 16 so maybe it does and I'd just never noticed. The choice of 16 usually comes from having some 4-bit field somewhere, and when dealing with bitfields you're best off using bitwise instructions.)
This is one of those things that compilers have been optimizing for years and are very good at: strength reduction wrt variables that depend on the loop variable.
Many compilers are good at it. In many instances. But if you do multi-platform development, with entirely different compilers for each platform, doing manual strength reduction is a good investment of your time if performance really matters.
and rather than doing any maintenance you just start a new game from scratch
Thankfully, that model is fading. It was a result of rapidly changing architectures, so that often at the beginning of the next console cycle, you had to rewrite anyways - the hardware was so different that what was previously fast suddenly was a disaster.
Given the fact that hardware is moving closer and closer to being bog-standard, and that code bases are large enough that a rewrite is actually insanity, not a couple of bored weekends, this mentality is fading out.
Slowly, granted, but there's hope :)
The Linux kernel has come a long way in the last few years with improvements to SMP scaling of sockets, zero copy, and large numbers of file handles; make use of it! The level of technical skill being applied to fix kernel problems is probably more expensive than you can afford.
In general doing this "properly" is an exercise in icky compromise.
When 1U commodity x86 server built on C602 Intel chipset can be packed with 768 GB RAM..
If that's the case, then yeah, 10 million connections would require a 14.3 terabytes/sec connection, which doesn't exist for regular PCs, as far as I know.
There are many applications when most of your connections are sitting idly and checking something like memcache for status updates once a second.
sorry to say I don't buy the "Unix was designed as a phone switch control plane" nonsense at all. Here is Dennis Ritchie:
Unix was designed for people, not for Bell System Switches: http://cm.bell-labs.com/cm/cs/who/dmr/hist.html
Why don't you focus on simplifying the network stack instead?
The stack is complicated and slow for a reason: it takes care of many things. I will believe that you can do better when you provide the same amount of functionality (QoS, firewall, probing, tracing). If you say that you can do without all these additional features, why don't you go and optimize the stack so that the most basic code path is smaller and faster?
To turn your own question around: Why bother trying to optimize a stack that contains a lot of stuff you don't strictly need? The talk doesn't deal with general-purpose servers that perform multiple roles; it says "if you have a singular role, here is how you hyper-optimize to support that role at a huge scale."
You only have one specialized need at the very beginning. Then you start seeing the need for "just another little feature". And soon you will start replicating big parts of the network stack. Call it Greenspun's tenth rule for the network, if you want.
Also, most of the time, what you "just need" happens to be also the common need of many other users out there. Joining forces to fix a single code path is a much better investment than redoing things in userland for the sake of it.
If you were to ask someone to build a vehicle that can go really fast you might end up with a car. But ideally you'd really want a rocket.
I'm sure that there are systems out there that serve web pages with only bare metal. Where the "kernel" exists only as an architectural stub. Why shouldn't the NIC serve web pages directly?
So my approach is a heap-cache usually. Calculate the log2 size, choose a heap bucket, if its empty THEN go to the heap. Never frees so never garbage collects (neither does single-large-allocation so no loss), just relinks freed blocks on the cache bucket by size for simple reuse. It soon comes to a working-set and never takes longer than a critical-section and link/unlink, at least once it settles down.
Interesting to see this thinking applied to something slightly different, thanks for the link!
http://www.cluecon.com/presentation/building-conferenceivr-p...
I would love to see actual working code for IP/SIP/RTP in node.js using packet sockets, if anybody knows of an open source project.
That was going to be the basis for a project to handle large numbers of concurrent connections. Still on the drawing board though.
Secondly, the article surmises that the kernel is the problem, which seems right. Then it makes a leap to state that the way to do this is to write your own driver.
Who said? I certainly don't agree. You are still running a multi-user kernel, but you've now sacrificed its stability by running a parallel network stack. Linux wasn't written to work in that way and it's hard to know what you're getting into when you subvert your OS in that way. This article would be much better if it talked about other options out there. For example..
Why not take out the middle-man entirely with something like OpenMirage (http://www.openmirage.org/)? Get rid of the lowest-common-denominator performance you get using a general-purpose OS and make your application the OS. Link in whatever OS-like services (network, filesystem, etc) you may need. Talk to the hardware directly without going through a middle-man and without ugly hacks.
But having written systems doing 10M TCP connections at 10Gbps, I strongly believe that you want to relegate the kernel into the role of a management system. Having the system split across the kernel and user-space will lead to unacceptable performance, pretty much no matter where you split things. And having the full application in the kernel would be a nightmare for development, debugging, and deployment. (And I sure as hell am not going to choose a pre-alpha research project over Linux as the base of telecoms systems.)
Presentation - http://www.slideshare.net/shemminger/uio-final
I have to agree. It didn't really turn out as well as I wanted. The talk is really good, but I could never make this read smoothly.
Fortunately I think the content is excellent and that will hopefully save the day.
My take is along the lines of the earlier embedded systems comment. This is the sort of thing you would have done in a real-time OS snagging packets directly in an ISR and queuing them to a task for later processing. The processor and memory suggestions are just common practice in that arena.
But that kind of sucks for numerous reasons. It's great having a widely supported OS that you can leverage while replacing the bits you need to meet your goals. That's pretty genius in my book.
Props for stepping forward and saying this :-)
I think it has to do with that you're trying to capture the content of a talk largely by presenting the bullet points from that talk's slide deck, but in doing so miss a lot of context that came from the presentation.
Your summary at the bottom is great -- I think it should be the whole article. This would offer viewers a snapshot of what they can expect out of the video so that they don't miss anything (for example, a very common takeaway I'm seeing from this and from people I show it to is that this is "just" a network stack hack -- no mention of his proposal for multi-core optimization, etc).
Maybe Mirage will pan out, but for right now it's in the pre-alpha stage. We've heard about the glories of microkernals before (GNU Hurd, anyone?).
"Debug normally" isn't the case with BigTable or any other MapReduce implementation, is it? Do we think Google and big bunch of others made a mistake with it? Obviously not.
[1] This paper seems to support that: http://int3.de/res/GfsMapReduce/GfsMapReducePaper.pdf
That seems like dubious logic.
Also unlike Google's bet on commodity hardware, I don't see the millions of dollars of savings to be had if the micro-kernel idea works out. At best you'll get an incremental performance benefit and easier debugging. It'd be different if there were no open source OSes and so rolling your own was the only alternative to paying millions in licensing fees.
[1] http://www.netbsd.org/docs/rump/
[2] http://erratasec.blogspot.ru/2013/02/custom-stack-it-goes-to...