[大数据]牛客网项目——项目总结

1. MySQL

1.1 存储引擎

MySQL自从5.1开始，默认引擎就是InnoDB，之前是MyISAM。InnoDB是支持事务（Transactions）的，NDB也是支持事务的，但是他是集群中的引擎，其他的引擎不支持集群。但是MySQL能不做集群就不做集群，分布式的任务比较麻烦。

InnoDB特点：

1. 支持事务（Transactions）
2. 支持外键（Foreign key support）

1.2 事务

1.2.1 事务的特性

1. 原子性

2. 一致性

3. 隔离性

4. 持久性

1.2.2 事务的隔离性

1. 并发异常
   1. 第一类更新丢失
   2. 第二类更新丢失
   3. 脏读
   4. 不可重复读
   5. 幻读
2. 隔离级别
   1. Read Uncommitted
   2. Read committed
   3. Repeatable Read
   4. Serializable

1.2.3 Spring事务管理

1. 声明式事务
2. 编程式事务

1.3 锁

1.3.1 范围

1. 表级锁：开销小，加锁快，发生锁冲突概率高，并发度低，不会死锁。ISAM默认表级锁，不支持行级锁，锁粒度比较粗，并发能力一般。
2. 行级锁：开销大，加锁慢，发生锁冲突概率低，并发度高，会死锁。InnoDB默认行级锁，并发能力较强。

1.3.2 类型（InnoDB）

1. 共享锁（S）：行级，读取一行
2. 排他锁（X）：行级，更新一行
3. 意向共享锁（IS）：表级，准备加共享锁
4. 意向排他锁（IX）：表级，准备加排他锁
5. 间隙锁（NK）：行级，使用范围条件时，对内存不存在的记录加锁。一是防止幻读，而实为了满足恢复和复制的需要。

第一列表示事务1加锁的级别，第一行表示事务2加锁的级别

1. 我准备读（意向共享锁（IS）），别人不能写（排他锁（X））
2. 我准备写（意向排他锁（IX）），别人不能读也不能写（共享锁（S），排他锁（X））
3. 我正在读这一行（共享锁（S）），别人不能写也不能准备写（排他锁（X），意向排他锁（IX））
4. 我正在写一行（排他锁（X）），别人什么也不能做

1.3.3 加锁

1. 增加行级锁之前，InnoDB会自动给表加意向锁

2. 执行DML语句时，InnoDB会自动给表加排他锁

3. 执行DQL语句

   1. 共享锁（S）：SELECT … FROM … WHERE … LOCK IN SHARE MODE ;
   2. 排他锁（X）：SELECT … FROM … WHERE … FOR UPDATE ;
   3. 间隙锁（NK）：上述SQL采用范围条件时，InnoDB对不存在的集里自动增加间隙锁

1.3.4 死锁

1. 场景

   ? 事务1：UPDATE T SET … WHERE ID = 1 ; UPDATE T SET … WHERE ID = 2 ;

   ? 事务2：UPDATE T SET … WHERE ID = 2 ; UPDATE T SET … WHERE ID = 1;

2. 解决方案

   1. 一般InnoDB会自动检测，并使一个事务回滚，另一个事务继续
   2. 设置超时参数 innodb_lock_wait_timeout ;

3. 避免死锁

   1. 不同的业务并发访问多个表时，应约定以相同的顺序来访问这些表
   2. 以批量的方式处理数据时，应先对数据排序，保证线程按固定的顺序来处理数据
   3. 在事务中，如果要更新记录，应该直接申请足够级别的锁，即排他锁

1.3.5 悲观锁（数据库）

数据库加的锁都是悲观锁，认为一定会出问题，得先加锁

1.3.6 乐观锁（自定义）

1. 版本号机制：UPDATE … SET …, VERSION=#{version+1} WHERE … AND VERSION=${version}
2. CAS算法（Compare and swap）：无锁算法，设计三个操作数（内存值，旧值，新值），当V等于A时，采用原子方式用B的值更新V的值。该算法通常采用自旋操作（自旋锁），他的缺点是：
   • ABA问题：某线程将A改为B，再改回A，则CAS会认为A没有修改过
   • 自旋操作采用循环方式实现，加锁时间过长会带来巨大开销
   • CAS只能保证一个共享变量的原子操作

1.4 索引

B+Tree（InnoDB）

• 数据分块存储，每一块称为一页
• 所有值都是按顺序存储的，并且每一个叶子到根的距离相同
• 非叶子节点存储数据边界，叶子节点存储指向数据行的指针
• 通过边界缩小数据范围，避免全表扫描，加快查找速度

2. Redis

2.1 数据类型

2.2 过期策略

Redis会把设置了过期时间的key 放入一个独立的字典里，在key过期时不会立刻删除它。

Redis会通过以下两种策略删除过期key

• 惰性删除

  客户端访问某个key时，Redis会检查该key是否过期，过期则删除

• 定期扫描

  Redis默认每秒执行10次过期扫描（配置hz选项），扫描策略如下：

  1. 从过期字典中随机选择20个key
  2. 删除这20个key中已过期的key
  3. 如果过期的key比例超25%，则重复步骤1

