# 高效 Web 伺服器開發 :::info 本文探討 ==[seHTTPd](https://github.com/sysprog21/sehttpd)== 的設計和實作議題,涵蓋並行處理、I/O 模型、epoll、React pattern,和 Web 伺服器在事件驅動架構的考量。 ::: > 資料整理: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) ## TCP 伺服器的實作挑戰 一般來說,TCP 伺服器的流程是先 [listen](http://man7.org/linux/man-pages/man2/listen.2.html) 於某個 port,呼叫 [accept](http://man7.org/linux/man-pages/man2/accept.2.html) 等待客戶端的連線,等客戶端連線後會返回一個 fd (file descriptor),自指定 fd 進行 [read](http://man7.org/linux/man-pages/man2/read.2.html),以 TCP echo 來說,對應的處置方式即 [write](http://man7.org/linux/man-pages/man2/read.2.html) 同樣的資料到該 fd,然後重新 [accept](http://man7.org/linux/man-pages/man2/accept.2.html),關鍵程式碼如下: ```cpp /* 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](http://www.paulgriffiths.net/program/c/srcs/echoservsrc.html) 理解這個 echo 伺服器後,即可在其上擴展為 web 伺服器 —— HTTP 建構於 TCP 之上,會有通訊協定的解析和處理。[CS:APP](https://hackmd.io/@sysprog/CSAPP) 提供 [tiny.c](http://csapp.cs.cmu.edu/public/ics2/code/netp/tiny/tiny.c) 來服務靜態和動態內容,儘管效益不彰,但已達到教學的目的。雖然這個程式能正常工作,但它無法勝任廣泛的應用,原因是伺服器在處理一個客戶端請求時,無法受理別的客戶端請求,也就是說,這個程式無法同時滿足兩個想獲得 echo 服務的使用者,這自然是極大的限制。 其中一項改進的解決方案:[accept](http://man7.org/linux/man-pages/man2/accept.2.html) 之後再進行 [fork](http://man7.org/linux/man-pages/man2/fork.2.html),父行程 (parent process) 繼續 [accept](http://man7.org/linux/man-pages/man2/accept.2.html),子行程 (child process) 則處理該 fd,對應的程式碼如下: ```cpp 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; } ``` > [完整程式碼](https://jameshfisher.com/2017/02/25/tcp-server-fork/) 乍看這個程式解決上述只能服務單一客戶端請求的問題,但基於以下幾個因素,仍無法滿足效能需求: * 每個網路連線都涉及 [fork](http://man7.org/linux/man-pages/man2/fork.2.html),開銷大:定址空間是 copy-on-write (CoW),因此初期開銷不大,但仍有複製父行程 page table 的操作,而執行緒卻可分享同一個 page table。 * 行程間的排程器承受的壓力大:考慮到系統因大量連線而有成千上萬個行程,排程器勢必要耗費時間於挑選出下一個欲執行的行程,及進行 context switch,整體開銷可觀,可參見《[A Design Framework for Highly Concurrent Systems](https://people.eecs.berkeley.edu/~culler/papers/events.pdf)》的分析。 * 在負載沈重的狀況下,行程易於消耗大量的記憶體資源:每個網路連線對應一個獨立的定址空間,即使在執行緒的狀況下,每個連線也會佔用資源。此外,[fork](http://man7.org/linux/man-pages/man2/fork.2.html) 後 parent-child 行程之間需要 IPC,這也是成本。 改用執行緒雖可克服 [fork](http://man7.org/linux/man-pages/man2/fork.2.html) 開銷的問題,但排程器和記憶體開銷仍無法解決。單純行程和執行緒的模型在本質相似,被歸類於 process-per-connection model,無法滿足高並行 (concurrency) 需求。 可引入 [thread pool](https://en.wikipedia.org/wiki/Thread_pool):事先建立數量固定的執行緒,依據需求分配任務到這些執行緒,免去 TCP 伺服器在服務客戶端請求時,需要重新建立執行緒的疑慮。引入 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 後,TCP 伺服器的基本架構是,主要的循環 (main loop) 用 [accept](http://man7.org/linux/man-pages/man2/accept.2.html) 網路連線,之後將該連線分配給 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 的某個執行緒,處理後這個執行緒又可處理別的網路連線。 > 延伸閱讀: [圖解 Go 執行時期排程器](https://tonybai.com/2020/03/21/illustrated-tales-of-go-runtime-scheduler/) ![](https://i.imgur.com/bhsp5jC.png) 乍看 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 是個理想的方案,但在真實情況中,很多連線都要長時間處理 (longer keep alive time,即在一個 TCP 連線中進行多次通訊),一個執行緒收到任務後,處理完第一批來的資料,此時會再次呼叫 [read](http://man7.org/linux/man-pages/man2/read.2.html),但卻無法確認對方何時發送新資料,於是該執行緒就被這個 [read](http://man7.org/linux/man-pages/man2/read.2.html) 給阻塞 (blocked) 住了,這也是預設 I/O 操作的模式 —— 即便該 fd 沒有任何資料,呼叫 [read](http://man7.org/linux/man-pages/man2/read.2.html) 仍會致使行程的 blocking。於是,在 [thread pool](https://en.wikipedia.org/wiki/Thread_pool) 上若有 $n$ 個執行緒,只要遇上第 $n + 1$ 個長時間的連線,系統仍無法滿足並行需求。 不難發現問題的根源是 [read](http://man7.org/linux/man-pages/man2/read.2.html) 預設行為致使的 blocking,解法是將後者該換為 non-blocking I/O。[read](http://man7.org/linux/man-pages/man2/read.2.html) 的做法是若有資料則返回資料,如果沒有可讀資料就返回 `-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)](http://man7.org/linux/man-pages/man2/open.2.html) for further details on the `O_NONBLOCK` flag. 很快我們發現新問題:行程如何得知這個 fd 在何時有資料可讀取呢?這就要透過事件驅動 (event-driven) 模型來克服。 ## I/O 事件模型 ![](https://i.imgur.com/uXPFiNs.png) > blocking I/O ![](https://i.imgur.com/c77Sx0q.png) > I/O Multiplexing > source: [I/O Multiplexing](http://www.cs.toronto.edu/~krueger/csc209h/f05/lectures/Week11-Select.pdf) - Blocking / Non-blocking I/O:在等待 I/O 資料**準備就緒** (e.g. **有資料可以讀取**) 的過程,使用者層級的行程是否會被 **blocked**。 - Blocking I/O:在等待 I/O 資料準備就緒的過程,使用者層級的行程會被 blocked。 - e.g. 未設定 **O_NONBLOCK** 的 [read](http://man7.org/linux/man-pages/man2/read.2.html), [select](http://man7.org/linux/man-pages/man2/select.2.html), [epoll](http://man7.org/linux/man-pages/man7/epoll.7.html) - Non-blocking I/O:在向核心詢問是否可進行 I/O 操作的過程,不論 I/O 資料是否準備就緒,使用者層級的行程都不會被 blocked。若 I/O 資料尚未準備就緒 (e.g. 尚無資料可讀取),則會直接返回,並設定 `errno` 指明錯誤 (e.g. `EAGAIN`、`EWOULDBLOCK`)。使用者層級的行程必須重複詢問 (e.g. 在 `while` 迴圈中重複呼叫 [read](http://man7.org/linux/man-pages/man2/read.2.html)) 直到 I/O 資料準備就緒才可進行 I/O operation。 - e.g. 設定 **O_NONBLOCK** 的 [read](http://man7.org/linux/man-pages/man2/read.2.html), `aio_read()`, `aio_write()` - Synchronous / Asynchronous I/O:在從/向核心空間讀取/寫入資料 (i.e. **實際進行 I/O 操作**) 的過程,使用者層級的行程是否會被 **blocked**。 - Synchronous I/O:從/向核心空間讀取/寫入資料 的過程,使用者層級的行程會被 blocked - e.g. [read](http://man7.org/linux/man-pages/man2/read.2.html), [recvfrom](http://man7.org/linux/man-pages/man2/recv.2.html) - Asynchronous I/O:從/向核心空間讀取/寫入的過程交由核心內部處理。核心複製完資料後,再通知使用者層級的行程。這中間使用者層級的行程不會被 blocked。 - e.g. `aio_read()`, `aio_write()` 延伸閱讀: [I/O Models 中文解說](https://rickhw.github.io/2019/02/27/ComputerScience/IO-Models/) ### I/O Multiplexing ```cpp int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); ``` [select](http://man7.org/linux/man-pages/man2/select.2.html) 搭配 [read](http://man7.org/linux/man-pages/man2/read.2.html) 可實作出 I/O multiplexing 機制,而 I/O multiplexing 其實是 Blocking I/O 的延伸,但 `select()` + `read()` 相較單一 [read](http://man7.org/linux/man-pages/man2/read.2.html) 的優勢是 `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 系列系統呼叫 關於 `epoll` 系列 API (注意: epoll 不是單一 Linux 系統呼叫),可參見 [The method to epoll’s madness](https://medium.com/@copyconstruct/the-method-to-epolls-madness-d9d2d6378642) 一文說明。 > select/poll 的時間複雜度是 $O(n)$,而 epoll 的時間複雜度是 $O(1)$ ```cpp int epoll_create(int size); ``` [epoll_create](http://man7.org/linux/man-pages/man2/epoll_create.2.html) 系統呼叫回傳指向在 Linux 核心新建的 epoll 資料結構對應的 fd,使用該系統呼叫的行程可透過該 fd,進行新增、刪除,和變更其他的想要監視的 fd。自 Linux `v2.6.8` 起,該系統呼叫的參數已被忽視,但考量到相容性,該參數仍要大於 `0`。 ![](https://i.imgur.com/sHHIdRk.png) 摘自 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. ```cpp int epoll_create1(int flags); ``` [epoll_create1](http://man7.org/linux/man-pages/man2/epoll_create.2.html) 系統呼叫的參數: * `0`: 表現如同 [epoll_create](http://man7.org/linux/man-pages/man2/epoll_create.2.html) * `EPOLL_CLOEXEC`: 透過 fork 自現有行程分出的子行程,將在行程執行前,關閉 epoll fd,換言之,子行程無法存取父行程設定的 epoll 資源。 ```cpp int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); ``` [epoll_ctl](http://man7.org/linux/man-pages/man2/epoll_ctl.2.html) ![](https://i.imgur.com/wnI4Gsp.png) > All the file descriptors registered with an epoll instance are collectively called an epoll set or the interest list. ready list 是 interest list 的子集合: ![](https://i.imgur.com/AY4LioQ.png) 下述三種操作: * Add/Register fd with the epoll instance (EPOLL_CTL_ADD) and get notified about events that occur on fd * Delete/deregister fd from the epoll instance. This would mean that the process would no longer get any notifications about events on that file descriptor (EPOLL_CTL_DEL). If a file descriptor has been added to multiple epoll instances, then closing it will remove it from all of the epoll interest lists to which it was added. * Modify the events fd is monitoring (EPOLL_CTL_MOD) ![](https://i.imgur.com/E8EWgJ4.png) ## Reactor Pattern 同步的事件循環搭配 non-blocking I/O 又稱為 [Reactor pattern](http://en.wikipedia.org/wiki/Reactor_pattern)。 ![](https://i.imgur.com/tmGVoO1.jpg) 事件循環用來通知特定事件,若 listenfd 可讀取,則呼叫 [accept](http://man7.org/linux/man-pages/man2/accept.2.html),把新建立的 fd 加入 epoll 中;若是普通的連線 fd,將其加入到一個生產者與消費者佇列中,讓 worker thread 取用。thread pool 用來做計算,從一個生產者與消費者佇列裡領取一個 fd 作為計算輸入,直到讀到 `EAGAIN` 為止,保存現在的處理狀態(狀態機),等待事件循環,直到這個 fd 讀寫事件的下一次通知。 [Reactor pattern](http://en.wikipedia.org/wiki/Reactor_pattern) 是個設計模式 (design pattern),針對同時處理多個或單個服務需求。服務處理任務 (service handler) 將傳入的需求拆解,然後分派給相關的請求端處理任務 (request handler)。 再來思考為何需要 [Reactor pattern](http://en.wikipedia.org/wiki/Reactor_pattern)。考慮這樣的情境:web 應用程式收到請求,處理過後接著要讀取資料或是將資料寫入到資料庫,中間勢必要等待其他功能模組或程式進行,延遲的時間可能數十毫秒或更長,但原本的 web 應用程式就處於等待的狀態,也就是不做事情,但 CPU 佔用率仍居高不下,因為行程處理資料庫的存取、檔案的 I/O 或者是跟其他服務的**溝通之間的等待**都存在可觀成本。在 Reactor Pattern 中有個單執行緒的事件循環 (event loop),不停地循環等待新事件的發生,事件處理的過程中如有Blocking I/O 的產生,會使用 **defer** 手段,將動作轉包到事件循環以外的其他執行緒,從而讓等待資料庫讀取的狀況發生在另外一個執行緒,這樣的好處很明顯 —— 主要的事件循環不會發生 blocking,並可繼續服務下一個事件,等待資料庫讀取完畢、資料回傳後,再透過預先設定的 callback,將資料傳回主要事件循環中,自此繼續受理各項請求。 ## 實作考量點 :question: 若將 fd 放入生產者與消費者佇列後,拿到這個任務的 worker thread 尚未讀完這個 fd,因為沒讀取完資料,所以這個 fd 可讀,那麼下一次事件循環又返回這個 fd,還分配給其他的執行緒,該如何處理? :thinking_face: 要從 `epoll` 的兩種工作模式談起: 1. Edge Triggered (ET, 邊緣觸發) 2. Level Triggered (LT, 條件觸發) ![](https://i.imgur.com/U5MvTC2.png) ET 表示在狀態改變時才通知(例如: 在邊緣上從低電位到高電位),LT 表示在這個狀態才通知(例如: 只要處於低電位就通知)。對應到 epoll,ET 指一旦有新資料就通知(狀態的改變),而 LT 是「只要有新資料」就會持續通知,直到緩衝區的資料全數取出。 舉例來說,若某 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](https://github.com/Manistein/test_epoll_lt_and_et) :question: 如果某個執行緒在處理 fd 的同時,又有新的一批資料進來,該 fd 可讀(注意和上一題的區別:一個是處理同一批資料,另一個是處理新一批資料),那麼該 fd 會被分配另一個執行緒,這樣兩個執行緒處理同一個 fd 就會導致錯亂。 :thinking_face: 設定 `EPOLLONESHOT` 可解決這個問題。在 fd 回傳可讀後,需要另行設定,才能讓 epoll 重新回傳這個 fd。 :question: 當 Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下,遇到 (1) 網頁瀏覽器突然關閉; (2) 客戶端網路離線; 這兩種狀況,伺服器該如何處理? :thinking_face: 分兩種狀況處理: 1. 此時該 fd 在事件循環裡會回傳一個可讀事件,然後分配給某個執行緒,該執行緒 read 會回傳 `0`,代表對方已關閉這個 fd,於是伺服器端呼叫 close 即可; 2. 通訊協定無法立刻知悉,所以僅能透過伺服器引入 timer 逾時事件來克服 timer 可透過 priority queue 實作,後者又常用 binary heap 實作,可參見以下: * [Priority Queue 簡介](https://alrightchiu.github.io/SecondRound/priority-queueintrojian-jie.html) * [Priority Queue:Binary Heap](https://alrightchiu.github.io/SecondRound/priority-queuebinary-heap.html) :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 的時候也維護一個狀態機。 ## 參考資訊 * [Concurrent HTTP Server with Epoll](https://kaleid-liner.github.io/blog/2019/06/02/epoll-web-server.html) * [fancy: A high performance web server](https://github.com/guangqianpeng/fancy) * [poll vs select vs event-based](https://daniel.haxx.se/docs/poll-vs-select.html) * [Async IO on Linux: select, poll, and epoll](https://jvns.ca/blog/2017/06/03/async-io-on-linux--select--poll--and-epoll/)