架构师训练营：第 8 周总结
数据结构与算法
算法的两个复杂度指标
时间复杂度：算法执行语句的次数，一般用大 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 谁先结束，隔离性主要依赖锁实现。
持久性：一旦事务提交，不管发生什么（崩溃或出错），数据要保存在数据库中。
一致性：只有合法的数据（依照关系约束和函数约束）才能写入数据库。
数据库事务日志
进行事务操作时，事务日志文件会记录更新前的数据记录，然后在更新数据库中的记录，如果全部记录都更新成功，那么事务正常结束，如果过程中某条记录更新失败，那么整个事务全部回滚，已经更新的记录根据事务日志记录的数据进行恢复，这样全部数据都恢复到事务提交前的状态，任然保持数据一致性。
LSN:一个按时间顺序分配的唯一事务记录日志序列号。
TransID：产生操作的事务 ID。
PageID：被修改的数据在磁盘上的位置。
preLSN：同一个事务产生的上一条日志记录的指针。
UNDO：取消本次操作的方法，按照此方法回滚。
REDO：重复本次操作的方法。
数据库事务隔离级别
事务并发代理的问题
脏读：事务 A 读取了事务 B 更新的数据，然后 B 回滚操作，那么 A 读取到的数据是脏数据
不可重复读：事务 A 多次读取同一数据，事务 B 在事务 A 多次读取的过程中，对数据作了更新并提交，导致事务 A 多次读取同一数据时，结果 不一致。
幻读：系统管理员 A 将数据库中所有学生的成绩从具体分数改为 ABCDE 等级，但是系统管理员 B 就在这个时候插入了一条具体分数的记录，当系统管理员 A 改结束后发现还有一条记录没有改过来，就好像发生了幻觉一样，这就叫幻读。
mysql 事务隔离界别
事务隔离级别 脏读 不可重复读 幻读
读未提交（read-uncommitted） 是 是 是
不可重复读（read-committed） 否 是 是
可重复读（repeatable-read） 否 否 是
串行化（serializable） 否 否 否
关于分布式事务
分布式系统的事务
业界说法：几段式事务提交，回滚补偿机制
老师经验：通过架构方案避免分布式事务的情况，或者业务容忍数据不一致性。
自我总结：
本周主要讲述，算法数据结构，网络协议及数据库架构优化。 这些看起来在实际业务开发过程中用到的不多，自己对这节课的收获感受不如前几周的强烈。但还是意识到常用的基础理论知识，是一定要理解掌握的。不然会犯一些 基本的低级错误。 本节课多偏于理论，且是基础概念大概的讲一讲。需要自己看书去补充一个全面的认识。
还未添加个人签名 2019.10.12 加入
精神小伙
评论