网络编程基础

- TCP：
  - 服务端：socket -> bind -> listen -> accept -> recv/send -> close。
  - 客户端：socket -> connect -> send/recv -> close。
- UDP：
  - 服务端：socket -> bind -> recvfrom/sendto -> close。
  - 客户端：socket -> sendto/recvfrom -> close。
send、sendto区别，recv、recvfrom区别？

TCP和UDP区别？
- TCP面向连接（三次握手），通信前需要先建立连接；UDP面向无连接，通信前不需要连接。
- TCP通过序号、重传、流量控制、拥塞控制实现可靠传输；UDP不保障可靠传输，尽最大努力交付。
- TCP面向字节流传输，因此可以被分割并在接收端重组；UDP面向数据报传输。
TCP为什么不是两次握手而是三次？
- 如果仅两次连接可能出现一种情况：客户端发送完连接报文（第一次握手）后由于网络不好，延时很久后报文到达服务端，服务端接收到报文后向客户端发起连接（第二次握手）。此时客户端会认定此报文为失效报文，但在两次握手情况下服务端会认为已经建立起了连接，服务端会一直等待客户端发送数据，但因为客户端会认为服务端第二次握手的回复是对失效请求的回复，不会去处理。这就造成了服务端一直等待客户端数据的情况，浪费资源。
TCP为什么挥手是四次而不是三次？
- TCP是全双工的，它允许两个方向的数据传输被独立关闭。当主动发起关闭的一方关闭连接之后，TCP进入半关闭状态，此时主动方可以只关闭输出流。
- 之所以不是三次而是四次主要是因为被动关闭方将”对主动关闭报文的确认”和”关闭连接”两个操作分两次进行。
- “对主动关闭报文的确认”是为了快速告知主动关闭方，此关闭连接报文已经收到。此时被动方不立即关闭连接是为了将缓冲中剩下的数据从输出流发回主动关闭方（主动方接收到数据后同样要进行确认），因此要把”确认关闭”和”关闭连接”分两次进行。
- Linux的close实际上是同时关闭输入流和输出流，并不是我们常说的四次握手。半关闭函数为shutdown，它可以用来断开某个具体描述符的TCP输入流或输出流。
为什么要有TIME_WAIT状态，TIME_WAIT状态过多怎么解决？
- 主动关闭连接一方在发送对被动关闭方关闭连接的确认报文时，有可能因为网络状况不佳，被动关闭方超时未能收到此报文而重发断开连接（FIN）报文，此时如果主动方不等待而是直接进入CLOSED状态，则接收到被动关闭方重发的断开连接的报文会触发RST分组而非ACK分组，当被动关闭一方接收到RST后会认为出错了。所以说处于TIME_WAIT状态就是为了在重新收到断开连接分组情况下进行确认。
- 解决方法：
  - 可以通过修改sysctl中TIME_WAIT时间来减少此情况（HTTP 1.1也可以减少此状态）。
  - 利用SO_LINGER选项的强制关闭方式，发RST而不是FIN，来越过TIMEWAIT状态，直接进入CLOSED状态。
