資料整理: jserv
本文探討 seHTTPd 的設計和實作議題,涵蓋並行處理、I/O 模型、epoll、React pattern,和 Web 伺服器在事件驅動架構的考量。
一般來說,TCP 伺服器的流程是先 listen 於某個 port,呼叫 accept 等待客戶端的連線,等客戶端連線後會返回一個 fd (file descriptor),自指定 fd 進行 read,以 TCP echo 來說,對應的處置方式即 write 同樣的資料到該 fd,然後重新 accept,關鍵程式碼如下:
/* Enter an infinite loop to respond to client requests */
while (1) {
/* Wait for a connection, then accept() it */
if ((conn_s = accept(list_s, NULL, NULL)) < 0) exit(EXIT_FAILURE);
/* Retrieve an input line from the connected socket */
for (size_t n = 1; n < MAX_LINE - 1; n++) {
ssize_t rc;
char c;
if ((rc = read(conn_s, &c, 1)) == 1) {
*buffer++ = c;
if (c == '\n') break;
} else if (rc == 0) break;
else {
if (errno == EINTR) continue;
break;
}
}
*buffer = 0;
/* simply write it back to the same socket */
size_t nleft = strlen(buffer);
while (nleft > 0) {
ssize_t nwritten;
if ((nwritten = write(conn_s, buffer, nleft)) <= 0) {
if (errno == EINTR) nwritten = 0;
break;
}
nleft -= nwritten;
buffer += nwritten;
}
/* Close the connected socket */
if (close(conn_s) < 0) exit(EXIT_FAILURE);
}
完整程式碼可見 echoserv
理解這個 echo 伺服器後,即可在其上擴展為 web 伺服器 —— HTTP 建構於 TCP 之上,會有通訊協定的解析和處理。CS:APP 提供 tiny.c 來服務靜態和動態內容,儘管效益不彰,但已達到教學的目的。雖然這個程式能正常工作,但它無法勝任廣泛的應用,原因是伺服器在處理一個客戶端請求時,無法受理別的客戶端請求,也就是說,這個程式無法同時滿足兩個想獲得 echo 服務的使用者,這自然是極大的限制。
其中一項改進的解決方案:accept 之後再進行 fork,父行程 (parent process) 繼續 accept,子行程 (child process) 則處理該 fd,對應的程式碼如下:
int guard(int n, char *err) {
if (n == -1) { perror(err); exit(1); }
return n;
}
int main(void) {
int listen_fd = guard(socket(PF_INET, SOCK_STREAM, 0),
"Could not create TCP socket");
guard(listen(listen_fd, 100), "Could not listen on TCP socket");
struct sockaddr_in listen_addr;
socklen_t addr_len = sizeof(listen_addr);
guard(getsockname(listen_fd, (struct sockaddr *) &listen_addr, &addr_len),
"Could not get socket name");
for (;;) {
int conn_fd = accept(listen_fd, NULL, NULL);
if (guard(fork(), "Could not fork") == 0) {
char buf[100];
for (;;) {
ssize_t nreceived = guard(recv(conn_fd, buf, sizeof(buf), 0),
"Could not recv on TCP connection");
if (nreceived == 0) {
guard(shutdown(conn_fd, SHUT_WR),
"Could not shutdown TCP connection");
guard(close(conn_fd),
"Could not close TCP connection");
exit(0);
}
guard(send(conn_fd, buf, nreceived, 0),
"Could not send to TCP connection");
}
} else {
/* Child takes over connection; close it in parent */
close(conn_fd);
}
}
return 0;
}
乍看這個程式解決上述只能服務單一客戶端請求的問題,但基於以下幾個因素,仍無法滿足效能需求:
改用執行緒雖可克服 fork 開銷的問題,但排程器和記憶體開銷仍無法解決。單純行程和執行緒的模型在本質相似,被歸類於 process-per-connection model,無法滿足高並行 (concurrency) 需求。
可引入 thread pool:事先建立數量固定的執行緒,依據需求分配任務到這些執行緒,免去 TCP 伺服器在服務客戶端請求時,需要重新建立執行緒的疑慮。引入 thread pool 後,TCP 伺服器的基本架構是,主要的循環 (main loop) 用 accept 網路連線,之後將該連線分配給 thread pool 的某個執行緒,處理後這個執行緒又可處理別的網路連線。
延伸閱讀: 圖解 Go 執行時期排程器
乍看 thread pool 是個理想的方案,但在真實情況中,很多連線都要長時間處理 (longer keep alive time,即在一個 TCP 連線中進行多次通訊),一個執行緒收到任務後,處理完第一批來的資料,此時會再次呼叫 read,但卻無法確認對方何時發送新資料,於是該執行緒就被這個 read 給阻塞 (blocked) 住了,這也是預設 I/O 操作的模式 —— 即便該 fd 沒有任何資料,呼叫 read 仍會致使行程的 blocking。於是,在 thread pool 上若有
不難發現問題的根源是 read 預設行為致使的 blocking,解法是將後者該換為 non-blocking I/O。read 的做法是若有資料則返回資料,如果沒有可讀資料就返回 -1
並設定 errno 為 EAGAIN
,後者表明下次有資料再繼續處理。
EAGAIN
The file descriptor fd refers to a file other than a socket and has been marked nonblocking (O_NONBLOCK
), and the read would block. See open(2) for further details on theO_NONBLOCK
flag.
很快我們發現新問題:行程如何得知這個 fd 在何時有資料可讀取呢?這就要透過事件驅動 (event-driven) 模型來克服。
探討 I/O 事件模型前,我們應當理解雙工 (duplex) 的概念,亦即二台通訊裝置之間如何進行雙向的資料傳輸,可區分為:
1969 年 UNIX 剛被創造時,其 shell/tty 是不折不扣的半雙工 I/O: 對終端機進行寫入和讀取,不可同時進行,這並非不合理的限制,畢竟當時的作業系統的使用者 (且為專業人士) 主要對電腦下命令:
換句話說,機器不能在使用者輸入命令前,提前輸出結果,這樣只要半雙工即可。但考慮另一個情境,由接線生負責操作多電話線的插線接通,依據發話端的要求將電話線接到其他線路,從而達成電話中繼 (relay):
依據 UNIX 檔案操作的特性,若一個 file descriptor (以下簡稱 fd
) 表示的檔案沒有資料可讀取,那麼讀取檔案的操作將會 blocked (阻塞),傳話中繼接線生就不知道 N 個終端機裡頭到底有哪個終端機可讀取,於是乎,任意讀取一個終端機就會造成行程的阻塞。
假設終端機編號 1
的資料在 2 分鐘後才會到來,中繼接線生不巧讓行程去讀終端機編號 1
,這會造成終端機編號 1
阻塞 2 分鐘。10 秒後,終端機編號 2 的資料到來,,然而此時行程已阻塞在終端機編號 1
,只能興嘆!
若要克服這窘境,中繼接線生需要一個指示:
「告訴我哪個終端機有資料可讀!」
4.2BSD 提供 select 系統呼叫,恰到好處地解決問題:檢查所有 N 個終端機,回傳有資料可讀的終端機列表。若無任何終端機有資料可讀,select 將會阻塞,反之,只要有任何終端機有資料可讀,select 就會返回原本的程式。
於是,select 成為全雙工的 fd 操作,並鞏固 UNIX 設計哲學 "Everything is a file",這也是為何單一行程可服務多個網連線,因為透過 select 可得知哪一組資料可處理。
blocking I/O
I/O Multiplexing
source: I/O Multiplexing
errno
指明錯誤 (e.g. EAGAIN
、EWOULDBLOCK
)。使用者層級的行程必須重複詢問 (e.g. 在 while
迴圈中重複呼叫 read) 直到 I/O 資料準備就緒才可進行 I/O operation。
aio_read()
, aio_write()
延伸閱讀: I/O Models 中文解說
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
select 搭配 read 可實作出 I/O multiplexing 機制,而 I/O multiplexing 其實是 Blocking I/O 的延伸,但 select()
+ read()
相較單一 read 的優勢是 select()
可同時等待多個 file descriptors
(fd
)。若 I/O multiplexing 要處理的連線數量過少,可能會因內部處理較複雜,致使更高的延遲。在 4.2BSD 提出 select 系統呼叫時,I/O multiplexing 並非著眼於提高單一連線的速度,而是可在只使用單一行程或執行緒狀況下,監視或處理更多的連線。
呼叫 select()
時所傳入的是多個 fd set
,而非只是一個 fd
。只要 fd set
中任一個以上的 fd
的 I/O 資料準備就緒,select()
就會返回。呼叫 select()
的行程必須走訪 fd set
來檢查是哪幾個 fd
可以進行 I/O 操作,爾後再呼叫 read()
、recvfrom()
讀取資料。此時 I/O 資料應準備就緒,可直接讀取。但也有例外,e.g. select()
man page 所述:
Under Linux, select() may report a socket file descriptor as "ready for reading", while nevertheless a subsequent read blocks. This could for example happen when data has arrived but upon examination has wrong checksum and is discarded. There may be other circumstances in which a file descriptor is spuriously reported as ready. Thus it may be safer to use O_NONBLOCK on sockets that should not block.
select()
後的 read()
、recvfrom()
是 Blocking I/O 或是 Non-blocking I/O,取決於設定 O_NONBLOCK 與否。將 read() 或 recvfrom() 設為 NON_BLOCKING 才可避免使用者層級的行程再次被 blocked。
由於 select()
最多只可同時監控 (watch) 1024
個 fd
,且當返回時,使用者層級仍要走訪整個 fd set
,才可知道是哪些 fd
的資料已準備好,存在性能疑慮,因此才有後續的 epoll()
。
關於 epoll
系列 API (注意: epoll 不是單一 Linux 系統呼叫),可參見 The method to epoll’s madness 一文說明。
select/poll 的時間複雜度是
,而 epoll 的時間複雜度是
int epoll_create(int size);
epoll_create 系統呼叫回傳指向在 Linux 核心新建的 epoll 資料結構對應的 fd,使用該系統呼叫的行程可透過該 fd,進行新增、刪除,和變更其他的想要監視的 fd。自 Linux v2.6.8
起,該系統呼叫的參數已被忽視,但考量到相容性,該參數仍要大於 0
。
摘自 man page:
In the initial epoll_create() implementation, the size argument informed the kernel of the number of file descriptors that the caller expected to add to the epoll instance. The kernel used this information as a hint for the amount of space to initially allocate in internal data structures describing events. (If necessary, the kernel would allocate more space if the caller's usage exceeded the hint given in size.) Nowadays, this hint is no longer required (the kernel dynamically sizes the required data structures without needing the hint), but size must still be greater than zero, in order to ensure backward compatibility when new epoll applications are run on older kernels.
int epoll_create1(int flags);
epoll_create1 系統呼叫的參數:
0
: 表現如同 epoll_createEPOLL_CLOEXEC
: 透過 fork 自現有行程分出的子行程,將在行程執行前,關閉 epoll fd,換言之,子行程無法存取父行程設定的 epoll 資源。int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
All the file descriptors registered with an epoll instance are collectively called an epoll set or the interest list.
ready list 是 interest list 的子集合:
下述三種操作:
同步的事件循環搭配 non-blocking I/O 又稱為 Reactor pattern。
事件循環用來通知特定事件,若 listenfd 可讀取,則呼叫 accept,把新建立的 fd 加入 epoll 中;若是普通的連線 fd,將其加入到一個生產者與消費者佇列中,讓 worker thread 取用。thread pool 用來做計算,從一個生產者與消費者佇列裡領取一個 fd 作為計算輸入,直到讀到 EAGAIN
為止,保存現在的處理狀態(狀態機),等待事件循環,直到這個 fd 讀寫事件的下一次通知。
Reactor pattern 是個設計模式 (design pattern),針對同時處理多個或單個服務需求。服務處理任務 (service handler) 將傳入的需求拆解,然後分派給相關的請求端處理任務 (request handler)。
再來思考為何需要 Reactor pattern。考慮這樣的情境:web 應用程式收到請求,處理過後接著要讀取資料或是將資料寫入到資料庫,中間勢必要等待其他功能模組或程式進行,延遲的時間可能數十毫秒或更長,但原本的 web 應用程式就處於等待的狀態,也就是不做事情,但 CPU 佔用率仍居高不下,因為行程處理資料庫的存取、檔案的 I/O 或者是跟其他服務的溝通之間的等待都存在可觀成本。在 Reactor Pattern 中有個單執行緒的事件循環 (event loop),不停地循環等待新事件的發生,事件處理的過程中如有Blocking I/O 的產生,會使用 defer 手段,將動作轉包到事件循環以外的其他執行緒,從而讓等待資料庫讀取的狀況發生在另外一個執行緒,這樣的好處很明顯 —— 主要的事件循環不會發生 blocking,並可繼續服務下一個事件,等待資料庫讀取完畢、資料回傳後,再透過預先設定的 callback,將資料傳回主要事件循環中,自此繼續受理各項請求。
select 和 poll 屬於 level-triggered
Asynchronous I/O 則傾向 edge-triggered.
epoll
的兩種工作模式談起:
ET 表示在狀態改變時才通知(例如: 在邊緣上從低電位到高電位),LT 表示在這個狀態才通知(例如: 只要處於低電位就通知)。對應到 epoll,ET 指一旦有新資料就通知(狀態的改變),而 LT 是「只要有新資料」就會持續通知,直到緩衝區的資料全數取出。
:question: 若將 fd 放入生產者與消費者佇列後,拿到這個任務的 worker thread 尚未讀完這個 fd,因為沒讀取完資料,所以這個 fd 可讀,那麼下一次事件循環又返回這個 fd,還分配給其他的執行緒,該如何處理?
:thinking_face: 若某 fd 對應到 2 KiB 的資料,程式只讀取 1 KiB,ET 就不會在下次 epoll_wait
時返回,而是會在讀取結束後又有新資料之際才回傳。而 LT 每次都會回傳該 fd,只要該 fd 有資料可讀。所以我們要用 epoll 的 ET,把 fd 設為 O_NONBLOCK
,如果返回某 fd 可讀,循環 read 直到 EAGAIN
(若 read 回傳 0
,則遠端關閉連線)。
實驗程式碼: test_epoll_lt_and_et
:question: 如果某個執行緒在處理 fd 的同時,又有新的一批資料進來,該 fd 可讀(注意和上一題的區別:一個是處理同一批資料,另一個是處理新一批資料),那麼該 fd 會被分配另一個執行緒,這樣兩個執行緒處理同一個 fd 就會導致錯亂。
:thinking_face: 設定 EPOLLONESHOT
可解決這個問題。在 fd 回傳可讀後,需要另行設定,才能讓 epoll 重新回傳這個 fd。
:question: 當 Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下,遇到 (1) 網頁瀏覽器突然關閉; (2) 客戶端網路離線; 這兩種狀況,伺服器該如何處理?
:thinking_face: 分兩種狀況處理:
0
,代表對方已關閉這個 fd,於是伺服器端呼叫 close 即可;timer 可透過 priority queue 實作,後者又常用 binary heap 實作,可參見以下:
:question: 將 fd 設定為 non-blocking 後,需要不斷地 read 直到回傳 -1
,errno 為 EAGAIN,然後等待下次 epoll_wait 回傳這個 fd 再繼續處理。這時就遇到了 blocking read 不曾遇到的問題:資料可能分批送達,於是在通訊協定解析到一半時,read 就回傳 -1
,所以我們必須將已讀到的資料保存下來,並維護其狀態,以表示是否仍需要資料。例如解析 HTTP Request Header 時,讀到 GET /index.html HTT
(注意:少一個 P
) 就結束,在 blocking I/O 裡只要繼續 read 就可處理,但在 nonblocking I/O,我們必須維護這個狀態,下一次必須讀到欠缺的 P
字元,否則 HTTP 通訊協定會遇上解析錯誤。
:thinking_face: 解法是維護一個狀態機,在解析 Request Header 時候對應一個狀態機,解析 Header Body 的時候也維護一個狀態機。