芝麻の杂谈

Redis整理

11 min

基本数据结构

redis支持的几种数据类型

  1. String
  2. List
  3. Set
  4. Hash
  5. ZSet

其中这五种数据类型分别对应的底层数据结构为：

1. string：SDS，简单动态字符串

这是Redis最为常用的类型，方法也比较简单

Get、Set、Exists、StrLen、Del、MSet、MGet

当然，如果你想存储整数，SDS底层也实现了兼容，还提供了这些方法

Incr、IncrBy、Decr、DecrBy

同时，还支持设计、查看过期时间：

Expire、TTL

当然，你也可以使用最为经典的方式，也就是常见的分布式锁使用的方式

SetNx key value EX time

或者设置过期时间

SetEx key time vaule

当然如果你觉得需要使用毫秒，可以使用PX

应用场景：

  1. 分布式锁
  2. 缓存对象
  3. 保存token等带有过期时间的信息

数据结构：

SDS是比较简单的数据结构，代码的实现类似于下:

struct{
    int len         //buf长度
    int alloc       //分配空间大小
    int flag        //存储数据类型（int还是string）
    byte[] buf      //字节数组，可以灵活转换int和string
}

优点：

  1. 计算好剩余容量，不会出现缓冲区溢出
  2. 字符串拼接方便

list：使用quicklist实现

list的存在就是作为链表使用的，当然，有些时候我们也可以把它当作任务队列使用。

常用命令：

LPush key vaule value …

RPush key value value …

LPop key

RPop key

LRange key start end

BLPop、BRPop：阻塞等待POP，可以当作阻塞任务队列使用，可以配合timeout使用

BLPop key1 [key2 …] timeout

应用场景：

  1. 之前提到的消息队列，BRPOPLPUSH使用这种方法还能进行一个已经消费消息的保存

数据结构：

quicklist也是个有趣的结构，它在3.2版本后取代了双向链表和压缩列表成为了list的底层数据结构。但是实际上，它并没有取代两者，而是结合了两者组成了一种新的数据结构。

首先先说压缩列表：

它的数据结构十分诡异，是由类似于数据的连续内存快组成的，表头部分有三个字段：

  1. zlbytes：整个压缩列表的分配的字节数（）
  2. zltail：表尾偏移量
  3. zllen：压缩列表节点数量

表头之后就是正式元素了，他们是由多个entry拼接而成，每个entry的构成：

  1. prevlen，前一个节点的长度，为了快速跳到下一个头节点
  2. encoding，当前节点类型和长度
  3. data实际数据

表尾有一个字段 zlend：压缩列表的结尾，固定为0xff

缺点：连锁更新

quicklist：和双向链表唯一的区别就是把node换成了压缩列表

typedef struct quicklistNode {
    //前一个quicklistNode
    struct quicklistNode *prev;
    //下一个quicklistNode
    //前一个quicklistNode
    struct quicklistNode *next;
    //quicklistNode指向的压缩列表
    unsigned char *zl;
    //压缩列表的的字节大小
    unsigned int sz;
    //压缩列表的元素个数
    //后一个quicklistNode
    unsigned int count;
    //ziplist中的元素个数
    ziplist *node;
} quicklistNode;

为了解决压缩列表的连锁更新问题，redis实现了新的结果，listpack

其实和压缩列表几乎没有差距，只是每个entry储存的信息不一样了

头部信息：

  1. 总字节数
  2. 元素数量

数据部分： 每个entry的信息：

  1. encoding
  2. data
  3. len

每个entry只记录自己的长度，就不会因为别人的更新而更新，同时，前一个节点往前读固定个字节，也能够知道前一个节点的头部在哪里。

Hash：使用ziplist或者hash表实现，当然，在7.0之后已经不适用ziplist而是使用listpack来实现

比较常用的存储ky信息的的结构，常用命令：

HSet key subkey subvalue

HGet key subkey

MHSet key subkey1 subvalue1 …

MHGet key subkey1 …

HLen key

HGelAll key

HIncr key subkey

应用场景：

多级层次缓存

数据结构：

  1. 当Hlen<512，并且每个元素大小小于64字节的时候，用ziplist或者listpack来存

  2. 否则使用hash表来存

