面试题自我检讨

面试

[TOC]

4.27 - 1

1. 指针和引用的区别

引用实际上是一个常量指针，它和指针最主要的区别在于初始化的时候指向一个对象，之后不能再指向其他对象，但指向对象的值可以改变。而指针可以定义为空指针。

指针的所占内存的大小由CPU寻址位数决定，引用的大小由指向的对象决定。

指针自增的时候修改了所指向的内存地址，引用自增的时候增加了指向对象的值。

[ 64 位指针 8 bytes, 32 位指针 4 bytes, 由此可以推测是多少位的机器。]

2. 判断主机是大端序还是小端序

大端序是高地址存放在内存的低地址，小端序相反。

可以使用联合体判断。

#include <iostream>
using namespace std;
union T {
    int a;//4 bytes
    char b;//1 byte
};
int main() {
    T t;
    t.a = 0x01020304;
    cout<<t.b<<endl;
    if(t.b == 0x01) {
    	cout<<"little end"<<endl;
    } else if(t.b == 0x04) {
  		cout<<"big end"<<endl;
    }
    return 0;
}

原理是：联合体共享一处内存，如果对联合体中4字节的一个对象写入十六进制的数字（地址），访问1字节的对象存储的内容就知道内存的低地址存储的是数据的高地址还是低地址，进而推断大小端序。

3. 管道实现原理

管道作为进程间通信的方式之一，分为命名管道和匿名管道。底层函数分别为 mkfifo()和 pipe() ，两者的实现原理一样，只是命名管道会创建一个公共的管道文件，供其他进程使用，而匿名管道的文件描述符只有父进程在fork()子进程时，拷贝传递给子进程，其他进程无法使用。

由一个长度为2的int数组作为管道读写的文件描述符，管道文件存储在内核里，相当于一个缓冲区，没有数据时会发生读阻塞，写操作一般不发生阻塞，类似于半双工通信。

在 命名管道的具体实现 kfifo 利用了环形缓冲器，使用指针表示内存起始地址，读写和内存末尾偏移量，在保证读线程和写线程没有共享变量的情况下，写入的内容大小永远小于内存分配大小，如果超过就覆盖最早写入的数据，也就是先进先出。

4. static 和 const 的区别

存储区域不同。static修饰的变量在静态存储区，const修饰的变量在动态存储区。并且多次初始化static变量，其值不会改变。

static修饰的变量对于定义作用范围之外的文件是不可见的。const修饰的变量表示不可以被修改，虽然可能被间接修改，但语义是不能修改。

static修饰的类成员变量和类成员函数是属于类而非该类类型的对象。const修饰的成员函数不能修改成员变量。

5. typedef 和 define 的区别

typedef是编译时处理，define在预处理阶段处理。

typedef只能替换真实存在的类型名，define可以替换各种变量，函数。

typedef的作用域受限，define作用域于全局。

在替换指针的时候，如 #define int* int_ptr， 同时声明两个指针时，会发生错误：int_ptr a,b -> int* a,b。应该是int*a, *b。

4.28 - 2

6. HTTPS 七次握手，是不是对称加密

*TCP:
客户端 SYN Seq
服务器 SYN Seq ACK
客户端 ACK
*TLS:
客户端 -> Client Hello : 			 发送加密协议版本，加密压缩算法，随机生成的素数等
		 Server Hello 		    <- 服务器 检查加密协议版本，加密压缩算法，随机生成的素数等
		 
		 Certificate  			<- 服务器 发送证书链，包含发行方，有效期
		 Server Key Exchange	<- 服务器 传递公钥，数字签名等
		 Server Done			<- 服务器 通知 Client 已经发完
		 
客户端 -> Client Key Exchange		 验证证书，传递用 Server 公钥加密的随机字符串
客户端 -> Change Cipher Spec		 通知 Server 之后的消息加密
客户端 -> Finished					 发送加密后的握手信息

		 Change Cipher Spec 	<- 服务器 通知 Client 之后的消息加密
		 Finished			 	<- 服务器 发送加密后的握手信息

因为只使用了一个密钥进行加密和解密，因此是对称加密的。

非对称加密有两个钥匙，及公钥（Public Key）和私钥（Private Key）。公钥和私钥是成对的存在，如果对原文使用公钥加密，则只能使用对应的私钥才能解密；因为加密和解密使用的不是同一把密钥，所以这种算法称之为非对称加密算法。

7. HTTP和HTTPS的区别

建立连接时，HTTP只需要TCP三次握手，HTTPS还需要多一次TLS四次握手，时延增加。后者保证了消息传输的可靠性。

HTTP的端口是80，HTTPS端口是443。

HTTPS需要服务端申请证书。

8. CA证书是什么

CA证书是包含版本，发行者，过期时间，公钥等信息的二进制或基于其他编码方式的文件，用来验证服务端或客户端是否值得信任。将证书中的数字签名用公钥进行解密，利用同样的哈希算法对证书进行加密，判断两者是否相同。

9. 进程如何申请分配内存（栈和堆的区别）

1、栈区（stack）：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其 操作方式类似于数据结构中的栈。

2、堆区（heap）：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，

3、全局区（静态区）（static）：全局变量和静态变量的存储是放在一块的，初始化的 全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另 一块区域。 程序结束后由系统释放。

静态变量存储在虚拟地址空间的数据段和bss段，c语言中其在代码执行之前初始化，属于编译期初始化，而c++中由于引入了对象，对象生成必须调用构造函数，全局或者局部静态对象当且仅当对象首次用到时进行构造。

4、文字常量区：常量字符串就是放在这里的。 程序结束后由系统释放

5、程序代码区：存放函数体的二进制代码。

进程的内存空间中，由高地址向下，依次是内核代码和数据，内核栈，用户栈，代码库，堆，数据，代码。

当进程需要用malloc()申请内存时，首先看所需内存大小是否超过128k，如果小于128k，则调用brk()，修改指向堆的指针，使其向高地址移动。如果大于128k，则调用mmap()，在堆和栈之间的虚拟内存中分配一块最接近所需内存大小的内存块。

10. 什么是多态，虚函数

• 封装：使用函数指针把属性与方法封装到结构体中
• 继承：结构体嵌套
• 多态：父类与子类方法的函数指针不同

多态是在继承的基础上，由于一个类继承了基类的成员函数，当此类需要对继承的函数进行重写时，就发生了多态。这时就引入了虚函数，即在基类需要发生多态的函数前加上virtual。对于每个类有一张虚函数表，对于每个不同的该类对象，它们有一个虚表指针。对于创建时使用了基类指针的对象，在调用虚函数时，通过该对象的虚指针访问虚表查找自己的函数实体。

• 构造函数不能是虚函数

虚函数主要是实现多态，在运行时才可以明确调用对象，根据传入的对象类型来调用函数，例如通过父类的指针或者引用来调用它的时候可以变成调用子类的那个成员函数。而构造函数是在创建对象时自己主动调用的，不可能通过父类的指针或者引用去调用。那使用虚函数也没有实际意义。
　　在调用构造函数时还不能确定对象的真实类型（由于子类会调父类的构造函数）；并且构造函数的作用是提供初始化，在对象生命期仅仅运行一次，不是对象的动态行为，没有必要成为虚函数。

4.29 - 3

11. 程序，进程，线程，协程 (多)

程序是静态的文件，没有执行的含义。

当开始运行一个程序的时候，就创建了一个对应的进程。

进程是资源分配的基本单位，线程是系统调度的基本单位，一个进程可以有多个线程，一个线程里可以有多个协程。同一个进程里的线程共享该进程的内存空间，每个进程拥有独立的内存空间。因为线程切换只需要更新内核栈和寄存器（eip, esp, ebx, ecx, edx, esi, edi, ebp）上下文，进程切换还需要更换页目录得到新的地址空间，所以线程开销小。

由于线程间的地址空间没有隔离，因此线程崩溃（访问了非法的地址进行操作，写坏其他线程的数据，触发信号（？）会造成进程崩溃。

协程相当于用户级的线程，是由程序员所写代码开启或退出，线程的管理取决于操作系统的调度算法【先来先服务，最短作业优先，轮转调度，优先级调度，多级队列，多级反馈队列】，可能由于抢占式调度被提前停止。进程和线程都是同步的，协程是异步的，多个协程交替拥有控制权。拥有自己的寄存器上下文和栈，协程调度切换时，将寄存器上下文和栈保存在其他地方，再切回来的时候，回复先前的寄存器上下文和栈。

线程和goroutine的区别？

· 内存占用：

创建一个goroutine的栈内存消耗为2KB，运行后如果栈不够用，会自动扩容。

创建一个thread为尽量避免极端情况下os线程栈溢出，默认会为其分配一个较大内存（1-8MB），还需要 guard page 的区域用于和其他thread的栈空间进行隔离。且栈内存空间一旦创建和初始化完成后就不能再变化，所以某些特殊情况下还是会有溢出的风险。

• 多进程多线程多协程

当线程数量太小，同一时间大量请求将被阻塞在线程队列中排队等待执行线程，此时 CPU 没有得到充分利用；当线程数量太大，被创建的执行线程同时在争取 CPU 资源，又会导致大量的上下文切换，从而增加线程的执行时间，影响了整体执行效率。

• 创建线程

  • pthread_create（新线程的标识符，属性，新线程将要运行的函数，及参数）

12. Sockets 原理，过程

• socket

  确定协议族（IPv4 IPv6），类型（UDP，TCP）

  返回一个 sockfd

• bind

  对于服务端来说，需要绑定一个确定的地址，方面让客户端指定连接。

  对于客户端来说，不需要命名socket，而是采用匿名的方式由内核分配。

• listen （服务端被动）

  传入socket文件描述符，创建一个等待处理连接的监听队列。

• accept

  传入执行过listen的socket文件描述符，返回一个新的连接 socket

• connect （客户端主动）

  传入由 socket 系统调用返回的 sockfd，服务器监听的地址，成功建立连接后，sockfd就唯一标识了这个连接。

• close

  传入 sockfd，并不是调用一次就关闭连接，在多进程程序里，父进程和子进程都执行close才能将连接关闭，每次 fork 都会让父进程的 socket 引用计数加一。

• recv

  读取 sockfd 上的数据

• send

  写入数据到 sockfd 上

13. OSI七层模型，TCP/IP模型

物理层 网卡
数据链路层 MAC ARP 交换机 网卡
网络层 IPv4 IPv6 路由器 ICMP 交换机 RIP
传输层 TCP UDP
会话层 RPC SOCKS
表示层 TLS
应用层 DNS HTTP FTP SMTP

应用层
传输层
网络层
链路层

14. 智能指针

为什么不用裸指针：

裸指针的声明不能表示它是指向单个对象还是数组；

销毁时不确定是用 delete 还是其他的销毁机制；

如果确定了删除的方法，也不知道用删除单个对象的格式还是删除数组的格式；

如果以上都确定了，但是它不能保证只被销毁一次；

不能判断对象被销毁，但指针依然指向他们情况。

• unique_ptr

表示对对象具有独占控制权，没有拷贝构造函数，而是移动语义。

任何一个被 unique_ptr 指向的对象只能被一个 unique_ptr 实例管理。

• shared_ptr

表示对对象有共享的控制权，当新的 share_ptr 指向同一个对象时，引用计数加一，其他share_ptr离开作用域时，引用计数减一。当引用计数为0的时候，销毁该指针。

• weak_ptr

与 shared_ptr 配合使用，没有控制权，也不会导致 shared_ptr 增加引用计数

15. TCP长连接，短连接，心跳保活

短连接：一次通信结束，client立即调用close()结束。

长连接【开关在应用层，参数在操作系统中】：一次通信结束，不立即调用close()。在一定时间内链路上没有数据的传输时，间隔一段时间发送Keep-alive探针，测试当前连接是否可用。如果都探测失败，说明连接不可用。

客户端和服务端各自都可以开启HeartbeatTask，发送特殊的心跳请求，如果心跳多次没有收到响应，客户端会尝试重连，服务端会close()。

• HTTP 协议的 KeepAlive 意图在于连接复用，同一个连接上串行方式传递请求, 响应数据
• TCP 的 KeepAlive 机制意图在于保活、心跳，检测连接错误。

4.30 - 4

16. 聚集索引和非聚集索引的区别

聚集索引指在表中的数据都会有各自的主键，在B+树存为一个键值。也就是以B+树索引的键值而构建的B+树索引。

非聚集索引指将主键以外的键值构成为B+树的索引。

非聚集索引的叶子节点不存储表中的数据，而是存储该列的主键，再根据主键去查找需要的数据。

17. HTTP Status Code

• 1：临时响应，表示请求已经被接受，客户应该等待服务器采取进一步行动。【HTTP 1.0 没有 1 开头的状态码】
  • 100：表示服务器已经接收了请求头，客户端可以继续发送请求主体。
• 2：服务已经被服务器接受。
  • 200：请求成功，返回希望得到的响应头。
  • 204：成功处理请求，但没有返回任何内容。WiFi登录连接到 Web认证页面。
  • 206：服务器已经成功处理了部分 GET 请求。
  • 207：之后的消息是 XML 消息，根据自请求的数量，会包含一系列独立的响应代码。

• 3：重定向
  • 301：永久重定向。
  • 302：临时重定向，以后应当以当前请求的地址为准。
  • 303：临时重定向，重定向到另一个资源，但不是原始地址的替代引用。
  • 304：请求的资源与已有的版本相同，没有修改。
• 4：客户端错误
  • 400：明显的客户端错误，错误的请求语法，无效的请求。
  • 401：未认证。表示当前的客户端需要验证 Authorization。
  • 403：服务器理解，但是拒绝执行，包含了不执行的理由。
  • 404：请求失败，允许用户的后续请求，但不揭示不执行的理由。
  • 405：方法不允许。
• 5：服务器错误
  • 500： 服务器无法完成对请求的处理。
  • 502：从上游服务器接收到的无效响应。
  • 503：服务器正在停机维护。

断点续传用的哪个状态码：206

18. HTTP 1.1 vs HTTP 2.0 vs HTTP 3.0

HTTP 1.1 采用纯文本格式传输， HTTP 2.0 多了一个二进制帧层。HTTP 1.1 允许在同一条连接上发起多个请求，当多个数据包同时抵达时，由于他们之间无法交互，有可能会发生队头阻塞，如果添加了并行的多个TCP连接，会受到并发连接数量的限制。

HTTP 2.0 则是建立单个TCP连接，允许客户端为多个数据流划分权重优先级，数据流中由许多二进制帧，根据他们的标签进行重新组织。

HTTP 1.1 由于资源内联，所以请求 html 的时候一起把 .css 等文件一起接收了，对于多个使用了相同资源的页面，造成重复的资源收发。HTTP 2.0 采用服务器推送的方式，提前告知客户端将要传输的资源，如果客户端拒绝，就可以不必接收重复的文件了。

HTTP 1.1 头部始终用纯文本格式传输，请求越多，头部越大，造成负担。HTTP 2.0 可以将数据拆分为头部帧和数据帧，利用压缩算法对其进行压缩。

QUIC 的多路复用和 HTTP2 类似。在一条 QUIC 连接上可以并发发送多个 HTTP 请求 (stream)。但是 QUIC 的多路复用相比 HTTP2 有一个很大的优势。

QUIC 一个连接上的多个 stream 之间没有依赖。这样假如 stream2 丢了一个 udp packet，也只会影响 stream2 的处理。不会影响 stream2 之前及之后的 stream 的处理。

19. 乐观锁和悲观锁

乐观锁：操作数据时认为数据不会被其他线程更新，不加锁，操作以后通过版本号判断操作是否合法。适合读多写少。

悲观锁：操作数据时认为数据很可能被其他线程更新，加锁，更新完后释放，但是会造成其他线程阻塞。适合读少写多。

5.1 - 5

20. 进程通信方式及其优缺点、应用场景

• 管道原理

  • 优点：容易知道数据是否被读取了
  • 缺点：数据大小受限。通信效率低，不适合频繁地交换数据，一般是单向，如果要双向必须创建两条管道。匿名管道只能在父子进程间创建，应用范围小。
  • 应用场景：一个进程的输出作为另一个进程输入的场景。

  ---

  System IPC：

  两个或多个进程间，想要共享内存，他们就要组成一个组，共享的内容在这几个进程的虚拟内存的一个固定区域映射，这时用来签别组的ID号的就是project id。

• 消息队列：

  • 底层是链表：用事先约定的 key 唯一标识一个消息队列。IPC_PERM存储权限和进程uid gid，指针 msg_first, msg_last，分别代表队列头和队列尾。
  • 进程：msgctl()控制, msgget()创建, msgrcv()接收, msgsnd()发送。
  • 和管道的区别：
    • 匿名管道生命周期取决于进程，消息队列生命周期取决于内核。
    • 命名管道属于文件，消息队列是特定的数据结构。
    • 管道属于流式存取，消息队列属于块式存取。【类似于 TCP vs UDP】
  • 优点：克服了信号传递信息少，管道缓冲区大小受限的问题
  • 缺点：通信不及时，MSGMAX限制消息体的大小，不适合较大数据的传输。进程对消息队列读写数据，会发生用户态 copy_to_user 与内核态 copy_from_user 的切换。
  • 应用场景：二进制块数据，因为每个数据块可以有不同的种类，不像管道一样要先进先出

• 信号量：在信号量结构中进行 P V 的原子操作，让计数器减一或加一（在0和1之间变化）。 如果某个进程操作以后变为负数，就会阻塞该进程，超过一就会忽略该操作。

  • 优点：可以保证进程的执行顺序，使得共享资源任意时刻只被一个进程控制，实现了互斥和同步。
  • 缺点：数量有限，如果使用信号量的进程突然崩溃，可能会导致锁定的信号量无法恢复。
  • 应用场景：进程间需要同步

• 共享内存：

  • 1. 创建共享内存段shmget(IPC key, size, shmflg)

2. 将进程附加到已经创建的共享内存段shm_at(shmid, shmaddr, shmflg)
   3. 将进程从已经附加到的共享内存段分离shm_dt(shmaddr)
   4. 控制已经附加上的共享内存段shm_ctl(shmid, 命令, 共享内存结构体指针)

• 优点：无需多次拷贝数据，提高进程间通信速度（最快）。
• 缺点：多个进程同时修改一块内存，可能发生冲突。
  • 应用场景：生产者消费者模式

---

• 信号：

  • 1. 发送：进程 kill()传入进程id，信号事件，线程pgkill()传入线程组id，线程id，信号事件。每个进程有一个信号事件等待队列，一个进程内的多个线程会共享该进程的信号事件等待队列，每个线程有自己的信号事件等待队列。

    2. 阻塞和屏蔽：如果收到多次某个常规信号，内核只会记录一次，如果是 POSIX 引入的多次某个实时信号，内核都会记录。sigprocmask()允许用户设定接收到某个信号的阻塞状态，一个信号被阻塞以后，不会触发该信号对应的处理函数，但是仍然可以添加到信号事件等待队列中。比如解除阻塞以后，可以继续处理在阻塞期间收到的信号。

    3. 响应和处理：一般发生在内核执行异常、中断、系统调用等返回到用户态的时刻。

       a. 忽略。

       b. 用户处理函数：用户注册的信号处理函数。属于用户态代码，

       c. 内核默认处理函数：用户没有注册处理函数。一般都是杀死或者忽略。

    4. 可重入性：信号函数允许多个任务并发使用。

       a. 不使用静态数据，或者静态数据只读。

       b. 尽量只使用本地数据。

       c. 全局共享数据使用时必须被保护。（避免死锁）

       d. 不调用不可重入函数。

  • 优点：虽然信号量也有通知的功能，但需要进程主动查询计数器或者陷入阻塞等待。信号不需要阻塞，就会切换到对应的信号事件处理函数中。（唯一的异步通信方式）

  • 缺点：单向通知，信息短。

  • 应用场景：

    • 前台输入特殊终端字符
    • 系统异常
    • 系统状态变化
    • 调用kill函数

• 套接字

  • 优点：本地套接字使用了和网络套接字同一套接口，既能发送数据报，也能进行字节流的传输。
  • 缺点：对于每次和客户端建立连接都要建立一个套接字，资源开销大。
  • 应用场景：跨网络实现进程间通信

21. 线程间同步及系统调用，互斥与同步（信号量、管程、锁）

同步：

• POSIX 信号量
  • 有别于 System V IPC 信号量。
  • 信号量函数：
    • sem_init(信号量，信号量类型，信号量初始值)：初始化一个未命名的信号量【不可重复初始化】
    • sem_destroy(信号量)：销毁信号量，释放其占有的资源【不可销毁被其他线程等待的信号量】
    • sem_wait(信号量)：减一。若为信号量是0，则阻塞。
    • sem_trywait(信号量)：非阻塞版本的 sem_wait。若为信号量不是0，则减一。若为信号量是0，则返回-1。
    • sem_post(信号量)：加一。
• 互斥锁
  • 进入关键代码段，获取互斥锁并加锁。离开关键代码段，解锁。用于同步线程对共享数据的访问。
  • 互斥锁API
    • pthread_mutex_init(mutex, 属性)：初始化
    • pthread_mutex_destroy(mutex)：销毁互斥锁，释放其占用的内核资源。【不可销毁一个加锁的互斥锁】
    • pthread_mutex_lock(mutex)：原子操作加锁，如果已经加锁，则阻塞，等待其解锁。
    • pthread_mutex_trylock(mutex)：非阻塞的加锁操作，如果已经加锁，返回EBUSY。
    • pthread_mutex_unlock(mutex)：解锁。如果其他线程正在等待这个互斥锁，这些线程中的某一个会获得它。
  • 属性
    • 共享权限
    • 1. 可以被跨进程共享
      2. 只能被和锁初始化线程隶属于同一个进程的线程哥共享。
    • 锁的类型
    • 1. 普通锁：当一个线程已经加锁，其他线程加锁会形成一个等待队列。前一个解锁后，按优先级获得。【重复加锁或解锁】
      2. 检错锁：对已经加锁的检错锁加锁，或者已经解锁的检错锁解锁，返回错误。
      3. 嵌套锁：可以重复加锁，但其他线程获得这个锁之前，要有相应次数地解锁。
      4. 默认锁。上面三者之一。对已经加锁的检错锁加锁，或者已经解锁的检错锁解锁，后果未知
• 条件变量
  • 在线程之间同步共享数据的值。共享数据到达某个值，唤醒等待这个共享数据的线程。
  • 条件变量函数
    • pthread_cond_init 初始化指定属性
    • pthread_cond_destroy 销毁条件变量，释放其占用的内核资源。
    • pthread_cond_broadcast 以广播的方式唤醒所有等待目标条件变量的线程。如果线程确认是自己被唤醒，则执行，不是则继续等待。
    • pthread_cond_signal
    • pthread_cond_wait 调用之前mutex已经加锁，调用时把线程放入等待队列，mutex解锁
