一文了解比特币挖矿难度调整全历程

作者 | 徐员外

来源 | 后端技术指南（ID:gh_ed1e2b37dcb6）

Linux IO多路复用有 epoll、poll、select，而epoll的性能比K v e 7 8 q ) 2 z其他几者+ o H $ D V要好。其中的原因是什么？IO复用能用来干什么？相信很多人有此疑问! d 8 g 4 k 8 N。

通过本篇文章，我们将了解到以下内容:

• I/O复用的定? A b ; o M A义和产生背景

• Linux系统的I/O复用工具

• epollM e V n u x 4设计的基本构成

• epoll高性能的底层实现

• epH F T p A M @ :oll的ET模式和LT模式

复用技术和I/O复] r x & F 用

• 复- [ K 1 : / n用的概念

复用技术(multiplexing)并不是新技术而是一种设计思想，在通信和硬件设计中存在频分复用、时分复用、波分复用、码分复用等，在日常生活中复用的场景也非常多，因此不要被专业术语所迷惑。

从本质上来说，复用就是为了解决有限资源和过多O G D { z * 8 I使用者的不平衡问题，且此技术的理论基础是资源的可释放性。

• 资源的可释放性

举个实际生活的例子：

不可释放场景：ICU病房的呼吸机作为有限资源，病人一旦占用且在未脱离危险之前是无法放弃占用的，因此不可能几个情况一样的病人轮流使用。

可释放场景：对于一些其他资源比如医护人员就可以? o )实现对多个病人的同q C v i J R k 9 G时监护，理论上不存在一个病人占用医护人员资源不释放的场景。

• 理解IO复用

I/O的| $ q m r n }含义：在计算机领域常说的IO包括磁盘IO和网络IO，我们所说的IO复A Y o ] b K + 1用主要是指网络IO，+ 7 5 } u v } j 4在Linux中一切皆文件，因此网络IO也经常用文件描述符FD来表示。

复用的含义：那么这些文件描述符FD要复用什么呢？在网络场景中复用的就是任务处理线程，所以简单理解就是多个IO共用1个线程。

IO复用的可行性：IO请求的基本操作包括read和write，由于网络交互的本E s a质性，必然存在等待，换言之就是整个网络连接中FD的读写是交替出现的，时而可读可写，时而空闲，所以IO复用是可用实现的。t ] K t ` N (

综上认为，IO复用技术就是协调多个可释放资{ 9 U C ; 6 d c源的FD交替共享任h / M v务处理线程完成通信任务，实现多个fd对应1个任务处理线程。

现I V 6 J S _ 2实生活中IO复用就像一只边牧管理几百只绵羊一样：

• IO复用的设计原则和产生背景

高效IO复用机制要满足：协调者消耗最少的系统资源、最小化FD的等待时间、最大化FD的数量、任务处理线程最少的空闲、多快好省完成任务等。

在网络并发量非常小的原始时期，即使per req per process地处理@ Y - | H &网络请求也可以满足要求，但& . * & z K是随着网络并发量的提高，原始方式必将阻碍进步，所以就刺激了IO复用机制的实现和推广。

Lu x [ $ ~ ` sinux中IO复用工具

在Linux中先后出现了select1 c b j | G、poll、epoll等，FreeBSD的kqueue也是非常优秀的IO复用工具，kS ] 5 {queue的9 + o原理和epoll很类似，本文以Linux环境为例，并且不讨论过多select和poll的实现机制和细节。

• 开拓者select

select大约是2000年初出现的，其对外的接口定义：

* According to) 5 o I POSIX.1-2001 */#include &lJ v Qt;sys/select.h>
/* According to earlier standards */#iI R $ V Unclude <sys/time.h>#include <sys/types.h>J )  ( _ m#include <u{ P s 9 * e a dnistd.h>
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timevaS ( x . ? s ?l *timeout);void FD_CLR(int fd, fd_set *set);int FD_ISSET(int fd, fd_set *set);void FD_SET(int fd, fd_set *set);void FD_ZERO(fd_set *set);

