hhhzua 发布的文章

Redis有两种持久化方式:RDB和AOF

  • RDB 是将Redis的内存数据生成一份快照保存在dump.rdb二进制文件中
  • AOF是将每一次执行的修改命令都以追加写入的方式写入appendonly.aof文件中

RDB是redis的默认持久化方式,可以配置持久化策略:save N M,表示N秒内至少M个改动则会触发一次RDB操作,RDB持久化的时候不会阻塞Redis的读写请求,因为Redis从主线程中fock出一个子线程bgsave,可以共享主线程中的数据,当读取redis内存数据时,主线程的读请求不受影响,当写请求时,会借助写时复制技术,将该写请求会操作的数据拷贝一份出来写入dump.rdb,这样主线程可以继续处理写请求

RDB的优缺点:

优点:

dump.rdb是二进制文件,可以很快用于数据恢复

缺点:

  1. 如果redis宕机的话,会丢失上一次RDB同步到宕机之间的数据
  2. RDB 需要将内存的数据都写入到dump.rdb,如果频繁执行的话,开销比较大,影响性能

AOF是同步地将修改写入到appendonly.aof,能最大限度地减少数据丢失的风险,为什么说是最大限度而不是完全避免呢?先看ROF的刷盘策略:

  1. appendfsync always 每次执行命令都刷盘
  2. appendfsync everysec 每秒刷盘一次
  3. appendfsync no 由系统决定什么时候刷盘

当修改命令写入到文件缓存后,需要将缓存刷到磁盘才能真正完成持久化,所以如果刷盘策略不是第一种,则可能丢失短时间内的数据。

AOF重写,因为ROF持久化的是命令而不是具体数据,所以可能有一些命令是重复的,redis有一个机制称为bgrewriteof,用于生成新的aof文件。

比起RDB,ROF还是有一个缺点,就是重放命令来恢复数据效率太低了,Redis 4.0版本为了解决这个问题,提供了混合持久化方案:

在AOF重写时,执行一次RDB,加上增量AOF一起写入到appendonly.aof,这样在恢复数据时,就可以先将RDB恢复,再重放AOF,重启效率提高。

在业务中,我们使用缓存来换缓解数据库压力,只有当缓存不存在或者缓存失效才让请求访问到数据库,这就不可避地需要保证缓存和数据库的数据的一致性

常见的,有3种更新策略:

  1. 先更新数据库,再更新缓存
  2. 先删除缓存,再更新数据库
  3. 先更新数据库,再删除缓存

先更新数据库,再更新缓存

这种方案不推荐,因为考虑有两个写请求A、B,当A更新数据库后,B请求又更新了数据库,但是因为A更新缓存的时候有网络波动导致,B的更新缓存早于A,则会导致缓存中的数据是脏数据的情况

先删除缓存,再更新数据库

这种方案也不推荐,考虑一个写请求A,一个读请求B,当A删除缓存后,B请求到达,查询不到缓存,则立即查询数据库,并更新缓存,A请求此时更新数据库,则导致缓存和数据库数据不一致

先更新数据库,再删除缓存

推荐,先更新数据库再删除缓存,则可以避免并发的写请求进行缓存更新导致缓存不是最新的数据的情况,当然极端情况下,一个读请求,在更新数据前查询到了数据,在删除缓存后写入了缓存,也会出现数据不一致,但是一般来说读请求效率比写请求更高,不会出现这种情况,

实在需要考虑来确保一致性,也可以采用 延时双删 的方案:在删除缓存后,先sleep,再执行一次删除,具体sleep的时长可以根据业务中一个请求的耗时来决定,确保删除可能的由读请求产生的脏数据。

当然,同步的删除操作,会降低吞吐量,可以考虑将删除操作放在MQ异步执行,或者订阅binlog来异步删除缓存

但是如果缓存删除失败,则也会出现数据不一致的情况,这时候可以考虑重试删除

