lryong

lryong 查看完整档案

深圳编辑  |  填写毕业院校  |  填写所在公司/组织 blog.herbert.top 编辑
编辑

专注于 Go 程序开发和技术进阶,包括操作系统、计算机网络、系统设计、算法数据结构和开发进阶。不定期分享在程序员道路上的思考和见解。

我的微信公众号:【程序开发进阶

欢迎同行朋友关注,我们一同交流,相互学习,共同成长!!

个人动态

lryong 赞了文章 · 3月27日

Linux IO模式及 select、poll、epoll详解

注:本文是对众多博客的学习和总结,可能存在理解错误。请带着怀疑的眼光,同时如果有错误希望能指出。

同步IO和异步IO,阻塞IO和非阻塞IO分别是什么,到底有什么区别?不同的人在不同的上下文下给出的答案是不同的。所以先限定一下本文的上下文。

本文讨论的背景是Linux环境下的network IO。

一 概念说明

在进行解释之前,首先要说明几个概念:
- 用户空间和内核空间
- 进程切换
- 进程的阻塞
- 文件描述符
- 缓存 I/O

用户空间与内核空间

现在操作系统都是采用虚拟存储器,那么对32位操作系统而言,它的寻址空间(虚拟存储空间)为4G(2的32次方)。操作系统的核心是内核,独立于普通的应用程序,可以访问受保护的内存空间,也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核(kernel),保证内核的安全,操心系统将虚拟空间划分为两部分,一部分为内核空间,一部分为用户空间。针对linux操作系统而言,将最高的1G字节(从虚拟地址0xC0000000到0xFFFFFFFF),供内核使用,称为内核空间,而将较低的3G字节(从虚拟地址0x00000000到0xBFFFFFFF),供各个进程使用,称为用户空间。

进程切换

为了控制进程的执行,内核必须有能力挂起正在CPU上运行的进程,并恢复以前挂起的某个进程的执行。这种行为被称为进程切换。因此可以说,任何进程都是在操作系统内核的支持下运行的,是与内核紧密相关的。

从一个进程的运行转到另一个进程上运行,这个过程中经过下面这些变化:
1. 保存处理机上下文,包括程序计数器和其他寄存器。
2. 更新PCB信息。
3. 把进程的PCB移入相应的队列,如就绪、在某事件阻塞等队列。
4. 选择另一个进程执行,并更新其PCB。
5. 更新内存管理的数据结构。
6. 恢复处理机上下文。

注:总而言之就是很耗资源,具体的可以参考这篇文章:进程切换

进程的阻塞

正在执行的进程,由于期待的某些事件未发生,如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等,则由系统自动执行阻塞原语(Block),使自己由运行状态变为阻塞状态。可见,进程的阻塞是进程自身的一种主动行为,也因此只有处于运行态的进程(获得CPU),才可能将其转为阻塞状态。当进程进入阻塞状态,是不占用CPU资源的

文件描述符fd

文件描述符(File descriptor)是计算机科学中的一个术语,是一个用于表述指向文件的引用的抽象化概念。

文件描述符在形式上是一个非负整数。实际上,它是一个索引值,指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时,内核向进程返回一个文件描述符。在程序设计中,一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于UNIX、Linux这样的操作系统。

缓存 I/O

缓存 I/O 又被称作标准 I/O,大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中,操作系统会将 I/O 的数据缓存在文件系统的页缓存( page cache )中,也就是说,数据会先被拷贝到操作系统内核的缓冲区中,然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

缓存 I/O 的缺点:
数据在传输过程中需要在应用程序地址空间和内核进行多次数据拷贝操作,这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

二 IO模式

刚才说了,对于一次IO访问(以read举例),数据会先被拷贝到操作系统内核的缓冲区中,然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。所以说,当一个read操作发生时,它会经历两个阶段:
1. 等待数据准备 (Waiting for the data to be ready)
2. 将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

正式因为这两个阶段,linux系统产生了下面五种网络模式的方案。
- 阻塞 I/O(blocking IO)
- 非阻塞 I/O(nonblocking IO)
- I/O 多路复用( IO multiplexing)
- 信号驱动 I/O( signal driven IO)
- 异步 I/O(asynchronous IO)

注:由于signal driven IO在实际中并不常用,所以我这只提及剩下的四种IO Model。

阻塞 I/O(blocking IO)

在linux中,默认情况下所有的socket都是blocking,一个典型的读操作流程大概是这样:
clipboard.png

当用户进程调用了recvfrom这个系统调用,kernel就开始了IO的第一个阶段:准备数据(对于网络IO来说,很多时候数据在一开始还没有到达。比如,还没有收到一个完整的UDP包。这个时候kernel就要等待足够的数据到来)。这个过程需要等待,也就是说数据被拷贝到操作系统内核的缓冲区中是需要一个过程的。而在用户进程这边,整个进程会被阻塞(当然,是进程自己选择的阻塞)。当kernel一直等到数据准备好了,它就会将数据从kernel中拷贝到用户内存,然后kernel返回结果,用户进程才解除block的状态,重新运行起来。

所以,blocking IO的特点就是在IO执行的两个阶段都被block了。

非阻塞 I/O(nonblocking IO)

linux下,可以通过设置socket使其变为non-blocking。当对一个non-blocking socket执行读操作时,流程是这个样子:
clipboard.png

当用户进程发出read操作时,如果kernel中的数据还没有准备好,那么它并不会block用户进程,而是立刻返回一个error。从用户进程角度讲 ,它发起一个read操作后,并不需要等待,而是马上就得到了一个结果。用户进程判断结果是一个error时,它就知道数据还没有准备好,于是它可以再次发送read操作。一旦kernel中的数据准备好了,并且又再次收到了用户进程的system call,那么它马上就将数据拷贝到了用户内存,然后返回。

所以,nonblocking IO的特点是用户进程需要不断的主动询问kernel数据好了没有。

I/O 多路复用( IO multiplexing)

IO multiplexing就是我们说的select,poll,epoll,有些地方也称这种IO方式为event driven IO。select/epoll的好处就在于单个process就可以同时处理多个网络连接的IO。它的基本原理就是select,poll,epoll这个function会不断的轮询所负责的所有socket,当某个socket有数据到达了,就通知用户进程。

clipboard.png

当用户进程调用了select,那么整个进程会被block,而同时,kernel会“监视”所有select负责的socket,当任何一个socket中的数据准备好了,select就会返回。这个时候用户进程再调用read操作,将数据从kernel拷贝到用户进程。

所以,I/O 多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符,而这些文件描述符(套接字描述符)其中的任意一个进入读就绪状态,select()函数就可以返回。

这个图和blocking IO的图其实并没有太大的不同,事实上,还更差一些。因为这里需要使用两个system call (select 和 recvfrom),而blocking IO只调用了一个system call (recvfrom)。但是,用select的优势在于它可以同时处理多个connection。

所以,如果处理的连接数不是很高的话,使用select/epoll的web server不一定比使用multi-threading + blocking IO的web server性能更好,可能延迟还更大。select/epoll的优势并不是对于单个连接能处理得更快,而是在于能处理更多的连接。)

在IO multiplexing Model中,实际中,对于每一个socket,一般都设置成为non-blocking,但是,如上图所示,整个用户的process其实是一直被block的。只不过process是被select这个函数block,而不是被socket IO给block。

异步 I/O(asynchronous IO)

inux下的asynchronous IO其实用得很少。先看一下它的流程:
clipboard.png

用户进程发起read操作之后,立刻就可以开始去做其它的事。而另一方面,从kernel的角度,当它受到一个asynchronous read之后,首先它会立刻返回,所以不会对用户进程产生任何block。然后,kernel会等待数据准备完成,然后将数据拷贝到用户内存,当这一切都完成之后,kernel会给用户进程发送一个signal,告诉它read操作完成了。

总结

blocking和non-blocking的区别

调用blocking IO会一直block住对应的进程直到操作完成,而non-blocking IO在kernel还准备数据的情况下会立刻返回。

synchronous IO和asynchronous IO的区别

在说明synchronous IO和asynchronous IO的区别之前,需要先给出两者的定义。POSIX的定义是这样子的:
- A synchronous I/O operation causes the requesting process to be blocked until that I/O operation completes;
- An asynchronous I/O operation does not cause the requesting process to be blocked;

两者的区别就在于synchronous IO做”IO operation”的时候会将process阻塞。按照这个定义,之前所述的blocking IO,non-blocking IO,IO multiplexing都属于synchronous IO。

有人会说,non-blocking IO并没有被block啊。这里有个非常“狡猾”的地方,定义中所指的”IO operation”是指真实的IO操作,就是例子中的recvfrom这个system call。non-blocking IO在执行recvfrom这个system call的时候,如果kernel的数据没有准备好,这时候不会block进程。但是,当kernel中数据准备好的时候,recvfrom会将数据从kernel拷贝到用户内存中,这个时候进程是被block了,在这段时间内,进程是被block的。

而asynchronous IO则不一样,当进程发起IO 操作之后,就直接返回再也不理睬了,直到kernel发送一个信号,告诉进程说IO完成。在这整个过程中,进程完全没有被block。

各个IO Model的比较如图所示:
clipboard.png

通过上面的图片,可以发现non-blocking IO和asynchronous IO的区别还是很明显的。在non-blocking IO中,虽然进程大部分时间都不会被block,但是它仍然要求进程去主动的check,并且当数据准备完成以后,也需要进程主动的再次调用recvfrom来将数据拷贝到用户内存。而asynchronous IO则完全不同。它就像是用户进程将整个IO操作交给了他人(kernel)完成,然后他人做完后发信号通知。在此期间,用户进程不需要去检查IO操作的状态,也不需要主动的去拷贝数据。

三 I/O 多路复用之select、poll、epoll详解

select,poll,epoll都是IO多路复用的机制。I/O多路复用就是通过一种机制,一个进程可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作。但select,poll,epoll本质上都是同步I/O,因为他们都需要在读写事件就绪后自己负责进行读写,也就是说这个读写过程是阻塞的,而异步I/O则无需自己负责进行读写,异步I/O的实现会负责把数据从内核拷贝到用户空间。(这里啰嗦下)

select

int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

select 函数监视的文件描述符分3类,分别是writefds、readfds、和exceptfds。调用后select函数会阻塞,直到有描述副就绪(有数据 可读、可写、或者有except),或者超时(timeout指定等待时间,如果立即返回设为null即可),函数返回。当select函数返回后,可以 通过遍历fdset,来找到就绪的描述符。

select目前几乎在所有的平台上支持,其良好跨平台支持也是它的一个优点。select的一 个缺点在于单个进程能够监视的文件描述符的数量存在最大限制,在Linux上一般为1024,可以通过修改宏定义甚至重新编译内核的方式提升这一限制,但 是这样也会造成效率的降低。

poll

int poll (struct pollfd *fds, unsigned int nfds, int timeout);

不同与select使用三个位图来表示三个fdset的方式,poll使用一个 pollfd的指针实现。

struct pollfd {
    int fd; /* file descriptor */
    short events; /* requested events to watch */
    short revents; /* returned events witnessed */
};

pollfd结构包含了要监视的event和发生的event,不再使用select“参数-值”传递的方式。同时,pollfd并没有最大数量限制(但是数量过大后性能也是会下降)。 和select函数一样,poll返回后,需要轮询pollfd来获取就绪的描述符。

从上面看,select和poll都需要在返回后,通过遍历文件描述符来获取已经就绪的socket。事实上,同时连接的大量客户端在一时刻可能只有很少的处于就绪状态,因此随着监视的描述符数量的增长,其效率也会线性下降。

epoll

epoll是在2.6内核中提出的,是之前的select和poll的增强版本。相对于select和poll来说,epoll更加灵活,没有描述符限制。epoll使用一个文件描述符管理多个描述符,将用户关系的文件描述符的事件存放到内核的一个事件表中,这样在用户空间和内核空间的copy只需一次。

一 epoll操作过程

epoll操作过程需要三个接口,分别如下:

int epoll_create(int size);//创建一个epoll的句柄,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);

1. int epoll_create(int size);
创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大,这个参数不同于select()中的第一个参数,给出最大监听的fd+1的值,参数size并不是限制了epoll所能监听的描述符最大个数,只是对内核初始分配内部数据结构的一个建议
当创建好epoll句柄后,它就会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close()关闭,否则可能导致fd被耗尽。

2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
函数是对指定描述符fd执行op操作。
- epfd:是epoll_create()的返回值。
- op:表示op操作,用三个宏来表示:添加EPOLL_CTL_ADD,删除EPOLL_CTL_DEL,修改EPOLL_CTL_MOD。分别添加、删除和修改对fd的监听事件。
- fd:是需要监听的fd(文件描述符)
- epoll_event:是告诉内核需要监听什么事,struct epoll_event结构如下:

struct epoll_event {
  __uint32_t events;  /* Epoll events */
  epoll_data_t data;  /* User data variable */
};

//events可以是以下几个宏的集合:
EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭);
EPOLLOUT:表示对应的文件描述符可以写;
EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);
EPOLLERR:表示对应的文件描述符发生错误;
EPOLLHUP:表示对应的文件描述符被挂断;
EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里

3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
等待epfd上的io事件,最多返回maxevents个事件。
参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create()时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。

二 工作模式

 epoll对文件描述符的操作有两种模式:LT(level trigger)ET(edge trigger)。LT模式是默认模式,LT模式与ET模式的区别如下:
  LT模式:当epoll_wait检测到描述符事件发生并将此事件通知应用程序,应用程序可以不立即处理该事件。下次调用epoll_wait时,会再次响应应用程序并通知此事件。
  ET模式:当epoll_wait检测到描述符事件发生并将此事件通知应用程序,应用程序必须立即处理该事件。如果不处理,下次调用epoll_wait时,不会再次响应应用程序并通知此事件。

1. LT模式

LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的。

2. ET模式

ET(edge-triggered)是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once)

ET模式在很大程度上减少了epoll事件被重复触发的次数,因此效率要比LT模式高。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

3. 总结

假如有这样一个例子:
1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符
2. 这个时候从管道的另一端被写入了2KB的数据
3. 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作
4. 然后我们读取了1KB的数据
5. 调用epoll_wait(2)......

LT模式:
如果是LT模式,那么在第5步调用epoll_wait(2)之后,仍然能受到通知。

ET模式:
如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志,那么在第5步调用epoll_wait(2)之后将有可能会挂起,因为剩余的数据还存在于文件的输入缓冲区内,而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候,调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。

当使用epoll的ET模型来工作时,当产生了一个EPOLLIN事件后,
读数据的时候需要考虑的是当recv()返回的大小如果等于请求的大小,那么很有可能是缓冲区还有数据未读完,也意味着该次事件还没有处理完,所以还需要再次读取:

while(rs){
  buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);
  if(buflen < 0){
    // 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读
    // 在这里就当作是该次事件已处理处.
    if(errno == EAGAIN){
        break;
    }
    else{
        return;
    }
  }
  else if(buflen == 0){
     // 这里表示对端的socket已正常关闭.
  }

 if(buflen == sizeof(buf){
      rs = 1;   // 需要再次读取
 }
 else{
      rs = 0;
 }
}

Linux中的EAGAIN含义

Linux环境下开发经常会碰到很多错误(设置errno),其中EAGAIN是其中比较常见的一个错误(比如用在非阻塞操作中)。
从字面上来看,是提示再试一次。这个错误经常出现在当应用程序进行一些非阻塞(non-blocking)操作(对文件或socket)的时候。

