暑期实习 - 面试八股文大纲

发表于 分类于 ， 阅读次数： 本文字数： 8.8k 阅读时长 ≈ 32 分钟

#Leetcode

  • 链表
  • dp
  • 排列组合
  • 大数模运算
  • 图算法
  • 数论
  • 字符串

#杂项

  • 自我介绍
  • 开放性问题
    • 项目中遇到的困难问题
    • 最近关注的新技术
    • 最近读了什么书
      • 高性能 MySQL
      • Redis 源码分析
      • 设计数据密集型应用 DDIA
      • 大规模并行处理器程序设计
    • 还在面其他的什么公司没
      • 其他几家云厂商，不过首选的是 xx
    • 有没有别的 offer
      • 目前拿到了一个 xx 的 offer，但不是最满意的，其他厂在评估中；贵公司的 offer 与我的意向最最相符
    • 为什么选择 xx 城市: 学校/家里/npy 在 XX
    • 为什么来 xx 公司
      • xx 公司是国内领先
      • 离学校比较近
      • 我的兴趣是 xx 和 yy 公司很匹配
      • 能够让我发挥特长，施展才学，获得成就感
    • 时间管理
      • 利用层次化的 todolist 软件分解、管理任务
      • 优先完成紧急的
    • 保研细节
      • 为什么选择这个实验室
      • 为什么选择这个方向
        • 解决的问题（软件工程问题）很贴近现实且重要
        • 采用的方法 AI 新颖，是未来的趋势
    • 职业规划
      • 1-2 年内 认真完成工作任务 全面建立起对这个行业和市场的了解
      • 未来的 3 年之内，我希望靠自己优秀的业绩从 xxxx 职位的执行工作上升到管理方面的工作。
      • 远期规划，我会根据环境的变化，工作内容的变化，以及我自身能力的变化，不断进行调整的。
      • 对于职业规划，我暂时的考虑是这样子的。谢谢！
    • 关于加班
      • 如果遇到紧急任务 牺牲部分个人时间 没问题
    • 用过公司什么产品
      • ECS/轻量应用/数据库/缓存/容器服务
    • 最佩服的人
      • Linus Torvalds 技术大牛 构建了今天的互联网
    • 字节的产品 抖音、今日头条、多闪、飞书、西瓜视频、火山小视频、faceU 激萌、悟空问答、飞聊、皮皮虾、懂车帝、图虫
    • 优点
      • 实事求是
    • 缺点
      • i 人 有时喜欢自闭 但是也在逐步变得 open
    • 印象最深的事情
      • 参加学校的 CTF 竞赛，奋战一周，最终获得校内第一名
    • 兴趣爱好
      • 骑自行车/跑步
      • 音乐
      • 读书
    • 烦恼
      • 有点 i
    • 最大的挫折
      • 论文被拒
    • 朋友评价
      • (导师) 有责任感
      • (同学) 能力强
      • 热心 乐于助人
      • 有点 i
    • 坚持最久的事情
      • Leetcode 每日一题
    • 激发
      • 挑战
      • 成就
    • 动机
      • 发挥特长 收获满足
  • 什么时间可以入职
  • 反问问题
    • 面试表现如何/还需要加强哪些方面
    • 新员工培养机制
    • (HR) 面试之后下一步的安排是怎样的
    • (HR) 面试之后大概多久能出结果
    • 对于实习生/这个职位的期望
    • 如果我有幸能成为公司的一员，请问我在入职前需要提前做哪些准备
    • (故作思考)~转正率有多少 (一般不回答)
    • 我想要了解的都已经了解到了，您讲的也非常清楚，我这里没有什么问题了，谢谢
  • STAR 原则
    • Situation
    • Task
    • Action!
    • Result!

#智力题

  • 高楼扔鸡蛋
  • 老鼠喝毒药
  • 海盗分金
  • 博弈论
    • 两个人轮流拿 1 或 2 或 3 个的石头，怎么能保证拿到最后一个

#计算机基础

#数据结构 ✅

  • 哈希表
    • 冲突解决
      • 开链法
        • 链表
        • JDK>=8 红黑树
      • 开放寻址
        • 线性探测法
        • 二次探测法
      • 再哈希
    • 扩缩容
      • 负载因子 = 元素个数 / 桶个数
        • JDK 默认 >0.75 扩容
        • Redis <0.1 缩容
      • Redis - 渐进式 Rehash
        • 防止扩容时 key 过多导致卡顿
        • 懒迁移
      • HashMap 一次性完成
  • B 树 B+树
    • +节点密度大, 3 层能存 2kw 数据, 需要的 IO 少
    • -节点分裂合并复杂
    • 使用场景
      • MySQL 索引
  • SkipList
    • 查找,插入 O(logn)
    • +编写简单
    • +插入删除更简单
    • -2kw 需要 24 层, 查询需要的跳转/IO 次数多
    • 使用场景
      • Redis
      • RocksDB
      • Lucene & ElasticSearch
  • AVL
  • Rb-tree
  • 堆

#算法 ❓

  • 排序算法
    • 选择排序
    • 插入排序 (打牌) 稳
    • 冒泡排序 稳
    • 快速排序
    • 归并排序 稳
    • 桶排序
    • 堆排序
    • 基数排序 稳
    • 希尔排序
    • 稳定 & 不稳定
    • STL -> timsort
    • Java ->

排序方法 平均 好 坏 空间 稳定性插入排序 n² n n² O(1) 稳希尔排序 n² n n² O(1)
选择排序 n² n² n² O(1)
冒泡排序 n² n n² O(1) 稳堆排序 nlogn nlogn nlogn O(1)
快速排序 nlogn nlogn n² nlogn
归并排序 nlogn nlogn nlogn n 稳基数排序 O(d(r+n)) O(d(n+rd)) O(d(r+n)) O(rd+n) 稳

  • 布隆过滤器
    • key -> hash 到多个 key
    • 快速判断元素是否存在于某个集合里面
  • 图算法
    • Dijkstra: BFS 每个节点更新最短距离，单源，需要无负权边+无环
    • Flord

