写点什么

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

用户头像
Anyou Liu
关注
发布于: 2020 年 11 月 14 日

本周学习了文件与硬盘I/O、常用的数据结构与算法、网络通信协议、非阻塞网络I/O

一、文件与硬盘I/O

机械硬盘

机械硬盘是通过马达驱动磁头臂,带动磁头到指定的磁盘位置访问数据。由于每次访问数据都需要移动磁头臂,如果要访问的数据是存储在连续的磁盘空间上,那么性能比较高,如果要访问的数据不是存储在连续的磁盘空间上,那么性能比较低。

固态硬盘

固态硬盘叫做SSD,数据存储在可持久记忆的硅晶体上,可以像内存一样快速随机访问。SSD相比机械硬盘具有更好的性能,但是可靠性比不上机械硬盘。

B+树

B+树是一种专门针对磁盘存储而优化的N叉排序树,以树节点为单位存储在磁盘中,从根开始查找所需数据所在的节点编号和磁盘位置,将其加载到内存中然后继续查找,直到找到所需的数据。关系型数据库的索引一般使用B+树。

LSM树

LSM树可以看作是一个N阶合并树。数据写操作都在内存中进行,并且都会创建一个新记录,这些数据在内存中仍然还是一棵排序树,当数据量超过设定的内存阈值后,会将这棵排序树和磁盘上最新的排序树合并。当这棵排序树的数据量也超过设定阈值后,和磁盘上下一级的排序树合并。合并过程中,会用最新更新的数据覆盖旧的数据。

在LSM树上进行一次数据更新不需要磁盘访问,在内存即可完成,速度远快于B+树。当数据访问以写操作为主,而读操作则集中在最近写入的数据上时,使用LSM树可以极大程度地减少磁盘的访问次数,加快访问速度。

文件控制块

文件系统将硬盘空间以块为单位进行划分,每个文件占据若干个块,然后再通过一个文件控制块FCB记录每个文件占据的硬盘数据块。

Linux Inode文件控制块记录着文件权限、所有者、修改时间和文件大小等信息,以及文件数据块硬盘地址索引。总共有15个硬盘地址索引,包括12个直接索引、1个一级索引、1个二级索引、1个三级索引,以数据块大小是4K为例,单个文件不超过70G。

RAID

RAID是指磁盘冗余阵列,主要是为了提高磁盘的访问速度,增强磁盘的可用性和容错能力,通过RAID技术,可以在多块磁盘上并发的进行读写操作。

一般实践中使用RAID5比较多,因为综合来看,RAID5访问速度比较快,可靠性比较高,磁盘利用率也比较高。

HDFS

HDFS是指Hadoop分布式文件系统,系统在整个存储集群的多台服务器上进行数据并发读写和备份。HDFS以块为单位管理文件内容,数据块默认大小是64MB,HDFS将DataNode上的磁盘空间分成N个这样的块。一个文件被分割成若干个块,当应用程序写文件时,每写完一个Block时,HDFS会自动将其复制到另外的2台机器上,保证每个数据块有3个副本。所以,即使有2台服务器宕机,数据依然可以访问。

HDFS集群中的节点可以分为NameNode和DataNode,NameNode只有单个实例,提供元数据,保存了数据块和对应的DataNode节点信息。DataNode上存储了具体的文件。

二、常用的数据结构与算法

时间复杂度与空间复杂度

时间复杂度是指算法需要执行语句的次数,一般有O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(n!)

空间复杂度是指算法需要占用存储空间的大小

数组

数组是内存中一段连续的存储空间,数组中存放的必须是相同的数据类型,数组访问的时间复杂度是O(1)

链表

链表在内存中可以是不连续的存储空间,链表中的元素通过指针来指向它的下一个元素,链表查找的时间复杂度是O(1),但是增加和删除比数组快,链表增删时只需要修改指针的值就可以了。

Hash表

Hash表的底层存储是数组,Hash表的Key根据散列函数得到Hash值,然后对数组长度取模运算,得到数组的下标,然后把Value存储进去,如果多个Key对应通过一个数组下标,那么Value会以链表的方式存储。

跟数组不一样的是,栈的增删只能在栈顶进行,增加一个元素,叫做入栈,删除一个元素,叫做出栈,栈的操作满足后进先出。

队列

队列的增加元素,只能在队尾,队列的删除元素,只能在对头,增加一个元素,叫做入队,删除一个元素,叫做出队,队列的操作满足先进先出。

类似于现实中的树木一样,树有根节点,根节点下面包含一个或者多个子节点,子节点下面还可以延伸一个或者多个孙子节点,通过这样层层扩展,形成一个树结构。

二叉排序树

左子树上所有节点的值均小于或者等于它的根节点的值。

右子树上所有节点的值均大于或者等于它的根节点的值。

左、右子树也分别为二叉排序树。

平衡二叉树

从任何一个节点出发,左右子树深度之差的绝对值不超过1。

左右子树仍然是平衡二叉树。

在增加或者删除节点时,需要旋转二叉树,使整棵树依然保持平衡。

红黑树

