深入解析redis的数据结构_redis头插法

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

1 数据结构

1.1动态字符串SDS

我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

• 获取字符串长度的需要通过运算
• 非二进制安全
• 不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。
例如，我们执行命令：

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“虎哥”的SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

SDS有多种结构（sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64），用于存储不同长度的字符串，分别代表25byte=32byte、28byte=256byte、216byte=65536byte=64kb、232byte=4GB。

例如，一个包含字符串“name”的sds结构如下：

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：
如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；

+1:是因为最后一位预留给“\0”，代表结束

如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。

上述分配称为内存预分配。

SDS的优点

• 获取字符串长度的时间复杂度为O(1)

  直接获取结构体中len的值

• 支持动态扩容

  内存预分配

• 减少内存分配次数

  内存预分配。在分配内存的时候，因为用户进程不能直接操作硬件的资源分配，所以需要进行系统调用切换到内核态，由内核进程进行进行硬件资源的分配，这一过程是相对耗时的，采用预分配，一次多分配一些内存，不至于每次频繁地请求资源（当然，预分配存在一个问题就是，操作系统一次分配的资源可能用不完，所以就会产生内存碎片，关于redis的内存碎片问题，我们后续讨论）

• 二进制安全

C字符串只能保存文本格式，不能保存保存音频、视频、图片等二进制的数据：比如“abc\0123”,C字符串会把’\0’当作结束标记，而’123‘就被忽略了，所以二进制不安全，而SDS根据len判断结束，因此二进制安全。

SDS可以理解为一个动态扩容的char型数组

1.2 IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

结构如下：

typedef struct intset {
    uint32_t encoding; /* 编码方式，支持存放16位、32位、64位整数*/
    uint32_t length; /* 元素个数 */
    int8_t contents[]; /* 整数数组，保存集合数据*/
} intset;
1
2
3
4
5

其中的encoding包含三种模式，表示存储的整数大小不同：

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t)) /* 2字节整数，范围类似java的short*/
#define INTSET_ENC_INT32 (sizeof(int32_t)) /* 4字节整数，范围类似java的int */
#define INTSET_ENC_INT64 (sizeof(int64_t)) /* 8字节整数，范围类似java的long */
1
2
3
4
5

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

寻址算法：只需要找到元素的index，就能定位到元素的起始地址

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：

• encoding：4字节
• length：4字节
• contents：2字节 * 3 = 6字节

IntSet升级

现在，假设有一个intset，元素为{5,10，20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节：

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。
以当前案例来说流程如下：

• 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
  

• 倒序依次将数组中的元素拷贝到扩容后的正确位置
  
  
  

• 将待添加的元素放入数组末尾
  

• 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4
  

IntSet新增流程

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);// 获取当前值编码
    uint32_t pos; // 要插入的位置
    if (success) *success = 1;
    // 判断编码是不是超过了当前intset的编码
    if (valenc > intrev32ifbe(is->encoding)) {
        // 超出编码，需要升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 在当前intset中查找值与value一样的元素的角标pos
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0; //如果找到了，则无需插入，直接结束并返回失败
            return is;
        }
        // 数组扩容
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 移动数组中pos之后的元素到pos+1，给新元素腾出空间
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    // 插入新元素
    _intsetSet(is,pos,value);
    // 重置元素长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
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

IntSet升级流程

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 获取当前intset编码
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 获取新编码
    uint8_t newenc = _intsetValueEncoding(value);
    // 获取元素个数
    int length = intrev32ifbe(is->length); 
    // 判断新元素是大于0还是小于0 ，小于0插入队首、大于0插入队尾
    int prepend = value < 0 ? 1 : 0;
    // 重置编码为新编码
    is->encoding = intrev32ifbe(newenc);
    // 重置数组大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    // 倒序遍历，逐个搬运元素到新的位置，_intsetGetEncoded按照旧编码方式查找旧元素
    while(length--) // _intsetSet按照新编码方式插入新元素
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    /* 插入新元素，prepend决定是队首还是队尾*/
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 修改数组长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
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

小结

Intset可以看做是特殊的整数数组，具备一些特点：

• Redis会确保Intset中的元素唯一、有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询

