登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›Redis核心数据结构全解析

Redis核心数据结构全解析

蚬蕞遂 2025-6-11 18:41:35
动态字符串SDS

字符串是Redis中最常用的一种数据结构

  • Redis中的Key是字符串
  • value往往是字符串或者字符串的集合
C语言字符串的缺点

Redis没有直接用C语言中的字符串，因为C语言字符串存在一些问题：

  • 获取长度：需要\(O(n)\)遍历数组
  • 非二进制安全：以\0为结束符，则字符串中不能包含\0，不能保存像图片、音频、视频文化这样的二进制数据
  • 操作不便：不可修改。进行拼接等操作时，需要考虑内存管理，存在风险
SDS

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS
SDS结构

Redis 是 C 语言实现的，其中 SDS 是一个结构体，源码如下：
  1. struct **attribute** ((**packed**)) sdshdr8 {  
  2.         uint8_t len; /* buf 已保存的字符串字节数，不包含结束标示 */  
  3.         uint8_t alloc; /* buf 申请的总的字节数，不包含结束标示 */  
  4.         unsigned char flags; /* 不同 SDS 的头类型，用来控制 SDS 的头大小 */  
  5.         char buf [];  
  6. };
复制代码

  • 注意：为满足不同大小的存储需求，还有sdshdr16、sdshdr32、sdshdr64，数字与int的bit长度相同（sdshdr5已弃用）
成员变量描述len记录字符串长度alloc分配给字符数组的空间长度flags用来表示不同类型的SDSbuf[]字节数组，用于保存实际数据例如，一个包含字符串“name”的sds结构如下：
1.png

动态扩容

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力。
SDS API通过alloc-len计算出可用的剩余空间，从而判断缓冲区大小是否支持操作正常进行。
当缓冲区大小不够时，Redis会自动扩大SDS的空间大小
  1. hisds hi_sdsMakeRoomFor(hisds s, size_t addlen)
  2. {
  3.         ...
  4.         // s目前的剩余空间已足够，无需扩展，直接返回
  5.         if (avail >= addlen) return s;
  6.         //获取目前s的长度
  7.         len = hi_sdslen(s);
  8.         sh = (char *)s - hi_sdsHdrSize(oldtype);
  9.         //扩展之后 s 至少需要的长度
  10.         newlen = (len + addlen);
  11.         //根据新长度，为s分配新空间所需要的大小
  12.         if (newlen < HI_SDS_MAX_PREALLOC)
  13.                 //新长度<HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间
  14.                 newlen *= 2;
  15.         else
  16.                 //否则，分配长度为目前长度+1MB
  17.                 newlen += HI_SDS_MAX_PREALLOC;
  18.                 ...
  19.         }
复制代码
  1. typedef struct intset {
  2.         uint32_t encoding;/*编码方式，支持存放16位、32位、64位整数*/
  3.         uint32_t length;/*元素个数 */
  4.         int8_t contents[];/* 整数数组，保存集合数据*/
  5. } intset;
复制代码
总结

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

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

Redis是一个键值型(Key-Value Pair)的数据库，我们可以根据键实现快速的增删改查，而键与值的映射关系正是通过Dict来实现的
结构

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）
  1. /* Note that these encodings are ordered, so:
  2. *INTSET ENC INT16 < INTSET ENC INT32 < INTSET ENC INT64. */
  3. #define INTSET_ENC_INT16(sizeof(int16_t))/* 2字节整数，范围类似iava的short*/
  4. #define INTSET_ENC_INT32(sizeof(int32_t))/*4字节整数，范围类似java的int */
  5. #define INTSET_ENC_INT64(sizeof(int64_t))/* 8字节整，范围类似java的long */
复制代码
  1. intset *intsetAdd(intset *is,int64_t value,uint8_t *success) {
  2.         uint8_t valenc = _intsetValueEncoding(value);// 获取当前值编码
  3.         uint32_t pos;// 要插入的位置
  4.         if(success) *success=1;
  5.         //判断编码是不是超过了当前intset的编码
  6.         if(valenc >intrev32ifbe(is->encoding)) {
  7.                 //超出编码，需要升级
  8.                 return intsetUpgradeAndAdd(is,value);
  9.         } else {
  10.                 // 在当前intset中查找值与value一样的元素的角标pos
  11.                 if(intsetSearch(is,value,&pos)) {
  12.                         if(success) *success =0;//如果找到了，则无需插入，直接结束并返回失败
  13.                         return is;
  14.                 //数组扩容
  15.                 is = intsetResize(is,intrev32ifbe(is->length)+1);
  16.                 //移动数组中pos之后的元素到pos+1，给新元素腾出空间
  17.                 if(pos <intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
  18.         }
  19.         //插入新元素
  20.         intsetSet(is,pos,value);
  21.         //重置元素长度
  22.         is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
  23.         return is;
复制代码

  • *next：哈希冲突时使用，拉链法
  1. static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
  2.         // 获取当前intset编码
  3.     uint8_t curenc = intrev32ifbe(is->encoding);
  4.         // 获取新编码
  5.     uint8_t newenc = _intsetValueEncoding(value);
  6.         // 获取元素个数
  7.     int length = intrev32ifbe(is->length);
  8.         // 判断元素是大于还是小于0，大于0则最大，插入队尾，小于0则最小，插入队首
  9.     int prepend = value < 0 ? 1 : 0;
  10.         // 重置编码为新编码
  11.     is->encoding = intrev32ifbe(newenc);
  12.         // 重置数组大小
  13.     is = intsetResize(is,intrev32ifbe(is->length)+1);
  15.     /* Upgrade back-to-front so we don't overwrite values.
  16.      * Note that the "prepend" variable is used to make sure we have an empty
  17.      * space at either the beginning or the end of the intset. */
  18.     while(length--)
  19.           _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
  21.     /* Set the value at the beginning or the end. */
  22.     if (prepend)
  23.         _intsetSet(is,0,value);
  24.     else
  25.         _intsetSet(is,intrev32ifbe(is->length),value);
  26.     //修改数组长度
  27.     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
  28.     return is;
  29. }
复制代码
2.png

添加元素

当我们向Dict添加键值对时，Redis首先根据key计算出hash值(h)，然后利用h & sizemask（实际上等效于取余，位运算的性能好）来计算元素应该存储到数组中的哪个索引位置。

  • 假设k1的哈希值h=1，则1&3=1，因此k1=v1要存储到数组角标1位置
    3.png

  • 如果发生哈希冲突，采用头插法（便于操作，如果尾插则需遍历到结尾再插入）
    4.png

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低
Dict在每次新增键值对时都会检查负载因子(LoadFactor=used/size)，满足以下两种情况时会触发哈希表扩容:

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

    • 这些后台进程对CPU使用较多，且涉及IO操作，性能开销大

  • 哈希表的 LoadFactor>5

    • 过大了，严重影响了性能，于是需要马上扩容

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


Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactorptr,field)==C_0K) {        deleted-1:        //制除成功后，检查是否需要重置Dict大小，如果需要则调用dictResize重置        /* Always check if the dictionary needs a resize after a delete. */        if(htNeedsResize(o->ptr)) dictResize(o->ptr);}...[/code]
  1. typedef struct dictEntry {
  2.         void *key;// 键
  3.         union {
  4.                 void *val:
  5.                 uint64 t u64;
  6.                 int64_t s64;
  7.                 double d;
  8.         } v;//值
  9.         //下一个Entry的指针
  10.         struct dictEntry *next;
  11. } dictEntry;
复制代码
  1. typedef struct dict {
  2.         dictType *type;//dict类型，内置不同的hash函数
  3.         void *privdata;//私有数据，在做特殊hash运算时用
  4.         dictht ht[2];//一个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用
  5.         long rehashidx; //rehash的进度，-1表示未进行
  6.         int16 t pauserehash:// rehash是否暂停，1则暂停，0则继续
  7. } dict;
复制代码
Dict的rehash

rehash

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

  • 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩:

    • 如果是扩容，则新size为第一个大于等于dict.ht[0].used+1的\(2^n\)
    • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的\(2^n\)(不得小于4)

  • 按照新的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]的内存
