超高频os、计网、mysql问题


计网

OSI七层模型及功能描述

物理层:规定电气,机械方面特性,来建立物理链路连接,进行比特流传输。以太网协议。

数据链路层:将数据分层数据帧,以帧为单位发送,并进行流量控制,传送出错对方要重发。ARP协议。

网络层:为数据包选择路由、分组传输。IP ICMP

传输层:提供端到端的接口。TCP UDP

会话层:进程之间的通信称为会话,会话层管理的是不同主机之间各进程的通信。

表示层:格式化、解压缩和转换服务。

应用层:顶层应用,如文件传出,电子邮件,HTTP FTP DNS

TCP/IP协议分层模型及每层常见协议

image-20220114173929807

UDP、TCP

TCP三次握手,四次挥手

TIME_WAIT

TCP可靠传输,滑窗、确认应答、超时重传、流量控制、拥塞控制

HTTP方法,GET POST

HTTPS

浏览器URL回车

数据库

为什么 MySQL 采用 B+ 树作为索引?和B树、红黑树、哈希表的比较。

单就索引来说,可以用哈希表、二叉查找树、自平衡二叉查找树、红黑树、B树、B+树,首先索引要满足的就是查找的性能。在MySQL里面,需要考虑两个问题:一个是查找的性能,因为是磁盘IO,所以查找次数要尽可能少;二是范围查找。

首先说下哈希表,它可以一次定位,效率比较高,但是对于模糊查找、联合索引、范围查询不行。

然后是二叉查找树,它一般查找效率是O(logN),但是极端条件会退化为O(N),针对这个极端情况可以采用自平衡二叉查找树,它是加了一个限制条件,左右子树高度差不能超过1,这样在插入的时候,就会进行调整。但是这个就降低了插入的效率,它的要求太严格了,在一般情况下可以选择保持相对程度的平衡,而不是绝对的高度差不能超过1,也就是可以选用红黑树的做法,它通过设置红黑结点和一些变色、旋转的规则下,来保持大致平衡。但是,红黑树还是二叉树,在数据多的时候,它的高度还是比较高,也就是磁盘IO查找的次数比较多,会影响性能,所以比这个稍微好一些的又有B树,它是多叉平衡查找树,也就是每个结点可以有多个子结点,这样就降低了磁盘IO的次数。B树文件系统的索引用的比较多。为什么文件系统的索引喜欢用B树而不是红黑树或者有序数组呢?

文件系统和数据库的索引都是存储在硬盘上的,如果数据量大的话,不一定能一次性加载到内存里。B树可以分批将需要的数据加载到内存,减少磁盘IO。

B+树是在B树的基础上改造,它的数据都在叶子结点,同时叶子结点之间还加了指针,方便范围查找。

InnoDB如何存储数据的?

按数据页为单位读写,读的时候并不是单独一条记录,而是以页为单位,整体读入内存。InnoDB默认数据页大小16kB。

image-20220112145845510

如何查询

image-20220112145954477

B+树的特点:

  • 只有叶子结点存放了数据,在非聚集索引里是主键,在聚集索引里是具体的数据行。
  • 所有结点按照索引键大小排序,构成一个双向链表。

例如查找主键为6的记录:查询根结点,6在页30,查询页30,二分法快速定位到6所在页16,在页16中,通过槽查找记录,二分法快速定位到分组,然后在分组内遍历,找到记录。

数据库一次查询遍历B+树的次数、磁盘IO数

主键索引遍历一次B+树。二级索引遍历一次或两次,第一次找到对应的主键,如果找到了需要的数据就结束,没有就根据找到的主键回表查找主键索引。

数据库B+树的高度一般在2-4层,也就是查找一个键值时,最多需要2-4次IO。B+树索引并不能找到具体行,只能找到被查找的键值所在行的页,然后数据库把页读取到内存,在内存中查找。每一页中数据的查找采用二分查找;

数据库每个数据页是通过一个双向链表连接。

InnoDB和MyISAM区别特点、适用场景

区别:

  • 事务处理,MyISAM非事务安全,InnoDB支持事务
  • 锁机制,MyISAM只有表级锁,InnoDB可以是行级锁,间隙锁。
  • 大量查找用MyISAM,大量更新用InnoDB
  • MyISAM不支持外键,InnoDB支持外键
  • MyISAM有保存行数