• 读写锁
  • 这把锁加了读锁，其他线程写操作都会阻塞
  • 加了写锁，其他线程的读写操作都会阻塞
  • 函数
    • pthread_rwlock_wrlock
    • pthread_rwlock_rdlock
    • pthread_rwlock_unlock
    • pthread_rwlock_destroy
    • pthread_rwlock_tryrdlock
    • pthread_rwlock_trywrlock
  • 场景：读多写少

22. 死锁原因、检测、预防和避免

死锁产生的原因：

• 互斥访问：一个共享资源同时只能被一个线程持有
• 持有并等待：线程持有并等待一些资源
• 资源非抢占：资源一旦被持有，其他竞争者都拿不到这个资源
• 循环等待：一系列线程等待的关系形成了一个环【关键】

死锁检测：

资源分配表和资源等代表检测是否出现了环。

死锁预防：

• 避免互斥访问：设计新的方法保持同时访问共享资源的正确性。（例如设计一个代理线程获取资源）
• 不允许持有并等待：可以让线程开始操作之前获取所有的资源，或者线程获取某个资源失败后释放之前持有的资源。（例如活锁，立即返回申请失败）
• 允许资源被抢占：要保证被抢占资源的线程正确地恢复。
• 循环等待：可以要求线程按照一定地顺序获取资源

死锁避免：

任一线程需要获取资源都需要向系统申请，系统根据所处的状态，判断能否分配资源给线程。

如果系统中存在一个安全序列，按这个序列调度线程执行可以避免资源不足的情况发生，就说明时安全状态。反之是非安全状态。

具体算法：银行家算法。

23. epoll 的原理，epoll receive返回的数据大小含义

• epoll 把用户关心的文件描述符放在内核的一个事件表里。
  • epoll_create 创建一个额外的文件描述符，来标识内核中的一个事件表。
  • epoll_ctl 传入文件描述符，增加修改删除事件表中的内容。【底层红黑树】
  • epoll_wait 在一段超时时间内等待一组文件描述符上的事件。如果检测到事件就将所有就绪的事件从内核事件表复制到 events 指向的数组中。
• 模式
  • LT水平触发：检测到有事件发生并通知应用程序后，应用程序可以不立即处理该事件，等下次调用epoll_wait时，还会再次通知该事件。只要某个socket处于readable/writable状态，无论什么时候进行epoll_wait都会返回该socket。
  • ET边沿触发：应用程序必须立即处理该事件，后续不会通知。只有某个socket从unreadable变为readable或从unwritable变为writable时，epoll_wait才会返回该socket。【文件描述符也必须非阻塞】
• 优点：
  • 有ET高效模式，适合连接数量多，活动连接少。不需要轮询整个文件描述符集合来检测哪些事件就绪，时间复杂度O（1）
• 缺点：活动连接频繁，回调函数也被触发得更频繁，效率未必比select高

recv()含义：如果大小等于要求数据大小，说明缓冲区可能未读完。

epoll模型，水平触发模式；当socket可写时，会不停的触发socket可写的事件，如何处理？

5.2 - 6

24. epoll 和 select 区别和使用场景,

图片

epoll原理

select原理：

select(被监听的文件描述符总数，可读、可写、异常事件对应的文件描述符集合，select函数的超时时间)

成功返回就绪的文件描述符总数，没有就绪的返回0，失败返回-1。

优点：监控时间精细到微秒，有良好的跨平台可移植性。

缺点：只能处理可读、可写、异常类型事件，每次调用select集合，由于内核对fd_set在线修改，传入的文件描述符集合也不同。

使用场景：活动连接数量多。

同步与异步
同步和异步关注的是消息通信机制 (synchronous communication/ asynchronous communication)
所谓同步，就是在发出一个调用时，在没有得到结果之前，该调用就不返回。但是一旦调用返回，就得到返回值了。
换句话说，就是由调用者主动等待这个调用的结果。

阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态.

阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。
非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。

25. 数据库事务四种隔离级别 ACID

• Atomicity（原子性）：一个事务（transaction）中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。即，事务不可分割、不可约简。
• Consistency（一致性）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设约束、触发器、级联回滚等。
• Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括未提交读（Read uncommitted）、提交读（read committed）、可重复读（repeatable read）和串行化（Serializable）。
• Durability（持久性）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

图示

并发出现的问题：

• 脏读：读了其他事务修改但是没有提交、发生了回滚的数据
• 不可重复读：读了多次其他事务正在修改的的数据，每次读取的结果不同 【UPDATE】
• 幻读：读了多次其他事务正在修改的的数据，每次读取的结果不同 【INSERT/DELETE】

四种隔离级别：

• 读未提交：读取其他事务修改但是没有提交的数据（可能发生脏读、不可重复读、幻读）
• 读已提交：读取其他事务修改且提交的数据（可能发生不可重复读、幻读）
• 可重复读：其他事务修改且提交，并且自己也提交，才能读取到修改的事务（MySQL的隔离级别，可能幻读）
• 可串行化：除了两个事务都是读操作不会阻塞以外的操作组合都会阻塞。

隔离级别实现原理：

• 每条记录更新的时候都会写入回滚操作日志，一条记录在系统中有多个版本。
• 如果当前没有事务用到回滚日志，就删除。

26. 虚表和虚指针对性能的影响

• 表面开销
  • 空间：对于每个包含虚函数的类，都要生成一张虚函数表。对于每个包含虚函数的类的实例，都要创建一个虚指针。
  • 时间：增加了一次内存寻址，通过虚指针查找虚函数表。
• 隐藏开销
  • 由于需要通过虚指针间接寻址，所以此时 CPU 会发生分支预测，如果预测失败，就要冲刷流水线，重新进行取指，译码的操作。

27. STL 容器的种类，底层数据结构，增删改查的复杂度(vector, list, map)

博客

• 种类：

  • 序列式

    • vector

    • list

    • queue

    • deque

      • 头部尾部插入删除：O(1)

        中间插入删除：O(N)

        查找：O(N)

    • stack

    • heap

    • priority_queue

    • slists

  • 关联式
    • map
    • hash_table
    • tree
    • set

• 底层数据结构

  • vector

    • 头部插入删除：O(N)

      尾部插入删除:O(1)

      中间插入删除：O(N)

      查找：O(N)

      优点：支持随机储存，查询效率高

      缺点：在头部和中间插入删除元素效率低，需要移动内存

      适用场景：适用于元素结构简单，变化小，并且频繁随机访问的场景

  • list

    • 任何位置的插入删除：O(1)(假设告诉了你插入删除的位置，不需要你线查找再删除)

      头尾查询：O(1)

      其他位置查询：O（N）

  • map

    • map由红黑树实现，其元素都是键值对，每个元素的键是排序的准则，每个键只能出现一次，不允许重复

    • 它提供一对一的hash

      • 第一个可以称为关键字(key)，每个关键字只能在map中出现一次
      • 第二个可能称为该关键字的值(value)

      map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的，后边我们会见识到有序的好处。比如一个班级中，每个学生的学号跟他的姓名就存在著一对一映射的关系。

• 增删改查的复杂度

  • 增删改查基本是O(log N)

数组

map vs unordered_map

1. map始终保证遍历的时候是按key的大小顺序的，这是一个主要的功能上的差异
2. map可以做范围查找，而unordered_map不可以。
3. map的iterator除非指向元素被删除，否则永远不会失效。unordered_map的iterator在对unordered_map修改时有时会失效。
4. 因为3，所以对map的遍历可以和修改map在一定程度上并行（一定程度上的不一致通常可以接受），而对unordered_map的遍历必须防止修改
5. map的iterator可以双向遍历，这样可以很容易查找到当前map中刚好大于这个key的值，或者刚好小于这个key的值

5.3 - 7

28. 实习项目流程