#体系结构 ❓

  • MMU
    • 位于 CPU 芯片内部
    • 将 CPU 请求的虚拟地址翻译成物理地址
    • TLB
      • 缓存了当前进程使用的页表项(PTE)
      • 在 MMU 旁边 被 MMU 使用
  • CPU Cache
    • 速度
      • L1: 1ns 64KB
      • L2: 4ns 256KB
      • L3: 10ns 8MB
      • Memory: 100ns 8GB
    • 拓扑
      • Write Through: 写内存同时写 Cache
      • Write Back: 写 Cache, 异步写内存
    • 多核缓存一致性
      • MESI(梅西)协议
        • M: Modified
        • E: Exclusive
        • S: Shared
        • I: Invalid
      • MOESI(萌西)协议
        • O: Owner
        • +允许多个 CPU 同时共享同一块缓存
        • +性能更好
  • 内存栅栏 ❓
  • NUMA
    • UMA(Uniform Memory Access) 多核对称
    • NUMA(Non-Uniform Memory Access) 多核不对称
    • Note: 苹果的 UMA(Unified Memory Architecture) 表示 CPU/GPU 共享内存，和这里的 UMA 不是一回事

#操作系统 ✅

  • Socket
  • 文件系统
  • Shell 命令 ✅
  • CPU 管理
    • 进程 线程 协程
      • 进程
        • 资源分配单位
        • 有自己的地址空间 堆 PCB 页表 文件表 信号处理
      • 线程
        • 执行和调度单位
        • 有自己的栈 寄存器
      • 协程
        • 用户态模拟的线程
        • 程序自己控制切换
    • 进程状态
      • R: Running 可被调度
      • S: Sleeping 等待中 可以被信号等中断
      • D: Sleeping 系统调用中 不可被中断
      • T: Stopped 收到了 SIGSTOP/SIGCONT 继续
      • Z: Zombies 进程已结束 但在等待父进程读取状态
      • X: Dead 已经退出
    • 孤儿进程: 父进程退出
    • 进程文件: lsof, /proc/fd/fd
    • 调度算法
      • FCFS
      • SPF
      • RR
      • 多级队列
    • 进线程切换
      • 上下文切换
      • 特权级切换
      • 页表切换
        • 刷新 TLB
    • 进程间通信
      • 信号
      • 利用锁
        • 消息队列 msg{get,snd,rcv}()
        • 信号量 sem{init,post,wait}()
      • 利用文件
        • 管道/FIFO
        • UDS
        • TCP
      • 利用内存
        • 共享内存 shm{get,at}()
  • 锁
    • mutex
    • semaphore
    • 原子变量
    • 条件变量
    • volatile
    • CAS
      • ABA 问题
    • 死锁
  • 内存管理
    • 为什么需要段页
      • -如果连续分配内存会导致碎片
    • 段式内存管理
      • 段表 段权限
      • -外碎片
    • 页式内存管理 x86-64
      • 4k 固定大小 页权限
      • +缓解外碎片 提高内存使用效率
      • -内碎片
      • 缺页中断
      • 换页算法
        • LRU
        • LFU
        • FIFO
    • 段页结合
      • 段表+页号+偏移
      • -> 页表+页号+偏移
      • -> 地址
    • Linux 实际上不使用段机制
      • SegFault 检测实际上是通过设置页权限实现的

#OOP & 设计模式 ❓

  • 封装 继承 多态
  • 继承的缺点
    • 不够灵活 随着项目发展 不利于重构
    • 会有菱形继承问题
    • golang Rust 等很多语言去掉继承
  • 重载
  • 工厂模式
  • 单例模式
  • Builder 模式
  • 代理模式
  • 适配器模式

#计算机网络 ❓

  • OSI 七层
    • L7 应用层
    • L6 表示层
    • L5 会话层
    • L4 传输层
    • L3 网络层
    • L2 数据链路层
    • L1 物理层
  • OSI 五层
  • 交换机 路由器
  • 常见的网络协议
    • MAC
    • TCP/UDP
    • SSH
    • FTP
    • ARP
  • IP 协议 网络层
    • IP 头 20 字节 源 ip 目标 ip
    • ARP
      • 广播 ARP 请求 询问
      • ARP 欺骗
    • ICMP ping
    • DHCP
    • NAT
  • TCP 协议 传输层
    • 可靠 点对点 字节流 面向连接 20 字节
    • 源 port 目标 port seq ack 长度 标志
    • 可靠性保证 ❓
      • 序列号 确认机制 超时重传
      • 流量控制 拥塞控制
      • 握手流程
        • 第二次握手重试
      • 挥手流程
        • 第一轮：
          • Est -(+FIN)-> FIN_WAIT_1 -(-ACK)-> FIN_WAIT_2
          • Est -(+ACK/-FIN)-> CLOSE_WAIT
        • 第二轮
          • FIN_WAIT_2 -(+ACK/-FIN)-> TIME_WAIT … CLOSE
          • CLOSE_WAIT -(+FIN)-> LAST_ACK -> CLOSE
        • 主动方 TIME_WAIT 等待 2MSL ❓
          • 保证对端正确断开
          • 保证本次连接所有报文都过期 不影响下次连接
      • 保活机制 (Linux SO_KEEPALIVE) 非标准 ❓
    • 流量控制 ❓
      • 侧重按照接收者的接收能力来发送数据
      • 发送 接收 滑动窗口
        • Selective ACK 额外回复收到了哪些段数据
        • Duplicate ACK 额外回复哪些段数据重复接收
        • Nagle 算法 接收窗口太小时 累计一定数据后(MSS)再发送
          • -实时性变差
          • TCP_NODELAY 关闭
        • 延迟 ACK 组合多个 ACK 为一个
          • -实时性变差
          • TCP_QUICKACK 关闭
    • 拥塞控制 ❓
      • 侧重避免网络出现负载过大的情况
      • 慢启动 指数增加
      • 拥塞避免 线性增加
      • 拥塞发生 超时重传 RTO 指数倍增 保险 回到起点
      • 快速恢复 快速重传 收到了 3ACK 没超时但是重传
      • BBR 拥塞控制算法 ❓
    • 调优选项
      • TCP Fast Open(TFO)
        • 第二次连接 通过 TFO cookie 省略一个 RTT
      • tcp_tw_recycle
        • TIME_WAIT 状态快速回收
      • tcp_tw_reuse
        • 复用 TIME_WAIT 状态的连接
        • 依赖 tcp_timestamps 启用时间戳
    • 缺陷
      • -队头阻塞: 中间丢包导致后面阻塞
      • -不支持网络迁移
    • 网络攻击
      • syn flood
        • 服务器只收到 SYN -> SYN_RCVD 半连接
        • 增大半连接队列
        • syn cookie
    • 应用问题
      • 对端断电 保持 ESTABLISHED 状态
        • 对端退出 FIN
        • 对端重启 RST
      • 大量 SYN_RCVD (等待对方第三次握手)
        • 缩短超时 (SYN Timeout) 时间
        • 增大半连接队列
        • SYN cookie 技术
          • 自己不再分配内存记录 而是将信息保存到第二次握手回复中
          • 等第三次握手再获取这个信息
      • 大量 CLOSE_WAIT (等待我方 close())
        • 对端 shutdown 自己没有 shutdown
      • 大量 TIME_WAIT (先关闭方 等待第四次的 ack 彻底过期)
        • 确保应用层使用长连接 Connection: Keep-Alive
          • 设置长连接超时时间
        • 使用 tcp_tw_reuse 和 timestamp
        • 增大 tcp_max_tw_buckets 默认 18000
        • SO_LINGER: 用 RST 代替 FIN, 不安全
  • QUIC 协议 传输层
    • 基于 UDP 实现可靠传输 旨在取代 TCP
    • +单连接传输多个流 避免队头阻塞
    • +握手过程集成 TLS 节约连接设置的开销
    • +包含连接 ID 支持底层网络切换
  • UDP 协议 传输层
    • 无状态 面向报文 8 字节
  • HTTP 协议
    • 0.9
    • 1.0
    • 1.1
      • Keep-Alive 默认开启
        • Connection: close 服务器回完 resp 就 close
          • 容易导致大量 TIME_WAIT
      • 流水线
        • -HTTP 队头阻塞
    • 2.0 ❓
      • http 请求头压缩编码
      • 二进制帧 请求头可以二进制
      • 引入流 可以单连接传输多个流
      • 服务器推送
      • -TCP 队头阻塞
    • 3.0 ❓
      • 底层 TCP->QUIC
    • 报文格式
      • GET / HTTP/1.1\r\nHost: xxx.com\r\n\r\nPAYLOAD
      • HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\nBODY
    • 状态码
      • 101 Switch
      • 200 OK
      • 301 Moved Permanently
      • 302 Found
      • 400 Bad Request
      • 403 Forbidden
      • 404 Not Found
      • 500 Server Error
      • 502 Bad Gateway
    • 请求方法
    • 请求头
    • 缓存控制
  • DNS 协议 应用层
    • over UDP
      • DOH DOT DOQ
    • 本地域名服务器
      • 递归解析
    • 根域名服务器
      • DNS 劫持
      • DNS 放大
        • 假装受害者发起大量 DNS 查询请求
      • DNS flood
  • SSL/TLS 协议 应用层和传输层之间/会话层
    • 建立流程 四次握手 ❓
      • ClientHello - ServerHello
      • KeyExchange - Finished
    • 密钥协商: RSA(大质数分解) -> DH(离散对数) -> ECHDA
    • 对称加密
    • 证书机制
    • 中间人攻击
    • 客户端验证 颁发客户端证书 类似网银 ukey
  • RPC
    • 一种调用方式
    • 没有 http 的条条框框 效率更高
    • 可以定制 例如使用 protobuf thrift
    • 一般基于 tcp 实现 也有基于 http2.0
  • WebSocket
    • HTTP 长连接
    • HTTP 长轮询
  • 扫码登录

#软件测试

  • 单元测试框架
    • CppUnit
    • GTest
      • TEST
      • TEST_F
      • TEST_P
  • 压测
    • TCP 压测 iperf3
    • HTTP 压测 wrk

#编译原理

  • 编译器过程
  • C/C++编译过程

#语言

#Java ❓

  • 基本数据类型
    • int vs Integer
    • 自动拆箱
    • 小整数优化
  • 抽象类 接口
  • 重载 重写
  • 字符串处理
  • Collections ✅
    • ArrayList
      • x1.5 扩容
      • 线程安全版 -> Vector
    • LinkedList
    • Hash{Map,Set}
      • x2 扩容
      • get() ❓
      • put() ❓
      • 线程安全版 -> HashTable
      • 线程安全版 2 -> ConcurrentHashMap
      • 记录插入顺序 -> LinkedHash{Map,Set}
    • Tree{Map,Set}
    • Stack 线程安全
    • BlockingQueue 线程安全
  • Comparable
  • 面向对象特性
    • Object 类
      • 析构 finalize()
      • 复制 clone()
      • 容器 hashCode() equals()
        • equals() 默认实现比较引用是否相同
      • 反射 getClass()
      • 字符串 toString()
      • 同步相关 wait() notify() notifyAll()
        • wait() 让持有此对象的监视器的线程等待
        • notify() 唤醒
  • 并发 ❓
    • ThreadLocal
    • Lock
    • synchronized
      • 修饰方法
      • 修饰代码块
      • 持有对象的锁
    • volatile
    • JUC
    • 线程
    • 线程池
      • 创建线程开销大
      • 状态
        • RUNNING
        • SHUTDOWN
        • STOP
        • TERMINATED
      • 参数调优
        • CPU 密集: n+1
        • IO 密集: 2n
  • 反射
  • JVM ❓
    • 内存结构 ❓
      • 程序计数器 PC
      • Java 栈: 和 C++的栈类似
      • 本地方法栈(C 栈): JNI 方法的栈
      • 堆 Heap
      • 方法区
        • 类信息
        • 静态变量
        • 常量
        • JIT 编译后的代码
      • 直接内存(堆外内存): JNI 直接分配的内存
    • 堆 Heap 结构
      • 新生代
        • Eden
        • Survivor
      • 老年代
      • 永久代
      • 元空间
    • 类加载器
      • Bootstrap
      • Extension
      • Application
    • GC 算法
      • 引用计数
        • -循环引用
      • 标记清除
      • 标记整理
      • CMS
        • Minor GC
        • Full GC
      • ZGC
  • JDBC

