发表更新数据库 / Redis29 分钟读完 (大约4400个字)

Redis

参考 官方文档，对象编码，数据类型，命令列表，代码仓库（7.4.2），事务，可编程性，《Redis 设计与实现》。

基本概念

Redis 服务器是事件驱动程序，主要使用单线程 + I/O 多路复用处理客户端请求。不过也会使用后台线程，例如，使用 UNLINK 命令可以异步删除大键（Redis 4.0），以及将网络 I/O 委托给其他线程来提高性能（Redis 6.0）。Redis 的瓶颈在内存和网络，CPU 很少成为 Redis 的瓶颈，而且由于多线程的复杂性，Redis 核心逻辑没有使用多线程设计。如果要提高 CPU 的利用率，可以在同一个机器中启动多个 Redis 实例，并将它们视为不同的服务器。

过期删除策略：定时删除会将 CPU 时间用在和当前任务无关的过期键上，影响服务器的响应时间。惰性删除检查当前处理的键是否过期，如果不对过期键执行命令就会导致内存泄露。定期删除结合前两种策略的优点，是时间和空间的折中。Redis 使用惰性删除 + 定期删除的策略，定期删除从一定数量的数据库中随机检查一定数量的键，如果过期就删除。

Key 淘汰策略：配置 maxmemory 来指定使用内存的上限，当超过该限制时会执行淘汰策略。概括一下：① 不淘汰键，此时只支持读命令，写命令会报错。② 使用 LRU、LFU 或者随机淘汰键。③ 使用 LRU、LFU 或者随机淘汰有过期时间的键，或者淘汰 TTL 最短的键。

Redis 使用的是近似 LRU，随机抽取少量的键，然后淘汰其中最久未被访问的键（Redis 3.0 会跟踪候选键来提高性能），不使用标准 LRU 的原因是会消耗更多内存（因为需要维护访问链表）。LFU 使用概率计数器（Morris 计数器）估计键的访问频率，结合衰减期以便计数器随时间减少，也使用上述采样方式淘汰访问频率最小的键。

通用命令

1
2
3
4
5
6
7
8
SELECT index
INFO [section [section ...]]
DEL key [key ...] | UNLINK key [key ...]
EXPIRE key seconds [NX | XX | GT | LT] | TTL key | TIME | PERSIST key
TYPE key | OBJECT ENCODING key | OBJECT IDLETIME key | OBJECT REFCOUNT key
SAVE | BGSAVE [SCHEDULE] | BGREWRITEAOF
WATCH key [key ...] | UNWATCH | MULTI | DISCARD | EXEC
EVAL script numkeys [key [key ...]] [arg [arg ...]]

数据结构

SDS

在 Redis 中，当无需修改字符串时，使用的是 C 字符串。否则，使用简单动态字符串（simple dynamic string，SDS）。相比 C 字符串有如下优点：① 获取长度的时间复杂度为 \(O(1)\)。② 自动扩容，空间预分配，不会自动缩容，但支持手动缩容。③ 二进制安全，不根据 \0 空字符判断字符串结束。

1
2
3
4
5
6
struct __attribute__ ((__packed__)) hisdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

ziplist

ziplist 是特殊编码的双向链表，非常节省内存。它存储字符串和整数值，其中整数被编码为实际整数，而不是一系列的字符。它允许在列表的任意一侧进行 push 和 pop 操作，该操作需要重新分配内存（realloc + memmove），时间复杂度和列表使用的内存量相关。

ziplist 的布局如下，<uint32_t zlbytes> 表示列表占用的字节数，<uint32_t zltail> 表示列表最后一个节点的偏移量，<uint16_t zllen> 表示列表中的节点数量（当节点数量超过 \(2^{16}-2\) 时，该值被设置为 \(2^{16}-1\)，此时需要遍历整个列表才能知道有多少节点），<uint8_t zlend> 是列表的结束标识（被设置为 0xFF）。

1
<zlbytes> <zltail> <zllen> <entry> <entry> ...  <entry> <zlend>

entry 的布局如下，<prevlen> 表示前一个节点的长度（如果小于 254 字节，则占用单个字节，否则占用 5 个字节，第一个字节被设置为 0xFE，后四个字节表示长度），<encoding> 和 <entry-data> 的编码方式取决于节点的内容。添加/删除节点可能引发级联更新（Cascade Update），不过新版 Redis 会提前计算所需空间，时间复杂度是 \(O(n)\)。

1
2
3
<prevlen> <encoding> <entry-data>
<prevlen from 0 to 253> <encoding> <entry>
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>

listpack

由于经常发生和 ziplist 的代码相关的崩溃报告，而 ziplist 实现复杂（主要源于级联更新）难以审计，所以对 ziplist 进行改进。listpack 的实现更紧凑、解析速度更快以及更易于审计和理解。listpack 的布局如下，由于没有使用偏移量，头部只占用 6 字节（ziplist 头部占用 10 字节）。依然使用 0xFF 单个字节作为结束标识，原因是这样可以很容易地识别列表的结束，而不需要额外保存末尾地址。由于没有使用偏移量，要快速定位最后一个元素实现反向遍历，很容易想到倒着存储元素的长度信息，element 的布局如下。

1
2
<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>
<encoding-type><element-data><element-tot-len>

quicklist

quicklist 是以 ziplist 或者 listpack 为节点的双向链表，结合 linkedlist 插入/删除快速以及 ziplist/listpack 节省空间的特点。

intset

inset 存储整数集合（不包含重复项），按照从小到大的顺序存储在 contents 数组中。所有元素的编码方式取决于 encoding 字段，可以将元素编码为 16、32 和 64 字节。如果当前编码方式无法存储新元素，则会将所有元素的编码方式都升级为更大的类型（不会自动降级）。因为引发升级的元素总是比现有元素都小/大，所以该新元素会存放到列表开头/结尾。

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

hashtable

ht_table 表示两个哈希表，一般只使用 ht_table[0]，而 ht_table[1] 在扩容/缩容时使用。哈希表的大小是 2 的幂，扩容的大小为第一个大于等于 ht_used[0] * 2 的 \(2^{n}\)，缩容的大小为第一个大于等于 ht_used[0] 的 \(2^{n}\)。扩容/缩容是渐进式的，在每次对哈希表执行操作时，会 rehash 一个桶（由 rehashidx 标识）。

扩容的时机：当没有在执行 BGSAVE 或者 BGREWRITEAOF 命令且负载因子大于等于 1，当在执行 BGSAVE 或者 BGREWRITEAOF 命令且负载因子大于等于 5。因为在持久化时会创建子进程，操作系统使用写时复制（COW）优化子进程的使用，所以如果存在子进程，服务器会尽可能避免扩容（避免修改共享的页面），从而避免写时复制的开销。缩容的时机：当负载因子小于 0.1 时自动缩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
};

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Keep small vars at end for optimal (minimal) struct padding */
    unsigned pauserehash : 15; /* If >0 rehashing is paused */

    unsigned useStoredKeyApi : 1; /* See comment of storedHashFunction above */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
    int16_t pauseAutoResize;  /* If >0 automatic resizing is disallowed (<0 indicates coding error) */
    void *metadata[];
};

skiplist

skiplist 使用 zset 结构作为底层实现，由跳表和哈希表组成。跳表维护多层链表，支持正序/倒序遍历，节点负责存储字符串元素 ele 和浮点数分值 score，同时会维护该节点在各层中的下一个节点的跨度 span（用于快速计算排名）。程序根据幂次定律生成节点的层数，节点层高为 k 层的概率是 (1 - ZSKIPLIST_P) * (ZSKIPLIST_P) ^ (k - 1)（其中 ZSKIPLIST_P = 0.25）。 使用跳表可以提高 ZRANGE 和 ZRANK 的效率，使用哈希表可以提高根据字符串查找分值的效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

