摘要


編寫連接數(shù)巨大的高負(fù)載服務(wù)器程序時(shí)，經(jīng)典的多線程模式和select模式都不再適用。
應(yīng)當(dāng)拋棄它們，采用epoll/kqueue/dev_poll來(lái)捕獲I/O事件。最后簡(jiǎn)要介紹了AIO。


由來(lái)


網(wǎng)絡(luò)服務(wù)在處理數(shù)以萬(wàn)計(jì)的客戶端連接時(shí)，往往出現(xiàn)效率低下甚至完全癱瘓，這被稱為
C10K問(wèn)題。隨著互聯(lián)網(wǎng)的迅速發(fā)展，越來(lái)越多的網(wǎng)絡(luò)服務(wù)開(kāi)始面臨C10K問(wèn)題，作為大型
網(wǎng)站的開(kāi)發(fā)人員有必要對(duì)C10K問(wèn)題有一定的了解。本文的主要參考文獻(xiàn)是
<http://www.kegel.com/c10k.html> http://www.kegel.com/c10k.htmls。

C10K問(wèn)題的最大特點(diǎn)是：設(shè)計(jì)不夠良好的程序，其性能和連接數(shù)及機(jī)器性能的關(guān)系往往
是非線性的。舉個(gè)例子：如果沒(méi)有考慮過(guò)C10K問(wèn)題，一個(gè)經(jīng)典的基于select的程序能在
舊服務(wù)器上很好處理1000并發(fā)的吞吐量，它在2倍性能新服務(wù)器上往往處理不了并發(fā)
2000的吞吐量。

這是因?yàn)樵诓呗圆划?dāng)時(shí)，大量操作的消耗和當(dāng)前連接數(shù)n成線性相關(guān)。會(huì)導(dǎo)致單個(gè)任務(wù)
的資源消耗和當(dāng)前連接數(shù)的關(guān)系會(huì)是O(n)。而服務(wù)程序需要同時(shí)對(duì)數(shù)以萬(wàn)計(jì)的socket進(jìn)
行I/O處理，積累下來(lái)的資源消耗會(huì)相當(dāng)可觀，這顯然會(huì)導(dǎo)致系統(tǒng)吞吐量不能和機(jī)器性
能匹配。為解決這個(gè)問(wèn)題，必須改變對(duì)連接提供服務(wù)的策略。


基本策略


主要有兩方面的策略：1.應(yīng)用軟件以何種方式和操作系統(tǒng)合作，獲取I/O事件并調(diào)度多
個(gè)socket上的I/O操作；2. 應(yīng)用軟件以何種方式處理任務(wù)和線程/進(jìn)程的關(guān)系。前者主
要有阻塞I/O、非阻塞I/O、異步I/O這3種方案，后者主要有每任務(wù)1進(jìn)程、每任務(wù)1線
程、單線程、多任務(wù)共享線程池以及一些更復(fù)雜的變種方案。常用的經(jīng)典策略如下：

1.         Serve one client with each thread/process, and use blocking I/O
這是小程序和java常用的策略，對(duì)于交互式的長(zhǎng)連接應(yīng)用也是常見(jiàn)的選擇(比如BBS)。
這種策略很能難足高性能程序的需求，好處是實(shí)現(xiàn)極其簡(jiǎn)單，容易嵌入復(fù)雜的交互邏
輯。Apache、ftpd等都是這種工作模式。

2.         Serve many clients with single thread, and use nonblocking I/O
and readiness notification
這是經(jīng)典模型，datapipe等程序都是如此實(shí)現(xiàn)的。優(yōu)點(diǎn)在于實(shí)現(xiàn)較簡(jiǎn)單，方便移植，也
能提供足夠的性能；缺點(diǎn)在于無(wú)法充分利用多CPU的機(jī)器。尤其是程序本身沒(méi)有復(fù)雜的
業(yè)務(wù)邏輯時(shí)。

3.         Serve many clients with each thread, and use nonblocking I/O and
readiness notification
對(duì)經(jīng)典模型2的簡(jiǎn)單改進(jìn)，缺點(diǎn)是容易在多線程并發(fā)上出bug，甚至某些OS不支持多線程
操作readiness notification。

4.         Serve many clients with each thread, and use asynchronous I/O
在有AI/O支持的OS上，能提供相當(dāng)高的性能。不過(guò)AI/O編程模型和經(jīng)典模型差別相當(dāng)
大，基本上很難寫出一個(gè)框架同時(shí)支持AI/O和經(jīng)典模型，降低了程序的可移植性。在
Windows上，這基本上是唯一的可選方案。

本文主要討論模型2的細(xì)節(jié)，也就是在模型2下應(yīng)用軟件如何處理Socket I/O。


select 與 poll


最原始的同步阻塞 I/O 模型的典型流程如下：

同步阻塞 I/O 模型的典型流程

從應(yīng)用程序的角度來(lái)說(shuō)，read 調(diào)用會(huì)延續(xù)很長(zhǎng)時(shí)間，應(yīng)用程序需要相當(dāng)多線程來(lái)解決
并發(fā)訪問(wèn)問(wèn)題。同步非阻塞I/O對(duì)此有所改進(jìn)：

經(jīng)典的單線程服務(wù)器程序結(jié)構(gòu)往往如下：


do {

         Get Readiness Notification of all sockets

         Dispatch ready handles to corresponding handlers

                   If (readable) {
                            read the socket

                            If (read done)

                                     Handler process the request
                   }

                   if (writable)

                            write response

                   if (nothing to do)

                            close socket

} while(True)

非阻塞 I/O 模型的典型流程:

異步阻塞 I/O 模型的典型流程

其中關(guān)鍵的部分是readiness notification，找出哪一個(gè)socket上面發(fā)生了I/O事件。
一般從教科書和例子程序中首先學(xué)到的是用select來(lái)實(shí)現(xiàn)。Select定義如下：


int select(int n, fd_set *rd_fds, fd_set *wr_fds, fd_set *ex_fds, struct
timeval *timeout);

Select用到了fd_set結(jié)構(gòu)，從man page里可以知道fd_set能容納的句柄和FD_SETSIZE相
關(guān)。實(shí)際上fd_set在*nix下是一個(gè)bit標(biāo)志數(shù)組，每個(gè)bit表示對(duì)應(yīng)下標(biāo)的fd是不是在
fd_set中。fd_set只能容納編號(hào)小于 FD_SETSIZE的那些句柄。

FD_SETSIZE默認(rèn)是1024，如果向fd_set里放入過(guò)大的句柄，數(shù)組越界以后程序就會(huì)垮
掉。系統(tǒng)默認(rèn)限制了一個(gè)進(jìn)程最大的句柄號(hào)不超過(guò)1024，但是可以通過(guò)ulimit -n命令
/setrlimit函數(shù)來(lái)擴(kuò)大這一限制。如果不幸一個(gè)程序在FD_SETSIZE=1024的環(huán)境下編
譯，運(yùn)行時(shí)又遇到ulimit –n > 1024的，那就只有祈求上帝保佑不會(huì)垮掉了。

在ACE環(huán)境中，ACE_Select_Reactor針對(duì)這一點(diǎn)特別作了保護(hù)措施，但是還是有recv_n
這樣的函數(shù)間接的使用了select，這需要大家注意。

針對(duì)fd_set的問(wèn)題，*nix提供了poll函數(shù)作為select的一個(gè)替代品。Poll的接口如下：


int poll(struct pollfd *ufds, unsigned int nfds, int timeout);

第1個(gè)參數(shù)ufds是用戶提供的一個(gè)pollfd數(shù)組，數(shù)組大小由用戶自行決定，因此避免了
FD_SETSIZE帶來(lái)的麻煩。Ufds是fd_set的一個(gè)完全替代品，從select到poll的移植很方
便。到此為止，至少我們面對(duì)C10K，可以寫出一個(gè)能work的程序了。

然而Select和Poll在連接數(shù)增加時(shí)，性能急劇下降。這有兩方面的原因：首先操作系統(tǒng)
面對(duì)每次的select/poll操作，都需要重新建立一個(gè)當(dāng)前線程的關(guān)心事件列表，并把線
程掛在這個(gè)復(fù)雜的等待隊(duì)列上，這是相當(dāng)耗時(shí)的。其次，應(yīng)用軟件在select/poll返回
后也需要對(duì)傳入的句柄列表做一次掃描來(lái)dispatch，這也是很耗時(shí)的。這兩件事都是和
并發(fā)數(shù)相關(guān)，而I/O事件的密度也和并發(fā)數(shù)相關(guān)，導(dǎo)致CPU占用率和并發(fā)數(shù)近似成O(n2)
的關(guān)系。


