自我介绍

面试官您好,我是湖北师范大学 17 级应届本科生李国威,大学所学专业是计算机,从入校就开始自学编程,大二加入了学校的 Jplus 实验室,参与了教师工作量统计系统的开发以及新人培训工作,后面又自学了 Go 语言,用 Go 语言写了两个练手项目,一个是模仿 Google 开源的 GroupCache 实现的一个分布式缓存库,并且对原项目热备功能做了增强,代码开源在 Github 平台,另一个是分布式的任务调度系统,通过分布式部署,任务保存在 etcd 集群中,并发的调度 cron 定时任务,提高整体的调度性能,代码也开源在 Github 平台上

同时我也有一个从大一就开始维护的个人博客,平时也会将学习的过程记录在博客上与他人分享

此次面试想应聘贵公司的 后端开发岗位

项目

湖师教师工作量统计系统

教务处委托我们实验室实现的,为了方便全校教师统计工作量以及教务处审核,项目采用 Java SpringBoot 以及 MyBatis 编写,我主要负责项目的登录模块和本科生实践教学工作量统计模块

项目本身没什么难度,但是在测试过程中发现一个有意思的 bug,在登录的过程中会偶尔卡死,起初我以为是网络的问题,因为我们用的是我的云服务器上的数据库,但是当我查看了控制台的输出发现请求根本就没有到达 dao 层,在前端 controler 层就 hang 住了,但是由于他们测试过程中发现这个 bug 后就直接重启服务了,导致我过去的时候 bug 以及消失了!!!所以我们当时在机房搞了几小时才复现出 bug,然后我马上用 jvisualvm 直接 dump 除了线程堆栈,然后发现有一条线程 BLOCK 在了 println() 的一条语句上,println() 是加了锁 synchronized,锁的是当前的实例 PrintStream 的实例,然后我继续查看堆栈信息发现占有该锁的一个 tomcat 的 http 线程正在 RUNNING,但是它也并没有输出任何信息,最后去网上根据已有的关键字查了一下,然后发现这里其实 windows 的 cmd 窗口的问题,我们启动后有人点了一下 cmd 窗口,导致 cmd 的输出被中断,不再允许写入,这就导致这些 write 线程 hang 住,这个问题解决方案也很简单,换成 Linux 平台就可以了,整件事给我的收获就是线上遇到这种 bug 不要急着重启服务,至少得先把线程堆栈 dump 下来再说,不然我们也不至于后面复现搞这么长时间

Gacache 缓存库

模仿 Google 开源的 GroupCache 实现的分布式缓存库,项目的特点就是只支持 get 操作,不支持 update/delete/ttl,当内存满的时候只能通过 lru(LRU-K 优化)去淘汰最近最少使用的,所以它适用的场景就是存储长期不会改变的数据

同时正是因为舍弃了 update,delete 等功能,所以 cache 可以支持热点互备的功能,分布式的实现也更加容易,不用考虑并发读写的问题

具体项目的实现,首先这是一个分布式的缓存库,所以需要考虑数据分片的问题,常规的做法可以采用取模的方法,将 key 的 hash 值与节点数量进行取模得到 key 映射的节点,这样就可以使得数据的分配更加均匀,但是这样做的问题是,如果节点的数量发生变化,那么所有的 key 都需要重新映射,扩展性较差,所以这里采用了一致性 Hash 算法进行数据分片和节点的选取,将所有的整数范围(2^32-1)内的 hash 值构成一个环,然后将节点根据 ip 和端口信息 hash 后有序的放入环中,同时为了避免数据倾斜的问题,我们同时生成多个该节点的 hash 值,作为虚拟节点,同时记录虚拟节点和真实节点的对应关系,然后当我计算某个 key 的映射时,将 key 的 hash 计算出来,然后直接在环中定位,顺时针找到离他最近的节点,然后返回其对应的真实节点就是该 key 的映射,这样当节点数量发生变化的时候,就只有少量的数据需要做迁移

各个节点之间通过 Http 通信,并且使用 Protobuf 序列化数据,每个节点既是客户端也是服务端,当请求随机落在某一个节点上时,首先会判断本地有没有,如果没有就会通过一致性 hash 去选择节点,如果节点是自己就会直接从 DB 中拉取数据然后缓存在当前节点上,否则去一致性 hash 所选择的其他节点去请求数据,最后返回给调用者

作为一个缓存库其实还存在一个问题就是缓存击穿的问题,如果一个热点 key 突然过期,那么就可能会导致大量请求直接打到 DB 层压垮 DB,而常规的解决方案有两种:

  1. 缓存永不过期,类似 Redis 中的惰性删除,仅仅设置逻辑过期时间,这样当访问一个过期的 key 时,请求不会直接打到 DB,然后我们通过后台异步线程去更新缓存,这样做用户延迟是最低的,但是可能会有数据的不一致,有的线程读取的仍然是老数据
  2. 互斥锁,当多个请求同时去 get 热点数据的时候,当第一个线程请求数据的时候进行加锁,其他线程阻塞,直到第一个请求到数据后进行热点 key 重建然后释放锁,其他请求就直接从缓存中 get 数据,不用再去 DB 请求数据

我采用的是第二种方案,因为我的这个 cache 是不支持主动的删除操作的,所以你无法控制 key 何时会被删除,自然也就无法保护 DB

除此之外我针对原项目的热点互备功能也进行了简单的增强,热点互备这里主要针对就是向某个节点请求该节点上没有的数据,那么该节点就会频繁的通过 http 去向其他的节点去请求数据,而网络请求本身也是一个比较耗时的操作,这样就可能使得节点的网卡成为热点 key 的瓶颈,所以需要进行热点互备,将这些 key 直接备份在当前节点上

但是在 GroupCache 的实现中,这里是采用的随机的做法,需要从其他节点获取的 key 有 1/10 的机会被缓存在当前节点上,从大样本的角度上来讲确实也是可行的,但是注意到这行代码上有一个 todo 的标签,并且注释中有写到,可以利用 QPS 去判断热点,所以我按照这个思路做了一些改动,首先封装了一个 KeyStat 的结构,包含了一个首次请求时间,以及一个用访问次数,并且用 Atomic 包实现了原子更新操作,当第一次获取的时候构建出 KeyStats,记录下当前时间,后面再请求该 key 的时候就利用原子包对访问次数做++,当达到我们预设的 QPS 阈值后就会被直接存入当前节点,然后将对应的 KeyStats 删除,经过我自己的测试也确实达到了我想要的效果

高性能任务调度系统

分布式的 cron 定时任务调度系统,任务保存 etcd 集群中,多个节点可以并发的调度其中的定时任务,整个系统划分为两类节点,分别为 Master 节点,和 Worker 节点

其中 Master 节点功能较为简单,主要就是负责和 Etcd 交互,对任务进行增删改查,从 DB 拉取任务执行日志,并且实现一个 Web 界面方便用户操作

Worker 节点就负责具体的调度和执行任务,主要分为几个模块,首先是一个** JobManager 任务管理器,这个模块内会有专门的协程去负责监听 etcd 对应目录的辩护,比如 save 目录发生了 PUT 事件,就说明有新增加的任务,就会将新的任务封装成一个 Event 然后通过 channel 传递到 **Schedule 调度器 模块,调度器会监听对应 channel 中的消息,然后根据 Event 的类型进行相应的处理,比如如果是 PUT 事件,那么就会将任务 包装后(这里就用到了 cronexpr 库对 cron 表达式进行解析,实现精细的秒级调度) 添加到 任务执行计划表 中,并且遍历任务计划表,执行到期的任务,并且统计下一次将要过期的任务的倒计时时间,然后设置定时器,进行精确的超时等待,避免频繁的遍历任务表消耗 CPU。当任务到期时,调度器首先会对任务判重,与之对应的有一个 任务执行表,如果当前任务正在执行过程中那么就会跳过本次调度,原生的 Linux Crontab 就没有判断重复的过程,如果定时间隔小于实际执行时机就会导致任务重复执行,就可能会造成一些问题

当确定任务并没有正在执行就会将任务交给 Executor 执行器 模块,这里就涉及到一个任务并发抢占的问题,会多个节点同时去执行同一个任务的问题,所以这里借助了 Etcd 手动实现了分布式锁,其实这里有一个小的考虑,本来是打算直接使用 EtcdV3 客户端 Concurrency 包提供的一个分布式锁,但是在看了它的实现后发现并不适合我的业务

官方的分布式锁是采用的一种 公平等待 的模式,创建锁的时候指定一个公共的前缀,然后拼接上当前节点的信息作为 key 插入 etcd 中,所有节点插入的 key 会按照 revision 排队,先来后到,排在前面的节点会先获取锁,其他的只能先等待,这样就达到了一个 公平锁 的效果,同时每个节点只需要监听他的上一个 revision 是否被删除就行了,如果被删除就说明上一个节点已经释放锁了,那么当前节点就会结束阻塞获取到锁,这样避免了 惊群效应,其实我感觉这个和** CLH 锁**的实想是一致的(分布式的 CLH 锁),也就是 Java 中 AQS 底层的实现机制,将竞争分散到各个节点上

但是这样的方式,每个节点获取不到锁会等待前一个节点释放锁,而在我的项目中,多个节点争抢的其实是 某个任务,某个时刻的执行权 ,当该时刻过去的时候这把锁其实就没意义了,其他的节点此时不应该继续等待,而是应该转向指向其他的任务,这样才能充分利用分布式的优点,并发的调度任务,而不是在这一棵树上吊死,所以在我后面利用 etcd 的 租约和事务 机制以 lock 前缀以及任务名字,实现的分布式锁中枪锁失败会直接返回,不再争抢锁(偏向的问题,如果问优化可以说说)

后面再实现任务强杀的过程中还发现了一个有意思的 bug,就是我的任务强杀后任务并不会发生返回,仍然会继续指向,直到任务结束,然后我写了个类似的最小 Demo,利用 context 取消任务,复现了 bug,起初以为是平台的问题,切换到 Linux 平台上发现问题仍然存在,然后我 pstree 查看了进程树,发现在我强杀后我的 shell 进程确实被 kill 了,但是我的任务执行的时候 shell 创建了一个子进程,这个子进程并没有被杀死,而是成为了孤儿进程,被 init 进程收养了,其实这个时候我就意识到这应该不是我的问题,可能是 Go 本身的问题,然后我看了 go 下源码,发现在 go 语言在这里的实现中,会创建一些 pipe 用于和 shell 进程通信,返回 out,err 一些信息, 而 shell 进程在 fork 子进程的时候会复制父进程的页表 ,所以 pipe 的文件描述符也会被子进程持有,所以当 kill 父进程后,pipe 仍然存在,写入端并没有关闭,而 Golang 的实现中对应的 goroutine 也会一直等待 pipe 写入端的信息或者 pipe 关闭,进而了导致无法 kill 任务的情况

解决的方案也很直接,当强杀任务的时候,连同 shell 进程和所有子进程一起当作一个进程组设置 pgid,然后利用 systemcall,kill 整个进程组,最终解决了 bug,但是这种方案仅仅适用于 Linux 平台,Windows 平台上暂时没找到好的解决方案

我在官方的 gihub 上搜了下,也搜索到了相关的 issue,这个问题已经存在很久了,可能会在 Go2.0 的时候修复

MySQL

Innodb vs MyISAM

  • MyISAM 不支持事务
  • MyISAM 只有表锁,不支持行锁
  • MyISAM 不支持外键
  • MyISAM 数据和索引分离,索引叶子节点是一个指针指向具体的数据块

    事务

    事务四大特性:ACID(Atomicity、Consistency、Isolation、Durability,即原子性、一致性、隔离性、持久性)

原子性:事务是最小的执行单位,不允许分割。事务的原子性确保动作要么全部完成,要么完全不起作用;

隔离性:多个事务并发的操作的时候,各个事务之间的状态不会相互影响,数据保持独立

持久性:事务提交后对于数据库的改变是永久的,应该保存在磁盘上,即使数据库发生故障也不影响

一致性:保证事务从一个有效的状态转移到另一个有效的状态,而有效指的其实就是我们在数据库中预先定义的规则,比如余额不能扣减为负数等,而,一致依赖 AID,实际上一致性的保障更依赖于应用层也就是程序员

隔离性 & 隔离级别

隔离级别实际上就是为了应对多个事务并发执行所可能产生的问题,当数据库上有多个事务同时执行的时候,就可能出现脏读(dirty read)、不可重复读(non-repeatable read)、幻读(phantom read)的问题,为了解决这些问题,就有了“隔离级别”的概念。

不可重复读取侧重 update,而幻读侧重 insert

  1. 读未提交(RU):一个事务还没提交时,它做的变更就能被别的事务看到。
  2. 读提交是指(RC):一个事务提交之后,它做的变更才会被其他事务看到。
  3. 可重复读是指(RR):一个事务执行过程中看到的数据,总是跟这个事务在启动时看到的数据是一致的。当然在可重复读隔离级别下,未提交变更对其他事务也是不可见的。
  4. 串行化(SERIALIZABLE):,顾名思义是对于同一行记录,“写”会加“写锁”,“读”会加“读锁”。当出现读写锁冲突的时候,后访问的事务必须等前一个事务执行完成,才能继续执行。

redo log

MySQL 中的 WAL(wtite-ahead logging)技术的实现,用来保障事务的持久性,关键点就是先写日志再写磁盘,所有的修改操作在提交之前都需要先写入 log 中,避免事务提交后落盘时发生故障,导致数据丢失,这样在数据库异常重启后之前提交的记录都不会丢失(crash-safe)

在文件系统中 WAL 通常被称为:日志式文件系统(journaling )Ext3,4 都支持

为什么不在事务提交前将修改的所有页面直接刷新到磁盘?

  1. MySQL 是以页为单位进行磁盘 IO 的,可能只修改了一条数据,但是依然需要刷新整个数据页到磁盘,效率会比较低,而 redo log 只需要记录修改了那些东西(物理日志:将第 0 号表空间的 100 号页面的偏移量为 1000 处的值更新为 2)
  2. 刷新到磁盘是随机 IO,效率比较低,redo log 是按照顺序写入磁盘的,并且可以分组提交,同时还有redo log buffer的存在,可以进一步缓解磁盘 IO 缓慢的问题(log buffer 中的数据会在事务提交前刷盘)

    undo Log

    保证原子性,事务执行过程中可能会遇到各种错误,比如服务器突然宕机等,又或者程序员需要在执行过程中处理异常情况需要手动ROLLBACK,这些会导致事务执行一半就结束,所以为了保证原子性,我们需要回滚数据到事务执行前,让事务看起来什么都没做

    总结来看其实 redo log 是保证事务提交后的持久性,而 undo log 是保证事务执行过程中的原子性,所以事务提交后 undo log 就没用了回被系统回收

    binlog

    redo log 是 InnoDB 引擎(引擎层次)特有的日志,而 Server 层也有自己的日志,称为 binlog(归档日志)。

MySQL 的二进制日志 binlog 可以说是 MySQL 最重要的日志,它记录了所有的 DDL 和 DML 语句(除了数据查询语句 select、show 等),以事件形式记录,还包含语句所执行的消耗的时间,MySQL 的二进制日志是事务安全型的。binlog 的主要目的是复制恢复

statement 格式下,记录到 binlog 里的是语句原文。row 格式下,记录那一条记录被修改了,修改成什么样了,所以 row 回更占空间,但是主从复制的时候不容易出现问题,mix 格式就前两者的混合

两阶段提交

由于存在 redo log 和 binlog ,而他们两是相互独立的。而事务提交必须确保两者同时有效。不然会出现不一致的情形。
image.png
将 redo log 的写入拆成了两个步骤:prepare 和 commit,这就是”两阶段提交”。

一阶段:InnoDB redo log 写盘,InnoDB 事务进入 prepare 状态

二阶段:如果前面 prepare 成功,binlog 写盘,那么再继续将事务日志持久化到 binlog,如果持久化成功,那么 InnoDB 事务则进入 commit 状态(实际是在 redo log 里面写上一个 commit 记录)

主从复制:

  1. Master 将数据改变记录到二进制日志 (binary log) 中
  2. Slave 中的 IO 进程连接上 Master,并请求从指定日志文件的指定位置之后的日志内容
  3. Master 接收到来自 Slave 的 IO 进程的请求后,负责复制的 IO 进程会根据请求信息读取日志指定位置之后的日志信息,返回给 Slave 的 IO 进程。返回信息中除了日志所包含的信息之外,还包括本次返回的信息已经到 Master 端的 bin-log 文件的名称以及 bin-log 的位置
  4. Slave 的 IO 进程 接收到信息后,将接收到的日志内容依次添加到 Slave 端的relay-log文件的最末端并将读取到的 Master 端的 bin-log 的文件名和位置记录到master-info文件中,以便在下一次读取的时候能够清楚的告诉 Master 从某个 bin-log 的哪个位置开始往后的日志内容
  5. Slave 的 Sql 进程 检测到 relay-log 中新增加了内容后,会马上解析 relay-log 的内容成为在 Master 端真实执行时候的那些可执行的内容,并在自身执行

    和 redolog 区别

  6. redo log 是 InnoDB 引擎特有的;binlog 是 MySQL 的 Server 层实现的,所有引擎都可以使用。
  7. redo log 是物理日志,记录的是“在某个数据页上做了什么修改”;binlog 是逻辑日志,记录的是这个语句的原始逻辑,比如“给 ID=2 这一行的 c 字段加 1 ”。
  8. redo log 是循环写的,空间固定会用完;binlog 是可以追加写入的。“追加写”是指 binlog 文件写到一定大小后会切换到下一个,并不会覆盖以前的日志。

    MVCC

    MVCC(Multi-Version Concurrency Control ,多版本并发控制),使得在 RC 和 RR 两种隔离级别下使得不同事务的读写操作可以并发执行从而提升性能

    这里指的读是 快照读,也就是普通的 select 语句,如果是 update 之类的依然是要加锁的 当前读

MySQL 中每条记录在更新的时候都会记录一条 undo log,这些 undo log 会通过 roll_pointer 成一个单链表,称之为版本链,每条 undo log 会记录当前创建该版本的事务 id

在 RC 和 RR 级别下,查询需要用到ReadView视图,其中包含了:当前活跃的事务 m_ids活跃事务 id 中最小的 min_trx_id,以及下一个分配的事务 id(max_trx_id)可以理解成最大事务 id,然后去版本链中依次找,如果

  1. 某个版本(undo log)的事务 id 小于Readview中的最小事务 id(min_trx_id),说明该版本事务已经提交了,可以访问。
  2. 事务 id 大于最大 id(max_trx_id),说明该版本的事务在ReadView之后才创建,所以不能访问
  3. 事务 id 在ReadView记录的当前活跃事务 ids 中,说明创建改版本的事务仍然活跃,不能访问,否则说明已经提交了,可以访问

而 RU 和 RC 的区别就是生成 ReadView 的时机不同,RC 在事务中每次查询都会创建 ReadView,所以 RC 级别可以读取到其他事务提交后的版本(提交后再查询,重新生成 ReadView 就没有之前提交了的事务 ID 了)

而 RR 只在事务开启的时候创建一个 ReadView,所以无论其他事务做什么改动当前事务都读取不到(其他事务 id 要么在 m_ids 中要么就大于 max_trx_id)

RR 级别能解决幻读问题么?

首先 RR 能解决可重复读,但是幻读呢?这个问题其实每个人看法都不同

索引

索引分类

从数据结构划分

  1. B+ Tree 索引:内节点存放目录项,叶子节点存放数据,各个页之间以双向链表链接,页内数据以单链表连接,整个叶子节点数据都是按照索引 key **有序存放的,同时每个页还有页目录**,可以通过页目录二分搜索快速定位记录

    (B 树不支持范围查询,而 B+树叶子节点内数据是由链表串起来的,范围查询较方便,而 avl 或者 RBTree 属于二叉搜索树,多在内存中使用,文件系统中由于深度过高,会导致 IO 效率低下)

  2. Hash 索引(Hash 索引快但是不支持范围查询,也不支持排序)

  3. FULLTEXT 索引

从物理存储划分

  1. 聚集索引
  2. 非聚集索引

    聚集索引的叶节点就是数据节点,而非聚集索引的叶子节点仍然是索引节点,但是有一个指针指向对应的数据块。MySIAM 的索引实现就是非聚集的,索引和数据是分开的,而 Innodb 的索引即数据,Innodb 会自动利用主键帮我们创建聚集索引,一张表聚集索引只能有一个,其他的都是二级索引(非聚集索引)

从逻辑角度

  1. 主键索引
  2. 普通索引(单列索引)
  3. 多列索引(复合索引)
  4. 唯一索引 & 非唯一索引

    索引优化

  5. 索引不是越多越好:首先空间上每个索引都会建立一颗 B+Tree,空间消耗不容忽视,其次时间上来说,索引太多当我做修改操作的时候设计到的 B+Tree 也就更多,每个相关的 B+Tree 都需要维护,效率可想而知
  6. 全值匹配:搜索条件和索引列完全一致(顺序不一致也可以,会有查询优化器调整,但是最好不要这样做,没有意义)
  7. 匹配左边的列:搜索条件和索引列左边部分一致(顺序也要一致)
  8. 匹配列前缀:对于一些字符类型的索引列,我们可以通过只匹配前缀就能用到索引,比如我们找所有名字 AB 开头的人 SELECT * FROM stu WHERE name LIKE "AB%"这样也是可以用到索引的,因为字符的排序本身就是通过前缀一一对比的
  9. 匹配范围值:如果对多个列同时进行范围查找的话,只有对索引最左边的那个列进行范围查找的时候才能用到 B+树索引,因为通过前面列范围查询的结果不一定是按照后面列的顺序来的
  10. 用于排序:当使用联合索引时需要注意顺序要一致
  11. 用于分组

建立索引的考虑:

  1. 只为用于搜索,排序或者分组的列建立索引
  2. 为列的基数大的及案例索引(基数指列不重复数据个数,一个列只有两种值 0,1 就没有建立索引的必要)
  3. 索引列的类型尽可能小
  4. 让主键具有AUTO_INCREMENT,让存储引擎自己为表生成主键,而不是我们手动插入,因为 B+Tree 是按照索引列顺序插入的,如果数据很乱的话就会导致前面一个,后面一个,造成页分裂记录移位,损耗性能

索引下推(ICP:index condition pushdown)

MySQL5.6 引入的优化,有的时候我们的查询语句虽然出现了索引但是确无法完全利用索引
SELECT * FROM s1 WHERE key1 > 'z' AND key1 LIKE '%a';
比如这条语句,就只有第一个条件key1 > 'z'能用到索引,后面的条件就需要回表去判断了,回表就需要去主键索引重新找,并且是随机 IO,效率相对低,这里 MySQL 做了优化,可以在索引遍历的时候就对索引列进行判断,然后过滤掉不满足条件的记录,减少回表次数,所以下推实际上是指将 Server 层的工作下推到引擎层处理了

  • ICP 只能用于二级索引,不能用于主索引;
  • 也不是全部 where 条件都可以用 ICP 筛选,如果某 where 条件的字段不在索引中,当然还是要读取整条记录做筛选,在这种情况下,仍然要到 server 端做 where 筛选;

    隐式转换导致索引失效

    参考 MySQL 文档

当操作符左右两边的数据类型不一致时,会发生隐式转换。

  1. 当 where 查询操作符左边为数值类型时发生了隐式转换,那么对效率影响不大,但还是不推荐这么做。
    select* from test1 where int_column= '10000',对于这条 sql int_column字段是整型,左边为 int 类型 10000,转换为浮点数还是 10000,右边字符串类型’10000’,转换为浮点数也是 10000。两边的转换结果都是唯一确定的,所以不影响使用索引。

  2. 当 where 查询操作符左边为字符类型时发生了隐式转换,那么会导致索引失效,造成全表扫描效率极低。
    select* from test1 where str_column= 10000, 对于这条 sql str_column是字符型,左边是字符串类型’10000’,转浮点数为 10000 是唯一的,右边 int 类型 10000 转换结果也是唯一的。但是,因为左边是检索条件,’10000’转到 10000 虽然是唯一,但是其他字符串也可以转换为 10000,比如’10000a’,‘010000’,’10000’等等都能转为浮点数 10000,这样的情况下,是不能用到索引的

    左边为数值类型影响不大,因为右边转换结果是唯一的,但是如果左边是字符类型,那么右边的值就不确定了,所以无法使用索引

    全局锁

    MySQL 提供了一个加全局读锁的方法,命令是 Flush tables with read lock (FTWRL),加上之后所有的更新操作都会阻塞,可以用于全库逻辑备份。也就是把整库每个表都 select 出来存成文本。

    表级锁

  • 表锁的语法是 lock tables … read/write
  • 另一类表级的锁是 MDL(metadata lock)。MDL 不需要显式使用,在访问一个表的时候会被自动加上。MDL 的作用是,保证读写的正确性

行锁

顾名思义就是锁定某一行,比如
select * from t where id=1 for update; 就会锁定 id=1 的这一行数

两阶段锁: 在 InnoDB 事务中,行锁是在需要的时候才加上的,但并不是不需要了就立刻释放,而是要等到事务结束时才释放。这个就是 两阶段锁协议
如果你的事务中需要锁多个行,要把最可能造成锁冲突、最可能影响并发度的锁尽量往后放(热点数据)。

间隙锁

RR 级别下为了禁止幻读而产生的,锁的是记录之间的间隙,间隙锁之间是不互斥的,互斥的是往间隙中插入记录的操作,所以 RR 级别下,加锁就不只是加行锁,还回加间隙锁,共同形成了next_key_lock

间隙锁造成死锁案例

begin;
select * from t where id=N for update;
/*如果行不存在*/
insert into t values(N,N,N);
commit;

wd3VzQ.png

死锁和死锁检测

wUwb4I.png

如上图,事务 A 抢占了 id=1 这一行的行锁,而事务 B 抢占了 id=2 这一行的行锁,接下来就陷入了循环等待,两个事务会等待对方释放锁,显然数据库是不能允许这种情况发生的,所以此时有两种解决方案

  1. 等待,直到超时,这里是通过 innodb 的innodb_lock_wait_timeout来控制的,这个值默认是 50s,显然在线上服务,这样的等待是不能接收的
  2. 发起死锁检测,发现死锁后主动回滚死锁链条中的某一个事务(一般是比较小的事务),但是死锁检测是比较耗时的(有向图环路检测?),

除了上面的方案,其实也有一些其他的方案,比如 修改 MySQL 的源码在进入引擎之前使相同行的更新操作排队,或者通过中间件的形式也行。或者可以通过分散竞争的方式来减少锁冲突,将热点数据打散,类似LongAdder的思想,这样竞争就会小很大

Redis

为什么快?

Redis 所有数据都是存放在内存中,这也是 Redis 速度快的主要原因。IO 多路复用监听多个事件,在内存中快速响应

数据类型

  1. 字符串:底层封装了一个 SDS 结构,对比 C 语言字符串,记录了字符的长度,可以 O(1) 获取长度。主动扩容,避免缓冲区溢出。空间预分配以及惰性删除减少内存分配次数
  2. 哈希(内部编码:小于阈值 ziplist,否则 hashtable)
  3. 列表(内部编码:ziplist,linkedlist,quicklist)
  4. 集合(内部编码:小于阈值 intset,否则 hashtable)
  5. 有序集合(内部编码:ziplist 或 skiplist,元素个数小于阈值就是 ziplist,否则就是 skiplist)

ziplist: 内部表现为排列紧凑的一块连续内存数组,新增和删除会涉及内存的重新分配和释放,读写操作涉及复杂的指针移动复杂度较高可以作为 hash,list,zset 小数据量的结构

intset:集合 set 类型编码的一种,内部为存储有序,不重复的整数集合底层结构为数组

持久化

RDB(快照)

把当前进程数据生成快照保存到硬盘的过程,(也可以作为主从复制的媒介)

save: 会阻塞当前 Redis 服务,直到 RDB 过程完成,对于内存较大的实例,影响会比较大,线上不推荐使用

bgsave:Redis 进程 fork 出子进程,由于 fork 会复制父进程的页表(并不会复制内存,而是采用 COW,所以不会产生大量拷贝消耗),所以子进程可以共享父进程的内存数据,进而在后台进行持久化生成 RDB

触发时机

  • 手动执行命令触发
  • 使用 save 相关配置,如 save m n 表示在 m 秒内存在 n 次修改自动触发 bgsave(并不好,并发量不好预估,不恰当的设置会导致 RDB 过多)
  • 执行 debug reload 重写加载 Redis 的时候
  • 从节点执行全量复制操作,主节点自动执行 bgsave 生成 RDB 文件并发送给从节点
  • 默认情况下执行 shutdown 的时候,如果没有开启 AOF 也会自动执行 bgsave

优点

  • RDB 是一个紧凑压缩的二进制文件,代表 Redis 某一个时刻的数据快照,非常适合用于备份,复制
  • Redis 加载 RDB 恢复的数据会比 AOF 快

缺点

  • RDB 无法做到 实时/妙级 持久化,RDB 需要保存整个内存的数据,频繁的执行 RDB 操作消耗也比较大

AOF(日志)

以独立日志的方式记录每次写命令,重启的时候再重新执行 AOF 文件中的命令达到恢复数据的目的

所有的命令都会追加到aof_buf缓冲区中,缓冲区会根据一定的 同步策略 进行fsync刷盘,随着 AOF 文件的不断增大,需要定期进行 AOF 重写 ,清除进程内过期的数据,读取进程数据只保留最终数据写入命令,合并多条命令,以达到压缩空间的目的

同步策略

  1. always : 命令写入aof_buf后立马fsync刷盘,当刷盘完成后返回,显然这种方式数据不会丢失,但是 IO 的开销比较大,频繁的写入会很影响性能
  2. everysec : 命令写入aof_buf后调用write,后台线程会每秒执行一次fsync,推荐的策略,即使是宕机也只会丢失 1s 的数据
  3. no :命令写入aof_buf后调用write然后旧不管了,同步操作交给 OS,不推荐,不太可靠

write只是将数据写入页缓存区,同步磁盘的操作会交给 OS 调度,如果在同步之前宕机,那么数就会丢失

AOF 重写

  1. 主进程 fork 从子进程,子进程进行 AOF 的重写
  2. 主进程继续响应客户端请求,这部分数据也不能就这样丢掉,此时产生的 AOF 日志会写入 AOF 重写缓冲区
  3. 子进程完成后,父进程将 AOF 重写缓冲区的数据写入新的 AOF 文件,然后替换旧的 AOF 文件

内存回收策略

删除到达过期时间的键对象

  • 惰性删除:当客户端读取到已经超时的键,就执行删除操作并返回空,这策略是为了节约 CPU 资源,不需要单独维护 TTL 链表来处理过期键的删除。单独使用这种方式存在内出泄露的问题,当过期键一直没有被访问将无法得到即时删除,从而导致内存无法的即时释放
  • 定时任务删除:Redis 内部维护一个定时任务,默认每秒运行 10 次,定时任务中删除过期键采用了自适应算法,根据过期键的比例采用快模式或者慢模式,每个数据库空间抽取 20 个键,判断是否有超过 25%的键过期,如果超过就会一直循环直到小于 25%或者超时

内存达到 max_memory 的适合触发内存溢出控制

  • novication:不删除任务数据,拒绝任何写入操作,并且返回客户端 OOM
  • volatile-lru:根据 lru 策略从设置了超时时间的键中剔除
  • volatile-random:随机从设置了超时时间的键中剔除
  • volatile-ttl:从设置了超时时间的键中,选择最早过期的剔除
  • allkeys-random:从所有键中随机剔除
  • allkeys-lru:从所有键中按照 lru 规则剔除

缓存穿透

指恶意攻击或者爬虫,恶意查询一个不存在的数据,因为不存在则不会写到缓存中,所以每次都会去请求 DB,如果瞬间流量过大,穿透到 DB 就会导致宕机

解决方案

  1. 缓存空对象,将 DB 查询为空的 key 也存在缓存中,然后设置一段过期时间,后面相同的 key 就可以通过缓存获取,不用查 DB,确定也显而易见,如果同时构造多个不同的 key 依然会导致穿透
  2. 布隆过滤器,相比传统的 HashMap,布隆过滤器更省内存查询也更快,底层是一个二进制位图,和一些 Hash 函数,当向布隆过滤器中存入一些 key 的时候,首先对 key 进行 k 次 hash,然后将 bitmap 中对应位置设置为 1,当判断一个 key 是否在集合中的时候,只需要将 key 再次 hash,并判断所有对应的位置是否为 1,如果都为 1,说明这个 key 有很大可能在集合中,反之,如果并不是所有位置都为 1,就说明这个 key 一定不在集合中,整体的误判率和插入元素的个数,以及哈希的次数,还有位图的长度都有关 ,另外布隆过滤器也不支持删除操作
    wTW711.png

    缓存击穿

    如果一个热点 key 突然过期,那么就可能会导致大量请求直接打到 DB 层压垮 DB,而常规的解决方案有两种:
  3. 缓存永不过期,类似 Redis 中的惰性删除,仅仅设置逻辑过期时间,这样当访问一个过期的 key 时,请求不会直接打到 DB,然后我们通过后台异步线程去更新缓存,这样做用户延迟是最低的,但是可能会有数据的不一致,有的线程读取的仍然是老数据
  4. 互斥锁,当多个请求同时去 get 热点数据的时候,当第一个线程请求数据的时候进行加锁,其他线程阻塞,直到第一个请求到数据后进行热点 key 重建然后释放锁,其他请求就直接从缓存中 get 数据,不用再去 DB 请求数据

主从复制

可以用于配合 读写分离负载均衡 ,也可以用于故障恢复,数据冗余

  1. slave 启动后会先 master 发送 SYNC 的同步命令
  2. Master 收到后会使用 bgsave 后台生成 RDB 文件,同时也会将主线程当前进行的命令也保存到缓冲区
  3. Master 将 RDB 和 Buffer 中的都发送给 Slave
  4. Slave 将接收到的数据恢复到内存中

缺点

  1. 数据一致性问题
  2. 主节点挂掉后需要人工干预,不能自动恢复

    部分复制 根据节点 id 和 offset,复制缓冲区

    哨兵模式

    哨兵是主从的升级版,部署 sentinel 监控主从的运行状态,如果发现异常就会发出警告,然后对异常情况进行处理,当 Master 出现故障的时候会自动选举一个 slave 作为 master 顶上去

Master 下线

当 sentinel 启动的时候会和 master 建立连接,订阅 master 的频道,然后定期(10s)向 Master 和 Slave 发送INFO或者PING消息,用于哨兵和哨兵,哨兵和 Master 通信,如果哨兵发送的PING在指定时间内没有收到回复,发送的哨兵就会认为该 Master 主观下线,同时询问其他哨兵是否也认为下线,如果达到一定数量(quorum)就会认为该节点 客观下线

然后会在哨兵中选取一个 Leader 哨兵,由它来进行故障恢复,从所有的 slave 中选取一个优先级最大的,如果优先级相同就会选择偏移量大,偏移量大意味着数据更加完整

Cluster(集群模式)

前面哨兵可以解决主从不能自动恢复的问题,但是仍然会存在难以扩容以及读写瓶颈问题,且主从复制各个节点上都是数据冗余消耗大量存储空间

redis cluster 有固定的 16384 个 hash slot,每个 Master 节点负责一部分 slot,对 key 计算 cyc16 值然后对 16348 取模,获取 key 对应的 hash slot,然后存储到对应的节点上,将 数据和节点解耦,并不用关系数据在那个节点,仅仅关心数据的槽在哪里就行了

无中心的架构模式,最终一致性

对比 Memcached

  • Redis 支持的数据类型更多,比如 Hash,Set,SortSet 等,而 Memcache 只支持简单的 k-v 结构,复杂的对象需要客户端手动序列化,100k 以上的对象,Memcached 性能会更好
  • Redis 支持 数据持久化,可以将内存中的数据保存到磁盘中,而 Memcache 不支持
  • Memcached 服务器本身不支持集群,需要客户端进行一致性 Hash 或者代理中间件支持集群,而 Redis 服务器本身支持集群
  • Redis 是的核心数据提交是单线程模型,保证了数据按顺序提交,Memcached 使用 CAS 确保并发的一致性
  • 基于上一点,Redis 只能利用单核,而 Memcached 可以利用多核,所以性能上可能会好一点

分布式

Zookeeper 保证 CP

当向注册中心查询服务列表时,我们可以容忍注册中心返回的是几分钟以前的注册信息,但不能接受服务直接 down 掉不可用。也就是说,服务注册功能对可用性的要求要高于一致性。但是 zk 会出现这样一种情况,当 master 节点因为网络故障与其他节点失去联系时,剩余节点会重新进行 leader 选举。问题在于,选举 leader 的时间太长,30 ~ 120s, 且选举期间整个 zk 集群都是不可用的,这就导致在选举期间注册服务瘫痪。在云部署的环境下,因网络问题使得 zk 集群失去 master 节点是较大概率会发生的事,虽然服务能够最终恢复,但是漫长的选举时间导致的注册长期不可用是不能容忍的。

Eureka 保证 AP

Eureka 看明白了这一点,因此在设计时就优先保证可用性。Eureka 各个节点都是平等的,几个节点挂掉不会影响正常节点的工作,剩余的节点依然可以提供注册和查询服务。而 Eureka 的客户端在向某个 Eureka 注册或时如果发现连接失败,则会自动切换至其它节点,只要有一台 Eureka 还在,就能保证注册服务可用(保证可用性),只不过查到的信息可能不是最新的(不保证强一致性)。除此之外,Eureka 还有一种自我保护机制,如果在 15 分钟内超过 85%的节点都没有正常的心跳,那么 Eureka 就认为客户端与注册中心出现了网络故障,此时会出现以下几种情况:

  1. Eureka 不再从注册列表中移除因为长时间没收到心跳而应该过期的服务
  2. Eureka 仍然能够接受新服务的注册和查询请求,但是不会被同步到其它节点上(即保证当前节点依然可用)
  3. 当网络稳定时,当前实例新的注册信息会被同步到其它节点中

因此, Eureka 可以很好的应对因网络故障导致部分节点失去联系的情况,而不会像 zookeeper 那样使整个注册服务瘫痪。

Java

JVM & GC

内存区域划分

  1. 程序计数器:线程私有,指令执行的行号指示器
  2. Java 虚拟机栈:每个方法执行的时候都会创建一个 栈帧 去存储局部变量表,操作数栈,等信息,而 Java 虚拟机栈就是线程内用于存放栈帧的区域,方法执行结束就对应着进栈出栈,可以通过-Xss 设置栈大小
  3. 堆:JVM 中最大的一块区域,所有的对象实例和数组都会分配在这里,同时也是 GC 最主要的区域
  4. 方法区:存放已经加载的类信息,运行时常量池,以及静态变量
  5. 直接内存:使用本地代码直接分配的堆外内存

对象创建过程

  1. 类加载检查,检查常量池 Class 是否被加载
  2. 分配内存,指针碰撞和空闲列表,内存规整的话就采用指针碰撞,否则就采用空闲列表
  3. 初始化零值,将内存空间设置为零值,所以对象中的属性不手动初始化也是可以使用的
  4. 设置对象头,执行init方法(构造器)

堆结构分代

  1. 新生代:新生成的对象优先放在新生代中,新生代对象朝升夕死,存活率很低,在新生代中,GC 回收效率很高
  2. 老年代:在新生代经历了多次 GC(具体次数要看 jvm 的配置)仍然存活下来的对象就会进入老年代,存活率高,大对象和长期存活的对象会直接进入老年代

    这样分代就可以让垃圾收集器有针对性的进行 GC,避免全堆扫描,对不同的区域采用不同的回收策略,比如新生代就采用 复制算法,老年代则采用 标记清除标记整理

