已删除

2022-05-05 20:37

关注

每日积累

网络部分

1. Epoll了解过吗?你知道Epoll的底层数据结构是什么吗?Epoll和Select有何不同?

Epoll是Linux内核对IO多路复用的实现, epoll的核心结构是三个API+一个红黑树+一个双向链表

红黑树用来管理FD, 保证我们新增、删除、更新FD时的速度都是Ologn

为什么不用AVL树而是用红黑树?

select存fd是用bitset存的, 每次查询就绪的fd需要遍历, 时间复杂度是On

TCP

1. 能简单介绍下TCP头都有哪些字段?分别有什么用吗

alt

SourcePort,DestinationPort 和 SourceIP,DestinationIP共同构成了一个TCP连接
SequenceNumber 序列号, 实现了TCP的顺序性
AcknowledgmentNumber 确认号, 实现了TCP的可靠性
TCP Flags 决定了一个TCP Segment的身份(在建立连接后, ACK永远设为1)
Window Size 流量控制的窗口大小(保证接受端的接受能力)

2. 说一下TCP建立和断开连接的过程 alt

下面是C代码使用socket接口实现最简单的server:

#include <stdio.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char *argv[])
{
  /* 1. 创建 socket
   * AF_INET 表示用于创建 IPv4 网络的 socket
   * SOCK_STREAM 表示用于 TCP 网络（还可以使用 SOCK_DGRAM 创建 UDP socket）
   * socket 函数文档：https://man7.org/linux/man-pages/man2/socket.2.html
   */
  int socket_fd = socket(AF_INET, SOCK_STREAM, 0);
  if (socket_fd == -1)
  {
    printf("failed to create socket\n");
    return 1;
  }

  // 2. 将 socket 绑定网络接口（IP + 端口）
  struct sockaddr_in address;
  address.sin_family = AF_INET;
  address.sin_addr.s_addr = INADDR_ANY; // 相当于 0.0.0.0
  address.sin_port = htons(8888);
  // https://man7.org/linux/man-pages/man2/bind.2.html
  int code = bind(socket_fd, &address, sizeof(address));
  if (code < 0)
  {
    printf("failed to bind net interface\n");
    return 1;
  }

  // 3. 开始监听连接
  // 第二个参数称为 backlog，用于指定等待连接的队列长度。
  // listen 函数文档，https://man7.org/linux/man-pages/man2/listen.2.html
  code = listen(socket_fd, 1024);
  if (code < 0)
  {
    printf("failed to listen at 0.0.0.0:8888\n");
    return 1;
  }

  printf("listen at 0.0.0.0:8888\n");

  // 4. pending 队列中取出连接
  // https://man7.org/linux/man-pages/man2/accept.2.html
  int conn;
  while ((conn = accept(socket_fd, NULL, NULL)))
  {
    char *message = "Hello\n";
    // 向 client 发送消息
    write(conn, message, strlen(message));
    // 关闭链接
    close(conn);
  }

  close(socket_fd);
  return 0;
}

可以使用telnet localhost 8888命令来测试

listen方法不会阻塞(只会将server从CLOSED->LISTEN),而accept才是阻塞式方法

第一个SYN的seq是根据随机算法随机生成的, 具体建立连接的实现是Linux内核实现的, socket暴露出来listen和accept两个api,其中listen接收一个backlog参数决定半连接队列(SYNC QUEUE)和全连接队列(ACCEPT QUEUE)的长度, accept方法便是从全连接队列里取一个连接出来 alt

SYNC FLOOD攻击便是攻击者发起大量SYN请求,但是不响应server返回的SYN,就会导致SYNC QUEUE打满无法再接受新的正常的请求, 而Linux下会有5次重试请求,间隔时间分别为1、2、4、8、16秒, 重试5次还没收到ACK,才会认为断开连接

SYN包发起连接请求时,通常会带上Option:MSS(Maximum Segment Size)表示可支持的最大PayLoad(不包括TCP header的内容)长度,默认时1460B

实际上, 断开连接不一定是四次挥手, 特殊情况下client和server会同时发送FIN包: alt

TIME_WAIT需要等待2MSL时间, 在Linux中将MSL设置为30s, 等待2MSL的原因是防止最后一个ACK对端没收到, 如果超过2MSL,则会重发

整个TCP的状态机: alt

可以使用netstat -tln -p tcp来查看当前机器所有TCP连接的状态

3. TCP的可靠性包含哪些方面?分别是如何实现的

相比UDP, TCP是一种面向连接的、可靠的传输层协议

顺序性

Sequence和Acknowlegment保证了TCP数据的顺序性:

