冲！(for Job-Interview)

语言八股

Golang

• 变量声明的:=简短模式 只能在函数内部使用，不能用来声明全局变量

• defer的顺序是栈的顺序，后进先出。先执行return，再执行defer

• 下面这段代码：

  func main() {
  	slice := []int{1, 2, 3}
  	for index, val := range slice {
  		fmt.Println(index, &val)
  	}
  }

  输出是：

  0 0xc00001a098
  1 0xc00001a098
  2 0xc00001a098

  在 for…range 循环里是不断给val赋新的值，并没有开辟新的空间

• slice的append

  • 不要忘记5个零值

    s := make([]int, 5)
    s = append(s, 1, 2, 3)
    fmt.Println(s)

    结果是[0 0 0 0 0 1 2 3]

  • 直接append一个slice

    s := make([]int, 3)
    s = append(s, []int{1, 2, 3}...)
    fmt.Println(s)

    结果是[0 0 0 1 2 3]，注意在被append的slice后要加...

• 函数多返回值

  func funcMui(x,y int)(sum int,error){
      return x+y,nil
  }

  如果有返回值被命名，那么所有的返回值都要被命名，上图返回值列表写成(sum int, err error)更好

  如果有多个返回值or有返回值被命名，返回值列表就要加括号

• new()与make()的区别

  new(T) 和 make(T, args) 是 Go 语言内建函数，用来分配内存，但适用的类型不同。

  new(T) 会为 T 类型的新值分配已置零的内存空间，并返回地址（指针），即类型为 *T的值。换句话说就是，返回一个指针，该指针指向新分配的、类型为 T 的零值。适用于值类型，如数组、结构体等。

  make(T,args) 返回初始化之后的 T 类型的值，这个值并不是 T 类型的零值，也不是指针 *T，是经过初始化之后的 T 的引用。make() 只适用于 slice、map 和 channel.

• 结构体的比较

  • 结构体只能比较是否相等，但是不能比较大小。

  • 相同类型的结构体才能够进行比较，结构体是否相同不但与属性类型有关，还与属性顺序相关，sn3 与 sn1 就是不同的结构体；

    sn1 := struct {
        age  int
        name string
    }{age: 11, name: "qq"}
        
    sn3 := struct {
        name string
        age  int
    }{age: 11, name: "qq"}

  • 如果 struct 的所有成员都可以比较，则该 struct 就可以通过 == 或 != 进行比较是否相等，比较时逐个项进行比较，如果每一项都相等，则两个结构体才相等，否则不相等；

    • 可以比较的类型：bool、数值型、字符、指针、数组等
    • 不能比较的类型：切片、map、函数等

  结构体的声明也要注意：

  • 结构体成员不需要用逗号隔开，声明的同时赋值单独用冒号

    sn1 := struct {
        age  int
        name string
    }{age: 11, name: "qq"}

  • 定义新的结构体类型：type关键字

    type Person struct {
    	age  int
    	name string
           child *Person
    }
    me := Person{age: 1, name: "nhx"}
    fmt.Println(me)

    键值之间以:分隔，键值对之间以,分隔。

  结构体成员中只能包含结构体的指针类型，包含非指针类型会引起编译错误。

  访问结构体成员只能用.操作符，不论是指针还是值

• 类型别名与类型定义：

  Go 是强类型语言，类型别名可以互相赋值，类型定义不可以互相赋值

  

• 字符串拼接

  str := "abc" + "123"

  fmt.Sprintf(“abc%d”, 123)

  strings.Join()、buffer.WriteString()

  第七天

面经八股

• 数据库事务的ACID特性：

  原子性（Atomicity）：【一个事务必须都发生或都不发生（基于日志的Undo log机制）】

  事务是一个不可再分割的工作单元，一个事务中的操作要么都发生，要么都不发生。

  一致性（Consistency）：【终极目标】

  数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性。

  隔离性（Solation）：【并发的事务之间不影响（脏读、幻读和不可重复读）（加锁）（MVCC也借助了Undo log）】

  多个事务并发访问时，事务之间是隔离的，一个事务不应该影响其它事务运行效果。

  持久性（Durability）：【保证数据不会因宕机等故障而消失（Redo log)】

  在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。

  ---

  在转账的例子中，A-100，B+100，如果只是A-100，B的账户没有变，这时认为同时违反了原子性和一致性

  原子性和一致性的区别是什么？

  在事务处理的ACID属性中，一致性是最基本的属性，其它的三个属性都为了保证一致性而存在的。

• HTTP的多路复用和长连接分别是什么，区别是什么

  另外，TCP连接复用与HTTP连接复用：

  在HTTP 1.0中，客户端的每一个HTTP请求都必须通过独立的TCP连接进行处理，而在HTTP 1.1中，对这种方式进行了改进。客户端可以在一个TCP连接中发送多个HTTP请求，这种技术叫做HTTP复用（HTTP Multiplexing）。

  它与TCP连接复用最根本的区别在于，TCP连接复用是将多个客户端的HTTP请求复 用到一个服务器端TCP连接上，而HTTP复用则是一个客户端的多个HTTP请求通过一个TCP连接进行处理。前者是负载均衡设备的独特功能；而后者是HTTP 1.1协议所支持的新功能，目前被大多数浏览器所支持。

自己的记录

用于回答自己的经验等相关问题

消息队列

根据青训营的课专门整理了一篇笔记

RDBMS

根据青训营的课专门整理了一篇笔记

队头堵塞

关于队头阻塞（Head-of-Line blocking），看这一篇就足够了

平时用到的Linux命令

• netstat

  Netstat 命令用于显示各种网络相关信息，如网络连接，路由表，接口状态 (Interface Statistics)及其相关查询等等。

  

• ping

  Linux ping 命令用于检测主机。

  执行 ping 指令会使用 ICMP 传输协议，发出要求回应的信息，若远端主机的网络功能没有问题，就会回应该信息，因而得知该主机运作正常。

  

