计网

操作系统

内存管理

1.某进程的虚拟内存中，当前要用到的数据会放在主存里面，当前不用的会放在磁盘中

• 当时这一点进程是没有感知的，它会认为当前所有数据都在主存里面，这样设计是为了让程序在逻辑上不用去考虑底层内存的分配问题

2.内存碎片

• 外碎片：分配单元间隙的未使用内存
• 内碎片：分配单元里面的未使用内存

3.内存的分配策略

• 最先分配：把遇到第一个空闲块分配
• 最好分配：把所有空闲块中最合适的空闲块分配，即内碎片最小
• 最坏分配：把所有空闲块中最不合适的空闲块分配，优点在于优先把大的空闲块破碎

进程管理

文件系统管理

I/O设备管理

目录

操作系统

计算机网络

数据库

数据结构与算法

C++

Golang

项目细节和场景设计

操作系统

1.线程独有的资源是什么

• 栈空间，CPU的使用权

2.进程和线程的区别

• 一个进程里包含多个线程
• 进程是操作系统分配资源的基本单位，线程是操作系统执行任务的基本单位
• 进程的通信方式是：
  • 共享内存：这块内存由多个进程共享
  • 管道：半双工通道，是单向的
  • 消息队列：消息的链表，有标识符标记存在内核里面
  • 套接字：socket，可实现不同机器、不同进程之间的通信
  • 信号：通知进程，系统中发生了某种预先规定好的事件
• 线程的通信方式：
  • 互斥量(即锁)
  • 临界区：通过对多线程的串行化来访问公共资源，速度快
  • 信号量：可视作有buffer的互斥锁
  • 事件：针对具有后继任务需要操作的的事件设计，用通知的方式来保持多线程同步

3.同一进程下的线程共享哪些资源

• 堆
• 数据空间
• 静态存储区

4.进程切换开销大是因为进程得去切换环境，例如全局变量、打开的文件

5.进程间通信有什么方式，详细展开说怎么通信

• 共享内存
• 管道
• 信号
• 消息队列
• socket套接字

6.共享内存是并发安全的吗，如何加锁

7.管道两端可以互传数据吗

• 不可以，管道是半双工的，即是单向的

8.浏览器是一个多进程服务

• 每开一个标签页，其实就是多开一个进程
• 设计的目的是避免某一页面出问题影响到其他页面

9.用户态和内核态

• Linux进程的虚拟内存分为用户空间(前3GB)和内核空间(最后1GB)
• 常规操作默认用用户态，使用到内核空间的必须要切换为内核态操作
• 从用户态切换到内核态需要进行中断操作，处理完后还需要恢复操作

10.虚拟内存

• 虚拟内存简单来说就是把外存当作内存来使用，便于缓解物理内存压力的不足
• 实现内存抽象，每个进程都以为自己拥有全部内存，操作虚拟地址的操作都会被转换为操作物理地址

11.多线程访问同一资源

• 需要上锁

12.epoll和select

• epoll
  • 文件描述符FD上限是最大可打开文件数，参考值20w
  • 水平触发和边缘触发(只会通知一次)
  • 通知进程时会直接返回就绪事件，不用去轮询(底层原理是内核里维护一个红黑树和双向链表)
  • 只在注册新事件的时候整体拷贝一遍，开销小
  • 只能在linux上使用，使用逻辑比select复杂
• select
  • FD上限是1024个，可以在linux内核中修改
  • 水平触发，如果程序没有完成I/O操作，那么这个FD还是会被select作为通知
  • 通知进程时只会告知有事件发生，具体地址还需要进程去轮询
  • 每次改变内核中的fd集合时，都需要整体拷贝一遍，开销巨大

13.在4G物理内存的机器上，申请8G内存

• 32位机器上，申请失败
  • 虚拟地址空间：内核占1G，用户占3G，实际最大只能申请3G
• 64位机器上，申请成功，但是实际读写该内存超过时会触发OOM
  • 虚拟地址空间：内核128T，用户128T

14.零拷贝

• 计算机在执行IO操作时，CPU不需要从一个存储区域复制到另一个存储区域，进而减少上下文切换以及CPU的拷贝时间
• 把数据从磁盘缓冲区搬运到内核缓冲区这个工作交给DMA控制器去做，CPU可以去处理其他事务
  • DMA处理完成后，CPU再去把数据从内核拷到用户空间
  • 现在的每个I/O设备基本都有自己的DMA控制器
• kafka就是利用了零拷贝，I/O吞吐量增大，处理海量数据效率才能这么高

计算机网络

1.TCP和IP

• TCP在传输层，IP在网络层
• TCP里包含IP包

2.TCP报文头里包含以下内容

• 源端口号
• 目的端口号
• 序列号：占4字节，表示当前报文的序列号，用于保证传输的有序性
• 校验和
• 窗口：占2字节，表示接收方所能处理的数据量
• 标识位：ACK、SYN、FIN等

3.GET和POST请求的区别

• GET请求
  • 参数通过url明文传递，只能用ASCII码，有长度限制，这个长度是浏览器限制的，实际上http别未有这种限制
  • 浏览器会主动缓存（包括传的参数）
  • 按RFC规范来是只读操作，是安全幂等的(幂等指的是多次执行相同操作，结果都是相同的)
• POST请求
  • 参数放在request body里，有多种编码方式(get只能url编码)
  • 不会被浏览器主动缓存
  • 未指定资源的存放位置，由服务器决定
  • 按RFC规范来说是新增操作，不是安全幂等的(实际上开发者可以不遵循规范，让get也去修改服务器数据)
• PUT请求(其他和POST相似)
  • 参数放在request body里
  • 指定了资源的存放位置
  • 按RFC规范来说是更新操作，是安全幂等的

4.跨域问题是什么，怎么解决跨域问题的，不同服务之间调用会有跨域问题么

• 同源政策保证该网站的资源只能由同源请求执行(域名和端口名一样)，是为了防止别的网站对该网站进行攻击，是浏览器采取的安全策略
• 实现方法是新增一组HTTP首部字段，允许服务器声明哪些源站通过浏览器有权限访问哪些资源
• 对那些可能对服务器数据产生副作用的HTTP请求方法（特别是GET以外的HTTP请求），浏览器必须首先使用OPTIONS方法发起一个预检请求，从而获知服务端是否允许该跨源请求。服务器确认允许之后，才发起实际的HTTP请求
• 不同服务如果部署在不同域名端口上，也会有跨域问题

5.说一下知道的状态码，200是什么，重定向是什么，它的过程是什么，如果重定向的话那么网页是如何获取客户端信息的呢？

• 状态码
  • 1开头表示信息
  • 2开头表示成功（200-请求成功）
  • 3开头表示发生了重定向（301-网页被永久转移到其他URL）
  • 4开头表示客户端错误（404-请求的网页不存在）
  • 5开头表示服务端错误(500-内部服务器错误)
• 重定向是浏览器发送请求到s1之后，s1需要访问s2，但并未在服务器内直接访问，而是由服务器自动向浏览器发送一个响应，浏览器再自动提交一个新的请求，这个请求就是对s2的请求
• s2获取客户端信息还通过第二次浏览器发起的请求获得的
• 对s2的请求是无法获得之前对s1提交的参数的，所以重定向也用来保证表单不重复提交

6.TCP和UDP区别

• TCP面向连接提供可靠服务；UDP是无连接的，尽最大努力交付，但不保证可靠交付，UDP 具有较好的实时性
• TCP连接是1对1，UDP无连接可以1对多
• TCP首部开销20字节，UDP首部开销8字节
• TCP把数据看成字节流，UDP把数据看成报文包

7.为什么TCP更可靠

• 校验和
• 序列号
• 超时重传机制
• 确认应答ACK机制
• 流量控制
• 拥塞控制

8.TCP三次握手，如果改成两次握手会怎么样，那如果我就按两次握手算是建立连接了，那客户端向服务端发数据会怎么样

• 1.会产生历史连接，例如client发了一个seq1的连接请求，然后client重启后重新发了一个seq2连接请求，此时client想要的结果是建立seq2的连接忽略seq1的连接，如果是两次握手的话会存在两个连接，其中历史连接会浪费资源
• 2.没有同步双方的初始序列号，比如client可能收不到serve的初始序列号，导致后面的传输序列号乱序，不能保证可靠性
• 3.产生冗余连接浪费资源，比如client发出的某个连接请求经网络延迟很久以后才到serve端，这时serve端回一个SYN+ACK后就默认连接建立的话，client此时并不需要建立连接直接忽略掉，那么serve端会一直等待数据传输导致资源浪费

9.HTTP是基于TCP的吗，HTTPS七次握手，七次握手中什么时候是对称加密什么时候是非对称加密，最后握手结束之后采用什么加密

10.将url输入到浏览器中会发生什么？

• 域名解析
• RAP解析将ip地址解析为物理地址
• TCP三次握手
• 服务端返回响应
• 浏览器将响应渲染成页面

11.单点登录：一次登录后，访问其他页面就不再需要登录

• 用token或者共享cookie实现

12.http版本区别

• http1.0：无状态无连接
• http1.1：长链接默认把Connection设为：keep-alive、增加host域、支持请求管道化
• http2.0：二进制分帧、头部压缩、服务器推送

13.cookie、session和token

• cookie存在客户端，本地易被篡改
• session存在服务端，服务器要为每个用户保留session信息，连接用户过多会造成服务器内存压力过大
• token：客户端后续每次请求中，浏览器会把token作为http header发送给服务器，使用jwt(json web token)加密token是现在主流形式
  • 这种方式的特点就是客户端的token中自己保留有大量信息，服务器没有存储这些信息，而只负责验证，不必进行数据库查询，执行效率大大提高。

14.https的七次握手

• 正常的三次握手
• c->s：TLS版本号+加密套件列表+希望采取的TLS选项
• s->c：加密套件+TLS选项+自己证书+公钥
• c->s：自己证书+对称秘钥(用公钥加密)
• s->c：FINISH

15.实际抓包中，会发现不是四次挥手而是三次挥手

• 因为在某些特定情形下C端不会处在持续传数据的情况
• 所以第二次挥手和第三次挥手合并了
• 这样可以极大地减少断开连接的开销，增加速度

16.close_wait和time_wait

• close_wait是接受端第一次收到FIN报文后，进入的状态，传输数据完成后就结束
• time_wait是发起端在等待接受端结束close_wait后收到FIN报文，进入的状态，等待2MSL时间之后就结束
  • 2MSL默认4分钟

17.http请求和响应报文格式

• 第一行
  • 请求是请求行：方法+url+版本，例如 GET /index/htm HTTP/1.1
  • 响应是响应行：版本+状态码+短语，例如 HTTP/1.1 404 Not Found
• 中间有n行首部行：字段名+值，例如host:www.baidu.com(表示请求资源存在哪个域名上)
• 最后有个请求体(post、put这类常用)

18.https如何保证服务端的证书是可信的

• 客户端将证书的公钥、持有者信息、有效时间等打包，然后进行Hash计算得到一个值h1
• 客户端对证书的签名用公钥进行解密，得到h2
• 比较h1和h2是否相等就可以验证证书是否合法了