例如,以 O_NONBLOCK的标志打开文件/socket/FIFO,如果你连续做read操作而没有数据可读。此时程序不会阻塞起来等待数据准备就绪返回,read函数会返回一个错误EAGAIN,提示你的应用程序现在没有数据可读请稍后再试。
又例如,当一个系统调用(比如fork)因为没有足够的资源(比如虚拟内存)而执行失败,返回EAGAIN提示其再调用一次(也许下次就能成功)。

三 代码演示

下面是一段不完整的代码且格式不对,意在表述上面的过程,去掉了一些模板代码。

#define IPADDRESS   "127.0.0.1"
#define PORT        8787
#define MAXSIZE     1024
#define LISTENQ     5
#define FDSIZE      1000
#define EPOLLEVENTS 100

listenfd = socket_bind(IPADDRESS,PORT);

struct epoll_event events[EPOLLEVENTS];

//创建一个描述符
epollfd = epoll_create(FDSIZE);

//添加监听描述符事件
add_event(epollfd,listenfd,EPOLLIN);

//循环等待
for ( ; ; ){
    //该函数返回已经准备好的描述符事件数目
    ret = epoll_wait(epollfd,events,EPOLLEVENTS,-1);
    //处理接收到的连接
    handle_events(epollfd,events,ret,listenfd,buf);
}

//事件处理函数
static void handle_events(int epollfd,struct epoll_event *events,int num,int listenfd,char *buf)
{
     int i;
     int fd;
     //进行遍历;这里只要遍历已经准备好的io事件。num并不是当初epoll_create时的FDSIZE。
     for (i = 0;i < num;i++)
     {
         fd = events[i].data.fd;
        //根据描述符的类型和事件类型进行处理
         if ((fd == listenfd) &&(events[i].events & EPOLLIN))
            handle_accpet(epollfd,listenfd);
         else if (events[i].events & EPOLLIN)
            do_read(epollfd,fd,buf);
         else if (events[i].events & EPOLLOUT)
            do_write(epollfd,fd,buf);
     }
}

//添加事件
static void add_event(int epollfd,int fd,int state){
    struct epoll_event ev;
    ev.events = state;
    ev.data.fd = fd;
    epoll_ctl(epollfd,EPOLL_CTL_ADD,fd,&ev);
}

//处理接收到的连接
static void handle_accpet(int epollfd,int listenfd){
     int clifd;     
     struct sockaddr_in cliaddr;     
     socklen_t  cliaddrlen;     
     clifd = accept(listenfd,(struct sockaddr*)&cliaddr,&cliaddrlen);     
     if (clifd == -1)         
     perror("accpet error:");     
     else {         
         printf("accept a new client: %s:%d\n",inet_ntoa(cliaddr.sin_addr),cliaddr.sin_port);                       //添加一个客户描述符和事件         
         add_event(epollfd,clifd,EPOLLIN);     
     } 
}

//读处理
static void do_read(int epollfd,int fd,char *buf){
    int nread;
    nread = read(fd,buf,MAXSIZE);
    if (nread == -1)     {         
        perror("read error:");         
        close(fd); //记住close fd        
        delete_event(epollfd,fd,EPOLLIN); //删除监听 
    }
    else if (nread == 0)     {         
        fprintf(stderr,"client close.\n");
        close(fd); //记住close fd       
        delete_event(epollfd,fd,EPOLLIN); //删除监听 
    }     
    else {         
        printf("read message is : %s",buf);        
        //修改描述符对应的事件,由读改为写         
        modify_event(epollfd,fd,EPOLLOUT);     
    } 
}

//写处理
static void do_write(int epollfd,int fd,char *buf) {     
    int nwrite;     
    nwrite = write(fd,buf,strlen(buf));     
    if (nwrite == -1){         
        perror("write error:");        
        close(fd);   //记住close fd       
        delete_event(epollfd,fd,EPOLLOUT);  //删除监听    
    }else{
        modify_event(epollfd,fd,EPOLLIN); 
    }    
    memset(buf,0,MAXSIZE); 
}

//删除事件
static void delete_event(int epollfd,int fd,int state) {
    struct epoll_event ev;
    ev.events = state;
    ev.data.fd = fd;
    epoll_ctl(epollfd,EPOLL_CTL_DEL,fd,&ev);
}

//修改事件
static void modify_event(int epollfd,int fd,int state){     
    struct epoll_event ev;
    ev.events = state;
    ev.data.fd = fd;
    epoll_ctl(epollfd,EPOLL_CTL_MOD,fd,&ev);
}

//注:另外一端我就省了

四 epoll总结

在 select/poll中,进程只有在调用一定的方法后,内核才对所有监视的文件描述符进行扫描,而epoll事先通过epoll_ctl()来注册一 个文件描述符,一旦基于某个文件描述符就绪时,内核会采用类似callback的回调机制,迅速激活这个文件描述符,当进程调用epoll_wait() 时便得到通知。(此处去掉了遍历文件描述符,而是通过监听回调的的机制。这正是epoll的魅力所在。)

epoll的优点主要是一下几个方面:
1. 监视的描述符数量不受限制,它所支持的FD上限是最大可以打开文件的数目,这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左 右,具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。select的最大缺点就是进程打开的fd是有数量限制的。这对 于连接数量比较大的服务器来说根本不能满足。虽然也可以选择多进程的解决方案( Apache就是这样实现的),不过虽然linux上面创建进程的代价比较小,但仍旧是不可忽视的,加上进程间数据同步远比不上线程间同步的高效,所以也不是一种完美的方案。

  1. IO的效率不会随着监视fd的数量的增长而下降。epoll不同于select和poll轮询的方式,而是通过每个fd定义的回调函数来实现的。只有就绪的fd才会执行回调函数。

如果没有大量的idle -connection或者dead-connection,epoll的效率并不会比select/poll高很多,但是当遇到大量的idle- connection,就会发现epoll的效率大大高于select/poll。

参考

用户空间与内核空间,进程上下文与中断上下文[总结]
进程切换
维基百科-文件描述符
Linux 中直接 I/O 机制的介绍
IO - 同步,异步,阻塞,非阻塞 (亡羊补牢篇)
Linux中select poll和epoll的区别
IO多路复用之select总结
IO多路复用之poll总结
IO多路复用之epoll总结

查看原文

赞 636 收藏 1075 评论 65

lryong 关注了用户 · 3月26日

美团技术团队 @meituanjishutuandui

一个只分享有价值技术干货的微信公众号

美团技术团队会定期推送来自一线的实践技术文章,涵盖前端(Web、iOS和Android)、后台、大数据、AI/算法、测试、运维等技术领域。 在这里,与8000多业界一流工程师交流切磋。

关注 4973

lryong 发布了文章 · 3月18日

常见排序算法总结和 Go 标准库排序源码分析

前言

排序算法是数组相关算法的基础知识之一,它们的经典思想可以用于很多算法之中。这里详细介绍和总结 7 种最常见排序算法,并用 Go 做了实现,同时对比这几种算法的时间复杂度、空间复杂度和稳定性 。后一部分是对 Go 标准库排序实现的源码阅读和分析, 理解官方是如何通过将以上排序算法进行组合来提高排序性能,完成生产环境的排序实践。

排序算法分类

常见的这 7 种排序算法分别是:

  • 选择排序
  • 冒泡排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序

我们可以根据算法特点像复杂度、是否比较元素、内外部排序等特点对它们做分类,比如上面的算法都是内部排序的。一般可以基于算法是否比较了元素,将排序分为两类:

  1. 比较类排序:通过比较来决定元素间的相对次序。由于其平均时间复杂度不能突破$O(N\log N)$,因此也称为非线性时间比较类排序。
  2. 非比较类排序:不通过比较来决定元素间的相对次序。它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。主要实现有: 桶排序、计数排序和基数排序。

通过这个的分类,可以先有一个基本的认识,就是比较类排序算法的平均时间复杂度较好的情况下是 $O(N\log N)$(一遍找元素 $O(N)$,一遍找位置$O(\log N)$)。

注: 有重复大量元素的数组,可以通过三向切分快速排序, 将平均时间复杂度降低到 $O(N)$

比较类排序算法

因为非比较排序有其局限性,所以它们并不常用。本文将要介绍的 7 种算法都是比较类排序。

选择排序

原理:遍历数组, 从中选择最小元素,将它与数组的第一个元素交换位置。继续从数组剩下的元素中选择出最小的元素,将它与数组的第二个元素交换位置。循环以上过程,直到将整个数组排序。

时间复杂度分析:$O(N^{2})$。选择排序大约需要 $N^{2}/2$ 次比较和 $N$ 次交换,它的运行时间与输入无关,这个特点使得它对一个已经排序的数组也需要很多的比较和交换操作。

selection_sort

实现

// 选择排序 (selection sort)
package sorts

func SelectionSort(arr []int) []int {

    for i := 0; i < len(arr); i++ {
        min := i
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[min] {
                min = j
            }
        }

        tmp := arr[i]
        arr[i] = arr[min]
        arr[min] = tmp
    }
    return arr
}

冒泡排序

原理:遍历数组,比较并将大的元素与下一个元素交换位置, 在一轮的循环之后,可以让未排序i的最大元素排列到数组右侧。在一轮循环中,如果没有发生元素位置交换,那么说明数组已经是有序的,此时退出排序。

时间复杂度分析: $O(N^{2})$

buble_sort

实现:

// 冒泡排序 (bubble sort)
package sorts

func bubbleSort(arr []int) []int {
    swapped := true
    for swapped {
        swapped = false
        for i := 0; i < len(arr)-1; i++ {
            if arr[i+1] < arr[i] {
                arr[i+1], arr[i] = arr[i], arr[i+1]
                swapped = true
            }
        }
    }
    return arr
}

插入排序

原理:数组先看成两部分,排序序列和未排序序列。排序序列从第一个元素开始,该元素可以认为已经被排序。遍历数组, 每次将扫描到的元素与之前的元素相比较,插入到有序序列的适当位置。

时间复杂度分析:插入排序的时间复杂度取决于数组的排序序列,如果数组已经部分有序了,那么未排序元素较少,需要的插入次数也就较少,时间复杂度较低。

  • 平均情况下插入排序需要 $N^{2}/4$ 次比较以及 $N^{2}/4$ 次交换;
  • 最坏的情况下需要 $N^{2}/2$ 比较以及 $N^{2}/2$ 次交换,最坏的情况是数组都是未排序序列(倒序)的;
  • 最好的情况下需要 $ N-1$ 次比较和 0 次交换,最好的情况就是数组已经是排序序列。

insertion_sort

实现

// 插入排序 (insertion sort)
package sorts

func InsertionSort(arr []int) []int {
    for currentIndex := 1; currentIndex < len(arr); currentIndex++ {
        temporary := arr[currentIndex]
        iterator := currentIndex
        for ; iterator > 0 && arr[iterator-1] >= temporary; iterator-- {
            arr[iterator] = arr[iterator-1]
        }
        arr[iterator] = temporary
    }
    return arr
}

希尔排序

原理:希尔排序,也称递减增量排序算法,实质是插入排序的优化(分组插入排序)。对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素位置,每次只能将未排序序列数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性,通过交换不相邻的元素位置,使每次可以将未排序序列的减少数量变多。

希尔排序使用插入排序对间隔 d 的序列进行排序。通过不断减小 d,最后令 d=1,就可以使得整个数组是有序的。

时间复杂度:$O(dN*M)$, M 表示已排序序列长度,d 表示间隔, 即 N 的若干倍乘于递增序列的长度

shell_sort

实现

// 希尔排序 (shell sort)
package sorts

func ShellSort(arr []int) []int {
    for d := int(len(arr) / 2); d > 0; d /= 2 { 
        for i := d; i < len(arr); i++ {
            for j := i; j >= d && arr[j-d] > arr[j]; j -= d {
                arr[j], arr[j-d] = arr[j-d], arr[j]
            }
        }
    }
    return arr
}

归并排序

原理: 将数组分成两个子数组, 分别进行排序,然后再将它们归并起来(自上而下)。

具体算法描述:先考虑合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解,基本思路是将数组分解成leftright,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

归并算法是分治法 的一个典型应用, 所以它有两种实现方法:

  1. 自上而下的递归: 每次将数组对半分成两个子数组再归并(分治)
  2. 自下而上的迭代:先归并子数组,然后成对归并得到的子数组

时间复杂度分析: $O(N\log N)$

merge_sort

实现

// 归并排序 (merge sort)
package sorts

func merge(a []int, b []int) []int {

    var r = make([]int, len(a)+len(b))
    var i = 0
    var j = 0

    for i < len(a) && j < len(b) {

        if a[i] <= b[j] {
            r[i+j] = a[i]
            i++
        } else {
            r[i+j] = b[j]
            j++
        }

    }

    for i < len(a) {
        r[i+j] = a[i]
        i++
    }
    for j < len(b) {
        r[i+j] = b[j]
        j++
    }

    return r

}

// Mergesort 合并两个数组
func Mergesort(items []int) []int {

    if len(items) < 2 {
        return items

    }

    var middle = len(items) / 2
    var a = Mergesort(items[:middle])
    var b = Mergesort(items[middle:])
    return merge(a, b)

}

快速排序

原理:快速排序也是分治法的一个应用,先随机拿到一个基准 pivot,通过一趟排序将数组分成两个独立的数组,左子数组小于或等于 pivot,右子数组大于等于 pivot。 然后可在对这两个子数组递归继续以上排序,最后使整个数组有序。

具体算法描述

  1. 从数组中挑选一个切分元素,称为“基准” (pivot)
  2. 排序数组,把所有比基准值小的元素排到基准前面,所有比基准值大的元素排到基准后面(相同元素不对位置做要求)。这个排序完成后,基准就排在数组的中间位置。这个排序过程称为“分区” (partition)
  3. 递归地把小于基准值元素的子数组和大于基准值的子数组排序

空间复杂度分析:快速排序是原地排序,不需要辅助数据,但是递归调用需要辅助栈,最好情况下是递归 $\log 2N$ 次,所以空间复杂度为 $O(\log 2N)$,最坏情况下是递归 $N-1$次,所以空间复杂度是 $O(N)$。

时间复杂度分析

  • 最好的情况是每次基准都正好将数组对半分,这样递归调用最少,时间复杂度为 $O(N \log N)$
  • 最坏的情况是每次分区过程,基准都是从最小元素开始,对应时间复杂度为 $O(N^{^{2}})$

算法改进

  1. 分区过程中更合理地选择基准(pivot)。直接选择分区的第一个或最后一个元素做 pivot 是不合适的,对于已经排好序,或者接近排好序的情况,会进入最差情况,时间复杂度为 $O(N^{2})$
  2. 因为快速排序在小数组中也会递归调用自己,对于小数组,插入排序比快速排序的性能更好,因此在小数组中可以切换到插入排序
  3. 更快地分区(三向切分快速排序):对于有大量重复元素的数组,可以将数组切分为三部分,分别对应小于 pivot、等于 pivot 和大于 pivot 切分元素

quick_sort

实现

// 三向切分快速排序 (quick sort)
package sorts

import (
    "math/rand"
)

