架构师训练营第 8 周学习总结
文件与硬盘 IO
* 机械硬盘 - 性能跟数据存储是否连续有关
* 固态硬盘 - 随机读写性能比机械硬盘好一个数量级
* 数据库索引存储结构是 B+树,但由于离散存储,还是需要几十毫秒访问到数据
* LSM 树连续存储数据
* Linux inode 文件控制块 ,12 个数据块指针,一/二/三级间接索引表指针,最大支持 70G 单个文件
* RAID 独立硬盘冗余阵列
* RAID 0 - 数据没有冗余,多个磁盘同时读写
* RAID 1 - 数据完全复制一份,但读写性能没有提升
* RAID 10 - 多个硬盘分为两组,互为备份,也会提升读写性能
* RAID 5 - 只记录 XOR 校验位,校验位轮流写在每个磁盘(校验位写在固定盘是 RAID 3)
* RAID 6 - 记录两个校验信息,P:XOR 校验码,Q:伽罗华域的校验码
* 分布式文件系统 HDFS
* NameNode 记录元数据,相当于文件控制块
* 64M 数据块,写数据会有三个备份
* DataNode 通过心跳机制汇报自己的状态
常见数据结构
* NP ?= P
* P 问题:能在多项式时间复杂度内解决的问题
* NP 问题:能在多项式时间复杂度内验证答案正确与否的问题
* NP-hard 问题:比 NP 问题更难的问题
* NP 完全问题:一个 NP-hard 问题,也是一个 NP 问题
* 数组
* 空间连续、类型相同、随机快速读写
* 链表
* 空间零散、数据长度可以不一样、快速增删数据
* 数组链表结合,实现快速查找和快速增删
* Hash 表
* 底层数据结构是数组,存储指针
* 下标计算方式:计算 key 的 hash 值,然后余数取模
* hash 冲突的数据会以链表的形式存储在对应下标
* 栈
* 增加“后进先出”限制的线性表
* 应用场景:函数调用
* 队列
* 增加“先进先出”限制的线性表
* 应用场景:生产者消费者;公平锁;搜索好友中关系最近的有钱人;搜索最短路径
* 红黑树
* 解决二叉排序树不平衡问题
* 平衡二叉排序树的插入最多两次旋转可以恢复平衡,但删除需要维护被删节点到根节点的平衡性
* 定义
* 根节点是黑色
* 每个叶子节点是黑色的空节点
* 从根节点到叶子节点,不会出现两个连续的红色节点
* 从任何一个节点出发,到叶子节点,路径上都有相同数目的黑色节点
* 最多 3 次旋转可以恢复红黑平衡
* 平衡性不如平衡二叉树,查询效率要低,但增删效率更高
* 跳表
* 链表元素本身是排序的
* 挑拣元素形成新的链表,元素比较多时可以形成多级链表
常用算法
* 递归算法
* 快速排序算法
* 贪心算法
* 背包问题
* 局部最优解可能不是全局最优
* Dijkstra 最短路径算法:查找起点到每个节点的最短路径
* 动态规划
* 大问题拆解为小问题,对小问题进行求解
* 遗传算法
* 基因编码:对问题的解空间元素进行编码
* 适应函数:计算每个基因编码的目标值
* 控制参数:问题的限制条件,淘汰不满足限制的基因
* 选择算法:选择基因进行遗传
* 交叉遗传:选择交叉点位置进行基因片段互换
网络通信协议
* TCP/IP 四层模型
* 链路层:在物理媒介上传输有地址的帧
* 网络层:为数据包选择路由
* 传输层:提供端对端的传输控制
* 应用层:提供会话管理、数据格式和应用支持
* 链路层负载均衡
* 集群服务器使用跟负载均衡器同样的虚拟地址
* LB 根据某种选择算法确定目标服务器,修改 mac 地址后把请求转发给应用服务器
* 应用服务器直接发送响应给客户端,不需要通过 LB 中转
* IP 负载均衡
* LB 会修改请求的源地址转发给应用服务器
* 响应需要通过 LB 返回给客户端,LB 可能会成为瓶颈
* TCP 3 次握手/ 4 次挥手
* HTTP 协议
* HTTP/1.0: 每个请求都会创建新的 TCP 连接
* HTTP/1.1: TCP 连接复用,每个连接只能执行一次请求/响应交换
* HTTP/2: 引入 HTTP 流的概念,并发复用 TCP 连接,顺序处理模式会出现队头阻塞现象
* QUIC: UDP 传输,应用程序自行处理包顺序
非阻塞网络 I/O
* I/O 操作立即返回,发起线程不会阻塞等待
* NIO:在每个时间片通过 selector 来处理时间
* poll:selector 遍历所有 socket 找到有事件发生的 socket
* epoll:需要操作系统支持 eventpoll 事件列表
评论