19.https出现的性能下降

• TLS额外的四次握手(RSA需要2RTT)
  • 非对称加密算法从RSA改成ECDHE，这样只需要1RTT
    • 该算法由于支持False Start抢跑，客户端可以在TLS协议的第3次握手后，第4次握手前，发送加密的应用数据
  • 升级到TLS1.3，也可以优化成1RTT
    • 1.3客户端在第一次握手的时候就传支持的椭圆曲线，以及这些椭圆曲线对应的公钥，这样服务端收到后，选定一个参数并带上服务端这边的公钥。经过1个 RTT，双方手上已经有生成会话密钥的材料
  • 服务器应该选用ECDSA证书而不是RSA证书，这样可以减少密钥长度
  • 采用会话重用技术
• 握手后的对称加密传输
  • 主流的AES等算法已进行优化，且CPU厂商会针对其做硬件上的优化，这方面开销已经极大减少

20.TCP拥塞控制

• 发送方维护一个拥塞窗口作为发送的大小
  • 出现拥塞的话要减少这个窗口，否则就增大
• 有一个慢开始门限，低于用慢开始算法，高于用拥塞避免算法
  • 慢开始：1,2,4,8….翻倍
  • 拥塞避免：1,2,3,4,5,6….+1

数据库

1.mysql的引擎有三种

• InnoDB：mysql默认引擎，用于事务，默认行锁，适合大规模数据，一张表的qps根据实验应该是8000左右
• MyISAM：不支持事务，适合小规模，默认表锁，mysql之前默认的老引擎
• Memory：数据放到内存中

2.b+树

• b+树的深度浅，每次读一个节点只要一次IO，减少了IO次数
• b+树的IO次数少，b+树的节点可以存多个关键字，并且单个节点默认存16k与磁盘页对齐，这样一次IO就可以传输一个完整节点
• b+支持范围查询和排序操作
• 具体实现：
  • 非叶子节点存的是每个子树的最小主键id，这样就可以根据要查的主键id去判断往哪边的子树往下走
  • 叶子节点按主键id有序存放数据，走到某叶子节点后用二分查找来定位到具体的位置
  • 插入需要旋转平衡开销，因为如果索引节点和数据节点某个已满的话需要拆分，如果两个都满了，还需要再往上加一层索引

3.跳表

• 跳表的深度深，同等高度下存的数据要比b+树少
• 跳表可能出现跨页IO
• 跳表只支持单个关键字的查找
• 具体实现
  • 插入不需要旋转平衡开销，直接在底层节点插入即可，而是否需要把这个数据也加到索引里，依靠随机函数即可
    • 因为理论上为了达到二分的效果，每一层的结点数需要是下一层结点数的二分之一，所以底层新增一个节点时，有0.5的概率需要加到第二层索引，有0.5*0.5的概率加到第三层索引

4.索引选型场景问题

• mysql用b+树实现索引而不是跳表的原因
  • b+树的IO次数少，一是因为节点大小和磁盘页大小对齐一次IO可以传输一个节点，二是b+树深度浅
  • Innodb引擎出现的时候，跳表还没得到广泛应用
• redis用跳表实现有序集合zset而不是b+树的原因
  • redis在内存中运行，所以层高，IO开销大就不再是劣势
  • 跳表的插入效率高，因为不用像b+树一样需要去旋转平衡
• 跳表写性能好：插入不需要去旋转平衡，b+树读性能好：层数低

5.Innodb的next-key lock机制解决幻读

• 里面包含间隙锁和记录锁，间隙锁会锁上记录之间的间隙
• 比如对5到10行的记录上next-key lock就是由(5, 10)之间的间隙锁和加在10上的记录锁组成，左开右闭(5,10]，即5不加锁，10要加锁

6.数据库的锁底层是怎么实现的，类似间隙锁，xx锁这种

• InnoDB并没有采用系统提供的锁机制，而是自己封装了操作系统提供的基本mutex互斥量和event信号量来实现锁
• InnoDB行锁是通过给索引上的索引项加锁来实现的，而不是给表的行记录加锁，通过索引检索数据才使用行级锁，否则将使用表锁

7.Redis是串行但是仍然快的原因

• Redis是单线程的，减去了CPU切换不同线程的开销，并且Redis是在内存里运行的
• Redis的多路复用模型是用epoll实现的

8.Redis是基于键值对的非关系数据库，值的数据类型可以是

• string
• hash
• list
• set
• zset(有序集合)
• Bitmaps(位图)

9.跳表的原理是二分查找，所以快。查询、插入、删除的平均复杂度都是logn

10. redis的哪种数据结构是有序的

• zset

11.mysql的MVCC

• 目的：为了实现事务读数据的时候不需要加锁
• 实现：InnoDB中的MVCC实现是通过undolog日志实现的
  • 执行更新操作时，会把更新前的数据放入undolog里面，并通过隐藏的回滚指针roll_pointer指向
  • 其他的事务，如果需要查询该记录，就会去undolog里面找这个记录的最新历史版本
• MVCC最大的好处是读不用加锁，实现读写不冲突，极大地增加了并发性同时保证了事务的隔离性

12.Innodb的隔离级别

• 读未提交
• 读提交RC：每次读都会更新快照，所有不能解决不可重复读和幻读问题
• 可重复读RR：只在第一次读的时候生成快照，然后后面只有事务内更新了数据才会去更新快照
  • 快照读情况下，根据MVCC机制，用版本号、undolog的方法，可以解决幻读问题
  • 当前读情况下，手动加record lock(记录锁)和gap lock(间隙锁)，即next-key-lock机制，可以解决幻读问题
    • 当前读的情况下只用MVCC不能解决幻读，要加间隙锁才行
• 串行

13.InnoDB的行锁算法有以下3种

• 记录锁record-lock：直接在记录上加锁
• 间隙锁gap-lock：锁定一个范围，但不包括记录本身
• next-key-lock：锁定一个范围和记录本身，解决幻读

14.聚簇索引和非聚簇索引，Innodb默认的是聚簇索引

• 聚簇索引将索引和数据放一块，b+树叶子节点存的是：主键id+数据，查询快+更新代价大
• 非聚簇索引将索引和数据分开放，b+树叶子节点存的是：主键id+数据地址(还需要去磁盘里找)，查询慢+更新代价小

15.缓存雪崩，缓存击穿和缓存穿透

• 缓存穿透：用户每次查的数据都不在缓存里面，都得去底层数据库查，导致缓存机制形同虚设
• 缓存雪崩：同一时间大量的缓存数据过期，导致该时间的请求底层全打到数据库上
• 缓存击穿：缓存里的某个key一直扛着大并发请求，这个key一旦过期，就会出现缓存击穿

16.mysql的最左匹配

• 例子，t1,t2,t3建立了一个联合索引，那么实际上是建立了(t1,t2)、(t1,t2,t3)这两个索引
• MySQL8.0之前一定是遵循最左前缀匹配的，即WHERE条件有t1==xx或者t1==xx and t2==xx时才能用到这个索引来加速检索
• MySQL8.0之后出现了索引跳跃扫描技术，假如只查了t2==xx and t3==xx也能去用到联合索引，因为实际上底层会去执行

  1 2 3 4

  xxx WHERE t1 == 1 and t2 == xx and t3 == xx; xxx WHERE t1 == 2 and t2 == xx and t3 == xx; ..... 直到扫描完t1字段所有的唯一值，最后将结果合并返回

17.redis是k-v结构，怎么实现复杂查询

• 一般可以使用set的交并集来实现多表联查需求，但是这样其实就抛弃了redis的优势，一般还是不建议在redis里面进行复杂查询，应该存放直接能使用的值

18.mysql的主从复制
主从复制的基本原理：slave会从master读取binlog来进行数据同步

• master将改变记录到二进制日志binlog，这些记录过程叫做二进制日志事件binlog events
• slave将master的binlog events拷贝到中继日志relay log
• slave重做中继日志中的事件，将改变应用到自己的数据库中。MySQL的复制是异步且串行化的

19.Redis实现数据持久化的方法

• RDB：把当前的数据生成快照，保存到硬盘里，有手动触发和自动触发两种
• AOF：用日志记录每次执行的写命令，重启时重新执行一遍AOF里的记录

20.数据库慢查询的原因

• 没有用到索引
• 内存不足
• 查询的数据量过大

21.解决慢查询用explain检查sql是否有问题，关注以下字段

• type：用来表示该sql底层是怎么扫描的，
  • all全表扫描
  • index全索引扫描
  • null表示不用去表里查可以直接得到结果
• possible_keys：可能用到的索引列
• key：实际用到的索引列
• Extra：底层用的是哪种检索方式
  • Using where用where来处理结果
  • Using index condition表示用索引

22.乐观锁和悲观锁

• 乐观锁：默认不发生并发冲突，只在提交时检查版本号
  • 有可能会出现两个事务读同一行后再写入的未知结果
• 悲观锁：默认发送并发冲突，需要关闭mysql的自动提交，并在事务中用select…for update用排他锁锁住数据，其他事务需要在该事务提交后才能去写这条数据
  • 效率比较低
• 并发冲突少时选择乐观锁，并发冲突多时选择悲观锁
  • 因为乐观锁出现冲突只能往上抛出，然后重试，而悲观锁可以避免冲突的发生

23.mysql如何管理脏页

• 用buffer pool来做缓存加速
• 更新数据的时候会把buffer pool里面的页更新，然后把该页标记为脏页
• 后台线程再将脏页写入到磁盘里面
  • 用一个flush链表来存所有脏页，后台线程遍历这个链表就可以把脏页写入磁盘了
  • 触发：redo log或者buffer pool满了，数据库空闲或者关闭
  • 数据库性能波动，可能就是后台正在写脏页导致的

24.MySQL是如何处理全局搜索导致的LRU污染

• 新增一个old区域
• 当某页第一次被访问时，直接放入old区域
• 后续访问的时间 - 第一次访问时间 > 一定时间，才能将该页放入LRU的热点young区域
  • 原理是：每次从页中取一条记录，即认为访问了一次该页。所以在全表扫描时，InnoDb会认为对该页短时间进行了多次访问
• 并且新增了，只有young区域后1/4的页被访问才将其移到首部

25.一级索引和二级索引

• 一级索引：叶子节点存的是数据，主键索引都是一级索引
• 二级索引：叶子节点存的是主键，找到叶子节点后再用主键去访问对应数据

26.怎么加索引，什么时候要去加索引

• alter table 表名 add 索引类型 列名
• alter table 表名 drop xx

27.为什么myisam查询比innodb快

• innodb寻址要映射到块，再到行，myisam记录的直接是文件的myisam，定位比innodb要快
• innodb需要维护MVCC一致，需要额外开销
• innodb要缓存数据块，所以其中还有块在缓存中换进换出的开销

28.Hive是怎么实现大数据查询的，mysql为什么不行

• Hive用MapReduce去分布式查询
• Hive是将结构化的文件映射成一张表，这个文件是在HDFS上的

数据结构与算法

1.哈希表的负载因子

• 负载因子=已保存节点空间/哈希表空间，一般设为0.75

2.set和array的区别

