The Secret to 10 Million Concurrent Connections: the Kernel Is the Problem, Not the Solution

Summary: The C10K problem taught us that at 10,000 concurrent connections, the right approach can let a laptop outperform a 16-core server. For C10K we either worked around it or overcame it. But as concurrency keeps climbing in this post-10K era, have you thought about how to overcome C10M?

Now that we’ve solved 10,000 concurrent connections, how do we raise the bar to support tens of millions? You might say it’s impossible. No — systems today already support tens of millions of concurrent connections, in ways you may not be familiar with, and which are fairly radical.

To understand how, we first need to look at Robert Graham, CEO of Errata Security, and his “nonsense” at Shmoocon 2013 — C10M Defending The Internet At Scale. Robert explained the problem cleverly in a way I’d never heard before. He started with a bit of Unix history: Unix was not designed as a general server operating system, but as the control system for the telephone network. Since it was an actual telephone network carrying data, there was a clear boundary between the control plane and the data plane. The problem is that we now shouldn’t be using a Unix server as part of the data plane at all. Designing a server kernel that runs one application is simply not the same as designing a multi-user server kernel.

Which is what he means by — the key insight is that the kernel is not the solution; the kernel is the problem.

That means:

• Don’t let the kernel do all the heavy lifting. Move packet handling, memory management, and processor scheduling out of the kernel and into the application, where they can be done efficiently. Let Linux handle only the control plane; hand the data plane entirely to the application.

The end goal is a system that can handle tens of millions of concurrent connections, processing packets in 200 clock cycles and application logic in 140,000 clock cycles. Since a single main-memory access costs 300 clock cycles, minimizing code and cache misses is critical.

A data-plane-oriented system can handle 10 million packets per second; a control-plane-oriented system can only handle 1 million packets per second.

That may sound extreme. Remember the old saying: scalability is specialization. To do something well, you can’t outsource the performance problem to the operating system — you have to do it yourself.

Now let’s learn how Robert builds a system that can handle tens of millions of concurrent connections.

The C10K Problem — The Last Decade

Ten years ago, engineers dealing with C10K scalability tried hard to avoid servers handling more than 10,000 concurrent connections. The problem has been solved by improving operating system kernels and by replacing threaded servers (Apache) with event-driven servers (Nginx and Node). It took people ten years to move from Apache to scalable servers, and adoption has grown faster in recent years.

The Apache Problem

• Apache’s problem is that performance degrades as the number of connections grows.

• Key point: performance and scalability are not the same thing. When people talk about scale, they’re usually talking about performance — but scale and performance are different, as Apache shows.

• Short-lived connections lasting a few seconds, such as fast transactions: at 1,000 transactions per second, there are only about 1,000 concurrent connections to the server.

• Stretch transactions to 10 seconds and, to sustain 1,000 transactions per second, you must open 10,000 concurrent connections. In that case: even ignoring DoS attacks, Apache’s performance falls off a cliff, and heavy download traffic can crash it outright.

• What do you do if connections per second go from 5,000 to 10,000? Say you upgrade the hardware and double the processor speed. What happens? You get twice the performance, but not twice the scale. You might reach 6,000 connections per second. Keep raising the speed and things don’t improve — even at 16x the performance it still can’t handle 10,000 concurrent connections. So performance and scalability are not the same.

• The problem is that Apache creates a CGI process and then shuts it down, and that step doesn’t scale.

• Why? The kernel’s O(N^2) algorithms make it impossible for the server to handle 10,000 concurrent connections.

• Two fundamental problems in the kernel:

• Connection count = thread count / process count. When a packet arrives, the kernel walks all of its processes to decide which one should handle it.

• Connection count = select count / poll count (single-threaded). Same scalability problem: every packet has to traverse every socket on the list.

• The fix: improve the kernel so lookups happen in constant time.

• Make thread switching time independent of the number of threads.

• Use a new scalable epoll() / IOCompletionPort that does socket lookups in constant time.

• Because thread scheduling doesn’t scale, servers apply epoll to sockets on a large scale, which forces asynchronous programming models — exactly the models Nginx and Node-type servers have. So when you migrate from Apache to Nginx and Node, performance doesn’t fall off a cliff as connections grow, even on a low-end server. At 10K connections, a laptop is even faster than a 16-core server.

The C10M Problem — The Next Decade

In the near future, servers will have to handle millions of concurrent connections. Under IPv6, every server’s potential connection count is in the millions, so the scale has to go up.

• Applications like IDS/IPS need to support this scale because they connect to a server backbone. Other examples: DNS root servers, TOR nodes, internet-scale Nmap, video streaming, banking, carrier NAT, VoIP PBX, load balancers, web caches, firewalls, email reception, spam filtering.

• People usually attribute internet-scale problems to applications rather than servers, because they sell hardware plus software. You buy an appliance and deploy it in your data center. Those appliances may contain an Intel board or a network processor, plus dedicated chips for encrypting and inspecting packets.

• As of February 2013, an x86 server with 40 Gbps, 32 cores, and 256 GB of RAM was listed on Newegg for $5,000. That server can handle over 10,000 concurrent connections; if it can’t, that’s because you chose the wrong software, not because of the underlying hardware. This hardware can easily scale to 10 million concurrent connections.

What the 10M concurrent connection challenge means:

1. 10 million concurrent connections

2. 1 million connections per second — with each connection lasting about 10 seconds at that rate

3. 10 GB/second of connections — fast connectivity to the internet

4. 10 million packets per second — current servers are estimated to handle 50K packets per second, and will do more later. Servers used to handle 100K interrupts per second, with every packet generating an interrupt.

5. 10 microsecond latency — a scalable server may handle this scale, but latency can spike.

6. 10 microsecond jitter — cap the maximum latency

7. Concurrency across 10 cores — software should support servers with more cores. Software typically scales to four cores easily. Servers scale to more cores, so software has to be rewritten to support them.

What We Learned Was Unix, Not Network Programming

• Many programmers learn network programming from W. Richard Stevens’ Unix Network Programming. The problem is that the book is about Unix, not just network programming. It tells you to let Unix do all the heavy work and just write a small server on top. But the kernel doesn’t scale; the answer is to move as much work as possible out of the kernel and handle the heavy lifting yourself.

• An influential example is Apache’s thread-per-connection model. It means the thread scheduler decides which read() to call next based on incoming data — in other words, it uses the thread scheduling system as a packet scheduling system. (I really like that framing; I’d never thought of it that way.)

• Nginx, by contrast, doesn’t use thread scheduling as a packet scheduler — it does its own packet scheduling. Using select to find the socket, it knows data has arrived and can read and process it immediately, so data never blocks.

• Lesson: let Unix handle the network stack; everything after that is yours.

How Do You Write Software That Scales?

How do you change your software so it scales? A lot of the received wisdom about scaling a project by throwing hardware at it is wrong. We need to know what performance actually looks like. To reach a higher level, these are the problems to solve:

1. Packet scalability

2. Multi-core scalability

3. Memory scalability

Packet Scalability — Write Your Own Driver to Bypass the Stack

• The problem with packets is that they have to go through the Unix kernel. The network stack is complex and slow; packets are better off reaching the application directly rather than passing through the OS first.

• The way to do that is to write your own driver. The driver sends packets straight to the application instead of through the stack. You can find drivers like this: PF_RING, NETMAP, Intel DPDK (Data Plane Development Kit). Intel’s isn’t open source, but it comes with plenty of technical support.

• How fast? Intel’s benchmark is 80 million packets per second on a fairly lightweight server (200 clock cycles per packet). That’s in user mode too: pass the packet up, process it in user mode, and send it back out. Linux handles no more than a million packets per second, bringing UDP packets up to user mode and back out again. The performance ratio between a custom driver and Linux is 80:1.

• For a target of 10 million packets per second, if 200 clock cycles go to getting the packet, 1,400 clock cycles remain for things like DNS/IDS functionality.

• What you get from PF_RING is raw packets, so you have to do your own TCP stack. What people do is a user-mode stack. Intel has a scalable TCP stack ready to go.

Multi-Core Scalability

