暑期实习 - 面试准备

#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 每日一题
  • 激发
    • 挑战
    • 成就
  • 动机
    • 发挥特长 收获满足
• 什么时间可以入职
  • 25.3 毕业
  • 6月份~毕业
  • 杭州!
• 反问问题
  • 面试表现如何/还需要加强哪些方面
  • 新员工培养机制
  • (HR) 面试之后下一步的安排是怎样的
  • (HR) 面试之后大概多久能出结果
  • 对于实习生/这个职位的期望
  • 如果我有幸能成为公司的一员，请问我在入职前需要提前做哪些准备
  • (故作思考)~转正率有多少 (一般不回答)
  • 我想要了解的都已经了解到了，您讲的也非常清楚，我这里没有什么问题了，谢谢
• STAR 原则
  • Situation
  • Task
  • Action!
  • Result!

#智力题

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

#计算机基础

#数据结构 ✅

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

#算法 ❓

• 排序算法
  • 选择排序
  • 插入排序 (打牌) 稳
  • 冒泡排序 稳
  • 快速排序
  • 归并排序 稳
  • 桶排序
  • 堆排序
  • 基数排序 稳
  • 希尔排序
  • 稳定 & 不稳定
  • 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 多核对称
  • NUMA 多核不对称

#操作系统 ✅

• 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
• 压测
  • 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
• 异常
  • 构造函数抛异常
  • 析构函数抛异常
  • 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
  • 网络
    • netstat
    • ss
  • 内存
    • sar
• 缓存 ❓
  • 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
    • -解决不了拜占庭问题
  • Raft
    • 关键点: 心跳同步log, 新log覆盖旧log, 选主过半数机制
    • -解决不了拜占庭问题
    • Log结构
      • Term
      • Index
      • Command
    • AppendEntries
      • Leader -> Follower
      • 包含log
      • 用于同步log
    • RequestVote
      • Candidate -> Follower
      • 用于选主
  • 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

#大数据

• 文件系统

  • GFS ❓
  • HDFS ❓
  • TaobaoFS ❓

• 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