架构师训练营第 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 事件列表