举个例子, 发送端发送的数据包Seq=1344683738, payload size(也就是数据长度)=517, 那么响应的ack=1344683738+517=1344684255 (响应的SYN+ACK包的Sequence Number也是算法随机生成的)

使用wireshark抓包时会显示[Next Sequence Number]=518, TCP Header里并没有直接存这个值, 这个值时wireshark自己算出来的

可靠到达性

通过「超时重传」来实现,当一定时间未收到ACK响应时,发送端会重新发送包,这里的一定时间就是RTO(Retransmission Timeout),但它不是固定的,而是根据RTT(Round Trip Time,从发送到接受到ACK回包的时间)动态算出来的(比如多次采样RTT,然后通过一定算法计算出RTO)

保证接收端的接受能力

TCP在内核实现有一个缓冲区(其中包括滑动窗口): alt

滑动窗口可以使发送端连续发送多个TCP包,而不用一个个等响应包,来加速数据传输

而接收方也不会对每个TCP包都做ACK响应, 而是收到多个包之后按顺序对最后一个包做ACK回应,这样发送端就知道之前的所有包都送到了: alt

防止网络环境拥塞

TCP有拥塞避免算法:慢启动、拥塞避免、快重传

「慢启动」:

拥塞窗口(congestion window,cwnd)初始化为10,每经过一个RTT,cwnd=cwnd*2, 是指数型上涨, 直到到达满启动上限(slow start threshold), 就会进入拥塞避免阶段

「拥塞避免」:

每经过一个RTT, cwnd=cwnd+1, 是线性增长, 直到出现超过RTO时间重传, 或者接收到连续三次重复ACK进行快重传, 这就说明网络出现了拥塞

出现拥塞的处理:这里分为上述提到的两种情况

「接收到连续三次ACK」:

快重传,发送端重发丢失的包
ssthreshold=cwnd/2
cwnd=ssthreshold+3*MSS(*3是因为连续三个重复的ACK说明丢失的包的后三个包接收方已经收到了) 开始「快恢复」

「出现RTO超时重传」(比较严重):

ssthreshold=cwnd/2 cwnd=1 重新进入慢启动阶段,重新指数型增加

「快重传」:

当发送端连续接收到三个重复的ACK时, 便认为接受端顺序端有一个包丢失了,发送端便要重新发送这个包,这就是快重传

「快恢复」(只有执行快重传后才会执行):

cwnd=ssthreshold+3*MSS, 如果收到重复的ACK,则cwnd=cwnd+1,如果是收到新的ACK则直接进入拥塞避免阶段(ssthreshold=cwnd)

「准确性」:

TCP Header有CheckSum校验和, 可以校验Header和数据的准确性

2. 一个浏览器的多个Tab的TCP连接的端口号是一样的吗?

不是一致的

HTTP

1. http 0.9/1.0/1.1/2的各有什么新特性?GET和POST有什么区别?

http0.9 无header 只有GET一个method 没有状态码

// req
GET /index.html

//rsp
<HTML>
A very simple HTML page
</HTML>

http1.0 多了header(其中Content-Type可以允许传输多种格式;Connection:Keep-Alive可以使http1.0也能实现TCP的复用,但是协议本身不支持,依赖的是浏览器和服务器厂商); 多了POST; 多了状态码

但是每次发起HTTP请求都要建一个新的TCP连接, HTTP请求结束都要4次挥手(从TCP层面看是,当server发完数据后会主动发起FIN)

GET和POST使用约定(比如GET把参数放在PATH里, POST参数放在body里;浏览器也会针对GET和POST做不同的一些诸如缓存的策略), 但是HTTP协议层没有强制规范

// req
GET /index.html HTTP/1.0
Accept-Type:text/html

//rsp
HTTP/1.0 200 OK
Content-Type:text/html
Content-Length:1024

<HTML> 
A page with an image
  <IMG SRC="/myimage.gif">
</HTML>

http1.1 支持多个HTTP请求复用同一个TCP连接(持久性连接) 和在同一个TCP连接同时发送多个请求(管道机制pipelining)

但是同一个TCP连接里的请求服务端是顺序执行的, 所以会有队头阻塞的情况, 一个处理比较慢的请求会阻塞后续请求

同时 http1.1 支持chunked transform

http2是真正的二进制协议, http1.1的body可以是各种格式, 但是http1.1的header信息必须是ascii码

2. 讲一讲http协议和https协议的区别

https是在http协议和TCP协议中间多了一个安全层, 通常使用TLS协议

3. 讲一讲TCP粘包问题, 以及HTTP如何解决粘包问题的

TCP粘包是指应用层要自己区分TCP缓冲区里的二进制数据哪一段是一个整体, 常见的解决方案有以下几种:

设定编解码规则, 比如第一个字节表示消息长度,后面跟着该长度的二进制数据

HTTP协议Header有Content-Length,也是采用上面的解决方案

你们公司用的什么RPC框架?讲一讲你所熟知的RPC框架以及RPC和HTTP的区别

RPC是远程过程调用协议

公司用的是Thrift框架, 通过编写IDL由编译器生成不同编程语言的代码(client/server), 支持C和S不同语言

Thrift从下到上分为4层:

服务层 Server Layer, 具体的业务代码
处理层 Processor Layer, IDL写好的和生成的特定语言的框架
协议层 Protocol Layer, 就是网络的应用层,包括序列化和反序列化和BIO/NIO, 包括Binary,Compact,JSON几种方式
传输层 Transport Layer, 可以选择TCP

协议层:Binary

采用TLV格式编码, T表示类型, L表示长度, V表示具体的值

数据类型	类型标识(8位)	值
bool	2	一个字节的值（true：1，false：0）
byte	3	一个字节值
double	4	八个字节值
i16	6	两个字节值
i32	8	四个字节值
i64	10	八个字节值
string	11	四个字节数据长度+数据的值
struct	12	嵌套数据+一个字节停止符（0）
map	13	一个字节的key类型+一个字节的val类型+四个字节的数据长度+数据的值（key+val)
set	14	一个字节的val类型+四个字节的数据长度+数据的值
list	15	一个字节的val类型+四个字节的数据长度+数据的值

举个例子:

struct Test {
    1: bool Open,
    2: string Name,
    3：i32 ID，
}

test = Test(Open=True, Name="hi", ID=18)
test实例序列化后16进制显示为(为了方便理解加了空格和换行)：
    02 0001 01
    0b 0002 00000002 6869
    08 0003 00000012

BinaryProtocol 本质就是一个通讯协议(应用层),里面包含了序列化协议,序列化协议+Message头就构成了BinaryProtocol,其分为严格模式和非严格模式:

对于严格模式: 四个字节的版本+调用类型,四个字节消息名称长度,消息名称,四个字节流水号,消息负载数据的值,一个字节的停止标记

version := uint32(VERSION_1) | uint32(typeId)
WriteI32(int32(version))
WriteString(name)
WriteI32(seqId)
WriteBody(body)
WriteByte(STOP)

Transport层分为两部分上层Transport和Low Level Transport, Low Level Transport就是TCP, 上层Transport可以选择BIO,NIO等

RPC和HTTP的区别是:

流量消耗上看, RPC普遍使用二进制, 而HTTP最起码Header头还是明文传输(ascii码)
资源粒度上看, RPC类似于本地方法调用, 而HTTP还要重新组织数据结构,所以RPC适合对内,HTTP适合对公

算法部分

1. 知道什么是稳定的排序算法吗?冒泡排序/选择排序是稳定的排序算法吗?

稳定的排序算法是指, 两个值相等的数在排序前后相对位置不变;

冒泡排序(可以)是稳定的排序算法:

if nums[i] > nums[i+1]{
  swap(nums,i,i+1)
}
// 如果是下面这种就不稳定了:
if nums[i] >= nums[i+1]{
  swap(nums,i,i+1)
}

选择排序是每次从待排序序列里找一个最大值放到末尾,稳不稳定也是看判断条件有没有=号

数据结构

1. 二叉搜索树、红黑树、AVL树、B树、B+树的区别是什么?

二叉搜索树保证每个节点的左子树都小于根, 每个节点的右子树都大于根, 增删改查时间复杂度预期是O(logn), 但是极端情况下时间复杂度会达到O(n), 比如只有左子树一条链下来

算法题:

红黑树变能通过自调整算法使二叉树保持平衡, 使时间复杂度稳定在O(logn)

参考 https://www.cnblogs.com/skywang12345/p/3245399.html

红黑树特性:

根节点是黑色, NULL节点是黑色
红节点的子节点是黑色
一个节点到它所有的子孙NULL节点途径的黑色节点数目一致

Redis

redis的string类型怎么存储多种类型的?

首先在redis每存一个key-value都会存两个对象(键对象和值对象),对象的结构体如下:

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; // 上一次使用的时间
    int refcount; // 用于内存回收的引用计数
    void *ptr; // 实际指向对象地址的指针
} robj;

// type 类型
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

encoding是指底层的存储结构 : alt 上面是redis3的编码，到redis5又有了：OBJ_ENCODING_QUICKLIST和OBJ_ENCODING_STREAM，且OBJ_ENCODING_LINKEDLIST不再使用