• ssh

  ssh免密登录详细原理：包括client和server如何鉴别对方

  ssh免密登录的时候的简易流程：即client在把公钥交给server之后双方用A的公钥和私钥相互传递一次信息

  

  ssh免密登录实操：实际上只需要client生成秘钥后把公钥上传到server，上面的剩下的步骤就会自动完成

  但是上传所使用的ssh-copy-id命令需要输入密码登录

图解MySQL

how_select

// 在 product 表中，查询 id = 1 的记录
select * from product where id = 1;

执行一条 SQL 查询语句，期间发生了什么？

• 连接器：建立连接，管理连接、校验用户身份；
• 查询缓存：查询语句如果命中查询缓存则直接返回，否则继续往下执行。MySQL 8.0 已删除该模块；
• 解析 SQL，通过解析器对 SQL 查询语句进行词法分析、语法分析，然后构建语法树，方便后续模块读取表名、字段、语句类型；
• 执行 SQL：执行 SQL 共有三个阶段：
  • 预处理阶段：检查表或字段是否存在；将 select * 中的 * 符号扩展为表上的所有列。
  • 优化阶段：基于查询成本的考虑， 选择查询成本最小的执行计划；
  • 执行阶段：根据执行计划执行 SQL 查询语句，从存储引擎读取记录，返回给客户端；

• MySQL的二级索引

  建立二级索引的方法及其搜索过程

• 有MySQL联合索引(A, B, C)，那么AC查询会用到索引吗？【BC查询呢？】

  AC和BC都会用到，但是原因不一样

row_format

MySQL 的 NULL 值是怎么存放的？

MySQL 的 Compact 行格式中会用「NULL值列表」来标记值为 NULL 的列，NULL 值并不会存储在行格式中的真实数据部分。

NULL值列表会占用 1 字节空间，当表中所有字段都定义成 NOT NULL，行格式中就不会有 NULL值列表，这样可节省 1 字节的空间。

MySQL 怎么知道 varchar(n) 实际占用数据的大小？

MySQL 的 Compact 行格式中会用「变长字段长度列表」存储变长字段实际占用的数据大小。

值得一提的是，「变长字段长度列表」要逆序存放，这样可以使得位置靠前的记录的真实数据和数据对应的字段长度信息可以同时在一个 CPU Cache Line 中，这样就可以提高 CPU Cache 的命中率。

占用空间：

varchar(n) 中 n 最大取值为多少？

一行记录最大能存储 65535 字节的数据，但是这个是包含「变长字段字节数列表所占用的字节数」和「NULL值列表所占用的字节数」。所以， 我们在算 varchar(n) 中 n 最大值时，需要减去这两个列表所占用的字节数。

如果一张表只有一个 varchar(n) 字段，且允许为 NULL，字符集为 ascii。varchar(n) 中 n 最大取值为 65532。

计算公式：65535 - 变长字段字节数列表所占用的字节数 - NULL值列表所占用的字节数 = 65535 - 2 - 1 = 65532。

如果有多个字段的话，要保证所有字段的长度 + 变长字段字节数列表所占用的字节数 + NULL值列表所占用的字节数 <= 65535。

多个字段的例子：

行溢出后，MySQL 是怎么处理的？

如果一个数据页存不了一条记录，InnoDB 存储引擎会自动将溢出的数据存放到「溢出页」中。

Compact 行格式针对行溢出的处理是这样的：当发生行溢出时，在记录的真实数据处只会保存该列的一部分数据，而把剩余的数据放在「溢出页」链表中，然后真实数据处用 20 字节存储指向溢出页的地址，从而可以找到剩余数据所在的页。

Compressed 和 Dynamic 这两种格式采用完全的行溢出方式，记录的真实数据处不会存储该列的一部分数据，只存储 20 个字节的指针来指向溢出页。而实际的数据都存储在溢出页中。

• 多个溢出页之间采用链表关联

index_interview

• 为什么 MySQL InnoDB 选择 B+tree 作为索引的数据结构？

  相同深度下，能查询更多的节点

  相同节点数量时，深度更小，查询更快

  叶子结点采用双链表连接，适合顺序查询

  1、B+Tree vs B Tree

  B+Tree 只在叶子节点存储数据，而 B 树 的非叶子节点也要存储数据，所以 B+Tree 的单个节点的数据量更小，B+Tree一个节点在存储引擎中占用一个16KB的页，一个页能包含的节点个数（即子节点的个数）更多，相同深度的树包含的节点数目更多；在相同的磁盘 I/O 次数下，就能查询更多的节点。

  

  另外，B+Tree 叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点。

  2、B+Tree vs 二叉树

  对于有 N 个叶子节点的 B+Tree，其搜索复杂度为$$O(log_dN)$$，其中 d 表示节点允许的最大子节点个数为 d 个。

  在实际的应用当中， d 值是大于100的，这样就保证了，即使数据达到千万级别时，B+Tree 的高度依然维持在 34 层左右，也就是说一次数据查询操作只需要做 34 次的磁盘 I/O 操作就能查询到目标数据。

  而二叉树的每个父节点的儿子节点个数只能是 2 个，意味着其搜索复杂度为 $$O(log_2N)$$，这已经比 B+Tree 高出不少，因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。

  3、B+Tree vs Hash

  Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。

  但是 Hash 表不适合做范围查询，它更适合做等值的查询，这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。

• 联合索引的两项优化：

  • 索引下推：

    索引下推能够减少二级索引在查询时的回表操作，提高查询的效率，因为它将 Server 层部分负责的事情，交给存储引擎层去处理了。

    原本需要Server层中的执行器来判断读取到的记录是否符合查询条件，这种判断就包含判断【联合索引中范围查询之后的查询的条件是否符合】；但是索引下推可以在联合索引遍历过程中，对联合索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

  • 索引区分度：

    另外，建立联合索引时的字段顺序，对索引效率也有很大影响。越靠前的字段被用于索引过滤的概率越高，实际开发工作中建立联合索引时，要把区分度大的字段排在前面，这样区分度大的字段越有可能被更多的 SQL 使用到。

    区分度就是某个字段 column 不同值的个数「除以」表的总行数，如性别的区分度就很小，而UUID的区分度就比较大，适合做索引或排在联合索引列的靠前的位置。

