第八周 - 总结

一、文件性能：

硬盘：

1、机械硬盘：

读取数据：如果数据是连续的，那么磁头只需移动一次，然后按照顺序就能读取相应的数据，速度较快。如果数据是不连续的，每次读取数据只读个几K然后又要移动磁头，速度就比较慢。磁头的移动速度是毫秒级别的。

2、固态硬盘：

读取数据：没有磁头，不需要移动磁头读取数据，速度较快。由存储控制逻辑单元决定将数据放到哪些存储颗粒上进行存储，连续读写也是比随机读写快。

文件存储结构：

1、B+树：

MySQL数据库使用的一种数据存储结构，每一个树的节点是保存在一个磁盘块中的，读取一个节点的数据是连续的，所以读取较快。但是不同的节点是保存在不同的区域中的，一般访问一个数据，是要从根节点到叶子节点访问三个磁盘块的数据，所以还是会要移动磁头，进行随机访问数据，仍需几十毫秒的时间。

2、LSM树：

Log Structured Merge Tree，日志结构合并树。NoSQL常用的一种文件存储结构。是以尽量的连续存储来提高速度的。在内存中会有一个log树，当内存中的log树满了会合并到磁盘上的树。

硬盘系统的管理：

1、文件系统：

是以块为单位来管理硬盘的，每个文件占据若干个块，然后再通过一个文件控制块FCB（这是Linux的，windows叫文件分配表FAB）记录每个文件占用的硬盘块。每个块4K，访问文件的时候，最少要访问一个文件块。

2、Linux Inode文件控制块：

Inode中记录着文件权限、所有者、修改时间和文件大小等文件信息属性，以及文件数据块硬盘地址索引，最多只有12个直接索引（也就是说能记录12 * 4K大小的文件），如果文件大小超过了，一级间接索引表指针会记录一个索引表，索引表会记录更多的文件地址块，二级间接索引表指针会记录一个记录着索引表的索引表地址，还有一个三级间接索引表指针。因此每个Inode最多可以存储12 + 256 + 256 * 256 + 256 * 256 * 256个数据块，也就是不超过70G。

3、RAID磁盘冗余阵列（单台服务器的优化）：

1) RAID 0：将几块磁盘当成一块磁盘，将数据分成几块，同时写入或读取到对应的具体磁盘中，速度就很能提升了。缺点：数据的安全性降低了，当有一块硬盘发生故障时，这个文件就不能用了。

2) RAID 1：将数据同时写到另一块硬盘上，增加冗余，提高了数据的安全性。缺点：性能不高。

3) RAID 10：将RAID1和RAID0结合起来，使用多块硬盘（如4块，两块做RIAD 0实现数据的高性能，两块对这两块硬盘做RAID1实现高可用）。缺点：磁盘利用率不高。

4) RAID 5（业界使用的最广泛）：使用多块硬盘记录数据，前几块组成RAID 0，最后一块硬盘记录前面磁盘数据的校验信息（其实不是所有的校验信息都记录在最后一个磁盘上，而是螺旋式的分散记录在每个磁盘上，因为单独记录在一个磁盘上文件修改都要读写这个磁盘，这个磁盘压力很大，寿命就会很低）。当有一块磁盘损坏了，可以通过校验信息和其它磁盘保存的信息进行反计算，计算（进行异或计算）出来丢失的数据。缺点：两块硬盘坏了就计算不出来原来的数据了。

5) RAID 6：记录两个校验信息，解决RAID5的问题。

分布式文件系统HDFS：

HDFS：将文件分片存储在多个文件服务器上，每个服务器都可以并发的进行文件的读取操作。目标：大文件的存储和计算。FDHS文件块的大小是64M（Linux是4K），写小文件是不划算的。使用数据复制（默认复制3分）实现了高可用。

主要角色：

1、NameNode：相当于Linux文件系统的文件控制块FCB，记录文件的一些重要信息和数据分片的地址。

2、DataNode：具体的数据存储节点。

二、数据结构：

1、算法量度：

1)时间复杂度：执行语句的次数，如O(2^n)表示对数据需要进行2^n次计算。

2)空间复杂度：一个算法在运行过程中临时占用的存储空间的大小量度，如O(n)表示要临时存储n个数据。

2、数据结构：

1)线性表：

