写点什么

架构师训练营第 8 周学习总结

用户头像
菜青虫
关注
发布于: 2020 年 12 月 13 日
  • 文件与硬盘 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 事件列表



用户头像

菜青虫

关注

还未添加个人签名 2017.11.20 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 8 周学习总结