• 索引的适用场景/不适用场景：

  

• SQL语句前加上explain得到的结果的参数解释

• 有什么优化索引的方法？

  • 前缀索引优化；

    减小索引字段大小，增加一个索引页中存储的索引值，提高查询速度

    局限性是order by无法使用前缀索引，且前缀索引无法使用覆盖索引

  • 覆盖索引优化；

    尽量从二级索引中获取query的目标，避免回表，减少I/O操作

  • 主键索引最好是自增的；

    插入新数据时都是追加操作，不需要移动原有数据；且避免产生页分裂，避免影响查询效率

  • 防止索引失效

    索引失效的查询语句就不会走索引

  • 索引列用NOT NULL约束

    索引列存在 NULL 时难以优化，且NULL值会占用空间

page

图解网络

TCP/IP model

• 同一台设备上的进程间通信：管道、消息队列、共享内存、信号等方式

  不同设备上的进程间通信：网络通信（需要一套通用的网络协议）

• 应用层的协议：

  HTTP（Hyper Text Transfer Protocol）超文本传输协议

  FTP（File Transfer Protocol）文件传输协议

  Telnet（专有名词）远程登录服务器

  DNS（Domain Name System）域名系统

  SMTP（Simple Mail Transfer Protocol）简单邮件传输协议

  DHCP（Dynamic Host Configuration Protocol）动态主机配置协议 基于UDP

  DHCP潜讲，DHCP深入，DHCP服务器放在哪里合适

  传输层的协议：

  TCP

  UDP

  网络层的协议：

  IP

  ARP

  ICMP（Internet Control Message Protocol）Internet控制报文协议

  ping 和 tracert是两个常用网络管理命令，ping 用来测试网络可达性，tracert 用来显示到达目的主机的路径。ping和 tracert 都利用 ICMP 协议来实现网络功能，它们是把网络协议应用到日常网络管理的典型实例

• 应用层是工作在操作系统中的用户态，传输层及以下则工作在内核态

  传输层：多路复用/分用服务、可靠数据传送、带宽保证及延迟保证等

  网络层：路由、存储转发

  （传输层和网络层都有CC和FC）

  传输层实现的是应用到应用的通信，真正的设备间通信是网络层负责的

• IP地址 IPv4是32位，每8位一段分成四段

  还分为网络号和主机号，需要配合子网掩码来确定网络号和主机号

• 为什么有了MAC地址，还需要IP地址：方便子网划分从而方便路由转发

  为什么有了IP地址，还需要MAC地址：因为 IP 地址是要设备上线以后，才能根据他进入了哪个子网来分配的，在设备还没有 IP 地址的时候（或者分配 IP 地址的过程中），我们还需要用 MAC 地址来区分不同的设备。

  另外，从始至终包头中的源IP和目的IP是不变的，但是每一跳源MAC地址和目的MAC地址都会改变

  整个网络流程

• 每一层的封装格式

  

what_happen_url

• MTU和MSS

  

• 源端口号和目的端口号封装在TCP报文中（传输层）

  源IP和目的IP封装在IP报文中（网络层）

• 当存在多个网卡时，在填写源地址 IP 时，就需要判断到底应该填写哪个地址。这个判断相当于在多块网卡中判断应该使用哪个一块网卡来发送包。

  这个时候就需要根据路由表规则，来判断哪一个网卡作为源地址 IP。

• ARP过程分为两种情况：目的主机在同一子网和目的主机不在同一子网

  这两种情况需要源主机自行根据掩码判断属于哪一种

  如果发现不在同一子网，需要先发到网关路由器，于是需要ARP来获取网关的MAC地址

• 数据链路层的网卡要在包头和包尾都封装的原因是：

  开头加上报头和起始帧分界符，在末尾加上用于检测错误的帧校验序列。

• 交换机是做什么工作的？

  1. 将电信号转换成数字信号（即包的接收）

  2. 通过包末尾的FCS校验错误

  1和2都与网卡的作用想同，但是交换机与网卡的不同之处在于（所以目标MAC地址至少也是下一条路由器的地址了）

  

  除此之外，还有

  3. 根据（MAC地址-端口）的映射表进行包的转发

     如果没有对应的MAC地址，交换机会把数据包发送到除了源端口之外的所有端口（接收方MAC地址是广播地址时交换机也会这么做）

• 路由器

  路由器的转发表中一条记录会同时有目的地址和网关两项内容

  • 如果网关是一个 IP 地址，则这个IP 地址就是我们要转发到的目标地址，还未抵达终点，还需继续需要路由器转发。
  • 如果网关为空，则 IP 头部中的接收方 IP 地址就是要转发到的目标地址，也是就终于找到 IP 包头里的目标地址了，说明已抵达终点。

• 数据包到达服务器之后一步步“拆封”的过程：

  • 检验MAC地址是不是自己

  • 检验IP地址是不是自己，并根据 IP 头中协议项，确认传输层协议类型

  • （如果是TCP）检验TCP报头中的序列号是不是自己想要的

    由于TCP的建立是基于（ip, port）的，所以已经限定好了端口，即相应端口的应用从自己的TCP连接队列中检验新到的包的序列号是否符合预期

  

• “如果知道你电脑的mac地址，我可以直接给你发消息吗？”

  MAC地址只能是同一子网内两个设备之间通信时使用的，如果你要从大老远给我发消息，是离不开 IP 的。

how_os_deal_network_package

电脑与电脑之间通常都是通过网卡、交换机、路由器等网络设备连接到一起，那由于网络设备的异构性，国际标准化组织定义了一个七层的 OSI 网络模型，但是这个模型由于比较复杂，实际应用中并没有采用，而是采用了更为简化的 TCP/IP 模型，Linux 网络协议栈就是按照了该模型来实现的。

TCP/IP 模型主要分为应用层、传输层、网络层、网络接口层四层，每一层负责的职责都不同，这也是 Linux 网络协议栈主要构成部分。