数据类型

1
2
3
4
5
6
7
8
9
struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
};

String

使用场景：存储字节序列（文本、序列化对象和二进制数组）或者充当计数器。默认最大可以存储 512 MB 的字符串。编码方式：① int，在保存 64 位有符号整数时使用，可以看作 Java 中的 long 类型。② embstr（embedded string），默认在字符串长度小于等于 44 字节时使用，该编码将 redisObject 和 sdshdr 存储在单个内存块中，不可修改。③ raw，该编码将 redisObject 和 sdshdr 存储在不同内存块中。

1
2
3
SET key value [NX | XX] [EX seconds | PX milliseconds]
GET key | MGET key [key ...]
INCR key | INCRBY key increment | INCRBYFLOAT key increment

List

使用场景：实现栈和队列。最多可以存储 \(2^{32}-1\) 个元素。编码方式：ziplist | listpack，linkedlist，quicklist。

1
2
3
4
5
[LPUSH | RPUSH] key element [element ...]
[LPOP | RPOP] key [count]
LREM key count element
LRANGE key start stop
LLEN key

Set

使用场景：存储唯一值，计算交集、并集和差集。最多可以存储 \(2^{32}-1\) 个元素。编码方式：intset，listpack，hashtable（值被设置为 NULL）。

1
2
3
4
5
6
SADD key member [member ...]
SREM key member [member ...]
SISMEMBER key member
SMEMBERS key | SSCAN key cursor [MATCH pattern] [COUNT count]
[SINTER | SUNION | SDIFF] key [key ...]
SCARD key

Hash

使用场景：存储键值对（对象）。最多可以存储 \(2^{32}-1\) 个键值对。编码方式：ziplist | listpack，hashtable。

1
2
3
4
HSET key field value [field value ...] | HSETNX key field value
HDEL key field [field ...]
HGET key field | HGETALL key | HSCAN key cursor [MATCH pattern] [COUNT count] [NOVALUES]
HLEN key

Sorted set（ZSet）

使用场景：排行榜、速率限制器。首先按照分数排序（浮点数），然后按照字典序排序（元素都是字符串）。编码方式：ziplist | listpack，skiplist。

1
2
3
4
5
ZADD key [NX | XX] [GT | LT] score member [score member ...]
ZREM key member [member ...]
ZRANGE key start stop [BYSCORE | BYLEX] [REV] [LIMIT offset count] [WITHSCORES]
[ZRANK | ZREVRANK] key member [WITHSCORE]
ZCARD key | ZCOUNT key min max

持久化机制

持久化机制：① RDB（Redis Database），以指定的时间间隔创建数据的快照。② AOF（Append Only File），记录所有写命令。（不建议单独使用 AOF）③ No persistence，不持久化。④ RDB + AOF：组合使用 RDB 和 AOF。

相比 AOF，RDB 文件表示更紧凑，允许更快地重启（就是使用快照恢复数据）。而 AOF 文件会更大，Redis 会自动重写 AOF 来减少文件大小。在发生故障时 RDB 会丢失更多数据（因为是指定时间间隔持久化），而 AOF 默认每秒执行 fsync（也可以配置为不执行 fsync，让操作系统决定何时刷盘，或者每次查询都执行，但是会很慢），最多丢失一秒的数据。如果数据很大 fork 会占用 CPU 从而阻塞客户端命令，RDB 相比 AOF 执行 fork 的频率更高（RDB 必然会执行 fork，AOF 只有在重写时执行 fork）。

