架构师训练营第 0 期第 8 周学习总结

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

1、本周学习内容汇总

首先,算法和数据结构,对于提升性能会带来很大帮助,在代码中选择【时间复杂度】更低的算法,可以大大降低系统的执行时间,并且好的数据结构可以在将来设计中带来灵感。

另外,关于性能优化的就是数据库索引,因为有了索引,对数据库查询的性能才会提升,所以理解索引的数据结构和优化索引的方法,对提升系统整体系统很有必要。



2、数据结构与算法

使用好的数据结构与算法,也是提升系统性能的重要手段,比如多个数据的查询,使用【数组】或者【二叉树】这些数据结构,时间复杂度低,加快查询的时间,而对于数据的插入和删除操作,使用【链表】这种数据结构,也可以提升程序执行效率;

所以,选择适合的数据结构和算法,对系统性能提升也会起到很大帮助。

2-1、时间复杂度和空间复杂度

2-1-1、概念

时间复杂度并不是指算法的时间,而是指一个函数或方法中 算法语句 执行总次数;

一般用大写的英文字母【O】表示;



空间复杂度就是一个算法在运行过程中临时占用的存储空间大小,一个算法中创建对象越多,那占用的空间就越多;



2-1-2、常用排序算法的时间复杂度和空间复杂度



2-2、数组

由【相同数据类型】组成的【连续内存空间】的数据结构;

通过【下标】访问数组,数组的【下标】都是从0开始;



2-2-1、数组按下标查询快的原因

是因为根据数组第一个下标的地址,可以计算出某个下标的地址,因为数组存放的相同数据类型,所以每个数据的长度是知道的,根据【数组第一个元素的下标地址 + 数据类型长度 * 元素下标】,可以得到元素在内存中存放的具体地址;

数组查询的时间复杂度为O(1),插入和删除的时间复杂度为O(N),N为数组的长度;

2-2-2、数组在Java语言中的应用

  1. Array:Java的数组类;

  2. ArrayList:可变长度的数组列表;

  3. CopyOnWriteArrayList:线程安全的数组列表;



2-3、链表

由【相同数据类型】组成的【不连续】的【内存空间】数据结构;

链表之间可以是不连续的,一个元素中除了存放值还存放下一个元素的内存地址指针。



2-3-1、链表的插入和删除

链表的插入和删除时间复杂度都是O(1),查询的复杂度为O(N),因为只能从头遍历访问;

链表插入一个元素,只需要将前一个元素的地址指针指向要插入的元素,插入元素的地址指针指向原来的元素;

链表删除一个元素也十分简单,只需要将要删除元素的前一个元素的地址指针指向删除元素后面的元素即可。

2-3-2、链表在Java语言中的应用

  1. LinkedList;

2-4、哈希表

哈希表是由【数组】+【链表】组成的数据结构,根据存放元素的值,先计算出Hash值作为数组下标,再根据Key值在遍历链表进行元素访问;

哈希表查询、插入和删除的复杂度都为O(1);

2-4-1、哈希表的结构



2-4-2、哈希表在Java语言中的应用

  1. HashMap

  2. ConcurrentHashMap



2-5、栈

2-5-1、栈的数据结构

【栈】是一个【last-in-first-out(LIFO)】的数据结构,只会在【栈顶】进行操作;



2-5-2、栈在Java中的应用

Java虚拟机栈在执行方法时,是用栈实现,方法执行进入栈底,如果方法还调用其他方法,则把依赖的方法在放入栈中,执行的时候,从栈顶开始执行,将执行结果存入栈中;



2-6、队列

2-6-1、队列的数据结构

队列是一个【FIFO (first-in-first-out)】的数据结构;



2-6-2、队列在Java中的应用

  1. 生产者消费者模式;

  2. Queue、ArrayBlockingQueue、PriorityBlockingQueue;



3、网络通信协议

需要了解网络通信的七层协议与TCP/IP协议的分层,

TCP主要是针对【传输层】的协议;

IP协议针对【网络层】;

3-1、OSI七层模型与TCP/IP四层模型



3-2、TCP与IP协议