• 图示发送和接收的过程：

  

• 发送一次网络数据的时候，会涉及几次内存拷贝操作？

  第一次，调用发送数据的系统调用的时候，内核会申请一个内核态的 sk_buff 内存，将用户待发送的数据拷贝到 sk_buff 内存，并将其加入到发送缓冲区。

  第二次，在使用 TCP 传输协议的情况下，从传输层进入网络层的时候，每一个 sk_buff 都会被克隆一个新的副本出来。副本 sk_buff 会被送往网络层，等它发送完的时候就会释放掉，然后原始的 sk_buff 还保留在传输层，目的是为了实现 TCP 的可靠传输，等收到这个数据包的 ACK 时，才会释放原始的 sk_buff 。

  第三次，当 IP 层发现 sk_buff 大于 MTU 时才需要进行。会再申请额外的 sk_buff，并将原来的 sk_buff 拷贝为多个小的 sk_buff。

http_interview

• 目前HTTPS是绝对安全的，只要

  • 服务器私钥不被泄露

    服务器私钥被泄露的话，持有服务器私钥的第三方就可以伪装成服务器，因为数字证书大家都可以获取，有了服务器私钥，第三方就可以解密客户端用服务器公钥加密的数据；【ECDHE解决这个问题】

  • 客户端不信任非法网站的安全证书

    上述操作会导致第三方可以冒充服务器，作为中间人转发+监听客户端和服务器之间的通信

    （这种情况下，客户端就相当于在用第三方的公钥加密自己的数据）

• TLS/SSL

  SSL 是洋文 “Secure Sockets Layer” 的缩写，中文叫做「安全套接层」。

  SSL标准化之后的名称改为 TLS（是 “Transport Layer Security” 的缩写），中文叫做 「传输层安全协议」。

http_optimize

图解系统

1_hardware

how_cpu_run

• 计算机基本结构为 5 个部分，分别是运算器、控制器、存储器、输入设备、输出设备，这 5 个部分也被称为冯诺依曼模型。

• 程序的CPU时间：

  

• CPU的位宽：

  通常来说 64 位 CPU 的地址总线是 48 位，而 32 位 CPU 的地址总线是 32 位，所以 64 位 CPU 可以寻址更大的物理内存空间。如果一个 32 位 CPU 的地址总线是 32 位，那么该 CPU 最大寻址能力是 4G，即使你加了 8G 大小的物理内存，也还是只能寻址到 4G 大小的地址，而如果一个 64 位 CPU 的地址总线是 48 位，那么该 CPU 最大寻址能力是 2^48，远超于 32 位 CPU 最大寻址能力。

  硬件的 64 位和 32 位指的是 CPU 的位宽，软件（操作系统也是一种软件）的 64 位和 32 位指的是指令的位宽。

  如果 32 位指令在 64 位机器上执行，需要一套兼容机制，就可以做到兼容运行了。但是如果 64 位指令在 32 位机器上执行，就比较困难了，因为 32 位的寄存器存不下 64 位的指令；

storage

一图流

• SRAM：Static Random-Access Memory 静态随机存储器

  叫做「静态」存储器，是因为只要有电，数据就可以保持存在，而一旦断电，数据就会丢失了。

• DRAM：Dynamic Random-Access Memory 动态随机存取存储器

  叫做「动态」存储器，是因为数据会被存储在电容里，电容会不断漏电，所以需要「定时刷新」电容，才能保证数据不会被丢失

• SSD：Solid-state disk 固态硬盘

• HDD：Hard disk drive 机械硬盘

how_to_make_cpu_run_faster

CPU的速度远高于内存速度，因而CPU速度会受限于内存速度，所以需要CPU cache来加速内存

要想写出让 CPU 跑得更快的代码，就需要写出缓存命中率高的代码，CPU L1 Cache 分为数据缓存和指令缓存，因而需要分别提高它们的缓存命中率：

• 对于数据缓存，我们在遍历数据的时候，应该按照内存布局的顺序操作，这是因为 CPU Cache 是根据 CPU Cache Line 批量操作数据的，所以顺序地操作连续内存数据时，性能能得到有效的提升；
• 对于指令缓存，有规律的条件分支语句能够让 CPU 的分支预测器发挥作用，进一步提高执行的效率；

另外，对于多核 CPU 系统，线程可能在不同 CPU 核心来回切换，这样各个核心的缓存命中率就会受到影响，于是要想提高线程的缓存命中率，可以考虑把线程绑定 CPU 到某一个 CPU 核心。

cpu_mesi

没看

how_cpu_deal_task

没看

soft_interrupt

中断是一种异步的事件处理机制，可以提高系统的并发处理能力。

操作系统收到了中断请求，会打断其他进程的运行，所以中断请求的响应程序，也就是中断处理程序，要尽可能快的执行完，这样可以减少对正常进程运行调度地影响。

为了避免由于中断处理程序执行时间过长，而影响正常进程的调度，Linux 将中断处理程序分为上半部和下半部：

• 上半部，对应硬中断，由硬件触发中断，主要是负责耗时短的工作，特点是快速执行；
• 下半部，对应软中断，由内核触发中断，主要是负责异步处理上半部未完成的工作，通常都是耗时比较长的事情，特点是延迟执行；

还有一个区别，硬中断（上半部）是会打断 CPU 正在执行的任务，然后立即执行中断处理程序，而软中断（下半部）是以内核线程的方式执行，并且每一个 CPU 都对应一个软中断内核线程，名字通常为「ksoftirqd/CPU 编号」，比如 0 号 CPU 对应的软中断内核线程的名字是 ksoftirqd/0

float

为什么负数要用补码表示？

负数之所以用补码的方式来表示，主要是为了统一和正数的加减法操作一样，毕竟数字的加减法是很常用的一个操作，就不要搞特殊化，尽量以统一的方式来运算。

十进制小数怎么转成二进制？

十进制整数转二进制使用的是「除 2 取余法」，十进制小数使用的是「乘 2 取整法」。

