高效 Web 伺服器開發

資料整理: jserv

本文探討 seHTTPd 的設計和實作議題，涵蓋並行處理、I/O 模型、React pattern，和 Web 伺服器在事件驅動架構的考量。

TCP 伺服器的實作挑戰

一般來說，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，開銷大：定址空間是 copy-on-write (CoW)，因此初期開銷不大，但仍有複製親代行程 page table 的操作，而執行緒卻可分享同一個 page table。
• 行程間的排程器承受的壓力大：考慮到系統因大量連線而有成千上萬個行程，排程器勢必要耗費時間於挑選出下一個欲執行的行程，及進行 context switch，整體開銷可觀，可參見〈A Design Framework for Highly Concurrent Systems〉的分析。
• 在負載沈重的狀況下，行程易於消耗大量的記憶體資源：每個網路連線對應一個獨立的定址空間，即使在執行緒的狀況下，每個連線也會佔用資源。此外，fork 後 parent-child 行程之間需要 IPC，這也是成本。

改用執行緒雖可克服 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 上若有 $n$ 個執行緒，只要遇上第 $n+1$ 個長時間的連線，系統仍無法滿足並行需求。

不難發現問題的根源是 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 the O_NONBLOCK flag.

很快我們發現新問題：行程如何得知這個 fd 在何時有資料可讀取呢？這就要透過事件驅動 (event-driven) 模型來克服。

Reactor Pattern

同步的事件循環搭配 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，將資料傳回主要事件循環中，自此繼續受理各項請求。

Edge vs. Level Triggering

select 和 poll 屬於 level-triggered
Asynchronous I/O 則傾向 edge-triggered.

epoll 的兩種工作模式談起:

1. Edge Triggered (ET, 邊緣觸發)
2. Level Triggered (LT, 條件觸發)
   

ET 表示在狀態改變時才通知（例如: 在邊緣上從低電位到高電位），LT 表示在這個狀態才通知（例如: 只要處於低電位就通知)。對應到 epoll，ET 指一旦有新資料就通知（狀態的改變），而 LT 是「只要有新資料」就會持續通知，直到緩衝區的資料全數取出。

實作考量點

若將 fd 放入生產者與消費者佇列後，拿到這個任務的 worker thread 尚未讀完這個 fd，因為沒讀取完資料，所以這個 fd 可讀，那麼下一次事件循環又返回這個 fd，還分配給其他的執行緒，該如何處理？

若某 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

如果某個執行緒在處理 fd 的同時，又有新的一批資料進來，該 fd 可讀（注意和上一題的區別：一個是處理同一批資料，另一個是處理新一批資料），那麼該 fd 會被分配另一個執行緒，這樣兩個執行緒處理同一個 fd 就會導致錯亂。

設定 EPOLLONESHOT 可解決這個問題。在 fd 回傳可讀後，需要另行設定，才能讓 epoll 重新回傳這個 fd。

當 Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下，遇到 (1) 網頁瀏覽器突然關閉; (2) 客戶端網路離線; 這兩種狀況，伺服器該如何處理？

分兩種狀況處理:

1. 此時該 fd 在事件循環裡會回傳一個可讀事件，然後分配給某個執行緒，該執行緒 read 會回傳 0，代表對方已關閉這個 fd，於是伺服器端呼叫 close 即可;
2. 通訊協定無法立刻知悉，所以僅能透過伺服器引入 timer 逾時事件來克服

timer 可透過 priority queue 實作，後者又常用 binary heap 實作，可參見以下:

• Priority Queue 簡介
• Priority Queue：Binary Heap

將 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 通訊協定會遇上解析錯誤。

解法是維護一個狀態機，在解析 Request Header 時候對應一個狀態機，解析 Header Body 的時候也維護一個狀態機。

參考資訊

• Concurrent HTTP Server with Epoll
• fancy: A high performance web server
• poll vs select vs event-based
• Async IO on Linux: select, poll, and epoll
• Fast UNIX Servers
• Concurrent Servers