从流量中筛选出攻击者流量、关键基础设施的流量，对筛选出的流量做进一步分析,从海量的网络流量中筛选出黑客攻击流量或关基流量，为后续的流量深入分析建立可行的坚实基础。网络流量中完成目标流量筛选，并将目标的标签信息（国家、行业等）通过流量携带出去。网络空间测绘引擎黑客攻击IP威胁情报,从海量的网络流量中筛选出精准的黑客攻击流量，将待分析的流量吞吐下降数个量级，达到最终可分析的目的

SDN网络控制器实现了控制与转发分离，对网络实现集中控制，必然离不开和网络设备建立连接或者BGP协议簇的邻居关系进行交互，部分场景可能高频次的进行数十万条协议路由的收发、过滤与计算，因此走较短且简单的路径连接到网络设备，将直接决定了SDN网络控制器的工作效率与可靠性。

另一方面，SDN网络控制器是软件和系统化的产品，和其他软件产品一样将会面临较频繁的版本迭代、扩缩容、故障处理乃至迁移等运维行为造成的诸多问题，容器化是简化运维的有效手段，特别是当容器数量增多时，k8s容器云平台是更好的选择。

SDN网络控制器容器化后通常需要两张网卡eth0/eth1在容器内，他们的ip地址分别称为北向地址和南向地址，北向地址用于REST api接口以供上层业务调用，而南向地址用于南向接口与网络设备交互。

• 基于ASIC：全端口线速转发，低延时，低功耗。

• P4可编程模型：协议无关的全流水线可编程架构。吸收了SDN数据平面与控制平面分离的思想，促进了网络协议的发展。其次 P4 让数据平面的可编程性更加灵活，弥补了 OpenFlow 等技术的不可重配置、协议无关、平台无关的缺点。

• 通过与 Tofino 一起供的 Capilano 软件开发环境（SDE）P4 编译器工具 链，用户现在可以编译其 P4 程序，

• 从网络流量中筛选出目标的流量，从可编程交换机的端口发送出去。可支持黑客攻击流量筛选和关基流量筛选。

// Client端 
//    int l_times_r = Call(ServerAddr, Multiply, lvalue, rvalue)
1. 将这个调用映射为Call ID。这里假设用最简单的字符串当Call ID的方法
2. 将Call ID，lvalue和rvalue序列化。可以直接将它们的值以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr，这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功，那么就将结果反序列化，并赋给l_times_r

// Server端
1. 在本地维护一个Call ID到函数指针的映射call_id_map，可以用std::map<std::string, std::function<>>
2. 等待请求
3. 得到一个请求后，将其数据包反序列化，得到Call ID
4. 通过在call_id_map中查找，得到相应的函数指针
5. 将lvalue和rvalue反序列化后，在本地调用Multiply函数，得到结果
6. 将结果序列化后通过网络返回给Client

protobuf，只是对象序列化协议

语言中立，支持多种语言；
基于 IDL 文件定义服务，通过 proto3 工具生成指定语言的数据结构、服务端接口以及客户端 Stub；
通信协议基于标准的 HTTP/2 设计，支持双向流、消息头压缩、单 TCP 的多路复用、服务端推送等特性，这些特性使得 gRPC 在移动端设备上更加省电和节省网络流量；
序列化支持 PB（Protocol Buffer）和 JSON，PB 是一种语言无关的高性能序列化框架，基于 HTTP/2 + PB, 保障了 RPC 调用的高性能。

REST的约束条件有：

1. 统一接口

2. 无状态

3. 缓存

4. 客户端-服务器

5. 分层系统

6. 按需代码（可选）

7. CDN 核心的两个模块？

调度，缓存（负载均衡）

（1）内容库模块

包括源站、内容中心、区域中心等，作为CDN中的核心部分，提供的功能是对内容资源进行一系列的操作，如存储并管理内容资源、将内容分发给下级节点等，并提供内容在CDN中的多副本分布式存储，从而实现系统存储资源、计算资源以及宽带资源的合理利用。

（2）流服务缓存模块

作为CDN中直接为用户提供流服务的模块，在面对用户请求时，将先在本地查找用户请求的内容，当本地名优命中是，则将请求转发到上级节点，并一边从内容服务器获取资源，一边对外提供服务。其中，缓存功能分担了内容库的压力，并加速了服务。采用多种开源软件相结合来设计流服务缓存模块。

CDN缓存时间会对“回源率”产生直接的影响。若CDN缓存时间较短，CDN边缘节点上的会经常失效，导致频繁回源，增加了源站的负载，同时也增大的访问延时；若CDN缓存时间太长，会带来更新时间慢的问题。开发者需要增对特定的业务，来做特定的缓存时间管理

2. 负载均衡用了什么组件（设备？软件）

   https://cloud.tencent.com/developer/article/1004723

3. 有哪几个核心的技术点来实现 Docker ？

   Docker 底层的核心技术包括 Linux 上的命名空间（Namespaces）、控制组（Control groups）、Union 文件系统（Union file systems）和容器格式（Container format）。

   Docker 采用了 C/S 架构，包括客户端和服务端。Docker 守护进程 （Daemon）作为服务端接受来自客户端的请求，并处理这些请求（创建、运行、分发容器）。

   客户端和服务端既可以运行在一个机器上，也可通过 socket 或者 RESTful API 来进行通信。

   

   Docker 基本架构

   Docker 守护进程一般在宿主主机后台运行，等待接收来自客户端的消息。

   Docker 客户端则为用户提供一系列可执行命令，用户用这些命令实现跟 Docker 守护进程交互。

4. Docker技术演变

5. Docker 和 虚拟机的区别

6. CDN配置中心核心模块，能够做哪些事情

7. channel 关闭了还能读吗，关闭了怎么知道能不能读，能不能继续写，channel实现，channel close的时候会发生什么事情，关闭的时候会发送什么信号，goroutine数量，GMP模型，free()-buffer-cache

8. 实习里做的比较难的事情

9. CDN配置秒级下发如何优化

29. SYN 洪泛攻击

发生：第二次握手时，服务器发送 SYN ACK 之后就等待客户端的下一次响应，如果客户端不发送 ACK 来完成第三次握手，那么服务器终止半开连接，回收资源，但这过程可能要等待一分钟或以上。如果大量的客户端不完成第三次握手，服务器的连接资源就会被耗尽。

解决：使用 SYN cookie。

​ 第二次握手，TCP 使用 SYN 报文段的源和目标 IP 和端口号利用散列函数生成初始 TCP 序列号，发送特殊的初始序列号的 SYNACK 分组。

​ 第三次，如果客户端没有发来 ACK， TCP 就没有分配资源。如果客户端发来ACK，服务端则根据源和目标 IP 和端口号利用散列函数处理，结果加一，如果刚好等于 ACK 的确认字段，说明客户端合法，生成一个具有套接字的全开连接。

30. GMP 调度器

GMP

G：goroutine 的缩写，每次 go func() 都代表一个 G，无限制。使用 struct runtime.g，包含了当前 goroutine 的状态、堆栈、上下文。

M：工作线程(OS thread)也被称为 Machine，使用 struct runtime.m，所有 M 是有线程栈的。

P：“Processor”是一个抽象的概念，并不是真正的物理 CPU——逻辑处理器。

引入一个结构P，它代表M所需的上下文环境，也是处理用户级代码逻辑的处理器。它负责衔接M和G的调度上下文，将等待执行的 G 与 M 对接。当 P 有任务时需要创建或者唤醒一个 M 来执行它队列里的任务。所以 P/M 需要进行绑定，构成一个执行单元。

第四层：Goroutine调度器：每个M对应了一个P，P对应了一个local runnable queue，如果满了可以放到 global runnable queue。每次P想要取出一个G，先看runtext中有没有内容，如果没有就从自身的队列取，如果都为空，则调用findrunable()阻塞地取，最后偷其他P的G。

第三层：用户空间 ：M（Machine）

第二层：内核空间 ：操作系统调度器

第一层：硬件 ：CPU

Work-stealing

