写点什么

Week 8 性能优化

用户头像
evildracula
关注
发布于: 2020 年 12 月 13 日

文件与硬盘 IO

Linux inode 文件控制块

  • inode 中记录着文件权限、所有者、修改时间和文件大小等文件属性信息,以及文件数据块硬盘地址索引。

  • inode 是固定结构的,能够记录的硬盘地址索引数也是固定的,只有 15 个索引。

  • 每个 inode 最多可以存储 12+256+256256+256256*256 个数据块,如果每个数据块的大小为 4k,也就是单个文件最大不超过 70G。


Raid 独立硬盘冗余阵列



分布式文件系统 HDFS


数据结构与算法

时间/空间复杂度

  • 时间复杂度

  • 并不是计算程序具体运行的时间,而是算法执行语句的次数

  • O(2^n) 表示对 n 数据处理需要进行 2^n 次计算

  • O(1), O(log(n)), O(n^a) 多项式时间复杂度

  • O(a^n), O(n!) 非多项式时间复杂度

  • 空间复杂度

  • 一个算法在运行过程中临时占用存储空间大小的量度

  • O(n) 表示需要临时存储 n 个数据

NP 问题

P 问题:能在多项式时间复杂度内解决的问题。

NP 问题:能在多项式时间复杂度内验证答案正确与否的问题。

NP ?= P

NP-hard 问题:比 NP 问题更难的问题(NP 问题的解法可以规约到 NP-hard 问题的解法)

NP 完全问题:是一个 NP-hard 问题,也是一个 NP 问题。


数组

创建数组必须要内存中一块连续的空间。

数组中必须存放相同的数据类型。

随机快速读写是数组的一个重要特性,根据数组的下标访问数据,时间复杂度为 O(1)。


链表

链表可以使用零散的内存空间存储数据。

所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

要想在链表中查找一个数据,只能遍历链表,所以链表的查找复杂度总是 O(N)。


Hash 表

Hash 冲突


  • 数组和链表都被称为线性表。

  • 栈就是在线性表的基础上加了这样的操作限制条件:后面添加的数据,在删除的时候必须先删除,即通常所说的“后进先出”。

  • 线程运行时专有内存被称为线程栈


队列

队列也是一种操作受限的线性表,栈是后进先出,而队列是先进先出。

典型应用场景:生产者消费者;阻塞等待的线程被放入队列。


二叉排序树

  • 左子树上所有结点的值均小于或等于它的根结点的值。

  • 右子树上所有结点的值均大于或等于它的根结点的值。

  • 左、右子树也分别为二叉排序树。


平衡二叉排序树

  • 从任何一个节点出发,左右子树深度之差的绝对值不超过 1。

  • 左右子树仍然为平衡二叉树。

  • 旋转二叉树恢复平衡:

  • 插入时,最多只需要两次旋转就会重新恢复平衡。

  • 删除时,需要维护从被删节点到根节点这条路径上所有节点的平衡性,时间复杂度 O(logN)。


红黑(排序)树

  • 每个节点只有两种颜色:红色和黑色。

  • 根节点是黑色的。

  • 每个叶子节点(NIL)都是黑色的空节点。

  • 从根节点到叶子节点,不会出现两个连续的红色节点。

  • 从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点。

  • 增删节点的时候,红黑树通过染色和旋转,保持红黑树满足定义


  • 红黑树最多只需 3 次旋转就会重新达成红黑平衡,时间复杂度 O(1)。

  • 在大量增删的情况下,红黑树的效率更高。

  • 红黑树的平衡性不如平衡二叉树,查找效率要差一些。


跳表


常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划


网络通信协议

WEB 请求通信历程


网络数据包格式


OSI 七层模型和 TCP/IP 四层模型


链路层

链路层就是将数据进行封装后交给物理层进行传输,主要就是将数据封装成数据帧,以帧为单位通过物理层进行通信,有了帧,就可以在帧上进行数据校验,进行流量控制。


链路层会定义帧的大小,这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上添加一个 HTTP 头一样,数据链路层也会将封装好的帧添加一个帧头,帧头里记录的一个重要信息就是发送者和接受者的 MAC 地址。MAC 地址是网卡的设备标识符,是唯一的,数据帧通过这个信息确保数据送达到正确的目标机器。

数据链路层负载均衡


网络层

网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器,请求离开 App 后,到达运营服务商的交换机,交换机会根据这个 IP 地址进行路由转发,可能中间会经过很多个转发节点,最后数据到达目标服务器。


网络层的数据需要交给链路层进行处理,而链路层帧的大小定义了最大传输单元,网络层的 IP 数据包必须要小于最大传输单元才能进行网络传输,这个数据包也有一个 IP 头,主要包括的就是发送者和接受者的 IP 地址。


IP 负载均衡

传输层(TCP 协议)

IP 协议不是一个可靠的通信协议,不会建立稳定的通信链路,并不会确保数据一定送达。要保证通

信的稳定可靠,需要传输层协议 TCP。


TCP 协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP 作为一个比较基础的通讯协议,有很多重要的机制保证了 TCP 协议的可靠性和强壮性:


使用序号,对收到的 TCP 报文段进行排序和检测重复的数据无错传输,使用校验和检测报文段的错误使用确认和计时器来检测和纠正丢包或者延时流量控制,避免主机分组发送得过快而使接收方来不及完全收下拥塞控制,发送方根据网络承载情况控制分组的发送量,以获得高性能同时避免拥塞崩溃丢失包的重传


TCP 建立 3 次握手过程

TCP 关闭连接 4 次握手

  • 客户端向服务器端发送一个 FIN,请求关闭数据传输。

  • 当服务器接收到客户端的 FIN 时,向客户端发送一个 ACK,其中 ACK 的值等于 FIN + SEQ。

  • 然后服务器向客户端发送一个 FIN,告诉客户端应用程序关闭。

  • 当客户端收到服务器端的 FIN 是,回复一个 ACK 给服务器端。其中 ACK 的值等于 FIN + SEQ。


应用层(Http 协议)

而互联网应用需要在全球范围为用户提供服务,将全球的应用和全球的用户联系在一起,需要一个统一的应用层协议,这个协议就是 HTTP 协议。

Http 请求的 7 种方法

Http 响应的 5 种状态

Http1.1


Http2

Http3

QUIC


非阻塞网络 I/O

Socket 接受数据,系统内核的处理过程


非阻塞 I/O 结构


系统 I/O 复用方式

Select (Poll)管理下的 read 过程


epoll 管理下的 read 过程


无连接时,selector.select 被阻塞方式


发布于: 2020 年 12 月 13 日阅读数: 33
用户头像

evildracula

关注

还未添加个人签名 2019.07.29 加入

还未添加个人简介

评论

发布
暂无评论
Week 8 性能优化