数组：内存中存放相同数据类型的一块连续空间，随机访问的时间复杂度是O(1)。

链表

栈：后进先出

队列：先进先出

2) hash表

3) 树：

二叉排序树：左子节点值小于或等于根节点值，右子节点的值大于或等于根节点的值。左右子树也都是二叉排序树。不平衡的二叉排序树会使得二叉排序树退化成链表。

平衡二叉排序树：全部符合二叉排序树，之外还要符合，从任意节点出发，左右子树的深度不超过1。在插入或删除时，需要旋转使得树再次平衡。

红黑排序树：每个节点只能是红色或黑色的；根节点是黑色的，叶子节点都是黑色的NULL空节点；从根节点到叶子节点，不会出现两个连续的红节点；从任意节点出发，到任一的叶子节点这条路径上都有相同的黑节点数量。当增加或删除节点时，需要通过染色和旋转，保持红黑树的定义。

红黑树VS平衡二叉树：

红黑树最多只需经过3次旋转就能重新达到红黑树定义，时间复杂度O(1)。

在大量增删的情况下，红黑树效率更高。

红黑树的平衡性不如平衡二叉树，查找效率要低一些。

4) 跳表：多个链表，（现在有些程序用来替代红黑树）。

三、常用算法：

1、穷举算法：

2、递归算法：自己调用自己。

3、贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是不从整体上考虑，算法得到的是在某种意义上的局部最优解。得到的可能不是最好的答案。

贪心算法改进：Djkstra最短路径算法：

从起点出发，找出最便宜的节点，更新该节点的邻居节点开销，检查是否有前往他们的更便宜的路径，比之前的小就修改并加入进来，继续以上办法，最终得到一个起点到每一个节点的花费表。

4、动态规划：将所求解的目标值在某几个维度上展开，将一个大问题拆解成为若干小问题，从小问题的最优解，寻找大问题的最优解。（很多动态规划都可以展成一个二维表格）



四、网络通信优化：

1、Web 请求的一次网络通信过程：

客户端（请求域名）-> DNS服务器（解析域名，返回IP地址）->客户端（请求IP地址）-> CDN ->负载均衡服务器->反向代理服务器（提供前端和一些静态内容缓存）->负载均衡服务器->网关服务器->微服务服务->数据库或缓存。

2、OSI七层模型和TCP/IP四层模型：

1) OIS模型：

会话层、表示层、应用层：都是需要应用程序自己处理的。

传输层：提供端对端的接口，进程间的通信，端口。

网络层：以数据包传输。

数据链路层：以数据帧传输。

物理层：以0/1传输。

2) TCP/IP模型：

应用层：HTTP、HTTPS。

传输层（TCP）：UDP、TCP协议，最重要的是要定义好端口号是什么。

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

使用序号：对TCP报文进行排序和检测重复数据，

无错传输：使用校验和检测报文段的错误，

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

流量控制：

拥塞控制：

丢失包的重传：

3次握手4次挥手：

网络层（IP）：通过IP地址进行数据包的路由和目标选择。

使得互联网应用根据IP地址就能访问到目标服务器，请求到达运营商的交换机后，交换机会根据这个IP地址进行转发，可能会经过很多个转发节点，最后到达目标服务器。IP协议是一个不可靠的通信协议。不会确保数据一定送达。

链路层：网卡的MAC地址处理，并进行数据帧的封装。

3、网络编程：

1) BIO：阻塞式IO通信：

一个服务器实现高并发处理能力，要创建多个线程对每个socket处理。当请求还没获得数据的时候，线程就会一直阻塞着等待请求获得数据。

但是线程数是有限的，线程资源是比较宝贵的。

当一个请求的数据包到达了网卡，网卡会调用自己的解析协议，解析链路层的数据（分析MAC地址），通知CPU拷贝数据到对应的Socket接收缓冲区内（如果接收缓冲区数据满了，就会通知发送方发送得慢一点），数据拷贝好之后，通知阻塞在该Socket缓存区上的线程区处理数据。线程调用Socket得InputStream或者OutputStream进行read或者write的时候，如果数据还没准备好或者Socket的缓冲区满了，线程就会被阻塞在这里。

2) NIO：非阻塞式IO通信：

IO操作立即返回，发起线程不会阻塞等待。

Read操作：

Write操作：