#C/C++ ❓

  • malloc
    • sbrk() mmap()
    • ptmalloc glibc
    • jemalloc Facebook
    • tcmalloc Google
      • thread cache
  • 编译
    • 工具
      • cmake
      • meson
      • makefile/ninja
      • gradle
  • 编译和链接
    • 变量位置
      • 局部变量 栈上
      • 全局 静态变量 零初始化 bss 否则 data
  • STL 容器
    • vector
      • 扩容 VSx1.5 GCCx2
        • x2 会导致重新分配
    • vector/stack
    • queue/deque
    • list
    • map/set
    • multimap/multiset
    • unordered_map/unordered_set
  • 引用
  • OOP
    • 类
      • 构造 析构
      • 复制 移动
      • 类 vs 结构体
        • 类默认 private 结构体默认 public
      • 空类 1 字节
    • 封装
      • 保护级别
      • friend
    • 继承 & 多态
      • 保护级别 区别
      • 关键字
        • final 防止继承
        • override 关键字 明确重写
      • 虚函数
        • Class() 不能是虚函数 否则无法调用
        • ~Class() 必须是虚函数
        • 纯虚函数: 没有实现(=0)的虚函数
      • 抽象类
        • 包含 纯虚函数 的类
        • 不可以被 new
      • 虚函数表
        • 每个(继承抽象类的)类一个 编译器分配
        • 每个对象有一个隐式的虚表指针成员
        • MRO 中有几个独立的抽象类 就会有几个虚表指针
      • 虚继承 virtual 继承
        • 防止菱形继承
        • 使得虚函数表更加复杂 且内存布局变化
      • 对象切片问题: 派生类对象赋值给基类对象
  • C++11
    • move() forward()
  • C++20 协程
  • 四种 cast
    • static_cast
    • const_cast
    • reinterpret_cast
    • dynamic_cast
    • std::reinterpret_pointer_cast
    • std::bit_cast
  • 异常
    • 构造函数抛异常
    • 析构函数抛异常
    • new 抛异常
  • 智能指针
    • unique_ptr
      • 内部: 对象指针
    • shared_ptr & weak_ptr
      • 内部: 对象指针, &use_count, &weak_count, (可选)Mutex
      • 多个共享指针持有同一个控制块
      • make_shared 创建智能指针
      • : public shared_from_this
        • 内部: 一个 weak_ptr(this)
    • auto_ptr
    • 实现
      • 原子变量
      • 引用计数
  • 并发
    • 原子操作
      • i++ 不是原子
    • volatile
      • 标记变量可能被未知的因素更改
      • 避免激进的优化 每次都去读内存
  • malloc
  • SAFINE:
  • CRTP: Curiously Recurring Template Pattern
    • A 继承 SomeTemplate<A>

#Golang

  • GMP 模型
    • G 协程
    • M OS 线程
    • P CPU 核
    • 调度: M:N 有栈 抢占式
  • 避免共享内存 使用通信
  • defer 语法

#JavaScript ❓

#Rust ❓

  • OwnerShip
  • Lifetime
  • 泛型
  • trait
  • Tokio 异步
    • 异步任务
  • 比 c/c++的优势
    • 内存安全
  • Unsafe
    • 有时候安全更重要

#Linux

  • 文件
    • 一切皆文件
    • 类型
      • Regular
      • Directory
      • Link
      • Char Dev
      • Block Dev
      • Socket
      • Pipe
    • inode
      • 内容
        • 大小
        • 权限
        • 所有者
        • 三个时间
        • 链接数
    • 打开文件: path->inode->block
  • 锁
    • 自旋锁 spinlock
      • -饥饿
    • Rwlock
    • seqlock
    • RCU
    • futex ❓
  • ELF
    • 结构
      • ELF 头
      • Program HT 程序头
      • Section HT 节数组
    • 静态链接
    • 动态链接
      • 链接
        • 加载 libc.so
      • 装载
        • dl{open,sym,close}()
  • PIE vs PIC
  • IO 多路复用
    • select
    • poll
    • epoll
  • 零拷贝
    • 内核态 only 减少切换次数: sendfile, splice
    • 利用 DMA
    • COW
    • 用户态 IO: SPDK, DPDK
  • Coredump
  • 链接与库
    • 静态链接
    • 动态链接
    • 装载
  • 运维命令
    • 负载
      • uptime
      • vmstat
      • top
      • atop
    • 网络
      • netstat
      • ss
      • ifstat
    • 内存
      • sar
      • free
  • 缓存 ❓
    • kswapd
    • 硬盘 Page Cache
    • File Cache
  • I/O 模型
    • Reactor 对 IO 事件反应
      • 单线程
      • 多线程
    • Proactor
  • UDS vs TCP
  • connect() 系统调用实现
  • 上下文切换
    • X86 Gate
  • 硬件中断
    • 顶半部 底半部
    • 软件中断
      • softirq
      • tasklet
      • workqueue
  • CPU 调度
    • 时机
      • 时钟中断 时间片用完
      • 系统调用
  • tcpdump
    • eBPF
      • 嵌入内核的虚拟机
      • Hook 内核 API

#MySQL ❓

  • SQL 基本
    • 语句
    • SQL 注入
      • PreparedStatement
      • WAF 过滤
  • 数据类型
  • 范式 ❓
    • 第一范式 列不可分
    • 第二范式 非主属性完全函数依赖于主键
    • 第三范式 非主属性既不部分依赖于主键也不传递依赖于主键
    • BC 范式 不允许主键的一部分被另一部分或其它部分决定
  • 引擎
    • MyISAM
      • +插入, 查询性能
      • -只有表锁
      • -不支持外键
      • -不支持事务
      • 适合非事务型负载 OLAP?
    • InnoDB
      • +行锁
      • +聚簇索引
      • +支持外键
      • +支持事务
    • 底层存储
      • MyISAM
        • 数据.myd 和索引.myi 分开存储
        • 数据按插入顺序存储
        • 索引 B+树叶子节点存数据行号 -> 没有聚簇索引
      • InnoDB
        • 数据和索引保存在一起
        • 主索引 B+树叶子节点存数据本身 -> 聚簇索引
        • 需要一个主 key 没有会自己创建
    • 区别
  • 索引 ❓❓
    • 优缺点
      • +加快速度
      • -空间开销
      • -维护索引开销
    • 索引类型
      • hash 索引
        • -范围查询
        • -模糊查询
        • -联合索引 最左匹配
      • Btree 索引
      • Fulltext 索引
        • +查询文本中的关键字
        • 模糊匹配
          • like ‘%abc%’ 场景
      • Rtree 索引
        • +地理数据范围查询
    • 聚簇索引
      • 聚簇索引
        • 数据和索引放在一起存储 索引的叶子节点保存数据
        • 相对的 其他索引叫做二级索引 次级索引
        • 举例 InnoDB
      • 非聚簇索引
        • 数据和索引分开存储 索引的叶子节点保存数据行号
        • 举例 MyISAM
    • 覆盖索引
      • 查询结果都包含在索引中
      • 不需要回表
    • 最左匹配原则
    • 索引失效的场景
      • like ‘%abc’ ‘%abc%’
      • 使用了表达式/函数/UDF
      • 包含隐式类型转换
      • 非前缀匹配
      • OR 单边索引
    • 索引使用原则
      • 经常查询的 where 条件
      • 长串索引需要限定前缀长度 看区分度
  • 优化
    • 查询慢
      • 缺少索引
    • 插入慢
      • 索引太多
    • show_query_log 定位慢查询
    • explain
      • “Using index” = 使用了覆盖索引
      • “type: ALL” = 全表扫描
      • “key: xxxx” = 使用了 xxxx 索引
    • optimize table 碎片整理
  • 事务 ✅
    • 概念: BEGIN 和 COMMIT 包裹起来的一组 SQL 语句
    • ACID ✅
      • 原子性: 事务要么全部执行 要么全部不执行
      • 一致性: 事务执行前后 数据库的完整性约束没有被破坏
        • 例如 A 转账给 B 两个账户总和不变
      • 隔离性: 事务之间互不干扰
      • 持久性: 事务提交后 数据库状态不会丢失 即使数据库崩溃
    • 事务隔离级别
      • RU 读未提交: 一个事务可以读取另一个事务未提交的数据
        • -脏读
      • RC 读已提交: 一个事务只能读取另一个事务已提交的数据
        • 对应方案: 行锁
        • -不可重复读: 在同一个事务中，多次读取同一数据返回的结果有所不同
      • RR 可重复读: 一个事务在执行期间看到的数据是一致的
        • 对应方案: MVCC 机制
          • 事务开始创建一个 Read View
          • 递增的事务 id 作为版本号
        • -幻读: 一个事务的写操作会导致另一个事务的查询结果不一致
          • e.g. 并发预订座位
          • 解决 1: 物化冲突: 改 SQL 用 FOR UPDATE 显式锁定
          • 解决 2: 使用序列化隔离级别
          • 解决 3: 使用范围锁，例如 next-key lock
        • -Write Skew: 更新不同数据破坏了一致性
          • e.g. 至少有一个医生值班
          • 解决: 应用侧控制
        • -Lost Update: 两个事务同时更新同一行
          • e.g. 并发计数器+1
      • SI 快照隔离
      • S 序列化 (完美)
        • -性能很差
    • MySQL 如何保证 ACID
      • 保证原子性 A
        • Undo log
      • 保证隔离性 I
        • 锁 + MVCC 机制
        • 锁
          • 记录锁(行锁) 锁定行 (3)
          • 间隙锁 锁定一个区间 (3,5)
          • 临界锁 (3,5]
          • 插入意向锁
      • 保证持久性 D
        • WAL 先写日志
        • Redo log (innodb)
          • 用于防止 Buffer Pool 因为异步落盘 数据丢失
          • 两个文件循环写 为了性能
          • 格式
            • 数据页位置+修改内容
        • Binlog
          • Server 层日志
          • 三种格式
            • STATEMENT SQL 语句
            • ROW 最终数据
            • MIXED
          • 保存开机后全量日志
          • 用于备份恢复 主从同步
      • 保证一致性 C
        • 前三个加起来
  • 锁 ❓
    • 全局锁
    • 表锁
      • MyISAM 默认
    • 行锁
      • MyISAM 没有
      • InnoDB 默认
      • 可能导致死锁
    • 页面锁
    • 乐观锁 & 悲观锁
      • 乐观锁: 先更新再检查是否有其他事务修改
        • 举例 共享文档 Git
      • 悲观锁: 先加锁再更新
  • MVCC 多版本并发控制
    • 提高并发性能
    • 当前读 读最新版本
    • 快照读
  • 主从同步
    • 目的 实现读写分离
    • 同步模式
      • 异步复制 (默认)
      • 全同步复制
      • 半同步复制
    • 配置
      • 主库 cnf 设置 server-id log-bin(>=8 默认开启)
      • 创建同步账户
      • SHOW MASTER STATUS;
      • 从库执行 SQL
        • START SLAVE;
        • SHOW SLAVE STATUS \G;
        • STOP SLAVE SQL_THREAD;
      • 从库升级成主库
        • RESET MASTER;
        • CHANGE MASTER TO
        • START SLAVE;
    • 主库在事务提交时 同步 binlog 到从库
    • 从库保存到 relay log 重放
      • 从库重放是 SQL Thread 单线程
    • 主从延迟
      • 避免大事务
      • 从库自身读压力太大 -> 增加从库数量分散压力
      • 设置 slave_parallel_workers 并行复制线程数 slave-parallel-type 并行复制策略
      • semi-sync 半同步复制
  • 分库分表
    • 单表行数超 500 万行或者单表容量超过 2GB
    • 垂直分库 按业务类型
    • 垂直分表 按字段
    • 水平拆分
      • ID 取模
    • MyCat
      • MySQL Stub
    • ShardingSphere
      • JDBC Stub
    • 分布式数据库
      • TiDB (兼容 mysql, HTAP)
      • Google Spanner
      • CockroachDB (兼容 pg, OLTP)
      • YugabyteDB (兼容 pg)