重写是根据当前数据记录写命令，而不是根据旧的 AOF 文件。在 Reids 7.0 之前，重写期间到达的所有写命令最终会写入磁盘两次，因为重写 AOF 的同时 AOF 操作也依然在执行（保证数据安全），所以写命令会写入旧文件，然后还会使用缓冲区记录写命令，等待 AOF 重写完成之后将其追加到新文件。在 Redis 7.0 之后，使用 Multi Part AOF 机制，AOF 文件被分为基本文件（最多一个）和增量文件（可能有多个）。基本文件表示重写 AOF 时的数据快照（RDB 或 AOF 格式），增量文件记录创建基本文件之后的增量更改。Redis 使用临时清单文件跟踪基本文件和增量文件，当 AOF 重写完成，Redis 执行原子切换使改临时清单文件生效。

应用场景

缓存数据

缓存穿透：频繁请求数据库中不存在的数据。解决方案：① 用户权限和参数校验，提前过滤无效请求。② 将无效键加入缓存同时设置较短的过期时间（区分无效值和正常空值），如果之后数据库中有相关数据，会导致短时间的不一致。或者可以在更新数据时删除缓存，从而保证一致性。③ 使用布隆过滤器（定期重建），一种概率数据结构，由一个位数组和多个哈希函数组成。插入元素会将所有哈希函数计算的索引位置置为 1。查询元素只要有一个计算出的索引位置不为 1，那么该元素就必定不在集合中。否则，有可能在集合中（由于哈希冲突，存在误报）。

缓存击穿：热点数据过期。解决方案：① 访问热点数据的同时重置过期时间。② 发现缓存失效时，加锁重建缓存，避免所有请求都查询数据库。其他线程会尝试加锁（使用 trylock，因为缓存重建完成之后就不需要互斥），失败之后休眠一段时间再查询缓存。③ 逻辑过期，不设置 TTL，而是在值中增加过期时间字段。如果查询缓存发现已经逻辑过期，依然加锁重建缓存，但是加锁失败的线程直接返回过期数据。

缓存雪崩：大量数据过期。解决方案：① 设计随机的过期时间（类似 Raft 里的随机选举超时），避免同时过期。

通用方案：① 缓存预热、多级缓存。② 为缓存业务添加限流（可以整体限流也可以根据用户 ID 限流）、降级（简化响应，保证核心功能稳定）和熔断（拒绝请求，防止故障扩散）策略。限流策略：固定窗口，对时间窗口内的请求计数，但是窗口切换时存在双倍流量的问题；滑动窗口，将窗口分为细粒度的时间片做计数，通过计算窗口内所有时间片计数的和来判断是否达到流量阈值，内存开销较大；漏桶算法，将请求放入桶中（排队），以恒定速率处理请求，不能处理突发流量；令牌桶算法，将令牌放入桶中（计数），以恒定的速率生成令牌，允许突发流量。③ 使用 Redis 集群提高服务可用性。

缓存一致性问题：① 更新数据不处理缓存，存在不一致的问题。② 更新数据时删除缓存。如果事务提交之后删除缓存，假设另一个请求已经读取到旧数据，但直到很久之后才设置缓存，也会存在不一致（可以延迟双删）。之所以删除缓存而不是更新缓存，是因为如果同时有多个请求更新相同的数据，更新缓存会有时序问题。③ 订阅 MySQL binlog（阿里 canal 组件，利用主从节点的日志复制），解析日志然后利用消息队列更新缓存（适合数据不过期的场景）。

分布式锁

使用 SET 命令获取分布式锁：① 设置过期时间，避免客户端宕机导致锁无法被释放。② 设置锁的持有者，在释放锁（删除键）时检查当前客户端是否持有锁，如果持有才执行释放操作（使用 Lua 脚本保证原子性）。避免客户端 A 持有的锁过期之后，释放客户端 B 持有的锁。③ 使用 Lua 脚本原子地执行 CAS 操作来解锁。

1
2
SET lock owner NX EX max-lock-time
EVAL ...script... 1 lock owner
1
2
3
4
5
6
if redis.call("get",KEYS[1]) == ARGV[1]
then
    return redis.call("del",KEYS[1])
else
    return 0
end
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×