Kenway's Blog

【笔记】OS计网数据库

发表于 更新于 分类于

目录

操作系统

计算机网络

数据库

Linux和git

操作系统

1.线程独有的资源是什么

  • 程序计数器
  • 寄存器状态
  • 栈空间，CPU的使用权

2.进程和线程的区别

  • 一个进程里包含多个线程
  • 进程是操作系统分配资源的基本单位，线程是操作系统执行任务的基本单位
  • 进程的通信方式是：
    • 共享内存：这块内存由多个进程共享，最快
    • 管道：半双工通道，是单向的
    • 消息队列：消息的链表，有标识符标记存在内核里面
    • 套接字：socket，可实现不同机器、不同进程之间的通信
    • 信号：通知进程，系统中发生了某种预先规定好的事件
  • 线程的通信方式：
    • 互斥量(即锁)
    • 临界区：通过对多线程的串行化来访问公共资源，速度快
    • 信号量：可视作有buffer的互斥锁
    • 事件：针对具有后继任务需要操作的的事件设计，用通知的方式来保持多线程同步

3.同一进程下的线程共享哪些资源

  • 堆
  • 数据空间
  • 静态存储区

4.进程、线程的上下文切换

  • 进程切换开销大是因为进程得去切换环境，例如全局变量、文件描述符
    • 父、子进程之间会共享文件描述符，因为文件描述符会关联一张内核文件表。相当于子进程复制了父进程的指针p1得到p2，但是p1和p2实际上指向的还是同一个数据
      • ps，父子进程之间的通信方式和进程之间通信一样
  • 线程切换比进程小，但是也有一定开销，因为要把CPU里寄存器存的状态保存到内存中，然后从内存中拿新线程的状态放到CPU里去执行，涉及内核态用户态的转换

5.进程和线程的调度策略(共用，因为进程和线程实质上一样)

  • 先来先执行
  • 短作业优先
  • 时间片轮转
  • 优先级调度
  • 带权时间片轮转：高权值获得更多时间片

6.共享内存是并发安全的吗，如何加锁

  • 不是，进入前mutex加锁，退出后mutex解锁

7.管道两端可以互传数据吗

  • 不可以，管道是半双工的，即是单向的

8.浏览器是一个多进程服务

  • 每开一个标签页，其实就是多开一个进程
  • 设计的目的是避免某一页面出问题影响到其他页面

9.用户态和内核态

  • Linux进程的虚拟内存分为用户空间(前3GB)和内核空间(最后1GB)，64位都是128T
  • 常规操作默认用用户态，使用到内核空间的必须要切换为内核态操作
    • I/O读写、进程销毁和创建、内存空间的申请和释放
  • 从用户态切换到内核态需要进行中断操作，处理完后还需要恢复操作

10.虚拟内存

  • 虚拟内存简单来说就是把外存当作内存来使用，便于缓解物理内存压力的不足
  • 实现内存抽象，每个进程都以为自己拥有全部内存，操作虚拟地址的操作都会被转换为操作物理地址
    • 虚拟地址是CPU里一个名叫MMU的硬件通过放在主存里的查询表来翻译成物理地址

11.多线程访问同一资源

  • 需要上锁
  • 在Linux里面，进程和线程的实现是一样的，只是两者可以使用的资源不一样

12.epoll和select

  • epoll
    • 文件描述符FD上限是最大可打开文件数，参考值20w
    • 水平触发LT和边缘触发ET(只会通知一次)
      • LT不如ET高效的原因，边缘触发可以减少epoll_wait的系统调用次数
      • 边缘触发一般搭配非阻塞I/O使用，因为边缘触发只通知一次，这时候应该尽可能地读写
      • 水平触发一般搭配阻塞I/O使用，因为持续通知，所有不需要尽可能地读写，可以按正常逻辑来读写
    • 通知进程时会直接返回就绪事件，不用去轮询(底层原理是内核里维护一个红黑树和双向链表)
    • 只在注册新事件的时候整体拷贝一遍，开销小
    • 只能在linux上使用，使用逻辑比select复杂
  • select
    • FD上限是1024个，可以在linux内核中修改。原理是把socket全放在一个集合里，每次都是去遍历看看是否有准备好的
    • 水平触发，如果程序没有完成I/O操作，那么这个FD还是会被select作为通知
    • 通知进程时只会告知有事件发生，具体地址还需要进程去轮询
    • 每次改变内核中的fd集合时，都需要整体拷贝一遍，开销巨大
  • poll
    • 返回全部的fd，和slect一样也是采用轮询来检测就绪事件
    • 水平触发

13.在4G物理内存的机器上，申请8G内存

  • 32位机器上，申请失败
    • 虚拟地址空间：用户占3G，内核占1G，实际最大只能申请3G
  • 64位机器上，申请成功，但是实际读写该内存超过时会触发OOM
    • 虚拟地址空间：内核128T，用户128T
  • ps，栈默认大小4M

14.零拷贝

  • 计算机在执行IO操作时，CPU不需要从一个存储区域复制到另一个存储区域，进而减少用户态到内核态的上下文切换以及CPU的拷贝时间
  • 把数据从磁盘缓冲区搬运到内核缓冲区这个工作交给DMA控制器去做，CPU可以去处理其他事务
    • DMA处理完成后，CPU再去把数据从内核拷到用户空间
    • 现在的每个I/O设备基本都有自己的DMA控制器
  • kafka就是利用了零拷贝，I/O吞吐量增大，处理海量数据效率才能这么高
    • 具体是利用了文件系统的页缓存和sendfile系统调用来实现数据从页缓存直接拷贝到内核缓冲区

15.多线程开发需要注意哪些问题

  • 线程的数量：比如线程是不是无限创造的，并且线程的创建和销毁是有开销的，常见做法是使用线程池，预先创建一些线程资源来供后续使用。还得考虑CPU核数来制定线程池的合理大小
  • 并发安全问题，读写共享变量等
  • 避免死锁
    • 按照固定的顺序获取锁：例如，如果A线程先获取了锁1，再获取锁2，那么B线程就应该先获取锁1，再获取锁2
    • 设置超时时间：在获取锁的过程中，可以设置超时时间，如果超过一定时间还没有获取到锁，就放弃获取锁，避免因等待锁而导致的死锁

16.IO密集型时epoll效率不高的原因

  • epoll每一次连接比起select->accpet要多一次epoll_ctl系统调用
  • epoll在读操作的时候，read完后也需要epoll_ctl加入写事件，相比select多了一次系统调用
    • 因为epoll是靠epoll_ctl的写入来保证敏感性的，而不是像select一样全copy一遍

17.linux命令

  • 查看进程占用的端口号 netstat & grep
  • 查看日志 tail -n 10 xx.log

18.僵尸进程

  • 子进程退出后，父进程没有调用对应的方法得知，导致该子进程的进程描述符仍保存在系统中(一直占据进程号)，成为僵尸进程
  • 即失去了对该进程号的控制，类似于内存泄漏

19.协程大小一般为2kb，线程大小一般为1mb

20.死锁怎么解决

  • 破坏死锁形成的条件之一：互斥、不可抢占、占有且请求、循环等待
  • 鸵鸟算法：忽略死锁
  • 银行家算法：
    • 首先，要求每个进程必须声明最大资源需求
    • 运行中，检查请求的资源是否超过了系统拥有的资源
    • 进行试分配
    • 安全性检查算法进行检查

21.阻塞I/O和非阻塞I/O区别

  • 遇到阻塞时，阻塞I/O会把程序挂起，直到系统硬件发起中断来告诉它数据准备好了
    • 不占用CPU，但是会浪费计算资源
  • 遇到阻塞时，非阻塞I/O的程序会收到一个错误，这时候有两种设计，一是持续轮询是否不阻塞，二是继续执行其他代码然后间歇回来轮询
    • 轮询占用CPU，所以开销很大
  • 总结：一个是直接由操作系统挂起，一个是收到错误信号然后自己处理

计算机网络

1.OSI七层模型(从下数起，物理层是第一层)：分层的意义在于把复杂问题拆解，各层相互解耦可以用不同的技术实现

  • 应用层：
    • 提供网络服务接口
    • FTP、Telnet、DNS、SMTP、POP、HTTP协议
  • 表示层：规范数据格式
  • 会话层：管理会话，socket在这一层
  • 传输层：
    • 数据单位为段
    • 网关
    • TCP、UDP协议
  • 网络层：
    • 数据单位为IP数据包
    • 寻址、选路由、连接的建立保持与终止
    • IP、ICMP、ARP、RARP协议
  • 数据链路层：
    • 数据单位为帧
    • 网桥、交换机、网卡
    • 以太网协议
  • 物理层(在终端设备间传输比特流)：提供物理媒体中继器、集线器(不具备寻址功能，会把信息发送给所有主机)

TCP/IP 5层模型：应用层、传输层、网络层、数据链路层、物理层

TCP/IP 4层模型：应用层、传输层、网络层、网络接口层

2.TCP报文头里包含以下内容(每部分默认2字节)

  • 源端口号
  • 目的端口号
  • 序列号：占4字节，表示当前报文的序列号，用于保证传输的有序性
  • 确认号：占4字节，表示确认的上一条报文的序列号。ACK标志为1时，确认号字段才有效
  • 窗口大小：表示接收方所能处理的数据量
  • 标识位：ACK、SYN、FIN、URG等
  • 校验和
  • 紧急指针：指出紧急数据在报文段中的位置，表示该数据需要优先读取。URG标志为1时，紧急指针才有效

3.GET和POST请求的区别

  • GET请求
    • 参数通过url明文传递，只能用ASCII码，有长度限制（这个是浏览器限制的，实际上http并没有这种限制）
    • 浏览器会主动缓存（包括传的参数）
    • 按RFC规范来是只读操作，是安全幂等的
      • 幂等指的是多次执行相同操作，结果和只执行一次是相同的，一般业务场景是用户重复提交导致多次扣钱等，可以用版本号这种乐观锁的方式来实现。这里get只是稍微涉及一点点概念
    • 简单请求
  • POST请求
    • 参数放在request body里，有多种编码方式(get只能url编码)
    • 不会被浏览器主动缓存
    • 未指定资源的存放位置，由服务器决定
    • 按RFC规范来说是新增操作，不是安全幂等的(实际上开发者可以不遵循规范，让get也去修改服务器数据)
    • 简单请求
  • PUT请求(其他和POST相似)
    • 参数放在request body里
    • 指定了资源的存放位置
    • 按RFC规范来说是更新操作，是安全幂等的
    • 复杂请求，需要option预检
  • DELETE请求
    • 复杂请求，需要option预检

4.跨域问题是什么，怎么解决跨域问题的，不同服务之间调用会有跨域问题么

  • 同源政策保证该网站的资源只能由同源请求执行(域名和端口名一样)，是为了防止别的网站对该网站进行攻击，是浏览器采取的安全策略
  • 实现方法是新增一组HTTP首部字段，允许服务器声明哪些源站通过浏览器有权限访问哪些资源
  • 对那些可能对服务器数据产生副作用的HTTP请求方法（特别是GET以外的HTTP请求），浏览器必须首先使用OPTIONS方法发起一个预检请求，从而获知服务端是否允许该跨源请求。服务器确认允许之后，才发起实际的HTTP请求
  • 不同服务如果部署在不同域名端口上，也会有跨域问题

5.说一下知道的状态码，200是什么，重定向是什么，它的过程是什么，如果重定向的话那么网页是如何获取客户端信息的呢？

  • 状态码
    • 1开头表示信息
    • 2开头表示成功（200-请求成功）
    • 3开头表示发生了重定向（301-网页被永久转移到其他URL、http升级成https也用这个）（302-网页展示转移到其他URL）
      • 301和302的区别在于用于告诉一些搜索引擎例如google等，是否要把老网页的权重转移到新网页
      • 这个状态也常用于短域名技术
    • 4开头表示客户端错误（404-请求的网页不存在）（499-客户端已关闭连接）
    • 5开头表示服务端错误(500-内部服务器错误（502-网关错误，表示服务器作为网关或代理服务器时收到了来自上游服务器的无效响应)（504-上游服务器响应超时）
  • 重定向是浏览器发送请求到s1之后，s1需要访问s2，但并未在服务器内直接访问，而是由服务器自动向浏览器发送一个响应，浏览器再自动提交一个新的请求，这个请求就是对s2的请求
  • s2获取客户端信息是通过第二次浏览器发起的请求获得的
  • 对s2的请求是无法获得之前对s1提交的参数的，所以重定向也用来保证表单不重复提交

6.TCP和UDP区别

  • TCP面向连接提供可靠服务；UDP是无连接的，尽最大努力交付，但不保证可靠交付，UDP 具有较好的实时性
  • TCP连接是1对1，UDP无连接可以1对多
  • TCP首部开销20字节，UDP首部开销8字节
  • TCP把数据看成字节流，UDP把数据看成报文包

7.为什么TCP更可靠

  • 校验和
  • 序列号
  • 超时重传机制
  • 确认应答ACK机制
  • 流量控制
    • 滑动窗口，根据发送端根据自己上一个接受到的确认报文的滑动窗口字段来决定发送的数据大小，如果为0就停止发送，但会定时发送窗口探测报文
  • 拥塞控制

8.TCP三次握手，如果改成两次握手会怎么样，那如果我就按两次握手算是建立连接了，那客户端向服务端发数据会怎么样

  • 1.序列号乱序，只有两次握手，不能同步双方的初始序列号，比如因为第二次握手就算成功了，client可能收不到serve的初始序列号
  • 2.产生冗余连接浪费资源，比如client发出的某个连接请求经网络延迟很久以后才到serve端，这时serve端回一个SYN+ACK后就默认连接建立的话，client此时并不需要建立连接直接忽略掉，那么serve端会一直等待数据传输导致资源浪费

9.HTTP是基于TCP的吗，七次握手中什么时候是对称加密什么时候是非对称加密，最后握手结束之后采用什么加密

  • HTTP是基于TCP的
  • 先采用非对称加密传递，再采用对称加密
  • 原因是非对称加密可以保证传递密钥时的安全性(被截取也不会泄露信息)，但是非对称加密的过程很慢，所有握手完传输数据要用对称加密
    • 非对称加密算法实现通常涉及大数分解、离散对数等，密钥较长
    • 对称加密算法通常是基于位运算和异或操作等简单运算，密钥较短

10.将url输入到浏览器中会发生什么？

  • 域名解析
  • RAP解析将ip地址解析为物理地址
  • TCP三次握手
  • 服务端返回响应
  • 浏览器将响应渲染成页面

11.SSO单点登录：一次登录后，访问其他页面就不再需要登录

  • 用token或者共享cookie实现

12.http版本区别

  • http1.0：无状态无连接，每个请求就建一个连接，每个请求独立
  • http1.1：
    • 1.keep-alive：长连接保活
    • 2.增加host域：运行一台物理机有多个域名(虚拟机情形)
    • 3.支持请求管道化：客户端在收到响应前，继续向服务端发送请求(但是响应需要依次处理)
    • 4.支持分块传输：将服务器响应分成多个块来分次传输，最后客户端再按约定组合
      • 设置头部中传输编码为chunked
      • 每个块第一行是这个块的长度，客户端读到大小为0的块就说明分块传输结束了
      • 目的是服务器可以持续地生成和发送数据，而无需在开始时知道内容的总长度
  • http2.0：
    • 1.二进制分帧：把头部转成二进制的形式传输，并进行分帧，分为头部帧和数据帧(数据帧保持原样，不转成二进制)
      • 注意1.0和1.1的起始行被处理成:xx的形式，并一起放进了头部帧
    • 2.头部压缩：使用HPACK算法对头部进行压缩并转成二进制
    • 3.服务器推送：允许服务端向客户端主动推送以更新资源（常用于推送未来可能用到的静态资源）
      • 之前的1.1是基于请求/响应模型的，所以不能支持
  • http3.0(还未应用)：
    • 1.改用UDP传输，使用QUIC协议控制UDP可靠
    • 2.解决2.0的队头阻塞
      • 队头阻塞指的是，按顺序发a、b、c包，b包里出现丢包，那么即使已经收到了c包也不会去处理，而是要等b包重传后才处理

13.cookie、session和token

  • 持久型cookie存在客户端，本地易被篡改，有name、value、expires(缺省时为会话型cookie)、size、domain、secure等属性
  • session存在服务端，服务器要为每个用户保留session信息，连接用户过多会造成服务器内存压力过大
  • token：客户端后续每次请求中，浏览器会把token作为http header发送给服务器，使用jwt(json web token)加密token是现在主流形式
    • 这种方式的特点就是客户端的token中自己保留有大量信息，服务器没有存储这些信息，而只负责验证，不必进行数据库查询，执行效率大大提高。

14.https的七次握手

  • c->s：SYN
  • s->c：SYN+ACK(服务端进入半连接)
  • c->s：ACK(服务端收到后进入全连接)
    • 这个时候如果全连接队列满了，那么就会丢弃这个第三次握手的ACK，并向client重发第二次握手SYN+ACK
  • c->s：TLS版本号+加密套件列表+希望采取的TLS选项
  • s->c：加密套件+TLS选项+自己证书+公钥
  • c->s：自己证书+对称秘钥(用公钥加密)
  • s->c：FINISH
    • 只要“信任链”可以从当前证书追溯到根CA，浏览器就会认为它是可靠的
    • 根CA(操作系统内置)、中间CA、下属CA(服务器的CA证书)

15.实际抓包中，会发现不是四次挥手而是三次挥手

  • 因为Client端和Server端同时向对方发送了FIN
  • 所以第二次挥手和第三次挥手合并了
  • 这样可以极大地减少断开连接的开销，增加速度

16.TCP四次挥手

  • c->s：FIN(客户端进入fin_wait_1)
  • s->c：ACK(客户端进入fin_wait_2、服务端进入close_wait)
  • s->c：FIN
  • c->s：ACK(客户端进入time_wait，默认2MSL即4分钟)

17.http请求和响应报文格式

  • 第一行
    • 请求是请求行：方法+url+版本，例如 GET /index/htm HTTP/1.1
    • 响应是响应行：版本+状态码+短语，例如 HTTP/1.1 404 Not Found
  • 中间有n行首部行：字段名+值(格式是纯文本键值对)，例如host:www.baidu.com(表示请求资源存在哪个域名上)
  • 最后有个请求体(post、put这类常用)

18.https如何保证服务端可信

  • 1.验证证书没被篡改
    • 客户端将证书的公钥、持有者信息、有效时间等打包，然后进行Hash计算得到一个值h1
    • 客户端对证书的签名用公钥进行解密，得到h2
    • 比较h1和h2是否相等就可以验证证书是否合法了
  • 2.验证证书信任链
    • 用服务端传过来的中间CA去验证服务端CA，再用本机内置有信任的根CA去验证中间CA有效，即构建了信任链

19.https出现的性能下降(非对称解密是大数分解、离散对数，而对称是位运算)

  • TLS额外的四次握手(RSA需要2RTT)
    • 非对称加密算法从RSA改成ECD，这样只需要1RTT
      • 该算法支持客户端在第3次握手后，就发送加密的应用数据
    • 升级到TLS1.3，也可以优化成1RTT
      • 1.3客户端在第一次握手的时候就传椭圆曲线和对应的公钥，这样服务端收到后，选定一个参数并带上服务端这边的公钥。经过1个 RTT，双方手上已经有生成会话密钥的材料
    • 服务器应该将RSA证书换成ECD证书，这样可以减少密钥长度
    • 采用会话重用技术
  • 握手后的对称加密传输
    • 主流的AES等算法已进行优化，且CPU厂商会针对其做硬件上的优化，这方面开销已经极大减少

20.TCP拥塞控制(没有在规定时间内收到ack包、连续收到三个序列号相同的ack包)

  • 发送方维护一个拥塞窗口作为发送的大小
    • 出现拥塞的话要减少这个窗口，否则就增大
  • 有一个慢开始门限，低于用慢开始算法，高于用拥塞避免算法
    • 慢开始：1,2,4,8….翻倍
    • 拥塞避免：1,2,3,4,5,6….+1

21.dns解析过程

22.socket在本机和在网络通信区别

  • 代码写法一样(bind 127.0.0.1即可)，但是实际执行的底层接口不一样
  • 本地不需要经过网络协议栈，不需要打包拆包、计算校验和、维护序号和应答等，只是将应用层数据从一个进程拷贝到另一个进程
  • 实际上这样通信会慢，进程通信还是共享内存最快，本地socket常用于不同编程语言进程间的通信

23.网络攻击方式

  • XSS跨站脚本攻击：攻击者在目标网站上注入恶意代码，当被攻击者登陆网站时就会执行这些恶意代码，这些脚本可以读取 cookie、session、tokens
  • CSRF跨站请求伪造：攻击者诱导受害者进入第三方网站，在第三方网站中，向被攻击网站发送跨站请求。例如伪装银行网页让用户登录，然后拿到用户密码等去登录真正的银行
  • DDos攻击：攻击者对目标网站发送大量的请求造成资源过载，导致服务不可用
  • 中间人攻击：攻击者与通讯两端分别创建联系，并交换其所收到的数据，使两端认为他们正在通过一个私密的连接与对方直接对话
  • Cors跨域攻击：利用Access-Control-Allow-Origin参数配置失误未严格验证，允许非同域站点访问本站资源从而造成跨域问题，即利用cors漏洞

24.CDN加速

  • 由CDN的全局负载均衡器GSLB负责找出离用户最近的可用CDN节点
  • 通过DNS解析把用户的请求引到GSLB上，然后GSLB通过
    • 根据用户ip的地理位置，找最近节点
    • 根据用户用的运营商网络，找同一网络节点
    • 根据请求的URL，找有资源的节点
    • 根据服务器负载状况，找负载最轻节点

25.序列化协议json、thrift和protobuf的区别

  • json
    • 简单开发成本低，体积大
  • protobuf
    • 每个字段都有编号，新添加的字段不影响老结构，解决了向后兼容问题
    • 传输的时候是二进制消息，效率高，但是抓包难读懂
    • 对象冗余，字段很多，生成的类较大，占用空间
    • 不支持动态更改，即不支持实时增删传输的字段数量，要先改pb文件才能传新字段
  • thrift
    • 除了是序列化方案，还包含了RPC框架
    • 包含完整的客户端/服务端堆栈，可快速实现RPC
    • 环境复杂，开发成本高
    • 用IDL接口定义语言，不支持动态更改，要先改IDL文件才能传新字段

26.TCP长连接的保活机制和心跳

  • 保活机制是TCP长连接中为了避免一堆无用连接占据资源设计的，每隔一段时间就会发一个检测包去探测连接另一方是否还处于可用状态
    • 所以即使拔掉了网线TCP连接还是会存在一段时间，直到保活机制进行检测
  • 心跳包是很多应用层协议自带的，比如QQ/MSN等协议
  • TCP传输层断开了连接但是上层可能没感知，所以还需要心跳包，心跳包实质上和保活的检测包没什么区别，心跳包是只含包头的空包，检测包是纯ACK包不含数据

27.http的分块chunk传输

  • 允许将数据分成多个块进行传输，每个块除了数据本身还有自己的长度
  • 发送时先发送数据块的长度，才发送数据本身
  • nagle算法就是尽可能发送大的数据块，并且在收到上一个数据的确认报文前，不会继续发送

28.ipv4与ipv6

  • 都是互联网协议版本
  • ipv4有42亿地址，ipv6有340万亿地址

29.公网ip怎么映射成私网ip

  • 方法一：把有公网ip的机器当作路由器使用，直接访问内网ip
  • 方法二：做端口映射
    • 例如a是公网机器，把访问a的80端口的请求转发到内网b的80端口

30.简单请求和复杂请求

  • 满足这两个条件就是简单字段的就是简单请求，例如
    • 1.get、post
    • 2.头信息是固定的那几种Accept、Content-Type的三种值….
  • 复杂请求是put、delet或者Content-Type字段的类型是application/json，要先进行option预检
  • option预检
    • 浏览器先询问服务器，当前网页所在的域名是否在服务器的许可名单之中，以及可以使用哪些HTTP动词和头信息字段。只有得到肯定答复，浏览器才会发出正式的请求

31.理论上的socket受端口数量、文件描述符数量(linux系统)限制

  • 实际上很难达到理论socket数量，因为系统内存、CPU有限

32.TCP和IP的关系

  • 整个过程是TCP把文件划分成多个数据段，数据段会放入一个IP数据包中
    • 数据段大于网络最大传输单元MTU还会再分割，然后再放入IP数据包中
  • TCP负责保证整体消息的顺序和完整
  • IP负责具体数据包的传输

数据库

1.mysql的引擎有三种

  • InnoDB：mysql默认引擎，用于事务，默认行锁，适合大规模数据，一张表的qps根据实验应该是8000左右
  • MyISAM：不支持事务，适合小规模，默认表锁，mysql之前的老引擎
  • Memory：数据放到内存中，用的索引底层是哈希表

2.b+树(查询时间复杂度logn)

  • 每个节点存多个子节点的指针
  • b+树的深度浅，每次读一个节点只要一次IO，减少了IO次数
  • b+树的IO次数少，并且单个节点默认存16k与磁盘页对齐，这样一次IO就可以传输一个完整节点
  • b+支持范围查询和排序操作
  • 具体实现：
    • 非叶子节点存的是每个子树的最小主键id，这样就可以根据要查的主键id去判断往哪边的子树往下走
    • 叶子节点按主键id有序存放数据，走到某叶子节点后用二分查找来定位到具体的位置
    • 插入需要旋转平衡开销，因为如果索引节点和数据节点某个已满的话需要拆分，如果两个都满了，还需要再往上加一层索引

3.跳表

  • 每个节点存向下和向后的指针
  • 跳表的深度高，同等高度下存的数据要比b+树少
  • 跳表可能出现跨页IO
  • 具体实现
    • 插入不需要旋转平衡开销，直接在底层节点插入即可，而是否需要把这个数据也加到索引里，依靠随机函数即可
      • 因为理论上为了达到二分的效果，每一层的结点数需要是下一层结点数的二分之一，所以底层新增一个节点时，有0.5的概率需要加到第二层索引，有0.5*0.5的概率加到第三层索引

4.索引选型场景问题

  • mysql用b+树实现索引而不是跳表的原因
    • b+树的IO次数少，一是因为节点大小和磁盘页大小对齐一次IO可以传输一个节点，二是b+树深度浅
    • Innodb引擎出现的时候，跳表还没得到广泛应用
  • redis用跳表实现有序集合zset而不是b+树的原因
    • redis在内存中运行，所以层高，IO开销大就不再是劣势
    • 跳表的插入效率高，因为不用像b+树一样需要去旋转平衡
  • 跳表写性能好：插入不需要去旋转平衡，b+树读性能好：层数低

5.Innodb的next-key lock机制解决幻读

  • 里面包含间隙锁gap和记录锁record，间隙锁会锁上记录之间的间隙
  • 比如对5到10行的记录上next-key lock就是由(5, 10)之间的间隙锁和加在10上的记录锁组成，左开右闭(5,10]，即5不加锁，10要加锁

6.数据库的锁底层是怎么实现的，类似间隙锁，xx锁这种

  • InnoDB并没有采用系统提供的锁机制，而是自己封装了操作系统提供的基本mutex互斥量和event信号量来实现锁
  • InnoDB行锁是通过给索引上的索引项加锁来实现的，而不是给表的行记录加锁，通过索引检索数据才使用行级锁，否则将使用表锁

7.Redis是串行但是仍然快的原因

  • Redis是单线程的，减去了CPU切换不同线程的开销，并且Redis是在内存里运行的
  • Redis的多路复用模型是用epoll实现的

8.Redis是基于键值对的非关系数据库，值的数据类型可以是

  • string
    • 底层实现，当成long类型来存(int编码)和动态字符串SDS(emstr编码、raw编码)
      • SDS数据结构
        • len：已使用的字节数量，属于header
        • alloc: 实际分配的buf数组长度，属于header
        • flags: 用来表示header类型，短的字符串用小的header类型，长的用大的header类型，因为len和alloc变长会占更多空间，属于header
        • buf[]: 字符数组，用于存放字符串
          • emstr编码SDS对象和字符串是连续的
          • raw编码SDS对象和字符串是断开的，因为太大了
      • SDS本质上就是一个char*指针，指向buf[]的开始，然后往前读一个字节获取flags，根据flags向前偏移xx去读len和alloc，然后再往自己的后面按照len去读字符串内容
      • 扩容：和vector一样，扩容2倍
      • 删除：缩短SDS只处理len，不处理alloc
      • 不同于C语言中直接用以空字符结尾的字符数组实现方式，但是为了兼容C末尾也会有\0，只是不依赖这个\0来识别字符串，而是依赖len来识别
  • hash
    • 底层实现是压缩列表和哈希表
  • list
    • 底层实现是压缩列表和双向链表
      • 因为压缩列表存储在一块连续的内存上，所以存储效率很高。而双向链表除了保存数据还要存next、pre指针，内存开销大。但是它不利于修改操作，插入和删除操作需要频繁地申请和释放内存。特别是当zipList长度很长时，一次realloc可能会导致大量的数据拷贝
      • redis3.2之后出现了快速列表，单节点用压缩列表来存，不同节点之间用双向链表的形式来连接，头部和尾部不能被压缩
  • set
    • 整数数组和哈希表
  • zset(有序集合)
    • 底层实现压缩列表和跳表
      • 压缩列表底层就是一段连续空间，每个数据有自身和一个长度lenth组成，压缩的意思是原来每个数据都是占用统一大小的空间的，现在改成每个数据只占它数据长度的空间，这样也可以通过偏移来计算地址
  • Bitmaps(位图)

9.跳表的原理是二分查找，所以快。查询、插入、删除的平均复杂度都是log{k}n，k是跳表索引步长

  1. redis的哪种数据结构是有序的
  • zset

11.mysql的MVCC

  • 目的：为了实现事务读数据的时候不需要加锁
  • 实现：InnoDB中的MVCC实现是通过undolog日志实现的
    • 执行更新操作时，会把更新前的数据放入undolog里面，并通过隐藏的回滚指针roll_pointer指向
    • 其他的事务，如果需要查询该记录，就会去undolog里面找这个记录的最新历史版本
  • MVCC最大的好处是读不用加锁，实现读写不冲突，极大地增加了并发性同时保证了事务的隔离性

12.Innodb的隔离级别

  • 读未提交：跳过快照机制，有脏读、不可重复读、幻读
  • 读提交RC：每次读都会更新快照，所有不能解决不可重复读和幻读问题
  • 可重复读RR：只在第一次读的时候生成一个快照Read View，然后后面只有事务内更新了数据才会去更新快照
    • 快照读情况下，根据MVCC机制，用版本号、undolog的方法，可以解决幻读问题
    • 当前读情况下，next-key-lock机制，可以解决幻读问题
      • 当前读的情况下只用MVCC不能解决幻读，要加间隙锁才行
  • 串行：任何读写操作都加锁

13.InnoDB的行锁算法有以下3种

  • 记录锁record-lock：直接在记录上加锁
  • 间隙锁gap-lock：锁定一个范围，但不包括记录本身
  • next-key-lock：锁定一个范围和记录本身，解决幻读

14.聚簇索引和非聚簇索引，Innodb的主键索引是聚簇索引，非主键索引都是非聚簇索引

  • 聚簇索引将索引和数据放一块，b+树叶子节点存的是：索引值+数据，查询快+更新代价大
    • 覆盖索引：聚簇索引(主键)和含有它的索引都是覆盖索引，即查询的数据从索引里就能全部拿到，不用再去数据表里拿
  • 非聚簇索引将索引和数据分开放，b+树叶子节点存的是：索引值+指向主键索引的指针(通常是主键的值，还需要去磁盘里找)，查询慢+更新代价小
    • 回表：查询到非聚簇索引目标值后，但是字段不全还要去聚簇索引里拿完整数据，这个拿的过程就叫回表
    • 如果某次查询的字段都在二级索引里，那么就不用回表了，这样也相当于覆盖索引

15.mysql的最左匹配（注意WHERE子句中的字段顺序并不影响联合索引的使用）

  • 例子，t1,t2,t3建立了一个联合索引，那么实际上是建立了(t1,t2)、(t1,t2,t3)这两个索引
  • MySQL8.0之前一定是遵循最左前缀匹配的，即WHERE条件有t1==xx或者t1==xx and t2==xx时才能用到这个索引来加速检索
  • MySQL8.0出现了索引跳跃扫描技术，假如只查了t2==xx and t3==xx也能去用到联合索引，因为实际上底层会去执行
    1
    2
    3
    4
    xxx WHERE t1 == 1 and t2 == xx and t3 == xx;
    xxx WHERE t1 == 2 and t2 == xx and t3 == xx;
    .....
    直到扫描完t1字段所有的唯一值，最后将结果合并返回

16.redis是k-v结构，怎么实现复杂查询

  • 一般可以使用set的交并集来实现多表联查需求，但是这样其实就抛弃了redis的优势，一般还是不建议在redis里面进行复杂查询，应该存放直接能使用的值

17.mysql的主从复制
主从复制的基本原理：slave会从master读取binlog来进行数据同步

  • master将改变记录到二进制日志binlog，这些记录过程叫做二进制日志事件binlog events
  • slave将master的binlog events拷贝到中继日志relay log
  • slave重做中继日志中的事件，将改变应用到自己的数据库中。MySQL的复制是异步且串行化的

18.Redis实现数据持久化的方法

  • RDB：把当前的数据生成快照，保存到硬盘里，有手动触发和自动触发两种
  • AOF：用日志记录每次执行的写命令，重启时重新执行一遍AOF里的记录(同比mysql的binlog、redolog)

19.数据库慢查询的原因和检查思路

  • 没有用索引
  • 内存不足
  • 查询的数据量过大
  • 检查思路
    • 使用explain查询
    • 开启慢sql日志

20.解决慢查询用explain检查sql是否有问题，关注以下字段

  • type：用来表示该sql底层是怎么扫描的，
    • all全表扫描
    • index全索引扫描
    • null表示不用去表里查可以直接得到结果
  • possible_keys：可能用到的索引列
  • key：实际用到的索引列
  • Extra：底层用的是哪种检索方式
    • Using where用where来处理结果
    • Using index condition表示用索引

21.乐观锁和悲观锁

  • 乐观锁：默认不发生并发冲突，只在提交时检查版本号
    • 有可能会出现两个事务读同一行后再写入的未知结果
  • 悲观锁(当前读)：默认发生并发冲突，需要关闭mysql的自动提交，并在事务中用select…for update用排他锁锁住数据，其他事务需要在该事务提交后才能去写这条数据
    • 效率比较低
  • 并发冲突少时选择乐观锁，并发冲突多时选择悲观锁
    • 因为乐观锁出现冲突只能往上抛出，然后重试，而悲观锁可以避免冲突的发生

22.mysql如何管理脏页

  • 用buffer pool来做缓存加速
  • 更新数据的时候会把buffer pool里面的页更新，然后把该页标记为脏页
  • 后台线程再将脏页写入到磁盘里面
    • 用一个flush链表来存所有脏页，后台线程遍历这个链表就可以把脏页写入磁盘了
    • 触发：redo log或者buffer pool满了，数据库空闲或者关闭
    • 数据库性能波动，可能就是后台正在写脏页导致的

23.buffer pool是如何处理全局搜索导致的LRU污染

  • 新增一个old区域
  • 当某页第一次被访问时，直接放入old区域
  • 后续访问的时间 - 第一次访问时间 > 一定时间，才能将该页放入LRU的热点young区域
    • 原理是：每次从页中取一条记录，即认为访问了一次该页。所以在全表扫描时，InnoDb会认为对该页短时间进行了多次访问
  • 并且新增了，只有young区域后1/4的页被访问才将其移到首部

24.null值和索引

  • 主键索引不允许为null，唯一索引允许有其中一行为null
  • 破坏联合唯一索引的办法就是，插入(null, 1)、(null, 1)这样的数据，出现重复的组合联合索引就会失效

25.怎么加索引，什么时候要去加索引

  • CREATE INDEX xx ON 表名(列名)
    • 唯一索引用UNIQUE INDEX
    • 联合索引在列名里填上多个列名即可
  • alter table 表名 add 索引类型 列名
  • alter table 表名 drop xx

26.为什么myisam查询比innodb快

  • innodb寻址要映射到块，再到行，myisam记录的直接是文件地址，定位比innodb要快
  • innodb需要维护MVCC一致，需要额外开销
  • innodb要缓存数据块buffer pool，所以其中还有块在缓存中换进换出的开销

27.Hive是怎么实现大数据查询的，mysql为什么不行

  • Hive用MapReduce去分布式查询
  • Hive是将结构化的文件映射成一张表，这个文件是在HDFS上的

28.redis的hash map怎么扩容(类似vector扩容)————渐进式哈希

  • 底层有两个dict，正常请求写入dict1中
  • 数据增加触发扩容，给dict2分配空间(dict1的两倍)
  • 然后一部分一部分地从1迁到2，最后再把dict1指向dict2，dict2指向新创建一个空白哈希表，等待下一次扩容
    • 一部分一部分迁移，当用户新增、删除、查询dict1的记录完成后会顺便把这个记录迁移道dict2中，在这个过程中如果在dict1中找不到key，再去dict2中找
    • 渐进式哈希过程中，新增k-v会直接放到dict2
  • dict存着一个used字段，每次单步rehash完成的时候，最后都会检查dict1的.used 是否变成了0，变成0后就会去释放掉老表，交换老表新表的指针，rehashidx置为 -1

29.MySQL的三种日志

  • Binlog：MySQL本身具备，二进制日志，存对数据库的所有操作，用于主从复制和数据恢复
    • 存的是全量数据(操作的全量，如果空的从库要重建的话还要一个原始数据的备份)
  • Redolog：Innodb独具，存对数据库的所有操作(物理层面)，例如页的修改等，用于数据库崩溃将数据库恢复到上一次commit
    • 只存了部分数据，边写边擦除已经写入到磁盘的数据
    • 因为是追加写，所以还实现了顺序写的功能，比起随机写(每一次写都要去找位置)来说极大提高效率
  • Undolog：存本次操作前的数据库状态，用于回滚，是MVCC的实现方式

30.redis String底层

  • 三种实现方式：int(内容全为数字时使用)、SDS

31.为什么不直接放进进程的内存里，而额外使用了redis

  • 进程之间需要通讯，不如直接用redis快
  • 自己去实现一份缓存不一定有Redis好
  • 在分布式架构中Redis能做同步

32.微博热度排行榜用的是redis的有序集合zset

  • zset是在set基础上，每个member关联一个score值（作为排序的参照）
  • zrevrange rank 0 9表示返回名为“rank”的有序集合的分数最高的前10名的member
    • zrevrange改成zrank就变成了分数最低的前10名

33.redis如何删除过期的键(惰性删除+定期删除)

  • 定时删除，每隔一段时间随机去遍历部分key，如果有过期的就删除
  • 惰性删除，访问某个key的时候如果发现它过期了，就删除
  • 使用LRU算法进行删除
    • 传统的LRU算法中如果一个中间节点被访问就要移动它的位置到头部去，一旦访问量太大就会带来很大的移动开销
    • Redis做了修改，去除了移动节点这一步开销，具体为：
      • 给每个节点设置一个最新访问的时间戳
      • 需要淘汰时，第一次随机拿出N个节点，然后把时间戳最远的淘汰，后面再需要淘汰就把一个节点放进这个集合里再把时间戳最远的淘汰

34.事务时并发控制的基本单位，它是一个操作序列，这些操作要么都执行要么都不执行(ACID)

  • 原子性：事务中的所有元素作为一个整体提交或回滚，不允许分割。通过undolog实现
  • 隔离性：每个事务相互独立，不能以任何方式影响别的事务(即同一时间只允许一个事务请求同一数据)。乐观、悲观锁+MVCC实现(即undolog)
  • 持久性：事务一旦提交，那么对数据库中数据的改变就是永久性的，即使系统故障也一直保留，真实地修改了数据库。通过redolog日志实现
  • 一致性：事务完成时，数据库完整性约束没有被破坏(例如A向B转账，不可能出现A扣了钱，B却没有收到的现象)。通过原子性、隔离性、持久性实现

35.联合唯一索引

  • 在表里设置a和b有联合唯一索引后，a、b都可以各自重复，但是不允许(a,b)组合起来重复，这时插入某个重复(a,b)的记录会报错
  • 如果(a,b)出现重复组合那么这个索引就失效了，做法有a、b其中一个为null的话就可以插入重复的组合了
  • 如果是普通联合索引，那么是允许重复组合的，因为B+树按序排列，所以重复组合一定会被放在一起，这样只要遍历完所有重复组合即可确定答案

36.数据库字段一般不允许为null

  • 会占用额外空间，NULL列在行中需要额外的空间以记录其值是否为NULL。对于MyISAM表，每个NULL列都多占一位，四舍五入到最接近的字节
  • 对允许为null的记录进行查询会出现以下错误：
    • sum(字段名)函数没统计到任何记录时，会返回 null 而不是 0
    • count(字段名)，不会统计为null的记录
    • 使用 =、<、>比较操作符比较 NULL 的结果总是False。需要使用IS NULL、IS NOT NULL或ISNULL()函数来比较

37.redis设置分布式锁

  • 使用setnx
  • 加锁：发送SETNX命令，将 key 设置为 lock，value 设置为一个随机字符串（作为锁的唯一标识）。如果返回 1，表示加锁成功；如果返回 0，表示加锁失败。
  • 解锁：发送GET命令，获取 key 的值，并与自己保存的随机字符串比较
    • 如果相同，表示是自己加的锁，就可以向 Redis 发送 DEL 命令，删除 key，释放锁
    • 如果不同，表示是别人加的锁，就不做任何操作

38.数据库冷热分离

  • 冷库存放的是已经走到最终状态的数据,同时也是不常使用的数据
  • 热库存放的未走到最终状态的数据,还需要在进行变更的、经常使用的数据

39.InnoDB里面有四种线程

  • 主线程，类似于主协程的作用，核心线程，用于调度其他线程，维护核心功能，挂了数据库就崩溃
  • I/O线程，默认读线程4个，写线程4个
  • Purge线程，用于修改数据成功后删除undolog记录的线程
  • 清除脏页线程，用于把脏页刷入磁盘的线程

40.redolog和checkPoint怎么搭配的

  • checkPoint有两种
    • 全量检查点：所有脏页刷入磁盘，数据库关闭时会触发
    • 模糊检查点：把部分脏页刷入磁盘，运行时会触发
  • checkpoint是日志对数据页刷新到磁盘的操作的检查点，通过LSN号保存记录，作用是当发生宕机后再次启动时会将该checkpoint之后发生的事务修改恢复到磁盘
  • checkpoint记录在redo log第一个文件的头部，维护最新的LSN
    • 该LSN记录当前页最后一次修改的LSN号
    • 以保证崩溃后重做的幂等性，避免崩溃发生时可能会出现指令重复执行的问题

41.执行update的流程

  • 在buffer pool里找，找不到就从磁盘里面读这条数据后放到buffer pool里
  • 写undolog记录修改前的值(这一步完成后崩溃，就依赖checkpoint来保证恢复的幂等性了)
  • 修改buffer pool里的数据
  • 写redolog和binlog
  • 最后数据写入硬盘

42.Es倒排索引的原理

  • 当数据写入ES时
  • 会通过分词被切分为不同的term
  • ES将term与其对应的文档列表建立一种映射关系，即倒排索引

43.三种错误读

  • 脏读：事务B读取到了未提交的正在执行的事务A中的数据，读提交隔离级别可以解决
  • 不可重复读：事务B两次读取间隔中，有一个事务A对同一数据就行了修改(针对同一数据项)，可重复读隔离级别可以解决
  • 幻读：事务B两次读取的间隔中，有一个事务A对同一数据就行了插入、删除(针对数据个数)
    • RR隔离事务启动后第一行select会进行一个快照，然后进行快照读
    • 然后select ..for update是当前读，当前读会出现幻读，可用间隙锁来解决，间隙锁是针对插入、删除数据的锁

44.当前读和快照读是什么，场景有什么区别

  • 快照读会生成快照readview，是MVCC+undolog实现的，读提交和可重复读默认快照读
    • 普通的select每次都会生成一个快照
  • 当前读，用next-key-lock邻键锁来实现(gap+record)，读未提交和串行化默认当前读
    • select xx for update、update、delete、insert这种手动上锁的也是当前读

45.R树是B树扩展到多维层面的数据结构

46.B+树的相关计算，n为总数据数，len为一个节点能存的数据数

  • 叶子节点数：n/len
  • B+树层高：log(n/len) + 1

47.单一张表的最佳数据量如何确定

  • 多种因素：硬件资源、查询频率、表结构，制约单表查询数据量最大的底层因素是索引
  • 一般数据量为1000w以内性能比较好，这样B+树一般是3层
  • 因为mysql如果内存充足会把索引放内存里面，如果数据量过大导致索引不能全放内存，那么就会产生磁盘I/O导致开销过大

48.设计数据表的三大范式

  • 第一范式：每一列只存一个值，例如姓名要是”张三”，而不是”张三、李四”
  • 第二范式：如果主键是多个列组合的，那么所有数据要全部依赖而不是部分依赖，例如主键是省份和城市，那么就应该存xx省xx市的人口，而不是存xx省的人口
  • 第三范式：列必须依赖主键，而不随非主键字段而改变，例如主键是员工id，那么就不能把员工的部门经理放这张表，因为部门经理这个字段更多依赖部门id

49.count()

  • count(xx)的原理其实是去整张表里找xx不为null的记录数
  • count(1)等于去找1不为null得到记录数，因为1永远不为null，所以count(1)的结果就是表内的总记录数
  • 而数据库在执行count(*)时底层会自动转换成执行count(0)，所以实质上count(*) == count(1)

50.索引失效情形

  • 联合索引不满足最左匹配
  • 使用”%like”模糊查询
    • 因为B+树是按索引值有序排列，前缀不确定自然就没法办法走索引
  • 对索引字段进行表达式、函数计算
  • or的前后不全是索引字段

51.主从复制的好处

  • 读写分离：主库写操作，从库读操作
  • 数据分发：根据地理位置等要素提供更快访问速度
  • 隔离：便于在从库上进行计算量大的数据分析任务和开发人员搭建测试环境
  • 备份、故障切换

52.布隆过滤器

  • 用来高效判断一个元素是否是某个集合的成员
    • 有一定的误报率，即可能会把不存在的元素误认为是该集合里的成员
  • redis用它来解决用户查询一些不存在db里的key时出现的缓存穿透问题，在实际请求db层之前就进行拦截

Linux和git

1.Linux下查找文件用什么命令

  • find “xx”表示在当前目录及其子目录查找xx

2.Linux命令

  • top：用于显示进程和Linux整体性能
  • ps：查看当前运行进程
  • kill：终止进程
  • chmod：修改文件或目录的权限

3.git blame用于查看指定文件的某行号范围的所有修改者，包括很久以前的版本