#Redis ✅

  • 特点
    • 性能
    • 功能
  • 单线程
  • 数据类型
    • string
    • list
    • hash
    • set
    • zset
  • 底层存储
    • int
    • sds
    • quicklist
    • 压缩列表/listpack
    • skiplist
      • SkipList vs B+tree
        • 实现简单
        • 占用内存少
        • 插入删除性能更好，没有旋转平衡的开销
    • hashtable
      • MurmurHash2
  • 持久化
    • RDB
      • 压缩
    • AOF 增量日志
      • 会定期 rewrite
    • 混合
  • Pub/Sub 机制
  • Key 过期机制
    • 惰性删除
    • 定期删除
  • 内存淘汰
    • noeviction
    • volatile-random
    • volatile-ttl
    • volatile-lru 默认
    • volatile-lfu
    • allkeys-random
    • allkeys-lru
    • allkeys-lfu
    • LFU 更好, LRU 容易受缓存污染影响
  • 实现事务
    • Redis 事务
    • Lua 脚本
  • 发布订阅
  • Redis 集群
    • 主从
      • 主库读写, 从库只读
      • 同步机制
        • 老版本 low 全量复制
        • 新版本 增量复制
        • 基于长连接的命令传播
    • 主从+哨兵 Sentinel
      • 哨兵: 一个集群 负责维护 Redis 集群的可用性
        • 监控集群是否正常 INFO 探活
        • 类似 Raft 协议
        • 自动故障转移
        • 提供配置
        • 通知客户端
      • 当>=quorum 个哨兵认为主库下线 则开始换主
        • 选择数据最完整的从库作为主库
      • 哨兵脑裂问题
        • 主节点虚假故障 丢失数据
        • 可以用 min-slaves 缓解 但是不能彻底解决
        • 换用强一致性的 Zookeeper
    • Cluster 模式
      • 去中心化 每个节点存储不同的分片
        • 没有使用一致性 hash 而是使用 crc16(key)/16384 因为开销较大
        • 存在迁出导入开销
      • 可以组合主从模式
      • GOSSIP 协议同步路由表和节点状态等信息
      • MOVED 重定向用户请求
      • ASK
  • 使用问题
    • 大 key
    • 缓存击穿 热点 key 过期
      • 设置热点 key 永不过期
      • 热点 key 加后缀散列
    • 缓存雪崩 大量 key 同时失效
      • 随机过期时间或永不过期
      • 热点数据分散
    • 缓存穿透 热点 key 不存在
      • 设置 key-null
  • 缓存一致性 (分布式一致性问题)
    • 缓存策略
      • Cache Aside: 读者读 db 时顺便设置缓存
        • -需要缓存设置过期时间
        • -过期时间内可能是旧的值
      • Read Through:
      • Write Through: 只写 db, 异步推送到缓存
      • Write Back: 只更新缓存, 异步写入 db
    • 同步机制
      • 更新派
        • 🔃 缓存, 🔃 db
          • 不好 缓存可能被另一个进程刷新为旧值
        • 🔃 db, 🔃 缓存
          • 不好 更新缓存需要计算 浪费系统资源
      • 删除派
        • 🆑️ 缓存, 🔃 db
          • 不好 缓存可能被另一个进程刷新为旧值
          • 延迟双删可以: 🆑️ 缓存, 🔃 db, 💤 延迟, 🆑️ 缓存
        • 🔃 db, 🆑️ 缓存
          • 好 第二步需要重试保证
    • 通用技巧
      • 过期时间
      • 终极方案 分布式锁
      • 失败重试
        • 单独线程
        • MQ
      • binlog 订阅

#Nginx & OpenResty

  • 功能
    • 负载均衡
      • 轮询
      • 加权轮询
      • 随机
      • 源地址(用户 IP)哈希
      • 最小连接数
      • 插件
        • fair (最快的)
        • URL(访问目标)哈希
    • 反向代理
  • 实现
    • 主从 Reactor 模式

#前端技术

  • Session & Cookie & Token
    • Session 服务端用于保存每个连接用户状态的对象
    • Cookie
      • 结构 name, domain, path, secure
      • 生命周期
        • 没设置过期时间 => 会话 Cookie 浏览器关闭即消失
        • 设置过期时间 保存在硬盘上
  • LocalStorage
    • 生命周期 不会过期
    • 大小 一般 5M
  • SessionStorage
    • 生命周期 浏览器关闭即消失
  • 浏览器加载资源的过程
  • 浏览器输入 URL 之后的过程

#后端技术

  • 缓存 -> Redis
  • Spring
    • AOP
    • IOC
    • 循环依赖
      • Bean 互相依赖
      • 三级缓存
        • 一级缓存为单例池 singletonObjects
        • 二级缓存为早期曝光对象 earlySingletonObjects
        • 三级缓存为早期曝光对象工厂 singletonFactories
    • Filter ❓
  • MyBatis
  • 高并发下库存超卖问题 ❓
    • 设置字段为无符号 依赖异常
    • 使用悲观锁
    • Redis 分布式锁
      • 事务 lua 脚本
      • 集群同步问题 RedLock
  • 限流
    • 固定窗口/滑动窗口
    • QPS 限流
      • +简单
      • +可以改周期增大突发流量
      • -周期边界不平滑
      • -放过请求不均匀
    • 令牌桶
      • +流量均匀
      • -第一个周期不平滑
    • 漏桶
      • -出水速度恒定 瞬时大流量会被丢弃

#中间件

  • 缓存
  • 消息队列
  • 定时任务
  • 日志采集