下面看一个具体过程

  • 初始状态
    5.png

  • 新增一个元素，现在需要扩容
    6.png

  • 申请空间并分配给ht[1]，同时修改其头部信息，将dict的rehashidx置0
    7.png

  • 将元素映射到ht[1]中
    8.png

  • 然ht[0]指向ht[1]的dictEntry数组，ht[1]置空，修改头部信息及dict的rehashidx字段
    9.png

渐进式

Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。
因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。流程如下:

  • 计算新hash表的size，值取决于当前要做的是扩容还是收缩:

    • 如果是扩容，则新size为第一个大于等于dict.ht[0].used+1的2”
    • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2”(不得小于4)

  • 按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]
  • 设置dict.rehashidx=0，标示开始rehash
  • 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直到dict.ht[0]的所有数据都rehash到dict.ht[1]
  • 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
  • 将rehashidx赋值为-1，代表rehash结束
  • 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空
总结

Dict的结构:

  • 类似java的HashTable，底层是数组加链表来解决哈希冲突
  • Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash
Dict的伸缩:

  • 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
  • 当LoadFactor小于0.1时，Dict收缩
  • 扩容大小为第一个大于等于used+1的\(2^n\)
  • 收缩大小为第一个大于等于used 的\(2^n\)
  • Dict采用渐进式rehash，每次访问Dict时执行一次rehash
  • rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表
ZipList

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

10.png

属性类型长度用途zlbytesuint32_t4字节记录整个压缩列表占用的内存字节数zltailuint32_t4字节记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定尾节点的地址zllenuint16_t2字节记录了压缩列表包含的节点数量。最大值为UINT16_MAX（65534），超过该值会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出entry列表节点不定压缩列表包含的各个节点，节点的长度由节点保存的内容决定zlenduint8_t1字节特殊值0xFF(\(255_{10}\))，用于标记压缩列表的末端ZipListEntry

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


  • previous entry length：前一节点的长度，占1个或5个字节。

    • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
    • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

  • encoding：编码属性，记录content的数据类型(字符串还是整数)以及长度，占用1个、2个或5个字节
  • contents：负责保存节点的数据，可以是字符串或整数
注意：ZipList中所有存储长度的数值均采用小端字节序，即地位字节在前，高位字节在后。
例如：数值0x1234，采用小端字节序实际存储值为：0x3412
Encoding编码

ZipListEntry中的encoding编码分为字符串和整数两种：
字符串

字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串

例如：
一个ZipList保存字符串：“ab”、“bc”
13.png

14.png

整数

整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节
15.png

例如，一个ZipList保存两个整数值：“2”、“5”
16.png

17.png

ZipList的连锁更新问题

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

  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示。

  • 初始状态
    18.png

  • 插入一条长度为254字节的数据
    19.png


    • 新插入的元素导致后继节点的pre_entry_len存储变化，进而导致后继节点的长度变化，并引发了其后继多个节点的连锁反应

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

ZipList特性：

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

问题1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

  • 为了缓解这个问题，我们必须限制ZipList的长度和entry大小。
    问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？
  • 我们可以创建多个ZipList来分片存储数据。
    问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？
  • Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。
    20.png

结构

以下是QuickList的和QuickListNode的结构源码：
  1. static int _dictExpandIfNeeded(dict *d)
  2. {
  3.     //如果正在rehash，则返回ok
  4.     if (dictIsRehashing(d)) return DICT_OK;
  5.     //如果哈希表为空，则初始化哈希表为默认大小:4
  6.     if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
  7.     //当负载因子(used/size)达到1以上，并且当前没有进行bgrewrite等子进程操作
  8.         //或者负载因子超过5，则进行 dictExpand ，也就是扩容
  9.     if (d->ht[0].used >= d->ht[0].size &&
  10.         (dict_can_resize ||
  11.          d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
  12.         dictTypeExpandAllowed(d))
  13.     {
  14.             //扩容大小为used + 1，底层会对扩容大小做判断，实际上找的是第一个大于等于 used+1 的 2^n
  15.         return dictExpand(d, d->ht[0].used + 1);
  16.     }
  17.     return DICT_OK;
  18. }
复制代码
  1. //t_hash.c # hashTypeDeleted()
  2. ...
  3. if(dictDelete((dict*)o->ptr,field)==C_0K) {
  4.         deleted-1:
  5.         //制除成功后，检查是否需要重置Dict大小，如果需要则调用dictResize重置
  6.         /* Always check if the dictionary needs a resize after a delete. */
  7.         if(htNeedsResize(o->ptr)) dictResize(o->ptr);
  8. }
  9. ...
复制代码
21.png

配置

ZipList的entry数量

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。

  • 如果值为正，则代表ZipList的允许的entry个数的最大值
  • 如果值为负，则代表ZipList的最大内存大小，分5种情况：

    • -1：每个ZipList的内存占用不能超过4kb
    • -2：每个ZipList的内存占用不能超过8kb
    • -3：每个ZipList的内存占用不能超过16kb
    • -4：每个ZipList的内存占用不能超过32kb
    • -5：每个ZipList的内存占用不能超过64kb
      其默认值为 -2：
      22.png


除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

  • 0：特殊值，代表不压缩
  • 1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
  • 2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
  • 以此类推
    默认值：
    23.png

总结

QuickList的特点：

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

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

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

24.png

25.png
  1. //server.c 文件
  2. int htNeedsResize(dict *dict){
  3.         long long size, used;
  4.         // 哈希表大小
  5.         size = dictSlots(dict);
  6.         //entry数量
  7.         used = dictsize(dict);
  8.         //size>4(哈希表初识大小)并且 负载因子低于0.1
  9.         return(size>DICT HT INITIAL SIZE &&(used*10@/size < HASHTABLE_MIN_FILL));
  10. }
复制代码
  1. int dictResize(dict *d) {
  2.         unsigned long minimal;
  3.         // 如果正在做bgsave或bgrewriteof或rehash，则返回错误
  4.         if(!dict_can_resize||dictIsRehashing(d))
  5.                 return DICT_ERR;
  6.         //获取used，也就是entry个数
  7.         minimal = d->ht[0].used;
  8.         //如果used小于4，则重置为4
  9.         if(minimal < DICTHT_INITIAL_SIZE)
  10.                 minimal = DICT_HT_INITIAL_SIZE;
  11.         //重置大小为minimal，其实是第一个大于等于minimal的2^n
  12.         return dictExpand(d,minimal);
  13. }
复制代码
总结

SkipList的特点：

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

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

redisObject头部就需要占16字节
注意：如果有大量String对象，每一个对象都有16字节的头部信息，就会造成很大的内存开销，所以存储大量数据时，建议不要用String类型，而用集合类型
Redis的编码方式

Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：
编号编码方式说明0OBJ_ENCODING_RAWraw编码动态字符串1OBJ_ENCODING_INTlong类型的整数的字符串2OBJ_ENCODING_HThash表（字典dict）3OBJ_ENCODING_ZIPMAP已废弃4OBJ_ENCODING_LINKEDLIST双端链表5OBJ_ENCODING_ZIPLIST压缩列表6OBJ_ENCODING_INTSET整数集合7OBJ_ENCODING_SKIPLIST跳表8OBJ_ENCODING_EMBSTRembstr的动态字符串9OBJ_ENCODING_QUICKLIST快速列表10OBJ_ENCODING_STREAMStream流五种数据类型的编码方式

数据类型编码方式OBJ_STRINGint、embstr、rawOBJ_LISTLinkedList和ZipList(3.2以前)、QuickList(3.2以后)OBJ_SETintset、HTOBJ_ZSETZipList、HT、SkipListOBJ_HASHZipList、HT五种数据结构

String

String是Redis中最常见的数据存储类型：

  • 其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。
    27.png

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

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

为什么以44字节为界?

当44字节时，SDS结构如图
30.png

头占3字节、尾占1个字节，内容占44字节
所以SDS共占48字节
加上RedisObject的16字节，整体共占64字节
而Redis的内存分配算法会以\(2^n\)进行分配，64恰好是一个分片大小，不会产生内存碎片
总结


  • 使用字符串时，尽可能保证其大小不超过44字节
  • 能使用整型保存就使用整型保存
List

Redis的List支持从首位对元素进行操作，哪个数据结构比较合适呢

  • LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
  • ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
  • QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高
在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。
在3.2版本之后，Redis统一采用QuickList来实现List：
  1. typedef struct quicklist {
  2.     // 头节点指针
  3.     quicklistNode *head;
  4.     // 尾节点指针
  5.     quicklistNode *tail;
  6.     // 所有ziplist的entry的数量
  7.     unsigned long count;    
  8.     // ziplists总数量
  9.     unsigned long len;
  10.     // ziplist的entry上限，默认值 -2
  11.     int fill : QL_FILL_BITS;    
  12.     // 首尾不压缩的节点数量
  13.     unsigned int compress : QL_COMP_BITS;
  14.     // 内存重分配时的书签数量及数组，一般用不到
  15.     unsigned int bookmark_count: QL_BM_BITS;
  16.     quicklistBookmark bookmarks[];
  17. } quicklist;
复制代码
  1. typedef struct quicklistNode {
  2.     // 前一个节点指针
  3.     struct quicklistNode *prev;
  4.     // 下一个节点指针
  5.     struct quicklistNode *next;
  6.     // 当前节点的ZipList指针
  7.     unsigned char *zl;
  8.     // 当前节点的ZipList的字节大小
  9.     unsigned int sz;
  10.     // 当前节点的ZipList的entry个数
  11.     unsigned int count : 16;  
  12.     // 编码方式：1，ZipList; 2，lzf压缩模式
  13.     unsigned int encoding : 2;
  14.     // 数据容器类型（预留）：1，其它；2，ZipList
  15.     unsigned int container : 2;
  16.     // 是否被解压缩。1：则说明被解压了，将来要重新压缩
  17.     unsigned int recompress : 1;
  18.     unsigned int attempted_compress : 1; //测试用
  19.     unsigned int extra : 10; /*预留字段*/
  20. } quicklistNode;
复制代码
内存结构

31.png

Set

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

  • 不保证有序性
  • 保证元素唯一（可以判断元素是否存在）
  • 求交集、并集、差集
可以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？

  • HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）
Set是Redis中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。

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

    • 二分查找保证了查询以及判断是否存在的效率

创建
  1. // t_zset.c
  2. typedef struct zskiplist {
  3.     // 头尾节点指针
  4.     struct zskiplistNode *header, *tail;
  5.     // 节点数量
  6.     unsigned long length;
  7.     // 最大的索引层级，默认是1
  8.     int level;
  9. } zskiplist;
复制代码
  1. // t_zset.c
  2. typedef struct zskiplistNode {
  3.     sds ele; // 节点存储的值
  4.     double score;// 节点分数，排序、查找用
  5.     struct zskiplistNode *backward; // 前一个节点指针
  6.     struct zskiplistLevel {
  7.         struct zskiplistNode *forward; // 下一个节点指针
  8.         unsigned long span; // 索引跨度
  9.     } level[]; // 多级索引数组
  10. } zskiplistNode;
复制代码
  1. void pushGenericCommand(client *c, int where, int xx) {
  2.     int j;
  3.     // 尝试找到KEY对应的list
  4.     robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
  5.     // 检查类型是否正确
  6.     if (checkType(c,lobj,OBJ_LIST)) return;
  7.     // 检查是否为空
  8.     if (!lobj) {
  9.         if (xx) {
  10.             addReply(c, shared.czero);
  11.             return;
  12.         }
  13.         // 为空，则创建新的QuickList
  14.         lobj = createQuicklistObject();
  15.         quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
  16.                             server.list_compress_depth);
  17.         dbAdd(c->db,c->argv[1],lobj);
  18.     }
  19.     // 略 ...
  20. }
复制代码
类型转换
  1. robj *createQuicklistObject(void) {
  2.     // 申请内存并初始化QuickList
  3.     quicklist *l = quicklistCreate();
  4.     // 创建RedisObject，type为OBJ_LIST
  5.     // ptr指向 QuickList
  6.     robj *o = createObject(OBJ_LIST,l);
  7.     // 设置编码为 QuickList
  8.     o->encoding = OBJ_ENCODING_QUICKLIST;
  9.     return o;
  10. }
复制代码
内存图

32.png

由图可以直观看出，内存占用太高

  • 数据重复存储、存在大量指针……
另一种实现

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

  • 元素数量小于zset_max_ziplist_entries，默认值128
  • 每个元素都小于zset_max_ziplist_value字节，默认值64
  1. robj *setTypeCreate(sds value) {
  2.     // 判断value是否是数值类型 long long
  3.     if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
  4.         // 如果是数值类型，则采用IntSet编码
  5.         return createIntsetObject();
  6.     // 否则采用默认编码，也就是HT
  7.     return createSetObject();
  8. }
复制代码
  1. robj *createIntsetObject(void) {
  2.     // 初始化INTSET并申请内存空间
  3.     intset *is = intsetNew();
  4.     // 创建RedisObject
  5.     robj *o = createObject(OBJ_SET,is);
  6.     // 指定编码为INTSET
  7.     o->encoding = OBJ_ENCODING_INTSET;
  8.     return o;
  9. }
复制代码
  1. robj *createSetObject(void) {
  2.     // 初始化Dict类型，并申请内存
  3.     dict *d = dictCreate(&setDictType,NULL);
  4.     // 创建RedisObject
  5.     robj *o = createObject(OBJ_SET,d);
  6.     // 设置encoding为HT
  7.     o->encoding = OBJ_ENCODING_HT;
  8.     return o;
  9. }
复制代码
编码转换
  1. int setTypeAdd(robj *subject, sds value) {
  2.     long long llval;
  3.     if (subject->encoding == OBJ_ENCODING_HT) {
  4.         dict *ht = subject->ptr;
  5.         dictEntry *de = dictAddRaw(ht,value,NULL);
  6.         if (de) {
  7.             dictSetKey(ht,de,sdsdup(value));
  8.             dictSetVal(ht,de,NULL);
  9.             return 1;
  10.         }
  11.     } else if (subject->encoding == OBJ_ENCODING_INTSET) {
  12.         if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
  13.             uint8_t success = 0;
  14.             subject->ptr = intsetAdd(subject->ptr,llval,&success);
  15.             if (success) {
  16.                 /* Convert to regular set when the intset contains
  17.                  * too many entries. */
  18.                 size_t max_entries = server.set_max_intset_entries;
  19.                 /* limit to 1G entries due to intset internals. */
  20.                 if (max_entries >= 1<<30) max_entries = 1<<30;
  21.                 if (intsetLen(subject->ptr) > max_entries)
  22.                     setTypeConvert(subject,OBJ_ENCODING_HT);
  23.                 return 1;
  24.             }
  25.         } else {
  26.             /* Failed to get integer from object, convert to regular set. */
  27.             setTypeConvert(subject,OBJ_ENCODING_HT);
  29.             /* The set *was* an intset and this value is not integer
  30.              * encodable, so dictAdd should always work. */
  31.             serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
  32.             return 1;
  33.         }
  34.     } else {
  35.         serverPanic("Unknown set encoding");
  36.     }
  37.     return 0;
  38. }
复制代码
注意到转换条件：

  • 压缩列表中的元素数量加 1 后超过了配置项 zset_max_ziplist_entries 的值时
  • 当要插入的元素（ele）的长度超过了配置项 zset_max_ziplist_value 的值时
  • ziplistSafeToAdd 函数用于检查是否有足够的内存空间来将新元素添加到压缩列表中。若该函数返回 false，也就是没有足够的内存空间，就会触发转换。（ZipList需要的是连续的内存空间）
ZipList如何满足Zset需求

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

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

Hash

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

  • 都是键值存储
  • 都需求根据键获取值
  • 键必须唯一
    区别如下：
  • zset的键是member，值是score；hash的键和值都是任意值
  • zset要根据score排序；hash则无需排序
结构

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

  • Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value
  • 当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：

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

ZipList形式内存图：
34.png

Dict形式内存图：
35.png

源码

当你执行一条hset命令时……
  1. // zset结构
  2. typedef struct zset {
  3.     // Dict指针
  4.     dict *dict;
  5.     // SkipList指针
  6.     zskiplist *zsl;
  7. } zset;
复制代码
判断是需要写入还是需要创建hash
  1. robj *createZsetObject(void) {
  2.     zset *zs = zmalloc(sizeof(*zs));
  3.     robj *o;
  4.     // 创建Dict
  5.     zs->dict = dictCreate(&zsetDictType,NULL);
  6.     // 创建SkipList
  7.     zs->zsl = zslCreate();
  8.     o = createObject(OBJ_ZSET,zs);
  9.     o->encoding = OBJ_ENCODING_SKIPLIST;
  10.     return o;
  11. }
复制代码
创建hash
  1. // zadd添加元素时，先根据key找到zset，不存在则创建新的zset
  2. zobj = lookupKeyWrite(c->db,key);
  3. if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
  4. // 判断是否存在
  5. if (zobj == NULL) { // zset不存在
  6.     if (server.zset_max_ziplist_entries == 0 ||
  7.         server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
  8.     { // zset_max_ziplist_entries设置为0就是禁用了ZipList，
  9.         // 或者value大小超过了zset_max_ziplist_value，采用HT + SkipList
  10.         zobj = createZsetObject();
  11.     } else { // 否则，采用 ZipList
  12.         zobj = createZsetZiplistObject();
  13.     }
  14.     dbAdd(c->db,key,zobj);
  15. }
  16. // ....
  17. zsetAdd(zobj, score, ele, flags, &retflags, &newscore);
复制代码
判断hash是否需要进行编码转换
hashTypeTryConversion(o,c->argv,2,c->argc-1);

  • 以hset user1 name Jack age 21为例，下标为2的参数开始才是存的数据，需要被判断
  1. robj *createZsetObject(void) {
  2.     // 申请内存
  3.     zset *zs = zmalloc(sizeof(*zs));
  4.     robj *o;
  5.     // 创建Dict
  6.     zs->dict = dictCreate(&zsetDictType,NULL);
  7.     // 创建SkipList
  8.     zs->zsl = zslCreate();
  9.     o = createObject(OBJ_ZSET,zs);
  10.     o->encoding = OBJ_ENCODING_SKIPLIST;
  11.     return o;
  12. }
复制代码
执行set过程
  1. robj *createZsetZiplistObject(void) {
  2.     // 创建ZipList
  3.     unsigned char *zl = ziplistNew();
  4.     robj *o = createObject(OBJ_ZSET,zl);
  5.     o->encoding = OBJ_ENCODING_ZIPLIST;
  6.     return o;
  7. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
蚬蕞遂
2025-6-11 18:41:35

0

粉丝关注

16

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