还可以结合主从同步来考虑,比如延时双删的sleep时间大于主从同步时间,避免从库查到旧数据写入缓存后形成脏数据

最后,可以设置过期时间来确保可能的脏数据被刷新,来达到最终一致性

缓存穿透

当大量请求访问的数据在并不存在时,也不能建立缓存,每个请求都会打到数据库,当请求量超过数据库承载能力时,数据库可能被打挂

比如,访问id为0的用户,数据库和缓存都不存在该用户数据,不断访问这个id则会导致数据库崩溃

解决方案:

1、使用布隆过滤器,将数据写入过滤器,如果是不存在的数据就无法再过滤器中查询到数据,丢弃请求或者返回默认值

2、增加参数校验,不合法的参数进行拦截

3、即使不存在的数据也加上缓存,设置合理的超时时间

缓存击穿

热点key缓存过期,导致大量并发访问热点数据的请求查询不到缓存时,需要查询数据库,由于同一时间压力陡增,数据库有崩溃的风险

解决方案:

1、热点数据不过期或者自动续期

2、加互斥锁,查询不到缓存时,只有第一个请求访问数据库

缓存雪崩

大量热点key,同一时间过期,导致大量请求打到数据库,数据库压力像雪崩一样越来越大

解决方案:

1、热点数据不过期或者自动续期

2、设置的缓存时间加上随机值,避免同时过期

3、加互斥锁,查询不到缓存时,只有第一个请求访问数据库

事务

事务的基本属性(ACID)

  1. 原子性(Atomicity):事务内的所有操作要么一起成功,要么一起失败,是一个不可分割的整体
  2. 一致性(Consistency):事务的执行不会破坏数据库的完整性约束,包括数据的完整性和业务逻辑的完整性
  3. 隔离性(Isolation):不同事务之间互不干扰,彼此隔离
  4. 持久性(Durability):事务执行的结果应该是被数据库保存的,不会回滚

事务的并发问题

  1. 脏读:事务A未提交的数据被另一个事务B读取,事务A被回滚后,事务B读取到的就是脏数据,称为脏读
  2. 不可重复读:事务A查询到数据后,事务B更新了数据并提交,事务A再查询数据时,结果就不一样了,就叫不可重复读
  3. 幻读:事务A将某个条件下数据更新时,事务B又插入了一条符合条件的数据,在事务A结束后,发现还有未更新的数据,跟发生幻觉一样,这就叫幻读

区分不可重复读和幻读
不可重复读侧重于修改,幻读侧重于新增或者删除
不可重复读侧重于事务内获取数据的变化,幻读侧重于事务执行后的变化
要解决不可重复读,锁住相应的行即可,要解决幻读则需要锁表

事务的隔离级别

  1. 读未提交:这种隔离级别下,事务之间没有隔离,会出现脏读、不可重复读、幻读
  2. 读已提交:这种隔离级别下,事务内部是隔离的,但是并行的事务会互相影响,会出现不可重复读、幻读
  3. 可重复读:这种隔离级别下,事务通过MVCC机制根据事务的版本区分是否可以获取数据,不会出现不可重复读,但是还会有幻读
  4. 串行化:事务按序执行,不互相影响,不会出现幻读

开启事务的两种方式

  • begin/end transaction

    执行begin transaction 语句之后,并不会立即开启事务,而是当有sql执行的时候才正式开启事务
  • start transaction with consistence snapshot

    执行语句之后,立即开启事务
    

如何解决事务并发的问题

  • 脏读:RC以及以上隔离级别,通过MVCC机制,读取当前sql可见的数据快照,即可避免脏读
  • 不可重复读:在RR及以上隔离界别,通过MVCC机制,读取当前事务可见数据快照,即可避免不可重复读
  • 幻读:RR级别的next-key lock可以避免幻读,串行化隔离级别下,所有事务无法并行,可以避免幻读

索引

索引是一种排好序的用于提高查询效率的数据结构。

Mysql的数据是存储在磁盘中的,而从磁盘查找数据最大的成本是磁盘的寻道操作,所以一般来说随机的磁盘IO的查询数据最大的性能瓶颈,由此,Mysql借助索引来实现高效查找。

为什么Mysql使用B+树作为索引结构?
Mysql中的索引是由B+树实现的,B+树实质上是一颗多路平衡查找树,类似的查找树有很多数据结构,比如平衡二叉树、红黑树,还有同样可以高效查找的hash表、跳表,之所以选择B+树而不是其他的数据结构,最重要的原因是B+树查询所需要的随机磁盘IO最少。

那为什么说B+树的查询效率高呢?可以通过3层的B+树可查找的数据量来体现:

假设主键是bigint类型(8个字节),每个索引项的指针是6个字节,索引上的每个节点都是一个页游16KB,也就是一个节点可以容纳16KB/(8+6)B=1142个索引项,如果B+树为3层,那有2层非叶子结点作为索引,最后1层叶子结点存放了数据,假设一条记录1KB,也就是一个节点可以存放16KB/1KB=16条数据,总共1142114216约为2kw,也就是3次随机磁盘IO下可检索的数据量为2kw,可以满足大多数场景了

那为什么也不选择B树呢?再对比B树和B+树:

  1. B树的非叶子结点和叶子结点都包含数据(索引+记录的磁盘地址),B+树只有叶子结点有数据,非叶子结点只有索引,所以相同数据量下,B树需要的节点更多,可能会有更大的树高
  2. B树中要做范围查询,需要做中序遍历,而在B+树中,叶子结点之间由双向指针形成了双向链表,做范围查询时,只需在叶子节点链表中遍历即可,涉及的磁盘IO更少
  3. B树的插入删除都可能需要重新做平衡,B+树因为有数据都在叶子结点上,而且所有的非叶子节点都在叶子结点上冗余了,所以插入删除操作大多数都可以直接在叶子节点上完成,不需要对B+树的结构做调整,只有在插入后节点饱存在节点分裂,相比起来插入删除效率更高

在Mysql中,不同的存储引擎的索引有所差别:

InnoDB

InnoDB的索引可分为主键索引和二级索引,其中主键索引是存放了数据的聚集索引(也叫聚簇索引),二级索引则是非聚集索引,依靠叶子结点上的主键值,去主键索引中进行回表查询来获取完整的数据。

当然,如果二级索引是复合索引,sql中查询的字段都在复合索引中可以找到,则不会再去回表查询,这也叫覆盖索引

MyISAM

MyISAM的索引和数据是分别存储的,所以没有聚集索引,所有的索引都只能从索引树中获取到指向磁盘的地址,再进行磁盘IO获取到数据

大多数时候,为了性能,我们都不会在在业务中使用串行化的事务隔离级别,所以必然存在事务并发的问题,对同一个数据的并发处理,很明显会发生竞态条件,产生不可预测的结果,对于需要确定性的程序来说是不可接受的,所以需要锁来保证并发操作下的数据正确性

按锁的定义可分为:

  • 共享锁(S Lock)
  • 排他锁(X Lock)

共享锁一般是读锁,当一个事务获取了共享锁之后,另一个事务也可以对相同的数据获取共享锁,但是如果此时另一个事务想要获取相同数据的排他锁则会被阻塞,必须等待共享锁的释放

排他锁一般是写锁,当一个事务获取了排他锁后,另一个事务无论获取排他锁还是共享锁都会阻塞,需要等待排他锁匙放

也就是共享锁共享锁兼容,排他锁与任何锁都不兼容

InnoDB实现了行级的排他锁共享锁,而为了支待在不同粒度上进行加锁操作,InnoDB允许行级锁与表级锁共存,实现了一种称为意向锁的额外的加锁方式,意向锁是表级的锁,用于表明是否有事物请求对数据加行级锁:

  • 意向共享锁(IS Lock):事务想要获得一张表中某几行的共享锁
  • 意向排他锁(IX Lock):事务想要获得一张表中某几行的排他锁

当事务对一行数据请求排他锁时,会同时对表请求意向排他锁,当另一个事务请求对全表进行修改,没有意向排他锁时,需要一行一行地扫描是否有行被锁定,而有意向排他锁时,则不需要判断,直接等待行锁匙放就行了。

InnoDB三种行锁算法:

  1. 行记录锁(Record Lock

    
    在行记录上加锁,防止事务间删除或者修改数据
    
  2. 间隙锁(Gap Lock

    
    锁住各个记录之间的间隙,不锁记录本身,为了防止幻读
    
  3. 临键锁(Next-Key Lock)

    
    锁住行记录本身与各个记录之间的间隙,为了防止幻读
    

注:可重复读隔离级别(RR)下,MVCC就可以解决快照读的幻读问题,为什么还要next-key 锁来防止并发呢?因为除了RR下的简单select语句是快照读,select … for update、select … lock in share mode都是当前读,还有inert、update、delete都是当前读,所以还需要next-key来防止幻读。

Next-Key Lock是Recod Lock 与 Gap Lock的组合,主要是为了防止幻读,是RR隔离级别下默认的行级锁算法:

  • 唯一索引的等值检索时

    • 如果查询记录存在,next-key lock会退化成record Lock
    • 如果查询记录不存在,next-key lock会退化成gap Lock
  • 唯一索引的范围检索时,next-key lock 退化为间隙锁和记录锁
  • 非唯一索引的等值检索时

    • 如果查询记录存在,除了加next-key lock外,还会加gap lock
    • 如果查询记录不存在,只会加next-key lock,然后退化成gap lock
  • 非唯一索引的范围检索时,next-key lock 不会退化为间隙锁和记录锁
  • 非索引检索则会加上全表next-key lock,也就是锁全表

InnoDB之所以可以实现行级锁,是因为有聚簇索引,基于聚簇索引可以实现在一棵索引树上产生竞态条件,从而实现行级锁

MyISAM中只支持表级锁,表级的共享锁、排他锁锁是Mysql的server层通过一种元数据锁的结构实现的。

InnoDB中依靠锁实现了一个事务的写操作与另一个事务的写操作的隔离性,以下是不同隔离级别下所使用的锁机制:

  • RC:insert、update、delete加Recode Lock
  • RR:iselect、nsert、update、delete都加Recod Lock
  • 串行化:读写都加表锁

MVCC

mvcc是多版本兵法控制,用来在数据库中控制事务并发读写的方法,mvcc只在隔离级别为RC、RR有效,是通过undo log中的版本链与ReadView一致性视图来实现的,mvcc就是在多个事物同时存在时,select语句找到具体版本链上的哪个版本,然后在找到的版本上返回所记录的数据。

原理

通过在每行记录上增加两个隐藏字段,分别保存了记录的创建时的版本号,和删除时的版本号,每开启一个新的事务版本号都会递增。

INSERT

插入的时候,将当前事务的ID作为创建的版本号

SELECT

根据两个条件查找记录:

  • 创建版本号小于当前事务ID
  • 删除版本号不存在或者大于当前事务ID

UPDATE

实际上是插入了一个新行,并且删除了原来记录行,插入的新行创建版本号为当前事务ID,删除的旧行的删除版本号为当前事务ID

DELETE

将当前事务ID作为行的删除版本号

上面的机制保证了,一个事务不会读取到另一个事务新产生的变更。

InnoDB的MVCC实现

InnoDB中会增加三个隐藏的列:

  1. DB_TRX_ID

    记录最近更新这条数据的事务ID
    
  2. DB_ROLL_PTR

    回滚指针,用于配合undo log找到该行的所有旧版本,形成一个版本链
    
  3. DB_ROW_ID

    隐藏的主键,表没有主键或者非NULL唯一列时会创建
    

ReadView是事务在快照读时创建的读视图,记录了事务快照图那一刻,系统中活跃的事务的ID,用于做可见性判断,即当前事务执行快照读的时候,创建一个ReadView,用于判断当前事务可以看到哪些版本的数据,如果当前活跃的事务不符合可见性,还会通过DB_ROLL_PTR回滚指针去undo log中取出历史版本的DB_TRX_ID来做比较,直到获取到满足条件的版本。

ReadView的结构:

  • trx_list

    
    当前活跃的事务列表
    
  • up_limit_id

    
    活跃事务列表中最小的事务ID
    
  • low_limit_id

    
    当前系统还没有分配的下一个事务ID
    
    

可见性判断:

  1. 首先比较DB_TRX_ID < up_limit_id则符合可见性,否则进入下一个判断
  2. 判断DB_TRX_ID ≥ low_limit_id,成立则说明这个版本是在当前ReadView之后才创建的,不可见,进入下一个判断
  3. 最后判断DB_TRX_ID是否在trx_list中,如果不在则说明该版本在创建ReadView之前就commit了,符合可见性,否则说明在创建ReadView时这个版本的事务还是活跃的,没有commit,对应的数据也不可见

不同的隔离级别下,创建ReadView的时机不同

  • RC下,每次快照读都会创建ReadView
  • RR下:只有第一次快照读会创建ReadView,后面

RC隔离级别下,每次快照读都会创建ReadView,也就导致在两次快照读之间,另一个事务的变更会被读取,所以存在 不可重复读

mvcc的优点,读操作不阻塞写操作,写操作也不阻塞读操作,实现了不加锁的并发读写

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,
并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 
对于给定的输入,保证和为 target 的不同组合数少于 150 个。

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

解析

    涉及到排列组合问题,或者说求多个解的问题,都优先考虑DFS。套用DFS公式:

  • 找到递归边界:组合之和大于等于target,或者最新加入组合的元素大于等于target-sum(当前组合)
  • 再找到状态遍历:for range candidates,搜索树的每个节点都可以选取所有元素
  • 然后看如何递归进行状态转移,在这里由于每次搜索都增加一个元素,只要递归调用中更新当前组合就行,递归调用里基于入参往组合里添加元素
  • 最后考虑回溯,即当达到递归边界时,递归调用返回,当前分支搜索结束,进行下一个分支搜索,需要将调用递归前往当前组合中添加进来的元素剔除掉

实现


//用于获取所有组合
var targetFrom = make([][]int, 0)
//用于去重
var alreadyMap = make(map[string]struct{})

func getTargetBy(candidates []int, childSet []int, target int) bool {
    sum := intSum(childSet)
    //终止条件
    if sum >= target {
        if sum == target {
            return true
        }
        return false
    }

    length := len(candidates)
    for i := 0; i < length; i ++ {
        childSet = append(childSet, candidates[i])
        if getTargetBy(candidates, childSet, target) {
            tmpSet := make([]int, len(childSet))
            copy(tmpSet, childSet)
            key := getKey(tmpSet)
            if _, ok := alreadyMap[key]; !ok {
                targetFrom = append(targetFrom, tmpSet)
                alreadyMap[key] = struct{}{}
            }
        }
        //回溯
        childSet = childSet[:len(childSet)-1]
    }
    return false
}

func intSum(arr []int) int {
    sum := 0
    for _,v := range arr {
        sum += v
    }
    return sum
}

func getKey(arr []int) string {
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] < arr[j]
    })
    key := ""
    for i,v := range arr {
        subKey := fmt.Sprintf("%v", v)
        if i == 0 {
            key = subKey
        } else {
            key += fmt.Sprintf("-%s", subKey)
        }
    }
    return key
}