3-2-1、IP协议

【网络层】IP协议是的互联网应用根据【IP地址】就能访问目标服务器,请求发起后,到达运营商的交换机,交换机会根据【IP地址】进行路由转发,中间会经过多个转发节点,最后数据到达目标服务器。

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



3-2-2、TCP协议

IP协议是【不可靠】的通信协议,不会建立稳定的通信链路,并不确保数据一定到达。要保证通信的可靠稳定,需要传输层协议TCP;

TCP协议是一种【面向连接的】、【可靠的】、【基于字节流】的【传输层】协议。



TCP作为一个比较基础的通讯协议,有很多重要的机制保证TCP协议的可靠性和强壮性:

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

  • 无错传输,使用校验和检测报文段的错误;

  • 使用确认和计时器来检测和纠正丢包或延时;

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

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



4、数据库架构原理与性能优化

4-1、数据库架构原理

数据库架构主要分为三层

  • 连接层:负责连接处理、授权认证、安全等;

  • 服务层:负责查询解析、分析、优化和缓存等;

  • 存储引擎:负责数据的提取和存储;

数据库整体架构示意图如下



4-1-1、数据库连接

数据库连接基于TCP连接原理实现,主要步骤如下:

  1. TCP建立连接3次握手;

  2. MySQL认证3次握手;

  3. 执行SQL;

  4. 关闭MySQL连接;

  5. 关闭TCP连接(4次挥手);



如果每次和数据库建立连接,会带来以下问题:

  • 网络IO较多;

  • 数据库负载较高;

  • 响应时间变长导致QPS变低;

  • 应用频繁创建和关闭连接,导致对象变多,引擎GC频繁;

  • 在关闭连接后,出现大量TIME_WAIT的TCP状态;



4-1-2、数据库连接池

每次与数据库交互都需要建立连接产生一系列的问题,解决的方法就是使用数据库连接池;

使用连接池技术,是加快数据库操作的重要手段;

同样,使用连接池,也能帮助我们提升系统性能;



连接池的工作原理包含以下三个部分:

  1. 连接池创建

  2. 连接池管理;

  3. 连接池关闭

4-1-2-1、连接池创建

在系统初始化时,连接池会根据系统配置建立,并在池中创建了几个【初始化】连接对象,以便使用时能从连接池中获取。连接池中的连接不能随意创建和关闭,这样避免了连接随意建立和关闭造成的系统开销。



4-1-2-2、连接池管理

当客户请求数据库连接时:

  1. 首先查看连接池中是否有空闲连接,如果存在空闲连接,则将连接分配给客户使用;

  2. 如果没有空闲连接,则查看当前连接数是否已经达到最大连接数,如果没达到就重新创建一个连接给请求的客户;

  3. 如果达到就按设定的最大等待时间进行等待,如果超出最大等待时间,则抛出异常给客户。



当客户释放数据库连接时,先判断该连接的引用次数是否超过了规定值,如果超过就从连接池中删除该连接,否则保留为其他客户服务。



该策略保证了数据库连接的有效复用,避免频繁的建立、释放连接所带来的系统资源开销。



4-1-2-3、连接池关闭

当应用程序退出时,关闭连接池中所有的连接,释放连接池相关的资源,该过程正好与创建相反。

4-1-2-4、Java中常用的数据库连接池

Java中常用的数据库连接池包括:C3P0,DBCP 和 Druid;



4-2、数据库索引

4-2-1、索引的作用(为什么需要索引)

索引的作用就是为了提高数据查询效率,就像根据书的目录一样查询内容;

如果没有索引,当查询一条数据时,需要进行全表扫描,这样大大降低了系统性能,所以建立一个好的索引也是系统性能优化的重要部分;

索引可以帮助我们快速的查询想要的数据,减少查询时间,有助于提高系统吞吐量;

4-2-2、索引使用的数据结构

目前大部分公司都使用MySQL数据库,而MySQL的常用引擎为InnoDB,这是因为【InnoDB】支持事务是一个主要原因,【InnoDB引擎】【索引】的数据结构有以下三类:

  1. B+Tree

  2. 哈希索引

  3. 全文索引



