简单动态字符串SDS

Redis中保存的key是字符串，value往往是字符串或者字符串的集合。可以说字符串是Redis中最常见的数据结构。

不过Redis中没有直接使用C语言中的字符串，而是构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String）。

比如我们执行命令set name Jack，那么Redis将在底层创建两个SDS，其中一个是包含name的SDS，另一个是包含Jack的SDS。

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

struct __attribute__((packed)) sdshdr8 {
    uint8_t len;	// buf已保存的字符串字节数，不包含结束标示\0
    uint8_t alloc;	// buf申请的总字节数，不包含结束标示\0
    unsigned char flags;	// 不同的SDS的头类型，用来控制SDS头大小
    char buf[];
};

flag对应的种类有五五种

#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如有一个内容为abc的SDS，其中len=2,alloc=2,flag=1,h,i,\0，我们要给他追加一段字符串defgh，首先会申请新的内存空间：

  • 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1
  • 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1

动态字符串优点：

  1. 获取字符串长度的时间复杂度为0(1)[因为长度已经存在于结构体中]
  2. 支持动态扩容
  3. 减少内存分配次数
  4. 二进制安全（可以存储特殊字符，无需考虑结束符的问题）

IntSet

Redis为了优化内存和性能，会根据Set中元素的特性自动选择底层实现：

  1. 所有元素都是整数
  2. 元素数量不超过配置的阈值
  • Redis配置项set-max-intset-entries定义了IntSet的最大元素数量，默认值为512
  • 如果元素数量超过该阈值，Redis 会将IntSet转换为HashTable

IntSet基于整数数组来实现，具备长度可变，有序（便于查找）等特性。

typedef struct intset {
    uint32_t encoding; // 编码方式（int16_t、int32_t、int64_t）
    uint32_t length;   // 集合中元素的数量
    int8_t contents[];  // 存储整数的数组
} intset;

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

#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 */

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，内部结构类似于encoding:INTSET_ENC_INT16,length:3,5,10,15。

寻址公式：startPtr【开始的起始地址为0】+（sizeof(int16) 【数据类型的字节大小】* index【它对应的下标】）就可以快速找到对应的数据

IntSet升级

现在，假设有一个intset,元素为{5,10,20}，采用的编码为INTSET_ENC_INT16，则每个整数占2字节。如果现在我想添加50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。

以当前案例来说流程如下：

  1. 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
  2. 倒序依次将数组中的元素拷贝到扩容后的正确位置（倒叙放是为了防止字节扩大时将后面的数据给覆盖掉）
  3. 将待添加的元素放入数组末尾
  4. 将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

如果插入的元素位于IntSet中间或者开头，底层会使用二分查找确定插入位置，然后再执行移动和插入操作。

小结

  • IntSet可以看做是特殊的整数数组
  • IntSet中的元素唯一、有序
  • 具备类型升级机制，可以节省内存空间
  • 底层采用二分查找方式来查询

Dict

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

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

哈希表

每个哈希表由数个entry组成，每个桶是一个链表，用于解决哈希冲突

typedef struct dictht {
    dictEntry **table;      // entry数组
    unsigned long size;     // 哈希表的大小
    unsigned long sizemask; // 用于计算索引的掩码（size - 1）
    unsigned long used;     // 已使用的entry数量
} dictht;

哈希节点

每个键值对存储在一个 dictEntry 结构中