作为第一个IO复用系统调用，select使用一个宏定义函数按照bitmap原理填充fd，默认大小是1024个，因此对于fd的数值大于1024都可能出% D -现问题，看下官方预警:

Macro: int FD_SETSIZEThe vT 5 O U R M f ]alue of this macro is the mr N # Q & gaximum number of file descriptorsthat a fd_set object can holz 7 - ~ m B y {d information abD 9 n Q & 5 W [ bout. On systems with a fixed maximum number, FD_SETSIZE i@ C W h A ^ E 8 {s at lea c j C ast that number. On some systems, including GNU, there is no absolute l_ s b 1 1 J { Gimit on the number o3 Z # y = Q }f descriptors open, but this macro stillt X C i i d  o has a constp : uant value which controls the number of bits in ane 4 ( D  t fk w V /d_set; if you get a f` e m R b e dile des | a V k t #scN { C J N 0 [ ]riptor with a value as high as FD_SETSIZE, you cannot put that descriptor into an fd_set.

数值大于1024时在将不可控，官方不建议 - U I l 7 E E超过1024，但是我们也无法控制fd的绝对数值大小，之前针对这个问题做过一些调研，结论是系统对于fd[ e y #的分配有自己的策略，v k h会大概率分配到1024以内，对此我并没有充分理解$ E ) T % t f，只是提及一下这个坑。

存在的问题:

• 可协调fd数量和数值都不超过1024 无法实现高并发

• 使用O(n)复! H s I杂度遍历fd数组查看fd的可读写性 效率低

• 涉及大量kernel和用户态拷贝 消耗大

• 每次完成监控需要再次重新传入并且分事件传入 操作冗余

综上可知，select以朴素的方式实9 + X U | 5 m d现了IO复用，将并发量提高的最大K级，但是对于完成这个任务的代价和灵活性都有待l | g ^提高。无论怎么样select作为先驱对IO复用有巨大的推动，并且指明了后续的优化方向，不要无知地指责select。

• 继承者epoll

epoll最初在2.5.44内核版本出现，后续在2.6.O h E (x版本中对代码进行了优化使其更加简洁，先后面对外界的质疑在后续增加了一些设置来解决隐藏的问题，所以epoll也已经有十几年的历史了。

在《Unix网络编程》第三版(2003年)还没有介绍epoll，因为那个时代epoll还没有出现，书中只介绍了sele( v ect和j H a a Y I %poll，epoll对select中存在的问题都逐一解决，简单来说epoll的优势包括：

• 对fd数量没有限制(当然这个在pX O d ~oll也被解决了)

• 抛弃了bitmap数组实现了新的结构来存储多种9 ~ % ^事件类型

• 无需重复拷贝fd 随用随加 随弃随删

• 采用事件驱动避免轮询查看可读写/ q 9 R J E事件

综上可知，epoll出现之后大大提高了并发量对于C10K问题轻松应对，即使后续出现了真正的异步IO，也并没有(暂时没有)撼动epoll的江湖地位，主要是因为epL u , {olM G i + x %l可以解决数万数十万的并发量，已经可以解决现U ] m . ^在大部分的场景了，异步IO固然优异，! X $但是编程难度比epoll更大，权衡之下epoll仍然富有生命力。

epoll的基本实现

• epoll的api定义：G } ` $ t s

//用户数据载体typedef union epoll_data { void *ptr; int fd; uint32_t u32; uint64_t u64;} epoll_data_t;//fd装载入内核的载体 st? / $ { Fruct epoll_event { uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */ }; //三板斧apiint epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);m w w } ; ;  int epolq Q X | . p { /l_wai| b x Lt(int epfd, struct epoll_event *events, iS { ! 3 ; $nt maxevents, int timeout);

• epoll_crea; W ! W z H ! = }te是在内核区创建一个epoll相关的一些列结构，并且将一个句柄fd返回给用户态，后续的操作都是基于此fd的，参数size是告诉内核这个结构的元素的大小，类似于stl的vector动态数组，如果size不合适会涉及复制扩容，不过貌似M L i Z i z4.1.2内核之后size已经没有太大用途了；

• epoll_ctl是将fd添加Y q / i/删除于epoll_q P o v % 3 f 9 $create返回的epfd中，其中epoll_event是用户态和内核态交互的结构，定义i B l了用户态关! - x W / S心的事: ; X l q件类型和触发时数据的载体epoll_data；

• epollw 8 R ^ ) G d O_wait是阻塞等待内核返回的可读写事件，epfd还是epot 4 / Z . 3 2 ?ll_create的返回值，events是个结构体数组指针存储epoll_event，也就是将内核返回的待处理epoll_event结构都存储下来，maxeventl 5 d 0 e _ -s告诉内核本次返回的最大fd数量，这个和events指向的数组是相关的；

• epoll_event是用户态需监控fd的代言人，后续用户程序对fd的操作都是基于此结构的；

• 通俗描述：

可能P _ k ~ s z Z $ `上面的描述有些抽象，不过其实很好理解，举个现实中的例子：

• epoll_create场景：

  大学开学第l h 一周，你作为班长需要帮全班同学领取相关物品，你在学生处告诉工作人员，我是xx学院xx专业xx班的班, } v v $ R长，这时工? f c作人员确定你的身份并且给了你凭证，后面办的事情都需要用到(也就是调用epoll_crG % Y ] ( zeate向内核申请了epfd结H % - ` U 1构，内核返回了epfd句柄给你使用)；

• epoll_ctl场景：

  你拿着凭证在办事大厅开始办事，分拣办公室工作人员说班长你把所有需要办理事情的同v 5 ; L * W学的学生册和需要办理的事情都记录下来吧，于是I q } ^ P H - W班长开始在每个学生手册单独写对应需要办的事情：

  李明需要开实验室权限、孙大熊需要办游泳卡......就这样班长一股脑写完并交给了工作人员(也就是告诉内核哪些fd需要做哪些操作)；

• epoll_wait场景：

  你拿着凭证在领取办公室门前等着，这时候广播喊xx班长你们班孙大熊的游泳卡办好了速来领取、李明实验室权限卡办好了速来取....还有同学的事情没办好，所以班长只能继续(也就是调用epoll_wait等待内核反馈的可读写事件发生并处理)；

• 官方DEMO

通过m3 J Nan epoll可以看到官方的demo：

#define MAX_EVENTS 10struct epoll_event ev, eveno F ets[Mv q $ CAX_EVENTS];int listen_sock, conn_sock, nfds, epollfd;
/* Ses R l j p 2 h Lt up listening socket, { / 6 } % 4 i h J\'listen_sock\' (socket, bind, listen) */
epollfd = epoll_create(10);if(epollfd == -1) { perror(\"epoll_create\"); exi 8  0 [ X /it(EXIT_FAILURE);}
ev.events = EPOLLIN;ev.data.fd = listen_sock;if(epoll_ctl(epollfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1) { perc , j K Y H M O Mror(\"epollF g y -_ctl: listen_sock\"); exit(EXIT_FAILURE);}
for(;;) { nfds = epoll_wait(epollfd, events,# H c & z 3 . 5 3 MAX_EVENTS, -1); if (nfds == -1) { perror(\G Y d C e & W"epoll_pwait\"); exit(EXIT_FAILURE); }
 for (n =O 8 Y . Q ! o ) / 0; n < nfds; ++n) { if (events[n].data.fd == listen_sock) { //主监听socket有新连接 conn_sock = accept(listen_sock, (s? _ = Vtruct sockaddr *) &local, &addrlen); if (conn_sock == -1) { perror(\"accept\"); exit(EXIT_FAILURE);+ / G 2 , |  A w } setm u 3nonblocking(conn_sock); ev.events = EPOLLIN |x j ( e @ + # ! EPOLLET; ev.data.fd = conn_sock; if (epoll_ctl(epollfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) { perror(\"epoll_ctl: conn_sock\"); exit(EXIT_FAILURE); } } else { //已建立连接的可读写句柄 do_use_fd(events[n].data.fd); } }}

在epoll_wait时需要区分是主监听线程fd的新连接事件还是已连接事件的读写请求，进而单独处* t h v c 0 F理。

epoll的底层实现

epoll底层实现最重要的两个数据结构:epitem和es r 3ventpoll。

可以简单[ a ~ q :的认为epitem是和每个用户态监控IO的fd对应的,evem I X s E X +ntpoll是用户态创建的管理所有被监控fd的结构，详细的定义如下：

#ifndef _LINUX_RBTREE_H#define _LINUX_RBTREE_H#include <linux/kernel.h>#include <linux/stddef.h>#include &li C O Pt;liW 3 Dnux/rcupdd 8 H & 1 N m Nate.h>
struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left;} __attribute__((aligneQ $ c {d(sizeof(long)))G } [ G);/* The alignment might seem pointless, but allegedly CRIS needs it */struct rb_root { struct rb_node *rb_node;};

struct epitem { struct rb_node rp ` 1 5 } Hbn;  std D , 0ruct list_head rdllink;  struct epitem *next;  struct epoll_filefd ffd;  ib = #nt nwaitY 8 4;  strx k e 4 {uct list_head pwqlist;  struct eventpollE l + O L t *ep;  strus T O k g p fct list_head fllink;  struct epoll_0 7 0 T ] } @event event; }

struct eventpoll { spin_lock_t lock;  s~ u @ G f A  htruct mutex2 ? C mtx;  wait_queue_head_t wq;  wait_queue_headb 2 N Q T j ) 9_t poll_wait;  struct list_head rdllist; //就绪链表 struct rb_root rbr;K { g B # z //红黑树根节点  struct e( O p D - $ W c !piti ` 7 - U @ 8em *ovflist;}

• 底层调用过程

epoll_create会创建一个类型为struct eventpoll的对象，并返回一个与之对应文件描述符，之后应用程序在用户态使用epoll的时候都将依靠这个H A 6 D =文件描述符，而在epoll内部也是通过该文件描述符进一步获取到eventpoll类型对象，再进行对应的操作，完成了用户态和内核态的贯穿。

epoll_ctl底层: 2 % A m P ; H u主要调用epy a !oll_insertL X i G & A n u g实现操作:

• 创建并初始化一个strut epitem类型的对象，完成该对象和被监控事件以及epoll对象eventpoll的关联;

• 将struct epitem类型的对象加入到epoll对象eventpoll的红黑树中管理起来;

• 将struct epitem类| H 0 c 2 | A s型的对象加入到被监控事件对应的目标文件的等待列表中，并注册事件就绪时会调用的回调函数，在epoll中该回调函数就是ep_D $ W : 7 K vpoll_callback;

• ovflist主要是暂态处P P M } r理，比如调用ep_poll_callback回调函数的时候发现eventpoll的ovflist成员不等于EP_UNACTIVE_PTR，说明正在扫描rdllist链表，这时将就绪事件对应的epitem加入到ovflist链表暂存l f | s 9 q ? )起来] w = $，等rdllist链表扫描完再将ovflist链表中y 9 * X n h ` 7 )的元素移动到rdllist链表中；

• 如图展示了红黑树、双链表、epitem之间的关系:

注:rbr表示rb_root，rbn表示rb_node 上文给出了其在内核中的定义

• eZ w o G 8 y bpoll_+ ^ o ~ t ? n & $wait的数据拷贝

常见错误观( h o ( I N点:epoll_wait返回时，对于就绪的事件，epoll使用的是共享内存的方式，即用户态和内核态都指向了就绪链表，所以u y u 7 e & 6 a就避免了内存拷贝消耗

网上抄来抄去的观点

关于epoll_waq . t .it使用共享内存的j : ( _ 9 c 9 ;方式来加速用户态和内核态的数据交互，避免内存拷贝的观点，并没有得到2.6内核版本代码的证实，并且关于这次拷贝的实现是这样的：

revents = ep_item_poll(epi, &pt)s * : f M H 3;//获取就绪事件if (revents) { if (__put_user(revents, &uevent->events) || __put_user(epi->event.data, &uevent->data)) { list_add(&epi->rdl! C y m D .link, heaA t sd);//F D ] G j m处理失败Y 8 m 5 = N v则重新加入链表 ep_pm_stay_awaU Y R ; Dke(epi); return eventcnt ? eventcnt : -EFAULT; } eventcnt++; uevent++; if (ed O [pi-&! w [ 7 T / v wgt;event.events & EPOLLONESHOT) epi->event.events &= EP_k [ 6PRIVATE_BITS;//EPOLLONET ! q x oSHa = k m p h ] $ nOT标记的处理 else if (!(epi-I S t>event.events & EPOLLET)) { lisN { _ + H 9 S &tQ f / H ! H_add_tail(&epi->rdllin: q P 1 / j Y =k, &e ( D cp->rdllist);//LT模式 @ & z k Z 1 } |处理 ep_pm_stay_a( 6 r 2 | 2wake(epi); }}

ET模式和LT模式

• 简单理解

默认采用LTY s t 8 q模式，LT支持阻塞和非阻塞套，ET模式只支持非阻塞套接字，其效率要高于LT模式，并且LT模式更加安全。

LT和ET模式下都可以通过epoll_wait方法来获取事件，LT模式下将事件拷贝给用户程序之后，如果没有被处理或者未处理完，那么在下次x % B调用时还会反馈给用户程序| i T s，可以认为数据不会丢失会反复提醒；

ET模式下如p ( L ;果没有被处理或者未处理完，那么下次将不再通知到用户程序，因此避免了反复被提醒，却加强了5 7 % s W对用户程序G t /读写的要求；

• 深入理解

上面的简单理解在网上随便找一篇都会讲到，但是6 ; ? K c F k )LT和ET真正使用起来，还是存在一定难度的。

• LT的读写操作

LT对于read操作比较简单，有read事件R W ! 1 ~ 3就读，读多读少都没有问题，但是wri+ @ H : g d (te就不那么容易了，一般来说socket在空闲状态时发送缓冲区一定是不满的，假如fd一直在监控中，那么会一直通知写事件，不胜其烦。

所以必i P E { I 2 R y须保证没有数据要发送的时候，要把fd的写事件监控从epoll列表中删除，需要的时候再加入回去，如此反复。

天下没有免费的午餐，总是无代价地提醒是不可能的G U F & s M k /，对应write的过度提醒，需要使用者随用随加，否则将一直被提醒可写事件。

• En h F & v ,T的读写操作

fd可读则返回U W ^ Z m _ !可读事件，G 8 M * D ; q B )若开发者没有把所有数据读取完毕，# P l x @ b N uepoll不会再次通知read事件，也就是说如果没有全部读取所有数据，那么导致epoll不会再通知该socket的read事件，事实上一直读完很容易做到。

若发送缓冲区6 / 2 B未满，epoll通知write事件，直到开发者填满发送缓冲区，epI R - X J noll才会在下次发送缓冲区由满变成未满时通知write事件。

ET模式下只有socket的状态发生变化时才会通知，也就是读取缓冲区由无数据到有数b { |据时通知readc B 9 #事件，发送缓冲区由满变成未满通知write事件。

• 一道面试题

使用Linux epoll模. K r O l q型的LT水平触发模` ; ` l式，当sockeS m $ m 0 6t可写& h g _ j r 0时，会不停的触发socket可写的事件，如何处理？

网络流传的腾讯面试题

这道题目对LT和ET考察比较深入，验证了前文说的LT模式write问题p [ Q 6 k w。

普通做法：

当需要向socket写数据时，将该socket加入到epoll等待可写事件。接收到socket可写事件后，调用write或send发送数据，当数据全部写完后， 将socket描述q $ # .符移出epoll列表，这种做法需要反复添加和删除。

改进做法:

向so u # - C Pcket写数据时直接调用send发送，当send[ [ f }返回错误码EAGAIN，才将socket加入到epol5 T Jl，等待可写事! N l m E ?件后再发送数据，全部数据发S U 6 T , O - p I送完毕，再移出epoll模型，改进的做法相当于认为c ~ w P ) ! e A isocket在大部分时候是可写的，不能写了再让ep( a foll帮忙监控。

上面两种做法是对LT模式下write事件j [ y频繁通知的修复，本质上E% C w 6 0T模式E } ) . H D a h就可以直接搞定，并不需要用户层程序的补i w l丁操作。

• ET模式的线程饥饿O T v $ +问题

如果某个socket源源r q 2 G O不断地收到非常多的数据，在试图读取完所有数据的过程中，有可能会造成其他的socO O $ B y c yket得不到处理，从而造成饥Y O K饿问题。

解决办法：为每个已经准备好的描述符维护一个队列，这 N R 样程序就可以知道哪些描述符已经准备好了但是并. e W Y . { d e 3没有被读取完，然后程序定时或定量的读取，= = = X L j c如果读完则移除，直到队列为空，这样就保证了每个fd都被读到并且不会丢失数据，流程如图:

• EPOLLONESHOT设置

A线程读完某socket上数据后开始处x S ` C V理这些数据，此时该socket上又有新数据可读，B线程被唤醒读新的数据，造成2个线程同时操作一个socket的局面 ，EPOLLONESHOT保证一个socket连接在任一时刻只被一个线程处理。

