Asynchronous Non-blocking I/O under the hood: poll, select, epoll/kqueue

Why asynchronous non-blocking I/O??

Ngắn dọn là do OS Thread quá tốn kém (memory, CPU time context switching). Các mô hình blocking với 1 thread / 1 request trở nên không còn hiệu quả.

File Descriptor (FD): “In Linux, everything is a file”

Hiểu đơn giản là để nhắc đến 1 file thì phải có 1 cái gì cụ thể (sờ được, xoá được, tạo được) để mô tả nó, đó chính là file descriptor. Cái đó trong linux nó chỉ là 1 con số integer để kernel có thể phân biệt được giữa các file:

File description chỉ là 1 số integer unique để phân biệt giữa các file
Socket, stdout, stdin, stderr… đều là file

FD được quản lý ở kernel, khi process tạo một file, mở một kết nối tới TCP Socket, … thông tin sẽ nằm trong data structure được kernel trả lại cho process (phần lưu trữ đó nằm trên kernel được gọi là global file table, chứa các thông tin như là inode của file, byte offset và quyền truy cập cho luồng dữ liệu đó như read-only, write-only, …)

Các phần trong bài viết được dựa trên sách The Linux Programming Interface - Chapter 63: Alternative I/O models.

How Did Linux Blocking I/O System Calls Evolve?

Ngày xưa, I/O trong Linux chỉ có thể là blocking call, kiểu như sau:

// Đọc file từ một FD
ssize_t read(int fd, void *buf, size_t count);

// Ghi file vào một FD
ssize_t write(int fd, const void *buf, size_t count);

Khi cần request read/write gì đó (I/O, pipe, disk…), sau khi call thì process (thread) sẽ bị sleep cho tới khi các I/O operation này được thực hiện xong, muốn làm gì (ví dụ xử lí 1 request khác) thì phải fork process (thread) khác mà làm, điều này dẫn tới 10K Problem.

Servers need to watch a lot of file descriptors

Trên server, mỗi lần khi bạn đồng ý mở một kết nối tới client với system call accept, sẽ có một FD sinh ra để biểu diễn kết nối đó cho process biết.

Đối với hầu hết các web server, thường phải xử lí hàng nghìn kết nối tới client cùng lúc. Lúc này server sẽ cần biết khi nào client trả dữ liệu mới lên những kết nối này, để server có thể process và response lại cho client, điều này có thể được thực hiện bằng một vòng for loop như bên dưới:

# Server tạo 1000 request tới DB (client) để query data, và đợi data từ DB client trả về
for x in database_query_connections:
    if has_new_response_data(x):
        process_response(x)

Vấn đề với cách làm này là nó có thể lãng phí rất nhiều CPU time. Thay vì lãng phí tất cả CPU time vào việc hỏi “có update nào mới không?”, chúng ta có thể đơn giản là nói với Linux kernal “này, tao đang có 100 FD, báo tao khi có một cái nào đó update data nhá!“.

Các system call giúp bạn gọi Linux theo dõi (monitor) các FD là poll, select và epoll (kqueue trên BSD và Mac). Hãy bắt đầu với select và poll.

Start with `poll` & `select`

2 Syscall này có sẵn trên tất cả các phiên bản Unix, trong khi epoll và kqueue là tuỳ vào bản Unix nào (Ubuntu xài epoll, Mac xài kqueue, 2 thằng này khá giống nhau). Đây là cách chúng hoạt động:

Input vào hàm một dãy các FD cần theo dõi, và timeout
Gọi hàm poll và select, nó sẽ báo cho bạn khi một trong những FD trong list có dữ liệu để đọc/ghi vào

int ppoll(struct pollfd *fds, nfds_t nfds,
          const struct timespec *tmo_p, const sigset_t
          *sigmask)`

int pselect(int nfds, fd_set *readfds, fd_set *writefds,
            fd_set *exceptfds, const struct timespec *timeout,
            const sigset_t *sigmask);

/* Returns: positive count of ready descriptors, 0 on timeout, –1 on error */

Khi các hàm ppoll và pselect được gọi, nó trả về ngay lập tức, chứ không đợi (block) cho tới khi I/O operation xong mới trả về như hàm read và write bên trên: trả về số dương thể hiện số lượng các ready FD, 0 nếu timeout, -1 nếu lỗi.

Một điều thú vị là poll và select về cơ bản xài có cách implement code khá giống nhau:

select chuyển đổi từ các result cụ thể của poll thành một result tổng quát hơn, ví dụ như POLLWRBAND được chuyển thành INPUT. Bạn có thể xem phần sourcecode đó trong Linux 4.10 ở đây.

Khác biệt tiếp theo nữa là: poll có thể có hiệu suất tốt hơn select khi bạn có một tập FD cần theo dõi nhỏ hơn.

Để thấy rõ điều này, bạn hãy nhìn vào signatures của các function poll và select ở bên trên.

Với poll, bạn có thể gọi “đây là các FD mà tao cần theo dõi: 1, 3, 8, 19, …” (đó là tham số pollfd). Với select, bạn gọi “Tao phải theo dõi 19 FD, đây là 3 danh sách của những FD cần reads/writes/exceptions”. Nên khi select chạy, nó sẽ loops từ 0 tới 19 trong danh sách các FD, ngay cả khi bạn thật sự chỉ cần dùng 4 cái.

Trên đây là 2 điểm khác biệt chính của poll và select như trong sách chủ yếu đề cập tới.

Why don’t we use poll and select?

Trên Linux, Node.js (dựa trên libuv) không xài poll hay select mà xài epoll, vì sao?

Theo như trong sách:

On each call to select() or poll(), the kernel must check all of the specified file descriptors to see if they are ready. When monitoring a large number of file descriptors that are in a densely packed range, the timed required for this operation greatly outweights [the rest of the stuff they have to do]

Cơ bản là: mỗi lần bạn gọi select hay poll, kernel cần kiểm tra lại từ đầu rằng các FD đã sẵn sàng để ghi/đọc chưa. Với poll/select, kernel hoàn toàn không có cơ chế “ghi nhớ” danh sách các FD mà nó cần được theo dõi.

Level-triggered vs Edge-triggered

Trước khi chúng ta nói về epoll, cần nói về level-triggered vs edge-triggered (2 cái này đối lập nhau):

get a list of every file descriptor you’re interested in that is readable (“level-triggered”)

get notifications every time a file descriptor becomes readable (“edge-triggered”)

epoll có thể sử dụng cả 2 mode trên, select và poll chỉ có thể dùng “level-triggered”.

Mặc định epoll là level-triggered, để được notify mỗi khi fd thay đổi, thì cần thêm cơ chế của Signal-driven I/O (sẽ nói trong phần dưới) để đạt được edge-triggered.

What’s epoll?

epoll là một group các syscall (epoll_create, epoll_ctl, epoll_wait) cho Linux kernel một danh sách FD để theo dõi và cập nhật.

Đây là các bước để dùng epoll:

Gọi epoll_create để nói kernel rằng bạn chuẩn bị epolling, hàm này sẽ trả về một id
Gọi epoll_ctl để nói kernel FD nào bạn muốn nhận update khi nó thay đổi, bạn có thể cung cấp nhiều loại FD khác nhau (pipes, FIFOs, sockets, POSIX message queues, inotify instances, devices, …) nhưng không thể là 1 file thông thường. Mình nghĩ rằng điều này có lí, vì pipes & sockets có API khá đơn giản (1 process write vào pipe, 1 process read từ pipe), nên khá đơn giản đễ nhận ra “pipe này có data mới để đọc”. Nhưng files thì khác, bạn có thể ghi vào giữa file, nên việc nhận biết data mới là không dễ. Cho nên, những trường hợp cần multiplex với storage file I/O, vẫn phải dùng mô hình blocking I/O cũ (improve bằng thread pool model).
Gọi epoll_wait để chờ nhận cập nhật về các FD trong danh sách bạn cần theo dõi.

Performance: select & poll vs epoll

Trong sách, có một bảng so sánh hiệu năng cho của các syscall như sau:

# operations  |  poll  |  select   | epoll
10            |   0.61 |    0.73   | 0.41
100           |   2.9  |    3.0    | 0.42
1000          |    35  |    35     | 0.53
10000         |   990  |    930    | 0.66

Sử dụng epoll sẽ nhanh hơn đáng kể nếu bạn có 10 hoặc nhiều hơn FD cần theo dõi.

Edge-triggered `epoll`

Nonblocking Mode (O_NONBLOCK)

1 fd được đặt vào “nonblocking mode” bằng cách thêm O_NONBLOCK vào tham số gọi hàm fcntl trên fd:

/* set O_NONBLOCK on fd */
int flags = fcntl(fd, F_GETFL, 0);
fcntl(fd, F_SETFL, flags | O_NONBLOCK);

(WIP)

Signal-driven I/O make `epoll` edge-triggered

Trong sách mô tả 2 cách để làm kernel “ghi nhớ” danh sách các FD mà nó phải theo dõi: signal-driven I/O và epoll. Signal-driven I/O là một cách để khiến kernel gửi bạn một tín hiệu khi một FD được cập nhật (aka edge-triggered).

Để kích hoạt signal-driven I/O, chúng ta phải thiết lập một handler cho SIGIO signal.

struct epoll_event ev;

ev.data.fd = fd;
ev.events = EPOLLIN | EPOLLET;
if (epoll_ctl(epfd, EPOLL_CTL_ADD, fd, ev) == -1) {
    errExit("epoll_ctl");
}

(WIP)

Signal-driven I/O là 1 trong 5 I/O model (gồm: blocking I/O, nonblocking I/O, I/O multiplexing, signal driven I/O và asynchronous I/O), mô hình này xài signals để nói với kernel thông báo với chúng ta SIGIO signal khi FD đã sẵn sàng.

Dưới đây là đoạn code demo việc sử dụng epoll ở edge-triggered mode với flagset EPOLLET:

#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/epoll.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <unistd.h>

#define MAXEVENTS 64
#define PORT 9000

static void set_nonblocking(int fd) {
  int flags = fcntl(fd, F_GETFL, 0);
  if (flags == -1) {
    perror("fcntl()");
    return;
  }
  if (fcntl(fd, F_SETFL, flags | O_NONBLOCK) == -1) {
    perror("fcntl()");
  }
}

int main(int argc, char **argv) {
  // create the server socket
  int sock = socket(AF_INET, SOCK_STREAM, 0);
  if (sock == -1) {
    perror("socket()");
    return 1;
  }
  int enable = 1;
  if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &enable, sizeof(enable)) ==
      -1) {
    perror("setsockopt()");
    return 1;
  }

  // bind
  struct sockaddr_in addr;
  memset(&addr, 0, sizeof(addr));
  addr.sin_family = AF_INET;
  addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK);
  addr.sin_port = htons(PORT);
  if (bind(sock, (struct sockaddr *)&addr, sizeof(addr)) < 0) {
    perror("bind()");
    return 1;
  }

  // make it nonblocking, and then listen
  set_nonblocking(sock);
  if (listen(sock, SOMAXCONN) < 0) {
    perror("listen()");
    return 1;
  }

  // create the epoll socket
  int epoll_fd = epoll_create1(0);
  if (epoll_fd == -1) {
    perror("epoll_create1()");
    return 1;
  }

  // mark the server socket for reading, and become edge-triggered
  struct epoll_event event;
  memset(&event, 0, sizeof(event));
  event.data.fd = sock;
  event.events = EPOLLIN | EPOLLET;
  if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, sock, &event) == -1) {
    perror("epoll_ctl()");
    return 1;
  }

  struct epoll_event *events = calloc(MAXEVENTS, sizeof(event));
  for (;;) {
    int nevents = epoll_wait(epoll_fd, events, MAXEVENTS, -1);
    if (nevents == -1) {
      perror("epoll_wait()");
      return 1;
    }
    for (int i = 0; i < nevents; i++) {
      if ((events[i].events & EPOLLERR) || (events[i].events & EPOLLHUP) ||
          (!(events[i].events & EPOLLIN))) {
        // error case
        fprintf(stderr, "epoll error\n");
        close(events[i].data.fd);
        continue;
      } else if (events[i].data.fd == sock) {
        // server socket; call accept as many times as we can
        for (;;) {
          struct sockaddr in_addr;
          socklen_t in_addr_len = sizeof(in_addr);
          int client = accept(sock, &in_addr, &in_addr_len);
          if (client == -1) {
            if (errno == EAGAIN || errno == EWOULDBLOCK) {
              // we processed all of the connections
              break;
            } else {
              perror("accept()");
              return 1;
            }
          } else {
            printf("accepted new connection on fd %d\n", client);
            set_nonblocking(client);
            event.data.fd = client;
            event.events = EPOLLIN | EPOLLET;
            if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, client, &event) == -1) {
              perror("epoll_ctl()");
              return 1;
            }
          }
        }
      } else {
        // client socket; read as much data as we can
        char buf[1024];
        for (;;) {
          ssize_t nbytes = read(events[i].data.fd, buf, sizeof(buf));
          if (nbytes == -1) {
            if (errno == EAGAIN || errno == EWOULDBLOCK) {
              printf("finished reading data from client\n");
              break;
            } else {
              perror("read()");
              return 1;
            }
          } else if (nbytes == 0) {
            printf("finished with %d\n", events[i].data.fd);
            close(events[i].data.fd);
            break;
          } else {
            fwrite(buf, sizeof(char), nbytes, stdout);
          }
        }
      }
    }
  }
  return 0;
}

Hoặc xem phiên bản source-code go (netpoller)

Who uses `epoll`?

Khi sử dụng event loop, green threads / goroutines thực chất là bạn đang sử dụng các high level interface để tiện cho việc development thôi, under the hood thì nó đều gọi qua epoll (hoặc kqueue) để thực hiện tất cả các operation về networking và pipe I/O.

Ví dụ, đây là một đoạn code Go mà under the hood nó sử dụng epoll trên Linux:

package main

import "net/http"
import "io/ioutil"
import "fmt"

func main() {
    resp, err := http.Get("http://tuhuynh.com/")
    if err != nil {
        // handle error
        panic(err)
    }
    defer resp.Body.Close()
    bodyData, err = ioutil.ReadAll(resp.Body)
    fmt.Println(string(bodyData))
}

Go runtime sử dụng epoll để thực hiện DNS lookup (qua log syscalls):

16016 connect(3, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.1.1")}, 16 <unfinished ...>
16020 socket(PF_INET, SOCK_DGRAM|SOCK_CLOEXEC|SOCK_NONBLOCK, IPPROTO_IP
16016 epoll_create1(EPOLL_CLOEXEC <unfinished ...>
16016 epoll_ctl(5, EPOLL_CTL_ADD, 3, {EPOLLIN|EPOLLOUT|EPOLLRDHUP|EPOLLET, {u32=334042824, u64=139818699396808}}
16020 connect(4, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.1.1")}, 16 <unfinished ...>
16020 epoll_ctl(5, EPOLL_CTL_ADD, 4, {EPOLLIN|EPOLLOUT|EPOLLRDHUP|EPOLLET, {u32=334042632, u64=139818699396616}}

Về cơ bản, với đoạn code trên Go runtime sẽ cố gắng connect 2 sockets (trên FD 3 và 4) để thực hiện DNS queries (tới 127.0.1.1:53), và sau đó dùng epoll_ctl để yêu cầu epoll trả về cập nhật của các queries này.

Sau đó thực hiện thêm 2 DNS queries cho tuhuynh.com (vì sao lại 2? có vẻ là 1 cái cho A record, 1 cái cho AAAA record), và dùng epoll_wait để đợi phản hồi từ các queries này.

# đây là DNS queries cho tuhuynh.com:
16016 write(3, "\3048\1\0\0\1\0\0\0\0\0\0\7tuhuynh\3com\0\0\34\0\1", 29
16020 write(4, ";\251\1\0\0\1\0\0\0\0\0\0\7tuhuynh\3com\0\0\1\0\1", 29
# ở đoạn này, runtime đang cố gắng lấy response nhưng vẫn
# chưa có response nào 
16016 read(3,  <unfinished ...>
16020 read(4,  <unfinished ...>
16016 <... read resumed> 0xc8200f4000, 512) = -1 EAGAIN (Resource temporarily unavailable)
16020 <... read resumed> 0xc8200f6000, 512) = -1 EAGAIN (Resource temporarily unavailable)
# sau đó nó sử dụng epoll để đợi các responses
16016 epoll_wait(5,  <unfinished ...>
16020 epoll_wait(5,  <unfinished ...>

Các tool language/framework phổ biến sử dụng epoll như thế nào:

Node.js xài libuv
Python xài libev/libevent
Java xài Netty, trước đó thì Java NIO chỉ xài level-triggered syscall như poll và select, sau đó thì cũng dùng epoll
Golang thì tự code (netpoller), trong Go runtime - chỉ khoảng 100 dòng code, vi diệu vãi

Webserver như Nginx cũng xài epoll, đây là source code, hay một số DB như Redis

(…to be continue)