C10K 和 C10M
计算机领域的很多技术都是需求推动的，上世纪 90 年代，由于互联网的飞速发展，网络服务器无法支撑快速增长的用户规模。1999 年，Dan Kegel 提出了著名的 C10 问题：一台服务器上同时处理 10000 个客户网络连接。10000 个网络连接并不会发送请求到服务器，有些连接并不活跃，同一时刻，只有极少的部分连接发送请求。不同的服务类型，每个连接发送请求的频率也不相同，游戏服务器的连接会频繁的发送请求，而 Web 服务器的连接发送请求的频率就低很多。无论如何，根据经验法则，对于特定的服务类型，连接越多，同一时刻发送请求的连接也越多。
时至今日，C10K 问题当然早已解决，不仅如此，一台机器能支撑的连接越来越多，后来提出了 C10M 问题，在一台机器上支撑 1000 万的连接，2015 年，MigratoryData 在单机承载 12M 的连接，解决了 C10M 问题。
本文先回顾 C10 问题的解决方案，再探讨如何构建支撑 C10M 的应用程序，聊聊其中涉及的各种技术。
C10K 问题的解决
时间退回到 1999 年，当时要实现一个网络服务器，大概有这样几种模式
简单进程 / 线程模型
这是一种非常简单的模式，服务器启动后监听端口，阻塞在 accept 上，当新网络连接建立后，accept 返回新连接，服务器启动一个新的进程 / 线程专门负责这个连接。从性能和伸缩性来说，这种模式是非常糟糕的，原因在于
进程 / 线程创建和销毁的时间，操作系统创建一个进程 / 线程显然需要时间，在一个繁忙的服务器上，如果每秒都有大量的连接建立和断开，采用每个进程 / 线程处理一个客户连接的模式，每个新连接都要创建创建一个进程 / 线程，当连接断开时，销毁对应的线程 / 进程。创建和销毁进程 / 线程的操作消耗了大量的 CPU 资源。使用进程池和线程池可以缓解这个问题。
内存占用。主要包含两方面，一个是内核数据结构所占用的内存空间，另外一个是 Stack 所占用的内存。有些应用的调用栈很深，比如 Java 应用，经常能看到几十上百层的调用栈。
上下文切换的开销。上下文切换时，操作系统的调度器中断当前线程，选择另外一个可运行的线程在 CPU 上继续运行。调度器需要保存当前线程的现场信息，然后选择一个可运行的线程，再将新线程的状态恢复到寄存器中。保存和恢复现场所需要的时间和 CPU 型号有关，选择一个可运行的线程则完全是软件操作，Linux 2.6 才开始使用常量时间的调度算法。以上是上下文切换的直接开销。除此之外还有一些间接开销，上下文切换导致相关的缓存失效，比如 L1/L2 Cache，TLB 等，这些也会影响程序的性能，但是间接开销很难衡量。
有意思的是，这种模式虽然性能极差，但却依然是我们今天最常见到的模式，很多 Web 程序都是这样的方式在运行。
select/poll
另外一种方式是使用 select/poll，在一个线程内处理多个客户连接。select 和 poll 能够监控多个 socket 文件描述符，当某个文件描述符就绪，select/soll 从阻塞状态返回，通知应用程序可以处理用户连接了。使用这种方式，我们只需要一个线程就可以处理大量的连接，避免了多进程 / 线程的开销。之所以把 select 和 poll 放在一起说，原因在于两者非常相似，性能上基本没有区别，唯一的区别在于 poll 突破了 select 1024 个文件描述符的限制，然而当文件描述符数量增加时，poll 性能急剧下降，因此所谓突破 1024 个文件描述符实际上毫无意义。select/poll 并不完美，依然存在很多问题：
- 每次调用 select/poll，都要把文件描述符的集合从用户地址空间复制到内核地址空间
- select/poll 返回后，调用方必须遍历所有的文件描述符，逐一判断文件描述符是否可读 / 可写。
这两个限制让 select/poll 完全失去了伸缩性。连接数越多，文件描述符就越多，文件描述符越多，每次调用 select/poll 所带来的用户空间到内核空间的复制开销越大。最严重的是当报文达到，select/poll 返回之后，必须遍历所有的文件描述符。假设现在有 1 万个连接，其中只一个连接发送了请求，但是 select/poll 就要把 1 万个连接全部检查一遍。
epoll
FreeBSD 4.1 引入了 kqueue，此时是 2000 年 7 月，而在 Linux 上，还要等待 2 年后的 2002 年才开始引入 kqueue 的类似实现: epoll。epoll 最初于 2.5.44 进入 Linux kernel mainline，此时已经是 2002 年，距离 C10K 问题提出已经过了 3 年。
epoll 是如何提供一个高性能可伸缩的 IO 多路复用机制呢？首先，epoll 引入了 epoll instance 这个概念，epoll instance 在内核中关联了一组要监听的文件描述符配置：interest list，这样的好处在于，每次要增加一个要监听的文件描述符，不需要把所有的文件描述符都配置一次，然后从用户地址空间复制到内核地址空间，只需要把单个文件描述符复制到内核地址空间，复制开销从 O(n)降到了 O(1)。
注册完文件描述符后，调用 epoll_wait 开始等待文件描述符事件。epoll_wait 可以只返回已经 ready 的文件描述符，因此，在 epoll_wait 返回之后，程序只需要处理真正需要处理的文件描述符，而不用把所有的文件描述符全部遍历一遍。假设在全部 N 个文件描述符中，只有一个文件描述符 Ready，select/poll 要执行 N 次循环，epoll 只需要一次。
epoll 出现之后，Linux 上才真正有了一个可伸缩的 IO 多路复用机制。基于 epoll，能够支撑的网络连接数取决于硬件资源的配置，而不再受限于内核的实现机制。CPU 越强，内存越大，能支撑的连接数越多。
编程模型
Reactor 和 proactor
不同的操作系统上提供了不同的 IO 多路复用实现，Linux 上有 epoll，FreeBSD 有 kqueue，Windows 有 IOCP。对于需要跨平台的程序，必然需要一个抽象层，提供一个统一的 IO 多路复用接口，屏蔽各个系统接口的差异性。
Reactor 是实现这个目标的一次尝试，最早出现在 Douglas C. Schmidt 的论文 ”The Reactor An Object-Oriented Wrapper for Event-Driven Port Monitoring and Service Demultiplexing” 中。从论文的名字可以看出，Reactor 是 poll 这种编程模式的一个面向对象包装。考虑到论文的时间，当时正是面向对象概念正火热的时候，什么东西都要蹭蹭面向对象的热度。论文中，DC Schmidt 描述了为什么要做这样的一个 Wrapper，给出了下面几个原因：
- 操作系统提供的接口太复杂，容易出错。select 和 poll 都是通用接口，因为通用，增加了学习和正确使用的复杂度。
- 接口抽象层次太低，涉及太多底层的细节。
- 不能跨平台移植。
- 难以扩展。
实际上除了第三条跨平台，其他几个理由实在难以站得住脚。select/poll 这类接口复杂吗，使用起来容易出错吗，写出来的程序难以扩展吗？不过不这么说怎么体现 Reactor 的价值呢。正如论文名称所说的，Reactor 本质是对操作系统 IO 多路复用机制的一个面向对象包装，为了证明 Reactor 的价值，DC Schmidt 还用 C ++ 面向对象的特性实现了一个编程框架：ACE，实际上使用 ACE 比直接使用 poll 或者 epoll 复杂多了。
后来 DC Schmidt 写了一本书《面向模式的软件架构》，再次提到了 Reactor，并重新命名为 Reactor Pattern，现在网络上能找到的 Reactor 资料，基本上都是基于 Reactor Pattern，而不是早期的面向 Object-Orientend Wrapper。
《面向模式的软件》架构中还提到了另外一种叫做 Proactor 的模式，和 Reactor 非常类似，Reactor 针对同步 IO，Proactor 则针对异步 IO。
Callback，Future 和纤程
Reactor 看上去并不复杂，但是想编写一个完整的应用程序时候就会发现其实没那么简单。为了避免 Reactor 主逻辑阻塞，所有可能会导致阻塞的操作必须注册到 epoll 上，带来的问题就是处理逻辑的支离破碎，大量使用 callback，产生的代码复杂难懂。如果应用程序中还有非网络 IO 的阻塞操作，问题更严重，比如在程序中读写文件。Linux 中文件系统操作都是阻塞的，虽然也有 Linux AIO，但是一直不够成熟，难堪大用。很多软件采用线程池来解决这个问题，不能通过 epoll 解决的阻塞操作，扔到一个线程池执行。这又产生了多线程内存开销和上下文切换的问题。
Future 机制是对 Callback 的简单优化，本质上还是 Callback，但是提供了一致的接口，代码相对来说简单一些，不过在实际使用中还是比较复杂的。Seastar 是一个非常彻底的 future 风格的框架，从它的代码可以看到这种编程风格真的非常复杂，阻塞式编程中一个函数几行代码就能搞定的事情，在 Seastar 里需要上百行代码，几十个 labmda (在 Seastar 里叫做 continuation)。
纤程是一种用户态调度的线程，比如 Go 语言中的 goroutine，有些人可能会把这种机制成为 coroutine，不过我认为 coroutine 和纤程还是有很大区别的，coroutine 是泛化的子进程，具有多个进入和退出点，用来一些一些相互协作的程序，典型的例子就是 Python 中的 generator。纤程则是一种运行和调度机制。
纤程真正做到了高性能和易用，在 Go 语言中，使用 goroutine 实现的高性能服务器是一件轻松愉快的事情，完全不用考虑线程数、epoll、回调之类的复杂操作，和编写阻塞式程序完全一样。
网络优化
Kernel bypass
网络子系统是 Linux 内核中一个非常庞大的组件，提供了各种通用的网络能力。通用通常意味在在某些场景下并不是最佳选择。实际上业界的共识是 Linux 内核网络不支持超大并发的网络能力。根据我过去的经验，Linux 最大只能处理 1MPPS，而现在的 10Gbps 网卡通常可以处理 10MPPS。随着更高性能的 25Gbps，40Gbps 网卡出现，Linux 内核网络能力越发捉襟见肘。
为什么 Linux 不能充分发挥网卡的处理能力？原因在于：
- 大多数网卡收发使用中断方式，每次中断处理时间大约 100us，另外要考虑 cache miss 带来的开销。部分网卡使用 NAPI，轮询 + 中断结合的方式处理报文，当报文放进队列之后，依然要触发软中断。
- 数据从内核地址空间复制到用户地址空间。
- 收发包都有系统调用。
- 网卡到应用进程的链路太长，包含了很多不必要的操作。
Linux 高性能网络一个方向就是绕过内核的网络栈(kernel bypass)，业界有不少尝试。
- PF_RING 高效的数据包捕获技术，比 libpcap 性能更好。需要自己安装内核模块，启用 ZC Driver，设置 transparent_mode= 2 的情况下，报文直接投递到客户端程序，绕过内核网络栈。
- Snabbswitch 一个 Lua 写的网络框架。完全接管网卡，使用 UIO(Userspace IO)技术在用户态实现了网卡驱动。
- Intel DPDK，直接在用户态处理报文。非常成熟，性能强大，限制是只能用在 Intel 的网卡上。根据 DPDK 的数据，3GHz 的 CPU Core 上，平均每个报文的处理时间只要 60ns（一次内存的访问时间）。
- Netmap 一个高性能收发原始数据包的框架，包含了内核模块以及用户态库函数，需要网卡驱动程序配合，因此目前只支持特定的几种网卡类型，用户也可以自己修改网卡驱动。
- XDP，使用 Linux eBPF 机制，将报文处理逻辑下放到网卡驱动程序中。一般用于报文过滤、转发的场景。
kernel bypass 技术最大的问题在于不支持 POSIX 接口，用户没办法不修改代码直接移植到一种 kernel bypass 技术上。对于大多数程序来说，还要要运行在标准的内核网络栈上，通过调整内核参数提升网络性能。
网卡多队列
报文到达网卡之后，在一个 CPU 上触发中断，CPU 执行网卡驱动程序从网卡硬件缓冲区读取报文内容，解析后放到 CPU 接收队列上。这里所有的操作都在一个特定的 CPU 上完成，高性能场景下，单个 CPU 处理不了所有的报文。对于支持多队列的网卡，报文可以分散到多个队列上，每个队列对应一个 CPU 处理，解决了单个 CPU 处理瓶颈。
为了充分发挥多队列网卡的价值，我们还得做一些额外的设置：把每个队列的中断号绑定到特定 CPU 上。这样做的目的，一方面确保网卡中断的负载能分配到不同的 CPU 上，另外一方面可以将负责网卡中断的 CPU 和负责应用程序的 CPU 区分开，避免相互干扰。
在 Linux 中，/sys/class/net/${interface}/device/msi_irqs 下保存了每个队列的中断号，有了中断号之后，我们就可以设置中断和 CPU 的对应关系了。网上有很多文章可以参考。
网卡 Offloading
回忆下 TCP 数据的发送过程：应用程序将数据写到套接字缓冲区，内核将缓冲区数据切分成不大于 MSS 的片段，附加上 TCP Header 和 IP Header，计算 Checksum，然后将数据推到网卡发送队列。这个过程中需要 CPU 全程参与，随着网卡的速度越来越快，CPU 逐渐成为瓶颈，CPU 处理数据的速度已经赶不上网卡发送数据的速度。经验法则，发送或者接收 1bit/s TCP 数据，需要 1Hz 的 CPU，1Gbps 需要 1GHz 的 CPU，10Gbps 需要 10GHz 的 CPU，已经远超单核 CPU 的能力，即使能完全使用多核，假设单个 CPU Core 是 2.5GHz，依然需要 4 个 CPU Core。
为了优化性能，现代网卡都在硬件层面集成了 TCP 分段、添加 IP Header、计算 Checksum 等功能，这些操作不再需要 CPU 参与。这个功能叫做 tcp segment offloading，简称 tso。使用 ethtool -k 可以检查网卡是否开启了 tso
除了 tso，还有其他几种 offloading，比如支持 udp 分片的 ufo，不依赖驱动的 gso，优化接收链路的 lro
充分利用多核
随着摩尔定律失效，CPU 已经从追求高主频转向追求更多的核数，现在的服务器大都是 96 核甚至更高。构建一个支撑 C10M 的应用程序，必须充分利用所有的 CPU，最重要的是程序要具备水平伸缩的能力：随着 CPU 数量的增多程序能够支撑更多的连接。
很多人都有一个误解，认为程序里使用了多线程就能利用多核，考虑下 CPython 程序，你可以创建多个线程，但是由于 GIL 的存在，程序最多只能使用单个 CPU。实际上多线程和并行本身就是不同的概念，多线程表示程序内部多个任务并发执行，每个线程内的任务可以完全不一样，线程数和 CPU 核数没有直接关系，单核机器上可以跑几百个线程。并行则是为了充分利用计算资源，将一个大的任务拆解成小规模的任务，分配到每个 CPU 上运行。并行可以 通过多线程实现，系统上有几个 CPU 就启动几个线程，每个线程完成一部分任务。
并行编程的难点在于如何正确处理共享资源。并发访问共享资源，最简单的方式就加锁，然而使用锁又带来性能问题，获取锁和释放锁本身有性能开销，锁保护的临界区代码不能只能顺序执行，就像 CPython 的 GIL，没能充分利用 CPU。
Thread Local 和 Per-CPU 变量
这两种方式的思路是一样的，都是创建变量的多个副本，使用变量时只访问本地副本，因此不需要任何同步。现代编程语言基本上都支持 Thread Local，使用起来也很简单，C/C++ 里也可以使用__thread 标记声明 ThreadLocal 变量。
Per-CPU 则依赖操作系统，当我们提到 Per-CPU 的时候，通常是指 Linux 的 Per-CPU 机制。Linux 内核代码中大量使用 Per-CPU 变量，但应用代码中并不常见，如果应用程序中工作线程数等于 CPU 数量，且每个线程 Pin 到一个 CPU 上，此时才可以使用。
原子变量
如果共享资源是 int 之类的简单类型，访问模式也比较简单，此时可以使用原子变量。相比使用锁，原子变量性能更好。在竞争不激烈的情况下，原子变量的操作性能基本上和加锁的性能一致，但是在并发比较激烈的时候，等待锁的线程要进入等待队列等待重新调度，这里的挂起和重新调度过程需要上下文切换，浪费了更多的时间。
大部分编程语言都提供了基本变量对应的原子类型，一般提供 set, get, compareAndSet 等操作。
lock-free
lock-free 这个概念来自
An algorithm is called non‐blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; an algorithm is called lock‐free if, at each step, some thread can make progress.
non-blocking 算法任何线程失败或者挂起，不会导致其他线程失败或者挂起，lock-free 则进一步保证线程间无依赖。这个表述比较抽象，具体来说，non-blocking 要求不存在互斥，存在互斥的情况下，线程必须先获取锁再进入临界区，如果当前持有锁的线程被挂起，等待锁的线程必然需要一直等待下去。对于活锁或者饥饿的场景，线程失败或者挂起的时候，其他线程完全不仅能正常运行，说不定还解决了活锁和饥饿的问题，因此活锁和饥饿符合 non-blocking，但是不符合 lock-free。
实现一个 lock-free 数据结构并不容易，好在已经有了几种常见数据结构的的 lock-free 实现：buffer, list, stack, queue, map, deque，我们直接拿来使用就行了。
优化对锁的使用
有时候没有条件使用 lock-free，还是得用锁，对于这种情况，还是有一些优化手段的。首先使用尽量减少临界区的大小，使用细粒度的锁，锁粒度越细，并行执行的效果越好。其次选择适合的锁，比如考虑选择读写锁。
CPU affinity
使用 CPU affinity 机制合理规划线程和 CPU 的绑定关系。前面提到使用 CPU affinity 机制，将多队列网卡的中断处理分散到多个 CPU 上。不仅是中断处理，线程也可以绑定，绑定之后，线程只会运行在绑定的 CPU 上。为什么要将线程绑定到 CPU 上呢？绑定 CPU 有这样几个好处:
- 为线程保留 CPU，确保线程有足够的资源运行
- 提高 CPU cache 的命中率，某些对 cache 敏感的线程必须绑定到 CPU 上才行。
- 更精细的资源控制。可以预先需要静态划分各个工作线程的资源，例如为每个请求处理线程分配一个 CPU，其他后台线程共享一个 CPU，工作线程和中断处理程序工作在不同的 CPU 上。
- NUMA 架构中，每个 CPU 有自己的内存控制器和内存插槽，CPU 访问本地内存别访问远程内存快 3 倍左右。使用 affinity 将线程绑定在 CPU 上，相关的数据也分配到 CPU 对应的本地内存上。
Linux 上设置 CPU affinity 很简单，可以使用命令行工具 taskset，也可以在程序内直接调用 API sched_getaffinity和sched_setaffinity.
其他优化技术
使用 Hugepage
Linux 中，程序内使用的内存地址是虚拟地址，并不是内存的物理地址。为了简化虚拟地址到物理地址的映射，虚拟地址到物理地址的映射最小单位是“Page”，默认情况下，每个页大小为 4KB。CPU 指令中出现的虚拟地址，为了读取内存中的数据，指令执行前要把虚拟地址转换成内存物理地址。Linux 为每个进程维护了一张虚拟地址到物理地址的映射表，CPU 先查表找到虚拟地址对应的物理地址，再执行指令。由于映射表维护在内存中，CPU 查表就要访问内存。相对 CPU 的速度来说，内存其实是相当慢的，一般来说，CPU L1 Cache 的访问速度在 1ns 左右，而一次内存访问需要 60-100ns，比 CPU 执行一条指令要慢得多。如果每个指令都要访问内存，比如严重拖慢 CPU 速度，为了解决这个问题，CPU 引入了 TLB(translation lookaside buffer)，一个高性能缓存，缓存映射表中一部分条目。转换地址时，先从 TLB 查找，没找到再读内存。
显然，最理想的情况是映射表能够完全缓存到 TLB 中，地址转换完全不需要访问内存。为了减少映射表大小，我们可以使用“HugePages”：大于 4KB 的内存页。默认 HugePages 是 2MB，最大可以到 1GB。
避免动态分配内存
内存分配是个复杂且耗时的操作，涉及空闲内存管理、分配策略的权衡（分配效率，碎片），尤其是在并发环境中，还要保证内存分配的线程安全。如果内存分配成为了应用瓶颈，可以尝试一些优化策略。比如内存复用 i：不要重复分配内存，而是复用已经分配过的内存，在 C ++/Java 里则考虑复用已有对象，这个技巧在 Java 里尤其重要，不仅能降低对象创建的开销，还避免了大量创建对象导致的 GC 开销。另外一个技巧是预先分配内存，实际上相当于在应用内实现了一套简单的内存管理，比如 Memcached 的 Slab。
Zero Copy
对于一个 Web 服务器来说，响应一个静态文件请求需要先将文件从磁盘读取到内存中，再发送到客户端。如果自信分析这个过程，会发现数据首先从磁盘读取到内核的页缓冲区，再从页缓冲区复制到 Web 服务器缓冲区，接着从 Web 服务器缓冲区发送到 TCP 发送缓冲区，最后经网卡发送出去。这个过程中，数据先从内核复制到进程内，再从进程内回到内核，这两次复制完全是多余的。Zero Copy 就是类似情况的优化方案，数据直接在内核中完成处理，不需要额外的复制。
Linux 中提供了几种 ZeroCopy 相关的技术，包括 sendfile,splice,copy_file_range,Web 服务器中经常使用sendfile 优化性能。
最后
千万牢记：不要过早优化。
优化之前，先考虑两个问题：
- 现在的性能是否已经满足需求了
- 如果真的要优化，是不是已经定位了瓶颈
在回答清楚这两个问题之前，不要盲目动手。
本文作者：太公
阅读原文
本文为云栖社区原创内容，未经允许不得转载。