C10M - The Kernel is the Problem, Not the Solution

C10K早已经不是问题，开始迎接C10M的挑战。
这篇文章列出了Linux 内核面对C10M的瓶颈：数据包的处理，CPU调度，内存管理。很有启发性。

The kernel isn’t the solution. The kernel is the problem.

Don’t let the kernel do all the heavy lifting. Take packet handling, memory management, and processor scheduling out of the kernel and put it into the application, where it can be done efficiently. Let Linux handle the control plane and let the the application handle the data plane.

不要让内核做了所有的通用的工作：收发数据包，内存管理，进程调度。把一些工作放到用户的app里，因为用户层的app可以根据应用的特性，精确的控制好数据的处理。
内核做控制，用户层做数据处理。

设计一个面向数据处理的系统，每秒可以处理10M个数据包；而现在的面向控制的Linux系统最多1M个数据包。

The Apache problem is the more connections the worse the performance.
Key insight: performance and scalability or orthogonal concepts. They don’t mean the same thing. When people talk about scale they often are talking about performance, but there’s a difference between scale and performance. As we’ll see with Apache.
With short term connections that last a few seconds, say a quick transaction, if you are executing a 1000 TPS then you’ll only have about a 1000 concurrent connections to the server.
Change the length of the transactions to 10 seconds, now at 1000 TPS you’ll have 10K connections open. Apache’s performance drops off a cliff though which opens you to DoS attacks. Just do a lot of downloads and Apache falls over.
If you are handling 5,000 connections per second and you want to handle 10K, what do you do? Let’s say you upgrade hardware and double it the processor speed. What happens? You get double the performance but you don’t get double the scale. The scale may only go to 6K connections per second. Same thing happens if you keep on doubling. 16x the performance is great but you still haven’t got to 10K connections. Performance is not the same as scalability.
The problem was Apache would fork a CGI process and then kill it. This didn’t scale.
Why? Servers could not handle 10K concurrent connections because of O(n^2) algorithms used in the kernel.
    Two basic problems in the kernel:
        Connection = thread/process. As a packet came in it would walk down all 10K processes in the kernel to figure out which thread should handle the packet
        Connections = select/poll (single thread). Same scalability problem. Each packet had to walk a list of sockets.
    Solution: fix the kernel to make lookups in constant time
        Threads now constant time context switch regardless of number of threads.
        Came with a new scalable epoll()/IOCompletionPort constant time socket lookup.
Thread scheduling still didn’t scale so servers scaled using epoll with sockets which led to the asynchronous programming model embodied in Node and Nginx. This shifted software to a different performance graph.  Even with a slower server when you add more connections the performance doesn’t drop off a cliff. At 10K connections a laptop is even faster than a 16 core server.

C10M - 下一个十年的目标。

Examples of applications that will need this sort of scalability: IDS/IPS because they connection to a server backbone. Other examples: DNS root server, TOR node, Nmap of Internet, video streaming, banking, Carrier NAT, Voip PBX, load balancer, web cache, firewall, email receive, spam filtering.
Often people who see Internet scale problems are appliances rather than servers because they are selling hardware + software. You buy the device and insert it into your datacenter. These devices may contain an Intel motherboard or Network processors and specialized chips for encryption, packet inspection, etc.
X86 prices on Newegg as of Feb 2013 - $5K for 40gpbs, 32-cores, 256gigs RAM. The servers can do more than 10K connections. If they can’t it’s because you’ve made bad choices with software. It’s not the underlying hardware that’s the issues. This hardware can easily scale to 10 million concurrent connections.

C10M问题的定义

10 million concurrent connections
1 million connections/second - sustained rate at about 10 seconds a connections
10 gigabits/second connection - fast connections to the Internet.
10 million packets/second - expect current servers to handle 50K packets per second, this is going to a higher level. Servers used to be able to handle 100K interrupts per second and every packet caused interrupts.
10 microsecond latency - scalable servers might handle the scale but latency would spike.
10 microsecond jitter - limit the maximum latency
10 coherent CPU cores - software should scale to larger numbers of cores. Typically software only scales easily to four cores. Servers can scale to many more cores so software needs to be rewritten to support larger core machines.

Richard教会我们的是Unix编程而不是网络编程。

A generation of programmers has learned network programming by reading Unix Networking Programming by W. Richard Stevens. The problem is the book is about Unix, not just network programming. It tells you to let Unix do all the heavy lifting and you just write a small little server on top of Unix. But the kernel doesn’t scale. The solution is to move outside the kernel and do all the heavy lifting yourself.
An example of the impact of this is to consider Apache’s thread per connection model. What this means is the thread scheduler determines which read() to call next depending on which data arrives. You are using the thread scheduling system as the packet scheduling system. (I really like this, never thought of it that way before).
What Nginx says it don’t use thread scheduling as the packet scheduler. Do the packet scheduling yourself. Use select to find the socket, we know it has data so we can read immediately and it won’t block, and then process the data.