func QuickSort(arr []int) []int {

    if len(arr) <= 1 {
        return arr
    }

    pivot := arr[rand.Intn(len(arr))]

    lowPart := make([]int, 0, len(arr))
    highPart := make([]int, 0, len(arr))
    middlePart := make([]int, 0, len(arr))

    for _, item := range arr {
        switch {
        case item < pivot:
            lowPart = append(lowPart, item)
        case item == pivot:
            middlePart = append(middlePart, item)
        case item > pivot:
            highPart = append(highPart, item)
        }
    }

    lowPart = QuickSort(lowPart)
    highPart = QuickSort(highPart)

    lowPart = append(lowPart, middlePart...)
    lowPart = append(lowPart, highPart...)

    return lowPart
}

堆排序

原理:堆排序是利用“堆积”(heap)这种数据结构的一种排序算法。因为堆是一个近似完全二叉树结构,满足子节点的键值或索引小于(或大于)它的父节点。

具体算法描述

  1. 将待排序数组构建成大根堆,这个堆为初始的无序区
  2. 将堆顶元素 $R_{1}$ 与最后一个元素 $R_{n}$ 交换,此时得到新的无序区($R_{1},R_{2},...R_{n-1}$)和新的有序区($R_{n}$),并且满足 $R_{1,2,...n-1}<= R_{n}$
  3. 由于交换后新的堆顶 $R_{1}$可能违反堆的性质,需要对当前无序区调整为新堆,然后再次将 $R_{1}$与无序区最后一个元素交换,得到新的无序区 $R_{1},R_{2}...R_{n-2}$ 和新的有序区$R_{n-1},R_{n}$。不断重复此过程直到有序区的元素个数为$n-1$,则整个排序过程完成

时间复杂度分析:一个堆的高度为 $\log N$,因此在堆中插入元素和删除最大元素的时间复杂度为 $O(\log N)$。堆排序会对 N 个节点进行下沉操作,因为时间复杂度为 $O(N \log N)$

heap_sort

实现

// 堆排序 (heap sort)
package sorts

type maxHeap struct {
    slice    []int
    heapSize int
}

func buildMaxHeap(slice []int) maxHeap {
    h := maxHeap{slice: slice, heapSize: len(slice)}
    for i := len(slice) / 2; i >= 0; i-- {
        h.MaxHeapify(i)
    }
    return h
}

func (h maxHeap) MaxHeapify(i int) {
    l, r := 2*i+1, 2*i+2
    max := i

    if l < h.size() && h.slice[l] > h.slice[max] {
        max = l
    }
    if r < h.size() && h.slice[r] > h.slice[max] {
        max = r
    }
    if max != i {
        h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
        h.MaxHeapify(max)
    }
}

func (h maxHeap) size() int { return h.heapSize } 

func HeapSort(slice []int) []int {
    h := buildMaxHeap(slice)
    for i := len(h.slice) - 1; i >= 1; i-- {
        h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
        h.heapSize--
        h.MaxHeapify(0)
    }
    return h.slice
}

算法复杂度比较

下面是各排序算法的复杂度和稳定性比较:

排序算法时间复杂度(平均)时间复杂度(最好)时间复杂度(最坏)空间复杂度稳定性备注
选择排序$O(N^{2})$$O(N^{2})$$O(N^{2})$$O(1)$不稳定
冒泡排序$O(N^{2})$$O(N)$$O(N^{2})$$O(1)$稳定
插入排序$O(N^{2})$$O(N)$$O(N^{2})$$O(1)$稳定时间复杂度和初始顺序有关
希尔排序$O(N^{1.3})$$O(N)$$O(N^{2})$$O(1)$不稳定改进版插入排序
归并排序$O(N \log N)$$O(N \log N)$$O(N \log N)$$O(N)$稳定
快速排序$O(N \log N)$$O(N \log N)$$O(N^{2})$$O(N \log N)$不稳定
堆排序$O(N \log N)$$O(N \log N)$$O(N \log N)$$O(1)$不稳定无法利用局部性原理

注:

  • 稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 的前面。
  • 不稳定:如果 a 原本在 b 的前面,而 a=b,排序之后 a 可能会出现在 b 的后面。

对比这里排序的时间复杂度,归并排序、快速排序和堆排序的平均时间复杂度都是 $O(N \log N)$。但是再比较最坏的情况, 可以看到堆排序的下界也是 $O(N \log N)$,而快排最坏的时间复杂度是 $O(N^{2})$。 你可能会问,按分析结果来说,堆排序应该是实际使用的更好选择,但为什么业界的排序实现更多是快速排序?

实际上在算法分析中,大 $O$ 的作用是给出一个规模的下界,而不是增长数量的下界。因此,算法复杂度一样只是说明随着数据量的增加,算法时间代价增长的趋势相同,并不是执行的时间就一样,这里面有很多常量参数的差别,比如在公式里各个排序算法的前面都省略了一个$c$,这个$c$ 对于堆排序来说是100,可能对于快速排序来说就是10,但因为是常数级所以不影响大 $O$。

这里有一份平均排序时间的 Benchmark 测试数据(数据集是随机整数,时间单位 s):

数据规模快速排序归并排序希尔排序堆排序
1000 w0.751.221.773.57
5000 w3.786.299.4826.54
1亿7.6513.0618.7961.31

因为堆排序每次取一个最大值和堆底部的数据交换,重新筛选堆,把堆顶的X调整到位,有很大可能是依旧调整到堆的底部(堆的底部X显然是比较小的数,才会在底部),然后再次和堆顶最大值交换,再调整下来,可以说堆排序做了许多无用功。

总结起来就是,快排的最坏时间虽然复杂度高,但是在统计意义上,这种数据出现的概率极小,而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间,但是常量时间差很多。

Go 标准库排序源码分析

梳理完最常用的7种排序算法后,我们继续来看下 Go 在标准库里是怎么做的排序实现。

标准库的 sort 包的目录树如下(以 Go 1.15.5为例):

$ tree . 
.
├── example_interface_test.go // 提供对 []struct 排序的 example
├── example_keys_test.go // 根据 struct 里对某一字段的自定义比较,来对 []struct 排序的 example 
├── example_multi_test.go // 根据用户定义好的 less 方法做排序的 example
├── example_search_test.go // sort.Search 提供对排序数组二分查找某一元素的 example
├── example_test.go // 基本的各种数组排序的 example
├── example_wrapper_test.go // 对 sort.Interface 接口的实现 (封装),排序的 example
├── export_test.go
├── genzfunc.go
├── search.go // 二分查找的实现
├── search_test.go
├── slice.go
├── slice_go113.go
├── slice_go14.go
├── slice_go18.go
├── sort.go // 主要代码,提供对 slice 和自定义集合的排序实现
├── sort_test.go
└── zfuncversion.go

其中带有 example_* 前缀的文件是 sort 包的示例代码,有官方 example 来说明排序的使用方法。很有必要看一遍,可以理解 sort 包怎么使用,和在一些相对复杂场景下如何排序。

排序的主要代码在 sort.go 这个文件里。实现的排序算法有: 插入排序(insertionSort)、堆排序(heapSort)、快速排序(quickSort)、希尔排序(ShellSort)和归并排序(SymMerge)。

sort 包根据稳定性,将排序方法分为两类:不稳定排序和稳定排序

不稳定排序

不稳定排序入口函数是 Sort(data interface),为支持任意元素类型的 slice 的排序,sort 包定义了一个 Interface 接口和接受该接口参数类型的 Sort 函数:

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

只要排序数组的元素类型实现了 sort.Interface , 就可以通过 sort.Sort(data)进行排序。其中 maxDepth(n) 是快排递归的最大深度,也是快排切换堆排的阈值,它的实现:

// maxDepth returns a threshold at which quicksort should switch
// to heapsort. It returns 2*ceil(lg(n+1)).
func maxDepth(n int) int {
    var depth int
    for i := n; i > 0; i >>= 1 {
        depth++
    }
    return depth * 2
}

需要注意的一点是, sort.Sort 调用的 quickSort 排序函数,并不是最常见的快排(参考本文 3.6 小节), quickSort的整体框架比较复杂,流程如下:

func quickSort(data Interface, a, b, maxDepth int) {
    // a是第一个索引,b 是最后一个索引。如果 slice 长度大于 12,会一周走下面排序循环
    for b-a > 12 {
        // 如果递归到了最大深度, 就使用堆排序
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        // 循环一次, 最大深度 -1, 相当于又深入(递归)了一层
        maxDepth--
        // 这是使用的是 三向切分快速排序,通过 doPivot 进行快排的分区
        // doPivot 的实现比较复杂,a 是数据集的左边, b 是数据集的右边,
        // 它取一点为轴,把不大于中位数的元素放左边,大于轴的元素放右边,
        // 返回小于中位数部分数据的最后一个下标,以及大于轴部分数据的第一个下标。
        // 下标位置 a...mlo,pivot,mhi...b
        // data[a...mlo] <= data[pivot]
        // data[mhi...b] > data[pivot]
        mlo, mhi := doPivot(data, a, b)
        // 避免较大规模的子问题递归调用,保证栈深度最大为 maxDepth
        // 解释:因为循环肯定比递归调用节省时间,但是两个子问题只能一个进行循环,另一个只能用递归。这里是把较小规模的子问题进行递归,较大规模子问题进行循环。
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }

    // 如果元素的个数小于 12 个(无论是递归的还是首次进入), 就先使用希尔排序,间隔 d=6
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

这里 insertionSort 的和3.3节实现的插排的实现是一样的; heapSort 这里是构建最大堆,通过 siftDown 来对 heap 进行调整,维护堆的性质:

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
    root := lo
    for {
        child := 2*root + 1
        if child >= hi {
            break
        }
        if child+1 < hi && data.Less(first+child, first+child+1) {
            child++
        }
        if !data.Less(first+root, first+child) {
            return
        }
        data.Swap(first+root, first+child)
        root = child
    }
}

func heapSort(data Interface, a, b int) {
    first := a
    lo := 0
    hi := b - a

    // Build heap with greatest element at top.
    for i := (hi - 1) / 2; i >= 0; i-- {
        siftDown(data, i, hi, first)
    }

    // Pop elements, largest first, into end of data.
    for i := hi - 1; i >= 0; i-- {
        data.Swap(first, first+i)
        siftDown(data, lo, i, first)
    }
}

在上面快速排序的原理我们有提到过:如果每次分区过程,基准(pivot)都是从最小元素开始,那么对应时间复杂度为$O(N^{^{2}})$ , 这是快排最差的排序场景。为避免这种情况,quickSort 里的 doPivot 选取了两个基准,进行三向切分,提高快速排序的效率:doPivot 在切分之前,先使用 medianOfThree 函数选择一个肯定不是最大和最小的值作为轴,放在了切片首位。然后把不小于 data[pivot] 的数据放在了 $[lo, b)$ 区间,把大于 data[pivot] 的数据放在了 $(c, hi-1]$ 区间(其中 data[hi-1] >= data[pivot])。即 slice 会被切分成三个区间:

$$ \left\{\begin{matrix} data[lo, b-1) \\ data[b-1, c) \\ data[c, hi) \end{matrix}\right.$$

doPivot的实现如下:

// Quicksort, loosely following Bentley and McIlroy,
// ``Engineering a Sort Function,'' SP&E November 1993.

// medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
func medianOfThree(data Interface, m1, m0, m2 int) {
    // sort 3 elements
    if data.Less(m1, m0) {
        data.Swap(m1, m0)
    }
    // data[m0] <= data[m1]
    if data.Less(m2, m1) {
        data.Swap(m2, m1)
        // data[m0] <= data[m2] && data[m1] < data[m2]
        if data.Less(m1, m0) {
            data.Swap(m1, m0)
        }
    }
    // now data[m0] <= data[m1] <= data[m2]
}

func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
    m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
    if hi-lo > 40 {
        // Tukey's ``Ninther,'' median of three medians of three.
        s := (hi - lo) / 8
        medianOfThree(data, lo, lo+s, lo+2*s)
        medianOfThree(data, m, m-s, m+s)
        medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    }
    medianOfThree(data, lo, m, hi-1)

    // Invariants are:
    //    data[lo] = pivot (set up by ChoosePivot)
    //    data[lo < i < a] < pivot
    //    data[a <= i < b] <= pivot
    //    data[b <= i < c] unexamined
    //    data[c <= i < hi-1] > pivot
    //    data[hi-1] >= pivot
    pivot := lo
    a, c := lo+1, hi-1

    for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }
    // If hi-c<3 then there are duplicates (by property of median of nine).
    // Let's be a bit more conservative, and set border to 5.
    protect := hi-c < 5
    if !protect && hi-c < (hi-lo)/4 {
        // Lets test some points for equality to pivot
        dups := 0
        if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
            data.Swap(c, hi-1)
            c++
            dups++
        }
        if !data.Less(b-1, pivot) { // data[b-1] = pivot
            b--
            dups++
        }
        // m-lo = (hi-lo)/2 > 6
        // b-lo > (hi-lo)*3/4-1 > 8
        // ==> m < b ==> data[m] <= pivot
        if !data.Less(m, pivot) { // data[m] = pivot
            data.Swap(m, b-1)
            b--
            dups++
        }
        // if at least 2 points are equal to pivot, assume skewed distribution
        protect = dups > 1
    }
    if protect {
        // Protect against a lot of duplicates
        // Add invariant:
        //    data[a <= i < b] unexamined
        //    data[b <= i < c] = pivot
        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--
        }
    }
    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c
}

稳定排序

sort 包中使用的稳定排序算法为 symMerge, 这里用到的归并排序算法是一种原址排序算法:首先,它把 slice 按照每 blockSize=20 个元素为一个 slice,进行插排;循环合并相邻的两个 block,每次循环 blockSize 扩大二倍,直到 blockSize > n 为止。

func Stable(data Interface) {
    stable(data, data.Len())
}

func stable(data Interface, n int) {
    blockSize := 20 // 初始 blockSize 设置为 20
    a, b := 0, blockSize
    // 对每个块(以及剩余不足blockSize的一个块)进行查询排序
    for b <= n {
        insertionSort(data, a, b)
        a = b
        b += blockSize
    }
    insertionSort(data, a, n)

    for blockSize < n {
        a, b = 0, 2*blockSize
        // 每两个 blockSize 进行合并
        for b <= n {
            symMerge(data, a, a+blockSize, b)
            a = b
            b += 2 * blockSize
        }
        // 剩余一个多 blockSize 进行合并
        if m := a + blockSize; m < n {
            symMerge(data, a, m, n)
        }
        blockSize *= 2
    }
}

// SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
// Computer Science, pages 714-723. Springer, 2004.
//
// Let M = m-a and N = b-n. Wolog M < N.
// The recursion depth is bound by ceil(log(N+M)).
// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
// The algorithm needs O((M+N)*log(M)) calls to data.Swap.
//
// The paper gives O((M+N)*log(M)) as the number of assignments assuming a
// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
// in the paper carries through for Swap operations, especially as the block
// swapping rotate uses only O(M+N) Swaps.
//
// symMerge assumes non-degenerate arguments: a < m && m < b.
// Having the caller check this condition eliminates many leaf recursion calls,
// which improves performance.
func symMerge(data Interface, a, m, b int) {
    // Avoid unnecessary recursions of symMerge
    // by direct insertion of data[a] into data[m:b]
    // if data[a:m] only contains one element.
    if m-a == 1 {
        // Use binary search to find the lowest index i
        // such that data[i] >= data[a] for m <= i < b.
        // Exit the search loop with i == b in case no such index exists.
        i := m
        j := b
        for i < j {
            h := int(uint(i+j) >> 1)
            if data.Less(h, a) {
                i = h + 1
            } else {
                j = h
            }
        }
        // Swap values until data[a] reaches the position before i.
        for k := a; k < i-1; k++ {
            data.Swap(k, k+1)
        }
        return
    }

    // Avoid unnecessary recursions of symMerge
    // by direct insertion of data[m] into data[a:m]
    // if data[m:b] only contains one element.
    if b-m == 1 {
        // Use binary search to find the lowest index i
        // such that data[i] > data[m] for a <= i < m.
        // Exit the search loop with i == m in case no such index exists.
        i := a
        j := m
        for i < j {
            h := int(uint(i+j) >> 1)
            if !data.Less(m, h) {
                i = h + 1
            } else {
                j = h
            }
        }
        // Swap values until data[m] reaches the position i.
        for k := m; k > i; k-- {
            data.Swap(k, k-1)
        }
        return
    }

    mid := int(uint(a+b) >> 1)
    n := mid + m
    var start, r int
    if m > mid {
        start = n - b
        r = mid
    } else {
        start = a
        r = m
    }
    p := n - 1

    for start < r {
        c := int(uint(start+r) >> 1)
        if !data.Less(p-c, c) {
            start = c + 1
        } else {
            r = c
        }
    }

    end := n - start
    if start < m && m < end {
        rotate(data, start, m, end)
    }
    if a < start && start < mid {
        symMerge(data, a, start, mid)
    }
    if mid < end && end < b {
        symMerge(data, mid, end, b)
    }
}

// Rotate two consecutive blocks u = data[a:m] and v = data[m:b] in data:
// Data of the form 'x u v y' is changed to 'x v u y'.
// Rotate performs at most b-a many calls to data.Swap.
// Rotate assumes non-degenerate arguments: a < m && m < b.
func rotate(data Interface, a, m, b int) {
    i := m - a
    j := b - m

    for i != j {
        if i > j {
            swapRange(data, m-i, m, j)
            i -= j
        } else {
            swapRange(data, m-i, m+j-i, i)
            j -= i
        }
    }
    // i == j
    swapRange(data, m-i, m, i)
}

以上是稳定排序方法 Stable的全部代码。

排序 example

为应用 sort 包里排序函数 Sort不稳定排序),我们需要让被排序的 slice 类型实现 sort.Interface接口,以整形切片为例:

type IntSlice []int

func (p IntSlice) Len() int  { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

func main() {
 sl := IntSlice([]int{89, 14, 8, 9, 17, 56, 95, 3})
 fmt.Println(sl) // [89 14 8 9 17 56 95 3]
 sort.Sort(sl)
 fmt.Println(sl) // [3 8 9 14 17 56 89 95]
}

总结

本文主要详细介绍了我们常见的7种排序算法的原理,实现和时间复杂度分析,并阅读 Go 源码里 sort 包的实现,分析官方如何通过将以上排序算法进行组合来提高排序性能,完成生产环境的排序实践。

参考

查看原文

赞 18 收藏 10 评论 0

lryong 发布了文章 · 3月13日

Go 的容器数据结构

前言

Java 内置了丰富的容器类,不同容器用于处理各种业务场景。 Go 虽然语言设计上和 Java 有很多相似的地方, 但原生并没有支持太多容器类的数据结构,只有 map 和 slice。标准库的 container package 对容器数据结构做了扩展,支持堆(Heap)、链表(LinkedList) 和循环链表(Circular List)3个容器。

容器

熟悉 C++ 和 Java 对容器应该都有清晰的了解, 它是现代编程实践中不可或缺的一部分,具有多种形式, 一般被描述为具有操作容器内容的方法的对象。Go 提供的基本容器主要有6个:

  • 内置容器:

    • map: 关联容器
    • slice: 动态扩容的顺序容器
  • channels:队列
  • container标准库(pkg/container):

    • list:链表容器
    • ring:循环链表容器
    • heap: 堆容器,提供 heap 的实现

slice 、map 和 channel 是 Go 最常见、也是内置的容器数据结构,其他容器都在标准库的 container 包下。在使用 container 三个容器的时候,不必再费心实现数据结构相关的算法。同时,因为container 提供的容器支持的入参类型都是 interface{}, 所以只要实现了容器的 interface, 就可以处理任何类型的值。

container/list

链表容器 list 的代码是一个双向链表的实现。list 维护两个结构体:Element 和 List:

// Element is an element of a linked list.
type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // To simplify the implementation, internally a list l is implemented
    // as a ring, such that &l.root is both the next element of the last
    // list element (l.Back()) and the previous element of the first list
    // element (l.Front()).
    next, prev *Element

    // The list to which this element belongs.
    list *List

    // The value stored with this element.
    Value interface{}
}

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
    root Element // sentinel list element, only &root, root.prev, and root.next are used
    len  int     // current list length excluding (this) sentinel element
}

linked-list

当通过 list.New() 创建一个 list 时,会初始化一个 Element 作为 Root Pointer,它要么指向列表的初始元素,要么为 nil。每一个 Element 除了数据字段Value外,还有 prevnext 分别指向 直接前驱 和 直接后继, 来允许用户在 list 中前后移动元素。

list 容器支持的方法如下:

type Element
    func (e *Element) Next() *Element
    func (e *Element) Prev() *Element
type List
    func New() *List
    func (l *List) Back() *Element   // 最后一个元素
    func (l *List) Front() *Element  // 第一个元素
    func (l *List) Init() *List  // 链表初始化
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素后插入
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在某个元素前插入
    func (l *List) Len() int // 在链表长度
    func (l *List) MoveAfter(e, mark *Element)  // 把 e 元素移动到 mark 之后
    func (l *List) MoveBefore(e, mark *Element)  // 把 e 元素移动到 mark 之前
    func (l *List) MoveToBack(e *Element) // 把 e 元素移动到队列最后
    func (l *List) MoveToFront(e *Element) // 把 e 元素移动到队列最头部
    func (l *List) PushBack(v interface{}) *Element  // 在队列最后插入元素
    func (l *List) PushBackList(other *List)  // 在队列最后插入接上新队列
    func (l *List) PushFront(v interface{}) *Element  // 在队列头部插入元素
    func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列
    func (l *List) Remove(e *Element) interface{} // 删除某个元素

下面是 list 的一个简单例子:

package main

import (
    "container/list"
    "fmt"
)

func main() {
    // Create a new list and put some numbers in it.
    l := list.New()
    e4 := l.PushBack(4)
    e1 := l.PushFront(1)
    l.InsertBefore(3, e4)
    l.InsertAfter(2, e1)

    // Iterate through list and print its contents.
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Printf(".2d",e.Value)
    }

}

这段代码的输出是: 1234。在初始化 list 后,在尾结点插入4,在头结点插入1;再在4前插入3,在1后插入2,所以结果是1234。

list 在插入、删除数据的时间复杂度在 $O(1)$; 随机查找效率较低,为 $O(N)$ (slice 随机查找的时间效率为 $O(1)$

链表容器常见的应用场景是用于做 LRU 缓存

container/ring

循环链表容器 ring 是一个没有头节点和尾节点的链表,这里可以看成是一个简化版的 list。ring 维护一个结构体 Ring:

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

ring

但跟 list 不同的是 ring 的方法是不一样的:

type Ring
    func New(n int) *Ring  // 初始化环
    func (r *Ring) Do(f func(interface{}))  // 循环环进行操作
    func (r *Ring) Len() int // 环长度
    func (r *Ring) Link(s *Ring) *Ring // 连接两个环
    func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前(n 可以为负数)
    func (r *Ring) Next() *Ring // 当前元素的下个元素
    func (r *Ring) Prev() *Ring // 当前元素的上个元素
    func (r *Ring) Unlink(n int) *Ring // 从当前元素开始,删除 n 个元素

下面是 ring 的一个简单例子:

package main

import (
    "container/ring"
    "fmt"
)

func main() {

    // Create a new ring of size 5
    r := ring.New(5)

    // Get the length of the ring
    n := r.Len()

    // Initialize the ring with some integer values
    for i := 0; i < n; i++ {
        r.Value = i
        r = r.Next()
    }

    // Iterate through the ring and print its contents
    r.Do(func(p interface{}) {
        fmt.Printf("%d", p.(int))
    })

}

这段代码的输出是01234。 在初始化 ring 后, 对每个元素的 Value 赋值, 因为 ring 提供 Do 方法,所以遍历到当前元素的是时候,执行 Print 函数打印结果。

从 ring 的实现上可以知道相关操作的时间复杂度在$O(N)$。因为 ring 节点没有头尾区分和 FIFO 的特性,所以一个能用到的应用场景是环形缓冲区:在不消费资源的情况下提供对缓冲区的互斥访问 。

container/heap

堆(Heap)就是用数组实现的完全二叉树。根据堆的特性可以分为两种:最大堆和最小堆,两者的区别在于节点的排序方式上:

  1. 在最大堆中,父节点的值比每一个子节点的值都要大,堆最大元素在 root 节点
  2. 在最小堆中,父节点的值比每一个子节点的值都要小, 堆最小元素在 root 节点

Go 的堆容器 heap 在实现上是一个最小堆,heap 维护一个 Interface 接口:

// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

除了 出堆方法Push()和 入堆方法push(), Interface 内联了 sort.Interface, 它实现了三个方法:

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)

min-heap

只要实现了 Interface 方法的数据类型, 就满足构建最小堆条件:

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

通过 heap.Init() 函数构建一个最小堆(按先序遍历排序的 slice),内部实现的 up()down() 分别来对 堆来进行 上调整 和 下调整。

  • Push():当往堆中插入一个元素的时候,这个元素插入到最右子树的最后一个节点中,然后调用up() 向上保证最小堆。
  • Pop():当要从堆中推出一个元素的时候,先把这个元素和右子树最后一个节点交换,然后弹出最后一个节点,然后对 root 调用 down(),向下保证最小堆。

heap 容器支持的方法如下:

func Fix(h Interface, i int) // 在 i 位置更新数据,重建最小堆
func Init(h Interface) // 初始化,把 h 构建成最小堆 
func Pop(h Interface) interface{} // 出堆操作
func Push(h Interface, x interface{}) // 入堆操作
func Remove(h Interface, i int) interface{} // 移除第 i 个元素

下面是使用 heap 容器的一个例子, 构建一个优先级队列 pq:

package main

import (
    "container/heap"
    "fmt"
)

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority > pq[j].priority }

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}

func main() {
    items := map[string]int{
        "banana": 3,
        "apple":  2,
        "pear":   4,
    }

    pq := make(PriorityQueue, len(items))
    i := 0
    for value, priority := range items {
        pq[i] = &Item{
            value:    value,
            priority: priority,
            index:    i,
        }
        i++
    }
    heap.Init(&pq)

    // insert a new item
    item := &Item{
        value:    "orange",
        priority: 1,
    }
    heap.Push(&pq, item)
    pq.update(item, item.value, 5)

    fmt.Printf("\nheap length: %d\n", len(pq))
    for pq.Len() > 0 {
        i := heap.Pop(&pq).(*Item)
        fmt.Printf("%.2d:%s\t", i.priority, i.value)
    }
    fmt.Printf("\nheap length: %d\n", len(pq))
}

这段代码的输出是05:orange 04:pear 03:banana 02:apple。 首先是定义一个 PriorityQueue的结构体数组作为队列,有个 priority字段标识优先级,在 Less() 方法里比较两个元素的优先级,队列 update()用于更新元素的优先级。然后每次在执行 heap.Pop(&pq).(*Item)操作,会把最小堆里高priority元素出堆。

heap 在初始化的时候,时间复杂度在 $O(N)$;入堆、出堆、移动元素和重建最小堆的时间复杂度都是 $O(logN)$

堆容器在实际应用上是比较常见的, 在生产上经常用于实现优先级队列 和 高性能定时器。

小结

本文主要梳理了 Go 的 容器数据结构,分析标准库里 container包实现的三个容器:list、ring 还有较复杂的 heap, 介绍它们的实现、特性和使用场景。虽然 slice 和 map 作为在 Go 中是经常被使用到的容器,但如果在实际开发中发现这两个数据结构并不满足我们的需求,可以在 pkg/container 下搜索是否有可用到的数据结构。

参考

  1. container pkg
  2. Go Containers Explained In Color
  3. container — 容器数据类型:heap、list 和 ring
  4. Go Containers
  5. 堆 heap
  6. 数据结果--容器(集合)
  7. 数据结构:堆
  8. 数据结构|双向链表简单实现和图示
查看原文

赞 0 收藏 0 评论 0

lryong 发布了文章 · 2020-12-21

如何校验 email 地址以提高邮件送达率

背景

在发送 email 的时候,如果邮件收件人是一个不存在的 email 账号、或者收件人账号存在问题、收件箱无法接收 email, 那么 email server 就会将该无法接收的信息响应回来, 这种情况称之为 bounce email,对应的衡量指标是 bounce 率。bounce email 是影响邮件送达率(email delivery rate)的一个重要因素。根据 Sendgrid 统计结果, bounce 率在 5% 以上,送达率为71%;但如果 bounce 率在2%或以下,平均送达率可以提高到91%。

目前我们平台每个月邮件发送量在千万封左右,包括通知类和营销类邮件,其中 marketing campaigns 占了大部分。 因为 marketing campaigns 会让客户自定义 contacts,这部分是潜在 bounce email 的一个风险,所以在发送邮件前检测收件人 email 地址是否可送达,过滤掉其中的垃圾和无效的 email 地址,可以有效减少 bounce rate。这篇文章我们会详细介绍如何通过校验 email 地址以及最佳实践 , 来提高邮件送达率。

为什么 Bounce 影响 email 送达率

上面 Sendgrid 对 bounce email 的统计数据, 可以较明显地看出 bounce 率和送达率的相关关系。但其中的相关性不仅仅只是 bounce 占了总发送邮件数的比例大才影响送达率,而是 bounce 率高会进而影响到正常用户的邮件送达。

每一个 email 账号都有一个发件人信誉的分数(reputation),来帮助收件人的 email 服务提供商(ESP)决定邮件的质量。分数越高,邮件的送达率也会越高,反之亦然。如果频繁的 bounce ,会导致收件的 Email Server “质疑” 发件人邮箱账号是否为真实账号,当到达一定程度, 该 sender 账号会被列入各种 ESP 的垃圾邮件索引,最后发送给其他用户就会被 blocked。并且 bounce 会影响发件人 domain 和 ip 的 reputation。

所以 email bounces 可以说是 marketing campaigns 的一个“噩梦”。校验 email 地址有助于将邮件发送给正确的收件人,同时使 email 帐户保持可用状态,并提高 reputation。对业务来说,也会提升 email campaign 的质量。

如何校验 email 地址

完整的 email 地址的校验过程主要包括以下4个维度:

  1. 语法检查
  2. 检查是否为一次性邮箱(disposable)
  3. 确认 domain 对应 DNS 记录是否存在
  4. Ping 收件人邮箱

语法检查

拼写的语法错误是 email 地址检查最常见的问题之一。 根据常用的 email 地址正则表达式,可以确认出地址是否有格式问题。一般检查的表达式类似于 abc@aftership.com, 包括3个部分: local part 、@分隔符 和 domain。

较重点检查的是 local part 部分,由以下3部分组成:

  • 字母数字 – A 到 Z(包括大小写), 0-9
  • 可打印字符 – !#$%&'*+-/=?^_~`
  • 一个标点符号. – 但是 local part 不能以 . 开头或结尾、或者连续使用,比如 example..dot@aftership.com是一个非法的 email 地址。

不同的 email 服务提供商对 local part 有不同的规定,这里 mailgun 提供了一份常见 ESP 的 校验规则