2.3 淘汰策略

当Redis占有的内存已经超过最大限制（maxmemory）时，可采用如下策略（maxmemory-policy），让Redis淘汰一些数据，腾出空间进行读写服务

• noeviction：对可能导致增大内存的命令返回错误（大多数写命令，DEL除外）
• volatile-ttl：在设置了过期时间的key中，选择剩余寿命（TTL）最短的淘汰
• volatile-lru：在设置了过期时间的key中，选择使用次数最少（LRU）的淘汰
• volatile-random：在设置了过期时间的key中，随机选择一些淘汰
• allkeys-lru：在所有key中，选择使用次数最少（LRU）的淘汰
• allkeys-random：在所有key中，随机选择一些淘汰

LRU算法：维护一个链表，用于顺序存储被访问过的key。在访问数据时，最新访问过的key被移动到表头，即最近访问的key在表头，最少访问的key在表。

近似LRU算法（Redis）：给每个key维护一个时间戳，淘汰时随机采样5个key，从中淘汰最旧的key，如果还是超出内存限制，则继续随机淘汰。优点，比LRU节省内存，但是可以的到非常近似的效果

2.4 缓存穿透

• 场景

  查询根本不存在的数据，使得请求直达存储层，导致负载过大，甚至宕机

• 解决方案

  1. 缓存空对象：存储层未命中后，仍将空值存入缓存层。再次访问缓存层直接返回空值。
  2. 布隆过滤器：将所有key提前存入布隆过滤器，在访问缓存层前，先通过拦截器拦截，若请求时不存在的key，则直接返回空值

## 2.5 缓存击穿

• 场景

  一份热点数据，访问量非常大。在其缓存失效瞬间，大量请求直达存储层，导致服务崩溃。

• 解决方案

  1. 加互斥锁：对句数访问加互斥锁，当一个线程访问该数据时，其他线程只能等待。这个线程访问过后，缓存中数据将被重建，节是其他线程就可以直接从缓存取值。
  2. 永不过期：不设置过期时间，所以不会出现上述问题，这是“物理”上的不过期。或者为每个value设置逻辑过期时间，当发现该值逻辑过期时，使用单独的线程重建缓存。

2.6 缓存雪崩

• 场景

  由于某些原因，缓存层不能提供服务，导致所有请求直达存储层，造成存储层宕机。

• 解决方案

  1. 避免同时过期：设置过期时间时，附加一个随机数，避免大量的ke同时过期。
  2. 构建高可用Redis缓存（集群）：部署多个Redis实例，个别结点宕机，依然可以保持服务整体可用。
  3. 构建多级缓存：增加本地缓存，在存储层前多加一级屏障，降低请求直达存储层的几率。
  4. 增加本地缓存：对存储层增加限流措施，当请求超出限制时，对其提供降级服务。

2.7 分布式锁

• 场景

  修改时，经常需要先将数据读取到内存，在内存中修改后再存回去。在分布式应用中，可能多个进程同时执行上述操作，而读取和修改非原子操作，所以会产生冲突。增加分布式锁，可以解决此类问题。

• 基本原理

  同步锁：在多个线程都能访问到的地方，做一个标记，标识该数据的访问权限。

  分布式锁：在多个进程都能访问到的地方，做一个标记，标识该数据的访问权限。

• 实现方式

  1. 基于数据库实现分布式锁
  2. 基于Redis实现分布式锁
  3. 基于zookeeper实现分布式锁

• 使用Redis实现分布式锁的原则

  1. 安全属性：独享。在任一时刻，只有一个客户端持有锁
  2. 活性A：无死锁。即便持有锁的客户端或者网络被分裂，锁仍然可以被获取。
  3. 活性B：容错。只要大部分Redis结点都活着，客户端就可以获取和释放锁。

• 单Redis实现分布式锁

  1. 获取锁使用指令

     SET resource_name my_random_value NX PX 30000

     NX：仅在key不存在时才执行成功

     PX：设置锁的自动过期时间

  2. 通过LUA脚本释放锁

     if redis.call("get",KEYS[1]) == ARGV[1] then
         return redis.call("del",KEYS[1])
     else return 0 end
     

     可以避免删除别的客户端获取成功的锁：

     A加锁——A阻塞——因超时释放锁——B加锁——A恢复——释放锁

• 多Redis实例实现分布式锁

  Rellock算法，该算法有现成的实现，其Java版本库为Redisson

  1. 获取当前Unix时间，毫秒为单位。
  2. 依次尝试从N个实例，使用相同的key和随机值获取锁，并设置响应超时时间。如果服务器没有在规定时间内响应，客户端应该尽快尝试另外一个Redis实例。
  3. 客户端使用当前时间减去开始获取锁的时间，得到获取锁使用的时间。当且仅当大多数Redis结点都获取到了锁，并且使用的时间小于锁失效的时间，锁才算取得成功。
  4. 如果取到了锁，key的真正有效时间等于有效时间减去获取锁使用的时间。
  5. 如果获取锁失败，客户端应该在所有的Redis实例上进行解锁。

3. Spring

3.1 Spring IOC

Bean的作用域

3.2 Spring AOP

3.3 Spring MVC

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系