当一个 P 执行完本地所有的 G 之后，并且全局队列为空的时候，会尝试挑选一个受害者 P，从它的 G 队列中窃取一半的 G。否则会从全局队列中获取(当前个数/GOMAXPROCS)个 G。

Syscall

调用 syscall 后会解绑 P，然后 M 和 G 进入阻塞，而 P 此时的状态就是 syscall，表明这个 P 的 G 正在 syscall 中，这时的 P 是不能被调度给别的 M 的。如果在短时间内阻塞的 M 就唤醒了，那么 M 会优先来重新获取这个 P，能获取到就继续绑回去，这样有利于数据的局部性。

P1 和 M 脱离后目前在 idle list 中等待被绑定（处于 syscall 状态）。而 syscall 结束后 M 按照如下规则执行直到满足其中一个条件：

尝试获取同一个 P(P1)，恢复执行 G

尝试获取 idle list 中的其他空闲 P，恢复执行 G

找不到空闲 P，把 G 放回 global queue，M 放回到 idle list

31. Goruntine

5.4 - 8

32. bitmap

33. Go GC

在垃圾收集器开始工作时，程序中不存在任何的黑色对象，垃圾收集的根对象会被标记成灰色，垃圾收集器只会从灰色对象集合中取出对象开始扫描，当灰色集合中不存在任何对象时，标记阶段就会结束。

1. 清理终止阶段；
   1. 暂停程序，所有的处理器在这时会进入安全点（Safe point）；
   2. 如果当前垃圾收集循环是强制触发的，我们还需要处理还未被清理的内存管理单元；
2. 标记阶段；
   1. 将状态切换至 _GCmark、开启写屏障、用户程序协助（Mutator Assiste）并将根对象入队；
   2. 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；
   3. 开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器；
   4. 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；
   5. 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段；
3. 标记终止阶段；
   1. 暂停程序、将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序；
   2. 清理处理器上的线程缓存；
4. 清理阶段；
   1. 将状态切换至 _GCoff 开始清理阶段，初始化清理状态并关闭写屏障；
   2. 恢复用户程序，所有新创建的对象会标记成白色；
   3. 后台并发清理所有的内存管理单元，当 Goroutine 申请新的内存管理单元时就会触发清理；

34. Go defer

• 功能：用于关闭文件描述符、关闭数据库连接以及解锁资源。

• 时间：defer 传入的函数不是在退出代码块的作用域时执行的，它只会在当前函数和方法返回之前被调用。