计算机是怎么存小数的？

计算机是以浮点数的形式存储小数的，大多数计算机都是 IEEE 754 标准定义的浮点数格式，包含三个部分：

• 符号位：表示数字是正数还是负数，为 0 表示正数，为 1 表示负数；
• 指数位：指定了小数点在数据中的位置，指数可以是负数，也可以是正数，指数位的长度越长则数值的表达范围就越大；
• 尾数位：小数点右侧的数字，也就是小数部分，比如二进制 1.0011 x 2^(-2)，尾数部分就是 0011，而且尾数的长度决定了这个数的精度，因此如果要表示精度更高的小数，则就要提高尾数位的长度；

用 32 位来表示的浮点数，则称为单精度浮点数，也就是我们编程语言中的 float 变量，而用 64 位来表示的浮点数，称为双精度浮点数，也就是 double 变量。

0.1 + 0.2 == 0.3 吗？

不是的，0.1 和 0.2 这两个数字用二进制表达会是一个一直循环的二进制数，比如 0.1 的二进制表示为 0.0 0011 0011 0011… （0011 无限循环)，对于计算机而言，0.1 无法精确表达，这是浮点数计算造成精度损失的根源。

因此，IEEE 754 标准定义的浮点数只能根据精度舍入，然后用「近似值」来表示该二进制，那么意味着计算机存放的小数可能不是一个真实值。

0.1 + 0.2 并不等于完整的 0.3，这主要是因为这两个小数无法用「完整」的二进制来表示，只能根据精度舍入，所以计算机里只能采用近似数的方式来保存，那两个近似数相加，得到的必然也是一个近似数。

2_os_structure

linux_vs_windows

计算机是由各种外部硬件设备组成的，比如内存、cpu、硬盘等，如果每个应用都要和这些硬件设备对接通信协议，那这样太累了，所以这个中间人就由内核来负责，让内核作为应用连接硬件设备的桥梁，应用程序只需关心与内核交互，不用关心硬件的细节。

• 用户态和内核态：

  内核具有很高的权限，可以控制 cpu、内存、硬盘等硬件，而应用程序具有的权限很小，因此大多数操作系统，把内存分成了两个区域：

  • 内核空间，这个内存空间只有内核程序可以访问；
  • 用户空间，这个内存空间专门给应用程序使用；

  用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间。因此，当程序使用用户空间时，我们常说该程序在用户态执行，而当程序使内核空间时，程序则在内核态执行。

• 应用程序如果需要进入内核空间，就需要通过系统调用，下面来看看系统调用的过程：

  

  内核程序执行在内核态，用户程序执行在用户态。当应用程序使用系统调用时，会产生一个中断。发生中断后， CPU 会中断当前在执行的用户程序，转而跳转到中断处理程序，也就是开始执行内核程序。内核处理完后，主动触发中断，把 CPU 执行权限交回给用户程序，回到用户态继续工作。

• 内核架构

  对于内核的架构一般有这三种类型：

  • 宏内核，包含多个模块，整个内核像一个完整的程序；（Linux）
  • 微内核，有一个最小版本的内核，一些模块和服务则由用户态管理；（Harmony）
  • 混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；（Windows NT）

  Linux 的内核设计是采用了宏内核，Window 的内核设计则是采用了混合内核。

  这两个操作系统的可执行文件格式也不一样， Linux 可执行文件格式叫作 ELF，Windows 可执行文件格式叫作 PE。

3_memory

vmem

比较关键

虚拟地址和物理地址都是内存管理的概念，虚拟地址是进程使用的逻辑地址，物理地址是访问==内存==时实际使用的地址，而不是外存

内存相当于保存了一大部分的页，是外存的缓存，断电后内存中的内容会丢失。有了更快的内存，可以避免每次都访问外存。

每个进程都会有自己的虚拟地址空间，即都会有自己的页表。

缺页异常：进程访问的页不在内存中，进程开辟的空间都会在页表中拥有对应的页表项映射。对于在内存中的页，页表项会直接映射为内存地址；对于不在内存中的已经被换出到外存的页，页表（疑似是页表）会记录该物理页在磁盘上的对应位置，以便在缺页时找到该页并换入。多级页表只需要一直维护第一级页表，即可覆盖全部虚拟地址空间，剩余的次级页表在需要的时候按需创建即可。

段表、页表都在内存中；TLB在CPU中，也可以称作cache。

缺页时页表怎么变？

段页式内存管理，增加了硬件成本，同时增加了读写数据时访问内存的次数，增加了系统开销。但是提高了内存的利用率。

为了在多进程环境下，使得进程之间的内存地址不受影响，相互隔离，于是操作系统就为每个进程独立分配一套虚拟地址空间，每个程序只关心自己的虚拟地址就可以，实际上大家的虚拟地址都是一样的，但分布到物理地址内存是不一样的。作为程序，也不用关心物理地址的事情。

每个进程都有自己的虚拟空间，而物理内存只有一个，所以当启用了大量的进程，物理内存必然会很紧张，于是操作系统会通过内存交换技术，把不常使用的内存暂时存放到硬盘（换出），在需要的时候再装载回物理内存（换入）。

那既然有了虚拟地址空间，那必然要把虚拟地址「映射」到物理地址，这个事情通常由操作系统来维护。

那么对于虚拟地址与物理地址的映射关系，可以有分段和分页的方式，同时两者结合都是可以的。

内存分段是根据程序的逻辑角度，分成了栈段、堆段、数据段、代码段等，这样可以分离出不同属性的段，同时是一块连续的空间。但是每个段的大小都不是统一的，这就会导致外部内存碎片和内存交换效率低的问题。

于是，就出现了内存分页，把虚拟空间和物理空间分成大小固定的页，如在 Linux 系统中，每一页的大小为 4KB。由于分了页后，就不会产生细小的内存碎片，解决了内存分段的外部内存碎片问题（相应的会产生内部内存碎片问题）。同时在内存交换的时候，写入硬盘也就一个页或几个页，这就大大提高了内存交换的效率。