判断对象死亡

  1. 引用计数,每当对象被引用,对应的引用计数就+1,如果引用失效就-1,计数器为 0 就说明不会再被使用了,但是这种方式可能会造成循环引用的问题,主流的 JVM 都不是采用的这种方式(py 似乎是这种方式
  2. 可达性分析,通过一系列的 GC ROOT 为起点向下搜索,当一个对象和 GC ROOT 没有引用链的话该对象就不可用了了

强软弱虚

  1. 强引用:发送 GC 也不会被清理
  2. 软引用:发送 GC 且内存不足就会被清理
  3. 弱引用:发生 GC 的时候不过内存是否足够都会被清理
  4. 虚引用:对对象的 GC 没有影响,用于在 GC 的时候收到通知

垃圾收集算法

  1. 标记-清除:首先标记出所有 需要回收 的对象,标记完成后统一回收所有被标记的对象,效率较低,而且会产生 内存碎片
  2. 标记-整理:和标记清除类似,不过在清除阶段会将存活对象都移动到一边,然后直接清除另一边,不会产生内存碎片,但是需要可能 要移动大量对象 效率仍然不高,适用于 存活率高老年代
  3. 复制算法:将内存划分为两块,每次只使用其中的一块,当其中一块使用完后就将 存活的对象 移动另一块上面,然后将使用过的空间一次清理掉,适用于 存活率较低的新生代,问题是空间的利用率变低,所以一般 jvm 的实现都并不是划分为 1/2,而是分成一块较大的Eden区,和两块较小的Survivor区,比例默认是 8:1,每次只使用 eden 区和其中一块 Survivor 区,回收时将 Eden 和 Survivor 区移动到另一块 Survivor,然后清理 Eden 和 Survivor

    如果存活对象太多了,一个 Surivior 存不下,那么就会依赖老年代的空间担保,借用老年代空间存储存不下的对象

  4. 分代收集:顾名思义,对不同的代采用不同的收集算法

垃圾收集器

  1. Serial 收集器:串行,单线程,GC 时候会 STW
  2. Serial Old 收集器:Serial 收集老年代
  3. ParNew 收集器:多线程,GC 时也会 STW,只是会有多个线程同时收集
  4. Parallel Scavenge 收集器:和 ParNew 类似,不过 更强调吞吐量(垃圾收集时间尽可能短)
  5. Parallel Old 收集器:Parallel Scavenge 老年代版本,使用标记整理
  6. CMS 收集器:强调 低停顿,GC 线程和用户线程并行,使用 标记清除 的老年代收集器。①初始标记(停顿)②并发标记③重新标记(停顿)④并发清除
  7. G1 收集器:实现了可预测额停顿时间,将内存划分为 Region,然后按照回收时间以及回收空间维护一个优先级队列,每次根据允许的时间回收价值最大的 Region ①初始标记(停顿)②并发标记③最终标记(停顿)④筛选回收

FULL GC 触发

Minor GC:新生代发生的 GC,Eden 区域快满的时候会就会触发,Minor GC 一般发生比较频繁,效率较高

FULL GC: 收集整个堆,效率很低

  1. System.gc(),建议 jvm 执行 Full GC
  2. 老年代空间不足,大对象进入老年代
  3. 老年代空间担保失败,Minor GC 复制时判断存活的对象能否放进老年代

    类加载

  4. 加载(loadCalss方法,可以通过覆盖该方法实现自定义的类加载器),通过类的全限定名获取定义此类的二进制字节流,类加载的最终产物是位于堆中的 Class 对象
  5. 连接(验证,准备,解析)
  6. 初始化,执行 类构造器 clinit ,类变量的赋值,静态语句块执行,虚拟机会保证clinit方法的线程安全(对应前文 对象的 init 方法

双亲委派

系统在加载类的时候会首先判断该类是否以及被加载了,如果被加载就直接返回,否则就尝试加载,在加载时候会首先委托父类去加载,如果父类加载不了,就会尝试自己加载,类似 Java 内部核心类就都会交给 BootStrapClassLoader 去加载,这样可以提高系统安全性,也能避免类重复加载

线程上下文加载器 (TCCL)

HashMap

对比 HashTable

  1. HashMap 不是线程安全的,HashTable 内方法都加了锁,线程安全,但是效率会低很多
  2. HashMap 初始容量不指定就是 16,之后每次扩容都会变成之前的 2 倍,如果给定了初始值但是并不是 2 的幂次,就自动转换成最接近的 2 的幂次。而 HashTable 初始容量为 11,每次扩容变成原来的 2n+1
  3. JDK8 之后 HashMap 底层链表长度如果大于 8 就会转换成红黑树

    2 的幂次是为了避免使用%操作,当 length 是 2 的幂的时候,hash%length = hash & (length-1) 而&操作相比%会高效很多
    9 % 4 = 1001 & 0011 = 0001

    equals 和 hashCode

    当向 HashMap 中插入元素的时候,会根据 key 计算得到的 hash 值,转换成 table 数组的索引,然后判断table[i]是不是 null,如果是 null,直接新建节点添加,如果不为空,通过hashCodeequals判断两个 key 是否相同(先判断 hashcode,hashCode 不同一定不同,再根据 equals),相同就直接覆盖,否则就用拉链法解决冲突

ConcurrentHashMap

JDK1.7 之前采用 分段锁,采用 Segment 分段的管理键值对,当线程访问某一个 Segment 的时候不影响其他的 Segment,这样可以分散竞争大大提高 HashMap 的并发度。

可以引出 LongAdder 的分段锁

put 的时候先将 key 经过 hash 后定位到具体的 Segment,然后再 Segment 中加锁进行 put(拉链法),Get 操作类似先定位到 Segment,然后再定位到具体的元素,整个过程不用加锁

JDK1.8 之后抛弃了原有的分段锁,采用了 CAS+synchronized,同时也引入了红黑树,当没有冲突的时候会通过 CAS 写入,如果发生 hash 冲突或者需要扩容才会加锁,并且 synchronized 在 1.8 之后也优化的很好

JMM

Java 内存模型主要是定义了一种规范,就是每个线程有自己独立的工作内存,所有变量存储在主内存,线程的工作内存中保存了需要使用的变量的副本,线程对变量的改变都是在工作内存中修改,修改完了之后再同步到主内存,线程不能直接对主内存的变量进行修改,不同线程之间也无法直接访问对方的工作内存的变量,只能通过主内存传递

synchnorized

可以保证并发的三要素,原子性,可见性,有序性,早期一直被成为重量级锁,依赖底层的系统调用,消耗较大

在 JDK6 之后,对其进行了大量的优化

  1. 偏向锁 :当锁对象第一次被获取的时候,会把对象头的锁标志位设置位偏向模式,然后利用 CAS 将线程 ID 写入对象头,后续该线程下一次进入同步块的时候就不会进行任何同步操作(锁消除),如果有另一个线程尝试获取锁对象偏向模式就会失效,升级为轻量级锁
  2. 轻量级锁 :将锁对象的 MarkWord 复制到本地线程空间,然后将对象头的 MarkWord 利用 CAS 更新为执行线程栈的复制的 MarkWord,成功后就拥有该对象的锁了,更新失败就说明有多个线程在同时竞争该对象,这个时候轻量级锁就失效了,会膨胀成重量级锁,所以这种方式在多个线程交替使用锁,不存在竞争的时候性能会很高
  3. 自旋锁和自适应锁:在重量级锁抢锁失败后并不马上阻塞挂起,而是短暂的自旋,避免线程切换,如果锁占用的时间很短,那么自旋的效果就会很好,否则长时间自旋会浪费 CPU,所以后面引入了 自适应锁,不再固定自旋时间,而是由前一个锁的状态决定
  4. 锁消除 & 锁粗化:锁消除是指 JIT 对于一些代码上要求同步,但是实际上并不会产生共享数据竞争的锁进行消除,这里就涉及到逃逸分析,而锁粗化就是将一些连续的对 同一个锁对象 的加锁解锁操作合并粗化,将锁的范围变大,避免频繁的加锁解锁

    Volatile

  5. 保证内存可见性,对变量的修改能马上同步到主内存,并且读取一个 volatile 变量也必须从主内存读取
  6. 保证有序性,jvm 可能会对我们编写的代码进行重排序以优化性能,经典的例子就是 DCL 单例的例子了,DCL 单例之所以要在单例上加 volatile 就是为了放在 jvm 对指令的重排序,new Object 的操作会分为好几步骤,可能把内存分配重排前面,就可能会导致错误

    可以保证 Long/Double 写入的原子性,早期写入这些 64 位的数据可能是分段写的

CAS

CPU 支持的一种并发原语指令,一般有 3 个参数,内存中的值 M,期望的值 E,以及更新的值 U,如果执行执行的时候,M==E,那么就会将 M 改成 U,这一系列的操作被 CPU 封装为一个系统原语,借此可以实现非阻塞的轻量级的乐观锁

缺点

  1. CAS 自旋消耗 CPU 资源
  2. ABA 问题,可以使用 AtomicStampedReference 的版本变量机制解决

JUC

  1. CountDownLatch,指定一个计数 count,当调用countdown()的时候计数器减一,await()会阻塞,知道计数器减为 0,(Golang 中的 WaitGroup 和这个类似)
  2. CyclicBarrier,控制多个线程到达某个点都再继续进行下一步,类似爬山,大家都到达某个点之后在一并前进
  3. Semaphore,信号量,PV 操作,设置初始凭证,释放凭证,获取凭证,不够就会阻塞
  4. ReentrantLock,可重入显示锁(Java 中不可重入的似乎就是线程池中的那个 Worker),对比内部锁:
    1. 显示锁支持公平锁
    2. 显示锁支持非阻塞 trylock 以及带超时的 tryLock(long timeout, TimeUnit unit)
    3. 显示锁可以中断请求 lockInterruptibly
    4. 显示锁需要手动的 release,sync 自动 release
    5. sync 在优化后性能和 lock 差不多
  5. Condition,显示锁的线程通信方式,对应 sync 的 wait 和 notify,但是 condition 可以解决 过早唤醒 的问题,为一个锁创建多个条件变量,比如典型的生产者消费者问题,我们就可以给消费者和生产者都创建一个 condition,让生产者只会唤醒消费者,而消费者只会缓存生产者
  6. ReadWriteLock,读写锁,读读可并发
  7. Atomic 类,CAS + Volatile
  8. LongAdder,CAS Cell[] 数组 分段锁,分散竞争,sum 不加锁,最终一致性,性能高于 Atomic

    阻塞队列

  9. ArrayBlockingQueue,数组实现的 有界 阻塞队列,默认是非公平的,底层实现是 ReentrantLock
  10. LinkedBlockingQueue,链表实现的阻塞队列,如果不设置容量,容量就会设置为INT_MAX变成无界队列
  11. SynchronousQueue,不存储元素的阻塞队列,或者说是一个容量为 0 的阻塞队列,put 和 take 成对的时候才不会阻塞,和 Golang 中无缓冲的 channel 类似,发送方需要等待接收方,接收方需要等待发送方
  12. DelayQueue,延时获取队列,存入元素后等待一定的时间后才能获取

ThreadLocal

每个线程 Thread 内部都有一个私有的 ThreadLoaclMap,以 threadLocal 对象作为 key,而对应私有变量则是 val,所以各个线程通过同一个 threadlocal 查到的 key 都是不一样的,并且一个线程可以关联多个 threadLocal 变量

内存泄漏问题:线程内部的 ThreadLocalMap 的 key 是 threadlocal 对象的弱引用,当发送 GC 的时候会被自动清除,但是 value 是强引用,所以就会产生 key 为 null 的 Entry,value 永远无法被 GC 回收,发生内存泄漏,在 ThreadLocal 实现中 get,set 的时候都会自动清理 key 为 null 的 entry,但是最好还是每次使用完都手动的 remove()

线程池

优点

  1. 减低线程资源消耗,重复利用已经创建的线程,避免频繁的创建和销毁线程
  2. 提高响应速度,不用等待线程创建
  3. 提高线程的可管理性,控制并发的数量

大致流程

  1. 提交任务到线程池
  2. 线程数小于核心线程数,直接创建线程执行,否则就添加到阻塞队列中
  3. 如果阻塞队列满了就判断当前线程数是否小于最大线程数量,如果是就继续创建线程执行任务,否则就直接采用拒绝策略拒绝任务

大致原理

封装了一个 Worker 类,继承 AQS 实现了一个不可重入的独占锁,然后有一个 runWorker 的方法

  1. while 循环不断从阻塞队列中获取任务
  2. 获取任务成功就会加上内部实现的锁(用于 shutdown 的时候判断是否正在执行任务),然后执行任务
  3. 如果获取任务返回 null,那么该线程就会跳出循环,结束生命周期等待 GC
  4. 获取任务返回 null 的情况有很多,比如 ①线程池关闭了②线程数量大于最大线程数,并且任务队列为空 ③允许核心线程超时,并且任务队列为空。..

核心参数

  1. corePoolSize:核心线程池大小,任务数量超过核心线程池之后任务就会被放到阻塞队列
  2. maximumPoolSize:最大线程数,表示该线程池中最多创建多少个线程
  3. keepAliveTime:这个参数最终是作用在阻塞队列上,当没有任务执行的时候 除核心线程外的线程 最多闲置多长时间就会被回收,如果设置了 allowCoreThreadTimeOut 那么核心线程也会超时,与之对应的还有一个参数是TimeUnit,也就是 keepAlive 的时间单位
  4. workerQueue:线程池使用的阻塞队列
  5. threadFactory:线程工厂,根据传进来的 Runnable 创建线程
  6. handler:拒绝策略,①丢弃任务,抛异常②丢弃任务,不抛异常③丢弃最前面的任务,然后再次执行,知道可以接收④由调用线程处理该任务

工厂方法

  • newCachedThreadPool():不缓存任务,core 为 0,最大线程数 INT_MAX,阻塞队列使用 SynchronousQueue 不缓存任务,线程数可能 OOM
  • newFixedThreadPool():核心线程和最大线程相同,不允许扩容,阻塞队列无界可能会 OOM
  • newSingleThreadExecutor():单例线程池,只有一个线程,阻塞队列无界可能会 OOM

AQS

AQS 底层是基于 CLH 锁的,当前共享资源空闲的时候,线程可以直接获取,如果请求的资源被占用了,那么线程就会被封装成链表的节点,然后进入队列中排队阻塞,等待前一个节点的执行完成后唤醒,这样就可以分散竞争,将所有线程对同一个资源的竞争分散到各个节点,同时也避免了 惊群效应 (etcd 和 zk 实现的分布式锁也是和这个思路一样的)

AQS 中非公平锁,特征其实不是很明显,其实仍然需要排队,只不过在刚开始获取锁的时候可以插一次队列,然后进入队列的时候不判断前面有没有线程,也会尝试获取一次,如果两次都失败了那么就和公平锁无异,老老实实进队列排队等待唤醒

Go

CSP

  • CSP 进程通常是同步的(即任务被推送进 Channel 就立即执行,如果任务执行的线程正忙,则发送者就暂时无法推送新任务),Actor 进程通常是异步的(消息传递给 Actor 后并不一定马上执行)。
  • CSP 中的 Channel 通常是匿名的,即任务放进 Channel 之后你并不需要知道是哪个 Channel 在执行任务,而 Actor 是有“身份”的,你可以明确的知道哪个 Actor 在执行任务。
  • 在 CSP 中,我们只能通过 Channel 在任务间传递消息,在 Actor 中我们可以直接从一个 Actor 往另一个 Actor 传输数据。

    垃圾回收

    对比 Java 的垃圾回收

  1. 无分代,分代 GC 所回收的主要目标是新创建的对象(存活时间短,朝生夕死),避免频繁的检查整个堆,但是 Go 的编译器会通过 逃逸分析 将大部分的新生对象创建在栈上(栈使用完后会直接回收,不需要 GC 参与),只有需要长期存在的对象才会放到需要 GC 的堆中,所以分代对 Go 来说意义不大
  2. 无整理,对象整理是为了解决内存碎片的问题,而 Go 语言采用的是 tcmalloc 基本上没有内存碎片,并且顺序内存分配器在多线程场景下并不适用,对象整理对 Go 来说性能提升不大

    QA

  3. Go 语言中数组是具有固定长度而且拥有零个或者多个相同或相同数据类型元素的序列。由于数组长度固定,所以在 Go 语言比较少直接使用

Go1.3 之前主要是 标记清除 算法,标记需要扫描整个堆,需要 STW,也会产生内存碎片

GC ROOT: 1. 全局变量 2. 执行栈 3. 寄存器

三色标记法

  1. 将所有节点放入 白色集合
  2. 首先从根节点出发 BFS 走一轮,将遍历到的节点移入 灰色集合
  3. 遍历所有的灰色集合,将灰色集合能 BFS 一轮,访问到的节点加入灰色集合,然后将原本的 灰色对象 加入 黑色集合
  4. 重复上一步,直到 灰色集合中没有对象
  5. 清除所有的 白色集合 中的对象

上面的做法看似没毛病,但是仍然存在问题,无法和用户程序并行,如果程序运行过程中 ①灰色对象丢失了白色对象黑色对象引用了白色对象。这个时候该 白色对象 因为失去了 灰色对象 的引用所以它就不会变成灰色,清理的时候就会将其清除,但是实际上这个对象已经被一个黑色对象引用了,这样就会导致误杀

解决办法:读写屏障,在赋值或者读取操作前后做一些额外的处理,将目标对象保存起来,最终还是会被作为灰色对象扫描,就不会漏标

GPM

Go 的用户级线程(协程)的实现是 N:M,内核创建出 N 个内核线程,M 个用户线程会对应这 N 个线程,用户线程完全由用户来调度,而内核线程由内核去调度

老的 GM 模型

M: 代表线程,他要运行 goroutine

G Queue: Golbal G Queue,所有的 goroutine 都保存在这个队列中

M 要执行 goroutine 或者放回都需要访问 GQueue,而 M 有多个,所以这里需要加锁保证互斥,导致性能较低

GPM 模型

G: 代表 goroutine,里面存储了 goroutine 的执行 stack 信息,goroutine 状态以及任务函数等

P: 逻辑 Process,P 的数量决定了系统的最大并发度(不超过 CPU 核数的前提下,GOMAXPROCS 可设置 P 的数量),没有数据竞争,不用加锁

M: 系统的计算资源,也就是 内核线程

每个 G 想要执行首先需要分配一个 P,只有将 P 和 M 绑定才有机会执行 P 的队列中的 G

特点

  1. 复用线程,协程本身是运行在一组线程组之上,不用频繁的创建销毁线程,除此之外 ① working stealing,当前 M 没有可以的 G 就会从其他 M 绑定的 P 中偷取任务 G,而不是消耗线程 ②hang offf,当发生阻塞的时候,会将当前 M 绑定的 P 释放,交给其他空闲的 M 去执行
  2. 抢占,在 coroutine 中要等待一个协程主动让出 CPU 才会执行下一个任务,那么就可能会造成线程饥饿,而 Go 中一个 goroutine 最多占用 10ms,防止其他协程饿死,这也是和传统协程不同的地方
  3. 全局 G 队列,新的调度器模型中仍然有全局 G 队列,当 M 从其他 P 偷取不到任务时候也会从 G Queue 偷取任务

网络

URL->显示主页

  1. DNS 解析
  2. TCP 连接
  3. 发送 HTTP 请求
  4. 服务器处理请求并返回 HTTP 报文
  5. 浏览器解析渲染页面
    连接结束

    GET 和 POST 区别

  6. Get 方法主要用于请求,请求服务端返回资源,而 POST 主要用于 form 表单的提交,相当于把信息提交到服务器,等待服务器做出响应。
  7. GET 请求是不安全的,发送请求的时候参数会拼接在 url 后面
  8. GET 请求的 URL 长度有限制(浏览器和服务器的限制),POST 数据放在 body 中一般没有限制
  9. GET 请求会被浏览器主动缓冲,而 POST 不会

    TCP

    三次握手 & 四次挥手

三次握手

  1. 客户端发送 SYN 同步信号,以及初始序列化 SEQ = ISN(c)
  2. 服务端返回 ACK = ISN(c)+1 信号以及 SYN 同步信号,以及初始序列化 SEQ = ISN(s) (半连接队列)
  3. 客户端回复 ACK = ISN(s)+1 信号(全连接队列)

    确认双发收发功能正常,交换 ISN 序列号

SYN flood

黑客伪造本地 IP 地址,然后想目标 IP 发送大量的 SYN 报文,服务端回复的 ACK+SYN 被发送到一个未知的地址,进而造成半连接队列满载,无法处理正常请求。 SYN Cookie 就是在三次握手的最后阶段才分配连接资源,收到 SYN 包后首先计算 Cookie,在收到第三次握手 ACK 的时候验证 Cookie,验证成功再分配资源

四次挥手

  1. 客户端发送 FIN 报文,Client:FIN-WAIT-1
  2. 服务端响应 ACK 信号,Server: CLOSE-WAIT,Client: FIN-WAIT-2
  3. 服务端发送 FIN 报文,Server: LAST-ACK
  4. 客户端响应 ACK 报文,Client:TIME-WAIT

TIME-WAIT

  1. 一方面确保通信过程中延迟的重复包能在连接结束后自动的消亡,否则可能会造成错乱
  2. 确保主动关闭方的最后的 ACK 能到达对端,同时也确保 ACK 丢失后,被动关闭端重发的 FIN 能顺利到达,一来一回 2MSL(msl 指的是报文在网络中最长的生存时间)

大量 TIME-WAIT 会造成一些浪费,会占用 TCP 端口,无法复用,可以通过 Linux 的一些设置去优化(net.ipv4.tcp_tw_reuse,tcp_tw_recycle)

TCP 可靠性保证

重传机制

  1. 超时重传,根据 RTO 的值重传丢失的数据,RTO 的值应该略大于 RTT,是一个动态值,会根据之前的 RTT 进行采样,然后动态变化
  2. 快速重传,不以时间为驱动,而是以数据为驱动,当收到 3 个重复的 ACK 信号的时候就会触发重传,可能会重传所有的数据
  3. SACK,快重传的一种实现方式,接收方通过 SACK 信号告知发送端丢失的数据段,这样发送端就可以准确的重传丢失的数据
  4. D-SACK,可以让「发送方」知道,是发出去的包丢了,还是接收方回应的 ACK 包丢了,可以知道是不是「发送方」的数据包被网络延迟了,可以知道网络中是不是把「发送方」的数据包给复制了

流量控制 & 滑动窗口

窗口实际上是发送方在 OS 中开辟的一块缓冲区,在收到对方的应答之前,数据会被缓存在窗口内

已发送并收到 ACK || 已发送未 ACK || 未发送且大小在窗口内 || 未发送且超出窗口

这样一来,发送方就可以在不等待 ACK 的情况下发送多个包(不超过窗口大小),接收方进行 累积确认(累计应答),当窗口耗尽,则无法发送数据,接收方 ACK 数据后,窗口右移,可用窗口增大

通常发送方的窗口是由接受方的窗口大小决定的,避免接收端处理不过来

拥塞控制

当网络出现拥堵,如果继续发送大量的数据包,会导致数据包延迟,丢失,进而导致重传,进一步加大阻塞程度,形成恶性循环

拥塞窗口(cwnd)

发送方维护的一个变量,根据网络拥塞程度动态的变化,swnd=Min(rwnd,cwnd),只要发生了超时重传其实就说明网络开始拥堵了,主要有以下算法

  1. 慢启动,发送方每接收一个 ACK,拥塞窗口 cwnd 的大小就会+1,直至 ssthresh
  2. 拥塞避免,每当收到一个 ACK 时,cwnd 增加 1/cwnd。
  3. 拥塞发生
    1. 超时重传;ssthresh 设为 cwnd/2,cwnd 重置为 1,重新开始慢启动,反应太剧烈,突然刹车
    2. 快速重传:ssthresh = cwnd,cwnd = cwnd/2
  4. 快速恢复

粘包解决方案:

  1. 固定长度
  2. 分割符号,文本中可能有分割符,需要扫描文本转义
  3. 添加长度字段,先读取长度字段,再读取内容

TCP 和 UDP 区别

  1. TCP 传输前需要建立连接,UDP 无连接
  2. TCP 面向流,将数据看做 UDP 则是面向报文
  3. TCP 提供可靠的服务,有超时重传,差错校验,滑动窗口,拥塞控制等机制确保可靠性能
  4. TCP 只支持点对点的通信,而 UDP 支持一对一,多对一和多对多的交互通信
  5. TCP 头部 20-60 字节,UDP 头部 8 字节

    如何设计可靠的 UDP

  6. 添加 seq/ack 机制,确保数据发送到对端
  7. 添加发送和接收缓冲区,主要是用户超时重传。
  8. 添加超时重传机制。

HTTP 1.0,1.1

  1. 长连接,Connection: keep-alive,这样可以在一个 TCP 连接中发送多个请求

  2. 错误状态响应码 : 在 HTTP1.1 中新增了 24 个错误状态响应码,如 409(Conflict)表示请求的资源与资源的当前状态发生冲突;410(Gone)表示服务器上的某个资源被永久性的删除。

  3. 缓存处理 : 在 HTTP1.0 中主要使用 header 里的 If-Modified-Since,Expires 来做为缓存判断的标准,HTTP1.1 则引入了更多的缓存控制策略例如 Entity tag,If-Unmodified-Since, If-Match, If-None-Match 等更多可供选择的缓存头来控制缓存策略。

    HTTPS

    HTTPS 是运行在 SSL/TLS 之上的 HTTP 协议,SSL/TLS 运行在 TCP 之上。所有传输的内容都经过加密,加密采用 对称加密 ,但对称加密的密钥用服务器方的证书进行了非对称加密。所以说,HTTP 安全性没有 HTTPS 高,但是 HTTPS 比 HTTP 耗费更多服务器资源。
    https://zhuanlan.zhihu.com/p/57142784

    TCP/IP 网络模型

  4. 应用层,(OSI 细分为:应用层,表示层,会话层)面向用户,为用户提供服务,常见协议有 HTTP,FTP,DNS

  5. 传输层,为应用层提供通用的数据传输服务,主要有 TCP 和 UDP 两种协议

  6. 网络层,提供路由和寻址的功能,确保两边的系统能互联,并选择最佳路径,网络层不提供通信服务,且网络层只对报文头部进行差错校验,协议有 IP,ICMP,ARP(路由器)

  7. 链路层,将网络层的数据封装成帧,然进行传输,并进行一些差错控制,PPP,HDLC,MAC(网桥,交换机)

  8. 物理层,利用一些传输介质,为数据链路层提供物理连接,时间 bit 流的传输(集线器)

操作系统

管理计算机资源,包括 CPU,内存,磁盘等,提供一些接口服务与一些第 3 方的软件

进程 & 线程 & 协程

进程 5 态模型: 1. 新建(fork) 2. 就绪 3. 运行 4. 等待 5. 终止

进程是操作系统资源分配的基本单位,当执行一个程序时候系统启动一个进程,分配给这个进程一些执行所需要的资源,包括打开的文件,虚拟内存地址空间等

孤儿进程:父进程被 kill 了,而子进程仍然存在就会变成孤儿进程,被 init 进程收养

僵尸进程:父进程没有 wait() 子进程,进程退出的时候会释放所占用的资源,但是不会释放 task_struct 里一些相关的状态信息,因为这些信息父进程可能会比较关心,父进程可以通过调用 wait 相关方法去获取子进程的这些信息,之后系统便才会完全回收子进程,所以如果父进程不调用 wait 就会导致子进程变成僵尸进程,占用进程号

线程就是进程中能够并发执行的实体,一个进程内至少有一个线程,是进程的组成部分,也是处理器调度执行的基本单位,一个进程内也可以有多个线程,多个线程共享进程所拥有的资源,共同完成任务

Java 线程生命周期: 1. 新建(new) 2. 运行 3. 阻塞 4. 等待 5. 限时等待 6. 终止

协程,英文 Coroutines,是一种比线程更加轻量级的存在,协程不是被操作系统内核所管理,而完全是由程序所控制,非抢占式的调度,创建成本更低,上下文切换成本低,当发生 IO 阻塞的时候调度器可以记录上下文然后主动的让出 CPU 执行权,实现协同式调度

死锁

  1. 互斥条件:该资源任意时刻只由一个线程占用
  2. 请求与保持条件:一个线程因为请求资源而阻塞,其他线程获取资源保持不变
  3. 不剥夺条件:线程已经获取的资源在未使用完成之前不能被其他线程强行剥夺
  4. 循环等待:若干线程之前形成的一直循环的依赖,比较容易打破的就是循环等待条件,只要按照顺序申请资源,释放则反序就能打破依赖

    存储管理

    连续分配会产生大量内存碎片,可以通过移动来合并但是消耗比较大,所以出现了离散式的分配方式,将进程数据分散的装入不相邻的内存分区中

    页式

    将逻辑空间等分为页,然后将物理内存空间等分为块,与页面大小相同,分配内存时将进程数据以块为单位,存放到离散的物理内存中,页的大小固定,不会产生外部碎片,只会产生少量内部碎片,用户不可见,由操作系统管理

    段式

    按照程序自身的逻辑关系划分为几个段,以段为单位分配内存,每个段在内存中占连续空间,但是各个段之间可以不相邻,分段更容易实现 信息的共享和保护,段的长度不固定,分配较大的段会产生外部碎片,对用户可见,用户编程需要显式的给出段名

    段页式

    先分段,在每一段内再做分页,存储依然采用页式存储,增加了硬件成本,系统复杂度大

    进程通信

  5. 管道(pipe)
  6. 信号(signal)
  7. 消息队列(Message)
  8. 共享内存 (share memory)
  9. 信号量 (semaphore)

调度算法

进程调度

  1. 先来先服务(First Come First Severd,FCFS),顾名思义,对长作业友好,短作业不友好,可能长期得不到执行
  2. 最短作业优先调度(Short Job First,SJF),优先选择短作业运行,对短作业有利,但是可能会导致长作业饥饿
  3. 高响应比优先(Highest Response Ratio Next,HRRN),优先执行响应比优先级高的进程,响应比 = (等待时间+要求服务时间)/要求服务时间,这样首先要求服务时间短的短作业会更容易被选中,同时长作业等待时间越长,相应比也会越高,兼顾长短作业
  4. 时间片轮转(Round Robin,RR)每个进程分配一个时间片,如果时间片用完,仍然在执行就会中断该进程,切换为其他进程,如果发生了阻塞后提前结束也会进行切换。时间片设置太短会导致大量的线程切换,如果设置太长就会导致短作业饥饿,一般设置 20ms-50ms
  5. 最高优先级调度(Highest Priority First,HPF),优先级可分为 静态优先级动态优先级,同时有两种调度方法, 抢占式非抢占式(出现优先级更高的,立马挂起当前进程,执行优先级更高的),可能会导致低优先级的永远不会执行
  6. 多级反馈队列,结合了 4 和 5

内存页面调度

也就是在产生缺页中断的时候,把磁盘中缺失的页面调度进虚拟地址映射的物理内存中时,由于物理内存空间不足所以需要选择一个物理页进行替换

  1. 最佳页面置换算法(OPT),置换 未来 最长时间不访问的页面,无法实现,仅仅是理论方法
  2. 先进先出置换(FIFO),直接选择内存中驻留最久的页面进行淘汰
  3. 最近最久未使用(LRU),选择 过去 最长时间未访问的页面进行置换
  4. 时钟页面置换(LOCK),将页面保存在一个环形链表中,一个表针指向最老的页面,当发生缺页中断的时候,检查指针指向的页面状态是否为 0,为 0 就淘汰该页面,并插入这个位置,然后把表针后移,如果是 1,就清除状态位为 0,然后继续向前找,知道找到 0
  5. 最不常用置换算法(LFU), 根据 过去 页面的访问次数,选择访问次数最少的页面淘汰,给每个页面增加一个计数器,然后用链表按照大小串起来。实现起来其实消耗会比较大,成本比较高

DMA

DMA,直接内存访问,使得 IO 模块在不涉及到 CPU 的情况下,读取或者写入内存,提高效率

虚拟内存

虚拟内存实际上是对主存的一种抽象,让每个进程都能 独占 内存,实际上进程发出的地址都是虚拟地址,通过虚拟寻址来间接的引用主存,cpu 产生的虚拟地址将通过 MMU 利用 页表(PTE(Page Table Entry)集合) 翻译成主存的物理地址,同时 CPU 还为页表寻址提供了缓存策略 TLB(Translation Lookaside Buffer) 提高翻译速度

虚拟地址被分为:虚拟页号(VPN)(高位)+ 偏移量(VPO)(低位)
通过虚拟页号定位页表中的PTE,判断是否有效,有效就拼接页表中的物理地址(PPN) 和虚拟地址的 偏移量 构成物理地址,如果无效就发生 缺页中断 ,这里中断页分为软中断和硬中断,软中断就是指页面已经在物理内存中,只是页表中没有,这时只要重新映射一下就行了,而硬中断就是物理内存中没有,这个时候就需要从磁盘中加载页到物理内存中(按需分页

fork() 其实就是复制页表,父子进程共享所有数据,但是当某一方执行了写入操作就会触发 COW,系统回为该进程申请新的内存,将要修改数据拷贝到新的区域,再进行读写

好处

  1. 虚拟内存利用主存起到缓存的作用,提高进程访问磁盘的效率
  2. 虚拟内存可以控制进程对物理内存的访问,隔离不同进程的访问权限,提高安全性能(页表中加入保护位)
  3. 为每个进程提供了一致的地址空间,简化内存管理,内存分配,可以一次分配多个连续的虚拟地址,但是在物理上不连续,简化内存共享

    mmap 内存映射

    将文件的物理地址和进程的虚拟地址进行映射(此时仅仅是进行了映射,没有拷贝),然后当进程发起对这块虚拟内存的访问的时候就会发生缺页,内核就会将文件从磁盘拷贝到物理内存中,然后进程就可以直接对这块内存进行读写,系统后台会自动刷新脏页到磁盘(也可以通过fsync强制刷盘)

常规的文件读写为了保证读写的效率和保护磁盘,提供了 页缓存(内核缓冲区) ,所以当我们读写某一个文件的时候会先将文件页从磁盘拷贝到 页缓存 ,但是由于页缓存依然位于内核态,用户进程无法寻址,所以还需要将数据从 页缓存 拷贝到用户的进程空间,然后才能操作,相比 mmap 的方法多了一次拷贝操作

五种 IO 模型

  1. 阻塞 IO,调用者一直阻塞,知道内核将数据准备好,然后将数据从内核态拷贝到用户态
  2. 非阻塞 IO,内核没准备好就会返回一个错误码,调用者不会阻塞,而是不断的轮询,询问内核数据是否准备好
  3. 多路复用 IO,类似非阻塞,只不过轮询交给内核,减少系统调用,内核会将进程加入到对应事件的等待队列,待事件就绪时候唤醒进程,避免空轮询
  4. 异步 IO,完全的非阻塞的 IO 方式,当数据准备好的时候会通过回调函数来处理
  5. 信号驱动 IO,内核在数据准备好的时候使用信号处理程序来进行通知

文件描述符表,文件描述符表,索引节点表

文件描述符表:进程创建的时候,会在内存中开辟 task_struct 结构体,又叫进程表,用于存放进程运行期间的一些相关信息

文件描述符表:记录进程打开的文件,内部有一个指针,指向 内核中的文件表

打开文件表(又叫做系统级的描述符表):所有进程共享这张表,记录了当前文件的偏移量,引用计数,以及指向i-node表的指针,当引用计数为 0 内核就会删除这个表项

i-node 表:记录文件对应的 inode 号,以及对应的 block

软链接 & 硬链接

硬链接 (ln): 实际上是给文件创建了一个别名,链接文件和原文件指向的其实是同一个 inode,创建一个硬连接实际上对应文件表中的引用计数+1,删除任意一个只是文件表的引用计数减一,并不会影响另一个文件

软连接(ln -s) 软连接实际上是一个快捷方式,软连接文件的 inode 会指向原文件本身的 inode,如果删除了原文件软连接就失效了

多路复用

提到多路复用就不得不说一下阻塞 IO,阻塞 IO 就是说当 IO 操作发起后会被阻塞直到收到数据才返回,因此当使用阻塞 IO 的时候通常会创建多个线程去监听描述符,但是多线程一来切换成本高,同时多线程的内存开销也会比较大

所以后面引入了非阻塞 IO,非阻塞 IO 不会挂起线程,调用后立即返回结果,所以可以在一个线程中轮询多个文件描述符是否准备就绪,但是非阻塞 IO 每次发起系统调用(syscall)都只能检测一个文件描述符是否就绪,系统调用成本很高,如果文件描述符很多,性能开销就会很大,同时还需要不停的去遍历所有的 FD,包括没有发生读写事件的 FD,这样会导致 CPU 的消耗非常大

而 IO 多路复用则可以通过一次系统调用检查多个文件描述符是否就绪,同时也不用像 非阻塞 IO 一样一直轮询所有的 FD,而是由事件驱动,当有监听的 FD 准备就绪时候通知进程返回处理,否则就会挂起进程到等待队列,避免 CPU 空转

select

// Linux
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
//位图结构
#define __FD_SETSIZE 1024
typedef __kernel_fd_set fd_set;
typedef struct {
unsigned long fds_bits[__FD_SETSIZE / (8 * sizeof(long))];
} __kernel_fd_set;

FD_SET(int fd, fd_set *set); // Add fd to the set
FD_CLR(int fd, fd_set *set); // Remove fd from the set
FD_ISSET(int fd, fd_set *set); // Return true if fd is in the set
FD_ZERO(fd_set *set); // Clear all entries from the set

特点

  1. 输入输出都是相同的 fd_set,所以每次都需要重新设置 fd
  2. 将 fd_set 从用户态拷贝到内核态,性能损耗大
  3. 内部每次调用的时候都是无差别轮询,当描述符很多的时候消耗较大
  4. fd_set 大小有限,最多 1024(fd_set 为长度为 32 的长整型数组,位图表示一个 bit 就是一个 fd,所以能表示 32*32=1024 个 FD)
  5. 不是线程安全的,如果正在使用的 fd 被其他进程关闭的话结果就未知了

实例

有空再来写

poll

#include <poll.h>
int poll ( struct pollfd * fds, unsigned int nfds, int timeout);

struct pollfd {
int fd; /* 文件描述符 */
short events; /* 等待的事件 */
short revents; /* 实际发生了的事件 */
} ;

特点

  1. poll_fd 数组只需要初始化一次,通过 events 和 revents 标识关注的事件和发生的事件
  2. poll 使用链表来实现,没有最大 fd 的限制
  3. 但是和 select 一样需要频繁的将 pollfd 从用户态拷贝到内核态
  4. poll 返回后,仍然需要对 pollfd 中的每个元素检查其 revents 值,来判断事件是否发生
  5. 水平触发,当报告了某个 fd 后如果没有被处理,下次还会继续报告该 fd

    实例

    有空再来写

    epoll

#include <sys/epoll.h>
//创建一个 epoll 的句柄,size 用来告诉内核这个监听的数目一共有多大
int epoll_create(int size);
//epoll 的事件注册函数
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
//等待事件的产生,类似于 select() 调用。
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

特点

  1. 在高速缓存 cache 中用红黑树保存要监听的事件,同时使用了一个 list 链表记录准备就绪的事件,当epoll_wait返回的时候只需要查看 list 中又没有数据就行了,所以我们不需要从内核态拷贝全部的描述符到用户态,只需要拷贝少量的就绪 fd 就可以了,并且调用epoll_wait的时候并不用拷贝描述符到内核态,因为前面epoll_ctl已经拷贝了,相比之前 selecl/poll 效率很大提升

工作模式

LT 模式 :当 epoll_ wait 检测到描述符事件发生并将此事件通知应用程序,应用程序没有一次性把数据读/写完。下次调用 epoll_wait 时,会再次响应应用程序并通知此事件。

ET 模式:当 epoll_ wait 检测到描述符事件发生并将此事件通知应用程序,应用程序必须立即处理该事件。如果不处理,下次调用 epoll_wait 时,不会再次响应应用程序并通知此事件。

ET 模式在很大程度上减少了 epoll 事件被重复触发的次数,因此效率要比 LT 模式高。epoll 工作在 ET 模式的时候,必须使用非阻塞 IO,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

ET 模式下阻塞 IO 需要一次性把数据全部读完,但是实际上 epoll 返回可读,到真正读取是由空窗期的,可能你读取的时候数据被其他进程取走了,如果采用阻塞读取就会导致进程一直阻塞

man 2 select 「BUGS」节:
Under Linux, select() may report a socket file descriptor as “ready for reading”, while nevertheless a subsequent read blocks. This could for example happen when data has arrived but upon examination has wrong checksum and is discarded. There may be other circumstances in which a file descriptor is spuriously reported as ready. Thus it may be safer to use O_NONBLOCK on sockets that should not block.

实例

有空再来写

Linux 常用命令

ps

-A 列出所有进程 -au 显示详细

海量数据处理

如何从大量的 URL 中找出相同的 URL?

  1. 给定 a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。

    64byte * 50 * 10^8 = 3000 * 10^8 byte = 300m
    hash 分治,将 a,b 中的 url 分别 hash 后模 1000,分别存放在 a(1,2,3,4..),b(1,2,3,4..) 文件中,然后将 a,b 文件直接加载到内存中统计就行了

  2. 如何从大量数据中找出高频词?

    hash 分治,将所有的数据 hash 后取模,分散到不同的小文件中,然后统计各个小文件的词频,然后用小根堆统计 TopK

  3. 如何在大量的数据中判断一个数是否存在?

    40 亿个不重复整数,我们用 40 亿个 bit 来表示,初始位均为 0,那么总共需要内存:4, 000, 000, 000b≈512M。我们读取这 40 亿个整数,将对应的 bit 设置为 1。接着读取要查询的数,查看相应位是否为 1,如果为 1 表示存在,如果为 0 表示不存在。

RAFT

https://juejin.im/post/6844903602918522888 这个讲的不错,后面有时间根据这个再整理下

leader 选举

Leader 选举需要某个节点首先发起投票请求,每个节点都有一个随机的 election timeout,当超过这个时间没有收到 Leader 的心跳消息就认为 Leader 挂掉了,就回将自己的 term+1 然后发起投票请求,成为 Candidate,其他节点收到请求后如果投票给该节点,那么当前节点就会成为 Leader,Leader 会每间隔 HeartbeatTimeout 向所有的 Follower 发送心跳包

日志复制

当一个节点被选为主节点后,它就开始对外提供服务,收到客户端请求后,主节点会先将数据加入自己的日志中,然后并行的向其他 Follower 节点发送消息,如果有大多数节点成功的写入了这条日志,那么 Leader 节点的这条日志状态就会更新为 committed 状态,提交该条目,同时也会将之前任期的条目,并且通过心跳包告知其他节点同步主节点的日志

安全性

  1. 选主的限制,只有包含了所有提交日志的节点才有机会成为主节点,所以在选举的时候,如果发起投票节点的最后一个 log 的任期比自己小,那么就拒绝为该节点投票,这样选出的节点的 log 至少比半数以上节点要新
  2. Raft 只对自己任期内的日志计数并在复制到多数节点时进行提交,且在提交这条日志的同时提交之前的所有日志

    非对称网络分区

    如果不做特殊处理,会反复出现新的选举,打断正常的 IO,造成,可用性降低的问题,一般可以通过 pre-vote 解决,例如,每次发起选举之前,先发起 pre-vote 如果获得大多数 pre-vote 选票,再增大 term 发起选举 vote 投票。为了避免问题描述的情况,其他节点只需要在收到 pre-vote 请求时,判断一下 leader 是否还在,一般实现上,判断最近和 leader 是否正常通信,如果有,那么说明 leader 正常在线,直接拒绝 pre-vote 即可。

    网络安全

    SQL 注入

    对用户的输入控制不严,导致黑客可以通过拼接 SQL 的方式进行攻击
"SELECT * FROM user WHERE username = " + uname + "ADN password = " + pwd

类似这种如果我传入 username = “ resolmi’# “,这样 SQL 语句就变成了

SELECT * FROM user WHERE username = 'resolmi' #ADN password = ''

#后把后面的 password 注释掉,这样就可以不用密码直接获取到 resolmi 的信息

解决方案就是严格过滤用户输入,但是这样会比较麻烦,目前比较好的解决方案是通过 DB 的预编译功能,通过占位符占位,MySQL 编译的时候就会将参数转义后填充到占位符中

MyBatis 中 # 和 $ 区别:#{}是预编译的方式,能防止 SQL 注入,${}是字符拼接的方式,会有 SQL 注入的问题

CSRF

Cross-site request forgery,中文名,跨站请求伪造

CSRF 攻击要满足两个条件

  1. 登录了受信任的网站 A,比如 tb
  2. 在不登出 tb 的情况下,访问危险网站 B

由于同源策略实际上是限制一个域名的 js,在未经允许的情况下不能读取另一个域名的内容,所以 ajax 提交是不能跨域的,因为 ajax 是可以读取响应的,而 Form 表单提交则没有跨域的问题,因为 Form 提交后,原页面是无法获取新页面的内容的,同理 GET 请求也是允许跨域的

同源:ip,协议,端口一致

Ajax 跨域请求实际上服务端是会收到请求的,但是浏览器如果接收到服务端的返回值没有Access-Control-Allow-origin说明不允许跨域就不会处理这条返回信息

所以当访问恶意网站的时候,恶意网站会向安全网站 tb 发起一个恶意的 get/post 请求,这个请求就会携带 tb 的 cookie 去执行该操作,进而达成跨站请求攻击

解决方案

  1. Http referer:根据请求的来源判断是否合法,但是这个 Referer 是浏览器提供的,是可以修改的

  2. csrftoken:
    对于 GET/POST 请求可以在 cookie 中加一个 csrftoken 字段,当发起请求的时候将 csrftoken 加入 url 或者 body 中,因为同源策略,危险 B 网站是无法访问 tb 的 cookie 的,所以也就无法伪造 csrftoken,服务端接收后验证下 cookie 和 url 中的是否一致就 ok 了。

    但是如果该站点存在 XSS,黑客可以通过 XSS 注入 cookie,那么就失效了。所以比较保险的方式是使用 session,在用户访问页面的时候生成一个 Token,存放到服务端 session 中,当发起请求的时候将 token 加到 url 或者 body 中(注意不能放到 cookie 中),这样黑客就无法伪造 token 了

  3. 验证码:执行关键操作时候需要输入验证码,这样黑客同样无法伪造

    XSS

    Cross Site Scripting,跨站脚本攻击,这个其实就是对用户的输入过滤不严格,导致黑客可以向网页插入恶意的 js 脚本,当其他用户访问到该页面脚本就会执行,窃取用户信息,笔者之前年轻不懂事的时候还曾经挖过几个小网站的 xss 漏洞(都反馈给相关人员了,不过有的也没理我就是了😂)

解决方案

  1. 输入过滤,一定程度上可以解决,这种方案整体还是不太可行,笔者之前挖过的一个网站就是使用输入过滤,但是最终还是被我绕过了
  2. 对 HTML 进行转义,很多模板引擎都自带转义功能
  3. Http-only Cookie,本质上并没有阻止 XSS,只是防止窃取 cookie

HTTP 请求篡改

  1. 采用 HTTPS
  2. 请求参数签名
  3. 客户端 IP 黑/白名单

    套路 CODE

    生产者消费者

    import java.util.*;
    import java.util.stream.*;

    public class ProducerConsumer1{
    /*
    多生产者消费者
    signal/await 模型
    */

    //缓存区
    private static List<Integer> buffer=new ArrayList<>();

    //缓冲区的最大值
    private static int MAX=3;

    //当前的缓冲区大小,需要加 volatile 保证可见性
    private static volatile int size=0;

    //锁
    private static final Object LOCK = new Object();

    //模拟 produce 数据
    private static int data=0;

    public static void main(String[] args) {
    Stream.of("Produce1","Produce2","Produce3","Produce4","Produce5").forEach(name->{
    new Thread(()->{
    try{
    produce();
    }catch(Exception e){
    e.printStackTrace();
    }
    },name).start();
    });
    Stream.of("Consumer1","Consumer2","Consumer3","Consumer4","Consumer5").forEach(name->{
    new Thread(()->{
    try{
    consumer();
    }catch(Exception e){
    e.printStackTrace();
    }
    },name).start();
    });
    }

    public static void produce()throws InterruptedException{
    while(true){
    synchronized(LOCK){
    while(size>=MAX){
    LOCK.wait();
    }
    buffer.add(++data);
    size++;//这里不用加锁,单线程
    System.out.println(Thread.currentThread().getName()+" produce "+ data);
    Thread.sleep(1000);
    LOCK.notifyAll();
    }
    }
    }

    public static void consumer () throws InterruptedException{
    while(true){
    synchronized(LOCK){
    while(size==0){
    LOCK.wait();
    }
    int temp=buffer.remove(0);
    size--;
    System.out.println(Thread.currentThread().getName()+" consumer "+ temp);
    Thread.sleep(1000);
    LOCK.notifyAll();
    }
    }
    }
    }

    死锁

    public class DeadLock{

    private static Object resourceA = new Object();

    private static Object resourceB = new Object();

    public static void main(String[] args) {
    Thread A=new Thread(()->{
    synchronized(resourceA){
    System.out.println("Thread A acquire resourceA");
    try{
    TimeUnit.SECONDS.sleep(2);
    }catch(InterruptedException e){}
    synchronized(resourceB){
    System.out.println("Thread A acquire resourceB");
    System.out.println("A do some thing");
    }
    }
    });

    Thread B=new Thread(()->{
    synchronized(resourceB){
    System.out.println("Thread B acquire resourceB");
    try{
    TimeUnit.SECONDS.sleep(2);
    }catch(InterruptedException e){}
    synchronized(resourceA){
    System.out.println("Thread B acquire resourceA");
    System.out.println("B do some thing");
    }
    }
    });
    A.start();
    B.start();
    }
    }

    单例

    DCL

    public class SingleTonDCL{

    private static volatile SingleTonDCL instance=null;

    //私有化构造器
    private SingleTonDCL(){
    if (instance !=null){
    throw new RuntimeException("实例已经存在,请通过 getInstance() 方法获取");
    }
    }

    //懒汉式
    public static SingleTonDCL getInstance(){
    if(instance==null){
    synchronized(SingleTonDCL.class){
    if(instance==null){
    //这里会有重排序的问题,instance 还没有初始化完成就返回了
    //所以需要加 volatile
    instance=new SingleTonDCL();
    }
    }
    }
    return instance;
    }
    }

    枚举

    //1、除枚举方式外,其他方法都会通过反射或者序列化的方式破坏单例
    public enum SingleTonEnum{
    INSTANCE;
    }

    饿汉

    public class SingleTonHungry{
    /*
    线程安全,但是消耗比较大,在类第一次加载的时候就会初始化
    但是也不一定马上会用,一般我们希望用的时候再创建
    */
    private static final SingleTonHungry instance=new SingleTonHungry();

    //私有化构造器
    private SingleTonHungry(){
    if (instance !=null){
    throw new RuntimeException("实例已经存在,请通过 getInstance() 方法获取");
    }
    }

    public static SingleTonHungry getInstance(){
    return instance;
    }
    }

    内部类

    public class SingleTonInnerClass{

    //私有化构造器
    private SingleTonInnerClass(){}

    private static class SingleTonHolder{
    static{
    //当 getInctance 静态方法 访问 SingleTonHolder 的静态变量
    //的时候才会初始化内部类,所以也是属于懒汉式,并且是线程安全的
    System.out.println("Inner class");
    }
    private static SingleTonInnerClass instance=new SingleTonInnerClass();
    }

    static{
    //先初始化外部类
    System.out.println("SingleTon Outer class");
    }

    public static SingleTonInnerClass getInstance(){
    return SingleTonHolder.instance;
    }
    }

    LRU

class LRUCache {

HashMap<Integer, Node> map = null;

int capacity = 0;

Node head = null;

Node tail = null;

public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}

public int get(int key) {
Node node = map.get(key);
if (node == null) {
return -1;
}
removeNode(node);
insert2head(node);
return node.val;
}

public void put(int key, int value) {
Node node = map.get(key);
if (node == null) {
node = new Node(key, value);
insert2head(node);
map.put(key, node);
} else {
removeNode(node);
node.val = value;
insert2head(node);
}
if (map.size() > capacity) {
map.remove(tail.prev.key);
removeNode(tail.prev);
}
}

public void insert2head(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}

//移除 Node 节点
public void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}

class Node {
Node prev, next;
int key, val;
public Node (int key, int val) {
this.key = key;
this.val = val;
}
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

P & NP

  1. P(polynominal)问题:有多项式时间算法,算得很快的问题。
  2. NP(Nondeterministic polynominal)问题:算起来不确定快不快的问题,但是我们可以 快速验证 这个问题的解。
  3. NP-hard 问题:比 NP 问题都要难的问题。
  4. NP-complete 问题:属于 NP 问题,且属于 NP-hard 问题。
  5. NPC 类问题:首先,它得是一个 NP 问题;然后,所有的 NP 问题都可以约化到它。
  6. NP 难问题:即所有的 NP 问题都能约化到它,但是它不一定是一个 NP 问题。NP-Hard 问题要比 NPC 问题的范围广,NP-Hard 问题没有限定属于 NP