epoll, kqueue, /dev/poll


因?yàn)橐陨系脑颍?nix的hacker們開(kāi)發(fā)了epoll, kqueue, /dev/poll這3套利器來(lái)幫助
大家，讓我們跪拜三分鐘來(lái)感謝這些大神。其中epoll是linux的方案，kqueue是
freebsd的方案，/dev/poll是最古老的Solaris的方案，使用難度依次遞增。

簡(jiǎn)單的說(shuō)，這些api做了兩件事：1.避免了每次調(diào)用select/poll時(shí)kernel分析參數(shù)建立
事件等待結(jié)構(gòu)的開(kāi)銷，kernel維護(hù)一個(gè)長(zhǎng)期的事件關(guān)注列表，應(yīng)用程序通過(guò)句柄修改這
個(gè)列表和捕獲I/O事件。2.避免了select/poll返回后，應(yīng)用程序掃描整個(gè)句柄表的開(kāi)
銷，Kernel直接返回具體的事件列表給應(yīng)用程序。

在接觸具體api之前，先了解一下邊緣觸發(fā)(edge trigger)和條件觸發(fā)(level trigger)
的概念。邊緣觸發(fā)是指每當(dāng)狀態(tài)變化時(shí)發(fā)生一個(gè)io事件，條件觸發(fā)是只要滿足條件就發(fā)
生一個(gè)io事件。舉個(gè)讀socket的例子，假定經(jīng)過(guò)長(zhǎng)時(shí)間的沉默后，現(xiàn)在來(lái)了100個(gè)字
節(jié)，這時(shí)無(wú)論邊緣觸發(fā)和條件觸發(fā)都會(huì)產(chǎn)生一個(gè)read ready notification通知應(yīng)用程
序可讀。應(yīng)用程序讀了50個(gè)字節(jié)，然后重新調(diào)用api等待io事件。這時(shí)條件觸發(fā)的api會(huì)
因?yàn)檫€有50個(gè)字節(jié)可讀從而立即返回用戶一個(gè)read ready notification。而邊緣觸發(fā)
的api會(huì)因?yàn)榭勺x這個(gè)狀態(tài)沒(méi)有發(fā)生變化而陷入長(zhǎng)期等待。

因此在使用邊緣觸發(fā)的api時(shí)，要注意每次都要讀到socket返回EWOULDBLOCK為止，否則
這個(gè)socket就算廢了。而使用條件觸發(fā)的api時(shí)，如果應(yīng)用程序不需要寫就不要關(guān)注
socket可寫的事件，否則就會(huì)無(wú)限次的立即返回一個(gè)write ready notification。大家
常用的select就是屬于條件觸發(fā)這一類，以前本人就犯過(guò)長(zhǎng)期關(guān)注socket寫事件從而
CPU 100%的毛病。

epoll的相關(guān)調(diào)用如下：


int epoll_create(int size)


int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)


int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int
timeout)

epoll_create創(chuàng)建kernel中的關(guān)注事件表，相當(dāng)于創(chuàng)建fd_set。

epoll_ctl修改這個(gè)表，相當(dāng)于FD_SET等操作

epoll_wait等待I/O事件發(fā)生，相當(dāng)于select/poll函數(shù)

epoll完全是select/poll的升級(jí)版，支持的事件完全一致。并且epoll同時(shí)支持邊緣觸
發(fā)和條件觸發(fā)，一般來(lái)講邊緣觸發(fā)的性能要好一些。這里有個(gè)簡(jiǎn)單的例子：


struct epoll_event ev, *events;

int kdpfd = epoll_create(100);

ev.events = EPOLLIN | EPOLLET;  // 注意這個(gè)EPOLLET，指定了邊緣觸發(fā)

ev.data.fd =listener;

epoll_ctl(kdpfd, EPOLL_CTL_ADD, listener, &ev);