IntSet可以理解为一个整型数组，采用二分查找的方式，因此查询很快

1.3 Dict（字典）

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。
Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

typedef struct dictht {
    // entry数组
    // 数组中保存的是指向entry的指针
   dictEntry **table; 
    // 哈希表大小
   unsigned long size; 
    // 哈希表大小的掩码，总等于size - 1
    unsigned long sizemask;
    // entry个数
    unsigned long used; 
} dictht;
1
2
3
4
5
6
7
8
9
10
11

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
   } v; // 值
    // 下一个Entry的指针
    struct dictEntry *next; 
} dictEntry;
1
2
3
4
5
6
7
8
9
10
11

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

h & sizemask 是效率更高的求余运算 ，值就是数组中的索引值

所以结构体就会变成这样：

如果存在hash冲突呢？

字典 Dict在解决hash冲突的时候采用的 头插法 解决的
字典结构在java中和hashMap比较相似，但是在hashMap在解决hash冲突的时候，在1.7以及之前采用的头插法，在1.8开始为了解决并发下扩容可能发生死链的情况，就使用尾插法了。
那为什么redis不要尾插法呢？
其实答案很简答，redis最大的特点就是单线程，没并发。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

typedef struct dict {
    dictType *type; // dict类型，内置不同的hash函数
    void *privdata;  // 私有数据，在做特殊hash运算时用
    dictht ht[2]; // 一个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用
    long rehashidx;  // rehash的进度，-1表示未进行
    int16_t pauserehash; // rehash是否暂停，1则暂停，0则继续
} dict;
1
2
3
4
5
6
7

最终字典Dict的结构就如图所示

Dict扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

used：哈希表中entry的数量
size：数组的大小

• 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
• 哈希表的 LoadFactor > 5 ；

static int _dictExpandIfNeeded(dict *d){
    // 如果正在rehash，则返回ok
    if (dictIsRehashing(d)) return DICT_OK; 
    // 如果哈希表为空，则初始化哈希表为默认大小：4
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    // 当负载因子（used/size）达到1以上，并且当前没有进行bgrewrite等子进程操作
    // 或者负载因子超过5，则进行 dictExpand ，也就是扩容
   if (d->ht[0].used >= d->ht[0].size &&
       (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio){
       // 扩容大小为used + 1，底层会对扩容大小做判断，实际上找的是第一个大于等于 used+1 的 2^n
        return dictExpand(d, d->ht[0].used + 1);
   }
    return DICT_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Dict的收缩

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩：

// t_hash.c # hashTypeDeleted() 
...
if (dictDelete((dict*)o->ptr, field) == C_OK) {
    deleted = 1;
    // 删除成功后，检查是否需要重置Dict大小，如果需要则调用dictResize重置
     /* Always check if the dictionary needs a resize after a delete. */
    if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
...
1
2
3
4
5
6
7
8
9

// server.c 文件
int htNeedsResize(dict *dict) {
   long long size, used;
   // 哈希表大小
   size = dictSlots(dict);
   // entry数量
   used = dictSize(dict);
  // size > 4（哈希表初识大小）并且 负载因子低于0.1
  return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL));
}
1
2
3
4
5
6
7
8
9
10

int dictResize(dict *d){
   unsigned long minimal;
   // 如果正在做bgsave或bgrewriteof或rehash，则返回错误
   if (!dict_can_resize || dictIsRehashing(d)) 
        return DICT_ERR;
  // 获取used，也就是entry个数
   minimal = d->ht[0].used;
    // 如果used小于4，则重置为4
    if (minimal < DICT_HT_INITIAL_SIZE)
       minimal = DICT_HT_INITIAL_SIZE;
     // 重置大小为minimal，其实是第一个大于等于minimal的2^n
        return dictExpand(d, minimal);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

无论是扩容还是收缩都会执行下面这块核心代码：dictExpand(d, minimal)

Dict的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询和sizemask有关。因此必须对哈希表中每一个key重新计算索引，插入新的哈希表，这个过程称为rehash，过程就是这样的：
①计算hash表的realeSize，值取决于当前要做的是扩容还是收缩:

②按照新的realeSize申请内存内存空间，创建dictht，并赋值给dict.ht[1]

③将dict.rehashidx =0,标示开始rehash

④将dict.ht[0] ]中的每一个dictEntry 都rehash到dict.ht[1]

实际上，这个过程并不是一次性完成的，这里先卖个关子

⑤将dict.ht[1] 赋值给dict.ht[0] ，给dict.ht[1] 初始化为空哈希表，释放原来的dict.ht[0]的内存

图解rehash过程

• 假如有以下的一个字典结构，此时哈希表的数组空间已经使用完了
  

• 如果此时客户端有加入了一个数据
  

• 首先计算hash表的realeSize，现在的元素个数是5，比(5+1)大1的最小的2^N的是 8，所以新的申请的哈希表的中数组的大小是8,并赋值给哈希表ht[1]：
  

• 接下来开始迁移，首先给ht[1]的字段赋值，并标记rehash过程开始
  

• 利用 h & sizemask来计算元素应该存储到ht[1]中数组中的哪个索引位置，依次迁移各个entry

• 让ht[0]中的数组指针指向新的数组，同时断开ht[1]中对数值指针对新数组的引用
  
  
• 重置ht[1]，恢复成没有初始值，同时修改ht[1]的字段，最后修改字典的rehashidx标记为-1 rehash过程结束
  
  上述过程整体看起来似乎没有太大的问题，但是这其中隐含了着一个非常大的风险：我们现在元素非常少，rehash时间短；假如有数百万的数据呢？数据迁移的过程将会是非常耗时的操作，我们知道redis是单线程的，如果redis花费大量的时间去做这个，那么客户端的指令就会被阻塞。所以我们之前卖的关子说【④将dict.ht[0] ]中的每一个dictEntry 都rehash到dict.ht[1]】不是一次性完成的。

渐进式rehash

小结

Dict虽然查询性能比较好，但是却浪费空间，因为其中会有大量的指针
DIct可以理解为两个hashTable的结构体

1.4 ZipList

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

ZipList特殊在没有指针，真正的双端链表节点与节点之间存在两个指针，因此ZipList省空间

ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412

ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
  现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：
  
  加入现在新增了一个254字节的entry
  
  因此这个【新增的entry】 后面的【entry】的previous_enry_length就得用5个字节表示【新增的entry】的大小，因此原来250字节的entry就变为254字节了，它后面的也得改。。。。
  

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。

连锁更新对性能影响非常大，可能会频繁地申请内存和销毁内存。但是发生的概率是很低的，必须要有N个连续的、长度为250~253字节之间的entry，目前redis的作者并没有解决这个问题

小结

ZipList特性：

• 压缩列表的可以看做一种连续内存空间的"双向链表"
• 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
• 如果列表数据过多，导致链表过长，可能影响查询性能
• 增或删较大数据时有可能发生连续更新问题

1.5 QuickList

以下是QuickList的和QuickListNode的结构源码：

typedef struct quicklist {
    // 头节点指针
    quicklistNode *head; 
    // 尾节点指针
     quicklistNode *tail; 
    // 所有ziplist的entry的数量
     unsigned long count;     
    // ziplists总数量
    unsigned long len;
    // ziplist的entry上限，默认值 -2 
     int fill : QL_FILL_BITS;       // 首尾不压缩的节点数量
    unsigned int compress : QL_COMP_BITS;
    // 内存重分配时的书签数量及数组，一般用不到
     unsigned int bookmark_count: QL_BM_BITS;
     quicklistBookmark bookmarks[];
} quicklist;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct quicklistNode {
    // 前一个节点指针
     struct quicklistNode *prev;
    // 下一个节点指针
     struct quicklistNode *next;
     // 当前节点的ZipList指针
     unsigned char *zl;
     // 当前节点的ZipList的字节大小
    unsigned int sz;
     // 当前节点的ZipList的entry个数
     unsigned int count : 16;    
    // 编码方式：1，ZipList; 2，lzf压缩模式
     unsigned int encoding : 2;
    // 数据容器类型（预留）：1，其它；2，ZipList
     unsigned int container : 2;
    // 是否被解压缩。1：则说明被解压了，将来要重新压缩
     unsigned int recompress : 1;
     unsigned int attempted_compress : 1; //测试用
     unsigned int extra : 10; /*预留字段*/
} quicklistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

