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

用户头像
李君
关注
发布于: 2020 年 07 月 29 日
架构师训练营 第八周 学习总结

一. 数据结构与算法

1. 时间复杂度与空间复杂度

1.1 时间复杂度

  • 表示算法执行语句的次数

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

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

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

1.2 空间复杂度

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

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



2. NP问题

3. 基本的数据结构

3.1 数组

  • 创建数组必须要内存中一块连续的空间,数组中必须存放相同的数据类型。

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

3.2 链表

  • 链表可以使用零散的内存空间存储数据,所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

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

3.3 Hash表

  • 既可以快速访问数据,又可以快速删除数据。

3.4 栈

  • 栈就是在线性表的基础上加了,“后进先出”的操作权限限制。

3.5 队列

  • 队列是一种先进先出的的线性表。

3.6 树

3.6.1 二叉排序树
  • 左子树上所有节点的值均小于等于根节点的值; 右子树上所有节点的值均大于或等于它的根节点的值。

  • 左右子树也被称为二叉排序树。

3.6.2 不平衡的二叉排序树
  • 从任何节点出发,左右子树深度之差的对决值不超过1,左右子树任为二叉排序树。

3.6.3 平衡二叉排序树
  • 从任何一个节点出发,左右子数深度之差的绝对值不超过1.

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

3.6.4 红黑树
  • 每个节点只有两种颜色:红色和黑色。根节点是黑色,每个叶子节点都是黑色的空间节点。从根节点到叶子节点,不会出现连续的红色节点。从任何一个节点出发,到叶子节点,这条路径上都有相同数量的黑色节点。

3.7 跳表

  • 增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

4. 常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划

  • 遗传算法

二. 网络通讯协议

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





1.1 物理层

  • 物理层负责数据的物理传输,计算机输入输出的只能是01这样的二进制数据,但是在真正的通信线路里有光纤,电缆,无线设备等。光信号,电信号及电磁信号在物理上是完全不同的。如何让这些不同的设备能够理解,处理相同的二进制数据,这就是物理层需要解决的问题。

1.2 链路层

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

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

1.3 网络层

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

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

1.4 传输层(TCP协议)

  • IP协议不是一个可靠的通讯协议,不会建立一个稳定的通讯链路,并不会确保数据一定会送达。要保证数据的稳定可靠,需要传输层协议TCP。

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



  1. 使用序号: 对收到的报文段进行排序和检测重复的数据。

  2. 无错传输: 使用校验,检测报文段的错误;使用确认和计时器来检测和纠正丢包和延时。

  3. 流量控制: 避免主机分组发送的过快而使接收方来不及接受。

  4. 拥塞控制: 发送方根据网络承载情况控制分组的发送量,已获得高性能的同时避免拥塞崩溃丢失包的传输。

TCP的三次握手建立连接
  • 第一次握手: APP发送位码为syn=1,seq=x的报文,表示请求建立连接,X是一个随机数;

  • 第二次握手: 服务器收到这个报文后,答应syn=1,ack=x+1,seq=Y的报文,表示同意建立连接;

  • 第三次握手: APP收到报文后,检查ACK的值为自己发送seq的值+1,确认建立连接,并发送ACK=Y+1的报文给服务器;服务器收到这个报文后检查ACK值为自己发送的Seq+1,确认建立连接。至此,APP和服务器建立起TCP连接,就可以进行数据传输了。

TCP四次挥手关闭连接
  • 客户端向服务端发送一个FIN,请求关闭数据传输。

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

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

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

1.5 应用层 HTTP 协议

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

1.5.1 HTTP 请求的7种方法

  1. GET: 只读请求,get请求不应该发生任何状态改变。

  2. HEAD: 和get一样,只返回响应头。

  3. POST: 提交请求。

  4. PUT: 上传请求。

  5. DELETE: 删除URL标识的资源。

  6. TRACE: 回显服务器收到的请求,用以测试和诊断。

  7. OPTIONS: 请求服务器返回支持的所有HTTP请求方法,测试服务器是否正常。

1.5.2 HTTP 响应的5种状态

  • 1xx(消息): 请求已被服务器接收,继续处理。

  • 2xx(成功): 请求成功被服务器接收,理解,并接受。

  • 3xx(重定向): 需要后续操作才能完成这一请求。

  • 4xx(请求错误): 请求含有词法错误或者无法被执行。

  • 5xx(服务器错误): 服务器在处理某个正确的请求时发生的错误。

1.5.3 HTTP 协议版本

  • HTTP/1.0, 客户端请求到资源后会关闭连接,并发量大时会导致频繁创建,关闭TCP连接。而TCP三次握手,四次挥手会消耗一定的时间。

  • HTTP/1.1, 默认启用长连接模式,即客户端可以使用一个TCP连接顺序发送多个请求,新版本也引入了管道机制,客户端可以不用等上一个请求的响应结果就可以发送下一个请求,但是服务器端也是按照客户端请求的顺序进行响应的,可以理解为半双工模式。

  • HTTP/2,复用TCP连接的方式不同,依然遵循请求-响应模式,但客户端发送多个请求和服务端给出多个响应的顺序不受限制,这样既避免了“对头堵塞”,又能更快获取响应。



三. 非阻塞网络 I/O

1. Java NIO

1.1 面向缓冲
  • 传统的 IO 是面向流的,传统 IO 每次从流中读取一个或者多个字节,直至读取完所有的字节。而 NIO 是面向缓冲区的,所有的读写操作都需要通过 Buffer 来完成,数据会被先写入 Buffer 中,然后再进行处理,Buffer 提供了多种方法用于操纵其中的数据,因此其在操作上更加灵活,读取速度也更加快。

1.2 同步非阻塞
  • 传统 IO 的流都是单向的,因此它们需要分为 Input Stream 和 Output Stream。而 NIO 中的 Channel 则是双向的,数据可以从 Channel 读到 Buffer 中,也可以从 Buffer 写到 Channel:

  • Channel 可以设置为非阻塞模式,此时当 Channel 从 Buffer 中读取数据时,如果有待读取的数据则返回该数据;如果没有待读取的数据,对应的方法也不会阻塞,而是直接返回。

1.3 多路复用
  • Java NIO 通过 Reactor 模型实现了 IO 的多路复用,可以在一个线程上通过一个选择(Selector)使用轮询的方式去监听多个通道 Channel 上注册的事件,从而在一个线程上就能实现对多个 Channel 的处理。

四. 数据库架构原理与性能优化

1. 数据库架构

1.1 连接器
  • 数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言相对比较重,需要花费一定的时间,因此应用程序启动的时候,通常会初始化建立一些数据库连接放在连接池,这样处理外部执行SQL操作的时候,就不需要花费时间建立了。

1.2 语法分析器
  • 分析SQL的结构是否正确

1.3 语义分析与优化器
  • 语义分析与优化器就是将各种复杂嵌套的SQL进行语义等价转化,得到有限几种关系代数计算结构,并利用索引等信息进一步优化。

1.4 执行引擎



发布于: 2020 年 07 月 29 日 阅读数: 4
用户头像

李君

关注

结硬寨,打呆仗。 2018.09.11 加入

还未添加个人简介

评论

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