Go 面试总结
经历了2个月的面试折磨,拿到offer总算结束了这段时间。主要是想记录面试中遇到的问题,列出来的问题不一定有答案,有答案也不一定是最佳答案,所以还是看问题为主,答案自行解决。
知识架构
数据库
MySQL
索引
- B+tree 索引
- 数据存储位置-在叶子节点 相邻节点是链表结构 这样可以实现 range 查询
- 联合索引 最左原则
- 索引不能是表达式的一部分 否则不走索引
- 为什么主键是递增的,随机会怎么样?
- 如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置,此时MySQL不得不为了将新记录插到合适位置而
移动数据
,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片
,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE
来重建表并优化填充页面。
- 如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置,此时MySQL不得不为了将新记录插到合适位置而
- 哈希索引 - 精准查询
- 聚簇索引和非聚簇索引
事务
事务的四种特性:
- 原子性:一个事务(transaction)中的所有操作,要么全部完成,要么全部不完成,不会结束在中间某个环节。事务在执行过程中发生错误,会被回滚(Rollback)到事务开始前的状态,就像这个事务从来没有执行过一样。
- 致性:在事务开始之前和事务结束以后,数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设规则,这包含资料的精确度、串联性以及后续数据库可以自发性地完成预定的工作。
- 隔离性:数据库允许多个并发事务同时对其数据进行读写和修改的能力,隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别,包括读未提交(Read uncommitted)、读提交(read committed)、可重复读(repeatable read)和串行化(Serializable)。
- 持久性:事务处理结束后,对数据的修改就是永久的,即便系统故障也不会丢失。
事务的隔离级别:
- 未提交读(Read Uncommitted):允许脏读,也就是可能读取到其他会话中未提交事务修改的数据
- 提交读(Read Committed):只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)
- 可重复读(Repeated Read):可重复读。在同一个事务内的查询都是事务开始时刻一致的,InnoDB默认级别。在SQL标准中,该隔离级别消除了不可重复读,但是还存在幻象读
- 串行读(Serializable):完全串行化的读,每次读都需要获得表级共享锁,读写相互都会阻塞
隔离级别 | 脏读(Dirty Read) | 不可重复读(NonRepeatable Read) | 幻读(Phantom Read) |
---|---|---|---|
未提交读(Read uncommitted) | 可能 | 可能 | 可能 |
已提交读(Read committed) | 不可能 | 可能 | 可能 |
可重复读(Repeatable read) | 不可能 | 不可能 | 可能(innodb 不存在) |
可串行化(Serializable ) | 不可能 | 不可能 | 不可能 |
分库分表
水平:
- 水平分表 – 表之间结构相同 表之间数据不相同 所有表的数据并集是总数据(单表数据量很大,影响sql性能)
- 水平分库 – 库之间表结构相同 库之间数据不相同 所有库数据的并集是总数据(并发量很高,cpu 网络扛不住,分库缓解压力)
垂直:
- 垂直分表 – 表之间结构不相同,数据根据某个字段关联,缓解io性能
- 垂直分库 – 库之前的表之间结构不相同,服务压力很高 可以考虑拆出去做单独服务了
方案:
方案一(水平扩容库) 采用双倍扩容策略,避免数据迁移。扩容前每个节点的数据,有一半要迁移至一个新增节点中,对应关系比较简单。 具体操作如下(假设已有 2 个节点 A/B,要双倍扩容至 A/A2/B/B2 这 4 个节点):
- 无需停止应用服务器;
- 新增两个数据库 A2/B2 作为从库,设置主从同步关系为:A=>A2、B=>B2,直至主从数据同步完毕(早期数据可手工同步);
- 调整分片规则并使之生效:
- 原 ID%2=0 => A 改为 ID%4=0 => A, ID%4=2 => A2;
- 原 ID%2=1 => B 改为 ID%4=1 => B, ID%4=3 => B2。
- 解除数据库实例的主从同步关系,并使之生效;
- 此时,四个节点的数据都已完整,只是有冗余(多存了和自己配对的节点的那部分数据),择机清除即可(过后随时进行,不影响业务)。
方案二(水平扩容表-双写)
- 第一步:(同步双写)修改应用配置和代码,加上双写,部署
- 第二步:(同步双写)将老库中的老数据复制到新库中
- 第三步:(同步双写)以老库为准校对新库中的老数据
- 第四步:(同步双写)修改应用配置和代码,去掉双写,部署;
Redis
数据结构
- String 简单动态字符串
- 编码方式不同会有什么影响
- Set 底层哈希表
- ZSet member存在哈希表中 score 存在跳表里 查询插入时间复杂 logn
- 为什么用跳表
- List 双向链表结构
- Hmap 哈希表
性能
- 数据均存在内存(引发出持久化问题)
- 高效的数据结构
- 单线程,省去线程间上下文切换的时间 以及不需要考虑锁
- 网络io 多路复用 可以让单个线程处理多个请求连接 减少网络io
- Redis采用自己实现的事件分离器,效率比较高,内部采用非阻塞的执行方式,吞吐能力比较大。
持久化
两种持久化:
- RDB持久化 即内存数据定时dump到磁盘上。
- fork 一个子进程 将数据写入一个临时文件 写入成功后 替换源文件。
- 快照的数据是截止fork命令执行的那一刻
- AOF 将Redis的操作日志以追加的方式写入文件。
- 将每一个写、删操作记录下来。默认配置时每秒同步一次。
RDB存在哪些优势呢?
1). 一旦采用该方式,那么你的整个Redis数据库将只包含一个文件,这对于文件备份而言是非常完美的。比如,你可能打算每个小时归档一次最近24小时的数据,同时还要每天归档一次最近30天的数据。通过这样的备份策略,一旦系统出现灾难性故障,我们可以非常容易的进行恢复。
2). 对于灾难恢复而言,RDB是非常不错的选择。因为我们可以非常轻松的将一个单独的文件压缩后再转移到其它存储介质上。
3). 性能最大化。对于Redis的服务进程而言,在开始持久化时,它唯一需要做的只是fork出子进程,之后再由子进程完成这些持久化的工作,这样就可以极大的避免服务进程执行IO操作了。
4). 相比于AOF机制,如果数据集很大,RDB的启动效率会更高。
RDB又存在哪些劣势呢?
1). 如果你想保证数据的高可用性,即最大限度的避免数据丢失,那么RDB将不是一个很好的选择。因为系统一旦在定时持久化之前出现宕机现象,此前没有来得及写入磁盘的数据都将丢失。
2). 由于RDB是通过fork子进程来协助完成数据持久化工作的,因此,如果当数据集较大时,可能会导致整个服务器停止服务几百毫秒,甚至是1秒钟。
AOF的优势有哪些呢?
1). 该机制可以带来更高的数据安全性,即数据持久性。Redis中提供了3中同步策略,即每秒同步、每修改同步和不同步。事实上,每秒同步也是异步完成的,其效率也是非常高的,所差的是一旦系统出现宕机现象,那么这一秒钟之内修改的数据将会丢失。而每修改同步,我们可以将其视为同步持久化,即每次发生的数据变化都会被立即记录到磁盘中。可以预见,这种方式在效率上是最低的。至于无同步,无需多言,我想大家都能正确的理解它。
2). 由于该机制对日志文件的写入操作采用的是append模式,因此在写入过程中即使出现宕机现象,也不会破坏日志文件中已经存在的内容。然而如果我们本次操作只是写入了一半数据就出现了系统崩溃问题,不用担心,在Redis下一次启动之前,我们可以通过redis-check-aof工具来帮助我们解决数据一致性的问题。
3). 如果日志过大,Redis可以自动启用rewrite机制。即Redis以append模式不断的将修改数据写入到老的磁盘文件中,同时Redis还会创建一个新的文件用于记录此期间有哪些修改命令被执行。因此在进行rewrite切换时可以更好的保证数据安全性。
4). AOF包含一个格式清晰、易于理解的日志文件用于记录所有的修改操作。事实上,我们也可以通过该文件完成数据的重建。
AOF的劣势有哪些呢?
1). 对于相同数量的数据集而言,AOF文件通常要大于RDB文件。RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快。
2). 根据同步策略的不同,AOF在运行效率上往往会慢于RDB。总之,每秒同步策略的效率是比较高的,同步禁用策略的效率和RDB一样高效。
二者选择的标准,就是看系统是愿意牺牲一些性能,换取更高的缓存一致性(aof),还是愿意写操作频繁的时候,不启用备份来换取更高的性能,待手动运行save的时候,再做备份(rdb)。rdb这个就更有些 eventually consistent的意思了。
内存模型
MongoDB
待补充
缓存
常见缓存策略
一致性哈希 解决某个缓存节点宕机的情况。
缓存穿透
描述:缓存穿透是指缓存和数据库中都没有的数据,而用户不断发起请求,如发起为id为“-1”的数据或id为特别大不存在的数据。这时的用户很可能是攻击者,攻击会导致数据库压力过大。
解决方案:
- 接口层增加校验,如用户鉴权校验,id做基础校验,id<=0的直接拦截。
- 从缓存取不到的数据,在数据库中也没有取到,这时也可以将key-value对写为key-null,缓存有效时间可以设置短点,如30秒(设置太长会导致正常情况也没法使用)。这样可以防止攻击用户反复用同一个id暴力攻击。
- 布隆过滤器:将所有可能存在的数据哈希到一个足够大的bitmap中,一个一定不存在的数据会被 这个bitmap拦截掉,从而避免了对底层存储系统的查询压力。
- 布隆过滤器原理:对key进行多个(n)hash算法 并将其值与 bitArray 长度m 进行取模 并对应的位置置位1,当一个新的key进行查询时 先查询其n个hash算法后的各个位置是否为1 如果都为1 则这个key可能存在 如果有任意一个位置不是1 则这个key 一定不存在。
缓存击穿
描述:缓存击穿是指缓存中没有但数据库中有的数据(一般是缓存时间到期),这时由于并发用户特别多,同时读缓存没读到数据,又同时去数据库去取数据,引起数据库压力瞬间增大,造成过大压力
解决方案:
- 热点数据不做过期
- 互斥锁。如果数据缓存不存在 则先进行上锁读数据写缓存释放锁
缓存雪崩
描述:缓存雪崩是指缓存中数据大批量到过期时间,而查询数据量巨大,引起数据库压力过大甚至down机。和缓存击穿不同的是,缓存击穿指并发查同一条数据,缓存雪崩是不同数据都过期了,很多数据都查不到从而查数据库。
解决方案:
- 过期时间加随机数
- 热点数据不过期
- 分布式缓存 将热点数据拆分到不同的实例
语言特性
GMP
概念
- G:代表一个goroutine对象,每次go调用的时候,都会创建一个G对象,它包括栈、指令指针以及对于调用goroutines很重要的其它信息,比如阻塞它的任何channel,其主要数据结构:
|
|
- M: 代表内核线程(Pthread),它本身就与一个内核线程进行绑定,goroutine 运行在M上。
|
|
- P:P(Processor)是一个抽象的概念,并不是真正的物理CPU。所以当P有任务时需要创建或者唤醒一个系统线程来执行它队列里的任务。所以P/M需要进行绑定,构成一个执行单元。 P决定了同时可以并发任务的数量,可通过GOMAXPROCS限制同时执行用户级任务的操作系统线程。可以通过runtime.GOMAXPROCS进行指定。在Go1.5之后GOMAXPROCS被默认设置可用的核数,而之前则默认为1。
|
|
调度过程
首先创建一个G对象,G对象保存到P本地队列或者是全局队列。P此时去唤醒一个M。P继续执行它的执行序。M寻找是否有空闲的P,如果有则将该G对象移动到它本身。接下来M执行一个调度循环(调用G对象->执行->清理线程→继续找新的Goroutine执行)。
M执行过程中,随时会发生上下文切换。当发生上线文切换时,需要对执行现场进行保护,以便下次被调度执行时进行现场恢复。Go调度器M的栈保存在G对象上,只需要将M所需要的寄存器(SP、PC等)保存到G对象上就可以实现现场保护。当这些寄存器数据被保护起来,就随时可以做上下文切换了,在中断之前把现场保存起来。如果此时G任务还没有执行完,M可以将任务重新丢到P的任务队列,等待下一次被调度执行。当再次被调度执行时,M通过访问G的vdsoSP、vdsoPC寄存器进行现场恢复(从上次中断位置继续执行)。
多个线程下如何调度
抛出一个问题:每个P里面的G执行时间是不可控的,如果多个P同时在执行,会不会出现有的P里面的G执行不完,有的P里面几乎没有G可执行呢?
这就要从M的自循环过程中如何获取G、归还G的行为说起了
有两种途径:1.借助全局队列 sched.runq 作为中介,本地P里的G太多的话就放全局里,G太少的话就从全局取。 2.全局列表里没有的话直接从P1里偷取(steal)。(更多M在执行的话,同样的原理,这里就只拿2个来举例)
调度循环中如何让出CPU
- 正常完成让出CPU
- 主动让出CPU
- time.Sleep(),IO阻塞等
- 抢占让出CPU
抢占式调度
概念:枚举所有的P 如果P在系统调用中(_Psyscall), 且经过了一次sysmon循环(20us~10ms), 则抢占这个P, 调用handoffp解除M和P之间的关联, 如果P在运行中(_Prunning), 且经过了一次sysmon循环并且G运行时间超过forcePreemptNS(10ms), 则抢占这个P
并设置g.preempt = true,g.stackguard0 = stackPreempt。
为什么设置了stackguard就可以实现抢占?
因为这个值用于检查当前栈空间是否足够, go函数的开头会比对这个值判断是否需要扩张栈。
newstack函数判断g.stackguard0等于stackPreempt, 就知道这是抢占触发的, 这时会再检查一遍是否要抢占。
抢占机制保证了不会有一个G长时间的运行导致其他G无法运行的情况发生。
主动让出CPU
time.Sleep()
timeSleep 函数里通过 addtimerLocked 把定时器加入到 timer 管理器(timer 通过最小堆的数据结构存放每个定时器,在这不做详细说明)后,再通过 goparkunlock 实现把当前G休眠,这里看到了上面提到的 gopark 方法进行调度循环的上下文切换。
在 addtimerLocked 方法的最下面有个逻辑在运行期间开启了’全局时间事件驱动器’timerproc,该方法会全程遍历最小堆,寻找最早进入 timer 管理器的定时器,然后唤醒。他是怎么找到要唤醒哪个G的?回头看下 timeSleep 方法里把当时正在执行的G以及唤醒方法 goroutineReady 带到了每个定时器里,而在 timerproc 则通过找到期的定时器执行f(arg, seq)
即通过 goroutineReady 方法唤醒。方法调用过程: goroutineReady() -> ready()
|
|
总结:time.Sleep 想要进入阻塞(休眠)状态,其实是通过 gopark 方法给自己标记个_Gwaiting 状态,然后把自己所占用的CPU线程资源给释放出来,继续执行调度任务,调度其它的G来运行。而唤醒是通过把G更改回_Grunnable 状态后,然后把G放入到P的待运行队列里等待执行。通过这点还可以看出休眠中的G其实并不占用 CPU 资源,最多是占用内存,是个很轻量级的阻塞。
Mutex
Mutex.Lock 方法通过调用 runtime_SemacquireMutex 最终还是调用 goparkunlock 实现把G进入到休眠状态。在进入休眠之前先把自己加入到队列里 root.queue(addr, s, lifo),在 queue 方法里,记录了当前的G,以便以后找到并唤醒。
Mutex. Unlock 方法通过调用 runtime_Semrelease 最终还是调用 goready 实现把G唤醒。
Channel
发送端:
当给一个 chan 发送消息的时候,实质触发的方法是 chansend。在该方法里不是先进入休眠状态。
1)如果此时有接收者接收这个 chan 的消息则直接把数据通过 send 方法扔给接收者,并唤醒接收者的G,然后当前G则继续执行。
2)如果没有接收者,就把数据 copy 到 chan 的临时内存里,且内存没有满就继续执行当前G。
3)如果没有接收者且 chan 满了,依然是通过 goparkunlock 方法进入休眠。在休眠前把当前的G相关信息存到队列(sendq)以便有接收者接收数据的时候唤醒当前G。
接收端:
chanrecv 方法是在 chan 接收者的地方调用的方法。
1)如果有发送者被休眠,则取出数据然后唤醒发送者,当前接收者的G拿到数据继续执行。
2)如果没有等待的发送者就看下有没有发送的数据还没被接收,有的话就直接取出数据然后返回,当前接收者的G拿到数据继续执行。(注意:这里取的数据不是正在等待的 sender 的数据,而是从 chan 的开头的内存取,如果是 sender 的数据则读出来的数据顺序就乱了)
3)如果即没有发送者,chan 里也没数据就通过 goparkunlock 进行休眠,在休眠之前把当前的G相关信息存到 recvq 里面,以便有数据时找到要唤醒的G。
QA
1.为什么p的local queue 可无锁访问 任务窃取的时候需要加锁嘛? 答:原子操作。
垃圾回收
- 三色标记
- 哪些情况下不被垃圾回收?
- 强三色和弱三色
- 写屏障
channel
slice
map
- 怎么解决读写并发(除了锁)
- sync.Map 了解一下
http库
interface
- iface
- 有方法的interface{}
- eface
- 没有方法的interface{}
其他
变量逃逸
项目经验
微服务
服务限流限速熔断
提现个人能力的点
- 引入 etcd,基于 etcd 开发服务间通信的基础库 解决服务间通信和服务选举问题
- 引入nsq 修改源码 支持延迟消息持久化,二次开发 SDK 支持连接池
- 开发项目基础架构,一键生成新项目
- 开发基础 lib 包,wechat 包 ,common 包, eventbus-lib ,htlog-go 提高开发效率
- 规范化项目开发+上线流程,规范化架构
- 开发统一的内部消息服务,规范内服飞书/企业微信消息的发送
- 后台服务单点登录功能
- 服务拆解 向微服务方向改进
- 敏感词 建立词库结构(B-tree)黑白名单的缓存
- 自我介绍:
- 部门内的定位:后端开发+基础服务搭建
- 关注新技术 表现出持续学习
- 岗位匹配度
系统设计
算法
堆
- 最小堆/最大堆
- topK 算法的实现: hash 加 小顶堆
- 堆排序
链表
- 单向链表/双向链表
- 链表找环(快慢指针)
- 链表局部/全部旋转(即修改方向)
问题:查找倒数第 K 个节点
二叉树
二叉树的五种遍历
- 前序 根-左-右
- 中序 左-根-右
- 后序 左-右-根
- 层次遍历 一层一层从左到右
- 锯齿遍历(s型遍历)每一层换方向
二叉树查找
- 查找最近路劲
- 查找共同祖先(最近祖先)
二叉树的转换
- 左右转换
其他
- 打印右视图左视图(即打印每一层的最右边或最左边)
回溯法递归法
理解回溯递归的每一层堆栈情况,学会什么情况下使用回溯/递归
动态规划(DP)
找路线数量,爬台阶,背包问题 数组等和分组问题
计算机基础
基础概念
问题:查看当前服务器的性能&查看 go 开的线程数?
问题:进程线程协程的区别?
问题:select poll epoll 的区别?
- select 有大小限制 效率低 对 socket 是线性扫描 同步多路复用 O(n)
- poll 与 select 类似 但是用的链表结构 所以没有大小限制 同步多路复用 O(n)
- epoll可以理解为event poll,不同于忙轮询和无差别轮询,epoll会把哪个流发生了怎样的I/O事件通知我们。所以我们说epoll实际上是事件驱动(每个事件关联上fd)的,此时我们对这些流的操作都是有意义的。(复杂度降低到了O(1))
tcp/udp
问题:tcp time await 发生在哪端?
A: 发生在四次挥手时客户端,最后会等2MSL。
问题:为什么客户端最后还要等待2MSL?
答:MSL(Maximum Segment Lifetime),TCP允许不同的实现可以设置不同的MSL值。第一,保证客户端发送的最后一个ACK报文能够到达服务器,因为这个ACK报文可能丢失。站在服务器的角度看来,我已经发送了FIN+ACK报文请求断开了,客户端还没有给我回应,应该是我发送的请求断开报文它没有收到,于是服务器又会重新发送一次,而客户端就能在这个2MSL时间段内收到这个重传的报文,接着给出回应报文,并且会重启2MSL计时器。如果客户端收到服务端的FIN+ACK报文后,发送一个ACK给服务端之后就“自私”地立马进入CLOSED状态,可能会导致服务端无法确认收到最后的ACK指令,也就无法进入CLOSED状态,这是客户端不负责任的表现。第二,防止失效请求。防止类似与“三次握手”中提到了的“已经失效的连接请求报文段”出现在本连接中。客户端发送完最后一个确认报文后,在这个2MSL时间中,就可以使本连接持续的时间内所产生的所有报文段都从网络中消失。这样新的连接中不会出现旧连接的请求报文。
在TIME_WAIT状态无法真正释放句柄资源,在此期间,Socket中使用的本地端口在默认情况下不能再被使用。该限制对于客户端机器来说是无所谓的,但对于高并发服务器来说,会极大地限制有效连接的创建数量,称为性能瓶颈。所以建议将高并发服务器TIME_WAIT超时时间调小。RFC793中规定MSL为2分钟。但是在当前的高速网络中,2分钟的等待时间会造成资源的极大浪费,在高并发服务器上通常会使用更小的值。
http
https 相关
grpc
其他QA
- Q: 解释graceful 平滑重启?
- Q: