redis 底层数据结构分析整理

2021/03/01 redis
如果文章图片无法显示,可尝试配置host:修复Github图片资源无法显示问题

前言:动态字符串SDS,字典,set,ziplist,quicklist,skiplist

redis kv 存储分析

image-20210308162540098

image-20210308162553044

image-20210308162600915

image-20210308162626632

一、动态字符串-SDS

概览

image

«左移

开始之前,我们先准备点东西:位运算

i«n 总结为 i*2^n

所以

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

SDS5种数据类型

Redis 3.2 以后SDS数据类型有5个

#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

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

外部类型String 找 SDS结构

我们现在有定义了5种SDS数据类型,那么如何根据字符串长度找这些类型呢?

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

image

再来看看源码:

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

那么这里的 256是指什么?这里的256就是字节

image

image

也就是说:

SDS_TYPE_5 -- 32 Byte
SDS_TYPE_8 -- 256 Byte
SDS_TYPE_16 -- 64KB
SDS_TYPE_32 -- ...
SDS_TYPE_64 -- ...

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

追加字符串

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

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

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

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

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

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

image

看一下源码,增加一下印象:

/* 追加字符串*/
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

这来能为仁兄呢分配内存的大小都是 2/4/8/16/32/64 字节

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

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

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

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

所以SDS和 内部类型的关系类似于这样的:

连续内存,和非连续内存

image

44 字节

SDS为什么会是这样的两种内部结构呢?回忆一下上面提到的:SDS结构,最小的应该是 SDS_TYPE_8(SDS_TYPE_5默认转成8)

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

所以从上代码看出,一个最小的SDS,至少占用3字节.

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

16字节 = 32bit(4字节) + 4字节 + 8字节

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

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

还记得上面我们提到过的内存分配器么?(2/4/8/16/32/64 字节)

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

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

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

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

image

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

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

关于字符串最大是512M

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,长度为3

image

现在做追加操作,APPEND q scadd ,encoding:raw,长度8

image

  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 取而代之。

image.png

image.png

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

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

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

image.png

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中的元素个数。encodinglength两个字段构成了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
}

image.png

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、底层结构

image.png

简单来讲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为什么用跳表而不用平衡树?

参考资料


公众号:豆仔gogo

golang、算法、后端知识、面试手册

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory