IO多路復用與epoll機制淺析
epoll是Linux中用於IO多路復用的機制，在nginx和redis等軟件中都有應用，redis的性能好的原因之一也就是使用了epoll進行IO多路復用，同時epoll也是各大公司面試的熱點問題。
IO多路復用
IO多路復用是一種同步IO模型，使得一個線程就可以對多個文件描述符進行監聽。當有文件描述符準備就緒時，函數就會返回，從而通知應用進行相應的處理；當沒有描述符就緒時，函數就會阻塞。
IO多路復用對於網絡應用來說是非常重要的，在沒有IO多路復用時，應用一般通過同步阻塞（每個socket連接建立一個新線程，這將十分耗費系統性能）或者同步非阻塞（對所有socket進行反覆遍歷，當沒有就緒描述符時就會做無用功）來實現，而這些方法的性能都不太好。
在Linux中，IO多路復用主要有三種方法select、poll和epoll。
select
int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
select是通過傳遞文件描述符數組fd_set*來實現的。當沒有描述符準備就緒時，函數就會阻塞；當有一個或多個文件描述符準備就緒時就會返回，之後通過遍曆數組找到準備就緒的描述符進行處理。select函數一般在所有操作系統中都會實現，因此具有良好的可移植性。
fd_set的大小是固定的，在Linux中一般為1024，本質是一個bitmap，通過FD_SET將描述符加入fd_set，通過對所有文件描述符依次調用FD_ISSET來判斷是否準備就緒。
因此，select就有着以下的缺點：
select的文件描述符最大只能支持1024個select需要通過遍歷來判斷是否準備就緒，因此時間複雜度為O(n)- 當監聽文件描述符數量增加時，性能會明顯下降
select內核態中通過輪詢來判斷文件描述符是否就緒select每次調用都需要將fd_set從用戶地址空間拷貝到內核地址空間中，函數返回時又要拷貝回來
poll
int poll(struct pollfd *fds, nfds_t nfds, int timeout);
struct pollfd {
int fd; // 文件描述符
short events; // 等待的事件
short revents; // 發生的事件
};
poll對select的主要改進就是沒有了描述符數組的大小限制，沒有最大連接數的限制。但是poll仍然需要進行遍歷才能知道哪些文件描述符準備就緒，因此，select的缺點poll也有。
epoll
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使用了三個系統調用來實現，epoll_create創建一個句柄，epoll_ctl向句柄中添加、刪除或修改文件描述符，epoll_wait對句柄進行監聽，當有文件描述符準備就緒後，就會通過events參數返回。返回的參數中僅包含準備就緒的文件描述符，也就是說不再需要通過遍歷來進行判斷。epoll通過回調機制來快速將文件描述符加入就緒鏈表，避免輪詢；同時epoll內部使用紅黑樹來保存所有監聽的文件描述符。
epoll有着以下的優點：
- 沒有最大文件描述符數量限制
- 使用mmap，避免了每次
wait都要將數組進行拷貝 - 直接返回就緒的文件描述符，避免了遍歷，時間複雜度為O(k)，k為就緒文件描述符
- 使用回調機制，當文件描述符就緒時會觸發回調函數，將描述符加入到就緒鏈表，避免輪詢
- 監聽的文件描述符數量對性能影響不大
但是epoll也不是一定比select和poll好，當就緒的文件描述符很多時，即O(k)中的k接近n時，兩者性能就比較接近了；當文件描述符數量較少時，兩者性能也差不多；epoll的回調函數註冊也會帶來一定的性能開銷。
觸發方式
epoll有兩種觸發方式，水平觸發（LT, level-triggered）和邊緣觸發（ET, edge-triggered）。通過一個例子來理解兩種方式：
當描述符a中到達2kb數據，調用epoll_wait會返回a，之後從描述符中讀取1kb數據，此時該描述符中仍有1kb數據，仍為就緒狀態；第二次調用epoll_wait時，如果是LT，那麼返回的描述符中仍包含a，如果為ET，那麼就不包含a。
即ET只會在狀態發生改變時觸發，只返回一次，類似於上升沿觸發；而LT只要處於就緒狀態就會一直返回，類似於電平觸發。
理論上ET的性能會比LT要好，但是ET要保證每次都要把數據全部處理完成，而LT使用起來就更加方便，不易出現bug。在實際當中兩種的性能區別可以忽略，redis使用的就是LT方式。