Multi-core scalability is not the same as multi-thread scalability. We all know the idea: processors aren’t getting faster, we’re just adding more of them. Most code isn’t parallel beyond four cores. When we add more cores, not only does the performance grade drop — processing speed itself can get slower. That’s a software problem. We want software improvements to track the number of cores close to linearly.

Multi-threaded programming is different from multi-core programming.

• Multi-threaded

  • More than one thread per CPU core

  • Threads coordinated with locks (via system calls)

  • Each thread has a different task

• Multi-core

  • Exactly one thread per CPU core

  • When two threads/cores access the same data, they must not stop and wait for each other

  • Threads of the same task

• The problem to solve is how to spread one application across multiple cores.

• Locks in Unix are implemented in the kernel. With four cores using locks, most software starts waiting for other threads to release them. So the gain from adding cores is far outweighed by the cost of waiting.

• We need an architecture more like a highway than an intersection controlled by traffic lights — no waiting, everyone moving at their own pace, overhead kept as low as possible.

• Solutions:

  • Keep data structures in each core, then read the data in aggregate.

  • Atomicity. CPUs support instructions callable from C that guarantee atomicity and avoid conflicts. The cost is high, so don’t use them everywhere.

  • Lock-free data structures. Threads access without waiting; it’s complex work across different architectures, so don’t write your own.

  • Thread models — pipeline vs. worker thread. This isn’t just about synchronization; it’s about how your threads are architected.

  • Processor affinity. Tell the OS to prefer the first two cores, then set which core each thread runs on; you can also do this through interrupts. So the CPU is under your control, not Linux’s.

Memory Scalability

• If you have 20 GB of RAM and each connection takes 2 KB, and you have 20 MB of L3 cache, the cache holds no data at all. Data moves out to main memory and costs 300 clock cycles to process, during which the CPU does nothing.

• Each packet carries a cost of 1,400 clock cycles (DNS/IDS functionality) and 200 clock cycles (getting the packet). We can afford only four cache misses per packet. That’s a problem.

• Collocate data

  • Don’t scatter data all over memory behind pointers. Every pointer you chase is a cache miss: [hash pointer] -> [Task Control Block] -> [Socket] -> [App] — that’s four cache misses.

  • Keep all the data in one memory block: [TCB | socket | APP]. Preallocate memory for all blocks, cutting cache misses from four to one.

• Paging

  • 32 GB of data needs 64 MB of page tables, which don’t fit in cache. So you get two cache misses — the page table and the data it points to. This is a detail you can’t ignore when writing scalable software.

  • Solution: compress the data; use cache architectures with many memory accesses rather than binary search trees.

  • NUMA architectures double main-memory access time. The memory may not be on the local socket — it may be on another socket.

• Memory pools

  • Preallocate all memory up front, at startup.

  • Allocate on the basis of objects, threads, and sockets.

• Hyperthreading

  • Each network processor can run up to four threads; Intel’s can run two.

  • Where appropriate we also need to hide latency — for instance, one thread waiting on a memory access while another runs at full speed.

• Huge pages

  • Shrink the page table. Reserve memory from the start and let your application manage it.

Summary

• NIC

  • Problem: going through the kernel isn’t efficient.

  • Solution: use your own drivers and manage them yourself, keeping the adapter away from the OS.

• CPU

  • Problem: coordinating your application with traditional kernel methods doesn’t work.

  • Solution: Linux manages the first two CPUs; your application manages the rest. Interrupts happen only on the CPUs you allow.

• Memory

  • Problem: memory needs special attention to be efficient.

  • Solution: allocate most memory at system startup, in huge pages that you manage.

Give the control plane to Linux and let the application manage the data. No interaction between application and kernel, no thread scheduling, no system calls, no interrupts — none of it. Yet you still have code running on Linux that you can debug normally; this isn’t some exotic hardware system requiring specialized engineers. You do need custom hardware to push performance in the data plane, but it has to be in a programming and development environment you already know.

Original: The Secret To 10 Million Concurrent Connections — The Kernel Is The Problem, Not The Solution

(Translated by Zhou Xiaolu, reviewed by Zhong Hao.)