Binary Search Tree Iterator(中序遍历)

C10k问题

C10k问题是关于web服务器同时处理上万条客户端连接的问题。在计算机发展的早期计算机硬件昂贵，要实现10k级别的连接要求对服务器而言显然瓶颈在硬件上。但如今，对于高并发的服务器设计而言，硬件已经不再是其瓶颈，甚至支持10k级别的连接现在也不是那么困难，但对于高并发的要求仍然是不得不面对的问题，因此C10k问题也便成为了高并发服务器设计所必须要面对的问题。这个问题的瓶颈也由硬件向软件转变。

而要设计好一个网络服务程序，需要注意如下问题：

• 如何从一个单一线程中发出多个I/O调用

  1. 不要使用阻塞/同步的调用，也不要使用多线程或进程去实现并发
  2. 使用非阻塞(O_NONBLOCK)和轮询通知(poll()或/dev/poll)的方式使用I/O，这种方式仅适用于网络应用，不适用于磁盘I/O
  3. 使用异步I/O(aio)实现高并发的网络或磁盘I/O也是一个不错的选择

• 如何设计服务模型去服务每一个客户端

  1. 一个进程服务一个客户端(经典的Unix服务模型)
  2. 一个系统级线程服务多个客户端，每个客户端被一个用户级线程控制或被一个状态机控制
  3. 一个系统级线程对应一个客户端
  4. 一个系统级线程对应一个激活的客户端（如Tomcat的设计，线程池的设计，NT的完成端口的设计）

• 是否使用标准OS服务，或者向内核中加入一些自定制代码以满足设计要求

网络应用设计中的I/O策略

由于网络应用的发展及如上的基本思路，产生了如下的经典的网络程序的服务模型。

多对一服务模型

多对一的服务模型可以说是最流行的服务模型，其依靠一个单一线程去监控多个连接的客户端套接字。在这种服务模型下又有三种实现方式：非阻塞与水平触发方式、非阻塞与边沿触发方式、异步I/O与完成通知方式。

非阻塞与水平触发

非阻塞的模式贯穿网络应用设计的始终，与其相配合的往往是如select()或poll()这样内核所设计的轮询与通知机制。而水平触发是相对于边沿触发而言的，其来源于硬件设计中，而在这里是指：

内核在最后时刻通知是否有文件描述符准备就绪，是否有文件描述符完成了某个事件。
Note 但需要注意的是，内核的通知仅仅是一个提醒，这个文件描述符可能在你去读或写的时候并没有准备好，因此非阻塞模式就显得尤为重要了。

对于以单个线程通过水平触发的方式管理多个套接字有如下几种实现方式：

• select()

  select是常见的一个系统调用，它提供了轮询机制来通知内核事件。但不幸的是，它的处理极限受到FD_SETSIZE的限制，这个限制被编译到了标准库中。

• poll()

  poll没有像select那样的处理极限的限制，但对于有大量文件描述符就绪的情况下，扫描完所有就绪文件描述符也是很耗时的。针对这一情况，在一些系统中有人对poll的通知机制做了改进,但这涉及到内核的改动。

• /dev/poll

  这是Solaris上poll最理想的替代品。使用它时，在轮询时只会遍历所有就绪的文件描述符，这对于select和poll来说显然是做了很大的改进。
  同时在linux上也出现了很多不同的/dev/poll的实现，但它的所有实现中没有一个可以媲美epoll,因此在linux上/dev/poll不建议使用。

• kqueue()

  这是FreeBSD上poll的替代品

非阻塞与边沿触发

边沿触发是指：

你给内核一个文件描述符，之后，当该文件描述符从未就绪状态像就绪状态迁移时，内核会通知你。
Note 假设一个文件描述符已经就绪，你将不会再收到相应的通知，直到对其进行处理后改文件描述符从就绪状态变为未就绪状态。

与水平触发不同，边沿触发方式中，当你遗漏了一个事件，那么该事件所位于连接将会被永远遗漏，因此在编程中很容易引发因遗漏事件而产生的bug。然而，边沿触发的方式也令使用OpenSSL编写非阻塞的客户端变得更容易，因此也值得去尝试。

使用边沿触发方式实现一对多服务模型的方式：

• kqueue()

  这是FreeBSD上边沿触发poll的替代品。

• epoll
• Polyakov’s kevent
• Drepper’s New Network interface
• Realtime Signals
• Signal-per-fd

异步I/O

可能是因为很少有操作系统支持异步I/O,所以这种实现在Unix上并不流行。但一些地方确具有其独特的优势，同时AIO正常来讲是使用边沿触发方式的异步通知方式，当某事件完成，相应信号会入队等待确认处理。

一对一服务模型

关于非阻塞的一对多服务模型为什么流行就不得不说关于阻塞方式及一对一服务模型的缺点。在阻塞的I/O方式下，一个客户端必须由一个单独的线程服务，由现在的线程模型设计，每个线程都有其对应的堆栈空间，因此每个连接相当于对应每个堆栈。

如果每个线程都有一个2MB的堆栈，当出现512个连接时就需要512个线程管理，即堆栈就需要占据1GB大小的虚拟地址空间。这在32bit处理器系统下显然是一个极为糟糕的问题。面对这个问题两种解决思路，一种是限制线程堆栈大小，二是使用64bit处理器。因此在这样的背景下产生了上面的一对多模型。

但是随着线程模型在Linux，FreeBSD和Solaris上的改进，同时64位处理器也已经成为主流处理器，可能不远的将来，对于解决10k级别的并发连接问题一对一模型会成为更好的选择，但是仅目前来说，一对多模型还是更具有优势的。

因此一对一模型所关注的问题就不再连接的管理和I/O本身了，而是线程模型的设计上了。下表展示了目前主流的线程模型及其概述。

线程模型	描述
LinuxThreads	linux的标准线程库，整合进glibc2.0,Posix兼容，但性能不佳，缺乏信号支持
NGPT(Next Generation Posix Threads for Linux)	NGPT是由IBM发起的一个Posix兼容良好的Linux线程库项目
NPTL(Native Posix Thread Library for Linux)	由Ulrich Drepper和Ingo Molnar发起的一流的面向linux的Posix线程库项目
FreeBSD threading support	FreeBSD同时支持LinuxThreads和一个用户空间线程库
NetBSD threading Support	内核实现了一个M:N线程模型
Solaris threading support	在Solaris2到Solaris8上默认使用M:N线程模型，在Solaris9上默认为1:1线程模型

内核服务模型

在内核中直接构建服务器的做法避免了内核与用户空间的交互，对于处理高并发问题具有最大的灵活性，但确面临实现和移植困难这两个双重难题，但仍然有例可参考，如linxu下的khttpd，和Ingo Molnar所设计的TUX都是直接在内核中进行实现的。虽然对于普及性来讲没那么高，但从解决问题的思路上来讲却仍然让人耳目一新。

用户空间协议栈模型

目前主流的系统协议栈的设计都是直接在内核中实现的，但是在内核中实现仍然存在一些不可避免的性能瓶颈问题，因此在此基础上，又产生了许多用户空间协议栈的设计思路，其中比较典型的当属Intel的DBDK,其对于高性能，高并发要求较高的场合，其在很多方面是优于内核原始的协议栈的。

c10k

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com