前言：动态字符串SDS，字典，set，ziplist，quicklist，skiplist

redis kv 存储分析

一、动态字符串-SDS

概览

«左移

开始之前，我们先准备点东西：位运算

i«n 总结为 i*2^n

所以

１<<5 = 2^5
１<<8 = 2^8
１<<16 = 2^16
１<<32 = 2^32
１<<64 = 2^64

SDS５种数据类型

Ｒｅｄｉｓ 3.2 以后ＳＤＳ数据类型有５个

#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

结合上面的位运算，我们也能理解这５个数据类型的命名规则。

外部类型String 找　SDS结构

我们现在有定义了５种ＳＤＳ数据类型，那么如何根据字符串长度找这些类型呢？

或者说输入的字符串长度和类型有什么关系？下面我们来看一看他们之间的关系。

再来看看源码：

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

根据位运算左移公式，我可以得知　1«8　= 2^8 = 256

那么这里的　２５６是指什么？这里的２５６就是字节

也就是说：

SDS_TYPE_5　-- 32 Byte
SDS_TYPE_8　-- 256 Byte
SDS_TYPE_16 -- 64KＢ
SDS_TYPE_32 -- ...
SDS_TYPE_64 -- ...

现在数据类型找到了，我们再来看看比较典型的几种操作。

追加字符串

从使用角度讲，追加一般用的频率很少。所以有多大分配多大。

所以这里追加的话，有两种大情况：还有剩余　或　不够用

主要讲一下不够用就要重新申请内存，那么我们如何去申请内存呢？

这里提供了两种分配策略：

1. <1M ，新空间 = ２倍扩容；
2. >1M , 新空间 = 累加1M

空间有了，那么我们需要根据最新的空间长度占用，再找到对应的新的ＳＤＳ数据类型。

看一下源码，增加一下印象：

/* 追加字符串*/
sds sdscatlen(sds s, const void *t, size_t len) {
    // 当前字符串长度
    size_t curlen = sdslen(s);
    // 按需调整空间（原来字符串，要追加的长度）
    s = sdsMakeRoomFor(s,len);
    // 内存不足
    if (s == NULL) return NULL;
    // 追加目标字符串到字节数组中
    memcpy(s+curlen, t, len);
    // 设置追加后的长度
    sdssetlen(s, curlen+len);
    // 追加结束符
    s[curlen+len] = '\0';
    return s;
}
/*空间调整，注意只是调整空间，后续自己组装字符串*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 当前剩下的空间
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    /* 空间足够 */
    if (avail >= addlen) return s;
    // 长度
    len = sdslen(s);
    // 真正的数据体
    sh = (char*)s-sdsHdrSize(oldtype);
    // 新长度
    newlen = (len+addlen);
    // < 1M 2倍扩容
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    // > 1M 扩容1M
    else
        newlen += SDS_MAX_PREALLOC;
    // 获取sds 结构类型
    type = sdsReqType(newlen);
    // type5 默认转成 type8
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    // 头长度
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) { // 长度够用 并且 数据结构不变
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 重新申请内存
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

SDS 和内部类型

外部字符串类型，找到了SDS结构，现在到了SDS转内部结构

对于字符串类型为什么会分　embstr 和　raw呢？

我们先说一下内存分配器：jemalloc、tcmalloc

这来能为仁兄呢分配内存的大小都是　２／４／８／１６／３２／６４　字节

对于redis 来讲如何利用并适配好内存分配器依然需要好好计算一下。

Redis 给我们实现了很多内部数据结构，这些内部数据结构得有自己的字描述文件－内部结构头对象

不同对象有不同的type,同一个对象有不同的存储形式，还有lru缓存淘汰机制信息，引用计数器，指向数据体的指针。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;　　　　　　
    void *ptr;
} robj;

所以ＳＤＳ和　内部类型的关系类似于这样的：

连续内存，和非连续内存

44 字节

ＳＤＳ为什么会是这样的两种内部结构呢？回忆一下上面提到的：ＳＤＳ结构，最小的应该是　SDS_TYPE_8（SDS_TYPE_５默认转成８）

struc SDS{
    int8 capacity;  // 1字节
    int8 len;       // 1字节
    int8 flags;     // 1字节
    byte[] content; // 内容
}

所以从上代码看出，一个最小的ＳＤＳ，至少占用３字节.

还有内部结构头：RedisObject
typedef struct redisObject {
    unsigned type:4;        // 4bit
    unsigned encoding:4;    // 4bit
    unsigned lru:LRU_BITS;  // 24bit
    int refcount;　　　　　　 // ４字节
    void *ptr;              // 8字节
} robj;

16字节　＝　32bit(4字节) + ４字节　+ 8字节

所以一个内部类型头指针大小为：16字节

再加上最小sds的３字节，一共　19字节。也就是说一个最小的字符串所占用的内存空间是19字节

还记得上面我们提到过的内存分配器么？（２／４／８／１６／３２／６４　字节）