typedef struct dictEntry {
    void *key;              // 键
    union {
        void *val;          // 值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下一个节点（解决哈希冲突）
} dictEntry;

字典结构

Dict 包含两个哈希表（ht[0]和ht[1]），以及Rehash相关的状态信息

typedef struct dict {
    dictType *type;         // dict类型，内置不同的hash函数
    void *privdata;         // 私有数据
    dictht ht;          // 两个哈希表，一个是当前数据，另一个一般是空，rehash时使用
    long rehashidx;         // Rehash 的进度（-1 表示未进行 Rehash）
    int16_t pauserehash;	// rehash是否暂停，1表示暂停，0则继续
} dict;

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

Dict的扩容和收缩

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

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

  • 哈希表的LoadFactor >= 1，并且服务器没有执行BGSAVE或者BGREWRITEAOF等后台进程（因为这种操作对性能要求高，如果我再进行rehash的操作就可能导致阻塞）
  • 哈希表的LoadFactor > 5
/* 检查是否需要扩容 */
static int _dictExpandIfNeeded(dict *d) {
    // 如果正在进行 Rehash，则不需要扩容
    if (dictIsRehashing(d)) return DICT_OK;
    // 如果哈希表为空，则初始化为默认大小（4）
    if (d->ht.size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // 如果负载因子超过1并且没有进行bgrewrite等子进程操作，则触发扩容
    if (d->ht.used >= d->ht.size &&
        (dict_can_resize || d->ht.used/d->ht.size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

当哈希表的负载因子低于0.1，并且size > 4时，Redis会触发收缩操作

/* 检查是否需要收缩 */
int dictResize(dict *d) {
    unsigned int minimal;

    // 如果正在进行 Rehash 或 dict_can_resize 为 0，则不能收缩
    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;

    // 调用 dictExpand 进行收缩，值为第一个大于等于minimal的2^n
    return dictExpand(d, minimal);
}

Dict的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.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最终为空

ZipList

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

结构

Ziplist由三部分组成：

  1. 头部
  • zlbytes：Ziplist的总字节数（4字节）
  • zltail：最后一个节点的偏移量（4字节），便于定位到最后一个entry节点
  • zllen：entry节点的数量（2字节）
  1. entry节点(长度不固定)
  • 每个entry节点包含以下字段：
    • previous_entry_len：前一个节点的长度（1或5字节）
      • 如果前一节点的长度小于254字节，则采用1个字节来保存
      • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
    • encoding：当前节点的编码方式（1、2或5字节）
    • content：实际存储的数据（字符串或整数）
  1. 尾部
  • zlend：Ziplist的结束标志（1字节，固定值0xff）

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

Encodeing编码

ZipListEntry中的encoding编码分为字符串和整数两种：
字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串

编码 编码长度 字符串大小
|00pppppp| 1 bytes <= 63 bytes
|01pppppp|qqqqqqqq| 2 bytes <= 16383 bytes
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 5 bytes <= 4294967295 bytes

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

编码 编码长度 整数类型
11000000 1 int16_t（2 bytes）
11010000 1 int32_t（4 bytes）
11100000 1 int64_t（8 bytes）
11110000 1 24位有符整数(3 bytes)
11111110 1 8位有符整数(1 bytes)
1111xxxx 1 直接在xxxx位置保存数值，范围从0001~1101，减1后结果为实际值

连锁更新问题

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

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

当插入或删除节点时，可能导致后续节点的prevlen字段发生变化。如果prevlen的长度从1字节变为5字节，则需要扩展当前节点的空间，这可能导致后续节点的prevlen字段也需要更新，从而引发连锁更新

不过发生的可能性较低，redis并没有解决这个问题

QuickList

Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，链表中的每个节点都是一个ZipList。可以用多个ZipList来分片存储数据

QuickList

为了避免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

QuickList源码：

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;

QuickListNode源码：

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;

ZipList的压缩可以选择头尾几个链表不压缩，一般crud都在头尾，只压缩中间的ZipList

quicklist_ziplist

SkipList

SkipList是链表，但是与传统链表有些差异，具有以下特点：

  • 节点按照score值排序，score值一样则按照ele字典排序
  • 节点可能包含多个指针，指针跨度不同
  • 查找、插入和删除操作的平均时间复杂度为O(logn)
  • SkipList的索引层级是动态调整的，插入新元素时会随机生成其层级
  • 跳跃表是一个双向链表，每一个节点都包含score和ele值

SkipList的源码：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;	// 头尾节点指针
    unsigned long length;	// 节点数量
    int level;	// 最大的索引层级，默认是1
} zskiplist;

SkipListNode的源码：

typedef struct zskiplistNode {
    sds ele;                      // 元素值
    double score;                   // 分值，排序、查找用
    struct zskiplistNode *backward; // 前一个节点指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 下一个节点指针
        unsigned long span;             // 索引跨度
    } level[];                        // 多级索引数组
} zskiplistNode;

skiplist

RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，它是Redis数据存储的基础，通过封装数据的类型、编码方式和实际值，提供了统一的接口来操作各种数据类型。源码如下：

typedef struct redisObject {
    unsigned type: 4;	// 5种数据结构类型，占4bit
    unsigned encoding: 4;	// 底层编码方式，共11种，占4bit
    unsigned lru： LRU_BITS;	// lru表示该对象最后一次被访问的时间，占24bit,便于判断空闲时间太久的key
    int refcount;	// 对象引用计数器，计数器为0则说明对象无人引用，可以被回收
    void *ptr;	// 指针，指向存放实际数据的空间
} robj;

Redis的编码方式

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

编号 编码方式 说明
0 OBJ_ENCODING_RAW raw编码动态字符串
1 OBJ_ENCODING_INT long类型的整数的字符串
2 OBJ_ENCODING_HT hash表（字典dict）
3 OBJ_ENCODING_ZIPMAP 已废弃
4 OBJ_ENCODING_LINKEDLIST 双端链表
5 OBJ_ENCODING_ZIPLIST 压缩列表
6 OBJ_ENCODING_INTSET 整数集合
7 OBJ_ENCODING_SKIPLIST 跳表
8 OBJ_ENCODING_EMBSTR embstr的动态字符串
9 OBJ_ENCODING_QUICKLIST 快速列表
10 OBJ_ENCODING_STREAM Stream流

五种数据结构对应的编码

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是Redis中最常见的数据存储类型

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

底层实现

OBJ_ENCODING_RAW的实现就是RedisObject中的ptr指向一个SDS

raw

EMBSTR的形式为RedisObject后直接跟SDS，而不是两个分开的地址空间

embstr

INT形式删除了SDS，直接把数据保存在ptr位置

INT

List

Redis的List类型可以从首、尾操作列表中的元素，哪一个数据结构能满足上述特征？

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

在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量<512并且元素大小<64字节时使用ZipList编码，超过则采用LinkedList编码

在3.2版本之后，Redis统一采用QuickList来实现List

创建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);
    }
    // ...
}