domain 跟对域名的命名约定是一致的:包括只使用字母数字和-符号且不能连续使用。

除了根据正则表达式对 email 地址做检查,还需要考虑的一些点是 IETF 标准non-ASCII domains

检查是否为一次性邮箱

一次性邮箱是指那些小段时间内有效的 email 地址,被称作 disposable email。 disposable email 是一个正确语法的地址,且可以接收和发送 email, 正常只能用一次,一般是用来注册新账号绕过登录、发送恶意邮件等场景。

常见的 disposable email 提供商包括 Nada 和 Mailinator 等。识别它们的方法是判断 domain 是否为disposable domain。目前开源社区有维护一些实时更新的 disposable domain 列表, 通过在列表里搜索 domian 的方式快速过滤掉 diposable email。

确认 domain 对应 DNS 记录是否存在

DNS 查询是指向 DNS 服务器请求 DNS 记录的过程。DNS 记录包括多种 domain 记录,这里我们主要确认 MX record(_mail exchanger record, 邮件交换记录_)。该解析记录用来指定 email server 接收特定域名的 email。举个例子,我们对 aftership.com 查询 DNS 记录如下:
image

可以看到 aftership.com对应有4条 MX 记录。MX 记录存在表示 domain 对应的 ESP 是存在, 否则不是一个有效的 email 地址。

Ping 收件人邮箱

确认完 MX record 记录存在, 可以通过与 SMTP server 建立连接,来完成对 email 地址有效性的校验。如上一步所示,MX records 一般会有多条(_有的 SMTP server 会设置 record 的权重值_),SMTP server 的地址是: MX 记录 + SMTP Relay 端口。 Ping 收件人邮箱的原理是使用 SMTP ,连接到其中有效的 SMTP server,并请求收件人地址,请求后 server 会有响应, 根据响应信息来判断地址是否存在。

如果 SMTP server 响应 250 OK, 那么这个 email 地址是可能就是一个有效地址;如果返回 550-5.1.1 类似错误那么就是一个无效的地址。

example@aftership.com 这个 email 地址为例, 下面是一个完整的 SMTP 连接的验证过程。
image

首先 telnet 连上收件人的 SMTP server, 通过 ehlo 标识发件人的身份,mail 设置 email 的发件人,最后 rcpt 设置 email 的收件人, rcpt只能设置 SMTP domain 的 email 地址, 否则分类器(SMTP rewriter)会重写邮件中的电子邮件地址,使其与主 SMTP 地址相匹配 。如果 rcpt 没有拒绝该请求,表明 SMTP server 校验通过该地址,将会把收件人添加到邮件列表。下图是一张使用 SMTP 协议发送 email 的全流程图:
image
SMTP Ping 收件人地址的方法,是整个 email 地址校验过程可能最有效的一环,SMTP server 能帮你确认收件人是否存在和可达。需要注意到这里所说的“可能”,比如 example@aftership.com其实是一个无效的地址, rcpt 响应250,email 地址不一定是可达的。

这里又涉及一个概念,是 Catch-All Email Server,也叫 accept-all server,指那些被配置为接受所有发送到 domain 的 email 的 SMTP server,无论指定的 email 地址是否存在。catch-all 会将错误地址重定向到一个通用的邮箱,以定期审查,但是带来的问题是提高 bounce 率的风险且 catch-all 地址无法被正确校验。( 比如 Gmail 是一个 catch-all email server )
所以 Ping 收件人邮箱来校验地址有效性, 需要确保对方的 SMTP server 是非 catch-all email server, rcpt命令响应250,才能说明地址是 deliverable,否则无法校验可达性。

更多关于连上 SMTP 服务器后校验过程的其他细节,比如为什么是用 rcpt 而不是其他命令来验证地址,可以参考 Email box pinging

什么时候需要校验 email 地址

校验 email 地址可以不是一个经常性的过程, 建议有下面几种情况时必须进行校验:

  1. 新增的 email 地址: 正如上面提到的, 在进行 marketing campaign 时必须对 contacts 新增的收件人列表校验 email 地址,过滤无效和非法收件人账号
  2. 超过一个月未重新校验过的 email 地址
  3. bounce 率达到或者超过 2%: 设置 bounce 率阈值来确保邮件送达率, 提高 sender 的 reputation
  4. 统计到的 email 事件,email 被打开的概率比较低

本地验证 emil 地址 vs 使用第三方 email 验证服务

经过以上步骤来完整地校验 email 列表,哪怕只有一个地址的验证也要多花不少时间。但是也可以不必进行手动验证,因为有许多第三方的 email 校验服务,一般有提供 API 来完成对地址的校验。调研了几个类似服务(比如 emailchecker),它们提供的功能主要包括以下几点:

  1. domain 校验
  2. 单个 email 地址校验
  3. 批量 email 地址校验
  4. 语法检查
  5. SMTP 校验 (Ping收件人邮箱)
  6. 提供校验 API
  7. bounce email 检测
  8. GDPR 数据保护

所以这两种验证方案哪一个是更好的选择呢?本地验证 email 地址无疑是首选, 因为自行校验其实更快,更好地支持批量校验邮件列表;要注意的是很多较好的第三方验证服务是付费的,在线验证时需要确认服务是否有 GDPR 数据保护以确保不会与第三方共享用户个人数据,或者存在安全问题,但是第三方校验不会有各种限制(多数 ISP 禁止在 25 端口上建立出站连接),且不存在影响 IP 段 和域名 reputation 的风险。

email-verifier

如果是本地验证 email 地址,目前社区其实有一些开源的验证 email 地址的工具, 其中 stars 数最多是 trumail 项目,它提供了地址校验 API。但是这个项目有两个问题, 一是校验慢,性能有些问题;二是不支持 disposable domain 的校验,且该项目 archived, 已不再维护。

在开发和维护 Messages Platform 上,作为平台方,我们除了对业务提供高可用、简单易接入的 email 消息通道服务外,降低 bounce 率和提高邮件送达率也是我们重要的指标之一。所以我们需要有一个高效的邮件校验服务,过滤非法 email 地址(平台邮件平均发送量在1000+w封/月),以提高送达率。基于我们的技术栈是 Go, 在调研了 git 社区其他开源的 email 验证工具后,发现 Go 项目对 email verifier 这一块建设是相对缺失,暂时还没有一个既提供多维度的 email 检查(包括 diposable domain, 和 Role Account 等)且校验地址可达性的工具。

由于 trumail 已不再维护,所以我们内部实现了一个新的 email 校验库 – email-verifier, 目前已经在线上环境上运行。对比 trumail, 校验 email 地址的效率更加明显,检查维度更多。

相比于现有其他的 email 地址校验工具, 我们提供高性能、多维度、高准确性的免费 email 地址校验方案,来解决在不同场景下对 email 地址校验的痛点问题。 期待 email-verifier 也能在更好地帮助到社区解决类似问题。

总结

本文主要从 bounce email 引入,详细介绍了如何在不发送邮件情况下来校验 email 地址,同时给出合适时间点校验 email 地址的几个建议;对比本地校验和第三方校验服务两者的优缺点以及为什么我们会选择自建校验服务的原因。最后是我们在这一过程中,基于校验原理孵化的一个检测工具。

一般来说, Marketing Campaigns 展开之后,肯定会遇到 bounce email 影响 campaigns 质量的问题,这个时候在发邮件前校验地址有效性的优点就不难理解:一是提高邮件送达率;二是维护和提高 sender 账号的 reputation,对业务方和平台方都是必要的。

参考

查看原文

赞 20 收藏 17 评论 2

lryong 赞了文章 · 2020-10-23

分享我成为GDE(Google开发者专家)的经历

本文同步发表于我的微信公众号,扫一扫文章底部的二维码或在微信搜索 郭霖 即可关注,每个工作日都有文章更新。

经过一段漫长且复杂的申请过程,我的GDE申请总算是顺利通过了。

很荣幸现在我成为了国内第二位Android GDE(第一位是朱凯),而我想写一篇文章将整个过程分享出来,同时向国内的开发者们普及一下什么是GDE,以及如何去申请。

引子

今年4月,Android 11的Beta版即将上线之际。

鸿洋在微信上找我:老郭,最近有Google的那边的人联系你么?

我:没有啊,咋了?

鸿洋:有个说是和Google合作的传播伙伴,正在做Android 11面向开发者群体的传播规划,想要找国内影响力比较大的Android公众号来帮忙推广传播。

我:那可能是我的影响力还不够大吧

鸿洋:他们说在公众号找过你,你没有回复他们。

我:。。。。

鸿洋:那我把你的微信发给他们,让他们直接联系你。

一场奇妙的旅程就这么开始了。

与Google建立联系

话说我在国内的Android技术社区也算是活跃很多年了,写过百余篇博客,写过三本书,写过不少开源项目。但Google官方从来没有联系过我,我也没有主动联系过Google。当然,我不去主动联系Google是因为我不知道是否可以联系上Google,所以这次能够和Google建立联系我是很开心的。

至于去帮助Google做Android 11方面的推广,这点我当然是非常乐意的。毕竟从毕业以来我就一直在做Android方向的开发工作,既然是吃这碗饭的,帮助Google推广技术自然是义不容辞的事情。

本来我以为这件事情很简单,就是Google官方开发者公众号发布了一些Android 11的文章,我这边帮忙转发一下就可以了,然而事实并不是如此。

Google联系我之后表示,希望我可以参加7月4号在上海举办的Android 11 Meetup活动,并进行主题演讲。由于疫情的原因,这也是Google今年的第一场线下开发者活动。

这个邀请对于我来说是有点突然的,平时我都是以写博客、写书为主,最多是开几场Live Coding直播,几乎没有参加过任何线下主题演讲。但是换个角度想想,能受到Google官方的邀请,这也是对我的一种认可,如果拒绝的话就显得太不礼貌了,所以貌似我也就只剩一种选择了:好好准备!

由于演讲的内容要围绕Android 11展开,我大致翻阅了一下Android官网关于Android 11的新特性和行为变更,发现了一个比较有意思的点:AsyncTask在Android 11当中被废弃了。

AsyncTask可以说是陪伴了广大Android开发者许多年,一直以来都可以很好地帮助我们进行异步任务处理。那么为什么在Android 11当中这个类被废弃了呢?因为现在Google有了更加推荐的异步任务处理方式:协程。所以,我的演讲主题也就这么确定下来了。

首次线下演讲对于我来说还是相当紧张的,并且由于是Google官方的活动,我可不想在演讲中出现什么技术性的错误,要不然丢人就丢大了,因此必须进行非常全面的准备。

我上网参考了大量关于协程的文章,认真学习和总结,把之前没能掌握或者是有疑惑的知识点逐个击破。另外还编写了许多Demo程序,对这些知识点进行测试验证,以加深理解。

除了技术方面的准备,我还要思考演讲的内容划分,时间分配(事实证明我一直不擅长这个),甚至还学会了做PPT。

最终,Android 11 Meetup上海站的活动举办得相当成功,线下名额全部报满,线上一共11000人观看,并且普遍收到了大家的好评。想看这次活动回放的朋友可以 点击这里

活动结束后,在Google一直负责和我联络的Tracy也在说:你讲得太好了,赶快去申请GDE吧!

恩?GDE?

什么是GDE

GDE的全称是Google Developer Expert,是Google在全球范围内开展的一个开发者专家认证项目。如果你对Google的某个技术领域非常擅长,同时在这个领域有比较高的影响力的话,那么就有可能成为Google官方认证的开发者专家。

由于我知道绝大部分的国内开发者对于GDE的了解可能都很少,因此这里我就给大家做一个比较详细的科普。

众所周知,Google是一家崇尚技术的科技公司,Google也经常会推出许多面向开发者的技术产品。开发者对于Google的整体生态来说是非常重要的一环。

在Google推出的这些技术产品中,某些影响力比较大且比较成功的技术,Google就会为其提供专家认证服务(GDE)。因此,GDE是有很多个领域的。当然,这些领域也会随着Google的技术迭代一直在变化。

目前Google一共提供了16个技术领域的GDE认证,如下图所示。

这些技术基本也代表着Google当下最热门的技术方向。

那么或许有的小伙伴会好奇,成为GDE具体有什么好处呢?

我感觉最主要的好处就是能够得到一个Google官方的认可,相当于官方承认你是这个领域的专家了。虽然Google不会直接发你钱,但是你完全可以借助这个Title去尝试获得更高的薪水,甚至是自主创业。

并且,成为GDE之后,你将可以和Google建立直接的联系,在技术方面有什么问题可以向Google的员工进行咨询,还能获得一些Google未发布产品的内部试用资格。

Google可能也会向你寻求一些技术建议,比如我最近就被问到,希望Android 12中可以增加哪些新功能?(当然我也没能给出什么有建设性的建议,如果你有什么功能是非常希望Android 12中加入的,可以告诉我,我再转告给Google。)

除了以上好处之外,直接经济上的好处也是有一些的。比如说,GDE将有很大的概率被邀请去参加每年的Google I/O大会(这也是我申请GDE的最主要原因),并且Google会帮你承担所有的门票、机票、酒店的费用。另外,JetBrains向所有GDE提供了免费的全家桶产品,原价大概200多美元一年吧,像我平时偶尔会用RubyMine写写服务器程序,现在这部分钱就能省下来了。

那么目前全球一共有多少位GDE呢?这个数字是一直在变化的。因为每天可能都会有新的GDE加入,但同时,GDE的身份并不是一直有效的,而是只有一年有效期,Google会在第二年重新评估你是否仍然具备GDE的资格,所以,每天可能又会有人失去GDE的身份。

截至我编写文章的时候,全球一共有843位GDE,分布于上图中的16个技术领域,其中Android GDE一共有109位。

Google在其开发者官网上有一个专门的页面,展示了所有的GDE,以及他们的详细信息,地址是:

https://developers.google.com/community/experts/directory

另外这个页面上还会使用Google地图来标注出每个GDE所在的位置,如下图所示。

从上图我们可以看出,中国其实是有很多位GDE的。

事实上,中国目前一共有30位GDE,但绝大多数的GDE都是Machine Learning这个领域的(24位)。而Android领域就比较少了,目前只有两位,并且我是最近才刚刚认证上的。

那么接下来,我就向大家详细介绍一下我的GDE申请过程。

如何申请GDE

受到了Google的邀请之后,我就开始了我的GDE申请之旅。

从开始申请到最终成为GDE,我经历了大概一个月左右的时间。据说这已经算是非常快的了,有些GDE甚至经历了半年之久的申请过程。

GDE的申请过程相当复杂,而且对申请人的要求很多。不过我最终总结下来,主要要求无非就是两点:技术和影响力。

技术自然不用多说,你既然申请成为这个领域的专家,没技术肯定是不行的。

影响力是Google非常看重的一点,就是你光有技术还不行,你还必须在这个领域上有比较大的影响力,Google才可能会授予你GDE的称号。

而影响力又可以再具体划分成以下几点:公开演讲(尤其重要),博客,书,视频教程,开源项目。

其中,公开演讲是最最重要的一环,因为Google特别看重你在线下技术社区的参与度。另外其他几个部分都是加分项,越多越好,上不封顶。

当你认为你具备了所有成为一名GDE的条件之后,就可以去尝试申请GDE了。不过,申请GDE还需要一位引荐人,并且引荐人必须是Google员工才行,这里我要特别感谢Google的钟辉老师愿意帮我引荐。