• 唯一性。set的底层是红黑树，但是保证唯一性用的是哈希表
  • 保证唯一性的底层实现是，先判断key得到的hashcode有一样的么，如果有，那么再调equals()去检查

3.如果发生哈希冲突应该怎么处理，哈希表的时间复杂度是多少
- 链表法，插入、查询、判断key值开销：unordered_map是O(1)，map是O(logn)

4.二叉树插入元素的时间复杂度

• O(logn)，插入其实开销就和查找一样

5.动态数组删除元素的时间复杂度

• O(n)，因为无论是开辟新数组还是移动其他成员的位置，复杂度都是n

6.unordered和普通的数据结构有什么区别，比如unordered_map和map

• 底层：unordered_map底层是hash_map，map底层是红黑树
  • hash_map是由vector和链表构成，每个vector的位置连一个链表，声明的时候就会自动初始化一个vector去占用空间(质数，不同编译器用不同的质数比如53)
• 顺序：unordered_map是插入顺序，map是按key从小到大排列的
• 插入、查询、判断key值开销：unordered_map是O(1)，map是O(logn)

7.红黑树的特性

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色
• 每个叶子节点是黑色(注意：红黑树叶子节点是NULL)
• 不能出现连续的黑色节点
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

8.红黑树与AVL树比较，都是BST(二叉搜索树)

• AVL是严格的平衡二叉搜索树，执行插入或删除，往往需要开销较大的旋转来保持平衡，但是高度较低
• 红黑树是一种弱平衡二叉搜索树，只需确保没有一条路径比其他路径长两倍即可，所以旋转次数少，但是高度较高
• 查询较多的情况用AVL树，
• 插入和删除场景较多的情况用红黑树，map和set

9.vector与list比较

• vector底层是数组，list底层是双向链表
• vector支持下标访问，list不支持
• vector是顺序内存，list不是
• vector扩容才会申请内存，list每次插入都需要申请内存

10.dijkstra和spfa区别

• dijkstra用堆，spfa用优先队列
• dijkstra不能处理负权值，spfa可以处理
• spfa的最坏复杂度和dijkstra相同，但是spfa可能会被卡

11.deque

• 底层由多段等长的连续空间组成
• 用一个数组map存放指向这些连续空间地址的指针
  • 和unordered_map底层类似，一个存指针指内存空间，一个存链表

12.希尔排序就是插入排序的改进版，也是不稳定的

• 先划分子序列，注意这里划分的子序列是交错的
  • 按增量的方式进行子序列划分，将整个序列中下标值相差固定值的所有元素划分到同一个子序列中。比如，整个序列有9个元素，而增量为3，那么第0、3、6个元素属于第一个子序列，第1、4、7个元素属于第二个子序列，第2、5、8个元素属于最后一个子序列
• 然后对每个子序列进行插入排序
• 然后再按一个新的较小的增量进行划分，再重复以上步骤
• 最后得到完整的排序

13.sort底层是快排

• 元素少的话会去用插入排序
• 用快排是因为快排在比较随机的分布上，表现较好

C++

1.C++的多态

• 多态就是一个接口，多种实现方法，即动态绑定
• 通过虚函数实现

2.什么是虚函数，原理是什么，怎么样使用虚函数

• 类中存有一个虚函数表，实例化的对象拥有一个虚函数指针用来指向虚函数表中的某个位置
• 虚函数在运行时通过虚函数表确定，是动态的；内联函数在编译时候进行代码嵌入，是静态的，所以如果把虚函数声明为内联，编译器仍然会当做普通虚函数处理
• 虚函数的缺点是：一是虚函数表和虚函数指针会增大开销，二是在一个CPUcache里面，有了虚函数以后，编译器不会做一些很强大的优化
• 对于继承自父类的子类，应该将父类析构函数设为虚函数

3.const关键字的作用和一般使用情景

• 定义不会改变的常量，使编译器保护这些常量，防止代码无意的修改

4.static关键字的作用和一般使用情景

• 类里的static函数，里面就只能调用static成员
• static成员在类未进行第一次实例化时就已经占据了空间

5.了解构造函数和析构函数吗？它们俩可以是虚函数吗

• 构造函数不能是虚函数，析构函数可以是虚函数
• 一般析构函数设为虚函数是便于子类重载，避免使用父类指针指向子类对象时，去调用了父类的析构函数导致部分子类成员没能释放，造成内存泄漏

6.incline函数和宏的区别是什么

• incline在编译时展开，宏在预编译时展开；
• incline内联函数有类型检测、语法判断等功能，而宏没有，因为宏只是做简单的文本替换，这也导致要注意括号问题

7.说一下你了解的vector和map实现方式和功能

• vector，动态数组，有扩容机制
• unordered_map的底层是用vector+链表实现的

8.字节对齐

• 原理：
  • 因为尽管内存是以字节为单位，但是大部分处理器并不是按字节块来存取内存的。它一般会以2字节,4字节,8字节,16字节甚至32字节为单位来存取内存，我们将上述这些存取单位称为内存存取粒度
  • 假如没有内存对齐机制，数据可以任意存放，现在一个int变量存放在从地址1开始的联系四个字节地址中，该处理器去取数据时，要先从0地址开始读取第一个4字节块,剔除不想要的字节（0地址）,然后从地址4开始读取下一个4字节块,同样剔除不要的数据（5，6，7地址）,最后留下的两块数据合并放入寄存器.这需要做很多工作
  • 有了内存对齐的，int类型数据只能存放在按照对齐规则的内存中，比如说0地址开始的内存。那么现在该处理器在取数据时一次性就能将数据读出来了，而且不需要做额外的操作，提高了效率。
• 对齐的准则：
  • 结构体变量的首地址能够被其对齐字节数大小所整除
  • 结构体每个成员相对结构体首地址的偏移都是成员大小的整数倍，如不满足，对前一个成员填充字节以满足
  • 结构体的总大小为结构体对齐字节数大小的整数倍，如不满足，最后填充字节以满足

9.单例模式

• 饿汉单例模式：系统启动的时候就利用static机制实例化了类

  1 2 3 4 5 6

  Class A{ static A single; static A* getClass(){ return &single; } };

• 懒汉单例模式：真正用到这个类时才去实例化

  1 2 3 4 5 6 7

  Class A{ static A* single; static A* getClass(){ if(single == nullptr) single = new A(); return single; } };

10.i++其实分3步执行

• 读取i的值，增加i的值，回写i的新值
• 这3步每一步都是原子操作，但是组合在一起就不一定是原子操作了，所以i++线程不安全，++i线程安全
• ++i比i++效率高得原因是，前者只用返回i+1的结果，而后者既要先保存i的结果还要保存i+1的结果

11.static关键字的作用

• 静态函数(在函数返回类型前加static)：作用域为声明语句所在的整个文件
• 全局静态变量(在全局变量前加static)：作用域为声明语句所在的整个文件
• 局部静态变量(在局部变量前加static)：作用域仍为局部
• 总结：
  • 类的静态成员和静态函数：这个类的所有对象都共用一个，注意静态函数只能引用类中的静态成员
  • static与extern相反，static意味着该变量、函数在被声明的文件之外是不可见的，除非引入声明的文件作为头文件，但是这样的话会每一个引入该头文件的文件都会定义一个自己的变量造成内存浪费，所以一般用extern在头文件中声明才是正确的方式
  • 静态变量都放在内存的静态存储区内，在程序运行期间一直存在不会释放，所有在函数内定义的局部静态变量，会在第一次运行到该语句时就创建，第二次运行到该定义语句会自动跳过，直到程序终止才释放

12.堆和栈的区别

• 堆会产生内存碎片，栈不会
• 堆只能动态分配需要程序员手动分配和释放；栈由系统管理静态分配，也可以用alloca()动态分配，但都是由系统释放
• 堆内存地址由低到高；栈内存地址相反
• 堆为虚拟内存大小；栈默认为1M（linux下为10M）
• 堆的分配效率低；栈的分配效率高，因为由系统调用，会有硬件层面的支持

13.new与malloc区别

• new是C++用于内存分配的运算符，malloc是C用于内存分配的库函数
• new会自动计算要多少字节的内存，malloc需要用户指定字节数
• new会返回指定类型的指针，malloc返回的统一是void *，需要用户自己再转一次
• new用delete释放，malloc用free释放

14.#define和typedefine

• define在编译前预处理做字符串替换，typedefine在编译的时候才处理，相当于起别名

15.shared_ptr

• shared_ptr和局部变量一样，离开作用域时会自己销毁
• 每当一个shared_ptr被拷贝或当成值赋给其他变量时，内置计数器都会自动+1，当指向该对象的一个shared_ptr被销毁时，shared_ptr类的析构函数会对计数器-1，为0时就去销毁这个对象(调用这个对象的析构函数)来释放动态内存
• weak_ptr指针不能直接访问对象的方法，要先将其转化成shared_ptr指针再访问
  • weak_ptr:用于解决shared_ptr互相指向形成循环，内存一直无法释放导致泄漏，它不会增加对象的引用计数

16.指针和引用的区别

• 指针占4字节空间，引用只是一个别名不占空间
• 指针可初始化为nullptr，引用必须初始化为一个已存在对象
• 引用易引起内存泄漏，因为指向的对象可能在栈里被回收了

17.C++的编译过程分几个阶段

• 预编译->编译->汇编->链接->执行
• Linux下用C++编程的步骤
  • 用vim编写.cpp文件
  • 用g++编译得到.out文件
  • 用./xx.out执行

18.C++在linux下怎么断点调试

• 使用gdb，对某行打上断点
• 然后在生成二进制程序的时候, 加上 -g 选项

Golang

1.GMP模型中，如果本地队列已经没有g了，全局队列也为空会休息吗

• 不会，因为还会去隔壁的本地队列里面拿g

2.channel的底层，如何用它来实现并发，如果channel满了会怎么办

• 底层用hchan结构体实现，一个ringbuffer，一个发送队列，一个接受队列

3.Go语言的特点

• 直接编译成二进制，没有虚拟化损失
• 代码跨平台，但是编译出来的产物是不跨平台的
• runtime直接编译进可执行文件里

4.Go中的扇入、扇出

• 扇入：多个通道合并到一个通道，select关键字聚合多条通道分别服务
• 扇出：一个通道分散到多个通道，用go关键字起多个协程

Linux

1.Linux下查找文件用什么命令

• find “xx”表示在当前目录及其子目录查找xx

场景设计

1.秒杀系统最重要的是异步、削峰，通过拦截器、分布式架构和消息队列实现

2.缓存数据一致性如何保证

• 一般而言都是先更新数据库，再去缓存里删老数据
• 两种方案
  • 双写策略：修改完数据库后，马上再用set方法将新数据写入到缓存中
    • 缺点：写入数据库后，再写入到缓存中这一步可能会由于网络原因延迟，导致脏数据
      • 例如改了数据库a改成1然后再改成2，此时网络波动改成1的写缓存操作在改成2的写缓存操作之后才执行，这样就不一致了
    • 解决办法：设置过期时间，这样一段时间后到数据库里取更新缓存的数据仍然可以得到正确数据
  • 先写后删策略:修改完数据库后，马上把缓存中的数据去删掉
    • 缺点：删除因为网络波动延迟和删除操作失败仍然可能有脏数据
    • 解决办法：设置过期时间，MQ异步处理保证执行删除
  • 延迟双删策略：先删缓存，再写数据库，延迟n秒后再去删缓存
    • 缺点：这n秒里还是会有脏数据，因此仍然不是强一致性的
    • 解决办法：设置过期时间，MQ异步处理保证执行删除