再来，为了解决简单分页产生的页表过大的问题，就有了多级页表，它解决了空间上的问题，但这就会导致 CPU 在寻址的过程中，需要有很多层表参与，加大了时间上的开销。于是根据程序的局部性原理，在 CPU 芯片中加入了 TLB，负责缓存最近常被访问的页表项，大大提高了地址的转换速度。

Linux 系统主要采用了分页管理，但是由于 Intel 处理器的发展史，Linux 系统无法避免分段管理。于是 Linux 就把所有段的基地址设为 0，也就意味着所有程序的地址空间都是线性地址空间（虚拟地址），相当于屏蔽了 CPU 逻辑地址的概念，所以段只被用于访问控制和内存保护。

另外，Linux 系统中虚拟空间分布可分为用户态和内核态两部分，其中用户态的分布：代码段、全局变量、BSS、函数栈、堆内存、映射区。进程在用户态时，只能访问用户空间内存；只有进入内核态后，才可以访问内核空间的内存。

最后，说下==虚拟内存有什么作用==？

• 第一，虚拟内存可以使得进程的运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
• 第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
• 第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。

malloc

Linux进程的内存示意图：

• malloc分配内存时有两种方式：

  • 方式一：通过 brk() 系统调用从堆分配内存
  • 方式二：通过 mmap() 系统调用在文件映射区域分配内存；

  如果用户分配的内存小于 128 KB，则通过 brk() 申请内存；如果用户本次分配的内存大于 128 KB，则通过 mmap() 申请内存；（阈值可变）

• malloc分配的是虚拟内存，只有在内存被读写的时候，触发缺页异常，才回去分配内存，建立虚拟内存和物理内存之间的映射关系。

• malloc(1) 实际上预分配 132K 字节的内存

• malloc 通过 brk() 方式申请的内存，free 释放内存的时候，并不会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用；
  malloc 通过 mmap() 方式申请的内存，free 释放内存的时候，会把内存归还给操作系统，内存得到真正的释放。

• mmap的缺点：频繁通过 mmap 分配的内存话，不仅每次都会发生运行态的切换，还会发生缺页中断（在第一次访问虚拟地址后），这样会导致 CPU 消耗较大。

  brk的缺点：随着系统频繁地 malloc 和 free ，尤其对于小块内存，堆内将产生越来越多不可用的碎片，导致“内存泄露”

• malloc分配的内存块前面会有16字节保存内存块的描述信息，如该内存块的大小

  这样当执行 free() 函数时，free 会对传入进来的内存地址向左偏移 16 字节，然后从这个 16 字节的分析出当前的内存块的大小，自然就知道要释放多大的内存了。

  

mem_reclaim

• 内存分配与回收：

  下图中第一个橙色的圆圈内应该是“分配虚拟内存”，先分配的是虚拟内存，在应用程序对这块虚拟内存进行读写时，CPU会去访问这块虚拟内存，这个时候才会触发缺页异常，进入下图中的“Page Fault”阶段

  

• 哪些内存可以被回收？

  总体思路是已经在磁盘中的，直接释放内存；不在磁盘中的，先写入磁盘，再释放内存

  选择回收页的原则依据LRU，实现中LRU基于双向链表

• 回收内存带来的影响：

  只要需要写入磁盘，发生磁盘IO，磁盘IO次数越多，对系统的性能影响越大。

  那么如何减小回收内存对性能的损耗呢？

  补充文件页和匿名页的概念：

  

  首先，文件页的回收操作对系统的影响相比匿名页的回收操作会少一点，因为文件页对于干净页回收是不会发生磁盘 I/O 的，而匿名页的 Swap 换入换出这两个操作都会发生磁盘 I/O。

  所以可以通过积极回收文件页，消极回收匿名页，来减少内存回收的影响；即

  1. 提高对于文件页的回收倾向
  2. 尽早触发 kswapd 内核线程异步回收内存
  3. 如果CPU是NUMA架构，可以调整其回收策略

• OOM机制：

  OOM （Out of Memory）机制

  在经历完直接内存回收后，空闲的物理内存大小依然不够，那么就会触发 OOM 机制，OOM killer 就会根据每个进程的内存占用情况和 oom_score_adj 的值进行打分，得分最高的进程就会被首先杀掉。

alloc_mem

本章讨论在 32 位/64 位操作系统环境下，申请的虚拟内存超过物理内存后会怎么样？

• 在 32 位操作系统，因为进程最大只能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。
• 在 64 位操作系统，因为进程最大只能申请 128 TB 大小的虚拟内存，即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。

程序申请的虚拟内存，如果没有被使用，它是不会占用物理空间的。当访问这块虚拟内存后，操作系统才会进行物理内存分配。

如果这块虚拟内存被访问了，就要看操作系统有没有开启 Swap 机制：

• 如果没有开启 Swap 机制，程序就会直接 OOM；
• 如果有开启 Swap 机制，程序可以正常运行。

cache_lru

==注意问题的问法==，例如下面的问题：

其实就是在问如何改进LRU算法

对应传统LRU算法的两个问题：预读失效 和 缓存污染

• 预读机制，在读取磁盘的时候都会多读一部分到内存，目标是为了借助空间局部性原理减少磁盘的I/O次数

• 缓存污染，可能出现一次读大量的页到内存，这些页只会被访问一次，却会淘汰掉热点数据（Redis中是通过转而使用LFU来解决这个问题的）

• 解决预读失效：

  • Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）；
  • MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：young 区域 和 old 区域。

  这两个改进方式，设计思想都是类似的，都是将数据分为了冷数据和热数据，然后分别进行 LRU 算法。不再像传统的 LRU 算法那样，所有数据都只用一个 LRU 算法管理。

• 解决缓存污染：

  提高数据由冷变热（从冷数据升级为热数据）的门槛。

  如限制冷数据在第二次被访问后才会被加入热数据链表的头部，进一步地可以限制第二次访问与第一次的时间间隔大于1秒才会被升级。

linux_virtual_mem

linux_physical_mem

这两篇像是前面内容的总结，没看