创建Quicklist：

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

redis_List

Set

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

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

可以看出，Set对查询元素的效率要求非常高，所以底层使用了IntSet和Dict实现。

为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。

当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries(默认512)时，Set会采用IntSet编码，以节省内存

创建Set的源码：

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
    0->encoding = OBJ_ENCODING_INTSET;
    return o;
}

默认编码HT：

robj *createSetObject(void) {
    // 初始化Dict类型，并申请内存
    dict *d = dictCreate(&setDictType, NULL);
    // 创建RedisObject
    robj *o= createObject(OBJ_SET, d);
    // 设置encoding为HT
    0->encoding = OBJ_ENCODING_HT;
    return o;
}

如果原本set中存储的元素使5,10,20，然后执行命令sadd s1 m1，因为新插入的元素是字符串，redis需要转换编码，会新建一个Dict，把原本IntSet中的元素和m1都存入Dict中，然后转换RedisObject中的ptr，指向Dict，最后更改encoding为OBJ_ENCODING_HT

redis_set

ZSet

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

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

因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。

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

zset会同时使用两个结构，需要查找，维护键唯一时使用HT，需要排序时使用SkipList

// 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;
}

zset

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

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

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

  • ZipList是连续内存，因此score和element是紧挨在一起的两个entry，element在前，score在后(当我们查询的时候就可以直接遍历即可，当我们要找m1的score，只需要找到m1在找下一个即可)
  • score越小越接近队首，score越大越接近队尾，按照score值升序排列

Hash

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

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

区别：

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

Hash的底层实现也与zset类似，只不过不需要用于排序的SkipList。

Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存key和value，随着数据的增加，底层的ziplist就可能会转成dict，具体配置如下：

  • hash-max-ziplist-entries > 512
  • hash-max-ziplist-value > 64

当满足上面两个条件其中之一的时候，Redis就使用dict字典来实现hash。Redis的hash之所以这样设计，是因为当ziplist变得很大的时候，它有如下几个缺点：

  • 每次插入或修改引发的realloc操作会有更大的概率造成内存拷贝，从而降低性能
  • 一旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更大的一块数据
  • 当ziplist数据项过多的时候，在它上面查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历

redis_hash