八股文-Redis

Redis
,

数据库结构

Server:DB = 1:N
DB内kv由字段dict(dict类型)存储；过期时间由字段expires(dict类型)负责，key均为SDS对象。
过期Key由访问时删除(惰性删除) 或 定时删除(随机访问过期Key的过期时间，删除过期Key)

RDB保存时不保存过期Key，加载时忽略过期Key。
AOF删除过期Key时显示追加DEL命令，加载忽略过期Key。
复制时主服务器显示发送DEL命令，从库不删除过期Key（从库可能返回已过期Key？）。

业务主逻辑

main

serverCron

更新服务器的各类统计信息
清理数据库中的过期键值对（执行时间上限为HZ的25%，从上次执行结束的数据库开始清理，每次测试20个Key，若25%的key失效，则继续清理；数据库过期Dict中若不满1%，不进行清理）
关闭和清理连接失效的客户端
渐进式Hash
触发RDB备份和AOF重写、Append

acceptTcpHandler

默认每次事件处理1000个accept请求。
创建Client时设置fd为非阻塞，并添加对应的readable事件

readQueryFromClient

默认每次事件处理最多读16k数据。
事件处理库封装了epoll(linux, 水平触发),select(其他),kqueue(BSE),以及evport(Solaris)。

epoll边沿触发不确保只通知一次，需要配合EPOLLONESHOT选项实现仅一次通知。

Select监控列表以位掩码实现，上限1024；每次调用，fd集合需要在用户态和内核态传递；返回后需要轮询整个监控列表，否则无法确定事件是否发生，复杂度O(n)。
Poll以链表代替位掩码，无上限(影响性能)；每次调用，fd集合需要在用户态和内核态传递；返回后需要轮询，复杂度O(n)

handleClientsWithPendingWrites

Redis在写入fd失败后注册epoll读事件。

集群

Redis默认slot数量为16384，hash函数为CRC16。
客户端直接向节点发送命令，若key不在对应节点上，返回MOVED错误。

节点内，slot所有的key由clusterState结构中的slots_to_keys维护。5.0版本以后slots_to_keys为radix tree基数树，树的key为hashSlot+kv.key。5.0版本之前由skipList存储。

发布和订阅

普通订阅由pubsub_channels(dict)维护，key为channel，value为client列表。
模式订阅由pubsub_patterns(list)维护，node为pubsubPattern对象{client, pattern}。
PUBLISH时服务器优先向pubsub_channels中对应client列表发送消息，然后遍历模式订阅列表，逐个匹配。

事务

Redis通过MULTI，EXEC，WATCH等命令实现事务功能。Redis不支持回滚，即不支持事务的原子性，错误出现通常为指令格式错误，即编程错误。

数据结构

SDS(Simple Dynamic String)

定义

1
2
3
4
5
struct sdshdr {
    int len;
    int alloc;
    char buf[];
}

优化

空间预分配（APPEND/SETRANGE）: len < 1M 时分配两倍空间；至多多分配1M
空间释放：修改操作不会导致空间缩小(空间只增加不缩小，空间扩充行为类似Java的ArrayList、HashMap)

链表(adlist)

标准双向链表

QuickList(3.2引入)

双向链表，Node的具体数据zl类型为ZipList，中间节点可以设置LZF压缩

Dict(字典)

基于HashMap实现，HashMap以链地址法处理Hash冲突。考虑到Redis主逻辑为单线程，
字典主体结构由 类型 + 双Hash表 + RehashIndex + 迭代器计数器 组成。字典Rehash过程为渐进式Hash，Hash内Entry不保存hash值，因此需要重新计算Hash值。

渐进式Hash过程：
分配 ht[1] 空间， rehashidx 设置为 0。
在 rehash 进行期间， 对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值+1。
随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

字典迭代器分为安全和不安全两种，安全迭代器用于KEYS，可以在迭代过程中对字典进行修改。

IntSets

typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;

encoding仅升级不降级。

ZipList

ZipList内存分布：
…

Entry内存分布：

编码字段包含data长度信息。（字符串类型在类型位后显示指定，其他隐式指定）

列表插入时若空间不足会除非内存分配，由于prevlen字段长度非固定，可能会导致连锁更新。

ZipMap

2.6版本废弃。

Skip List

复杂度：平均O(logN)，最差O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;

redisObject

类型

OBJ_STRING
OBJ_LIST
OBJ_SET
OBJ_ZSET
OBJ_HASH
OBJ_MODULE
OBJ_STREAM(Redis 5.0 新增特性)

编码

OBJ_ENCODING_RAW
OBJ_ENCODING_INT
OBJ_ENCODING_HT（Dict类型）
OBJ_ENCODING_ZIPMAP (ZipMap类型，2.6版本废弃，数量小时采用ZipList存储Hash)
OBJ_ENCODING_LINKEDLIST
OBJ_ENCODING_ZIPLIST
OBJ_ENCODING_INTSET
OBJ_ENCODING_SKIPLIST
OBJ_ENCODING_EMBSTR
OBJ_ENCODING_QUICKLIST
OBJ_ENCODING_STREAM

具体编码

OBJ_STRING 编码类型可以为 OBJ_ENCODING_RAW(SDS) 或 OBJ_ENCODING_INT 或 OBJ_ENCODING_EMBSTR(最大限制不同版本不一致，39 -> 39，以能匹配Jemalloc的64字节Arena为准)
OBJ_LIST 编码类型 3.2版本之后为 OBJ_ENCODING_QUICKLIST， 3.2版本之前为 OBJ_ENCODING_LINKEDLIST 或 OBJ_ENCODING_ZIPLIST (控制参数：list_max_ziplist_entries，默认512; list-max-ziplist-value 默认 64)
OBJ_SET 编码类型为 OBJ_ENCODING_HT 或 REDIS_ENCODING_INTSET
OBJ_ZSET 编码类型为 OBJ_ENCODING_ZIPLIST 或 REDIS_ENCODING_SKIPLIST(实际为skipList+dict) (控制参数zset_max_ziplist_entries, zset_max_ziplist_value)
OBJ_HASH 编码类型为 OBJ_ENCODING_ZIPLIST 或 OBJ_ENCODING_HT

内存回收

Redis内存回收机制由引用计数实现，即RedisObject的refcount。
Redis 4.0引入Lazy Free，空间回收交由Bio线程处理。（Lazy Free仅仅是异步处理free，在交由bio处理之前，主线程负责unlink）