写点什么

架构师训练营 - 性能优化 2

用户头像
Pontus
关注
发布于: 2020 年 07 月 28 日

参考

Data Structure

1D

  • Array(String), Linked List

  • Stack, Queue, Priority Queue, Deque, Set(hashset(o(1)) or treeset(o(logn))), Map(hashmap or treemap)

2D

  • Tree, Graph

  • Binary Search Tree(red-black tree, AVL), Heap, Disjoint Set 并查集, Trie 字典树

Others

  • Bitwise 位运算, BloomFilter 布隆过滤器

  • LRU Cache

Algorithm

General Coding

  • If...else

  • For loop

  • Recursion(Divide and Conquer, Backtrace)

High-Class

  • Binary Search

  • Breadth-first/Depth-first Search (BFS/DFS)

  • Dynamic Programing

  • Greedy

  • Math/Geometry 几何

切题四步

  • Clarification 沟通题目需求、边界

  • Possible SolutionsCompare(time/space complexity)Optimal(加强)

  • Coding

  • Test Cases



五遍刷题法

  • 刷题第一遍五分钟:读题+思考直接看解法,注意比较解法优劣背诵、默写好的写法

  • 刷题第二遍马上自己写,LeetCode提交多种写法比较、体会 - 优化

  • 刷题第三遍过一天后,再重复做题不同解法的熟练程度,专项练习

  • 刷题第四遍过了一周,反复回来练习相同的题目

  • 刷题第五遍面试前回来恢复性训练

思想

  • 化繁为简拒绝人肉递归找到最近最简方法,将其拆解成可重复解决的问题数学归纳法思维

  • 刻意练习五毒神掌寻求反馈

Time/Space Complexity







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



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





网络数据包格式



物理层

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



链路层

链路层就是将数据进行封装后交给物理层进行传输,主要就是将数据封装成数据帧,以帧为单位通过物理层进行通信,有了帧,就可以在帧上进行数据校验,进行流量控制等。链路层会定义帧的大小,称为最大传输单元(MTU)。数据链路层会将封装好的帧添加一个帧头,帧头记录的一个重要信息就是发送者和接受者的MAC地址。



网络层

网络层IP协议使得互联网应用根据IP地址就能访问到目标服务器,请求离开APP后,到达运营商的交换机,交换机会根据这个IP地址进行路由转发,可能中间会经过很多个转发节点,最后数据到达目标服务器。网络层的数据需要交给链路层进行处理,而链路层帧的大小定义了最大传输单元,网络层的IP数据必须要小于最大传输单元才能进行网络传输。



传输层协议

IP协议部署一个可靠的通信协议,不会建立稳定的通信链路,并不会确保数据一定送达。要保证通信的稳定可靠,需要传输层协议TCP。TCP协议是一种面向连接的,可靠的,基于字节流的传输层协议。TCP作为一个比较基础的通信协议,有很多重要的机制保证了TCP协议的可靠性和健壮性。比如:使用序列号进行TCP报文段的排序和判重;使用校验进行报文段的错误检测;使用确认和重传定时器进行丢包重传;流量控制,避免发送方发送数据过快而接收方接受不过来;拥塞控制,避免网络拥塞。



HTTP请求的7种方法

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

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

Post:提交请求。

Put:上传请求。

Delete:删除URL标识的资源。

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

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



HTTP协议版本

1.0:1996年发布,客户端和服务器之间交换的每个请求/响应都会创建一个新的TCP连接,会产生延迟。

1.1:加入了保持连接的概念来解决这个问题,降低了很多建立连接的开销。但是这个连接不能并发处理多个请求。

2.0:引入了HTTP流的概念,允许将多个不同的HTTP并发地复用同一个TCP连接,使得浏览器更高效地复用TCP连接。但是,TCP并不理解HTTP流,当多个HTTP请求复用一个TCP连接,如果前面的请求/响应没有处理完,后面的请求/响应也无法处理,也就是会出现队头阻塞的现象。

3.0:使用QUIC的传输协议。协议在传输层把流当作一等公民来看待。多个QUIC流共享相同的QUIC连接,因此不需要额外的握手和慢启动来创建新的QUIC流。QUIC流是独立的,其中一个流的丢包不会影响其他流。



BIO Blocking I/O阻塞I/O

进行I/O操作时,用户线程会一直阻塞,直到读操作或者写操作完成。



Socket接收数据,操作系统内核处理过程



非阻塞I/O(Non-Blocking I/O)

I/O操作立即返回,发起线程不会阻塞等待。

非阻塞read:

1)Socket接收缓冲区有数据,读n个(不保证数据被读完整,因此可能要读多次)

2)Socket接收缓冲区没数据,则返回失败(不会等待)

非阻塞write

1)Socket发送缓冲区满,返回失败(不会等待)

2)Socket发送缓冲区不满,写n个数据(不保证一次性全部写入,因此可能要多次写)



Select(poll)管理下的read过程

主要是通过遍历所有socket的方式。缺点是socket数量多时,遍历成本很高,拷贝成本也高。



epoll管理下的read过程





数据库架构

连接器:数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对于数据库而言相对比较重,需要花费一定的时间。

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



为什么PrepareStatement更好

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



数据库事务日志

进行事务操作时,事务日志文件会记录更新前 数据记录,然后再更新数据库中的记录,如果全部记录都更新成功,那么事务正常结束,如果过程中某条记录更新失败,那么整个事务全部回滚,以及更新的记录根据事务日志中记录的数据进行恢复,这样全部数据都恢复到事务提交前的状态,仍然保持数据一致性。



LSN:一个按时间顺序分配的唯一事务记录日志序列号。

TransID:产生操作的事务ID。

PageID:被修改的数据再磁盘上的位置。

PrevLSN:同一个事务产生的上一条日志记录的指针。

UNDO:取消本次操作的方法,按照此方法回滚。

REDO:重复本次操作的方法。



用户头像

Pontus

关注

还未添加个人签名 2018.04.21 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 性能优化2