为什么MyISAM查询会快?

因为InnoDB要维护的东西比较多,像是MVCC,还有寻址InnoDB是先映射到块再到行,MyISAM直接是文件的偏移。

场景:

  • MyISAM:插入不频繁,查询频繁,没有事务
  • InnoDB:要求事务,表更新频繁

聚集索引;辅助索引(二级索引);什么是回表查询;如何优化回表查询;什么是覆盖索引;覆盖索引的应用场景

覆盖索引:避免回表查询的优化策略,就是把所有需要查询的字段都放到普通索引中,如果Explain时输出信息中有using index,就使用了覆盖索引。就是特定于具体select语境而言的联合索引,可以通过索引直接查找记录,不需要回表查询。

如之前已经建立了name索引,但是业务经常用name查找age,怎么做?

image-20220112153359082

建立联合索引,直接就找到age了,不需要回表。

联合索引及要求,最左匹配(给一个表,sql判断是否走索引,为什么)

如果一条SQL里面用到了联合索引最左边的索引,就会利用这个联合索引去匹配,当遇到范围查询的时候就会停止。

对(a,b)联合索引

a = 1 #yes
a = b and b = 2 #yes
b = 2 and a = 1 #yes 优化器会自动调整顺序
b = 2 #no

如何建立索引

SELECT * FROM table WHERE a = 1 and b = 2 and c = 3;
# (a,b,c) (a,c,b)...都可以,sql会优化顺序,关键是区分度高的放前面。

SELECT * FROM table WHERE a > 1 and b = 2;
# (b,a),因为遇到范围查询停止

SELECT * FROM `table` WHERE a > 1 and b = 2 and c > 3;
# (b,a和c中区分度高的)

SELECT * FROM `table` WHERE a = 1 ORDER BY b;
# (a,b),因为a=1的时候,b相对有序

SELECT * FROM `table` WHERE a > 1 ORDER BY b;
# (a),因为范围了,b无序

SELECT * FROM `table` WHERE a IN (1,2,3) and b > 1;
# (a,b) IN可以视为等值,不会终止索引匹配

ACID、隔离级别、脏读、不可重复读、幻读

mysql ACID分别怎么保证

读取未提交的数据,也被称之为脏读。

因为同一事务的其他实例在该实例处理其间可能会有新的commit,所以同一select可能返回不同结果。

幻读指当用户读取某一范围的数据行时,另一个事务又在该范围内插入了新行,当用户再读取该范围的数据行时,会发现有新的“幻影” 行。

张三查又查不到,插又不成功,幻读。

操作系统

管道本质

匿名管道:管道是半双工的,数据只能向一个方向流动;需要双方通信时,需要建立起两个管道;只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程)。命名管道不同于匿名管道之处在于它提供一个路径名与之关联,以FIFO的文件形式存在于文件系统中。这样,即使与FIFO的创建进程不存在亲缘关系的进程,只要可以访问该路径,就能够彼此通过FIFO相互通信(能够访问该路径的进程以及FIFO的创建进程之间),因此,通过FIFO不相关的进程也能交换数据。值得注意的是,FIFO严格遵循先进先出(first in first out),对管道及FIFO的读总是从开始处返回数据,对它们的写则把数据添加到末尾。它们不支持诸如lseek()等文件定位操作。

消息队列本质

类似命名管道,优势在于独立于发送和接收进程存在,消息可以带类型。消息队列的本质是一个内核提供的链表,可以插入数据(写入消息队列),也可以删除数据(读出消息)。也是有上限的。

消息队列和管道区别

为什么共享内存通信最快?

是什么,怎么做,为什么

共享内存用于实现进程间大量数据传输。它会在内存中单独开辟一段内存空间,这段内存空间有自己特有的数据结构,包括访问权限、大小等。进程间的通信不需要经过内核,但是需要用户自己进行同步操作。

image-20220114180820500

共享内存消息只复制两次。

image-20220114175752150

消息队列和管道需要复制四次。

死锁

资源锁、获取资源阻塞时不释放、不被抢、循环等待资源。

阻塞

同步/异步:是针对操作系统来说的,发送请求后,是否一直等待数据的到来。如果一直等待,则是同步。

阻塞/非阻塞:是针对接口来说的,接收请求后,是否立即返回响应。如果不是立即响应,则是阻塞。