对，如果要给这个最小19字节分配内存，至少要分配一个32字节的内存。当然如果字符串长一点，再往下就可以分配到64字节的内存。

以上这种形式被叫做：embstr，这种形式使得 RedisObject和SDS 内存地址是连续的。

那么一旦大于64字节，形式就变成了raw，这种形式使得内存不连续，因为SDS已经变大，取得大的连续内存得不偿失。

再回来讨论一下 embstr, 最大64字节内存分配下来，我们实际可以真正存储字符串的长度是多少呢？–44字节

64字节，减去RedisObject头信息19字节，再减去３字节SDS头信息，剩下45字节，再去除\0结尾。这样最后可以存储44字节。

所以　embstr　形式，可以存储最大字符串长度是44字节。

关于字符串最大是５１２Ｍ

Strings
Strings are the most basic kind of Redis value. Redis Strings are binary safe, 
this means that a Redis string can contain any kind of data, 
for instance a JPEG image or a serialized Ruby object.
A String value can be at max 512 Megabytes in length.

出个题（redis 5.0.5版本）

SET q sc

encoding:embstr，长度为３

现在做追加操作，APPEND q scadd ，encoding:raw，长度８

1. 为什么从 sc ----> scscadd 简单的追加操作内部类型会从　embstr　-----> raw ，如何解释？

二、字典-dict

1、字典使用范围

dict为redis中使用最频繁的数据结构，使用范围有：

• hash结构的数据
• 整个redis中所有的key-value为一个全局字典
• 所有带过期时间的key为一个字典
• zset集合中value和score的映射关系也是通过dict实现

部分源码如下：

struct RedisDb {
    dict* dict;         // all keys key=>value
    dict* expires;      // all expired keys key=>long(timestamp)
    ...
}

struct zset {
    dict *dict;         // all values value=>score
    zskiplist *zsl;
}

2、字典dict内部结构

dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的hashtable 取而代之。

hashtable结构和java中的HashMap几乎一样，使用分桶方式解决冲突：第一维是数组，二维为链表，数组中存储的是二维链表中的第一个元素

// hash整体结构
struct dictht {
    dictEntry** table;  // 二维
    long size;          // 第一维数组的长度
    long used;          // hash 表中的元素个数
    ...
}

// 单个元素
struct dictEntry {
    void* key;
    void* val;
    dictEntry* next;     // 链接下一个 entry
}

3、渐进式rehash

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
    // 这里进行小步搬迁
    if (dictIsRehashing(d)) _dictRehashStep(d);
    /* Get the index of the new element, or -1 if
    * the element already exists. */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;
    /* Allocate the memory and store the new entry.
    * Insert the element in top, with the assumption that in a database
    * system it is more likely that recently added entries are accessed
    * more frequently. */
    // 如果字典处于搬迁过程中，要将新的元素挂接到新的数组下面
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

有两种方式可以触发rehash：

• 当前字典的后续指令，如hset等
• 定时任务

4、查找和Hash

查找元素源码：

func get(key) {
    let index = hash_func(key) % size;
    let entry = table[index];
    while(entry != NULL) {
        if entry.key == target {
            return entry.value;
        }
        entry = entry.next;
   }
}

hash_func为hash函数，redis使用的是siphash算法,保证key即使很小也能产生较好的随机性

5、扩容和缩容

扩容条件：

• 正常扩容： hash 表中元素的个数等于第一维数组的长度，开始扩容。扩容的新数组是原数组大小的 2 倍
• 避免扩容：如果 Redis 正在做 bgsave，为了减少内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容
• 强制扩容：hash过于拥挤的情况，元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio)

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;
    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
    * table (global setting) or we should avoid it but the ratio between
    * elements/buckets is over the "safe" threshold, we resize doubling
    * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
        {
        return dictExpand(d, d->ht[0].used*2);
        }
    return DICT_OK;
}       

缩容条件：

• hash表过于稀疏：缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave

扩容时考虑 BGSAVE 是因为，扩容需要申请额外的很多内存，且会重新链接链表（如果会冲突的话）, 这样会造成很多内存碎片，也会占用更多的内存，造成系统的压力。

而缩容过程中，由于申请的内存比较小，同时会释放掉一些已经使用的内存，不会增大系统的压力。因此不用考虑是否在进行 BGSAVE 操作。

三、小而轻的set-intset

1、 什么是intset？

set的底层实现，随着元素类型是否是整型以及添加的元素的数目多少，而有所变化。概括来讲，当set中添加的元素都是整型且元素数目较少时，set使用intset作为底层数据结构，否则，set使用dict作为底层数据结构，那如何定义”较少”这个概念呢？

通过如下配置，当元素个数超过set-max-intset-entries中定义的值时，intset转化为dict进行存储

set-max-intset-entries 512

2、intset源码

简单来讲：intset通过维护一个数组来模拟set的相关操作，通过二分法来获取对应元素

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

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

各个字段含义如下：