• 根据系统设计的思想：
  • 放入缓存的数据本就不应是实时性的、一致性要求很高的，所以缓存数据的时候要加上过期时间保证每天拿到最新的即可。
  • 遇到实时性、一致性要求高的数据，就应该直接查数据库，即时速度慢一些

3.rabbitmq如何保证消息不丢失，如果发送了多次相同的消息要怎么处理

• 消息丢失有三种
  • 生产者发给mq途中丢失：开启confirm机制给每个消息分配一个id，生成者发送消息后mq收到返回ACK，没收到返回nack
  • mq因为断电等情况丢失：设置消息持久化和镜像集群
  • mq发给消费者途中丢失：开启AKC应答机制，即消费者收到后给mq回一个ACK
    • kafka的ack有以下三种策略：
    • ACK = 0 时 发送一次 不论下游是否接收
    • ACK = 1 时，等待下游接收成功即可
    • ACK = -1 时 ，需等待下游将消息同步给消息队列

4.如果让你设计一个应用层的协议你会考虑什么，怎么去识别包的长度，如果包里本身包含这个特殊字符怎么办
- 用socket封装实现，基于TCP去实现，考虑首部包含资源的位置、请求的方式、协议版本
- 1.首部加一个len字段 2.用特殊字符做分割，换一个少用的字符或者加转义符/

5.rabbitmq和kafka的优缺点

• kafka有ack机制可以保证消息的顺序处理
• rabbitmq有消息存活时间和延迟/预定消息
• rabbitmq消息一旦消费成功就会删除，反之处理失败则放回；但kafka会一直保留消息，根据超时时间来删除，可以反复消费消息
• kafka使用分区的结构，在横向扩展上更有优势

必背重点题

字典序的第K小数字

给一个整数n和一个k，求在字典序排序的小于n的数组中的第k个数字

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int findKthNumber(int n, int k) {
    int count = 1;
    int cur = 1;
    while(count < k){
        int tmpCount = getCount(cur, n);
    
        if(count + tmpCount > k){ 
            cur *= 10;
            count++;
        }else{
            cur++;
            count += tmpCount;
        }
    }
        
    return cur;
}

int getCount(int cur, int n){
    int res = 0;
    for(int a = cur, b = cur+1; a <= n; a*=10, b*=10){
        res += min(n+1, b) - a;
    }
    
    return res;
}

约瑟夫环问题

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3

1
2
3
4
5

vector<int> dp(n+1);
for (int i = 2; i <= n; i++) {
    dp[i] = (dp[i-1] + m) % i;
}
return dp[n];

二叉树的前序遍历(迭代)

• 迭代法(统一格式)：栈 + nullptr标识已访问节点
  • 前序遍历

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

    vector<int> ans; stack<TreeNode*> s; if(root) s.push(root); while(!s.empty()){ TreeNode* now = s.top(); s.pop(); if(now){ if(now->right) s.push(now->right); if(now->left) s.push(now->left); s.push(now); s.push(nullptr); }else{ now = s.top(); s.pop(); ans.push_back(now->val); } } return ans;

寻找排序数组旋转后的最小值

给一个排序数组经过若干步旋转后得到的数组，求用logn的时间复杂度找到最小值(即原先排序数组的头部成员)

解法：二分法变形

1
2
3
4
5
6
7
8
9
10
11
12
13

int left = 0, right = nums.size()-1;

while(left < right){
    int mid = left +(right - left) / 2;
    
    if(nums[mid] < nums[right]){
        right = mid;
    }else{
        left = mid + 1;
    }
}

return nums[right];

进阶：这个数组里面可能有重复数字

解法：在基础上多加一个nums[mid] == nums[right]的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int left = 0, right = nums.size()-1;

while(left < right){
    int mid = left +(right - left) / 2;
    
    if(nums[mid] < nums[right]){
        right = mid;
    }else if(nums[mid] < nums[right]){
        left = mid + 1;
    }else{
        right--;
    }
}