#消息队列

  • 作用 异步削峰解耦 日志 消息系统
  • 监控
  • 怎么保证消息不丢失
    • 消费者反馈消息收到
    • 数据持久化
  • 消息积压 ❓
    • 保存到硬盘上
  • 消息队列模型
    • 队列模型
      • 每个消费者一个队列
      • -不适合广播场景 (需要复制)
    • 发布-订阅模型
      • 消息有主题 消费者订阅主题 (Topic)
      • +支持广播场景
      • 示例 Kafka RocketMQ
  • RabbitMQ ❓
  • Kafka
    • 流式数据处理平台 by Linkedin
    • 适合离线和在线消息消费
    • 组件
      • Broker 中介人
        • Leader 提供服务 与客户端交互
        • Follower 不提供服务 只与 Leader 同步
      • ZooKeeper 元数据管理
    • 功能
      • 消息队列
      • 消息持久化
      • 消息流式处理
    • 消息分区 Partition & 消费者组 Consumer Group
      • Topic-Partition 一对多关系 目的是提高并行度
      • 相对地 Consumer Group 对等的消费者集群 消费一整个 topic
      • Partition 会平均分布在所有 Broker 上
      • 底层实现: append-only log file
    • 性能高
      • Page Cache 缓存
      • 磁盘顺序写
      • 零拷贝
      • Pull 拉模式
    • 消费模式
      • Push 模式
        • -容易挤爆消费者
      • Pull 模式
        • -容易导致空轮询
          • 可以设置成阻塞收取
    • 确认机制
      • 0 无确认 完全异步
      • 1 leader 确认即可 (默认)
      • -1 leader 和 follower 都确认
    • 主从同步 replica

#分布式系统

  • CAP 理论 ✅
    • C 强一致性
    • A 可用性
    • P 分区可用性
    • C+A:
    • C+P: Raft
  • BASE 理论 ✅
    • BA 基本可用
    • S 软状态
    • E 最终一致性
  • 强一致性
    • 线性一致性 集群看起来和单个节点一样
    • 顺序一致性 弱一点
  • 分布式共识算法 CP
    • Paxos ❓
      • 三种身份 Proposers Acceptors Learners
      • -解决不了拜占庭问题
      • Multi-Paxos
        • 乱序确认+乱序提交
    • Raft
      • 关键点: 心跳同步 log, 新 log 覆盖旧 log, 选主过半数机制
      • -解决不了拜占庭问题
      • Log 结构
        • Term
        • Index
        • Command
      • AppendEntries
        • Leader -> Follower
        • 包含 log
        • 用于同步 log
      • RequestVote
        • Candidate -> Follower
        • 用于选主
      • Multi-Raft
        • 一种工程架构模式，通过数据分片和并行 Raft Group 解决单组瓶颈，实现高性能与高扩展性
        • 实例: TiDB, CockroachDB, ByteKV
      • Parallel Raft
        • 阿里云 PolarFS 使用的 Raft 变种，借鉴 Multi-Paxos 的思想，允许 log 中存在空洞，提高性能
    • ZAB
      • 过半数 ACK 提交
  • 分布式锁 ❓
    • Redis setnx
      • 需设置过期时间 防止死锁
      • 需设置独特 value 防止被别人释放
      • 锁提前释放 后台线程去续期锁 可以用 Redission
      • Redis 集群同步可能丢锁 使用 Redlock
    • ZooKeeper 临时文件
      • 写强一致性 读不是(顺序一致性)
        • 读之前 sync()一下就是强一致
      • +连接结束会自动释放
      • -如果进程卡住 心跳不及时 会导致提前释放
    • Google Chubby (Paxos)
  • 一致性哈希
    • 防止节点扩容导致未知变化
    • Hash 环
    • 虚拟节点
  • 负载均衡算法
    • RR
    • Weight RR
    • Random
    • Weight Random
    • Hash
  • 分布式 ID
    • 雪花算法
  • 分布式事务
    • 两阶段提交 2PC ❓❓
      • +原理简单，实现方便
      • -同步阻塞 即所偶参与的事务逻辑均处于阻塞状态。
      • -单点故障 协调者存在单点故障问题，如果协调者出现故障，参与者将一直处于锁定状态。
      • -脑裂问题 在阶段二中，如果只有部分参与者接受并执行了 Commit 请求，会导致节点数据不一致。
    • 三阶段提交 3PC ❓❓
      • +降低了阻塞范围 在等待超时后，协调者或参与者会中断事务。
      • +避免单点故障 阶段 3 中协调者出现问题时，参与者会继续提交事务。
      • -脑裂问题
    • TCC
  • 系统
    • ZooKeeper
      • 分布式注册中心 按照目录层级划分 可以监听节点
      • ZAB 算法
      • 最好是奇数个节点
    • Etcd
      • 强一致性
    • Consul

#大数据

  • 分布式文件系统

  • NoSQL 数据库

    • Google BigTable
      • 分布式存储系统
      • 三个维度: 表名, 行键, 列键
      • 适合海量数据存储
      • 适合读多写少
    • HBase
      • OLTP 数据库 列式存储模型
      • 存储 PB 级别的海量数据 支持最多几万个稀疏列 支持快速随机查询
      • 追求数据一致性，CP 系统
      • HBase Shell
        • 类似 redis-cli
      • 底层是 kv 存储, 相对于基于 RocksDB 的分布式存储系统，成本更高
        • 结构: RegionServer, HMaster, ZooKeeper
        • RegionServer: 存储数据, 包含 Hlog 和若干个 HRegion
        • HRegion
          • 存储一段连续的 Tuples, 包含多个 Store
          • 基于 range 策略分散数据 支持分裂
        • Store(类似 Column Family): 包含一个 MemStore(类似 memtable) 和多个 StoreFile(类似 sstfile)
        • HFile
      • 热 Key 问题
        • 加盐
        • 哈希 类似 redis crc16
        • 反转 类似手机号
    • Cassandra ❓

  • 数据仓库 & 大数据分析

    • Google Spanner ❓
    • Google F1 ❓
    • Hive
      • OLAP 数据仓库 大数据查询、处理和计算引擎
      • 使用 HiveQL 进行查询
      • 底层支持多种执行引擎 MapReduce Tez Spark
    • Spark
      • 通用大数据处理引擎, 支持批处理、交互式查询、流处理、机器学习
      • RDD

  • OLAP

  • Kafka -> 消息队列

  • Lucene

  • 海量数据处理问题

    • 离线 Top n
    • 在线 Top n
    • 通用技巧
      • 数据结构: 位图 平衡树 索引 Trie BloomFilter
      • 分治 合并

  • MapReduce