内存结构图

小结

QuickList的特点：

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

1.6 SkipList（跳表）

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同。

首先，看下传统链表

对于传统链表，它不适合于访问中间的数字，因为它要从头或者从尾进行遍历，主要是因为它的指针跨度太小。

// t_zset.c
typedef struct zskiplist {
    // 头尾节点指针
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 最大的索引层级，默认是1
    int level;
} zskiplist;
1
2
3
4
5
6
7
8
9

// t_zset.c
typedef struct zskiplistNode {
    sds ele; // 节点存储的值
    double score;// 节点分数，排序、查找用
    struct zskiplistNode *backward; // 前一个节点指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 下一个节点指针
        unsigned long span; // 索引跨度
    } level[]; // 多级索引数组
} zskiplistNode;
1
2
3
4
5
6
7
8
9
10

完整的调表结构

小结

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

1.7 RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下：

RedisObject的头部就要占16个字节
假如说现在有10个字符串，关头部就得占160个字节。。。。所以redis对字符串类型进行了不同的编码

Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：

Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

2 五种数据类型

2.1 String

String是Redis中最常见的数据存储类型：
1、其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。

2、如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。

RAW编码的RedisObject和SDS是需要通过指针引用的

可以看出EMBSTR编码的String类型中RedisObject和SDS是一块连续的内存空间

分析下为什么EMBSTR编码只需要一次内存分配？

• 首先一个RedisObject16个字节（EMBSTR没有指针）
• SDS中len、allo、flag和结束符各占1个字节，数据占44字节总共占48字节
• 所以EMBSTR编码的字符串占64（48+16）个字节，而内存分配的基本单位是页（64字节），所以一次内存分配即可。

3、如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

Long_MAX真的很大，9223372036854775807

2.2 List

Redis的List类型可以从首、尾操作列表中的元素：

哪一个数据结构能满足上述特征？

• LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
• QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

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

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

void pushGenericCommand(client *c, int where, int xx) {
    int j;
    // 尝试找到KEY对应的list
    robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
    // 检查类型是否正确
    if (checkType(c,lobj,OBJ_LIST)) return;
    // 检查是否为空
    if (!lobj) {
        if (xx) {
            addReply(c, shared.czero);
            return;
        }
        // 为空，则创建新的QuickList
        lobj = createQuicklistObject();
        quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
                            server.list_compress_depth);
        dbAdd(c->db,c->argv[1],lobj);
    }
    // 略 ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

robj *createQuicklistObject(void) {
    // 申请内存并初始化QuickList
    quicklist *l = quicklistCreate();
    // 创建RedisObject，type为OBJ_LIST
    // ptr指向 QuickList
    robj *o = createObject(OBJ_LIST,l);
    // 设置编码为 QuickList
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}
1
2
3
4
5
6
7
8
9
10

2.3 Set

Set是Redis中的单列集合，满足下列特点：

• 不保证有序性
• 保证元素唯一
• 求交集、并集、差集

可以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？

• HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

Set是Redis中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高

• 为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存

set-max-intset-entries的默认值是512：

2.4 ZSet

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值：

• 可以根据score值排序后
• member必须唯一
• 可以根据member查询分数

因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？

• SkipList：可以排序，并且可以同时存储score和ele值（member）
• HT（Dict）：可以键值存储，并且可以根据key找value

// zset结构
typedef struct zset {
    // Dict指针
    dict *dict;
    // SkipList指针
    zskiplist *zsl;
} zset;
1
2
3
4
5
6
7

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;
}
1
2
3
4
5
6
7
8
9
10
11

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

• 元素数量小于zset_max_ziplist_entries，默认值128
• 每个元素都小于zset_max_ziplist_value字节，默认值64

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. */
}
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

ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

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

2.5 Hash

Hash结构与Redis中的Zset非常类似：

• 都是键值存储
• 都需求根据键获取值
• 键必须唯一
  
  

区别如下：

• zset的键是member，值是score；hash的键和值都是任意值
• zset要根据score排序；hash则无需排序

因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可：