那么你可能会说,我上哪有什么机会去认识Google员工帮我引荐啊?没错,所以首先你自身还是要有比较大的影响力才行,有了影响力自然就会有机会认识Google员工(主动或被动都有可能)。或者你也可以联系其他GDE帮助你引荐,比如说我。

当你获得了引荐资格之后,会有专门负责GDE项目的Google员工与你进行对接。首先他会发你一个链接,让你在这个网页上填写申请资料,注意必须全部都用英文填写。

填写申请资料大概是我申请GDE过程中最痛苦的一个部分,因为要填的内容实在是太多了。

我记得有两个部分是需要你非常详细地去填写的:个人介绍和申请原因。

个人介绍是让Google快速了解你的最佳途径,因此你需要将自己最有优势的一面展现出来,让Google知道你有多出色。另外,假如你能顺利成为一位GDE的话,在这里填写的内容,最终也会成为你的GDE专属页面上的个人介绍。

下图是我的GDE专属页面。

而申请原因要如何填写就不太好说了,我不清楚Google会如何评估这部分资料,甚至不清楚Google想要从申请原因中获取怎样的信息。但根据我的大体猜测,不应该在申请原因中填写太过功利性的目的,因为成为GDE本身就是一个无经济收益的事情,Google更希望看到的是你愿意在开发者社区中无偿做出贡献的态度。

总之,关于申请原因这块,我相信1000个人就会有1000种写法,只要你的原因是充分合理的即可,并没有什么所谓的标准答案,因此这里我就不把当初我写的申请原因分享出来了。

将上述两大块内容填写完成之后,接下来就到了要你使劲吹牛的时间:证明你的影响力。注意这里我并没有开玩笑的意思,因为Google想要确切地知道你的影响力到底有多大,所以你有任何值得吹嘘的地方,都要尽可能地写上。

关于影响力这块的资料填写,主要分为线下影响力、内容创作、项目贡献这3个块面。

线下影响力就是指你参加过哪些线下开发者活动,发表过多少次演讲,总共影响到了多少人,Google和非Google的活动都可以。当然,由于今年疫情的原因,许多开发者活动变成了线上举行,所以这部分内容的填写今年变得相对灵活了一点,一些线上演讲也可以算到里面。

内容创作是指你创作过哪些与Google技术相关的内容,这些内容影响到了多少开发者,主要包括博客、书、视频教程等等。这部分内容的填写对于我来说就非常有优势了,因为我的博客访问量以及书的销量都是相当可观的,所以可以在这个地方好好吹一波。

最后项目贡献这部分我的理解是开源项目的贡献,不知道在公司开发的商业项目能不能算到里面。总之你需要把你做过哪些拿得出手的项目都填写上去,然后这些项目在开发者群体中有多大的影响力(如star数量)也要告诉Google,好让Google对你可以有一个更加综合的评估。

我印象中要填写的申请资料主要就是这些了,由于全部都要用英文来填写,所以还是挺花时间的,我大概用了一周左右的时间才全部填写完成。

申请资料填写完成之后,点击提交审核,你的GDE申请之旅就正式起飞了。

面试

不过填写申请资料仅仅只是GDE申请的开始,接下来还有重重考验在等着你。

在你提交完申请资料之后,将会立即收到一封邮件,告诉你成为一名GDE需要经历哪些步骤。

一共是五步,详情见下图:

第一步是资格审查。Google会先对你的申请资料进行评估,确保你的资历足以担当得起GDE这个名号,不然可能在资格审查这一轮就会被刷掉。当然我认为这个概率很小,因为申请GDE都是需要Google员工引荐的,如果资历不够的话,首先他就不会引荐你。

过了资格审查这一关,接下来就会进入第一轮面试。第一轮Google会安排一位与你申请领域相同的GDE作为你的面试官,这位面试官可能来自于世界上任何一个国家,所以你要做好他的英语口音不标准的心理准备。不过在英语方面也不需要太过担心,毕竟你是在申请GDE而不是在做英语考试。只要你能听得懂对面在问什么,并且能用英语把自己想说的话表达出来就可以了,听不懂的地方可以多问几遍Pardon?面试官是不会介意的。

我的一轮面试官是一位来自印尼雅加达的GDE:Andrew Kurniadi。

Google会通过邮件让我们俩建立会话,然后我们自行沟通面试时间就可以了。以下是部分沟通细节:

面试的具体内容我就不能跟大家透漏了,其实无非就是我前面跟大家总结的两个点:技术和影响力,一切都是围绕这两个点展开的。

Andrew是一位相当友好的GDE,在开始面试前我一直比较担心我的英语口语到底行不行,面试结束后他告诉我完全不需要担心英语的问题,因为他觉得我的英语非常棒。一位好的GDE果然非常善于鼓励人。

首轮面试结束之后,面试官应该会根据面试的结果填写总结报告并提交给Google,具体是怎么操作的我就不清楚了,Andrew在面试的时候有跟我解释,但其实我并没有怎么听懂。

总之,我大概是在首轮面试两天之后收到了面试通过的邮件,与此同时Google会帮你安排第二轮面试。

第二轮面试的面试官将会是一名Google员工,这次我的运气比较好,Google帮我安排了一名中国区的Google员工来帮我面试,就是我们国内Android圈非常知名的陈卓老师。

由陈卓老师来帮我面试算是有利有弊吧,好处就是我最担心的语言障碍没有了,总算可以比较舒适地问答了。坏处就是,由于没有了语言障碍,面试官可以向你问更多更复杂的问题,并且你不能再以听不懂当作借口了。

我的一轮面试只花了30分钟左右的时间,而二轮面试足足花了一个小时,可能也是和陈卓老师聊得比较投缘吧

同样,我不能将二轮面试的具体内容分享出来,但大体无非还是围绕着我前面提到的那两点展开的。

两轮面试都通过了之后,你离GDE就只差一步之遥了:签署保密协议和服务与条款。

这两项虽然已经不是什么考核内容了,但却是你成为GDE的必备前提条件。我当时就因为服务与条款邮件莫名其妙进入了垃圾邮箱,导致我没看到这封邮件,然后GDE的申请进度就一直卡在那里,白白多等了一个多星期。

关于保密协议这块,因为GDE是有可能获取到一些Google的内部信息的,另外还能得到一些Google未发布产品的试用资格,为了防止这些机密信息被泄漏出去,所有GDE都必须签署保密协议才行。由于签署了保密协议,我在写本文时也比较谨慎,不过以上所有信息和截图都是我在签署保密之前就可以获取到的,所以应该不会触犯保密协议的规则。

而服务与条款这块,就是Google要和每一位GDE进行的一系列约定,哪些事情你可以做,哪些事情你不可以做。比如你不可以代表Google的立场去发表任何声明,还有你不可以向Google索要薪水等等。

Welcome On Board

以上所有环节全部通过之后,恭喜,你就正式成为一名GDE了。如果你还有点太敢相信的话,检查一下你的邮箱,将会看到这样一封邮件:

成为GDE之后,你将会收到一大堆Google发来的资料,包括GDE的Guide Line,GDE的专属联络通道,GDE的专属差旅网站资源等等等等。我大概花了一个晚上的时间才将这些资料全部梳理清楚。

每一个GDE的领域,在Google都会有一个全球范围的负责人,这个负责人会很快与你取得联系,并要求与你进行一次视频会面。这次视频会面的主要目的是为了欢迎你加入GDE的行列,向你介绍一些GDE的知识,并回答你的各种关于GDE的问题。

但是这对于我来说,又像是经历了一次面试,因为整个视频会面过程又是全英文进行的。

如果你的英文水平并不是非常好的话,这里我可以教你一个小窍门。就是你先提前跟他打一剂预防针,告诉他:I'm sorry, my English is not very good, so I need to make a apology in advance. 然后对面出于客气就会说:That's fine. Don't worry about it. 最后结束的时候他还会再补充一句:I think your English is perfect!

我屡试不爽。

GDE的责任

很明显,成为GDE只是一个开始。如果你想把成为GDE当成一个终点的话,那么你可能并不适合去申请这个头衔,因为GDE是要承担很多责任的。

Google非常乐于和愿意分享并传播Google技术的人一起合作,所以才有了GDE这个项目。能够成为GDE,说明Google对你的技术水平,以及你的技术影响力都表示了足够的认可。但如果你就此躺在功劳簿上,不再持续分享和传播你所擅长的技术,那么很遗憾,Google将会在下一年移除你的GDE身份。

所以,在申请GDE之前,一定要先想清楚这一点。

我在申请之前就进行了一下自我评估,我认为无论我是不是GDE,常年以来我都一直在分享Android相关的开发技术,我非常乐于做这件事,并且也愿意持续做下去,所以才决定提交了申请。

事实证明,这可能是我今年最正确的决定之一。这场奇妙的旅程让我结识了许多优秀的Googler,包括钟辉老师、陈卓老师、Tracy、Ben Weiss等等。甚至我竟然还能跟我的偶像Yigit Boyar(Jetpack负责人,RecyclerView作者)进行视频连线,共同参加一场圆桌会议,这实在是太不可思议了。

Tracy在刚刚加上我微信的时候就告诉我,Google一直在招募优秀的GDE候选人,同时希望进一步扩大国内Android GDE的人数。

而现在,我已经成为国内第二位Android GDE了。

如果你也具备成为GDE的资质,同时有兴趣申请的话,请与我联系。

关注我的技术公众号,每天都有优质技术文章推送。

微信扫一扫下方二维码即可关注:

查看原文

赞 11 收藏 2 评论 2

lryong 赞了文章 · 2020-10-23

TCP的状态 (SYN, FIN, ACK, PSH, RST, URG)

在TCP层,有个FLAGS字段,这个字段有以下几个标识:SYN, FIN, ACK, PSH, RST, URG.

其中,对于我们日常的分析有用的就是前面的五个字段。

它们的含义是:

SYN表示建立连接,

FIN表示关闭连接,

ACK表示响应,

PSH表示有 DATA数据传输,

RST表示连接重置。

其中,ACK是可能与SYN,FIN等同时使用的,比如SYN和ACK可能同时为1,它表示的就是建立连接之后的响应,

如果只是单个的一个SYN,它表示的只是建立连接。

TCP的几次握手就是通过这样的ACK表现出来的。

但SYN与FIN是不会同时为1的,因为前者表示的是建立连接,而后者表示的是断开连接。

RST一般是在FIN之后才会出现为1的情况,表示的是连接重置。

一般地,当出现FIN包或RST包时,我们便认为客户端与服务器端断开了连接;而当出现SYN和SYN+ACK包时,我们认为客户端与服务器建立了一个连接。

PSH为1的情况,一般只出现在 DATA内容不为0的包中,也就是说PSH为1表示的是有真正的TCP数据包内容被传递。

TCP的连接建立和连接关闭,都是通过请求-响应的模式完成的。

概念补充-TCP三次握手:

TCP(Transmission Control Protocol)传输控制协议

TCP是主机对主机层的传输控制协议,提供可靠的连接服务,采用三次握手确认建立一个连接:

位码即tcp标志位,有6种标示:SYN(synchronous建立联机) ACK(acknowledgement 确认) PSH(push传送) FIN(finish结束) RST(reset重置) URG(urgent紧急)Sequence number(顺序号码) Acknowledge number(确认号码)

第一次握手:主机A发送位码为syn=1,随机产生seq number=1234567的数据包到服务器,主机B由SYN=1知道,A要求建立联机;

第二次握手:主机B收到请求后要确认联机信息,向A发送ack number=(主机A的seq+1),syn=1,ack=1,随机产生seq=7654321的包;

第三次握手:主机A收到后检查ack number是否正确,即第一次发送的seq number+1,以及位码ack是否为1,若正确,主机A会再发送ack number=(主机B的seq+1),ack=1,主机B收到后确认seq值与ack=1则连接建立成功。

完成三次握手,主机A与主机B开始传送数据。

在TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握手建立一个连接。 第一次握手:建立连接时,客户端发送syn包(syn=j)到服务器,并进入SYN_SEND状态,等待服务器确认; 第二次握手:服务器收到syn包,必须确认客户的SYN(ack=j+1),同时自己也发送一个SYN包(syn=k),即SYN+ACK包,此时服务器进入SYN_RECV状态;

第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1),此包发送完毕,客户端和服务器进入ESTABLISHED状态,完成三次握手。完成三次握手,客户端与服务器开始传送数据. 摘自中国云安网(www.yunsec.net) 原文:http://www.yunsec.net/a/schoo...

查看原文

赞 3 收藏 5 评论 0

lryong 赞了文章 · 2020-10-21

MySQL性能优化,MySQL索引优化,order by优化,explain优化

前言

今天我们来讲讲如何优化MySQL的性能,主要从索引方面优化。下期文章讲讲MySQL慢查询日志,我们是依据慢查询日志来判断哪条SQL语句有问题,然后在进行优化,敬请期待MySQL慢查询日志篇

建表

// 建表
CREATE TABLE IF NOT EXISTS staffs(
    id INT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(24) NOT NULL DEFAULT "" COMMENT'姓名',
    age INT NOT NULL DEFAULT 0 COMMENT'年龄',
    pos VARCHAR(20) NOT NULL DEFAULT "" COMMENT'职位',
    add_time TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT'入职事件'
) CHARSET utf8 COMMENT'员工记录表';
// 插入数据
INSERT INTO `test`.`staffs` (`name`, `age`, `pos`, `add_time`) VALUES ('z3', 22, 'manager', now());
INSERT INTO `test`.`staffs` (`name`, `age`, `pos`, `add_time`) VALUES ('July', 23, 'dev', now());
INSERT INTO `test`.`staffs` (`name`, `age`, `pos`, `add_time`) VALUES ('2000', 23, 'dev', now());
// 建立复合索引(即一个索引包含多个字段)
ALTER TABLE staffs ADD INDEX idx_staffs_nameAgePos(name, age, pos);

优化一:全部用到索引

介绍

建立的复合索引包含了几个字段,查询的时候最好能全部用到,而且严格按照索引顺序,这样查询效率是最高的。(最理想情况,具体情况具体分析)

SQL 案例

优化二:最左前缀法则

介绍

如果建立的是复合索引,索引的顺序要按照建立时的顺序,即从左到右,如:a->b->c(和 B+树的数据结构有关)

无效索引举例

  • a->c:a 有效,c 无效
  • b->c:b、c 都无效
  • c:c 无效

SQL 案例

优化三:不要对索引做以下处理

以下用法会导致索引失效

  • 计算,如:+、-、*、/、!=、<>、is null、is not null、or
  • 函数,如:sum()、round()等等
  • 手动/自动类型转换,如:id = "1",本来是数字,给写成字符串了

SQL 案例

优化四:索引不要放在范围查询右边

举例

比如复合索引:a->b->c,当 where a="" and b>10 and 3="",这时候只能用到 a 和 b,c 用不到索引,因为在范围之后索引都失效(和 B+树结构有关)

SQL 案例

优化五:减少 select * 的使用

使用覆盖索引

即:select 查询字段和 where 中使用的索引字段一致。

SQL 案例

优化六:like 模糊搜索

失效情况

  • like "%张三%"
  • like "%张三"

解决方案

  • 使用复合索引,即 like 字段是 select 的查询字段,如:select name from table where name like "%张三%"
  • 使用 like "张三%"

SQL 案例

优化七:order by 优化

当查询语句中使用 order by 进行排序时,如果没有使用索引进行排序,会出现 filesort 文件内排序,这种情况在数据量大或者并发高的时候,会有性能问题,需要优化。

