本篇博文主要介绍2021秋招时汇总的一些虾皮后端面试过程中可能遇到的一些问题。
数据结构相关 1. 介绍一下哈希表
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。
常见的散列函数有:
取关键字或关键字的某个线性函数值为散列地址
当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址
择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不等的场合
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key % p, p <= m
2. 怎么解决哈希冲突
开放寻址法 -- 当发生哈希冲突后,就去寻找下一个空的散列地址,只要散列表足够大,这个空的位置一定能找到 线性探测: 此时这个位置已经存在数,那么就继续对下一个位置进行探测,当到表尾时还没有空位置,此时就返回表头继续找寻空位置
二次探测: Hi=(H(key) + di) MOD m, 每次查找的是距离上一个为 i^2 个距离的位置
当散列表元素太多(即装填因子 α 太大)时,查找效率会下降;当装填因子过大时,解决的方法是加倍扩大散列表,这个过程叫做“再散列(Rehashing)”。Hash 表中每次发现 loadFactor==1 时,就开辟一个原来桶数组的两倍空间(称为新桶数组),然后把原来的桶数组中元素全部转移过来到新的桶数组中。注意这里转移是需要元素一个个重新哈希到新桶中的。实用最大装填因子一般取 0.5 <= α<= 0.85
当发生冲突时,该位置上的数据会用链表链起来,当表中的某些位置没有结点时,该位置就为 NULL
公共溢出区
为所有冲突的关键字记录建立一个公共的溢出区来存放。在查找时,对给定关键字通过散列函数计算出散列地址后,先与基本表的相应位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表进行顺序查找。如果相对于基本表而言,在有冲突的数据很少的情况下,公共溢出区的结构对查找性能来说还是非常高的。 3. 哈希表的扩容
假设以数组形式存放哈希表,当数组中元素过多时,可能会导致接下来存放数据时多次遇到冲突且寻找数据时也会遇到同样的问题。这时哈希表引入了一个装填因子(元素个数/数组长度),当装填因子越大,表明数组可能存在的冲突越多,越需要扩容,实用的装填因子大小为0.5-0.85。当装填因子过大时,就需要考虑为哈希表进行扩容,一般来说,扩容选择二倍的当前容量,一方面可以快速的进行位运算,另一方面能够减少再哈希的冲突。需要注意的是,扩容的时候,原哈希表中的元素需要重新进行哈希。显然,再哈希是个非常耗时的问题,引入了渐进式rehash。以下是哈希表渐进式 rehash 的详细步骤:
为 ht[1] 分配空间, 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
*在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始。 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一。 随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。 4. 数组和链表的区别
数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况,即数组的大小一旦定义就不能改变。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费;链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删 除数据项时,需要移动其它数据项)。 (静态)数组从栈中分配空间(用 new 创建的在堆中), 对于程序员方便快速,但是自由度小;链表从堆中分配空间, 自由度大但是申请管理比较麻烦。 数组在内存中是连续存储的,因此,可以利用下标索引进行随机访问;链表是链式存储结构,在访问元素的时候只能通过线性的方式由前到后顺序访问,所以访问效率比数组要低。 5. 二叉树、二叉搜索树、平衡二叉树、红黑树
二叉树特点是每个结点最多只能有两棵子树,且有左右之分。 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。 平衡二叉树(AVL)。它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多 红黑树。一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此,红黑树是一种弱平衡二叉树(由于是弱平衡,可以看到,在相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,我们就用红黑树。
性质:1. 每个节点非红即黑 2. 根节点是黑的; 3. 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的; 4. 如果一个节点是红的,那么它的两儿子都是黑的; 5. 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点; 6. 每条路径都包含相同的黑节点。 平衡二叉树和红黑树对比。
结构对比: AVL 的结构高度平衡,RBT 的结构基本平衡。平衡度 AVL > RBT。
查找对比: AVL 查找时间复杂度最好,最坏情况都是 O(logN)。RBT 查找时间复杂度最好为 O(logN),最坏情况下比 AVL 略差。
插入删除对比: 1. AVL 的插入和删除结点很容易造成树结构的不平衡,而 RBT 的平衡度要求较低。因此在大量数据插入的情况下,RBT 需要通过旋转变色操作来重新达到平
衡的频度要小于 AVL。2. 如果需要平衡处理时,RBT 比 AVL 多一种变色操作,而且变色的时间复杂度在 O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。3. 当插入一个结点引起了树的不平衡,AVL 和 RBT 都最多需要 2 次旋转操作。但删除一个结点引起不平衡后,AVL 最多需要 logN 次旋转操作,而 RBT 最多只需要 3 次。因此两者插入一个结点的代价差不多,但删除一个结点的代价 RBT要低一些。4. AVL 和 RBT 的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与 O(logN) 成正比的。
总体评价:大量数据实践证明,RBT 的总体统计性能要好于平衡二叉树。
红黑树详解 6. B树、B+树
B 树:
一种二叉搜索树。 除根节点外的所有非叶节点至少含有(M/2(向上取整)-1)个关键字,每个节点最多有M-1个关键字,并且以升序排列。所以M阶B树的除根节点外的所有非叶节点的关键字取值区间为[M/2-1(向上取整),M-1]。 每个叶节点最多有M-1个关键字。 B+树:
有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点(b树是每个关键字都保存数据)。 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接(叶子节点组成一个链表)。 所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。 通常在b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。 同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。 B树与B+树的区别:
B树每个节点都存储数据,所有节点组成这棵树。B+树只有叶子节点存储数据(B+数中有两个头指针:一个指向根节点,另一个指向关键字最小的叶节点),叶子节点包含了这棵树的所有数据,所有的叶子结点使用链表相连,便于区间查找和遍历,所有非叶节点起到索引作用。 B树中叶节点包含的关键字和其他节点包含的关键字是不重复的,B+树的索引项只包含对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。 B树中每个节点(非根节点)关键字个数的范围为m/2(向上取整)-1,m-1 ,并且具有n个关键字的节点包含(n+1)棵子树。B+树中每个节点(非根节点)关键字个数的范围为m/2(向上取整),m ,具有n个关键字的节点包含(n)棵子树。 B+树中查找,无论查找是否成功,每次都是一条从根节点到叶节点的路径。 B树的优点:
B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。 B+树的优点:
所有的叶子结点使用链表相连,便于区间查找和遍历。B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。 b+树的中间节点不保存数据,能容纳更多节点元素。 B树与B+树的共同优点:
考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,m的大小取决于磁盘页的大小。 B树和B+树简介
数据库相关 1. ACID
原子性:指事务是一个不可再分割的工作单位,事务中的操作要么都发生,要么都不发生。事务在执行过程中发生错误,会被回滚(Rollback)到事务开始前的状态,就像这个事务从来没有执行过一样
一致性:指事务使得系统从一个一致的状态转换到另一个一致状态。这是说数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性
隔离性:多个事务并发访问时,事务之间是隔离的,一个事务不应该影响其它事务运行效果。这指的是在并发环境中,当不同的事务同时操纵相同的数据时,每个事务都有各自的完整数据空间。由并发事务所做的修改必须与任何其他并发事务所做的修改隔离。
持久性:意味着在事务完成以后,该事务所对数据库所作的更改便持久的保存在数据库之中,并不会被回滚。即使出现了任何事故比如断电等,事务一旦提交,则持久化保存在数据库中。
2. 四种隔离级别以及 MySQL 的默认隔离级别
READ UNCIMMITTED(读未提交) 事务中的修改,即使没有提交,其他事务也可以看得到。会出现脏读现象
READ COMMITTED(读提交)大多数数据库系统的默认隔离级别是 READ COMMITTED(mySQL 不是),这种隔离级别就是一个事务的开始,只能看到已经完成的事务的结果,正在执行的,是无法被其他事务看到的。这种级别会出现读取旧数据的现象
REPEATABLE READ(可重复读)REPEATABLE READ 解决了脏读的问题,该级别保证了每行的记录的结果是一致的,也就是上面说的读了旧数据的问题,但是却无法解决另一个问题,幻行
SERIALIZABLE(可串行化)SERIALIZABLE 是最高的隔离级别,它通过强制事务串行执行(注意是串行),避免了前面的幻读情况,由于他大量加上锁,导致大量的请求超时,因此性能会比较底下,再特别需要数据一致性且并发量不需要那么大的时候才可能考虑这个隔离级别。
MYSQL的默认隔离级别是可重复读级别。
3. MYSQL怎么实现多版本(MVCC)的
详细
MVCC就是为了实现读-写冲突不加锁,而这个读指的就是快照读, 而非当前读,当前读实际上是一种加锁的操作,是悲观锁的实现。
在Mysql中进行数据操作时会将操作的相反命令写入undo log,根据各种策略读取时非阻塞就是MVCC,undo log中的行就是MVCC中的多版本。一般认为MVCC有下面几个特点
每行数据都存在一个版本,每次数据更新时都更新该版本 修改时Copy出当前版本随意修改,个事务之间无干扰 保存时比较版本号,如果成功(commit),则覆盖原记录;失败则放弃copy(rollback) Innodb的实现方式是:
事务以排他锁的形式修改原始数据 把修改前的数据存放于undo log,通过回滚指针与主数据关联 修改成功(commit)啥都不做,失败则恢复undo log中的数据(rollback) 4. 复合索引
索引有两个特征,即唯一性索引和复合索引。唯一性索引保证在索引列中的全部数据是唯一的,不会包含冗余数据。复合索引就是一个索引创建在两个列或者多个列上,搜索时需要两个或者多个索引列作为一个关键值。
创建索引
key index_name (attr1, attr2, ...); # 联合索引 key index_name (attr); # 唯一索引
5. 聚簇索引和非聚簇索引
聚簇索引的数据的物理存放顺序与索引顺序是一致的,即:只要索引是相邻的,那么对应的数据一定也是相邻地存放在磁盘上的。
在聚簇索引下,数据在物理上按顺序排在数据页上,重复值也排在一起,因而在那些包含范围检查(between、<、<=、>、>=)或使用group by或orderby的查询时,一旦找到具有范围中第一个键值的行,具有后续索引值的行保证物理上毗连在一起而不必进一步搜索,避免了大范围扫描,可以大大提高查询速度。
非聚簇索引,叶级页指向表中的记录,记录的物理顺序与逻辑顺序没有必然的联系。
每个表可以有250个索引,其中至多有一个聚簇索引。
非聚簇索引需要大量的硬盘空间和内存。另外,虽然非聚簇索引可以提高从表中取数据的速度,它也会降低向表中插入和更新数据的速度。每当你改变了一个建立了非聚簇索引的表中的数据时,必须同时更新索引。
6. MyISAM和InnoDB差别
Innodb 引擎提供了对数据库 ACID 事务的支持,并且实现了 SQL 标准的四种隔离级别。该引擎还提供了行级锁和外键约束,它的设计目标是处理大容量数据库系统,它本身其实就是基于 MySQL 后台的完整数据库系统,MySQL运行时 Innodb 会在内存中建立缓冲池,用于缓冲数据和索引。但是该引擎不支持 FULLTEXT类型的索引,而且它没有保存表的行数,当 SELECT COUNT(*) FROM TABLE 时需要扫描全表。当需要使用数据库事务时,该引擎当然是首选。由于锁的粒度更小,写操作不会锁定全表,所以在并发较高时,使用 Innodb 引擎会提升效率。但是使用行级锁也不是绝对的,如果在执行一个 SQL 语句时 MySQL 不能确定要扫描的范围,InnoDB 表同样会锁全表。 MyIASM 是 MySQL 默认的引擎,但是它没有提供对数据库事务的支持,也不支持行级锁和外键,因此当 INSERT(插入)或 UPDATE(更新)数据时即写操作需要锁定整个表,效率便会低一些。不过和 Innodb 不同,MyIASM 中存储了表的行数,于是 SELECT COUNT(*) FROM TABLE 时只需要直接读取已经保存好的值而不需要进行全表扫描。如果表的读操作远远多于写操作且不需要数据库事务的支持,那么 MyIASM 也是很好的选择。 大尺寸的数据集趋向于选择 InnoDB 引擎,因为它支持事务处理和故障恢复。数据库的大小决定了故障恢复的时间长短,InnoDB 可以利用事务日志进行数据恢复,这会比较快。主键查询在 InnoDB 引擎下也会相当快,不过需要注意的是如果主键太长也会导致性能问题。大批的 INSERT 语句(在每个 INSERT 语句中写入多行,批量插入)在 MyISAM 下会快一些,但是 UPDATE 语句在 InnoDB 下则会更快一些,尤其是在并发量大的时候。 7. Mysql 的 redo和undo
Undo日志记录某数据被修改前的值,可以用来在事务失败时进行回滚;Redo日志记录某数据块被修改后的值,可以用来恢复未写入data file的已成功事务更新的数据。
redo log是重做日志,提供前滚操作,undo log是回滚日志,提供回滚操作
undo log不是redo log的逆向过程,其实它们都算是用来恢复的日志:
redo log通常是物理日志,记录的是数据页的物理修改,而不是某一行或某几行修改成怎样怎样,它用来恢复提交后的物理数据页(恢复数据页,且只能恢复到最后一次提交的位置)。undo用来回滚行记录到某个版本。undo log一般是逻辑日志,根据每行记录进行记录。
数据库进行任何写入操作的时候都是要先写日志的,同样的道理,我们在执行事务的时候数据库首先会记录下这个事务的 redo 操作日志,然后才开始真正操作数据库,在操作之前首先会把日志文件写入磁盘,那么当突然断电的时候,即使操作没有完成,在重新启动数据库时候,数据库会根据当前数据的情况进行 undo 回滚或者是 redo 前滚,这样就保证了数据的强一致性。
8. MySQL主从同步有哪些策略?insert到master是等同步完成再响应还是?
详细
MySQL主从复制的基础是主服务器对数据库修改记录二进制日志,从服务器通过主服务器的二进制日志自动执行更新。一句话表示就是,主数据库做什么,从数据库就跟着做什么。
mysql复制的类型:
基于语句的复制 :主库把sql语句写入到bin log中,完成复制 基于行数据的复制:主库把每一行数据变化的信息作为事件,写入到bin log,完成复制 混合复制:上面两个结合体,默认用语句复制,出问题时候自动切换成行数据复制 和上面相对应的日志格式也有三种:STATEMENT,ROW,MIXED STATEMENT模式(SBR): 每一条会修改数据的sql语句会记录到binlog中。优点是并不需要记录每一条sql语句和每一行的数据变化,减少了binlog日志量,节约IO,提高性能。缺点是在某些情况下会导致master-slave中的数据不一致(如sleep()函数,last_insert_id(),以及user-defined functions(udf)等会出现问题) ROW模式(RBR): 不记录每条sql语句的上下文信息,仅需记录哪条数据被修改了,修改成什么样了。而且不会出现某些特定情况下的存储过程、或function、或trigger的调用和触发无法被正确复制的问题。缺点是会产生大量的日志,尤其是alter table的时候会让日志暴涨。 MIXED模式(MBR)以上两种模式的混合使用,一般的复制使用STATEMENT模式保存binlog,对于STATEMENT模式无法复制的操作使用ROW模式保存binlog,MySQL会根据执行的SQL语句选择日志保存方式。 主从复制工作原理剖析:
Master 数据库只要发生变化,立马记录到Binary log 日志文件中 Slave数据库启动一个I/O thread连接Master数据库,请求Master变化的二进制日志 Slave I/O获取到的二进制日志,保存到自己的Relay log 日志文件中 Slave 有一个 SQL thread定时检查Realy log是否变化,有变化那么就更新数据 解决的问题有:
实现服务器负载均衡: 可以通过在主服务器和从服务器之间切分处理客户查询的负荷,从而得到更好的客户响应时间 通过复制实现数据的异地备份 提高数据库系统的可用性: 当主服务器出现问题时,数据库管理员可以马上让从服务器作为主服务器,用来数据的更新与查询服务 9. 慢查询优化
优化数据库结构 分解关联查询: 很多高性能的应用都会对关联查询进行分解,就是可以对每一个表进行一次单表查询,然后将查询结果在应用程序中进行关联,很多场景下这样会更高效。 增加索引 建立视图 优化查询语句 添加存储过程 冗余保存数据 10. 主键索引和唯一索引的区别
在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访
问。 主键索引不仅仅具有索引的特征,还包含着主键约束,如不为空,值唯一的特征 主键可以被其他表引用为外键,而唯一索引不能 一个表最多只能创建一个主键,但可以创建多个唯一索引 11. Innodb 自增主键
InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。
12. 忘了写主键索引,但是已经有几万条数据,该怎么优化
将数据导出,添加索引,导入数据
13. innodb和myism对count的支持?为什么innodb不像myism存储记录总条数
因为MyISAM会保存表的具体行数,MyISAM只要简单地读出保存好的行数即可。然而,InnoDB存储引擎不会保存表的具体行数,因此,在InnoDB存储引擎中,InnoDB要扫描一遍整个表来计算有多少行。
InnoDB的事务特性,在同一时刻表中的行数对于不同的事务而言是不一样的,因此count统计会计算对于当前事务而言可以统计到的行数,而不是将总行数储存起来方便快速查询。
14. mysql的存储引擎有哪些?索引数据结构有哪些?
InnoDB存储引擎 MyISAM存储引擎 MEMORY存储引擎 MEMORY存储引擎将表中的数据存储到内存中,为查询和引用其他表数据提供快速访问。
Archive存储引擎 如果只有INSERT和SELECT操作,可以选择Archive,Archive支持高并发的插入操作,但是本身不是事务安全的。Archive非常适合存储归档数据,如记录日志信息可以使用Archive
计算机网络 1. 介绍一下 OSI
OSI七层网络模型
物理层:规定通信设备的机械的、电气的、功能的和过程的特性,用以建立、维护和拆除物理链路连接。在这一层,数据的单位称为比特(bit)。属于物理层定义的典型规范代表包括:EIA/TIA RS-232、EIA/TIA RS-449、V.35、RJ-45 等 数据链路层:在物理层提供比特流服务的基础上,建立相邻结点之间的数据链路,通过差
错控制提供数据帧(Frame)在信道上无差错的传输,并进行各电路上的动作系列。数据链路层在不可靠的物理介质上提供可靠的传输。该层的作用包括:物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。在这一层,数据的单位称为帧(frame)。数据链路层协议的代表包括:SDLC、HDLC、PPP、STP、帧中继等。 网络层:在 计算机网络中进行通信的两个计算机之间可能会经过很多个数据链路,也可能还要经过很多通信子网。网络层的任务就是选择合适的网间路由和交换结点,确保数据及时传送。网络层将数据链路层提供的帧组成数据包,包中封装有网络层包头,其中含有逻辑地址信息- -源站点和目的站点地址的网络地址。IP 是第 3 层问题的一部分,此外还有一些路由协议和地址解析协议(ARP)。有关路由的一切事情都在这第 3 层处理。地址解析和路由是 3 层的重要目的。网络层还可以实现拥塞控制、网际互连等功能。在这一层,数据的单位称为数据包(packet)。网络层协议的代表包括:IP、IPX、RIP、OSPF 等。 传输层:第 4 层的数据单元也称作数据包(packets)。但是,当你谈论 TCP 等具体的协议时又有特殊的叫法,TCP 的数据单元称为段 (segments)而 UDP 协议的数据单元称为“数据报(datagrams)”。这个层负责获取全部信息,因此,它必须跟踪数据单元碎片、乱序到达的数据包和其它在传输过程中可能发生的危险。第 4 层为上层提供端到端(最终用户到最终用户)的透明的、可靠的数据传输服务。所谓透明的传输是指在通信过程中 传输层对上层屏蔽了通信传输系统的具体细节。传输层协议的代表包括:TCP、UDP、SPX 等。 会话层:在会话层及以上的高层次中,数据传送的单位不再另外命名,而是统称为报文。会话层不参与具体的传输,它提供包括访问验证和会话管理在内的建立和维护应用之间通信的机制。如服务器验证用户登录便是由会话层完成的。 表示层:这一层主要解决拥护信息的语法表示问题。它将欲交换的数据从适合于某一用户的抽象语法,转换为适合于 OSI 系统内部使用的传送语法。即提供格式化的表示和转换数据服务。数据的压缩和解压缩, 加密和解密等工作都由表示层负责。 应用层:为操作系统或网络应用程序提供访问网络服务的接口。应用层协议的代表包括:Telnet、FTP、HTTP、SNMP 等 2. 输入网址到页面渲染的过程
详细
浏览器构建HTTP Request请求 网络传输 服务器构建HTTP Response 响应 网络传输 浏览器渲染页面 DNS解析URL地址、生成HTTP请求报文、构建TCP连接、使用IP协议选择传输路线、数据链路层保证数据的可靠传输、物理层将数据转换成电子、光学或微波信号进行传输
3. 介绍一下不对称加密以及对称加密
对称加密是最快速、最简单的一种加密方式,加密(encryption)与解密(decryption)用的是同样的密钥(secret key)。对称加密的一大缺点是密钥的管理与分配,换句话说,如何把密钥发送到需要解密你的消息的人的手里是一个问题。在发送密钥的过程中,密钥有很大的风险会被黑客们拦截。现实中通常的做法是将对称加密的密钥进行非对称加密,然后传送给需要它的人。 非对称加密为数据的加密与解密提供了一个非常安全的方法,它使用了一对密钥,公钥(public key)和私钥(private key)。私钥只能由一方安全保管,不能外泄,而公钥则可以发给任何请求它的人。非对称加密使用这对密钥中的一个进行加密,而解密则需要另一个密钥。 4. HTTP 1.0、HTTP 2.0到HTTP 3.0以及HTTPS
HTTP1.0 使用的是非持久连接,主要缺点是客户端必须为每一个待请求的对象建立并维护一个新的连接,即每请求一个文档就要有两倍RTT 的开销。因为同一个页面可能存在多个对象,所以非持久连接可能使一个页面的下载变得十分缓慢,而且这种 短连接增加了网络传输的负担。(RTT(Round Trip Time):一个连接的往返时间) HTTP1.1 支持长连接, 在HTTP1.0的基础上引入了更多的缓存控制策略,引入了请求范围设置,优化了带宽,在错误通知管理中新增了错误状态响应码,增加了Host头处理,可以传递主机名(hostname),但是传输内容是明文,不够安全 HTTP 1.x优化(SPDY):SPDY 并不是新的一种协议,而是在 HTTP 之前做了一层会话层。为了达到减少页面加载时间的目标,SPDY 引入了一个新的二进制分帧数据层,以实现优先次序、最小化及消除不必要的网络延迟,目的是更有效地利用底层 TCP 连接。为多路复用设立了请求优先级,对header部分进行了压缩,引入了HTTPS加密传输,客户端可以在缓存中取到之前请求的内容。 HTTP2.0:支持明文传输,而HTTP 1.X强制使用SSL/TLS加密传输,和HTTP 1.x使用的header压缩方法不同。HTTP2.0 基于二进制格式进行解析,而HTTP 1.x基于文本格式进行解析,多路复用,HTTP1.1是多个请求串行化单线程处理,HTTP 2.0是并行执行,一个请求超时并不会影响其他请求。多路复用可以绕过浏览器限制同一个域名下的请求数量的问题,进而提高了网页的性能。 HTTP 3.0 (QUIC):QUIC (Quick UDP Internet Connections), 快速 UDP 互联网连接
,QUIC是基于UDP协议的。 线头阻塞(HOL)问题的解决更为彻底:基于TCP的HTTP/2,尽管从逻辑上来说,不同的流之间相互独立,不会相互影响,但在实际传输方面,数据还是要一帧一帧的发送和接收,一旦某一个流的数据有丢包,则同样会阻塞在它之后传输的流数据传输。而基于UDP的QUIC协议则可以更为彻底地解决这样的问题,让不同的流之间真正的实现相互独立传输,互不干扰。 切换网络时的连接保持: 当前移动端的应用环境,用户的网络可能会经常切换,比如从办公室或家里出门,WiFi断开,网络切换为3G或4G。基于TCP的协议,由于切换网络之后,IP会改变,因而之前的连接不可能继续保持。而基于UDP的QUIC协议,则可以内建与TCP中不同的连接标识方法,从而在网络完成切换之后,恢复之前与服务器的连接
HTTPS: HTTPS运行在安全套接字协议(Secure Sockets Layer,SSL )或传输层安全协议(Transport Layer Security,TLS)之上,所有在TCP中传输的内容都需要经过加密。HTTP的端口是80,HTTPS的端口是443 5. TCP 的拥塞控制、流量控制、滑动窗口
TCP拥塞控制用于控制发送端向网络一次连续写入的数据量。 使用的方法有 当发送窗口大小小于发送门限时,使用慢开始指数增大窗口,当发送窗口大于发送门限时,使用拥塞避免算法加性增加发送窗口大小,当出现网络拥塞时,门限减为当前发送窗口的一半,重新开始慢启动。另一种快速重传的方法是:如果收到连续三个ACK,则视作网络的阻塞程度不严重,将门限减为当前发送窗口大小的一半,将发送窗口尺寸设置为当前门限大小,启动拥塞避免算法。 如果发送方把数据发送得过快,接收方可能会来不及接收,这就会造成数据的丢失。TCP 的流量控制是利用滑动窗口 机制实现的,接收方在返回的 ACK 中会包含自己的接收窗口(RWND)的大小,TCP 头部有个 16 位窗口大小,表示的就是 RWND。以控制发送方的数据发送。 6. TCP与UDP
TCP 面向连接的,UDP 是无连接的 TCP 面向字节流,UDP 面向数据包 (字节流:发送端执行的写操作数和接收端执行的读操作数之间没有任何数量关系) Tcp 通过校验和,重传控制,序号标识,滑动窗口、确认应答实现可靠传输 UDP 具有较好的实时性,工作效率比 TCP 高,适用于对高速传输和实时性有较高的通信或广播通信 每一条 TCP 连接只能是点到点的, UDP 支持一对一,一对多,多对一和多对多的交互通信 TCP 对系统资源要求较多,UDP 对系统资源要求较少 若通信数据完整性需让位与通信实时性,则应该选用 TCP 协议(如文件传输、重要状态的更新等);反之,则使用 UDP 协议(如视频传输、实时通信等) 7. 为什么三次握手、SYN攻击、SYN攻击的应对方法
采用两次握手,那么若 Client 向 Server 发起的包 A1 如果在传输链路上遇到的故障,导致传输到 Server 的时间相当滞后,在这个时间段由于 Client 没有收到 Server的对于包 A1 的确认,那么就会重传一个包 A2,假设服务器正常收到了 A2 的包,然后返回确认 B2 包。由于没有第三次握手,这个时候 Client 和 Server 已经建立连接了。再假设 A1 包随后在链路中传到了 Server,这个时候 Server 又会返回 B1 包确认,但是由于 Client 已经清除了 A1 包,所以 Client 会丢弃掉这个确认包,但是 Server 会保持这个相当于“僵尸”的连接。
TCP 在传递数据前需要经过三次握手,SYN 攻击的原理就是向服务器发送SYN 数据包,并伪造源 IP 地址,服务器在收到 SYN 数据包时,会将连接加入 backlog 队列,并向源 IP 发送 SYN-ACK 数据包,并等待 ACK 数据包,以完成三次握手建立连接。由于源 IP 地址是伪造的不存在主机 IP,所以服务器无法收到 ACK 数据包,并会不断重发,同时 backlog 队列被不断被攻击的 SYN 连接占满,导致无法处理正常的连接。
针对 SYN 攻击的几个环节,提出相应的处理方法:
减少 SYN-ACK 数据包的重发次数 增加 backlog 队列 限制 SYN 并发数 使用 SYN Cookie 技术 8. TCP四次挥手的TIME_WAIT
首先调用 close()发起主动关闭的一方,在发送最后一个 ACK 之后会进入 time_wait 的状态,也就说该发送方会保持 2MSL 时间之后才会回到初始状态。MSL 指的是数据包在网络中的最大生存时间,一般是2min。
为什么存在 time_wait:
可靠地终止 TCP 连接。维持一个状态防止对端没有接受到最后一个 ACK 报文段 保证让迟来的 TCP 报文段有足够的时间被识别从而丢弃。TCP 报文段最大生存时间是 MSL,2MSL 保证两个传输方向上没有接收到的、迟到的 TCP 报文段全部消失。一个使用原本 IP 和端口的新连接可以在 2MSL 之后安全建立,而绝对不会接收到原有连接上的数据。 9. TCP 如何保证数据传输的可靠性
可靠连接 序号 应答机制 序列号与ACK 超时重传 流量控制 拥塞控制 CRC校验 TCP 对接收到的 TCP 报文段重排、整理,再交付给应用层 10. HTTP状态码
1XX 信息码,服务器收到请求,需要请求者继续执行操作;100 正常,客户端应该继续请求 2XX 成功码,操作被成功接收并处理;200 正常处理,204 成功处理,但是没有内容返回 3XX 重定向,需要进一步的操作以完成请求;301 永久重定向,302 临时重定向 4XX 客户端错误,请求包含语法错误或无法完成请求;400 语法错误,401 要求身份认证,403 禁止 404 找不到资源 5XX 服务器错误,服务器在处理请求的过程中发生了错误 500 内部服务器错误,503服务不可用 11. 路由器的作用
12. 我们的电脑能转发网络吗,原理是什么
14. 五层网络IO模型
物理层 数据链路层 网络层 运输层 应用层 (OSI会话层、表示层、应用层) 15. HTTP协议怎么解决拆包粘包的问题
TCP发送端为了将多个发往接收端的包,更有效的发到对方,使用了优化方法(Nagle 算
法),将多次间隔较小、数据量小的数据,合并成一个大的数据块,然后进行封包。这样,接收端,就难于分辨出来了,必须提供科学的拆包机制。
TCP 粘包是指发送方发送的若干包数据到接收方接收时粘成一包,从接收缓冲区看,后一包数据的头紧接着前一包数据的尾。
出现粘包的原因,发送端使用Nagle算法将多个小TCP合并发送,接收端将多个TCP包缓存接收。
解决方案:
16. HTTPS握手的过程,用到的加密算法
浏览器请求连接 服务器返回证书:证书里面包含了网站地址,加密公钥,以及证书的颁发机构等信息 浏览器收到证书后作以下工作 验证证书的合法性 生成随机(对称)密码,取出证书中提供的公钥对随机密码加密 将之前生成的加密随机密码等信息发送给网站 服务器收到消息后作以下的操作 使用自己的私钥解密浏览器用公钥加密后的消息,并验证 HASH 是否与浏览器发来的一致;获得浏览器发过来的对称秘钥 使用加密的随机对称密码加密一段消息,发送给浏览器 浏览器解密并计算握手消息的 HASH:如果与服务端发来的 HASH 一致,此时握手过程结束,之后进行通信 幂等性怎么确保的
TCP报文内容,http报文内容
ARP协议的作用
ARP(地址解析)协议是一种解析协议,本来主机是完全不知道这个 IP 对应的是哪个主机的哪个接口,当主机要发送一个 IP 包的时候,会首先查一下自己的 ARP 高速缓存表(最近数据传递更新的 IP-MAC 地址对应表),如果查询的 IP-MAC 值对不存在,那么主机就向网络广播一个 ARP请求包,这个包里面就有待查询的 IP 地址,而直接收到这份广播的包的所有主机都会查询自己的 IP 地址,如果收到广播包的某一个主机发现自己符合条件,那么就回应一个 ARP 应答包(将自己对应的 IP-MAC 对应地址发回主机),源主机拿到 ARP 应答包后会更新自己的 ARP 缓存表。源主机根据新的 ARP 缓存表准备好数据链路层的的数据包发送工作。
HTTP 无状态 无连接
无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求,并收到客户的应答后,即断开连接。采用这种方式可以节省传输时间。为请求时建连接、请求完释放连接,以尽快将资源释放出来服务其他客户端,可以加KeepAlive弥补无连接的问题 无状态是指协议对于事务处理没有记忆能力,服务器不知道客户端是什么状态。即我们给服务器发送 HTTP 请求之后,服务器根据请求,会给我们发送数据过来,但是,发送完,不会记录任何信息。 可以通过Cookie和Session来弥补这个问题。 Cookie 和 Session
cookie 是一种发送到客户浏览器的文本串句柄,并保存在客户机硬盘上,可以用来在某个WEB站点会话间持久的保持数据。 Session的本质上也是cookie,但是不同点是存在服务器上的。这就导致,你如果使用cookie,你关闭浏览器之后,就丢掉Cookie了,但是如果关掉浏览器,重新打开之后,发现还有相应的信息,那就说明用的是Session。因为cookie是存在本地的,所以也会有相应的安全问题,攻击者可以去伪造他,填写相应的字段名,就能登录你的账户,还有如果cookie的有效期很长的话,也不安全。 session 由服务器产生,对于客户端,只存储session id在cookie中 操作系统 进程与线程的区别
协程与线程
协程是一种比线程更加轻量级的存在。一个线程可以拥有多个协程;协程不是被操作系统内核管理,而完全是由程序所控制 协程的开销远远小于线程 协程拥有自己寄存器上下文和栈。协程调度切换时,将寄存器上下文和栈保存到其他地方,在切换回来的时候,恢复先前保存的寄存器上下文和栈 每个协程表示一个执行单元,有自己的本地数据,与其他协程共享全局数据和其他资源 跨平台、跨体系架构、无需线程上下文切换的开销、方便切换控制流,简化编程模型 协程又称为微线程,协程的完成主要靠 yeild 关键字,协程执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行 协程极高的执行效率,和多线程相比,线程数量越多,协程的性能优势就越明显 不需要多线程的锁机制 同一个进程中,不同线程什么是共享的,什么不是共享的(操作栈、程序计数器)
共享:
进程代码段 进程的公有数据(利用这些共享的数据,线程很容易的实现相互之间的通讯) 进程打开的文件描述符 信号的处理器 进程的当前目录 进程用户ID与进程组ID 私有:
线程ID 寄存器组的值 (PC指针) 线程的堆栈 错误返回码 线程的信号屏蔽码 线程上下文切换的时候,什么东西需要保存、什么东西需要恢复
进程切换步骤:
保存当前进程的上下文 恢复某个先前被抢占的进程的上下文 将控制传递给这个新恢复的进程 详细步骤:
保存处理器上下文环境即 PSW、PC 等寄存器和堆栈内容,保存到内核堆栈中 调整被中断进程的 PCB 进程控制块信息,改变进程状态和其它信息 将进程控制块移到相应队列即阻塞队列或就绪队列 选择另一个进程执行 更新所选择进程的 PCB 进程控制块(包括将状态变为运行态) 更新内存管理的数据结构 恢复第二个进程的上下文环境 进程调度算法
先来先服务调度算法 短作业优先调度算法 非抢占式优先级调度算法 抢占式优先级调度算法 高响应比优先调度算法 时间片轮转法调度算法 进程间怎么通信
管道 (具名管道,无名管道) 消息队列 信号:用于通知接收进程某个事件已经发生 信号量: 信号量是一个计数器,信号量用于实现进程间的互斥与同步,而不是用于存储进程间通信数据 共享内存 socket套接字 线程间通信
临界区:通过多线程的串行化来访问公共资源或一段代码,速度快,适合控制数据访问 互斥量 Synchronized/Lock:采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个,所以可以保证公共资源不会被多个线程同时访问 信号量 Semphare:为控制具有有限数量的用户资源而设计的,它允许多个线程在同一时刻去访问同一个资源,但一般需要限制同一时刻访问此资源的最大线程数目 事件(信号),Wait/Notify:通过通知操作的方式来保持多线程同步,还可以方便的实现多线程优先级的比较操作 LRU算法是如何实现的
哈希链表法
volatile 内存屏障
volatile 关键字是一种类型修饰符,用它声明的类型变量表示可以被某些编译器未知的因素更改,比如:操作系统、硬件或者其它线程等。遇到这个关键字声明的变量,编译器对访问该变量的代码就不再进行优化,从而可以提供对特殊地址的稳定访问。声明时语法:int volatile vInt; 当要求使用 volatile 声明的变量的值的时候,系统总是重新从它所在的内存读取数据,即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存
volatile 用在如下的几个地方:
中断服务程序中修改的供其它程序检测的变量需要加 volatile 多任务环境下各任务间共享的标志应该加 volatile 存储器映射的硬件寄存器通常也要加 volatile 说明,因为每次对它的读写都可能由不同意义 死锁的四个条件和预防
互斥:一个资源每次只能被一个进程使用 不可抢占性: 当某个进程已经获得这种资源后,系统是不能强行收回,其他进程也不能强行夺走,只能由自身使用完释放 保持与等待:部分分配,允许进程在不释放其已经分得的资源的情况下请求并等待分配别的资源 循环等待:若干个进程形成环形链 预防方法:
允许进程强行从占有者那里夺取某些资源,破坏不可抢占条件 进程在运行前一次性地向系统申请它所需要的全部资源。,破坏了保持与等待条件 把资源事先分类编号,按号分配,使进程在申请,占用资源时不会形成环路,破坏了
循环等待条件 银行家算法
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。
算法内容:
每一个线程进入系统时,它必须声明在运行过程中,所需的每种资源类型最大数目,其数目不应超过系统所拥有每种资源总量,当线程请求一组资源系统必须确定有足够资源分配给该进程,若有,再进一步计算这些资源分配给进程后,是否会使系统处于不安全状态,不会(即若能在分配资源时找到一个安全序列),则将资源分配给它,否则等待 多路IO模型 NIO
在多路复用IO模型中,会有一个线程(Java中的Selector)不断去轮询多个socket的状态,只有当socket真正有读写事件时,才真正调用实际的IO读写操作。因为在多路复用IO模型中,只需要使用一个线程就可以管理多个socket,系统不需要建立新的进程或者线程,也不必维护这些线程和进程,并且只有在真正有socket读写事件进行时,才会使用IO资源,所以它大大减少了资源占用。
五种IO模型
阻塞IO: 应用程序调用一个 IO 函数,导致应用程序阻塞,等待数据准备好 非阻塞IO: 我们把一个 SOCKET 接口设置为非阻塞就是告诉内核,当所请求的 I/O 操作
无法完成时,不要将进程睡眠,而是返回一个错误。这样我们的 I/O 操作函数将不断的测试数据是否已经准备好,如果没有准备好,继续测试,直到数据准备好为止。在这个不断测试的过程中,会大量的占用 CPU 的时间 多路IO复用: I/O 复用模型会用到 select、poll、epoll 函数,这几个函数也会使进程阻塞,但是和阻塞 I/O 所不同的的,这三个函数可以同时阻塞多个 I/O 操作。而且可以同时对多个读操作,多个写操作的 I/O 函数进行检测,直到有数据可读或可写时,才真正调用 I/O 操作函数 信号驱动IO(不常用): 首先我们允许套接口进行信号驱动 I/O,并安装一个信号处理函数,进程继续运行并不阻塞。当数据准备好时,进程会收到一个 SIGIO 信号,可以在信号处理函数中调用 I/O操作函数处理数据。 异步IO: 当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者的输入输出操作 有哪几种多路复用的方式?它们之间的区别
select 单个进程能够监视的文件描述符的数量存在最大限制,通常是 1024。由于 select 采用轮询的方式扫描文件描述符,文件描述符数量越多,性能越差 内核/用户空间内存拷贝问题,select 需要大量句柄数据结构,产生巨大开销 Select 返回的是含有整个句柄的数组,应用程序需要遍历整个数组才能发现哪些句柄发生事件 Select 的触发方式是水平触发,应用程序如果没有完成对一个已经就绪的文件描述符进行 IO 操作,那么每次 select 调用还会将这些文件描述符通知进程 poll 与 select 相比,poll 使用链表保存文件描述符,一没有了监视文件数量的限制,但其他三个缺点依然存在 epoll epoll 使用一个文件描述符管理多个描述符,将用户关系的文件描述符的事件存放到内核的一个事件表中,这样在用户空间和内核空间的 copy 只需一次。Epoll 是事件触发的,不是轮询查询的。没有最大的并发连接限制,内存拷贝,利用 mmap() 文件映射内存加速与内核空间的消息传递 epoll的两种工作模式
当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序,应用程序可以不立即处理该事件。下次调用 epoll_wait 时,会再次响应应用程序并通知此事件。一个 socket 第一次有数据,LT 模式下检测到 socket 处于活跃状态,接下来再有数据过来,接着触发。或者说可以根据需要收取部分数据,只要 socket 上数据不收取完,epoll_wait 会接着返回这个可读 socket。编程上如果需要数据包一部分一部分的处理,可以使用 LT 模式
当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序,应用程序必须立即处理该事件。如果不处理,下次调用 epoll_wait 时,不会再次响应应用程序并通知此事件。第一次有数据会触发 socket,第二次再有数据不会触发,必须等第一次的数据完全读完或写完。必须把当前 socket 数据全部收完,才能接受下一次的可读 socket。编程上 ET 模式必须是一个循环,收取数据到 recv 返回-1,errno=EAGAIN
虚拟内存
虚拟内存使得应用程序认为它拥有连续的可用内存,这样一来,就在逻辑层面上扩大了内存容量。但是实际上,只是把比较常用的内存片段取出来了而已,还有部分资源是放在磁盘存储器上的。需要的时候再进行数据交换。 调度方式有,分页式,段式,段页式。比较流行方式是段页式,他结合了前两者的优点,以页为单位替换,以段为单位使用。 常见的替换替换算法有4种,随机算法,先进先出算法,LRU算法,最优算法。 比较常使用的是LRU算法,他在redis里也有使用,当redis的内存满了的时候就是使用LRU算法替换掉旧内存。 算法 加密算法
线性同余法
快排的优化
打印二叉树每一层,最右边节点的值
寻找两个链表的公共节点
镜像二叉树
删除链表中所有值相等的节点
单例模式
鸡蛋摔楼的问题
Linux kill -9与kill -15的区别
SIGNKILL(9) 的效果是立即杀死进程. 该信号不能被阻塞, 处理和忽略。 SIGNTERM(15) 的效果是正常退出进程,退出前可以被阻塞或回调处理。并且它是Linux缺省的程序中断信号(默认是15)。 kill - 9 表示强制杀死该进程;与SIGTERM相比,这个信号不能被捕获或忽略,同时接收这个信号的进程在收到这个信号时不能执行任何清理 Linux修改用户权限
sudo password xxx # xxx 表示用户名
sudo userdel xxx sudo rm -rf /home/xxx # 删除用户权限相关配置 cd /home rm -rf xxx cat /etc/passwd # 找到最后一行,可以发现刚刚创建的用户,再使用vi编辑器删除最后一行 cat /etc/group # 找到最后一行,可以发现刚刚创建的用户,再使用vi编辑器删除最后一行 cd /var/spool/mail rm -rf xxx # 删除邮箱文件
# 采用修改系统中/etc/sudoers文件的方法分配用户权限。因为此文件只有r权限,在改动前需要增加w权限,改动后,再去掉w权限 sudo chmod +w /etc/sudoers sudo vim /etc/sudoers # User privilege specification add text root ALL=(ALL:ALL) ALL xxx ALL=(ALL:ALL) ALL # 这一行为添加的代码,XXX表示需要添加权限的用户名 sudo chmod -w /etc/sudoers # 改为只读模式
查看网络端口
netstat -a #列出所有端口
netstat -at #列出所有tcp端口
netstat -au #列出所有udp端口
netstat -ax #列出所有UNIX端口
netstat -al #列出所有监听中的端口
netstat -lt #列出所有监听中的tcp有端口
netstat -lu #列出所有监听中的udp端口
netstat -lx #列出所有监听中的unix端口
查看所有文件的大小
du -h --max-depth=1 # 如果没有--max-depth=1,则会递归显示所有目录
df 命令是查看文件系统给的大小
Git 版本控制 git rebase 与 git merge
Merge 会自动根据两个分支的共同祖先和两个分支的最新提交进行一个三方合并,然后将合并中修改的内容生成一个新的 commit,即 merge 合并两个分支并生成一个新的提交,并且仍然后保存原来分支的 commit 记录。 Rebase 会从两个分支的共同祖先开始提取当前分支上的修改,然后将当前分支上的所有修改合并到目标分支的最新提交后面,如果提取的修改有多个,那 git 将依次应用到最新的提交后面。Rebase 后只剩下一个分支的 commit 记录