return nums[right];

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//快速排序从小到大
void quickSort(int left, int right, vector<int>& arr)
{
	if(left >= right) return;
	
    srand((int)time(0));
    int tmp = (rand() % (right - left + 1)) + left; 
    int temple = nums[tmp];
    nums[tmp] = nums[left];
    nums[left] = temple;

	int i, j, base, temp;
	i = left, j = right;
	base = arr[left]; 
	while (i < j){
		while (arr[j] >= base && i < j) j--;
		while (arr[i] <= base && i < j) i++; 
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);
	quickSort(i + 1, right, arr);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

vector<int> sortArray(vector<int>& nums) {
    vector<int> temple(nums.size());
    mergeSort(nums,temple,0,nums.size()-1);
    
    return nums;
}


void mergeSort(vector<int>& nums, vector<int>& temple, int left, int right){
    if(left >= right) return;
        
    int mid = (right - left) / 2 + left;
    mergeSort(nums, temple, left, mid);
    mergeSort(nums, temple, mid+1, right);
    merge(nums, temple, left, right); 
        
    return;
}

void merge(vector<int>& nums, vector<int>& temple, int left, int right){
    int mid = (right - left) / 2 + left;
        
    int i = left, j = mid+1, k = 0;
    while(i <= mid && j <= right){
        if(nums[i] < nums[j]) temple[k++] = nums[i++];
        else temple[k++] = nums[j++];
    }
        
    while(j <= right) temple[k++] = nums[j++];
        
    while(i <= mid) temple[k++] = nums[i++];
        
    for(int i = left; i <=right; i++) nums[i] = temple[i-left]; 
        
    return;
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

vector<int> main(vector<int> nums){
    heapSort(nums);
    
    return nums;
}

void heapSort(vector<int> &arr, int size){
    for(int i=size/2 - 1; i >= 0; i--){
        adjust(arr, size, i);
    }
 
    for(int i = size - 1; i >= 1; i--){
        swap(arr[0], arr[i]);
        adjust(arr, i, 0);
    }
}

void adjust(vector<int> &arr, int len, int index){
    int left = 2*index + 1;
    int right = 2*index + 2;
 
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;
 
    if(maxIdx != index){
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);
    }
}

至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
解法：对字符种类个数kind依次枚举+滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int longestSubstring(string s, int k) {
    int res = 0;
    for(int i = 1; i <= 26; i++){
        res = max(res, box(s, k, i));
    }
    return res;
}

int box(string s, int k, int kind){
    int left = 0, right = 0;
    unordered_map<char, int> memo;
    
    int maxLen = INT_MIN;
    int isValid = 0;
    while(right < s.size()){
        memo[s[right]]++;
        if(memo[s[right]] == k){
            isValid++;
        }
        right++;
        
        while(memo.size() > kind){
            memo[s[left]]--;
            if(memo[s[left]] == k-1) isValid--;
            if(memo[s[left]] == 0) memo.erase(s[left]);
            left++;
        }
        
        if(isValid == kind) maxLen = max(maxLen, right-left);
    }
    
    return maxLen;
}

分割数组的最大值

给一个数组和分割次数m，求分割m次后，最小的最大子数组之和，例如1,2,3,4分割两次得到123和4，最大子数组之和为6，该值在这个分割情况是最小的

解法：合法函数+二分查找

• 最大子数组之和，最小值为最大数字，最大值为原数组之和
• 亮点是：已知上下界，将其转换成二分查找的思想

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

  int splitArray(vector<int>& nums, int m) { int left = 0, right = 0; for(int i = 0; i < nums.size(); i++){ right += nums[i]; left = max(left, nums[i]); } int res = 0; while(left <= right){ int mid = left + (right - left) / 2; if(isValid(nums, m, mid)){ res = mid; right = mid - 1; }else{ left = mid + 1; } } return res; } bool isValid(vector<int>& nums, int m, int x){ int sum = 0; int count = 0; for(int i = 0; i < nums.size(); i++){ if(sum + nums[i] > x){ sum = nums[i]; count++; }else{ sum += nums[i]; } } if(sum != 0) count++; if(count > m) return false; return count; }

搜寻名人

有编号从0到n-1的人，其中有一个名人，所有人都认识名人，名人不认识任何人。只能用knows(i,j)来询问i是否认识j

解法：

• 先找出不认识任何人的人famous，利用所有人都认识名人这一点来迭代更新
• 检验这个人是否是名人

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  int famous = 0; for(int i = 1; i < n; i++){ if(knows(famous, i)){ famous = i; } } for(int i = 0; i < n; i++){ if(i == famous) continue; if(knows(famous, i) || !knows(i, famous)) return -1; } return famous;

最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。例如输入：s = “banana” 输出：”ana”

解法：二分查找+字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

string longestDupSubstring(string s) {
    int len = -1, index = -1;
    
    int left = 1, right = s.size();
    while(left <= right){
        int mid = (right-left) / 2 + left;
        
        int t = isValid(s, mid);
        if(t != -1){
            index = t;
            len = mid;
            left = mid + 1;
        }else right = mid - 1;
    }
    
    if(len == -1 || index == -1)  return "";
    return s.substr(index, len);
}
    
    int isValid(string& s, int m){
    int mode = pow(10, 9) + 7;
    int base1 = 131;
    unordered_map<int, bool> memo;
    
    vector<unsigned long long> hash1(s.size()+1);
    vector<unsigned long long> power1(s.size()+1);
        
    power1[0] = 1;
    for(int i = 1; i <= s.size(); i++){
        hash1[i] = hash1[i-1] * base1 + s[i-1]-'a';
        power1[i] = power1[i-1] * base1;
    }
    
    for(int i = 1; i + m -1 <= s.size(); i++){
        int j = i + m - 1;
        int code1 = hash1[j] - hash1[i-1]*power1[j-i+1];
        
        if(memo.count(code1) > 0){
            return i-1;
        }
        
        memo[code1] = true;
    }
    
    return -1;
}

1.修改nginx配置文件

• 获得nginx路径

  1

  nginx -t

• 进入到nginx文件夹中修改nginx.conf文件，加入以下内容

  1 2 3 4 5 6 7 8 9 10

  server{ listen 8090; server_name 39.105.120.230; location /buffer/ { alias /home/gowork/gopath/dy/buffer/; autoindex on; } }

• 此时就可以
  • 通过url:39.105.120.230:8090/buffer/xx.mp4
  • 来访问位于服务器/home/gowork/gopath/dy/buffer/xx.mp4文件
• 如果使用的云服务器记得打开安全组端口8090，并且重启实例

1
2

心得：
1.错误处理很关键，前期可以只打印日志，后面还需要写入数据库或者发邮件等等

Go重写Redis中间件

Runtime介绍

1.Go语言的优势

• 不像Java还有一个JVM层，和C++一样直接编译成二进制让机器执行
• 自带运行环境，无需处理GC问题
• 一次编码，多套环境使用
• 天生支持高性能并发

2.Runtime的概念

• 是go的一个官方库，也是go程序的运行环境，用来支撑go代码的正常运行，相当于Java的JVM
• 编译成二进制时，会自动把Runtime作为程序的一部分打包进去
• Runtime实际上也就是一堆google开发者写的代码，和用户程序同时运行的，也可以直接通过函数来调用

3.Runtime的功能

• 内存管理：自动为变量分配内存
• 垃圾回收：回收堆上的空间
• 超强的并发能力：协程的实现
• 有一定屏蔽系统调用的能力
• go、new、make、<-等其实都是去调用Runtime的函数

4.Go的编译

• 编译指令是go build

  1

  go build

• .a文件是compile编译过程中出现的机器码的中间文件，后续需要link成exe文件
• 编译过程
  • 词法、句法、语义分析
  • 生成平台无关的中间码SSA(类似汇编语言)

    1 2 3 4 5

    # 查看SSA可以依次执行下列命令 $env:GOSSAFUNC="main" export GOSSAFUNC=main go build # 加-n表示不实际编译，只打印出编译的过程

  • 生成二进制的机器码.a文件
  • 链接生成.exe文件

5.go程序运行

• 1.运行rt0文件。go程序的入口底层上是runtime库的rt0_xx.s汇编文件，而不是main.go
  • rt意思是runtime，0表示入口，rt0有多个文件不同的操作系统、芯片用不同的rt0文件
• 2.起g0协程。g0是调度协程的协程，即母协程，是第一个协程
  • 启动调度器
• 3.启动主协程，并放入调度器等待调。用来来运行main.go
  • 执行runtime包的init()方法
  • 启动GC垃圾收集器
  • 执行用户包依赖的init()方法
  • 执行用户的main()方法

6.细节

• argc存参数的数量，argv存参数的值，args泛指参数
• ide中双击shift只会查找有意义的变量和方法，即它会忽略汇编文件里的成员，要找的话要再选file选项去找

7.在struct中只声明类型没指定名字的变量，称为匿名字段，go会自动到里面去调用函数(因为没有成员名，算一种语法糖)

8.Go的接口其实就是抽象出来的一组方法，哪个struct里实现了里面的所有方法，就说这个struct实现了该接口

9.一些包管理的方法

• 在go.mod文件里用如下语句可以把对应的包换成本地存在的库

  1	replace github.com/Jeffail/tunny => xx/xx

• 执行以下命令可以把依赖的包都缓存到本地，以免go mod的时候去网上拉

  1 2 3

  go mod vendor //也可以 go build -mod vendor

• 自动向远程仓库推送生成go.mod文件

  1	go mod init github.com/xx/xx

Go的数据结构底层

10.go的数据结构

• 指针大小和int保持一致，32位系统4字节，64位系统8字节
• 独立的空结构体的大小是0，但是也是有一个地址的，所有的空结构体共有这个地址，该地址叫zerobase
  • 该设计用于节省内存，但是如果一个父结构体包含了空结构体，那么这个空结构体就不能算独立了，它的地址就要跟着它的兄弟结构体了，还有内存补齐等问题
  • set可以用map来声明，将val声明为空结构体

    1 2 3

    set1 := map[string]struct{}{} set1["aa"] = struct{}{} //正常写法应该是map[string]int{}，struct{}表示空结构体类型

11.string在底层是由一个unsafe.point指针(本质是byte数组)和一个int组成的结构体，分别指向字符串值地址和存字符串byte长度

• 注意len(str)的结果是字符串底层字节的长度！！例如“慕a”的len()就是4
• rune就是utf8字符的意思，底层是int32
• utf-8的文件在runtime/utf8.go里面

12.切片的底层slice由一个unsafe.point指针和两个int类型的len、cap组成，参考C++的vector

• 声明定义时[]写了具体数字的就是数组，没写的就是切片
• 只增加len就只由编译器负责，如果需要扩容增加cap就要去调runtime.growslice()
• 默认扩容是长度小于1024扩大到2倍，大于1024扩大到0.25倍，除非期望容量比要扩容的还大那就采用期望容量
• 切片的扩容是并发不安全的，扩容要记得加锁，因为扩容会把老数组丢掉

13.map的底层其实是HashMap实现的

• go的map是由链表法实现的，hmap底层又由bucket指针指向一个由bmap结构体组成的数组，每一个bmap放8个哈希值相同的数据
  • bmap
    • 有tophash存hash值的前8位
    • 有一个overflow指针指向可用的bmap，若超过8个的话就把多的数据根据这个指针传到另一个bmap去
    • 有key和value，最多只能存8个k-v对，注意这里存的不是值，也是key和value的地址
  • 将key值和hash0输入到hash函数里面会得到一个二进制的hash值，然后取后B位作为桶数，例如100010 B=3，则取010，即该key应该放在bucket2里
    • 然后再根据前8位的值作为tophash得到这个key具体在bucket2的哪个位置，tophash的设置就是为了快速定位的(因为是二进制表示节省开销，而用key去匹配可能是string等开销大的类型)
• 在runtime包里面
• 开放寻址法和链表法其实差不多，区别只在于开放寻址法的槽存值，而链表法的槽存指针(也叫桶法)
• 字面量赋值，少于25个之间编译成一个个赋值，多余25个会自动建key数组和val数组然后改写成for赋值
• 扩容是因为如果哈希值太多，溢出桶指向溢出桶指向溢出桶，这样性能就会大跌
  • 装载因子超过6.5会触发扩容，即每个桶里平均装了6.5个以上数据
  • 溢出桶数量大于普通桶数量也会触发扩容(这里的扩容有可能不增加桶数，只做整理，因为可能之前很多然后删了之后现在数据很少，会很稀疏地存在)
  • step1：建新的双倍普通桶，然后bucket指向新桶，oldbucktet指向旧桶，并且把该hmap标记为扩容
  • step2：渐进式转移数据，即每一次数据要写到旧桶时才把这个旧桶的数据转移到新桶里(因为根据B的增加只增加一个高位，所以根据高位是0还是1只分成两部分放入新桶)
  • step3：当所有旧桶里都迁移完了之后就释放旧桶占据的内存空间（所以会有并发问题）
• 并发里用map要用sync.Map，里面自动会给读、写加锁
  • 里面有两个map，一个read map，一个dirty map，他们的key都是一样的并且都指向同一组val地址
    • 正常的读、修改都走read这个map；发生追加的时候走dirty这个map，mutex锁会去锁dirty，同一时间只允许一个协程去操作dirty
      • 每次去read读读不到并且read的mended为true则要去dirty里面找，每发生一次misses+1，当misses==len(dirty)时触发把dirty上升为read，然后之前那个read删掉，新建一个老dirty的副本作为新dirty——当时并不新建，发生追加时才顺便新建
    • 删除则是把执行val的指针置为空，这样过段时间go就会自动回收空间
      • 如果是提升之前dirty里追加的就被删了，那么提升后新dirty就不会再建立这个key

Go的并发

14.常用并发

• 简单的并发

  1 2 3

  go func(){ fmt.print("123") }

• 简单的阻塞

  1

  select {}

• 简单的利用管道缓冲(以下表示最多同时运行3000个协程)

  1 2 3 4 5 6 7 8 9 10 11 12

  func main(){ c := make(chan struct{}, 3000) for...{ c <- struct{}{} go do(c) } } func do(ch chan struct{}){ time.sleep(time.Hour) <-ch }

• 简单的加锁：在结构体里新增一个mutex类型成员

  1 2 3 4 5 6 7 8 9 10

  type person struct{ mu sync.mutex name string } func(p *person) promote{ p.mu.Lock() ... p.mu.Unlock() }

• 另一种加锁方式：用原子操作，这种方法不实用，在并发大的时候已卡住，因为触发不了协程切换

  1 2 3 4 5 6 7 8 9 10

  type person struct{ mu int32 //0表示未锁，1表示已上锁 name string } func(p *person) promote{ atomic.CompareAndSwapInt32(&p.mu, 0, 1); ... atomic.CompareAndSwapInt32(&p.mu, 0, 1); }

15.interface{}的底层，一个实例化的接口有以下特性

• 接口的数据用runtime.iface表示
• iface记录了数据的地址
• iface也记录了底层是由什么类型实现的和实现的方法
  • 所以当接口有类型信息时，空接口就不会是nil了

16.nil不一定是空指针，可能是别的类型的0值。在底层文件builtin里面nil的类型时可变的

• 空接口不一定是nil，因为如果这个空接口有类型信息的话它就不会是nil
• 空结构体的指针是zerobase，跟nil没关系

17.以下语句可以获得对齐系数

1

unsafe.Alignof()

18.可以调整结构体的成员声明顺序，来节省空间，因为会有字节对齐

• 结构体的对齐系数是其最大成员对齐系数，和C++一样
• 空结构体在末尾时要补齐字节，比如前面字节已经对齐了，然后多了一个空结构体，那么也要补齐字长

19.go用协程而不是线程的原因

• 协程资源开销、切换开销更小，协程本质是一段包含了运行状态的程序
• 协程并发其实就是用同一个线程先执行协程a的一步计算，把状态保存到协程a，再去切换到协程b计算再保存，又切回协程a继续计算。这样的好处就是cpu一直在一个线程上跑，减少了cpu在线程之间切换带来的开销
• 协程底层是一个g结构体(g0是母协程)，g结构体里包含的gobuf成员的sp堆栈指针记录的是运行到哪个方法了，pc程序计数器记录的是运行到哪一行了
  • 描述线程的底层是m结构体，里面记录了母协程g0、当前协程curg和操作系统的信息mOS
• go执行协程会把这个协程要运行的方法依次压入栈中，并且初始化这个栈的时候先压入一个goexit()用于执行完成退出协程

20.go协程在线程中执行的循环过程(一个线程是一个循环)

• 首先，g0的stack上执行schedule()、execute()、gogo()等
• 然后，去对应协程的g的stack上执行业务方法
• 最后，在g的stack上运行到goexit()的时候又返回g0开始下一个执行协程的循环

21.GMP调度模型：用于协程的调度

• go以前是用一个有全局锁的协程队列实现多线程并发
  • 每个线程循环运行完后，就去队列里拿一个协程进行下一个循环
• G是协程，M是线程，P是送料体，每一个P服务一个M，P里面有：
  • 指向本地协程队列头尾的指针，当前协程的指针，下一个协程指针
  • 线程信息
• 某个P的本地队列用完之后，就会去全局锁队列里面获取一批新的协程作为本地队列
  • 如果全局的队列也用完，会出现任务窃取：从其他本地队列里偷
• 新建协程时，会随机寻找一个P放入本地队列，若本地队列满再放入全局队列，这是因为go认为新协程更需要先完成

21.协程的并发

• 如果顺序执行的话，会产生饥饿问题：大协程卡住了线程，后面的协程永远得不到执行
• 触发切换时，正在线程中循环的协程会被保存现场然后放回队列去
  • 四种触发方式：
    • gopark()，主动调用或者在方法内执行sleep等操作后go自动调用
    • 系统调用后去执行exitsyscall()，系统调用指的是，比如linux会去定期检查网络连接等
    • 抢占式调度，当被标记为抢占的协程触发了morestack()，就会触发切换
      • 当某个协程运行超过10ms时，系统会把它标记为抢占
    • 垃圾回收器定期让线程去调用doSigPreempt()，注册信号函数
• 每执行61次协程循环，就去全局队列里去拿一个协程进入本地队列

22.协程的方法a里再去调方法b时，编译器会自动在b()前面去先调用runtime.morestack()

• morestack()本质意为去检查协程方法栈里面是否有空间再放入一个b()

23.协程过多

• 带来问题：
  • 文件打开数限制
  • 内存限制
  • 调度开销过大限制
• 解决办法：
  • 优化业务逻辑
  • 利用channel缓存区：channel大小就是允许同时运行的协程数量
  • 协程池tunny：预创建一定数量协程，然后把任务送入协程池队列，协程池再不断取出可用协程来执行任务
    • 不太推荐，因为go的协程调度已经有池的思想了，再自己套一个池的逻辑会冗余、出问题难以查错
  • 增加系统资源

24.atomic包的原子锁是一种硬件层面的加锁，因为它是用底层汇编语言来实现的，会进行对某块内存加锁

• 只能用于简单变量的加减操作，不能对结构体、map这种复杂类型使用

25.sema锁是信号量锁，是mutex这些互斥锁、读写锁的底层实现

• 底层用平衡二叉树来存协程
• sema锁为几就表示有几个协程可以同时获取这个sema锁
  • 为0的时候，就会把要获取这个sema锁的协程放进平衡二叉树树里面去休眠
  • 有一种用法是，把sema设为0然后当成一个休眠队列把要休眠的放进去，要用时再对sema赋>0的值

26.mutex的state的最后一位0表示未被锁，1表示被锁

• 正常模式：默认模式
  • 当一个协程去获取mutex的锁时，若获取不到，则会自旋一段时间后再去获取，还获取不到就放到sema的休眠队列里去
  • 会有饥饿问题，即协程a等锁等了很久，终于锁释放了然后轮到唤醒它去拿锁，但是那一瞬间有新来的协程一起在竞争这个锁，那这样协程a可能永远也得不到执行
• 饥饿模式(先来后到)：当某个协程等锁等了1ms就会进入
  • 新来的协程不自旋，直接进sema休眠
  • 休眠队列里的协程被唤醒时，直接获得这把锁，不用再去和刚来的新队列竞争
  • 当sema队列被清空时，退出饥饿模式，返回正常模式
• mutex有3个sema，一个mutex的sema，一个readSema，一个writeSema

27.iota是以此类推的意思，下面一次多加1，是go的语法糖

• 另一个常用语法糖，在方法后.var可以快速新建变量来接受方法返回值

28.只读锁mutex.RLock()：锁上的时候不能再去写，但是还可以去读，即第一个读协程锁上，最后一个读协程释放

• 加读锁
  • 给readCount+1
    • 如果readCount > 0，表示加锁成功
    • 如果readCount < 0，表示有写锁，要被放入readerSema去等待
• 解读锁
  • 给readCount-1
    • 如果readCount > 0，表示解锁成功
    • 如果readCount < 0，表示有写协程在writerSema里等待，如果此时自己是readerWait里的最后一个读协程，那么还要去唤醒这个写协程

29.读写锁mutex.Lock()

• 加读写锁
  • 先加mutex的锁，如果已经有锁了就会阻塞等待
  • 将readCount前面加-号变为负值，阻塞读锁的获取
  • 如果有读协程还未释放，那么就进入writerSema
• 解写锁
  • 解开mutex的锁
  • 将readCount变为正值，允许读锁的获取
  • 释放在rederSema中等待的读协程

29.加锁的底层

• 加互斥锁就是去竞争mutex的state的最后一位，希望它由0变成1
• 读锁是共享锁，写锁是互斥锁

30.开go协程的时候一定要记得：主程序退出会把所有协程都终止！

31.sync.WaitGroup对象：用于实现一组协程要等待另一组协程

• Add(int)方法进行设置等待数
• Done()方法会结束一个等待
• Wait()方法只有在等待数为0时才不阻塞

32.让一段代码全局只执行一次的方法

• 调用sync包的once，底层也是用mutex互斥锁来实现的

  1 2 3 4 5

  o := sync.Once{} go o.Do(xx.xx()) go o.Do(xx.xx()) ...... //这样无论起多少个协程，xx.xx()全局只被执行一次

33.并发问题的检查工具

• 锁千万不要去拷贝，因为会连锁状态、sema休眠队列等也一起拷贝的，会有死锁等很多问题
  • 拷贝结构体的时候要注意里面有没有锁mutex的情况
• vet检查：用于检测xx.go文件里的锁拷贝等问题，例如拷贝了某个有锁的结构体

  1	go vet xx.go

• race检查：用于检查出文件里的数据竞争问题，例如并发地加某个变量值而不上锁

  1 2	go build -race xx.go //然后运行xx.go

• go-deadlock库：用于检测死锁，实际是检测锁解开的时间来实现的
  • 用go-deadlock包的mutex来取代sync包

channel管道

34.管道的阻塞

• 以下代码会在第二行阻塞，因为channel没有缓冲区，塞不进去
  • 能运行的情况是有另一个协程阻塞着等着从a里面拿数据

    1 2 3

    a := make(channel int) a <- 1 <- a

• 使用管道比共享内存好的原因
  • 避免协程竞争和数据冲突问题
  • 减少开销，可以省去循环一遍遍查询，管道是一种信号机制，一旦有值就会通过
  • 更高级的抽象，代码逻辑清晰，更容易模块解耦
• 原则上：不要通过共享内存的方式来通信，而是要用通信的方式来共享内存

35.channel底层

• channel的底层结构体是hchan
  • 指针实现ring buffer，缓存是用环状结构来实现的
    • 环状可以降低垃圾回收GC开销，固定环的长度新增的数据直接放在下一个数据块即可，如果不用环状的话，新增要开辟空间，删除要回收空间
  • 接受队列Receive Queue，用于存放准备读这个channel里数据的协程(休眠等待)————此时ring buffer一定是空的
    • 从这个队列被唤醒时，数据已经被拷贝放到了这个协程里面
  • 发送队列Send Queue，用于存放准备把数据放到这个channel里的协程(休眠等待)————此时ring buffer一定是满的或者没有缓存区
  • mutex成员，任何对该channel的修改都要去获取mutex
    • 一般人说的“channel无锁”，指的是ring buffer里有位置，数据只有放进去的一瞬间要加锁，很短暂，所以说无锁

36.channel实践

• 实践中用select搭配channel更方便
  • 因为select可以用case来判断哪个channel里有数据或哪个channel可以塞数据，然后执行不同逻辑
• time库的timer对象里的成员C是一个channel，在这个timer对象计时结束后会自动往里面塞一个数据
  • 利用这个特性可以实现计时的并发逻辑

用netpoll管理socket(go的网络编程是基于epoll的)

37.socket

• TCP连接应该要有三次握手四次挥手的，socket是操作系统对这些操作的封装，我们只需操作socket即可实现TCP，不用去具体写什么时候握手什么时候挥手等
• socket的id叫文件描述符FD

38.Go封装的epoll

• 把linux/windows/mac的多路复用统一抽象成Network Poller
• 底层核心方法netpoll()用来查询发生了什么事件
  • 里面实际是调用epoll_wait()来具体查询的
  • 会返回一个关心这些事件的协程列表pollDesc(链表结构)
    • pollcache是带锁的链表头，不含具体信息，它后面跟的pollDesc才有数据
    • pollDesc是链表成员-也是runtime包对socket的详细描述
• 实际逻辑
  • 首先，runtime里的gcStart()会调用netpoll()，因为gc是周期性的所以可以理解为周期性地调用netpoll()查询，发现某Socket可读写的时候，给对应的rg或wg置为pdReady(1)，在g0协程上运行的
  • 然后，当协程运行的时候会去判断rg或wg是否就绪，如果就绪就往下走；如果不就绪就会把这个协程的地址写到rg或wg上，并把协程休眠，等rg或wg就绪的时候就会用这个地址去唤醒协程

39.net包是go原生的网络包，它实现了TCP、UDP、HTTP等网络操作，底层靠NetworkPoller实现

• net.Listen()会得到一个TCPListener对象(listen状态的socket)，底层如下
  • 新建一个Socket，并执行bind和listen
  • 新建一个FD，FD是net包对socket的描述，相当于runtime包的pollDesc
• TCPListener.Accept()得到TCPConn对象(establish状态的socket)
  • 直接调用accept，新生成一个socket来连接
  • 如果失败了就休眠等待
• TCPConn.Read()和TCPConn.Write()就可以对socket进行读写了

40.把byte数组转成字符串的方法

1
2

# b是[]byte类型
string(b[:])

41.怎样实现一个协程负责一个socket

• 死循环里每监听到一个新的连接，就新起一个协程去处理这个连接
• 即主协程监听listen，然后起新协程去处理连接
• 这种代码风格也叫goroutine-per-connection编程

Go的GC垃圾回收

42.Go的栈也是从堆上申请的，即不像C++等栈由程序释放，Go的栈依旧由GC释放

• 堆内存在操作系统的虚拟内存上
• 函数参数传递顺序和C++一样，从右往左传，因为栈是后进先出
• Go天然有一个runtime.main栈帧(一个协程有一个自己的协程栈，多个栈帧组成了一个协程栈)
  • 运行主函数时有一个main.main栈帧紧跟着runtime的栈帧
  • Go的main()调用一个函数，会在新起一个栈帧跟着main.main的后面(C++的递归太多导致栈溢出就是这个原理)

43.Go解决协程栈溢出的方法

• 逃逸分析：不是所有的变量都能放在协程栈上，用来减少栈空间不足
  • 指针逃逸：某方法返回了一个指向它局部变量的指针，按理来说这个局部变量应该要被回收，但是指针被传出去了，外面的其他方法可能会用到，所以就把这个局部变量放到堆上(C++的策略是直接回收)
    • 例如a()调用了b()，按理说b()的变量要全删，但是因为b()返回了一个指针给a()使用，那么这个指针指向的变量就不能删，会逃逸到堆上
  • 空接口逃逸(反射导致)：某方法用局部变量调用了另一个参数类型是空接口的方法，那么这个局部变量就会逃逸了，因为空接口的方法往往都会用到反射，而反射要求变量需要在堆上
  • 大变量逃逸：太大的变量会导致协程栈空间不足，一般64位的机器超过64kb的变量都直接放堆上
• 栈扩容：Go之前采用分段栈，原理类似链表；现在采用连续栈，原理类似vector，找一个2倍的空间然后迁移过去

43.Go的堆内存结构，类似tcmalloc-也是C++17推荐用的内存结构

• Go申请和释放虚拟内存的单位是64M(一个heapArena)，许多个64M组成了Go的用的所有内存(底层用mheap描述)
  • 在heapArena里面给对象分配内存策略
    • 分级分配，给heapArena里的空间分割成不同大小的箱子，每个箱子只能放一个对象，然后把每个对象放到能放下它的最小的箱子
      • 每一级箱子叫做一个mspan，即如果分成2级，就有两个mspan
      • go最多有68个mspan(0级-67级)，是根据对象的内存需求再去分割的，最小8bit，最大32kb
    • 不用线性和链表分配，是因为易出现内存碎片
• 用mcentral来做mspan的索引，而每个mspan里面有两个mcentral，分别记录需要GC扫描的内存和不需要GC扫描的内存，里面有互斥锁
• 每个线程P有一个本地的内存mcache做缓存用，里面每个级别的mspan分别有2个(scan和noscan)，每次线程要申请空间时不用去中央要，先从自己本地去要，这种结构类似协程调度的GMP模型
• 即整体结构，heapArena里用mcentral来指向mspan，采用分级分配，线程本地的mspan缓存叫做mcache

44.堆内存的分配

• 微对象tiny(0,16b)，不包含指针。把多个微对象合并成一个16 bite分配到2级mspan，优先使用本地的mcache
• 小对象small[16b,32kb]。分配到对应等级的mspan，优先使用本地的mcache
• 大对象large(32kb, 无穷大)。分配到量身定制的0级mspan，即0级mspan没有固定大小，它是根据大对象来改的，只能从中央要

45.GC垃圾回收

• “标记-清除”：把需要的内存标记，然后清除，易内存碎片，go采用，因为go用了分级分配，不会有内存碎片问题
  • 标记的对象(GC Root)
    • 被栈上的指针引用
    • 被全局变量指针引用
    • 被寄存器中的指针引用(即os正在操作处理时用的指针)
  • 每次标记的时候会对每个Root Set对象进行bfs，因为如果某个对象是Root Set的话，那么它里面引用的对象也不能清除
  • GC的策略
    • 串行GC：停下其他协程，然后GC，开销大影响业务
• “标记-整理”：把需要的内存标记，然后把还在用的内存往前移，开销大，老java用
• “标记-复制”：把需要的内存标记，然后只把标记的部分复制到另一个空间，新java用

46.三色标记法-go采用的并发的垃圾回收，并发指的是程序一边运行业务一边进行GC(说是并发，但是其实关键操作的瞬间还是会暂停程序，只不过时间及其短)

• 含义
  • 黑色：有用，并且已经分析扫描过了
  • 灰色：有用，还未分析扫描
  • 白色：无用或者还没分析到，最后需要清除的对象
• GC过程
  • 首先，所有的节点都置为白色
  • 接着，把所有Root Set节点置为灰色
  • 然后，把Root Set引用的所有节点置为灰色
  • 如此循环往复，当灰色队列里面为空时表示扫描完成，开始清除
• 解决GC对新引用节点标记错误的问题：解决思路都是，保险起见把有改变的节点都置灰
  • 删除屏障(也叫快照标记)：把释放的指针指向的对象置灰色
  • 插入屏障：把新增的指针指向的对象置灰色
  • go采用的是混合屏障，即删除屏障+插入屏障
• 触发GC方式
  • sysmon定时检查超过2分钟没GC，自动触发
  • 分配的堆大小达到阈值，自动触发
  • 如果检测GC机制没有启动，启动GC并触发一次
  • 代码里用runtime.GC方法强制触发(不推荐)

47.写代码过程中优化GC的方式

• 减少堆上垃圾
  • 减少逃逸：因为逃逸会使栈上的对象跑到堆上，不能靠栈来回收，而变成堆上的垃圾等GC来回收，例如fmt这种常会用到反射的包
  • 常用空结构体：因为所有空结构体指向同一个地址，不占用堆空间
• GC分析工具

  1 2	$env:GODEBUG="gctrace=1" gun run main.go

Go的cgo、defer、recover、反射

48.在Go里面调用C写的代码

• 在package下面，import上面用注释的形式写C的代码

  1 2 3

  /* int sum(int a){return a;} */

• 使用，先导入包C，然后用C.sum()来使用

  1 2	import "C" fmt.Println(C.sum(1))

• 注意执行c程序的时候，不一定快，因为有以下开销
  • 调度器就会暂停不再调度，直到执行完这个c程序
  • 从go的协程栈切换到系统栈上方便c执行

49.defer

• 碰到defer的时候会把地址记录，然后函数返回的时候调deferreturn()去执行这个地址
  • 一般记录在栈上，如果defer里面有recover就放到堆上
• 另一种是defer的语句在编译的时候就确定了，那么编译器会直接把defer的内容加在函数末尾，也叫开放编码

50.print和fmt.print区别

• print和println输出到标准错误流中并打印，官方不建议写程序时候用它，后期不保证是否会继续保留
• fmt.Print，fmt，Println属于官方包fmt中自带的打印方法，属于标准输出流，一般使用它来进行屏幕输出.

51.recover用于从panic中恢复

• panic一旦触发会直接终止当前协程，并向调用堆栈的上层函数传播，直到被最外层的recover捕获或者程序结束
  • 如果在协程里panic的话，会触发当前协程的defer，但不会触发主协程main的defer
• 在当前协程的defer里面写recover()，可以让当前协程因为panic退出时不带崩其他协程

  1 2 3 4

  defer func(){ recover() }() panic("")

52.反射reflect，底层还是把变量的值和类型转换成一个eface结构体表示

• 获取变量的值和类型

  1 2	ty := reflect.TypeOf(s) val := reflect.ValueOf(s)

• 把变量的值还原成变量

  1 2	str := val.Interface().(string) //意为先转成空结构体，再转成字符串

• 处理函数，用于框架和用户方法解耦，由框架来调用，用户来实现

  1 2 3 4 5 6 7 8 9 10 11

  func CallAdd(f func(a int, b int) int){ val := reflect.ValueOf(f) if val.Kind() != reflect.Func { return; } argv := make([]reflect.Value, 2) argv[0] = reflect.Value(1) //表示把第一个参数a存到argv[0]里 argv[1] = reflect.Value(2) val.Call(argv) //这一步就会用argv作为参数去调用上面传进来的f()方法 }

myRedis开发

1.RESP是Redis的数据序列化协议，即client和server之间如何交流的协议，其定义了5种数据格式

• 正常回复：以”+”开头，以”\r\n”结尾，例如+OK\r\n
• 错误回复：以”-“开头，以”\r\n”结尾，例如-Error message\r\n
• 整数：以”:”开头，以”\r\n”结尾，例如:123456\r\n
• 多行字符串：以”$”开头后跟字符数量，数据由”\r\n”隔断，例如:$6\r\n123456\r\n
• 数组：以”*“开头后跟成员数量，每个成员由”\r\n”隔断，例如:*2\r\n$4\r\nstr1\r\n$4\r\nstr2\r\n

2.myRedis的解析异步化

• 对外公布的Parser()方法会返回一个<-ch *PayLoad，因为方法里面用协程去调用了执行解析的实际方法，当解析完成时，会吐到这个channel里面

  1 2 3 4 5

  func ParseStream(reader io.Reader) <-chan *Payload{ ch := make(chan *Payload, 0) go parse0(reader, ch) return ch }

3.k-v和dict的实现

• k-v的val用interface{}，是因为可以适应各种数据类型的值
• dict里面的方法:get、put、len等等的实现，其实就是底层对sync.map的业务调用，而因为这样封装了一层，以后改用不是sync.map的数据结构实现也方便

4.数据命令解析过程

• 主线程监听端口，用handle去处理
• parse0里面根据传的命令第一个字符是’*’还是’$’分别调不用的函数进行处理，当前读取的状态用state结构体记录
• 解析得到args数组后吐到channel里
• handle接受了这个channel里面的数据args数组后，去调数据库内核的Exce方法
  • echo_database这个数据库内核的Exce()实现的是，传什么进来就返回什么回去，所以会把解析好的数据再重新包装

5.核心链路

• tcp包里监听接口的数据，然后拿去给resp协议层handle()处理
• handle()去调parseStream解析命令
• parseStream将翻译后的命令转给内核database去处理
  • 这里是异步执行，通过go parse0异步往channel里写数据，然后主程序去获取这个channel的产出往下执行
• 每个内核database里面有一个*DB列表
• 每个db里面有一个它的序号和一个dict
• 每个dict底层用sync.map实现了Get()、PUT()等一系列方法

6.aof落盘逻辑

• database内核在初始化时，也会初始化aof，先根据aof文件恢复之前状态
  • 恢复依然是走的parseStram()方法
• 初始化有buffer的管道，然后起一个协程去异步从管道里拿操作命令写aof文件(落盘)
  • 每次出现set、rename这种写命令时，就调一次addAof()把命令塞入管道

7.碰到的问题

• aof落盘的时候，明明应该是db0，但是落盘成db15
  • 原因：
    • 初始化database内核时，用匿名函数赋予里面的成员db的addAof()方法出现闭包问题
    • 因为闭包去调addAof()的方法会使用到局部变量db.index，所以这个局部变量db会逃逸到堆上，然后每次for遍历的时候都会去更新这个堆上的db值
    • 最后实际堆上是遍历的最后一个db成员
  • 解决办法：
    • for循环里新定义一个临时变量来放db
  • 原理：
    • for循环头部的变量每次循环中在内存上的地址其实是一样的，只是每次的值不一样(所以有时候这个地址逃逸到堆上就会产生闭包问题)
    • 而for循环内部定义的变量每次循环都会是一个新的内存地址，单次循环结束后就销毁

8.集群化

• 采用一致性哈希，好处是：增加一个新节点只用迁移部分数据
• 每个节点运行有一个database内核和一个连接池

    - 连接池是自己作为客户端与其他节点的连接(客户端用的是github上的开源库)
  

• 对于数据不存在自己本地上的命令，会把本机当做一个redis客户端去访问别的节点

Go秒杀系统

1.系统架构设计

• 需求
  • 前端页面承载大流量
  • 在并发量大的情况下解决超卖问题
  • 后端接口要满足可横向扩展
• 解决方案
  • CDN->阿里提供的流量负载器->流量拦截系统->Go服务器集群->消息队列->DB数据库

2.RabbitMQ

• 定义：面向消息的中间件，用于组件之间的解耦，主要体现在消息的发送者和消费者之间无强依赖关系
• 使用场景：流量削峰，异步处理，应用解耦等
• RabbitMQ安装命令
  • 安装erlang，因为RabbitMQ是用erlang编写的

    1 2 3

    sudo apt install erlang wget http://www.rabbitmq.com/releases/erlang/erlang-19.0.4-1.el7.centos.x86_64.rpm

  • 检测erlang是否安装成功

    1

    erl

  • 安装RabbitMQ

    1	sudo apt install rabbitmq-server

  • 检测RabbitMQ是否安装成功

    1	rabbitmqctl status

  • 启动RabbitMQ

    1	systemctl start rabbitmq-server

  • 启动RabbitMQ的插件，要用web控制台必须启动这个

    1	rabbitmq-plugins enable rabbitmq_management

  • 访问web控制页面

    1 2	本地部署直接访问127.0.0.1:15672(默认用账户guest密码guest访问) 远程部署先开放防火墙15672端口，然后再用公网ip:15672访问(需要新建一个用户)

  • 远程部署需要创建admin用户并赋权限

    1 2 3 4 5 6 7 8 9 10 11 12

    # 创建一个账户为admin，密码为admin的新用户 rabbitmqctl add_user admin admin # 给这个admin用户赋管理员权限 rabbitmqctl set_user_tags admin administrator # 给这个admin用户赋virtual host的所以配置、读、写权限 # virtual host权限是管理虚拟机的权限 rabbitmqctl set_permissions -p "/" admin ".*" ".*" ".*" # 查看当前存在的用户和他们对应的权限 rabbitmqctl list_users

• RabbitMQ使用命令
  • 启动RabbitMQ

    1	systemctl start rabbitmq-server

  • 停止RabbitMQ

    1	rabbitmqctl stop

  • 插件管理命令

    1 2 3 4 5 6 7 8

    # 表示查看插件列表 rabbitmq-plugins list # 表示启用rabbitmq_management rabbitmq-plugins enable rabbitmq_management # 表示卸载rabbitmq_management rabbitmq-plugins disable rabbitmq_management

• RabbitMQ核心概念
  • virtual host虚拟机
    • 每个账户需要绑定一个virtual host才能使用
    • 每个virtual host起的是一个数据隔离的作用
  • connection连接
    • 连接的进程
  • exchange交换机
    • 消息要经过交换机
    • 把消息经过对应的规则处理绑定到特定的key上
  • channel通道
    • 一个connection里面有多个channel
  • queue队列
    • 临时存储信息
  • binding绑定
    • 把队列绑定到交换机上
• RabbitMQ工作模式(重点)
  • Simple简单模式：生产者把消息放到队列里，消费者从队列里取出来消费
    • 一个生产者，一个队列，一个消费者
    • 只用queue来做区分，exchange和key都为空
  • Work工作模式：一个消息只能被一个消费者获取，即一个消息只能被消费一次
    • 一个生产者，一个队列，多个消费者
    • 适用于生产效率高于消费效率的情境，来提高系统运行速度
    • 用于起到负载均衡的作用
  • Publish/Subscribe订阅模式：一个消息可以被多个消费者获取
    • 一个生产者，一个交换机，多个队列，多个消费者
  • Routing路由模式：一个消息可以被多个消费者获取，并且可以通过key来指定哪个队列接受消息
    • 一个生产者，一个交换机，多个队列，多个消费者

go mod tidy -go=1.16 && go mod tidy -go=1.17

3.不同项目对比

• 趣约课、校友平台
  • 架构：用户->Web服务器->Mysql
  • 缺点：
    • Web服务器既要验证安全性，又要处理请求，负载大
    • 用户每发起一次请求就要去查一次数据库，数据库有压力
    • 高并发的情况下无法保证数据一致性
• 秒杀系统
  • 架构：用户->SLB负载均衡器->分布式安全验证->秒杀数量控制->Web服务器->RabbitMQ->Mysql

4.CDN流程

• 用户产生访问url的请求
• 请求打到DNS服务器
• CDN网络的智能DNS解析系统会把这个请求解析得到离用户最近的CDN节点并返回用户
• 用户再对这个CDN节点直接请求
• CDN节点
  • 如果本身有静态文件缓存的话会直接返回给用户(这一步就大大减少了对Web的请求流量)
  • 如果没有的话会对我们的Web站点发起一次请求获得静态文件，本次及下次就可以直接用了
• 前四步都由CDN的厂商做，我们做项目只关注Web站点这一步

5.cookie和token

• cookie存放在客户端，所以是不安全的，人为可以清除。
• cookie有过期时间设定。如果不设置过期时间，说明这个cookie就是当前浏览器的会话时间，浏览器关了，cookie就不存在了。如果有过期时间，cookie就会存储到硬盘上，浏览器关闭不影响cookie。下次打开浏览器，cookie还存在
• cookie有大小的限制，4KB。
• 最后，对于一个分布式的web系统，通用的解决方案就是cookie+token。由服务端生成token，将用户信息与token进行关联，token返回给浏览器，存储到cookie中。后续请求都携带cooke或者将token从cookie取出以参数传递(其实把token放在header里更好，还易于解决跨域问题)

6.一致性Hash算法

• 作用：用于分布式结构中，快速定位资源位置
• 实现过程：
  • 把存储空间看成一个Hash圆环，出发地址0，终点地址2^32-1，超过终点地址就又从0开始
  • 把服务器的ip地址或者服务器的名称作为关键字进行Hash，然后均匀地分布在Hash圆环上
    • 哈希算法是把string转换成byte[]数组，长度小于64的用0补满到64，然后用IEEE多项式返回crc-32校验和，也就是哈希值
  • 把数据也按hash算法放到圆环上，然后以这个数据的位置为起点，顺时针去找最近的一个服务器，这个服务器即是这个数据应该放的物理地址
  • 当请求的数据不存在本机时，以本机作为代理去向其它主机发起http请求
• 解决分布不均匀的办法
  • 虚拟节点：把每个服务器的值略作修改，生成多个虚拟节点，如果数据最终要放到这个虚拟节点上，那么直接把数据放到对应的服务器上，这样即使服务器数量过少或者服务器和数据分布不均也可以尽量均匀分布
• 不考虑hash冲突的原因
  • 数据hash冲突，无影响。因为数据只用去找最近的节点，就算算出来的哈希位置是一样的，说明这两个数据应该放到同一个服务器上，且本项目中的数据是userId，唯一标识基本不考虑冲突情况
  • 节点hash冲突，节点是ip+虚拟节点编号，这个重复的概率极低，发生重复那么说明的是网络出现了问题

7.为什么不用redis

• 如果用Redis的话要用redis cluster来提高性能，商品信息分散在各个cluster上
• 但是这样在对单件商品并发请求流量大的话，流量还是会集中到某一个redis cluster，这样的话其实性能还是会受限
• 而采用go语言写的数量控制接口可以解决以上问题

8.引入消息队列的作用

• 异步
• 解耦
• 削峰

9.为什么用这么多组件来控制流量

• 保障系统稳定的情况下，不浪费系统资源，即最大化系统利用
• 因为如果不控制的话，在某个点流量全堆到接口上，导致暴库、接口挂掉等线上故障，而如果设置一个休眠时间的话，又很难利用好系统资源，所以就有以上的流量控制，接口做完自己手上的事才发起请求要下一个事来

10.一共需要启动四个程序

• 拦截器(分布式在此实现)
• 数量控制接口
• 后端api接口
• 消费端接口

11.流量控制措施

• 同一用户抢购设置间隔
• 对异常频繁请求的用户建立黑名单
• 限流方法：
  • 漏桶算法
  • 令牌算法
• 秒杀前
  • 增加冗余机器来保证稳定
  • 预估访问量等级和峰值时间
• 秒杀中
  • 分批次秒杀

12.总结

• 开发系统流程
  • 需求分析
  • 原型设计
  • 系统设计
  • 编码
  • 后期迭代优化
• 秒杀难点
  • 消息队列RabbitMQ
  • Gin框架
  • 高并发分布式验证
  • token权限验证
  • 超卖问题(Redis会有瓶颈，采用go接口实现)
  • 横向扩展设计
• 一个请求按顺序走过的节点
  • 前端CDN
  • SLB
  • 分布式权限验证
  • SLB
  • 分布式数量控制接口
  • 后端web服务器
  • 消息队列RabbitMQ
  • 数据库Mysql

Go微服务和容器化

1.微服务是一种架构模式，里面的一个服务仅仅用于一个特定功能，可以单独拿出来用而不依赖其他架构模块

2.Docker搭建微服务

• 拉取微服务镜像

  1	sudo docker pull micro/micro

• 设置工作目录

  1 2	# user是模块名称，后面会换成git地址 sudo docker run --rm -v $(pwd):$(pwd) -w $(pwd) \ micro/micro new user

3.ProtoBuf，简称pb，后缀名是.proto

• 概念：本质上是一种序列化数据的协议，常用于存储数据和需要远程数据通信的情景，可以提高数据传输效率和解决数据格式不规范问题
  • 服务端与服务端之间只需要关注接口方法名（service）和参数（message）即可通信，而不需关注繁琐的链路协议和字段解析
• 数据类型：int32/64、float、double、string、bool、bytes
• 一个pb实例

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  syntax = "proto3"; package go.micro.service.product; service Product{ rpc AddProduct(ProductInfo) returns (ResponseProduct){} } message ProductInfo{ int64 id = 1; string product_name = 2; } message ResponseProduct{ int64 product_id = 1; }

4.命令行工具micro

• 安装

  1	docker pull micro/micro

5.go-micro的主要组件

• 注册Registry：提供服务发现机制
• 选择器Selector：实现负载均衡
• 传输Transport：服务之间通信

6.一个微服务架构

• 服务注册
  • client端通过Slector去服务注册中心发现服务
  • server端通过Registry去服务注册中心注册服务
• 客户端请求
  • client通过Broker发布消息到消息队列里面
  • server通过Broker从消息队列里面订阅消息
• 客户端和服务端的信息传输直接用Tranport

7.根据pb文件生成go代码

• 下载proto-compile，并且注册到环境变量里
• 安装go的支持插件

  1 2	go install google.golang.org/protobuf/cmd/protoc-gen-go@v1.28 go install google.golang.org/grpc/cmd/protoc-gen-go-grpc@v1.2

• 运行，根据.proto文件生成.go文件

  1	protoc --go_out=./test --go-grpc_out=./test test\test.proto

9.安装go-micro

1

go get go-micro.dev/v4

10.一个简单微服务

• 结构

  1 2 3 4 5 6 7

  rpc_demo - test //该文件夹里go文件是根据.proto文件自动生成的 - test.pb.go - test.proto - test_grpc.pb.go - server.go - client.go

• 客户端

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  func main(){ address := "127.0.0.1:5004" conn, err := grpc.Dial(address, grpc.WithInsecure(), grpc.WithBlock()) if err != nil { fmt.Println(err) return } defer conn.Close() client := test.NewTestClient(conn) message := "hello world" ctx, cancel := context.WithTimeout(context.Background(), time.Second) defer cancel() res, err := client.SayHello(ctx, &test.SayRequest{Message: message}) if err != nil { fmt.Println(err) return } fmt.Println(res.Answer) return }

• 服务端

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  type Server struct{ test.UnimplementedTestServer } func (s *Server) SayHello(ctx context.Context, req *test.SayRequest) (*test.ResponseSay, error){ fmt.Println(req.GetMessage()) return &test.ResponseSay{Answer: "你好世界"}, nil } func main(){ listen, err := net.Listen("tcp", "127.0.0.1:5004") if err != nil { fmt.Println(err) return } s := grpc.NewServer() test.RegisterTestServer(s, &Server{}) err = s.Serve(listen) if err != nil { fmt.Println(err) return } return }

11.用docker在git仓库上建模板

• 拉micro

  1	docker pull micro/micro

• ~~~
  sudo docker run –rm -v $(pwd):$(pwd) -w $(pwd) micro/micro new user
  ~~收益