架构师训练营第八周总结

文件与硬盘I/O



B+树、LSM树

LSM树和B+树的差异主要在于读性能和写性能进行权衡，在牺牲的同时寻找其余补救方案。



B+树

每个树节点只存放键值，不存放数值，而由叶子节点存放数值。这样会使树节点的度比较大，而树的高度就比较低，从而有利于提高查询效率。

叶子节点存放数值，并按照值大小顺序排序，且带指向相邻节点的指针，以便高效地进行区间数据查询；并且所有叶子节点与根节点的距离相同，因此任何查询的效率都很相似。

与二叉树不同， B+树的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比较小的代价实现自平衡。

缺点在于随着数据插入的不断发生，叶子节点会慢慢分裂——这可能会导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的磁盘 IO，以致严重影响到性能。

LSM树

同时使用了两部分类树的数据结构来存储数据，并同时提供查询。其中一部分数据结构（ C0树）存在于内存缓存（通常叫作 memtable）中，负责接受新的数据插入更新以及读请求，并直接在内存中对数据进行排序；另一部分数据结构（ C1树）存在于硬盘上 (这部分通常叫作 sstable)，它们是由存在于内存缓存中的 C0树冲写到磁盘而成的，主要负责提供读操作，特点是有序且不可被更改。



RAID

RAID0 具有低成本、高读写性能、 100% 的高存储空间利用率等优点，但是它不提供数据冗余保护，一旦数据损坏，将无法恢复

RAID1 在数据写入时，响应时间会有所影响，但是读数据的时候没有影响。 RAID1 提供了最佳的数据保护，一旦工作磁盘发生故障，系统自动从镜像磁盘读取数据，不会影响用户工作。

RAID5 兼顾存储性能、数据安全和存储成本等各方面因素，它可以理解为 RAID0 和 RAID1 的折中方案，是目前综合性能最佳的数据保护解决方案。

RAID10 RAID1+RAID0



分布式文件系统HDFS

Namenode：记录元数据信息

Datanode：存储数据块

数据块以多副本的方式保证可靠



数据结构与算法

常用算法



穷举算法

最简单算法，依赖计算机的强大计算能力穷尽每一种可能的情况。穷举算法效率不高，但是适合一些没有明显规律可循的场合。

递归算法

如果其中每一步都要用到前一步或前几步的结果，称为递归。在计算机算法中，则是方法本身调用自己方法的过程，它可将一个大问题一步步的化为小问题，直到可以直接求解计算

贪心算法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。

动态规划

它通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。



网络通信协议

OSI定义了网络互连的七层框架（物理层、数据链路层、网络层、传输层、会话层、表示层、应用层），即ISO开放互连系统参考模型。





OSI七层和TCP/IP的区别



• TCP/IP他是一个协议簇；而OSI（开放系统互联）则是一个模型，且TCP/IP的开发时间在OSI之前。

• TCP/IP是由一些交互性的模块做成的分层次的协议，其中每个模块提供特定的功能；OSi则指定了哪个功能是属于哪一层的。

• TCP/IP是五层结构，而OSI是七层结构。OSI的最高三层在TCP中用应用层表示。



经典图





TCP协议

三次握手





四次握手





应用层HTTP协议

7种方法： GET、POST、HEAD、PUT、DELETE、OPTIONS、TRACE

5种状态：

1xx -- 请求已被服务器接收，继续处理

2xx -- 请求已成功被服务器接收、理解、并接受

3xx -- 需要后续操作才能完成这一请求

4xx -- 请求含有词法错误或者无法被执行

5xx -- 服务器在处理某个正确请求时发生错误