4_process

process_base

• 进程的三个基本状态：运行状态、阻塞状态、就绪状态

  再加上创建状态和结束状态

  

  • 除了上面的状态，还要添加一个挂起状态

    如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间，显然不是我们所希望的，毕竟物理内存空间是有限的，被阻塞状态的进程占用着物理内存就一种浪费物理内存的行为。

    所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

    挂起状态用来描述进程没有占用实际的物理内存空间的情况

    另外，挂起状态可以分为两种：

    • 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
    • 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；
    

• 进程控制块PCB（process control block）

  PCB通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列，如就绪队列、阻塞队列

青训营文章

并发场景下的限流

新来个技术总监，把限流实现的那叫一个优雅，佩服！

常见限流方式之一：计数器

原理好理解，这里补充两种计数器的实现方式：互斥锁（Golang实现sync.Mutex和sync.RWMutex）和原子操作（Golang实现sync/atomic）

（补充：原子操作和互斥锁）

原子操作由底层硬件支持，而锁则由操作系统的调度器实现。锁应当用来保护一段逻辑，对于一个变量更新的保护，原子操作通常会更有效率，并且更能利用计算机多核的优势，如果要更新的是一个复合对象，则应当使用atomic.Value封装好的实现。

常见限流方式之二：滑动窗口

滑动窗口是将计数器的时间区间进一步划分多个格子，以格子为单位右移

计数器是只有一个格子的滑动窗口，格子越多，精度越高，但更新频率越快，计算负担越大，同时无法根本上解决临界点的问题

常见限流方式之三：漏桶

相当于给业务加了个缓冲区队列，同步执行时等待线程会阻塞；异步执行时业务由水桶代理执行，调用方只能知道请求被接受了，不知道请求具体什么时候执行

常见限流方式之四：令牌桶（Token Bucket）

按照一定生成速率在桶中生成令牌，请求到来时从桶里拿令牌，桶为空则阻塞或拒绝请求

令牌桶相对于漏桶的不同：

• 漏桶限制的是最大流出速率
• 令牌桶限制的是平均流入速率，并允许一定程度突发流量

Golang中还有一种限流方式：借助channel进行限流，有点像令牌桶

Golang官方也有自己的基于令牌桶的限流器，见time/rate包的Limiter类型

HTTP协议与websocket协议

• TCP协议本身是全双工的，但我们最常用的HTTP1.1，虽然是基于TCP的协议，但它是半双工的，对于大部分需要服务器主动推送数据到客户端的场景，都不太友好，因此我们需要使用支持全双工的websocket协议。

• 在HTTP1.1里。只要客户端不问，服务端就不答。基于这样的特点，对于登录页面这样的简单场景，可以使用定时轮询或者长轮询的方式实现服务器推送(comet)的效果。

• 对于客户端和服务端之间需要频繁交互的复杂场景，比如网页游戏，都可以考虑使用websocket协议。

• websocket和socket几乎没有任何关系，只是叫法相似。

• 正因为各个浏览器都支持HTTP协议，所以websocket会先利用HTTP协议加上一些特殊的header头进行握手升级操作，升级成功后就跟HTTP没有任何关系了，之后就用websocket的数据格式进行收发数据。

Kafka 科普

字节青训营练习题

DAY1

• 第一题：36进制加法

  nowcoder.36进制加法

• 第二题有点怪，暂且认为是一个DFS/BFS，感觉题目描述的不清楚，没做

• • 第三题：有效 IP 地址（小模拟）

  LeetCode有简化版题目：93. 复原 IP 地址

• HTTP和HTTPS的区别

  Client 在使用 Https 协议访问网站进行通信的过程中，以下说法正确的是？
  A. 只用到了对称加密技术
  B. 只用到了非对称加密技术
  C. 没有用到任何加密技术
  D. 同时用到了对称加密和非对称加密技术

  答案是D，详见小林coding

• 操作系统中堆和栈的区别

  以下哪些是操作系统中堆和栈的区别？
  A. 增长方向
  B. 空间大小
  C. 分配方式
  D. 管理方式

  答案是ABCD，详见操作系统中的堆栈区别

DAY2

• Golang中切片初始化的方式：

  Go 中关于整型切片的初始化，以下正确的是？
  A. s := []int{1, 2, 3, 4, 5}
  B. s := make([]int)
  C. s := make([]int, 0)
  D. s := make([]int, 5, 10)

  答案是ACD，原因：

  • 因为 Golang 语言是静态语言，它不能像动态语言那样，在运行时可以通过分析变量的值，自动确定变量的内存边界，所以在 Golang 语言中，使用变量之前，需要先声明变量，且要求可以通过声明确定变量的内存边界。

• 组原

  以下哪些操作可能触发本地 CPU cache 失效？
  A. 本地读取
  B. 本地写入
  C. 远端读取
  D. 远端写入

  答案是D

DAY3

• 解决哈希冲突的手段：

  以下哪些是解决哈希冲突的手段？
  A. 拉链
  B. 开放地址
  C. 再散列
  D. 滑动窗口

  四种方法解决哈希冲突：

  • 开放定址法

    在开放定址法中根据探查序列生成方式的不同，细分有：线性探查法、平方探查法、双散列函数探查法、伪随机探查法等。

  • 链地址法

  • 再哈希法（再散列法）

  • 公共溢出区法

  本题选ABC

• TLS连接

  建立 TLS1.2 连接需要几次握手？
  A. 3
  B. 4
  C. 6
  D. 7

  • TLS协议在协议栈中的位置

    

  • TCP三次握手，TLS四次握手

    图示连接

    （HTTPS）

  答案是D.7

DAY4

• MYSQL数据库

  MySQL 数据库中是通过以下哪种日志实现 MVCC 机制的？
  A. Undo Log
  B. Redo Log
  C. Binary Log
  D. Slow Log

  答案是A. Undo Log

  • MVCC（Multi-Version Concurrency Control），即多版本并发控制

  • 几种log

    

