前言

熟悉了Redis的内部数据结构后，本篇文章将介绍面向使用者的Redis的五种基本数据结构的内部实现原理。

我们首先把上一篇文章的数据类型编码方式表搬过来做参考：

数据类型 编码方式
OBJ_STRING int、embstr、raw
OBJ_LIST LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET intset、HT
OBJ_ZSET ZipList、HT、SkipList
OBJ_HASH ZipList、HT

String

  • String的基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。
  • 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。
  • u如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

image-20250220155303909

List

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

  • 在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。
  • 在3.2版本之后，Redis统一采用QuickList来实现List，其结构图如下：

image-20250220155903407

Set

Set是Redis中的单列集合，满足下列特点：不保证有序；保证元素唯一；求交集、并集、差集。代码如下：

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
28
robj *setTypeCreate(sds value) {
    // 判断value是否是数值类型 long long 
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
        // 如果是数值类型，则采用IntSet编码
        return createIntsetObject();
    // 否则采用默认编码，也就是HT
    return createSetObject();
}

robj *createIntsetObject(void) {
    // 初始化INTSET并申请内存空间
    intset *is = intsetNew();
    // 创建RedisObject
    robj *o = createObject(OBJ_SET,is);
    // 指定编码为INTSET
    o->encoding = OBJ_ENCODING_INTSET;
    return o;
}

robj *createSetObject(void) {
    // 初始化Dict类型，并申请内存
    dict *d = dictCreate(&setDictType,NULL);
    // 创建RedisObject
    robj *o = createObject(OBJ_SET,d);
    // 设置encoding为HT
    o->encoding = OBJ_ENCODING_HT;
    return o;
}
  • 为了查询效率和唯一性，set一般采用O(1)查询的Dict。Dict中的key用来存储元素，value统一为null；
  • 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，使用连续内存空间以节省内存，此时查询复杂度为O(logn)

Set的实现可以用下图表示，注意ptr的实际指向是根据encoding来确定的。

image-20250220160525441

ZSet

Zset底层采用SkipList加Dict实现，SkipList负责存储score和ele并按照score排序；Dict负责根据ele快速查找到其对应的socre。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// zset结构
typedef struct zset {
    // Dict指针
    dict *dict;
    // SkipList指针
    zskiplist *zsl;
} zset;

robj *createZsetObject(void) {
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;
    // 创建Dict
    zs->dict = dictCreate(&zsetDictType,NULL);
    // 创建SkipList
    zs->zsl = zslCreate(); 
    o = createObject(OBJ_ZSET,zs);
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}

其结构图如下所示：image-20250220163349904

当元素数量不多时，HT和SkipList在时间开销上的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：

  1. 元素数量小于zset_max_ziplist_entries，默认值128
  2. 每个元素都小于zset_max_ziplist_value字节，默认值64
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// zadd添加元素时，先根据key找到zset，不存在则创建新的zset
zobj = lookupKeyWrite(c->db,key);
if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
// 判断是否存在
if (zobj == NULL) { // zset不存在
    if (server.zset_max_ziplist_entries == 0 ||
        server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
    { // zset_max_ziplist_entries设置为0就是禁用了ZipList，
        // 或者value大小超过了zset_max_ziplist_value，采用HT + SkipList
        zobj = createZsetObject();
    } else { // 否则，采用 ZipList
        zobj = createZsetZiplistObject();
    }
    dbAdd(c->db,key,zobj); 
}
// ....
zsetAdd(zobj, score, ele, flags, &retflags, &newscore);

如果当前ZSet使用Ziplist实现且在添加元素后不满足以上两条规则，需要转换为SkipList编码方式：

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
28
29
30
31
32
int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
    /* 判断编码方式*/
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {// 是ZipList编码
        unsigned char *eptr;
        // 判断当前元素是否已经存在，已经存在则更新score即可        if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {
            //...略
            return 1;
        } else if (!xx) {
            // 元素不存在，需要新增，则判断ziplist长度有没有超、元素的大小有没有超
            if (zzlLength(zobj->ptr)+1 > server.zset_max_ziplist_entries
 		|| sdslen(ele) > server.zset_max_ziplist_value 
 		|| !ziplistSafeToAdd(zobj->ptr, sdslen(ele)))
            { // 如果超出，则需要转为SkipList编码
                zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
            } else {
                zobj->ptr = zzlInsert(zobj->ptr,ele,score);
                if (newscore) *newscore = score;
                *out_flags |= ZADD_OUT_ADDED;
                return 1;
            }
        } else {
            *out_flags |= ZADD_OUT_NOP;
            return 1;
        }
    }  // 本身就是SKIPLIST编码，无需转换
    if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
       // ...略
    } else {
        serverPanic("Unknown sorted set encoding");
    }
    return 0; /* Never reached. */
}

Ziplist本身没有排序功能，而且没有键值对的概念，因此需要约定：

  • ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后
  • score越小越接近队首，score越大越接近队尾，按照score值升序排列

image-20250220164604835

Hash

Hash结构与Zset结构都是键值存储，唯一区别是Hash不需要以score为value并排序。因此Hash的底层编码只是将Zset的编码去掉了SkipList。

同样的，在元素数量较少时会采用ZipList编码以节省内存。ZipList中相邻的两个entry 分别保存field和valueu。Hash结构转为Dict的条件有两个：

  • ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
  • ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

image-20250220165536928

__END__