哈希表没什么好讲的，冲突采用拉链法解决，额外提一嘴，解决哈希冲突一共有三种方法：

  1. 开放地址法
  2. 再Hash法
  3. 拉链法

哈希表也是要扩容的，当负载因子=哈希表内kv数量/哈希表大小>=1时候，采用渐进式rehash的方式进行扩容（没有进行AOF重写或者RDB快照的时候），档负载因子>=5的时候，强制rehash

set：整数集合或者hash表

集合，没啥好说的。

常见命令：

SAdd

SRem

SMenbers key用于获取全部元素

SISMenber

SRandMenber key count

Spop key count

同时支持集合运算

SInter、SUnion、SDiff

SInterStore tostore key1 key2 …

SUnionStore、SDiffStore同上

应用场景：

  1. 点赞
  2. 抽奖

数据结构：

元素都是整数，且元素个数小于512的时候就使用整数集合，否则使用hash表。

整数集合本质上就是个整数数组，但是带有长度和编码方式。编码方式主要关注存储数组类型，int8、int16、int32、int64。

最开始从最初存入的整数的大小开始，支持数组升级，但是不支持降级。

ZSet，有序集合

被问得最多的类型，其实没什么可说的，无非是底层结构是个跳表。

ZSet的作用保存<元素,Score>对，并且按照Score排序。

支持的操作：

  1. ZADD key score menber
  2. ZREM key menber
  3. ZScore key menber
  4. ZCard key
  5. ZIncrBy key toadd menber
  6. ZRange key start end [WithSocre]
  7. ZRevRange
  8. ZRangeByScore key min max

应用场景：

  1. 排行榜

数据结构

怎么讲清楚跳表是个难的事情，但其实也很简单。

跳表本质上还是个链表，但是链表的每个节点可能有多层，上层节点可以指向同一级高度的下个节点。这样可以跨越更多层级去寻找到下个节点。类似于二分的思路。

  1. 查询过程： 从最高节点往后查找，若tagert大于等于高层节点的next值，则直接跳转到高层节点的next；若小于，则降低一层继续上述操作

  2. 插入过程： 同理，找到插入位置，然后建立完第一层之后，随机一个数，如果<=0.25，加高一层。

更加常见的问题：

为什么要使用跳表，而不是二叉树、B+树等

  1. 不使用二叉树：

    需要进行ZRange操作，跳表局部性更好

    跳表比B树更加省内存

    易于实现

  2. 不是用B+树

    插入更加方便

    实现更加简单

    内存中，不像磁盘一样在乎IO次数

持久化

两种方式，AOF日志和RDB快照，一种是增量写，一种是全量写

AOF

客户端的写命令实际的执行流程

  1. 写内存
  2. 记录命令到AOF日志

为什么是先写内存

  1. 不阻塞操作
  2. 写内存会校验语法，防止日志记录出错

AOF存在问题

  1. 日志丢失
  2. 阻塞下一条写操作

三种写回策略（落盘策略）

AOF日志并不是直接落盘，执行完写操作后写AOF日志先写入到server.aof_buffer缓冲区，然后调用命令write()将数据拷贝到内核缓冲区page cache，落盘则需要等待调用fsync()方法，至于什么时机调用，有三种策略

  1. Always 这时候调用fsync方法的是主线程，会阻塞
  2. EverySec 这时候调用fsync方法的是子线程，不阻塞
  3. No

AOF重写机制

当AOF文件过大的时候，会执行AOF重写，一般会调用一个子进程在后台执行。

对于增量部分，使用写时复制机制。子进程拷贝父进程副本的时候，一开始并不拷贝共享内存，在父进程修改后才具有独立的父子数据副本。

此时父进程增量的修改在写入AOF缓冲区的时候，会被同步写入到AOF重写缓冲区中，子进程继续同步修改之前的数据。

待子进程执行完毕后，将AOF重写缓冲区的数据增量加入到AOF文件中

执行完成后使用新的AOF文件替换旧的文件。

RDB

有两种方式生成RDB快照，一种是阻塞主线程的save，一种是不阻塞主线程的bgsave

save的触发逻辑：

每900s一次，如果900s内对数据库进行了至少一次修改

每300s一次，如果300s内对数据库进行了至少10次修改

每60s一次，如果60s内对数据库进行了至少10000次修改

RDB快照同样是写时复制。

Reids 八股笔记