虽然平衡二叉树的平衡性好,查找效率高,但是增加和删除节点时,需要进行多次旋转来平衡,比较不容易实现。所以人们定义了红黑树来达到近似平衡二叉树的性能,但是又比较容易实现的一种树的结构

  • 每个节点只有2种颜色:红色和黑色

  • 根节点是黑色

  • 每个叶子节点(NIL)都是黑色的空节点

  • 从根节点到叶子节点,不会出现2个连续的红色节点

  • 从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点。

相比平衡二叉树,红黑树最多只需3次旋转就可以重新达到平衡,时间复杂度是O(1),在大量增删的情况下,红黑树的效率更高。

跳表

跳表也实现了和红黑树一样的查找性能和增删时间复杂度,但是比红黑树更好实现,就是把所有的元素形成一个链表,然后把链表中每隔N个节点的元素再往上升形成一个上一级的链表,这样一层一层的往上垒,最终形成一个具有M层链表的数据结构。跳表查找时,从最上面一层的链表开始,然后再往下一层一层的查找,查找的性能也是O(log n),增删操作的时间复杂度是O(1),但是跳表比较占据空间,不过在现在单机资源配置很高的情况下,这个问题就不那么重要了。

常用算法

常用算法有穷举算法、递归算法、贪心算法、动态规划、遗传算法

  • 穷举算法是暴力算法,比如告诉你密码有6位,由字母和数字组成,那么可能的组合就有62^6,遍历这么多次,密码也就破解了。穷举算法适合问题规模不大的情况

  • 比如快速排序就用到了递归算法

  • 贪心算法有著名的背包问题:一个小偷去商场偷东西,怎么才能收益最大化。

  • 动态规划是通过将一个大问题拆分成若干个小问题,然后求小问题的最优解,从而找到大问题的最优解

  • 遗传算法通过模拟达尔文进化论的自然选择和遗传学理论,来尝试找到问题的最优解。一般而言,通过几轮筛选过程,遗传算法求出问题的解,这个解虽然不是最优解,但是也是一个相对比较好的解。遗传算法适用以比较低的代价求出相对比较好的解的场景。

三、网络通信协议

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

OSI七层模型包括物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。

TCP/IP四层模型包括网络访问层、网络互联层、传输层、应用层。

物理层

物理层负责数据的物理传输,比如光纤、电缆、无线等线路。如何在各种不同的设备上传输和处理相同的二进制数据,是物理层需要解决的问题。

数据链路层

数据链路层通过将数据封装成数据帧交给物理层传输。数据帧里面包含发送者和接受者的MAC地址。MAC地址是网卡的设备标识符,是唯一的,数据帧被传输到MAC地址对应的机器上。

数据链路负载均衡就是利用了MAC地址进行负载均衡,把负载均衡服务器和应用服务器的IP地址设置成同一个,负载均衡服务器通过修改接收数据的MAC地址,把数据发送到对应的应用服务器。

网络层

网络层的数据需要发送给数据链路层处理,数据包里面包含了发送者和接受者的IP地址。通过在负载均衡服务器上修改数据包的目标IP地址,可以实现IP负载均衡。

传输层

IP协议不是一个可靠的通信协议,不会建立稳定的通信链路,并不会确保数据一定送达。要保证通信的稳定可靠,需要传输层协议TCP。TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP建立连接有3次握手过程,关闭连接的时候有4次挥手过程。

应用层

应用层的协议主要是HTTP协议,关于HTTP请求,有7种方法

  • Get:只读请求

  • Head:和Get方法一样,不过只返回响应头

  • Post:提交请求

  • Put:上传请求。

  • Delete:删除URL标识的资源

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

  • Options:请求服务器返回支持的所有Http请求方法,测试服务器是否正常

四、非阻塞网络I/O

一般服务器和客户端通信时,服务器端会开启一个线程监听客户端发送的数据,如果有多个客户端都要连接服务器,那么就要开启多个线程,由于线程是系统中比较昂贵的资源,可以建立线程池来管理所有的客户端的连接。

阻塞IO(Blocking I/O)

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

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

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

非阻塞read操作:

  • Socket接收缓冲区有数据,读n个数据

  • Socket接收缓冲区没数据,则返回失败

非阻塞write操作:

  • Socket发送缓冲区满,返回失败

  • Socket发送缓冲区不满,写n个数据

Java NIO

在Java NIO中,主要利用Selector实现多路复用。Selector是基于事件驱动实现的,我们可以在Selector中注册accept、read监听事件,Selector会不断轮询注册在其上的Channel,如果某个Channel上面发生监听事件,这个Channel就处于就绪状态,然后进行I/O操作。

一个线程使用一个Selector,通过轮询的方式,可以监听多个Channel上的事件。注册Channel时可以设置该通道为非阻塞,那么当没有I/O操作时,线程就不会一直等待了,从而避免发生阻塞。

目前操作系统的I/O多路复用都使用了epoll,相比传统的select机制,epoll没有最大连接句柄1024的限制。



用户头像

Anyou Liu

关注

还未添加个人签名 2019.05.24 加入

还未添加个人简介

评论

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