for(;;) {

   nfds = epoll_wait(kdpfd, events, maxevents, -1);

 

   for(n = 0; n < nfds; ++n) {

       if(events[n].data.fd == listener) {

           client = accept(listener, (struct sockaddr *) &local,

                           &addrlen);

           if(client < 0){

               perror("accept");

               continue;

           }

           setnonblocking(client);

           ev.events = EPOLLIN | EPOLLET;

           ev.data.fd = client;

           if (epoll_ctl(kdpfd, EPOLL_CTL_ADD, client, &ev) < 0) {

               fprintf(stderr, "epoll set insertion error: fd=%d0,

                       client);

               return -1;

           }

       }

       else

           do_use_fd(events[n].data.fd);

   }

}

簡(jiǎn)單介紹一下kqueue和/dev/poll

kqueue是freebsd的寵兒，kqueue實(shí)際上是一個(gè)功能相當(dāng)豐富的kernel事件隊(duì)列，它不
僅僅是select/poll的升級(jí)，而且可以處理signal、目錄結(jié)構(gòu)變化、進(jìn)程等多種事件。
Kqueue是邊緣觸發(fā)的

/dev/poll是Solaris的產(chǎn)物，是這一系列高性能API中最早出現(xiàn)的。Kernel提供一個(gè)特
殊的設(shè)備文件/dev/poll。應(yīng)用程序打開(kāi)這個(gè)文件得到操縱fd_set的句柄，通過(guò)寫入
pollfd來(lái)修改它，一個(gè)特殊ioctl調(diào)用用來(lái)替換select。由于出現(xiàn)的年代比較早，所以
/dev/poll的接口現(xiàn)在看上去比較笨拙可笑。

C++開(kāi)發(fā)：ACE 5.5以上版本提供了ACE_Dev_Poll_Reactor封裝了epoll和/dev/poll兩種
api，需要分別在config.h中定義ACE_HAS_EPOLL和ACE_HAS_DEV_POLL來(lái)啟用。

Java開(kāi)發(fā)： JDK 1.6的Selector提供了對(duì)epoll的支持，JDK1.4提供了對(duì)/dev/poll的支
持。只要選擇足夠高的JDK版本就行了。


異步I/O以及Windows


和經(jīng)典模型不同，異步I/O提供了另一種思路。和傳統(tǒng)的同步I/O不同，異步I/O允許進(jìn)
程發(fā)起很多 I/O 操作，而不用阻塞或等待任何操作完成。稍后或在接收到 I/O 操作完
成的通知時(shí)，進(jìn)程就可以檢索 I/O 操作的結(jié)果。

異步非阻塞 I/O 模型是一種處理與 I/O 重疊進(jìn)行的模型。讀請(qǐng)求會(huì)立即返回，說(shuō)明
read 請(qǐng)求已經(jīng)成功發(fā)起了。在后臺(tái)完成讀操作時(shí)，應(yīng)用程序然后會(huì)執(zhí)行其他處理操
作。當(dāng) read 的響應(yīng)到達(dá)時(shí)，就會(huì)產(chǎn)生一個(gè)信號(hào)或執(zhí)行一個(gè)基于線程的回調(diào)函數(shù)來(lái)完成
這次 I/O 處理過(guò)程。異步I/O 模型的典型流程：

異步非阻塞 I/O 模型的典型流程

對(duì)于文件操作而言，AIO有一個(gè)附帶的好處：應(yīng)用程序?qū)⒍鄠€(gè)細(xì)碎的磁盤請(qǐng)求并發(fā)的提
交給操作系統(tǒng)后，操作系統(tǒng)有機(jī)會(huì)對(duì)這些請(qǐng)求進(jìn)行合并和重新排序，這對(duì)同步調(diào)用而言
是不可能的——除非創(chuàng)建和請(qǐng)求數(shù)目同樣多的線程。

Linux Kernel 2.6提供了對(duì)AIO的有限支持——僅支持文件系統(tǒng)。libc也許能通過(guò)來(lái)線
程來(lái)模擬socket的AIO，不過(guò)這對(duì)性能沒(méi)意義。總的來(lái)說(shuō)Linux的aio還不成熟

Windows對(duì)AIO的支持很好，有IOCP隊(duì)列和IPCP回調(diào)兩種方式，甚至提供了用戶級(jí)異步調(diào)
用APC功能。Windows下AIO是唯一可用的高性能方案，詳情請(qǐng)參考MSDN 

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1537545