TCP建立连接及断开连接是状态转换？
- 客户端：SYN_SENT -> ESTABLISHED -> FIN_WAIT_1 -> FIN_WAIT_2 -> TIME_WAIT。
- 服务端：LISTEN -> SYN_RCVD -> ESTABLISHED -> CLOSE_WAIT -> LAST_ACK -> CLOSED。
TCP流量控制和拥塞控制的实现？
- 流量控制：TCP采用大小可变的滑动窗口进行流量控制。窗口大小的单位是字节，在TCP报文段首部的窗口字段写入的数值就是当前给对方设置的发送窗口数值的上限，发送窗口在连接建立时由双方商定。但在通信的过程中，接收端可根据自己的资源情况，随时动态地调整对方的发送窗口上限值。
- 拥塞控制：网络拥塞现象是指到达通信子网中某一部分的分组数量过多，使得该部分网络来不及处理，以致引起这部分乃至整个网络性能下降的现象。严重时甚至会导致网络通信业务陷入停顿，即出现死锁现象。拥塞控制是处理网络拥塞现象的一种机制。
TCP重传机制？
- 滑动窗口机制，确立收发的边界，能让发送方知道已经发送了多少、尚未确认的字节数、尚待发送的字节数；让接收方知道已经确认收到的字节数。
- 选择重传，用于对传输出错的序列进行重传。
三次握手过程？
- 主动建立连接方A的TCP向主机B发出连接请求报文段，其首部中的SYN(同步)标志位应置为1，表示想与目标主机B进行通信，并发送一个同步序列号x进行同步，表明在后面传送数据时的第一个数据字节的序号是x + 1。SYN同步报文会指明客户端使用的端口以及TCP连接的初始序号。
- 接收连接方B的TCP收到连接请求报文段后，如同意则发回确认。在确认报中应将ACK位和SYN位置1，表示客户端的请求被接受。确认号应为x + 1，同时也为自己选择一个序号y。
- 主动方A的TCP收到目标主机B的确认后要向目标主机B给出确认，其ACK置1，确认号为y + 1，而自己的序号为x + 1。
四次挥手过程？
- 主动关闭主机A的应用进程先向其TCP发出连接释放请求，并且不再发送数据。TCP通知对方要释放从A到B这个方向的连接，将发往主机B的TCP报文段首部的终止比特FIN置1，其序号x等于前面已传送过的数据的最后一个字节的序号加1。
- 被动关闭主机B的TCP收到释放连接通知后即发出确认，其序号为y，确认号为x + 1，同时通知高层应用进程，这样，从A到B的连接就释放了，连接处于半关闭状态。但若主机B还有一些数据要发送主机A，则可以继续发送。主机A只要正确收到数据，仍应向主机B发送确认。
- 若主机B不再向主机A发送数据，其应用进程就通知TCP释放连接。主机B发出的连接释放报文段必须将终止比特FIN和确认比特ACK置1，并使其序号仍为y，但还必须重复上次已发送过的ACK = x + 1。
- 主机A必须对此发出确认，将ACK置1，ACK = y + 1，而自己的序号是x + 1。这样才把从B到A的反方向的连接释放掉。主机A的TCP再向其应用进程报告，整个连接已经全部释放。

阻塞和非阻塞I/O区别？
- 如果内核缓冲没有数据可读时，read()系统调用会一直等待有数据到来后才从阻塞态中返回，这就是阻塞I/O。
- 对于往缓冲区写的操作同理。
同步和异步区别？
- 同步I/O指处理I/O操作的进程和处理I/O操作的进程是同一个。
- 异步I/O中I/O操作由操作系统完成，并不由产生I/O的用户进程执行。
- Reactor模式已经是同步I/O，处理I/O操作的依旧是产生I/O的程序；Proactor是异步I/O，产生I/O调用的用户进程不会等待I/O发生，具体I/O操作由操作系统完成。
- 异步I/O需要操作系统支持，Linux异步I/O为AIO，Windows为IOCP。
epoll和select及poll区别？
- 文件描述符数量限制：select文件描述符数量受到限制，最大为2048（FD_SETSIZE），可重编内核修改但治标不治本；poll没有最大文件描述符数量限制；epoll没有最大文件描述符数量限制。
- 检查机制：select和poll会以遍历方式（轮询机制）检查每一个文件描述符以确定是否有I/O就绪，每次执行时间会随着连接数量的增加而线性增长；epoll则每次返回后只对活跃的文件描述符队列进行操作（每个描述符都通过回调函数实现，只有活跃的描述符会调用回调函数并添加至队列中）。当大量连接是非活跃连接时epoll相对于select和poll优势比较大，若大多为活跃连接则效率未必高（设计队列维护及红黑树创建）
- 数据传递方式：select和poll需要将FD_SET在内核空间和用户空间来回拷贝；epoll则避免了不必要的数据拷贝。
epoll中ET和LT模式的区别与实现原理？
- LT：默认工作方式，同时支持阻塞I/O和非阻塞I/O，LT模式下，内核告知某一文件描述符读、写是否就绪了，然后你可以对这个就绪的文件描述符进行I/O操作。如果不作任何操作，内核还是会继续通知。这种模式编程出错误可能性较小但由于重复提醒，效率相对较低。传统的select、poll都是这种模型的代表。
- ET：高速工作方式（因为减少了epoll_wait触发次数），适合高并发，只支持非阻塞I/O，ET模式下，内核告知某一文件描述符读、写是否就绪了，然后他假设已经知道该文件描述符是否已经就绪，内核不会再为这个文件描述符发更多的就绪通知（epoll_wait不会返回），直到某些操作导致文件描述符状态不再就绪。
ET模式下要注意什么（如何使用ET模式）？
- 对于读操作，如果read没有一次读完buff数据，下一次将得不到就绪通知（ET特性），造成buff中数据无法读出，除非有新数据到达。
  - 解决方法：将套接字设置为非阻塞，用while循环包住read，只要buff中有数据，就一直读。一直读到产生EAGIN错误。