• 两种模式的选择

通过前面的对比) Z 2 t # D可以看到LT模式比较安全V V 2 D ? *并且代码编写也更清晰，但是ET模式属于高速模式，在处理大高并发场景使用得当效果更好，具体选择什么根据自己实际需要和团队代码能力来选择，如果并发很@ - k { W q c S y高且团队水平较高可以选择ET模式，否则建议LT模式。

ep, G y ] p D 5 w Uoll的惊群问题

在2.6.18内核中accept的惊群问题已经被解决了，但是在epoll中仍然存在惊群问题，表现起来就是当多个进程/线程调用. r = %epoll_wait时会阻塞等待，当内核x R A =触发可读写事件，所有进程/线程都会进行响} J w ( g / i 4应，但是实际上只有一个进程/线程真实处理这些事件。

在epoll官方没有正式修复这个问题之前，N[ 1 ~ m G c g Rginx作为知名使用者采用全局锁来限制每次可监听fd的进程数量，每次只有1个可监听的进程，后来在Linux 3.Y I W # y (9内核中增加了SO_REUSEP% ] @ G e 1 N 9 _ORT选项实现了内核级的负载均衡，Nginx1.9.1版本支持了reusg = * L S f , yeport这个新特性，从而解决惊群问题。

EPOLLEXCLS ! 7USIVE是在2016年Linux 4.5内核新添加的一个 epoll 的标识，Ngnix 在 1.11.3 之后添加了5 e Y 4 Q 0 1NGX_EXCLUSIVE_EVENT选项对该特性C _ X ) #进行支持。EPOLLEXCLUSIVE标识会保证一个事T T ~ ^ E r | # e件发生时候只有一个线程会被唤醒，以避免多侦听下的惊群问题。

参考资料

• http://harlon.org/2018/d M R 1 | V i y04/11/net8 ` C # =worksocket5/

• https://devarea.com/lN R H e Zinux-io-multiplexing-select-vs-poll-vs-epoll/#.Xa0sDqqFOUk

• https://jvns? X : 1 W D &.ca/blog/2017/06/03/async-io-on-linux--select--poll--and Q Y R Y F K-epoll/

• https://zhuanlE C 8 l S 5 -an.zhihu.com/p/78510741

• http://www.cnhalo.net/2016/07/13/linux-epoll/

• http6 . O ~ Y - 5 8s://www.ichenfu.com/20175 9 E C ^/05/03/proxy-epoll-tB V , ! H ^ 4 ahuk * K U C B Xndering-hb F t h gerd/

• https://github.com/torvalds/linux/commit/df0108c5da561c66c333bb46bfe3c1fc65905898

• https://simpleyyt.com/2017/06/25/how-ngnix-s_ h Q ! 2 Yolve-thundering-herd/