• 排序

  关于排序算法以下结论正确的是？
  A. 归并排序任何情况下都能保持时间复杂度为 O(n×log n)
  B. 插入排序时间复杂度为 O(n×n)，所以在任何情况下都比快速排序慢
  C. 快速排序的最坏情况下的时间复杂度为 O(n×n)
  D. 希尔排序任何情况下都比插入排序更快

  答案是AC

  • 几种排序算法这里都有介绍

    直接插入排序细节容易忘记（nju面试还问过）

    快排边界问题比较多（下面整理了模板）

    基数排序、计数排序、桶排序是三大不常见的排序，都是对数据分布有苛刻的要求的，或是空间复杂度较高，不通用

    

  • 快排模板（边界问题太多，就记模板吧）：

    • do-while循环多此一举的原因

  • do-while循环判断条件是<和>，不是≤和≥

    • 递归调用的是j和j+1

    void quick_sort(int q[], int l, int r)
    {
        if (l >= r) return;
    
        int i = l - 1, j = r + 1, x = q[l + r >> 1];
        while (i < j)
        {
            do i ++ ; while (q[i] < x);
            do j -- ; while (q[j] > x);
            if (i < j) swap(q[i], q[j]);
        }
        quick_sort(q, l, j), quick_sort(q, j + 1, r);
    }

DAY5

• 关系型数据库RDBMS（Relational Database Management System）

  以下哪些是 RDBMS 跟常见的对象存储系统的不同点？
  A. 数据库支持事务
  B. 数据库向用户暴露 put/get 接口
  C. RDBMS 一般存储结构化数据
  D. 数据库里的数据不能修改，只能删除后重新写入

  答案是AC

• 存储系统IO性能优化

  常见的存储系统 IO 性能优化方式有哪些？
  A. 尽可能多设计随机读写逻辑
  B. 预读
  C. 减少 IO 路径上的内存拷贝
  D. batch 写入

  答案是BCD

  顺序读写和随机读写区别和实现

  顺序读写要远远优于随机读写

DAY6

• MD5

  关于 MD5 以下哪些说法是正确的？
  A. MD5 可以用于加密密码
  B. MD5 不可逆
  C. 对于不同的输入， MD5 一定输出不一样的结果
  D. 对于不同长度的输入，MD5 一定输出相同长度的结果

  答案是BD

  A：MD5加盐做密码检验是可以的，但是不能把他叫做加密，一个加密算法必须要有解密算法，MD5是信息摘要算法

  C：MD5已经被证实无法避免碰撞

• 红黑树

  关于红黑树以下说法正确的是？
  A. 红黑树是平衡二叉树，任意两个子树的高度差不超过 1
  B. 红黑树从一个节点到该节点的子孙节点的所有路径上包含相同数目的红色节点
  C. 红黑树插入节点时最多经过 3 次旋转达到平衡
  D. 红黑树进行插入操作时需要解决红红冲突

  答案是CD

  A：

  红黑树特性之一：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树。

  而“任意两个子树的高度差不超过1”是平衡二叉树的定义，红黑树是“长的子树长度不会超过短的长度的2倍”，所以红黑树牺牲了查找的性能，但是插入和删除的性能更好。

  B：

  应该是：相同数目的黑色节点

  C和D记一下；

  • 除此之外，补充一个：**高度为n的平衡二叉树的最少节点数**：$F(n) = F(n-1) + F(n -2 ) + 1$

DAY7

• 排序

  在最好情况下，下列排序算法中，哪些排序算法所需比较的关键次数最少？
  A. 冒泡
  B. 归并
  C. 快速
  D. 直接插入

  排序的最好情况下的时间复杂度也要记

  冒泡和直接插入最好情况下都是$O(n)$

  归并和快速排序最好情况下都是$O(nlogn)$

  答案是AD

• Golang

  以下哪些是 Go 支持的指针运算？
  A. 通过 & 取地址
  B. 对指针进行自增
  C. 下标运算
  D. 通过 * 解引用

  答案是AD

  Go 语言支持指针，但只支持指针的取址运算符(&) 和解址运算符()，*不支持指针的算术运算

  但是切片可以通过下标访问（上面说的应该是不能给指针取下标）

DAY8

• 计算机网络

  在 MTU=1500 字节的以太网中，TCP 报文的最大分段大小为多少字节？
  A. 1440
  B. 1460
  C. 1420
  D. 1480

  MTU这个概念是指数据帧中有效载荷的最大长度，不包括帧首部的长度。

  所以TCP报文的有效载荷=1500B-20B(IP数据报首部)-20B( TCP报文首部)=1460B

  答案是B

• Skiplist

  关于经典的 Skiplist（原始论文实现）以下结论正确的是？
  A. 每次的查找都从 head 节点的第 0 层（最底层）开始寻找
  B. skiplist 的插入节点的层级都是固定的
  C. skiplist 的元素都是有序的
  D. skiplist 平均查询时间复杂度为 O(log n)

  答案是CD

  关于跳表（Skiplist）可以参考这篇文章

  • 跳表是可以实现二分查找的有序链表。

  • 查找示意图：每次的查找都从 head 节点的最顶层开始查找

    

  • 跳表的插入节点的层级是随机的，使用randomLevel()概率算法来确定节点插入不同层级的概率，再确定最终插入层级

DAY9

• 排序稳定性

  以下哪些排序算法是不稳定的？
  A. 快速排序
  B. 归并排序
  C. 基数排序
  D. 堆排序

  答案是AD

• Golang语言

  关于 Go 语言以下结论正确的是？
  A. 在多核机器中，核数越多，使用多个 goroutines 写入 sync.Map 的性能越好
  B. 只调用一次 rand.Seed，则之后 rand.Int 的生成序列是固定的
  C. 放入 sync.Pool 中的结构体可能随时被回收
  D. Goroutine 的栈不仅会增长而且还会缩容

  答案是BCD

• 本文作者：wan_nan
• 本文链接：https://wan-nan.github.io/2022/12/30/Preparation-for-Job-Interview/
• 版权声明：本博客所有文章除特别声明外，均默认采用 许可协议。