阻塞是进程调度的一环,进程在等待某事件(如接收网络数据)发生之前的等待状态,recv select epoll wait都是阻塞方法。

如recv

//创建socket 
int s = socket(AF_INET, SOCK_STREAM, 0);    
//绑定 
bind(s, ...) 
//监听 
listen(s, ...) 
//接受客户端连接 
int c = accept(s, ...) 
//接收客户端数据 
recv(c, ...); 
//将数据打印出来 
printf(...) 

recv阻塞,会一直等待,直到接收到数据才执行,阻塞的原理是什么?

运行到recv,程序从运行态变为等待状态,接收到数据之后又变回运行状态。

image-20220114184607967

阻塞不耗费cpu,但是进程阻塞了,如果同时来了三个访问请求,ABC都阻塞了,又来了一个请求,就没有进程能处理了,虽然阻塞时会进程切换,但是也要有干活的进程才行啊,所以阻塞就意味着要开大量的进程或者线程。

非阻塞是一个进程可以对接多个请求,一个请求没好,那就处理好了的那个。

问题不在于CPU干活不干活,而是进程干活不干活。

用户进程发起请求从内核中获取数据那么这时候有两种情况:

  • 操作系统还没有准备后数据,那么这时候怎么办,有两种方法:

    • a. 让用于进程等着(这种情况就是阻塞)
    • b. 如果没有数据就返回一个ERROR,不需要用户进程干等(这种情况就是非阻塞)
  • 过了一会儿操作系统准备好数据了,这时候又有两种方法:

    • a. 啥也不管,等着用户进程再次来请求才把数据给它(这种情况就是同步)
    • b. 负责到底,数据准备好,直接给到用户进程,并且还发出一个信号,告诉用户进程数据已经准备好(这种情况就是异步)

思维题

如何在10亿数中找出前1000大的数?

首先大数据要分析一下内存空间。

  • 排序,O(logN)
  • 快速选择,O(n),如果内存装不下,可以写入文件,然后在分治的时候把其中一个文件读出来继续分治。但是这样就牵扯到多次磁盘IO。可以利用分布式的思想,把数据切分,放到多台机器上,然后分别计算前1000大的数据,然后进行汇总。
  • 最小堆

力扣题目

2127. 参加会议的最多员工数

内向基环树:每个连通块仅有一个环,每个点的出度均为1,这样的图叫做内向基环树。有一个基环和指向基环的树枝组成。

image-20220114161336442

两种情况,三人以上环的话,只能是这个环。二人环的话,所有二人环及各自跟随着的最长舔狗链们。(注:三人环,二人环可能都有,即不同的舔狗团)

步骤:

  • 拓扑排序找环(拓扑排序后没有访问过的就是环上的结点),三人环,记录大小
  • 二人环,全部舔狗链
  • max(三人环,二人环和)
class Solution {
    public int maximumInvitations(int[] favorite) {
        // 拓扑排序找非环,统计链长
        int n = favorite.length;
        int[] dogsChain = new int[n]; //舔狗链长度
        int[] dogsCount = new int[n];  //入度
        boolean[] visited = new boolean[n];

        Deque<Integer> deque = new LinkedList<>();
        for(int i=0;i<n;i++) {
            dogsCount[favorite[i]]++;
        }

        for(int i=0;i<n;i++) {
            if(dogsCount[i]==0) {
                deque.addLast(i);
            }
        }

        while(!deque.isEmpty()) {
            int cur = deque.pollLast();
            visited[cur] = true;
            dogsCount[favorite[cur]]--;
            dogsChain[favorite[cur]] = Math.max(dogsChain[favorite[cur]],dogsChain[cur]+1);
            if(dogsCount[favorite[cur]]==0) {
                deque.addLast(favorite[cur]);
            }
        }
        // 找环大小
        int twos = 0;
        int result = 0;
        for(int i=0;i<n;i++) {
            if(visited[i]) continue;
            visited[i] = true;
            int cur = i;
            int next;
            int c = 1;
            while((next=favorite[cur])!=i) {
                visited[next] = true;
                cur = next;
                c++;
            }
            if(c==2) twos+=dogsChain[i]+dogsChain[cur]+2;
            else result = Math.max(result,c);
        }
        return Math.max(result,twos);
    }
}