架构师训练营第八周 - 总结
1. 数据结构与算法
2. 网络通信协议
3. 非阻塞网络 IO
4. 数据库架构原理与性能优化
数据结构与算法
数据结构
常见的数据结构有数组、链表、树
算法是在这些数据结构上对数据进行操作的一系列动作
评判算法好坏有两个维度,时间复杂度和空间复杂度
时间复杂度
并不是计算程序具体运行的时间,而是算法执行语句的次数和数据量的关系
O(1),O(log(n)),O(n^a)多项式时间复杂度
O(a^n)和 O(n!)非多项式时间复杂度
空间复杂度
一个算法在运行过程中临时占用存储空间的大小的标尺
O(n)表示要处理的数据量为 n,需要另外 n 个单位的存储空间
常见的时间空间复杂度有 O(1),O(log(n)),O(n),O(nlog(n)),O(n^2),O(n^3),O(2^n),O(n!)
NP 问题
P:能在多项式时间复杂度内解决的问题
NP:能在多项式时间复杂度内验证答案正确与否的问题
NP 问题范围包含 P 问题
NP-hard:比 NP 问题更难的问题
NPC:可以规约到 NP-hard 问题的 NP 问题就是 NPC 问题。
数组
数组的存储需要一块连续的空间,存储的内容是相同的数据类型。
数组的一个重要特性是随机快速读写,根据数组下标访问数组数据,时间复杂度为 O(1)
链表
链表使用非连续内存空间。
链表中的节点都包含指向下一个节点的地址,最后一个节点指向 null
查找链表中的元素,只能遍历链表,所以链表的查询时间复杂度为 O(1)
链表中替换删除等操作很简单,找到元素后,时间复杂度为 O(1)
Hash 表
hash 表结合了数组和链表
hash 表中,key 和 value 组成一个 Map.Entry
hash 表根据 key 计算 hash 值,然后与数组长度做余数 hash,hash 值为 Entry 需要放入的位置
若计算出的数组位置有值,即存在冲突的情况下,则把 Entry.next->原 Entry,array[hash]=Entry
栈
数组和链表是线性表
栈也是一种线性表
栈被规定只能在栈顶做操作:入栈和出栈
栈具有的特点被称为后进先出
线程调用使用的数据结构是栈,存储的元素是栈帧
队列
队列也是线性结构
队列有队头和队尾,操作有:入队和出队,从队尾入队,队头出队
队列的特点是先进先出
典型的应用场景是生产者消费者模型
使用队列搜索出好友中关系最近的有钱人
使用队列搜索最短路径
树
树的节点类型有:根节点,叶子节点,普通节点
节点间的关系有:父节点、子节点、兄弟节点、祖先节点、子孙节点
二叉排序树
树上的一个节点最多有两个子节点
左子树的值小于或等于根节点
右子树的值大于根节点
左右子树也分别为二叉排序树
二叉排序树在不平衡的情况下,退化为链表
平衡二叉(排序)树
从任何一个节点出发,左右子树深度之差的绝对值不超过 1
左右子树仍然为平衡二叉树
插入时,最多只需要两次旋转就会恢复平衡
删除时,需要维护从被删除节点到根节点这条路径上所有节点的平衡性,时间复杂度为 O(log(n))
红黑(排序)树
每个节点只有两种颜色:红色和黑色
根节点都是黑色
每个叶子节点(NIL)都是黑色的空节点
从根节点到叶子节点,所有路径上,不会出现两个红色节点相连的路径
从任何一个节点出发,到叶子节点,所有路径上黑色节点的数目都相等
增删节点时,红黑树通过染色和旋转,保持红黑树满足定义
红黑树 VS 平衡二叉树
红黑树最多通过三次旋转就可达到红黑树再次平衡,时间复杂度为 O(1),平衡二叉树最多是 lO(og(n))
在大量增删的情况下,红黑树效率更高
红黑树的平衡性不如二叉平衡树,查询效率要差一些
跳表
对于一个有序链表,不断加大 step,生成一个长度变小的链表
通过查找小的链表,提高查找数据的效率
常用算法
穷举算法
递归算法
贪心算法
动态规划
穷举算法
使用列举出所有情形的方法,找出最优解
递归算法
在快速排序中,使用了递归算法
递归算法要有退出条件,以及递推工时
算法的时间复杂度为 O(n*log(n))
贪心算法
通过获得每一步的最优解来获取整体最优解
贪心算法获得的整体最优解不是数学上的最优解
迪杰斯特拉算法
改进的贪心算法,在最短路径中的使用
找出“最便宜”的节点,即可在最短时间内到达的节点
更新该节点邻居的开销,检查是否有前往它们的更短路径,如果有,就更新其开销
重复该过程,直到对图中的每个节点都这样做了
计算最终路径
动态规划
动态规划解决背包问题
使用网格,横轴是限制条件,单位按实际刻度来
纵轴是可选物品,可按照价值高低升序排序
从上往下开始填表格,填写在当前限制和物品下的最佳组合
最后在右下角得出最佳组合
遗传算法
遗传算法的遗传操作
选择
交叉
变异
遗传算法的核心内容
参数编码
初始群体的设定
适应度函数的设计
遗传操作设计
控制参数设定
遗传算法的特点:得到的解不是最整体最优解,是局部最优解
网络通信协议
网络协议在设计时,分层
有两种分层方式
OSI 的标准七层,TCP/IP 的实用四层
OSI 七层
物理层(Physical Layer)
数据链路层(Data Link Layer)
网络层(Network Layer)
传输层(Transport Layer)
会话层(Session Layer)
表示层(Presentation layer)
应用层(Application Layer)
TCP/IP 四层
网络访问(链路)层(Network Access(Link)Layer)
网络互联层(Intennet Layer)
传输层(Transport Layer)
应用层(Application Layer)
OSI 与 TCP 对应关系
1,2 == 1
3 == 2
4 == 3
5,6,7 == 4
网络数据包格式
链路层协议头
IP 协议头
TCP 协议头
HTTP 协议头
以上协议头从外到内
TCP 三次握手
客户端先发送 SYN=1,Seq=X 的报文,请求建立连接,X 是一个随机数
服务端收到这个报文后,应答 SYN=1,Seq=Y,ACk=X+1,表示同意建立连接
客户端收到报文后,检查 ACK 的值是否为 X+1,确认连接,并发送 ACK=Y+1 的报文给服务器;服务器收到报文后,确认 ACK 值为自己发送的 Seq+1,确认建立连接
通过以上散步,TCP 连接建立
TCP 四次挥手
主动方发送一个 FIN,seq=m,请求关闭连接
被动方收到主动方的 FIN,回应主动方发送一个 ACK,其中 ack=m+1
被动方向主动方发送 FIN 码,seq=n
主动方收到被东方的 FIN,回应主动方一个 ACK 码,ack=n+1
HTTP 请求的七种方法
GET
只读请求,不产生副作用,服务端无状态变更
POST
提交请求,一般用于创建
PUT
上传请求,一般用于变更
DELETE
删除 URL 标识的资源
OPTIONS
请求服务器所支持的方法,测试服务器是否正常
TRACE
回显服务器收到的请求,用于测试或者诊断
HEAD
和 GET 类同,但是只返回响应头
HTTP 响应的五种状态
1XX
请求已被服务器接收,继续处理
2XX
请求已成功被服务器接收,理解,处理
3XX
需要后续操作才能完成这一请求
4XX
请求含有词法错误或者无法被执行
5XX
服务器在处理某个正确请求时,发生错误
HTTP 协议版本
HTTP/1.0
客户端请求到资源后,关闭连接。并发量大的时候,会频繁的创建、关闭 TCP 连接,而 TCP 三次握手,四次挥手会消耗一定的时间
HTTP/1.1
默认启用长连接,客户端可以用一个 TCP 连接默认发送多个请求,引入了管道机制,客户端不用等上个请求得到响应就可以发送下个请求,但服务端是按照请求的顺序进行响应,半双工模式
HTTP/2
复用 TCP 连接的方式不同,依然遵循请求响应模式,但客户端发送多个请求和服务端给出多个响应的顺序不受限制,既避免“队头阻塞”,又能更快获取响应,全双工模式
非阻塞网络 IO
BIO
BlockingIO,阻塞 IO,一个线程服务一个 Socket 连接,处理读写关闭时间
read、write 时,请求被阻塞,等待数据到达内核并从内核态复制到用户态
NIO
Non-Blocking I/O
I/O 操作立即返回,发起线程不会阻塞等待
系统 I/O 复用方式
select
poll
epoll
说下对非阻塞的理解,BIO 时代,之所以阻塞,是 I/O 时间内核没有通知用户线程。当内核有了通知用户线程的机制,只需用户注册感兴趣的 I/O 事件到内核,内核感知连接上是否可读、可写。可读时,把数据放入读取缓冲区,可写时,通知用户继续写(写有带宽以及 TCP 连接上拥堵限制等)。请求连接时,通知用户常见一个连接 Socket,处理读、写、关闭等操作。
数据库架构原理与性能优化
数据库组成
连接器
为每个连接分配一块内存空间,用于连接回话上下文管理。连接对数据库来说是一个重操作,消耗高,一般会在应用服务启动后,就会创建几个连接缓存着供后续传输 SQL 使用
语法分析器
分析 SQL 语句,生成 SQL 语法树,可检查 SQL 是否正确
语义分析与优化器
将各种复杂嵌套的 SQL 进行语义等价转化,得到有限集中关系代数计算结构,利用表索引信息进一步优化
执行引擎
根据执行引擎的不同,生成执行计划,执行
PrepareStatement
PrepareStatement 会预先提交带占位符的 SQL 到数据库进行预处理,提前生成执行计划,当给定占位符参数,真正执行 SQL,执行引擎直接执行,效率更高,因为提前做了语法分析、语义分析与优化
B-树和 B+树
相比于 B-树,B+树非叶子节点不存储数据,所有的数据都存储在叶子节点,且叶子节点之间有链接
索引
聚簇索引
聚簇索引的数据库记录和索引在一起。典型的,像 MySQL 的主键索引就是聚簇索引
非聚簇索引
在叶子节点记录的不是数据行,而是聚簇索引,也就是主键。
通过非聚簇索引找到聚簇索引,再通过聚簇索引找到行记录的过程,被称为回表
创建索引
优点
查找行记录表较慢,通过添加索引,提高查找效率
缺点
索引创建消耗时间长
创建索引时,所有数据库增删改操作全部阻塞,对应用来说,查询也表现为阻塞
索引占用存储空间
增删改数据时,要联动修改索引,维护不易
数据库事务
事务特性 ACID
原子性(Atomicity)
事务要么全部完成,要么全部取消。如果事务崩溃,状态回到事务之前
一致性(Consistency)
只有合法的数据(遵守关系约束和函数约束)才能写入数据库
隔离性(Isolation)
两个事务 T1 和 T2 运行,事务 T1 和 T2 最终的结果是相同的,不管 T1 和 T2 谁先结束,隔离性主要依靠锁实现
持久性(Durability)
一旦事务提交,不管发生什么(崩溃或者出错),数据要保存在数据库中
数据库事务日志
进行数据库事务日志操作时,事务日志文件会记录更新前的数据记录,然后再更新数据库中的记录。如果全部记录更新成功,那么事务正常结束;如果过程中某条记录更新失败,那么整个事务全部回滚,已经更新的记录根据事务日志中记录的数据进行恢复,这样全部数据都恢复到事务提交前的状态,仍然保持数据一致性。
事务日志组成
LSN
一个按时间顺序分配的唯一事务记录日志序列号
TransID
产生操作的事务 ID
PageId
被修改的数据在磁盘上的位置
PrevLSN
同一个事务产生的上一条日志记录的指针
UNDO
取消本次操作的方法,按照此方法回滚
REDO
重复本次操作的方法
评论