架构师训练营:第 8 周总结

用户头像
zcj
关注
发布于: 2020 年 07 月 29 日

数据结构与算法

算法的两个复杂度指标

时间复杂度:算法执行语句的次数,一般用大O表示法

常出现的时间复杂度

其中 为多项式时间复杂度

为非多项式时间复杂度

空间复杂度:一个算法在运行过程中临时占用存储空间大小的度量,也用大O表示法

如:O(n)表示 执行算法需要额外n个存储单元的开销。

NP问题

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

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

NP =P ?:待科学家证明。

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

NP完全问题:是一个NP-hard问题,也是一个NP问题 。(晕乎)

常见的数据结构

线性结构:

  • 数组:内存中一块连续的内存空间,数据类型必须相同,下标访问,随机访问快O(1),插入数据慢O(n)。

  • 链表:零散的内存空间通过地址指针指向串连。查找慢O(n),插入快O(1)。

  • Hash表:利用hash映射关系,将数据存储到对应数组下标中,hash冲突时用链表存多个数据。

  • 栈:LIFO 后进先出规则。

  • 队列:FIFO 先进先出规则。

  • 跳表:链表基础上每个节点增加跳跃访问后几个节点的特性。查找效率高,需要额外空间存储多跳的关联连接。

树型结构:

  • 二叉排序树:每个跟节点最多只能有两个子节点。做子节点小于跟节点,有子节点大于跟节点。

  • 平衡二叉树:二叉排序树基础上,限制树的左右子树深度差不超过1。二分查找时间复杂度O(logn),删除增加需要重新平衡,效率不高。

  • 红黑树:引入红黑节点颜色和空叶子节点规则,重新平衡效率高于平衡二叉树。查找效率稍差,增加删除节点效率好于平衡二叉树。

  • B树:树层级扁平,节点有序。一个节点下有多个子节点。

  • B+树:基于B树变化,跟节点不存储信息,只做索引使用。

网状结构:

  • 图:每个节点有多个到其他节点的路径。

  • 无向图: 到其他节点的路径没有方向

  • 有向图:到其他节点的路径有方向。

  • 带权图:到其他节点的路径有权值比重。

常用的算法

穷举算法:遍历算法执行每一个状态,最终会找到一个最优的可行解。适用于解决极小规模或者复杂度线性增长,而线性规模不会很大的状态。

递归算法:一种通过重复将问题分解为同类的子问题而解决问题的方法。

贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解

动态规划:一个问题由多个阶段决策组成,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的方法。

网络

Web请求的一次网络通信历程

如图:



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

ISO国际标准组织定义的OSI七层模型与现实真是使用的TCP/IP四层协议簇对比图



网络数据包的嵌套封装格式



TCP协议

TCP协议:面向连接,可靠,基于字节流的传输层协议。

有很多重要机制保证TCP协议的可靠性和强壮性:

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

  • 无错传输:使用校验和检测报文段的错误,使用确认和计时器类检测和纠正对包或者延时。

  • 流量控制:避免主机分组发送的过快二使接收方来不及完全收下

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



TCP连接的建立和关闭连接的过程

TCP三次握手过程

TCP连接关闭时四次确认离开过程



HTTP协议

超文本传输协议(英语:HyperText Transfer Protocol),缩写为HTTP,它是一种用于分布式、协作式和超媒体信息系统的应用层协议,是万维网的数据通信的基础,也是互联网应用最为广泛的一种网络传输协议互联网应用需要在全球范围为用户提供服务。

HTTP协议版本

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



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



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



HTTP协议 请求的 7 中方法

  • GET:只读请求,请求处理过程不应该产生副作用,即web应用不应该应为get请求二发生任何状态改变。

  • HEAD:和get方法一样,但是只返回响应头。

  • POST:提交请求

  • PUT:上传请求

  • DELETE:删除URL 标识的资源。

  • TRACE:回显服务器收到的请求,用以测试或者诊断。

  • OPTIONS:请求服务器返回的所有 HTTP 请求方法,测试服务器是否正常

HTTP协议请求数据格式



HTTP协议 响应的 5 种状态

  • 1XX : 请求已经被服务器接收,继续处理

  • 2XX : 请求以成功被服务器接收、理解、并接收

  • 3XX : 需要后续操作才能完成这一请求

  • 4XX : 请求含有词法错误或者无法被执行

  • 5XX : 服务器在处理某个正确请求时发生错误