#微服务

  • RPC
    • 原理
    • 框架
  • Nacos 注册中心
  • Dubbo 微服务框架

#存储

  • 块存储
    • Ceph
  • 文件存储
    • Ceph
    • HDFS
  • 对象存储
    • Ceph
    • MinIO
  • KV 存储
    • Redis
    • LevelDB
    • RocksDB
  • SSD
    • 优点
      • 读写速度快
      • 无噪音
      • 无碎片
    • 缺点
      • 寿命短
      • 价格高
      • 容量小
  • Log-Structured Merge Tree
    • vs B+Tree
    • 读放大: 读取的数据量和用户写入的数据量之间的比值
    • 写放大: 用户写入的数据量和实际写入磁盘的数据量之间的比值
    • LevelDB
    • RocksDB
  • 快照机制
    • COW
      • -1 次写变 1 读 2 写 写放大 性能低
    • ROW (Redirect On Write)
      • +不会有额外的写入
      • -有数据碎片

#数据库内核

  • LSM-Tree ❓
  • LevelDB ❓
  • RocksDB
    • WAL
    • MemTable
      • Immutable MemTable
    • Flush
    • Compaction
      • Leveled Compaction
        • 10 倍
        • +减少读放大
        • -写放大
      • Universal Compaction
        • 相当于前者只有一个 level
      • FIFO Compaction
        • 适合时间序列数据
      • Tiered Compaction
        • +减少写放大
        • -空间放大
    • 读路径
      • MemTable
      • Immutable MemTable
      • L0 全部 + BloomFilter
      • L1~Ln 二分查找 + BloomFilter
    • 写路径
      • WAL
      • MemTable
    • BlockCache
      • 保存 Data, Index, Filter
  • MySQL
  • Buffer Pool
    • 文件系统缓存层
  • 执行模型
    • 火山模型/迭代器模型
    • Batch 模型

#搜索

  • 粗排
  • 精排
  • 召回
  • 算法

#离散数学 & 密码学

  • 格 理想
  • 哈希算法
    • MD5 SHA1 SHA256
    • MurmurHash3 Fnv1a
  • 对称加密
    • DES 3DES AES
  • 非对称加密
    • RSA
      • -不支持前向保密
      • 大质因数分解
    • DSA
      • 大数离散对数
  • 密钥交换
    • Diffie-Hellman
    • EC Diffie-Hellman

#隐私计算

  • 方法
    • 差分隐私 DP
      • 将原始数据淹没在噪音中, 使得无法得到原始数据
    • 混淆电路 GC
    • 密钥分享 SS
    • 同态加密 HE
      • 原理 先加密再运算
      • 类型
        • 半同态加密 (Partially HE, PHE) 加密后只支持加法或乘法运算
        • 全同态加密 (Fully HE, FHE)
      • 方法
        • Pailier 算法
        • 复合剩余类问题 DCRA
      • 应用场景
      • 工具
        • Microsoft SEAL
  • 应用场景
    • 联合建模
    • 联合统计
    • 安全预测
    • 隐匿查询
    • 机构之间的联合计算
  • 安全两方计算 2PC
    • 工具
      • Cheetah 猎豹 阿里安全
  • 多方安全计算 MPC
    • 把多个参与方的数据放在一起计算出特定的结果 同时保证每一方信息的细节不被泄露 典型 百万富翁问题
  • 硬件设备
    • 多方安全计算 MPC
    • 同态加密 HE
    • 可信执行环境 TEE
    • 可信密态计算 TECC
  • 可信执行环境 TEE
    • 将处理器的一个区域与 CPU 的其余部分分开来使用基于硬件的安全计算模型
      • 隔离
      • 数据加密
      • 完整性校验
      • 远程认证
    • +安全性
    • -侧信道攻击
    • 实现
      • Intel SGX
        • LibOS
        • Grammy
      • ARM TrustZone
    • TEE OS
      • Occlum 蚂蚁
  • 联邦学习 FL
  • 隐私计算框架
    • TensorFlow Federated (TFF)
    • KubeTEE 蚂蚁
    • 隐语 蚂蚁
    • PySyft OpenMined

#安全

  • Web 漏洞
    • CSRF
    • XSS
    • SQL
    • WAF
  • 安全机制
    • SELinux
    • AppArmor
    • NX(Dep)
    • Seccomp 过滤系统调用
    • namespace
      • User
      • Net
      • PID
      • FS

#云计算 & 虚拟化

  • 云计算
    • IaaS
    • PaaS
    • FaaS
    • DBaaS
  • QEMU
  • KVM
  • Hypervisor
  • 体系结构
  • virtio
    • 模拟 PCI 设备 麻烦
    • VRing
    • Kick

#容器

  • Docker
    • 底层
      • namespace
      • cgroups
    • Containerd
  • K8S
    • 架构
      • kubelet
      • apiserver
      • etcd (raft) 配置信息和服务发现
      • controller
      • scheduler
      • runtime
        • containerd
      • kube-proxy
    • 概念
      • Pod
      • Node
      • Container
    • CRI
    • CNI
    • OCI
  • Docker
  • Containerd
  • Kata
    • +资源管理
    • +隔离彻底
    • -比较重
  • gVisor
    • +轻量级 开销更小
    • -不支持资源限制
    • -仍然是同一个内核
    • 两种工作模式
      • ptrace + Seccomp
        • 退出场景
          • 执行 syscall
          • 收到 signal

#音视频

  • 数字图像滤波
  • 图像特征
  • RGB YUV
  • 视频编码
  • 视频格式
  • 视频帧

#渲染引擎

  • C++
  • Unity Unreal 等引擎经验
  • 图形学 渲染 计算几何
  • 动画
  • 物理仿真

#机器学习 & 深度学习

  • C++
  • CNN
    • 卷积层
  • RNN
  • LSTM
  • Transformer
  • 移动端部署
    • TensorFlow Lite
    • NCNN
    • MNN
    • Paddle-Lite
    • 技术点
      • big.LITTLE 调度
      • OpenCL