- 对于写操作主要因为ET模式下非阻塞需要我们考虑如何将用户要求写的数据写完。
  - 解决方法：只要buff还有空间且用户请求写的数据还未写完，就一直写。

Linux下进程间通信方式？
- 管道：
  - 无名管道（内存文件）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程之间使用。进程的亲缘关系通常是指父子进程关系。
  - 有名管道（FIFO文件，借助文件系统）：有名管道也是半双工的通信方式，但是允许在没有亲缘关系的进程之间使用，管道是先进先出的通信方式。
- 共享内存：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与信号量，配合使用来实现进程间的同步和通信。
- 消息队列：消息队列是有消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 套接字：适用于不同机器间进程通信，在本地也可作为两个进程通信的方式。
- 信号：用于通知接收进程某个事件已经发生，比如按下ctrl + C就是信号。
- 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，实现进程、线程的对临界区的同步及互斥访问。
Linux下同步机制？
- POSIX信号量：可用于进程同步，也可用于线程同步。
- POSIX互斥锁 + 条件变量：只能用于线程同步。
线程和进程的区别？
- 调度：线程是调度的基本单位（PC，状态码，通用寄存器，线程栈及栈指针）；进程是拥有资源的基本单位（打开文件，堆，静态区，代码段等）。
- 并发性：一个进程内多个线程可以并发（最好和CPU核数相等）；多个进程可以并发。
- 拥有资源：线程不拥有系统资源，但一个进程的多个线程可以共享隶属进程的资源；进程是拥有资源的独立单位。
- 系统开销：线程创建销毁只需要处理PC值，状态码，通用寄存器值，线程栈及栈指针即可；进程创建和销毁需要重新分配及销毁task_struct结构。
介绍虚拟内存？
内存分配及碎片管理？
有很多小的碎片文件怎么处理？

fork系统调用？
什么场景用共享内存，什么场景用匿名管道？
有没有用过开源的cgi框架？
epoll和select比有什么优势有什么劣势，epoll有什么局限性？
- epoll优势：1. 没有描述符数量限制；2. 通过回调代替轮询；3. 内存映射代替数据在用户和内核空间来回拷贝。
- epoll劣势（局限性）：select可以跨平台，epoll只能在Linux上使用。
线程（POSIX）锁有哪些？
- 互斥锁（mutex）
  - 互斥锁属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程A和B，它们分别运行在core 0和core 1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁，而此时这个锁正被线程B所持有，那么线程A就会被阻塞，此时会通过上下文切换将线程A置于等待队列中，此时core 0就可以运行其他的任务（如线程C）。
- 条件变量(cond)
- 自旋锁(spin)
  - 自旋锁属于busy-waiting类型的锁，如果线程A是使用pthread_spin_lock操作去请求锁，如果自旋锁已经被线程B所持有，那么线程A就会一直在core 0上进行忙等待并不停的进行锁请求，检查该自旋锁是否已经被线程B释放，直到得到这个锁为止。因为自旋锁不会引起调用者睡眠，所以自旋锁的效率远高于互斥锁。
  - 虽然它的效率比互斥锁高，但是它也有些不足之处：
    - 自旋锁一直占用CPU，在未获得锁的情况下，一直进行自旋，所以占用着CPU，如果不能在很短的时间内获得锁，无疑会使CPU效率降低。
  - 自旋锁只有在内核可抢占式或SMP的情况下才真正需要，在单CPU且不可抢占式的内核下，自旋锁的操作为空操作。自旋锁适用于锁使用者保持锁时间比较短的情况下。

项目整体架构是什么？请求怎么进来？处理完怎么出去？
- 整体架构为：I/O多路复用 + 非阻塞I/O + 线程池，即Reactor反应堆模型。
- 处理流程：
  - 创建监听描述符并在epoll中注册。
  - 监听到新请求，epoll从阻塞中返回并建立新连接。
  - 将新建的连接描述符在epoll中注册。
  - 当某个连接接收到用户请求数据时，将任务投放到线程池任务队列中。
  - 工作线程被条件变量（任务队列不为空）唤醒，并互斥访问线程池。
  - 得到任务的线程完成解析及响应。
    - 工作线程执行函数为do_request，参数即为task结构。
      - 每个task结构在建立连接是被初始化，包含描述符、缓冲区等信息是，并在do_request执行时记录解析结果及状态。
在做压测时，机器配置是什么样的？数据如何？
- 本地测试。
  - 四核i5处理器 + 128G固态硬盘。
为了QPS（Query per second, 1秒内完成的请求数量）更高可以做哪些改进？
- 对请求结果做缓存。
- 多次搜索请求采用异步I/O，改串行为并行。
- 调整并发线程数量（通常和CPU核心数相同）。
有没有注意到压测时内存，CPU，I/O指标？
- 压测同时打开top -H -p pid查看CPU，I/O，内存信息。
压测时有没有见过TIME_WAIT？怎么样会见到？怎么解决？
- 当服务端关闭连接时会产生TIME_WAIT。
- 解决方案：
  - HTTP 1.1在同一个TCP连接上尽量传输更多数据。
  - 通过修改sysctl配置减小TIME_WAIT时间。
是会主动关闭还是会等待客户端关闭连接?
- 服务端会在完成请求之后关闭连接。
写一个Server需要注意哪些问题？
- 只支持request/response，除此之外是否需要支持cgi。
- 并发量，QPS，资源占用（内存，CPU，I/O，网络流量等）。
  - CPU占用是否过高。
  - 内存是否泄露。
项目中遇到什么困难，你是如何解决的？
- CPU占用过高。
- 压测时，每次最后会挂掉。
做这个项目的目的是什么？
定时器是如何实现的？里面放了有多少个连接（怎么确定大小）？谁去取超时的连接？检查超时之后还会继续检查吗，还是检查完之后就断了？
如果发生超时，在关闭连接时同时又收到了新的数据怎么办？
用什么数据结构存放url，怎么解析的？
- 使用tk_request_t结构中buff读取用户请求，buff为循环缓冲（8192 Bytes）。
- 每次进入while循环时读取用户请求到buff中循环队列尾位置（plast），之后解析用户请求并响应。
- 支持HTTP 1.1，只要有数据就读取 -> 解析 -> 响应。

介绍一下上网行为管理这个系统？
介绍一下格林威治云平台做哪些任务？
改变数据获取方式及校验数据一致性？
WTGGroup模块做什么用的？

层序遍历二叉树？
map和hashmap的区别是什么？
Hash发生冲突时怎么处理？
hashmap的时间复杂度是多少？map的时间复杂度？
优先队列时间复杂度？