filesort 出现的情况举例

  • order by 字段不是索引字段
  • order by 字段是索引字段,但是 select 中没有使用覆盖索引,如:select * from staffs order by age asc;
  • order by 中同时存在 ASC 升序排序和 DESC 降序排序,如:select a, b from staffs order by a desc, b asc;
  • order by 多个字段排序时,不是按照索引顺序进行 order by,即不是按照最左前缀法则,如:select a, b from staffs order by b asc, a asc;

索引层面解决方法

  • 使用主键索引排序
  • 按照最左前缀法则,并且使用覆盖索引排序,多个字段排序时,保持排序方向一致
  • 在 SQL 语句中强制指定使用某索引,force index(索引名字)
  • 不在数据库中排序,在代码层面排序

order by 排序算法

  • 双路排序

    Mysql4.1 之前是使用双路排序,字面的意思就是两次扫描磁盘,最终得到数据,读取行指针和 ORDER BY 列,对他们进行排序,然后扫描已经排好序的列表,按照列表中的值重新从列表中读取对数据输出。也就是从磁盘读取排序字段,在 buffer 进行排序,再从磁盘读取其他字段。

文件的磁盘 IO 非常耗时的,所以在 Mysql4.1 之后,出现了第二种算法,就是单路排序。

  • 单路排序

    从磁盘读取查询需要的所有列,按照 orderby 列在 buffer 对它们进行排序,然后扫描排序后的列表进行输出, 它的效率更快一些,避免了第二次读取数据,并且把随机 IO 变成顺序 IO,但是它会使用更多的空间, 因为它把每一行都保存在内存中了。

当我们无可避免要使用排序时,索引层面没法在优化的时候又该怎么办呢?尽可能让 MySQL 选择使用第二种单路算法来进行排序。这样可以减少大量的随机 IO 操作,很大幅度地提高排序工作的效率。下面看看单路排序优化需要注意的点

单路排序优化点

  • 增大 max_length_for_sort_data

    在 MySQL 中,决定使用"双路排序"算法还是"单路排序"算法是通过参数 max_length_for_ sort_data 来决定的。当所有返回字段的最大长度小于这个参数值时,MySQL 就会选择"单路排序"算法,反之,则选择"多路排序"算法。所以,如果有充足的内存让 MySQL 存放须要返回的非排序字段,就可以加大这个参数的值来让 MySQL 选择使用"单路排序"算法。
  • 去掉不必要的返回字段,避免select *

    当内存不是很充裕时,不能简单地通过强行加大上面的参数来强迫 MySQL 去使用"单路排序"算法,否则可能会造成 MySQL 不得不将数据分成很多段,然后进行排序,这样可能会得不偿失。此时就须要去掉不必要的返回字段,让返回结果长度适应 max_length_for_sort_data 参数的限制。
  • 增大 sort_buffer_size 参数设置

    这个值如果过小的话,再加上你一次返回的条数过多,那么很可能就会分很多次进行排序,然后最后将每次的排序结果再串联起来,这样就会更慢,增大 sort_buffer_size 并不是为了让 MySQL 选择"单路排序"算法,而是为了让 MySQL 尽量减少在排序过程中对须要排序的数据进行分段,因为分段会造成 MySQL 不得不使用临时表来进行交换排序。

但是sort_buffer_size 不是越大越好:

  • Sort_Buffer_Size 是一个 connection 级参数,在每个 connection 第一次需要使用这个 buffer 的时候,一次性分配设置的内存。
  • Sort_Buffer_Size 并不是越大越好,由于是 connection 级的参数,过大的设置和高并发可能会耗尽系统内存资源。
  • 据说 Sort_Buffer_Size 超过 2M 的时候,就会使用 mmap() 而不是 malloc() 来进行内存分配,导致效率降低。

优化八:group by

其原理也是先排序后分组,其优化方式可参考order by。where高于having,能写在where限定的条件就不要去having限定了。

IT 老哥

一个通过自学,进入大厂做高级Java开发的程序猿,希望能通过我的分享,让你学到知识

查看原文

赞 26 收藏 20 评论 3

lryong 赞了文章 · 2020-10-20

程序人生|从网瘾少年到微软、BAT、字节offer收割机逆袭之路

引言

今天给大家分享一个我的读者的故事,这个故事很长,从游戏boy到offer收割机,从富士康到百度再到微软,国内知名大厂的公司他都拿了一遍offer。

这当中有太多心酸和努力,在他的身上我也能看到一些自己的影子,希望大家可以从他的文章里有所收获,有所感悟。

话不多说,我们来听他的故事。

正文

国庆节的第一天,自习室里已经没有什么人了。窗外,西安的秋天飘一点点雨,坐在电脑前心情十分平静。想在这个难得的闲暇里,想起记录一下自己这些年的经历,也是给自己留一点以后可以回忆的故事。

个人2014年入学,武汉某大学计科相关专业,学科评估200名开外。

大一上学期一门专业课差点挂科,直接奠定了无法保研的局面,开始浑浑噩噩混了两年。除了高数上下,其他能逃的课基本都用来打英雄联盟了。

16年升大三的暑假,一个偶然的机会看到隔壁院的师兄发在群里的一条实习招聘,是武汉富士康招聘软件测试实习生。

暑期岗位,能签实习证明,有班车来学校接送,一天还有220工资。我觉得这是个很好的机会,起码富士康这个厂也算有些名气,能赚个实习经历还有点工资。

我向师兄报了名,简历里面特别注明了大学C语言92分,班级第二。简历通过的还算顺利,也没有面试,直接就让去了。

当时负责的任务主要是Windows 10 SP1的多国版本测试任务,跟我以为的进去的写代码相差甚远,就是个黑盒测试吧,或者再说直白些,就是点点点的无脑操作没什么技术含量。

不过由于是对接外企,所以任务都是英文下达的,有时候翻译还是得花点功夫,英文能力倒是得到些许锻炼。测试需要自己组装机器,选择各型号的cpu和显卡等配件。

因为是第一份实习,我学习的非常认真,直到现在我仍然能够闭上眼睛,清晰完整的回忆出一台整机的拼装全过程。

CPU的引脚,内存条的金手指和各式各样的SATA线束是那段时间接触最多的东西。

机器点亮后就开始做DASH(从服务器上下载测试版本的系统并安装),然后是激活系统开始对照着测试用例展开测试。

差不多两个星期之后,常规的操作已经比较熟练了,任务也显得逐渐无聊了起来。由于DASH的过程很漫长,我经常会在三楼到四楼的楼梯口望着窗外的太阳,不知道是哪个有趣的同事在窗台用矿泉水瓶养了一个小叶子,我看着这抹绿色总是很舒服。

富士康的生活很规律,八点半到工位,五点半出公司,日复一日的装配着各种方案让我在想,以后我要从事这种枯燥但是轻松的工作吗? 想了想还是写代码做需求比较有意思。

由于本科学校不太好找工作,而我自认代码能力还可以,所以我决定通过考研来获得一个更好的教育背景或者说,一个让公司能够看上的背书。

大三暑假正值备考,跟我关系不错的老师给了我一个机会,说有个师兄在美团,想把我的简历推给他。我当然很激动,花了一下午的时间准备了一份简历:xx学校,计算机专业,主语言java,曾经做过xx校园app的后端功能以及一个在线OJ评测网站... ...

简历发给了老师,一天,两天,一个星期过去了,老师说那边认为简历还是太单薄了,不能发起面试。

那天我感到一阵失落,我以为起码能有个面试机会,结果却是简历都过不了。

我对自己的代码水平还是比较有信心,但恰恰是这种信心带给了我更大的失落。我生气的跟舍友说,以后绝对不去美团,他求我去我都不去。这当然是一个大话,只是孩子心气地不肯承认罢了。

考研历时五个半月,还算顺利地通过了初试复试,来到了西安的一所高校开始了研究生阶段的学习。

那时候有同学说,一个叫字节跳动的公司能开很高的工资,不过对算法题的要求很高。

这也是我第一次听说字节跳动,研究生的课和本科其实没有太大的区别,至少对我来说都是不怎么听的进去的(当然也有部分非常优秀的课程,这是后话了)。

但我在课上发呆的时候,慢慢地却不会再去想我要怎么操作我的英雄站在兵线前面干掉对面的玩家,LOL至今都没时间再玩了,时不时看看比赛倒也对青春有个交代。

<img  style="border-radius: 0.3125em;
box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
data-original="https://m.qpic.cn/psc?/V12w6YIp4GQ5pr/bqQfVz5yrrGYSXMvKr.cqXpLZKuvoQw5kIZ6DG1L4Gst9rS7q3SpJaiYiZE.lzn1t*nvJ7he89lfvt*BtlKvuJGoGUgVsPhWzNMYR73Va9Y!/b&bo=gAc4BAAAAAABB5s!&rf=viewer_4">

研究生阶段无聊的时候,一般我会打开牛客网,在上面做几道题目,看着各种计算机网络和操作系统的知识,总觉得自己永远也学不完了。在浏览讨论贴的过程中,我渐渐发现网友会去做一些算法题的训练,一般在leetcode上。我也随之注册了这个网站,全英文的界面让我觉得很有范。

没多久我就决定要开始我的刷题之路,我仍然记得第一题好像是求两数之和,其实这个题目我在备考时的九度OJ上做过,感觉应该难度不算太大,磨了一些边界之后,当一个绿色的Accept出现在眼前,我觉得这种感觉就像是我用XX√√√完成了一局BO5晋级赛。

于是我的生活变得更简单了,能逃的课就在寝室和图书馆刷LEETCODE,不能逃的课就在课上刷LeetCode。我尽量保持在一天6+的题量,有时候会做到10+,我喜欢看到登录界面上的绿点连成一片的样子。

不过由于课程作业和考试原因,有时候也会中断好一会。我非常清楚的记得在一个下雪的午后,我完成了在Leetcode上的第一百个Accept,那一题调了两个小时,是LRU置换算法的实现。我激动的发了一条朋友圈,拍下100/1300的标记。

我觉得我好像会离字节这样的公司近一点了,在刷题的过程中我也会穿插着学习一些计算机网络的东西,主要是为了应付面试。搜索的资料很杂,大部分来自博客和B站。

包括在刷题的过程中我看的算法视频也是在B站搜罗的盗版,主讲人是左程云左神,也是我心目中永远的真神。那一版的视频左神的桌面还是齐天大圣飘着红色披风的背影,后来在北京时期我补上了欠左神的正版课,这也是后话了。

研一暑期我也开始投一些公司的实习,我惊奇的发现,大部分的笔试都拦不住我了,反正基本没有因为笔试挂过的公司,也拿到了一个不错的机会,但因为一些原因未能成功去实习。

后来看着同学们都出去了外面的公司实习,我的心里又开始痒痒了,打开牛客网,翻查着有限的实习信息,看到一个爱奇艺的招聘机会。

一轮大概50分钟左右的面试,主要是针对OJ项目,后面问到了Java异常机制,泛型的实现,FutureTask的实现思路,以及一些线程池的问题,线程池这个我没用过所以就说不会。

当天晚上八点,面试官问我公司在北京,能不能来实习,我想都没想就说地点绝对不是问题,于是我定了第三天最早的一班高铁,花了一天的时间收拾东西,其实我不是为了带走什么,只是要把它们放在朋友那里。

我带走的只有一个背包,里面放了两天的换洗衣物,我的各种证件,一小盒谷维素(改善失眠)和一本深入理解Java虚拟机。我觉得做Java的人,这个东西带在身上就很有安全感,有信仰陪着我,虽然我从来也没有翻开过。

房子是在高铁上租的,转租的人是个字节跳动的运营,地点就在人大旁边,离爱创大厦很近。

我还记得当时我的leader在做完新手教程后,就过来帮我搬电脑,带我整理工位,简单的交代了一下之后,就慢慢的开始了开发流程。

第一次进入大公司实习,第一次来到首都北京,红绿灯前等待的全部都是清一色年轻的面孔,有那么一个瞬间我恍惚地看到,斑马线变成了律动地音符,而这个城市年轻人的心跳就是它的节拍。

我喜欢早上骑着师兄传给我的美利达,再放一首Young For You, 我觉得我就是属于这个时代的年轻的人儿。

作为新人,要学习的东西很多,一般我会十点半以后下班。而且我喜欢前紧后松,所以会把心中的工期排的靠前一点。

我惊讶于自己学了一年没学懂的Spring框架在公司捣把捣把竟然就能上手一些项目了,这种学习的速度是我从来没有想过的。

周末我也会在公司赶需求或者自我学习,累了就去对面吃一个麦当劳甜筒,有时候也会去咖啡厅坐会。那通常是因为我解决了一个困扰很久的Bug.虽然在爱奇艺的生活很充实,但是心中还是有一份大厂梦。

19年的国庆,整整八天我都呆在公司看着各种字节跳动的面经和算法题,只要有一题我觉得我可能不能100%实现,我都会上Leetcode立马把它AC掉。

行内的朋友可能知道这是怎样的痛苦,因为一道题有思路和真正稳稳地实现它,中间的差距实在太大了。

7号的晚上,我坐在电脑前,关上所有的页面,打开Eclipse,花一分钟或者几十秒撸了一发快排,测试用例直接写在main里,一把过,我关上了电脑回家。

这是我自己的习惯,每逢大战,我都会在最后以一个快排收尾,因为当年就是这个代码断了我的保研路。开发的时候我用的更多的是IDEA,但是写算法题我只用Eclipse, 因为算法题对依赖环境的要求很低,基本上有个JDK就足够。

而我是个恋旧的人,所以我把自己最擅长的方面,留给我的老朋友Eclipse。

结果并不像过程一般顺利,也不是每个幸运都会眷顾努力。

12号一天两个公司面试,分别在早上10点和晚上7点开始。紫金数码园成为了我永远的痛,我记得他们问的都是比较深入的问题,诸如TCP,UDP能不能绑在同一个端口,Java的线程底层是如何实现的,TCP和IP的详细报文结构,报头,进程切换的上下文到底包括什么,哪些寄存器,CFS算法如何实现的等等。

最后我实在烦了,我说我就不会操作系统,他又问了个字符串匹配算法,我给他详细的讲了KMP的实现,然后他让写个树的深度遍历。我火一下子上来了,我觉得你可以挂我,但是不要用这种简单的东西来拖一下面试时间让我体面的离开。

我就说:这个东西太简单了,我不想写,你可以问个难点的。

他让我写Linux的定时器算法,我想了很久,没想出来,事实上我都没听过这个东西,自己设计了一个类似哈希表的结构希望来存放这些定时任务。他表示摇头,我知道今天就到这里了。

现在回想起来,我并没给到面试官足够的尊重,多少年少轻狂了点。

直到最近这个月,我开始认真的阅读深入理解Linux内核,才明白当时我到底错在哪(当然时间轮算法是我在第二天就去看了的)。

字节的面试是在晚上,七天的努力好像什么效果也没有,因为我准备的面经基本一点也没被问到。

走在中关村大街上,我觉得今天有点格外的冷,只能把耳机的声音调的再大一点,宝石老舅的Disco让我的情绪稍微得到了一些缓和。

细心的朋友可能发现,那天的面试有两场,这个机会说来很巧,我某次跟同学提到我想换个更大的厂,她说百度给她打过电话面试,是个私人号码,她自己已经有公司了所以不想面试。