• type _defer struct {
      siz       int32 参数和结果的内存大小
      started   bool
      openDefer bool
      sp        uintptr 栈指针的程序计数器
      pc        uintptr 调用方的程序计数器
      fn        *funcval 关键字中传入的函数
      _panic    *_panic 触发延迟调用的结构体
      link      *_defer 是否经过开放编码的优化
  }
  [`runtime._defer`](https://draveness.me/golang/tree/runtime._defer) 结构体是延迟调用链表上的一个元素，所有的结构体都会通过 `link` 字段串联成链表。
  
  因为在编译期间我们已经创建了 [`runtime._defer`](https://draveness.me/golang/tree/runtime._defer) 结构体，所以在运行期间 [`runtime.deferprocStack`](https://draveness.me/golang/tree/runtime.deferprocStack) 只需要设置一些未在编译期间初始化的字段，就可以将栈上的 [`runtime._defer`](https://draveness.me/golang/tree/runtime._defer) 追加到函数的链表上
  
  
  
  ### 35. git
  创建版本库：		修改和提交：		   查看提交历史：		   	撤销：							分支标签：					远程操作：
  git clone		git status			git log				 git reset --hard HEAD			git branch				git remote -v
  git init		git diff			git log -p <file>	 git checkout HEAD <file>	 	git branch <new-branch> git remote show
                git add 								 							    git tag					git remote add
                git mv old new															git tag -d				git fetch
                git rm																							git pull
                git commit -m																					git push
  

## 5.5 - 9

###  36. Go 网络模型

![image-20210507174843102](/home/aliceshair/.config/Typora/typora-user-images/image-20210507174843102.png)

client 连接 server 的时候，listener 通过 accept 调用接收新 connection。

每一个新 connection 都启动一个 goroutine 处理。

accept 调用会把该 connection 的 fd 连带所在的 goroutine上下文信息封装注册到 epoll 的监听列表里去。

当 goroutine 调用 conn.Read 或者 conn.Write 等需要阻塞等待的函数时，会被 gopark 给封存起来并使之休眠，让 P 去执行本地调度队列里的下一个可执行的 goroutine,往后 Go scheduler 会在循环调度的 runtime.schedule() 函数以及 sysmon 监控线程中调用 runtime.netpoll 以获取可运行的 goroutine 列表并通过调用injectglist 把剩下的 g 放入全局调度队列或者当前 P 本地调度队列去重新执行。

netpoll 通过使用非阻塞 I/O,避免让操作网络 I/O 的 goroutine 陷入到系统调用从而进入内核态,因为一旦进入内核态,整个程序的控制权就会发生转移(到内核),不再属于用户进程了,那么也就无法借助于 Go 强大的 runtime scheduler 来调度业务程序的并发了。

而有了 netpoll 之后,借助于非阻塞 I/O ,G 就再也不会因为系统调用的读写而 (长时间) 陷入内核态,当 G 被阻塞在某个 network I/O 操作上时,实际上它不是因为陷入内核态被阻塞住了，而是被 Go runtime 调用 gopark 给 park 住了，此时 G 会被放置到某个 waitqueue 中，而 M 会尝试运行下一个 _Grunnable 的 G,如果此时没有 _Grunnable 的 G 供 M 运行，那么 M 将解绑 P，并进入 sleep 状态。



### 37. 访问一个CDN网址，HTTP请求

假设通过CDN加速的域名为`www.a.com`，接入CDN网络，开始使用加速服务后，当终端用户（北京）发起HTTP请求时，处理流程如下：

1. 当终端用户（北京）向`www.a.com`下的指定资源发起请求时，首先向本地DNS发起域名解析请求。
2. 本地DNS检查缓存中是否有`www.a.com`的IP地址记录。如果有，则直接返回给终端用户；如果没有，则向授权DNS查询。
3. 当授权DNS解析`www.a.com`时，返回域名CNAME www.a.tbcdn.com对应IP地址。
4. 域名解析请求发送至DNS调度系统，并为请求分配最佳节点IP地址。
5. 本地DNS获取DNS返回的解析IP地址。
6. 用户获取解析IP地址。
7. 用户向获取的IP地址发起对该资源的访问请求。

- 如果该IP地址对应的节点已缓存该资源，则会将数据直接返回给用户，请求结束。
- 如果该IP地址对应的节点未缓存该资源，则节点向源站发起对该资源的请求。获取资源后，结合用户自定义配置的缓存策略，将资源缓存至节点，例如，图中的北京节点，并返回给用户，请求结束。

### 38. REST 的指导原则

1. C/S 端分离。

   本质：将用户界面和数据存储分开。

   **优点：**提高用户界面的可移植性，简化服务器组件提高了可伸缩性。

2. 状态无关。

   从客户端到服务器的每个请求都必须包含理解该请求所需的所有信息。任何状态管理都在客户端上进行。

   服务器将不存储有关客户端发出的最新HTTP请求的任何内容。 它将每个请求视为新请求。

   **优点**：无状态的特征大大提高的服务端的健壮性和可拓展性。

   **缺点**：造成传输数据的冗余性，但这种确定对于性能和使用来说，几乎是忽略不计的。

3. 可缓存的。响应中的数据被标记为可缓存或不可缓存。 如果响应是可缓存的，则授予客户端缓存以将响应数据重新用于以后的等效请求的权限。除非明确指出不可能进行缓存，否则所有资源都应允许缓存。

   **优点：**管理良好的缓存部分减少了一些客户端-服务器的交互，从而进一步提高了可伸缩性和性能。

4. 系统分层。

   REST允许使用分层的系统架构，例如，您可以在服务器A上部署API，并在服务器B上存储数据并在服务器C中对请求进行身份验证。 客户端通常无法告知客户端是直接连接到终端服务器还是中间设备。

   没有分层：

@GET
public String myService() {
return “

HELLO

“;
}

   **优点**：层次清晰，便于分离各个同类层次的功能。

5. 统一接口。

   资源应该通过单个URL进行唯一标识，并且只有通过使用网络协议的基础方法（例如带 HTTP 的 DELETE，PUT 和 GET），才有可能操纵资源。

GET /orders/1 ：返回订单编号为1的订单
POST /orders ：增加一个订单
Delete /orders/1 ：删除一个订单编号为1的订单
PUT /orders/1 :更新订单编号为1的订单

6. 按需编码。

   大多数时候，将以 XML 或 JSON 的形式发送资源的静态表示。 但是，如果需要可以自由返回可执行代码以支持应用程序的一部分。

   程序代码在Web服务器上处于非活动状态，直到用户（客户端）使用客户端的Web浏览器请求一个包含指向该代码链接的网页为止。 根据此请求，使用HTTP将网页和程序传输到用户的计算机上。 当页面显示时，代码在浏览器中启动并在用户计算机内部本地执行，直到停止。

   

   

### 39. BASE理论，CAP理论

BASE理论是指，Basically Available（基本可用），Soft-state（软状态），Eventual Consistency（最终一致性）。是基于CAP定理演化而来，是对CAP中一致性和可用性权衡的结果。

核心思想：即使无法做到强一致性，但每个业务根据自身的特点，采用适当的方式来使系统达到最终一致性。

基本可用
指分布式系统在出现故障的时候，允许损失部分可用性，保证核心可用。但不等价于不可用。

软状态
软状态是指允许系统存在中间状态，并且该中间状态不会影响系统整体可用性。即允许系统在不同节点间副本同步的时候存在延时。

最终一致性
系统中的所有数据副本经过一定时间后，最终能够达到一致的状态，不需要实时保证系统数据的强一致性。最终一致性是弱一致性的一种特殊情况。



一致性（C）
数据在多个副本之间是否能够保持一致的特性。当执行数据更新操作后，仍然可保证数据处于一致的状态。

可用性（A）
系统提供的服务必须一直处于可用的状态。对于用户的每一个操作情况总是能够在有限的时间内返回结果。这个有限时间是系统设计之初就指定好的系统运行指标。返回的结果指的是系统返回用户的一个正常响应结果，而不是系统错误信息。

分区容错性（P）
分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。

### 40.  僵尸进程 孤儿进程



当一个进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。此时，子进程虽然已经退出了，但是在系统进程表中还为它保留了一些退出状态的信息。

在进程还未退出之前，它的父进程就已经退出了，一个没有了父进程的子进程就是一个孤儿进程（orphan）。既然所有进程都必须在退出之后被wait()或waitpid()以释放其遗留在系统中的一些资源，。每当出现一个孤儿进程的时候，内核就把孤儿进程的父进程设置为init，而init进程会循环地wait()它的已经退出的子进程。



## 5.6 - 10



### 41. 跳表

要随机插入和删除，以及排序。所以不能使用数组。

为什么不用红黑树：

* 性能：在高并发的情况下，属性结构需要执行一些rebalance等可能涉及到整颗树的操作，对于跳表来说只涉及局部。
* 实现：在复杂度和红黑树相同的情况下，跳表实现简单，直观。

在插入的过程中，跳表中新增的这个结点所在的层数是随机出来的，也不会影响其他结点所在的层数，只需要修改前后的指针，而不需要对多个结点进行调整。



### 42. .o .a .so文件的作用

编译器阶段：

C 预处理器
语法和语义分析
代码生成
优化
汇编
链接载入

.o 称为目标文件，是源代码编译之后产生的二进制代码。

.a 是静态库，这个东西和.o的关系其实很清楚，基本上就是.o打了一个包，把多个.o文件放到一个.a文件里面。所以你标题里的一个问题 .o能不能放进.a？答案是能，而且大家一般就是这样生成.a的。

你编了程序a.out，如果它链接了一个静态库libxx.a那么a.out这个文件里面直接包含了从libxx.a里面来的所有有用的数据。这是静态库的含义，在链接时直接合并到了可执行文件之中。

.so是动态库。动态库则相反，如果你的程序链接了libyy.so，那么libyy.so里面的代码并没有合并到a.out之中，而在a.out真正被执行的时候，加载器才会从你的机器上找到libyy.so，把它加载到你的程序的地址空间里面以便于你能够使用其中的函数。

* 静态链接
* 动态链接





### 43. 重载和覆盖

overload

函数名相同，函数的参数列表不同。

静态编译。

override

函数名相同，函数的参数列表相同。

子类对虚函数继承就是覆盖。属于动态编译。

### 44. 可变参数存放于哪里

可变参数是根据函数的调用约定实现的。

假如我们只考虑整数或者指针，32位的参数都是通过栈来传递，最后一个参数到第一个参数依次入栈，结果通过`eax`传递。64位的参数，前6个通过寄存器传递，剩下的参数通过栈传递，结果通过`rax`传递。

拿 `printf("%d, %d, %d", 1, 2, 3);` 举例，通过第一个参数中% 加字母以及分割符形成的字符串，来决定参数列表的数量和类型，然后根据调用约定到对应的位置去访问它的参数。它只能会盲目地接收之后的参数，不会检查。

## 5.7 - 11

### 45. 缓存策略：写回和写穿

1. LRU - Least Recently Used
   通常用于组相联高速缓存，会有一个age counter（替换index）与每个数组S相关。这个counter最大值就是S，当一个set被访问到，那么比它低的counter就被置为0，其他set自增1。举个例子，有4个set的缓存，原本的counter值是`0-3-2-1`，如果第三个被访问到了，那么counter的值是`1-3-0-2`。
2. FIFO - First-In First-Out
   先进先出策略
3. LFU – Least Frequently Used
   很高效的算法，但很耗资源，通常不用。
4. Round-robin
   有一个指针指向将要被替换的行，当行被替换，指针就会自增1，指针是环形的。
5. Random
   随机策略，每个时序Round-robin就要更新，而不是每个替换操作。

**2. 回写策略**

决定怎么把cache的数据写到内存的位置中去

原因：cache速度远大于RAM(主存)。在必要的时候再统一写入主存，从而减少频繁的相对较慢的对主存的写操作，这样明显能加速系统。

- 写回（write back）
  - 写回是指，仅当一个缓存块需要被替换回内存时，才将其内容写入内存。如果缓存命中，则总是不用更新内存。为了减少内存写操作，缓存块通常还设有一个脏位（dirty bit），用以标识该块在被载入之后是否发生过更新。如果一个缓存块在被置换回内存之前从未被写入过，则可以免去回写操作。CPU只向Cache写入，并用标记加以注明，直到Cache中被写过的块要被进入的信息块取代时，才一次写入主存。
  - 优点是节省了大量的写操作。这主要是因为，对一个数据块内不同单元的更新仅需一次写操作即可完成。这种内存带宽上的节省进一步降低了能耗，因此颇适用于嵌入式系统。
- 写通（write through）
- 即CPU在向Cache写入数据的同时，也把数据写入主存以保证Cache和主存中相应单元数据的一致性。
- 每当缓存接收到写数据指令，都直接将数据写回到内存。如果此数据地址也在缓存中，则必须同时更新缓存。由于这种设计会引发造成大量写内存操作，有必要设置一个缓冲来减少硬件冲突。这个缓冲称作写缓冲器（Write buffer），通常不超过4个缓存块大小。不过，出于同样的目的，写缓冲器也可以用于写回型缓存。
  - 特点是简单可靠，但由于CPU每次更新时都要对主存写入，速度必然受影响。



### 46. 哈希碰撞，对字符串取哈希的方法



### 47. 线程数量如何定义

最佳线程数目 = （（线程等待时间+线程运行时间）/线程运行时间 ）* CPU数目

> 备注这个公式也是前辈们分享的，当然之前看了淘宝前台系统优化实践的文章，和上面的公式很类似，不过在CPU数目那边，他们更细化了，上面的公式只是参考。不过不管什么公式，最终还是在生产环境中运行后，再优化调整。

对于 CPU 密集型来说，理论上 `线程数量 = CPU 核数（逻辑）` 就可以了，但是实际上，数量一般会设置为 `CPU 核数（逻辑）+ 1`， 计算密（CPU）集型的线程恰好在某时因为发生一个页错误或者因其他原因而暂停，刚好有一个“额外”的线程，可以确保在这种情况下CPU周期不会中断工作。

于 I/O 密集型程序：

> 最佳线程数 = `(1/CPU利用率)` = `1 + (I/O耗时/CPU耗时)`

这是一个CPU核心的最佳线程数，如果多个核心，那么 I/O 密集型程序的最佳线程数就是：

> 最佳线程数 = `CPU核心数` *`(1/CPU利用率)` = `CPU核心数`\*( `1 + (I/O耗时/CPU耗时)`）



### 48. 为什么要进程池和线程池

* 进程池是由服务器预先创建的一组子进程，这些子进程的数目在3-10个之间（一般情况）；线程池中的线程数量一般和CPU数量差不多。进程池中的所有子进程都运行着相同的代码，并具有相同的属性，比如优先级，PGID等相对于动态创建子进程，现在只需选择一个已经存在的子进程，代价要小的多。

  * 主进程使用某种算法主动选择子进程。最简单常用的算法是随机算法和轮流选取（Round-Robin)算法

  * 主进程和所有子进程通过一个共享的工作队列来同步，子进程在该队列上都是睡眠态。当有新的任务到来时，主进程将任务添加到工作队列中。这将唤醒正在等待任务的子进程。

    不过只有一个子进程获得新任务的“接管权”，它可以从工作队列中取出并执行它，而其他子进程将继续睡眠在工作队列上。

    当选择好子进程后，主进程还需要使用某种通知机制来告诉目标子进程有新进程需要处理，并传递必要的数据。

    最简单的方法是，在父进程和子进程之间预先建立好一条管道，然后通过该管道来实现所有进程间通信

* 创建线程/进程

线程只不过是共享虚拟地址空间和文件描述符表的进程而已。由某一进程产生的线程是该主线程（父进程）的子进程。

## 5.8 - 12

### 49. auto展开推断原理





### 50. Docker 和虚拟机的区别

![preview](https://pic2.zhimg.com/v2-c2a31e2008835b2974170ad1dbac0d42_r.jpg?source=1940ef5c)



## 8.28 - 13

### 51. InnoDB与MyISAM的区别

1. InnoDB 支持事务，MyISAM 不支持事务
2. InnoDB 支持外键，而 MyISAM 不支持
3. InnoDB 是聚簇索引，MyISAM 是非聚簇索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB必须要有主键，通过主键索引效率很高。
4. InnoDB 最小的锁粒度是行锁，MyISAM最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞
5. InnoDB 不保存表的具体行数，而MyISAM会保存，所以MyISAM在执行`select count(*)`更快



### 52. 自己实现一个 vector



### 53. 零拷贝

零拷贝的步骤为：

1）DMA将数据拷贝到DMA引擎的内核缓冲区中；

2）将数据的位置和长度的信息的描述符加到套接字缓冲区；

3）DMA引擎直接将数据从内核缓冲区传递到协议引擎；

可以看出，零拷贝并非真正的没有拷贝，还是有2次内核缓冲区的DMA拷贝，只是消除了内核缓冲区和用户缓冲区之间的CPU拷贝。Linux中主要的零拷贝函数有sendfile、splice、tee等。



### 54. Linux 线程调度策略

**linux内核的三种 调度策略 ：** 

- SCHED_OTHER 分时调度策略，（默认的）
- SCHED_FIFO实时调度策略，先到先服务
- SCHED_RR实时调度策略，时间片轮转 



## 8.29 - 14



### 55. 常用TCP UDP端口，区别

Telnet(远程登录)、FTP(文件传输协议)、SMTP(简单邮件传输协议)。//TCP

NFS(网络文件系统)、SNMP(简单网络管理系统)、DNS(主域名称系统)、TFTP(通用文件传输协议) 

端口：21 FTP
端口：22 SSH

端口：23 Telnet

端口：25 SMTP
端口：53 Domain Name Server（DNS）



- 连接
  - TCP是面向连接的传输层协议，即传输数据之前必须先建立好连接。
  - UDP无连接。
- 服务对象
  - TCP是点对点的两点间服务，即一条TCP连接只能有两个端点
  - UDP支持一对一，一对多，多对一，多对多的交互通信。
- 可靠性
  - TCP是可靠交付：无差错，不丢失，不重复，按序到达。
  - UDP是尽最大努力交付，不保证可靠交付。
- 拥塞控制，流量控制
  - TCP有拥塞控制和流量控制保证数据传输的安全性。
  - UDP没有拥塞控制，网络拥塞不会影响源主机的发送效率。
- 报文长度
  - TCP是动态报文长度，即TCP报文长度是根据接收方的窗口大小和当前网络拥塞情况决定的，流式传输
  - UDP面向报文，不合并，不拆分，保留上面（应用层）传下来报文的边界，直接传输报文。
- 首部开销
  - TCP首部开销大，首部20个字节。
  - UDP首部开销小，8字节。（源端口，目的端口，UDP数据报长度，检验和，每个字段两个字节）

### 

### 56. 十大排序

https://sort.hust.cc/

![image-20210909125413111](/home/aliceshair/.config/Typora/typora-user-images/image-20210909125413111.png)



### 57. 拥塞控制





### 58. B树和 B+树区别

B+树有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了。

**B+树支持range-query(区间查询)非常方便，而B树不支持**。这是数据库选用B+树的最主要原因。

比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。

B树的优势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询，而B+树由于非叶节点只是索引部分，这些节点中只含有其子树中的最大(或最小)关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是继续向下直到叶子节点。因此在B+树中，无论查找成功与否，都是走了一条从根到叶子节点的路径。

有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。
另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。 mysql底层存储是用B+树实现的，因为内存中B+树是没有优势的，但是一到磁盘，B+树的威力就出来了。



#### 3.21 

#### 59. 系统调用

1. **应用程序** 代码调用系统调用( xyz )，该函数是一个包装系统调用的 **库函数** ；
2. **库函数** ( xyz )负责准备向内核传递的参数，并触发 **软中断** 以切换到内核；
3. CPU 被 **软中断** 打断后，执行 **中断处理函数** ，即 **系统调用处理函数** ( system_call )；
4. **系统调用处理函数** 调用 **系统调用服务例程** ( sys_xyz )，真正开始处理该系统调用；



 **执行态切换** 过程如下：

1. **应用程序** 在 **用户态** 准备好调用参数，执行 int 指令触发 **软中断** ，中断号为 0x80 ；
2. CPU 被软中断打断后，执行对应的 **中断处理函数** ，这时便已进入 **内核态** ；
3. **系统调用处理函数** 准备 **内核执行栈** ，并保存所有 **寄存器** (一般用汇编语言实现)；
4. **系统调用处理函数** 根据 **系统调用号** 调用对应的 C 函数—— **系统调用服务例程** ；
5. **系统调用处理函数** 准备 **返回值** 并从 **内核栈** 中恢复 **寄存器** ；
6. **系统调用处理函数** 执行 ret 指令切换回 **用户态** ；