HTTP响应数据格式



网络IO与多路复用

计算接上的应用在网络上 使用IP地址加端口的 套接字 互相连接通讯。 套接字Socket是系统对于应用网络连接的一个抽象。服务器端的socket可以监听 接收多个连接请求,每个请求建立一个TCP连接。



由于TCP基于字节流的传输,网络IO可能会阻塞。原始的 Socket程序 使用多个线程处理 网络通信连接,每一个连接创建一个单独的线程去处理。资源利用路不高,平凡的创建线程,请求数多时,线程会创建的非常多。



IO多路复用改进:应用的线程数固定,有一个主线线程负责监听连接的状态,包括准备建立连接、连接建立,连接中IO可读,连接IO可写四个状态。当监听到某个连接到达某转态时,将处理状态的动作交个子线程去处理。线程处理以后继续等待主线程分配其他的任务。 这样多线程就可以达到复用的目的,将某个状态的动作看做一个任务。子线程一个接着一个的去处理任务。



linux系统下的IO多路复用方式有三种select,poll,epll。其思路都一样,只是在监听到转态后的处理细节不同。



java中的IO

普通IO ,也叫OIO(旧IO)。是基于流的方式,从 普通IO读取或写入数据,就是直接调用到系统的网络IO的读写。



New IO, 也叫NIO。 是基于缓冲(buffer)的方式, 在系统网络IO 和 java的IO之间加了缓冲,当写入时先向缓冲写入,缓冲等待系统网络IO可写时,把缓冲数据写入到网路IO。读取时,当网络IO有数据可读时自动写入到缓冲,应用在从缓冲读取数据。

数据库

一条sql在数据库中的执行历程

数据库的各个模块

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



语法分析器:对sql的语法分析拆解。校验sql有没有语法错误。



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



执行引擎:对执行计划的sql执行。

使用 prepareStatement

PremareStatement 会预先提交带占位符的 sql 到数据库进行预处理计划,提前生成执行计划,当给定占位符参数,真正执行SQL的时候,执行引擎可以直接执行,效率更好。 还可以防止 SQL 注入攻击。

数据库的事务

数据库的事务特性ACID

  • 原子性 :事务要么全部完成,有么全部取消。如果事务崩溃,状态回到事务之前(回滚))

  • 隔离型: 如果2个事务T1 和 T2 同时运行,事务 T1 和T2 最终的结果是相同的,不管T1 和T2 谁先结束,隔离性主要依赖锁实现。

  • 持久性:一旦事务提交,不管发生什么(崩溃或出错),数据要保存在数据库中。

  • 一致性:只有合法的数据(依照关系约束和函数约束)才能写入数据库。

数据库事务隔离级别

事务并发代理的问题

脏读:事务A读取了事务B更新的数据,然后B回滚操作,那么A读取到的数据是脏数据



不可重复读:事务 A 多次读取同一数据,事务 B 在事务A多次读取的过程中,对数据作了更新并提交,导致事务A多次读取同一数据时,结果 不一致。



幻读:系统管理员A将数据库中所有学生的成绩从具体分数改为ABCDE等级,但是系统管理员B就在这个时候插入了一条具体分数的记录,当系统管理员A改结束后发现还有一条记录没有改过来,就好像发生了幻觉一样,这就叫幻读。



mysql事务隔离界别

事务隔离级别 脏读 不可重复读 幻读

读未提交(read-uncommitted) 是 是 是

不可重复读(read-committed) 否 是 是

可重复读(repeatable-read) 否 否 是

串行化(serializable) 否 否 否

关于分布式事务

分布式系统的事务

业界说法:几段式事务提交,回滚补偿机制

老师经验:通过架构方案避免分布式事务的情况,或者业务容忍数据不一致性。

自我总结:

本周主要讲述,算法数据结构,网络协议及数据库架构优化。 这些看起来在实际业务开发过程中用到的不多,自己对这节课的收获感受不如前几周的强烈。但还是意识到常用的基础理论知识,是一定要理解掌握的。不然会犯一些 基本的低级错误。 本节课多偏于理论,且是基础概念大概的讲一讲。需要自己看书去补充一个全面的认识。

用户头像

zcj

关注

还未添加个人签名 2019.10.12 加入

精神小伙

评论

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