Lesson: Let Unix handle the network stack, but you handle everything from that point on.
    不要用线程的调度来代替数据包的调度

packet scalability
    multi-core scalability
    memory scalability

数据包
    多核
    内存

The problem with packets is they go through the Unix kernel. The network stack is complicated and slow. The path of packets to your application needs to be more direct. Don’t let the OS handle the packets.
The way to do this is to write your own driver. All the driver does is send the packet to your application instead of through the stack. You can find drivers: PF_RING, Netmap, Intel DPDK (data plane development kit). The Intel is closed source, but there’s a lot of support around it.
How fast? Intel has a benchmark where the process 80 million packets per second (200 clock cycles per packet) on a fairly lightweight server. This is through user mode too. The packet makes its way up through to user mode and then down again to go out. Linux doesn’t do more than a million packets per second when getting UDP packets up to user mode and out again. Performance is 80-1 of a customer driver to a Linux.
For the 10 million packets per second goal if 200 clock cycles are used in getting the packet that leaves 1400 clocks cycles to implement functionally like a DNS/IDS.
With PF_RING you get raw packets so you have to do your TCP stack. People are doing user mode stacks. For Intel there is an available TCP stack that offers really scalable performance.

多核和多线程

Multi-threading:
    More than one thread per CPU core
    Locks to coordinate threads (done via system calls)
    Each thread a different task
Multi-core:
    One thread per CPU core
    When two threads/cores access the same data they can’t stop and wait for each other
    All threads part of the same task
Our problem is how to spread an application across many cores.
Locks in Unix are implemented in the kernel. What happens at 4 cores using locks is that most software starts waiting for other threads to give up a lock. So the kernel starts eating up more performance than you gain from having more CPUs.
What we need is an architecture that is more like a freeway than an intersection controlled by a stop light. We want no waiting where everyone continues at their own pace with as little overhead as possible.

Keep data structures per core. Then on aggregation read all the counters.
        Atomics. Instructions supported by the CPU that can called from C. Guaranteed to be atomic, never conflict. Expensive, so don’t want to use for everything.
        Lock-free data structures. Accessible by threads that never stop and wait for each other. Don’t do it yourself. It’s very complex to work across different architectures.
        Threading model. Pipelined vs worker thread model. It’s not just synchronization that’s the problem, but how your threads are architected.
        Processor affinity. Tell the OS to use the first two cores. Then set where your threads run on which cores. You can also do the same thing with interrupts. So you own these CPUs and Linux doesn’t.

The problem is if you have 20gigs of RAM and let’s say you use 2k per connection, then if you only have 20meg L3 cache, none of that data will be in cache. It costs 300 clock cycles to go out to main memory, at which time the CPU isn’t doing anything.
Think about this with our 1400 clock cycle budge per packet. Remember 200 clocks/pkt overhead. We only have 4 cache misses per packet and that's a problem.
Co-locate Data
    Don’t scribble data all over memory via pointers. Each time you follow a pointer it will be a cache miss: [hash pointer] -> [Task Control Block] -> [Socket] -> [App]. That’s four cache misses.
    Keep all the data together in one chunk of memory: [TCB | Socket | App]. Prereserve memory by preallocating all the blocks. This reduces cache misses from 4 to 1.
Paging
    The paging table for 32gigs require 64MB of paging tables which doesn’t fit in cache. So you have two caches misses, one for the paging table and one for what it points to. This is detail we can’t ignore for scalable software.
    Solutions: compress data; use cache efficient structures instead of binary search tree that has a lot of memory accesses 
    NUMA architectures double the main memory access time. Memory may not be on a local socket but is on another socket.
Memory pools
    Preallocate all memory all at once on startup.
    Allocate on a per object, per thread, and per socket basis.
Hyper-threading
    Network processors can run up to 4 threads per processor, Intel only has 2.
    This masks the latency, for example, from memory accesses because when one thread waits the other goes at full speed.
Hugepages
    Reduces page table size. Reserve memory from the start and then your application manages the memory.

NIC
        Problem: going through the kernel doesn’t work well.
        Solution: take the adapter away from the OS by using your own driver and manage them yourself
    CPU
        Problem: if you use traditional kernel methods to coordinate your application it doesn’t work well.
        Solution: Give Linux the first two CPUs and you application manages the remaining CPUs. No interrupts will happen on those CPUs that you don’t allow.
    Memory
        Problem: Takes special care to make work well.
        Solution: At system startup allocate most of the memory in hugepages that you manage.