• encoding: 数据编码，表示intset中的每个数据元素用几个字节来存储。它有三种可能的取值：INTSET_ENC_INT16表示每个元素用2个字节存储，INTSET_ENC_INT32表示每个元素用4个字节存储，INTSET_ENC_INT64表示每个元素用8个字节存储。因此，intset中存储的整数最多只能占用64bit。
• length: 表示intset中的元素个数。encoding和length两个字段构成了intset的头部（header）。
• contents: 是一个柔性数组（flexible array member），表示intset的header后面紧跟着数据元素。这个数组的总长度（即总字节数）等于encoding * length。柔性数组在Redis的很多数据结构的定义中都出现过（例如sds,quicklist, skiplist），用于表达一个偏移量。contents需要单独为其分配空间，这部分内存不包含在intset结构当中。

其中需要注意的是，intset可能会随着数据的添加而改变它的数据编码：

• 最开始，新创建的intset使用占内存最小的INTSET_ENC_INT16（值为2）作为数据编码。
• 每添加一个新元素，则根据元素大小决定是否对数据编码进行升级。

3、intset转化为dict

• 添加了一个数字，但它无法用64bit的有符号数来表达。intset能够表达的最大的整数范围为-264~264-1，因此，如果添加的数字超出了这个范围，这也会导致intset转成dict。
• 添加的集合元素个数超过了set-max-intset-entries配置的值的时候，也会导致intset转成dict（具体的触发条件参见t_set.c中的setTypeAdd相关代码）。

四、压缩列表-ziplist

为节省内存开销，zset和hash在元素较少时，使用压缩列表ziplist进行存储。

可以通过debug object key_name 命令，通过结果中的encoding字段判断数据存储类型。

1、ziplist底层结构

struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个
    节点
    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

entry随容纳元素的不同，会呈现不同的结构：

struct entry {
    int<var> prevlen; // 前一个 entry 的字节长度
    int<var> encoding; // 元素类型编码
    optional byte[] content; // 元素内容
}

2、编码转换

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

• 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；
• 哈希对象保存的键值对数量小于 512 个；

不能满足这两个条件的哈希对象需要使用 hashtable 编码

对应redis配置文件中的配置:

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

Redis的hash之所以这样设计，是因为当ziplist变得很大的时候，它有如下几个缺点：

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

总之，ziplist本来就设计为各个数据项挨在一起组成连续的内存空间，这种结构并不擅长做修改操作。一旦数据发生改动，就会引发内存realloc，可能导致内存拷贝。

五、快速列表-quicklist

1、发展

redis早起list使用压缩列表ziplist和普通双向链表linklist。后期因linklist会因元素过多加剧内存碎片化影响内存管理效率，对其进行了优化，形成如今的quicklist

2、底层结构

简单来讲quicklist底层结构为：双向链表+ziplist

这又是一个需要找平衡点的难题。我们只从存储效率上分析一下：

• 每个quicklist节点上的ziplist越短，则内存碎片越多。内存碎片多了，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项，这就蜕化成一个普通的双向链表了。
• 每个quicklist节点上的ziplist越长，则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间（它们加起来很多），但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点，所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了。

redis默认，每个ziplist大小为8kb

3、配置文件相关

list-max-ziplist-size -2
list-compress-depth 0

（1）list-max-ziplist-size -2

当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。

当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，每个值含义如下：

• -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes）
• -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
• -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
• -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）
• -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

当列表很长的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（访问起来性能也很低）。如果应用场景符合这个特点，那么list还提供了一个选项，能够把中间的数据节点进行压缩，从而进一步节省内存空间

（2）list-compress-depth 0

这个参数表示一个quicklist两端不被压缩的节点个数。注：这里的节点个数是指quicklist双向链表的节点个数，而不是指ziplist里面的数据项个数。实际上，一个quicklist节点上的ziplist，如果被压缩，就是整体被压缩的。

参数list-compress-depth的取值含义如下：

• 0: 是个特殊值，表示都不压缩。这是Redis的默认值。
• 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
• 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
• 3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。
• 依此类推…

由于0是个特殊值，很容易看出quicklist的头节点和尾节点总是不被压缩的，以便于在表的两端进行快速存取。

Redis对于quicklist内部节点的压缩算法，采用的LZF (http://oldhome.schmorp.de/marc/liblzf.html)——一种无损压缩算法。

拓展阅读：《ziplist、linkedlist 和 quicklist 的性能对比》

六、跳跃列表-skiplist

跳跃列表主要在redis的zset中使用。

这一切要源于zset功能的特殊性：

• zset既需要一个hash存储value和score的对应关系
• 另一方面需要提供按照 score 来排序的功能
• 还需要能够指定 score 的范围来获取 value 列表的功能。

待研究：

Redis为什么用跳表而不用平衡树？

参考资料

• Redis开发与运维：SDS与embstr、raw 深入理解
• Redis内部数据结构详解(5)——quicklist
• Redis内部数据结构详解(4)——ziplist
• Redis设计与实现3 哈希对象（ ziplist /hashtable）