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

关注
发布于: 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的限制。
﻿