我意识到这是个机会,招聘信息里面大部分是邮箱或者工作电话,其实联系的成功率并不高,但是这种私人电话基本是点对点,中间不存在邮箱这种轮询或者工作号码背后的一层Nginx。

我直接把号码拨过去,询问对面是不是需要招收实习生,表明了自己的学校和来意,希望对面能安排一个面试机会。

答复是肯定的,我特意要求在跟字节同一天,这样子免得我需要频繁请假,所有才有了一天之内字节和百度的两次面试。

来北京的第一个星期我就去拜访过百度大厦,西二旗地铁的一侧静静躺着一个熊掌,当我近距离看到这个标志的时候心中翻起的是澎湃和向往。

不过这次的面试在百度科技园,如果说大厦给我的感觉是大气,那么科技园就是真正的气势恢宏。

回字型的无限大标志由七栋大楼构成,K2和K1的连廊接在三楼,直接跨过了一个双向车道。面试的整体过程比较顺利,给我的面试体验也非常好,面试官会针对我简历上的技术栈由浅入深的进行询问,有些原理还会给我讲解。

三轮面试一共做了四个题,刚好打在了我的强项上。分别是最短编辑距离,最长回文字符串,变态跳楼梯和树的最长直径。我把这些题全部通关,中间还在百度食堂吃了个饭。

面试耗时3个半小时,到我出公司的时候已经是下午两点半了。

我非常感谢百度,不仅仅是因为它给了我实习的机会,更多的是对我这样一个要强的人来说,一天内连续挂掉两家公司的局面可能真的是无法接受的。

特别是字节的面试让我觉得毫无还手之力,在这种情况下,熊度就显得格外可亲。

进入百度是一个新的开始,我需要做的事情很多:学习一门新的语言,学习服务器上的开发,学习百度的一些内部工具以及...学习使用Mac。

在这些需求里面我直接砍掉了Mac的学习,把重心放在了语言和Linux上,具体的做法是我向Mentor提出把Mac换成ThinkPad。

我Mentor奇怪地跟我说:大部分人都是Windows本想换Mac,很少有你这样Mac想换Win的,我就笑笑说我时间不够用。

其实很巧的是我的Mentor也是ThinkPad,而他的技术非常强,是我们组绝对的实力担当 ,我觉得我技术路线的尽头应该就是我Mentor的样子。白天我看公司内部的各种文档,八点半下班以后我会花两个小时看Linux视频,并且做一些笔记,因为我觉得在工作时间看视频总给人一种在偷玩的感觉。

十点的西北旺还是灯火通明,出了科技园会看到旁边的网易,新浪和腾讯北京。我顺着腾讯的大楼先走到马连洼地铁站,回中关村的地铁一共要倒两趟,然后再从苏州街走回人大。

通勤时间大概在一小时四十分钟,所以到家一般都是十一点多了,我经常会在楼下的KFC买个吮指原味鸡或者鸡米花,静静地坐着吃完再回去洗澡睡觉。

期间我也想过换个住处,但是想了想,现在的房子地段很好,各种生活用品和娱乐都很多,西北旺那片还是有些冷清,还是算了。

还有一个原因是我特别喜欢人大,我在任何一个地方租房都喜欢租在学校旁边,校园的景色和人文气息都让我很舒服。

在百度的周末我一般也用来学习,通常是花一天的时间看Linux,另外一天去公司看文档。我看的书是Linux编程手册,这是我一个大牛同学推荐给我的,他初中就开始玩Linux,在社区比较活跃。

很难想象我这么一个不爱学习的人能静下心来看一本大部头的书看一下午,最深的原因是,我在北京有个漂亮的女同学,我一般都会喊她陪我在她们学校的自习室看一下午,然后去吃个饭看个电影啥的。如果这我都看不进去的话,那我真的不知道该说对不起谁了。

那段时间可能是我在北京最快乐最回忆的时光,每当地铁报站到了芍药居的时候,我都会有些悸动。

我们一起去过中关村的店,后海的店,印象最深的是第一次在万泉河的一家西餐厅。

那天她穿黑色的裙子,化了妆,坐在西餐厅的白色桌布前。我直接想到了十年以后,天是那么蓝,花静静躺在路边,我觉得我一定要好好写代码,成为一个厉害的人因为... ...

这样规律的日子我过了大概有三个月,也是我在百度呆的大半时间,我每周最大的期待就是周末可以看书的时光,因为去别人学校学习知识当然让人快乐啊。

百度楼下的蛋糕店有很好吃的慕斯蛋糕,有时候我会六点就下班,然后大概一个多小时通勤给同学带一个吃,因为这个蛋糕到六点以后基本上就买不到了。

不过很认真的说,我能坚持看Linux很重要的原因也是在字节的面试给我的打击太大了,让我认识到我在Linux这块就是一片空白。并且工作中确实遇到了相关的问题,有一次我做了一个定制化的HDFS上传程序,fork的时候在父进程中没有wait,导致服务器上产生了大量处于僵死状态的进程。

这些进程的执行流已经结束了,可是由于父进程未对它们进行最终处理,导致进程号一直被占用,久而久之可能会影响到服务器上其他进程的pid分配。

还有我们的HDFS资源比较有限,处理的数据量很大,大家的MR任务和Spark任务都在一个HDFS空间上,细碎的文件很多导致INode被占用的很严重,有时候还有磁盘,却没有足够的INode能分配了,导致任务执行失败等等。后来这种类似的问题我都在Linux编程手册中找到了对应的知识点,也让我越来越认识到它的重要性。

差不多两个月之后,我对Python和服务器上的开发已经有了一点点认识了,也开始接了一个新的项目。这个项目在工作计划上的执行人其实是我Mentor,不过他比较忙,我看了下这个活应该可以做,我就接了下来。项目的具体内容在此不方便多提,但是这个项目让我真正的接触到了很多开发中的交流,合作,踩坑,出坑,设计等等等等。

印象最深的是来自Google响应报文里面一个隐式编码的问题,Chunk协议在一些报文中会被使用,用作数据交流格式的标准。

Google的响应报文中使用了这种编码,却没有显式地声明出来,我在对报文进行了DOM树构建和重写之后,改变了报文的字符数,而Google用一个16进制的数字声明了这个长度。这个细节直接导致所有被我篡改的报文均不能在浏览器端被正常解析,表现为无限等待的界面。

这个Bug我足足改了七天,中间有一天我已经无限接近这个答案了,我把一个疑似表示长度的十六进制数进行了还原,想看看它是否指代长度。坑爹的是在服务器上看到的长度是字节数,中间涉及到编码的问题,而这个16进制数指代的是字符数,中间的差值让我一直不敢确定这个是代表长度(其实就算知道了也不可能改对,因为中文字符的字节数在UTF-8下是不同于字符数的)。

在这个开发周期中我熬过最多的夜就是这个时期了,以至于之后的需求性开发我都很轻松的完成,因为我觉得应该没有比这个Bug更加难弄的情况了(中间还有其他的问题,比如URL编码异常,Gzip的隐式刷流,开源库的DOM化缺陷,但是这些慢慢处理就好)。

这期间最让我印象深刻的是在我解决了这个问题之后一天的晚上,隔壁组对接的开发过来问我的经历我是今年的新同事吗,工作多久了。

经理哈哈大笑,说“怎么样,xx牛*吧”。隔壁的开发说确实很不错,我经理又补了一句“xx是我们的实习生”,隔壁的开发惊讶了说“我以为xx都早工作了”。

我全程背对着他们,那一刻我靠在椅子上,他们看不到我嘴角咧起的笑。我很喜欢看程序员生涯记录之类的小说,《疯狂的程序员》里面这样子写道“很多时候,我们开发一个项目,做一个需求,加班,熬夜,干耗,不是为了赶某个工期,或者是任务完成后领导给的拿一笔钱,更重要的是,我们享受这种克服万难,成人所不能的感觉,这种感觉跟钱是不一样的东西”。

正是这样子的瞬间,让我在程序的世界里真正的发现了自己。

故事直到这里,好像都跟微软没什么关系,可能有些朋友很想看如何去微软的过程,但是我个人觉得此处实在是乏善可陈,同时这个事情本身也没那么重要了。

一月下旬我从北京回湖北过年,没几天就遇到了疫情,在老家被辗转着隔离,家里也有亲人感染,可以说整个二月都是在隔离中度过。心里的压力更多来自对亲人健康的关心,到了二月中旬,情况渐渐好转,基本处于康复期了,恰逢学校群里有人发布微软春季实习生招聘,我就发了简历。

二月下旬开始,我在隔离的地方用手机开着热点,抱着公司的ThinkPad开展了新一轮的征程。

实习期间大量的开发任务确实很难抽出时间做这种集中式的复习,这次刷题我的目标很明确,牛客上的剑指Offer和LeetCode148一题不漏全部写完。

其实之前已经实现了大概80%,但是剩下的20%无疑是更加麻烦的,中间穿插着各种DP的训练,还是老规矩,AC才算过。刷累的时候会去整理在爱奇艺和百度的项目,它们的需求点,难点和结果。

这中间还有天在群里吹水,跟人吵起来AVL和红黑树哪个更难,我为了证明红黑树更难还专门花了半天去实现了一个可用的AVL。

写的时候我内心已经是很平静了,记得大学刚学树的时候,我觉得这种代码只能靠背,而且还背不下来。

到现在,这种东西只是去看一遍它的思路,然后在心中大概的复现一次,遇到有问题的点就停下来详细想想。一个数据结构无非ADT和对应的增删改查,然后再想想哪块的代码可以复用,抽离出来。

接下来就是各种边界和小case,头一天晚上我看到两点钟,把全部的思路复现了一遍。第二天起来吃完隔离点送过来的早饭就开始写,直接在记事本里面开始进行实现,然后微调了下,过我自己的case,没啥磕绊就完成了。

后面的微软面试一共做了五个题,最后一面的leader说我对边界条件的分析很到位,是她今天面试的所有人里面最全面最准确的,我当她给了个好消息吧。

同年的四月,我在师弟的帮助下,再次进行了字节跳动的面试,一下午三面过关斩将,也在不久之后收到了字节跳动的意向书。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gjv21j04xnj315s0kuard.jpg)


坦白来说,这个时期的我心中已经没有了什么波澜,不会特别高兴,也不会再对哪家公司产生特别的展开追逐的那种意愿。一来我已经呆过好几个公司了,那种大公司的憧憬和新鲜感对我而言已经没有那么大的吸引力,同时我也开始认为,一个程序员,他的目光不应该全部放在对哪家公司的追求上。

第一,我们服务于我们具体的业务和相应的技术,具体的业务是比公司这种平台性的东西更加值得讨论的。

第二,追求公司的本质是希望自我的提升,在这种前提下更应该把精力放在如何精进自己的技术水平上,因为公司本身并不能成为一个努力的方向和路线,它只是一个结果。

最后,又是一年的国庆,还是坐在电脑前。闭上眼睛,一路的回忆像浮光搬掠过眼前。

我喜欢看别人故事的原因是,几千个字的篇幅其实写尽了这个人很长的一段经历,浮浮沉沉,故事中的低潮可能在几行文字中就轻描淡写的过去了,读者喜欢去看走出这个低潮再见阳光的感动,其实对这个人来说,这一段恰恰是最难熬最难经历的一段。

我们看着故事中的人,好像自己也会离开这样的谷底。真实的说,这个故事中应该花大篇幅描述的难过我都略去了。

许多面试时候被否定的环节,被问到哑口无言的时刻,丹棱街SOHO微软大楼明灭的红光,冬天寒冷的西北旺东路到万泉河路海淀中街,爱奇艺十点半下班回去还在床上抱着电脑看一两个小时博客的那种追逐,西二旗人头多过Integer.MAX_VALUE的地铁站,一道题一个Bug困整整一个下午的纠结,二月新冠疫情落在家庭的恐慌,隔离时期对于家人的担心,老家甚至没有Wifi的手机热点面试,包括出来实习需要顶住的学业压力。

我把这个故事记录下来,是因为我喜欢《疯狂的程序员》里面的绝影,Boss绝,我想成为他那样的程序员,一个执着于代码,纯粹于代码的程序员。

本科期间我有些想做的事情未能完成,大三的时候武汉一个比中兴还低的本地的国企IT公司我都觉得很不错了,而时至今日我已经去过好几家大型互联网公司实习,拿遍了头部互联网的Offer,亦或者去到微软。

这些东西其实我在那时候并没想过,但是我也更加没想过绝对到不了今天。在晚归的中关村大街上,我经常会想到一首歌《奉献》,这是电影[飞驰人生]的主题曲。长路奉献给远方,岁月奉献给季节,我拿什么奉献给你。我们经常提起奉献,却很少真正理解奉献的样子。

对啊,到这一步,做到纯粹,更多的是热爱带来的奉献,我不是要执着于哪个Boss,或者执着于哪个公司,我是执着于我所热爱的程序,我所热爱的行业。

因为热爱,所以我不计回报,所以我做到比自己更多一点,因为喜欢,所以回忆里更多的是那些奉献与努力的时刻。

再回望去年随便收拾了两件衣服就踏上北京的自己,有些面试官听到我这个经历的时候会先大笑一下,然后说这样子是否有些冒进。也有些面试官因为这个性格将我挂掉,但是我已经过了那种因为别人评价感到疑问的阶段。如果再给我一次机会选择,或者说再给我一百次机会选择,在爱奇艺的那个电话里给的回复也还会是YES。

因为年轻,就是有无限的可能,青春就是不设限的。

阿里的招聘页面上有句话:If not now, when? If not me, who? 官方给出的翻译是“此时此刻,非我莫属”,我觉得差点意思。

时不我待,舍我其谁。

2020年10月3日于西安

写在最后

故事结束了,但是属于这个少年的未来才刚刚开始。

其实这个故事结尾最好的并不是他收到了多少offer,而是他终于找到了这份工作对于他的意义,找到了自已真正热爱的事业。单从这一点来说,他就已经成功了。

而当他拿到那些曾经遥不可及的大厂offer之后再回首,那些在暗淡时的迷茫困顿却不屈不挠用力生长的经历,每一秒都熠熠生辉。

我是敖丙,你知道的越多,你不知道的越多,我们下期见。

查看原文

赞 38 收藏 14 评论 5

lryong 关注了用户 · 2020-10-19

LNMPRG源码研究 @php7internal

一群热爱代码的人 研究Nginx PHP Redis Memcache Beanstalk 等源码 以及一群热爱前端的人
希望交流的朋友请加微信 289007301 注明:思否 拉到交流群,也可关注公众号:LNMPRG源码研究

《PHP7底层设计与源码分析》勘误https://segmentfault.com/a/11...

《Redis5命令设计与源码分析》https://item.jd.com/12566383....

景罗 陈雷 李乐 黄桃 施洪宝 季伟滨 闫昌 李志 王坤 肖涛 谭淼 张仕华 方波 周生政 熊浩含 张晶晶(女) 李长林 朱栋 张晶晶(男) 陈朝飞 巨振声 杨晓伟 闫小坤 韩鹏 夏达 周睿 李仲伟 张根红 景罗 欧阳 孙伟 李德 twosee

关注 11687

认证与成就

  • 获得 45 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 1 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

  • email-verifer

    ✅ 一个 Go 实现的高性能,支持多维度检查的 email 校验器

  • hugo-leetcode-dashboard

    ✨ 一个 LeetCode 答题看板的生成插件, 支持一键部署到 Hugo 站点。 完整记录刷题的心路历程 ✨

注册于 2019-05-08
个人主页被 2.6k 人浏览