B+Tree

B+Tree是MySQL多数引擎常用且有效的索引类型,构造类似二叉树,能根据键值快速查找数据;支持全值匹配,最左前缀匹配,范围查询等



哈希索引

哈希索引(hash index)基于哈希表(Key-Value)实现,只有【精确匹配】索引所有列的查询才有效;

对于每一行数据,存储引擎都会对所有的索引列计算一个hash code,哈希索引将所有hash code存储在索引中,同时在哈希表中保存指向每个数据行的指针;

适合的应用场景:手机号,身份证等值的全值匹配;



4-2-3、B+树索引

4-2-3-1、B+树

B+树可以看做一颗M阶树,主要有以下特性:

  • 一棵树有M阶(节点【最大】【键值】数量M);

  • 叶子节点(无子节点)和非叶子节点;

  • 非叶子节点有M+1个指针,指向其子节点;

  • 数据按键值存在在【叶子节点】;

  • 键值从左到右,数字从大到小排序,字母按字母表顺序排序;

  • 叶子节点间为双向链表;





4-2-4、聚簇索引

聚集索引(又称聚簇索引),因为 InnoDB存储引擎表示【索引组织表】,表中数据按主键顺序存放。



1、聚簇索引的选择

MySQL通常将【主键】设置为聚簇索引,

如果没有定义主键,则会选择【唯一的】【非空索引】代替;

如果没有这样的索引,会隐式的定义一个主键作为聚簇索引;



2、聚簇索引的优点

  • 可以把相关数据保存在一起;

  • 数据访问更快,因为将索引和数据保存在同一颗B+Tree中,因此聚簇索引中获取数据比从非聚簇索引中查找更快;

  • 使用覆盖索引扫描的查询可以直接使用页节点中的主键值;



3、聚簇索引的缺点

  • 插入速度严重依赖插入顺序;

  • 更新聚簇索引列的代价很高;

  • 基于聚簇索引的表在插入新行,或者聚簇索引列被更新后,需要移动行,而这会导致“页分裂”;当插入页满之后,则会进行分页操作,从而导致表占用更多的空间;



4、聚集索引的特性

  • 每张表主键构成一颗B+树,叶子节点存放整张表的行记录数据;

  • 每张表只有一个聚集索引,因为数据页只能按照一颗B+树进行排序;

  • 聚集索引能够特别快的访问针对【范围值】的查询;

  • 聚集索引的存储不是物理连续的,而是逻辑连续,页之间通过【双向链表】链接;

  • 聚集索引的【排序】查找和【范围】查找速度快。



4-2-5、非聚簇索引

非聚集索引,叶子节点不包含行记录的全部数据,除了包含索引键值外,另外包含就是【聚集索引键】;

当通过非聚集索引查找数据时,InnoDB存储引擎会遍历辅助索引并通过叶级别的指针,获得指向主键索引的主键,然后通过主键索引来找到一个完整的行记录;

这样带来的问题,会增加磁盘IO的次数,具体如何解决参考后续的内容;



4-3、数据库事务

4-3-1、什么是事务

事务会把数据库从一种【一致状态】转换为另一种【一致状态】;

数据库提交工作时,可以确保所有修改都已经保存,要么所有修改都不保存;



4-3-2、事务的特性

事务是访问并更新数据库各种数据项的一个【程序执行单元】。

在事务操作中,要么都做修改,要么都不做。

事务的4大特性(ACID):

  • 原子性(Atomicity):要么全部成功,要么全部失败,不能出现执行一般成功,另一半失败的情况,在MySQL中主要有【Undo Log】实现回滚;

  • 一致性(Consistency):在事务开始之前和事务结束之后,数据库的完整性约束没有被破坏;

  • 隔离性(Isolation):每个读写事务的结果,对其他事务的操作是隔离,主要用【锁】来实现;

  • 持久性(Durability):事务一旦提交,结果必须是持久的。即使发生宕机等故障,数据库也能将数据恢复,主要由【redo log】实现;



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

Albert

关注

还未添加个人签名 2018.08.31 加入

还未添加个人简介

评论

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