• Redis内存数据结构与编码
  • 发布于 1个月前
  • 43 热度
    0 评论
  • 小马哥
  • 1 粉丝 19 篇博客
  •   

想要弄清楚Redis内部如何支持5种数据类型,也就是要弄清Redis到底是使用什么样的数据结构来存储、查找我们设置在内存中的数据。

虽然我们使用5种数据类型来缓存数据,但是Redis会根据我们存储数据的不同而选用不同的数据结构和编码。

这些数据类型在内存中的数据结构和编码有很多种,随着我们存储的数据类型的不同、数据量的大小不同都会引起内存数据结构的动态调整。

本文只是做数据结构和编码的一般性介绍,不做过多细节讨论,一方面是关于Redis源码分析的资料网上有很多,还有一个原因就是Redis每一个版本的实现有很大差异,一旦展开细节讨论,每一个点每一个数据结构都会很复杂,所以我们这里就不展开讨论这些,只是起到抛砖引玉作用。

1、OBJECT encoding key、DEBUG OBJECT key

我们知道使用type命令可以查看某个key是否是5种数据类型之一,但是当我们想查看某个key底层是使用哪种数据结构和编码来存储的时候,可以使用OBJECT encoding命令。

同样一个key,由于我们设置的值不同,Redis选用了不同的内存数据结构和编码。虽然Redis提供String数据类型,但是Redis会自动识别我们cache的数据类型是int还是String。

如果我们设置的是字符串,且这个字符串长度不大于39字节,那么将使用embstr来编码;如果大于39字节将使用raw来编码。Redis4.0将这个阀值扩大了45个字节。

除了使用OBJECT encoding命令外,我们还可以使用DEBUG OBJECT命令来查看更多详细信息。

DEBUG OBJECT能看到这个对象的refcount引用计数、serializedlength长度、lru_seconds_idle时间,这些信息决定了这个key缓存清除策略。

2、简单动态字符串(simple dynamic String)

简单动态字符串简称SDS,在Redis中所有涉及到字符串的地方都是使用SDS实现,当然这里不包括字面量。SDS与传统C字符串的区别就是SDS是结构化的,它可以高效的处理分配、回收、长度计算等问题。

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

这是Redis3.0版本的sds.h头文件定义,3.0.0之后变化比较大。len表示字符串长度,free表示空间长度,buf数组表示字符串。

SDS有很多优点,比如,获取长度的时间复杂度O(1),不需要遍历所有charbuf[]组数,直接返回len值。

static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

当然还有空间分配检查、空间预分配、空间惰性释放等,这些都是SDS结构化字符串带来的强大的扩展能力。

3、链表(linked list)

链表数据结构我们是比较熟悉的,最大的特点就是节点的增、删非常灵活。Redis List数据类型底层就是基于链表来实现。这是Redis3.0实现。

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

在Redis3.2.0版本的时候引入了quicklist链表结构,结合了linkedlist和ziplist的优势。

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklist提供了灵活性同时也兼顾了ziplist的压缩能力,quicklist->encoding指定了两种压缩算法。quickList->compress表示我们可以进行quicklist node的深度压缩能力。Redis提供了两个有关于压缩的配置:

List-max-zipList-size:zipList长度控制;
List-compress-depth:控制链表两端节点的压缩个数,越是靠近两端的节点被访问的机率越大,所以可以将访问机率大的节点不压缩,其他节点进行压缩。

对比Redis3.2的quicklist与Redis3.0,很明显quicklist提供了更加丰富的压缩功能。Redis3.0的版本是每个listnode直接缓存值,而quicklistnode还有强大的有关于压缩能力。

LPUSH list:products:mall 100 200 300
(integer) 3

OBJECT encoding list:products:mall
"quicklist"

4、字典(dict)

dict字典是基于Hash算法来实现,是Hash数据类型的底层存储数据结构。我们来看下Redis3.0.0版本的dict.h头文件定义:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;
    int iterators; 
} dict;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

说到Hash table有两个东西是我们经常会碰到的,首先就是Hash碰撞问题,Redis dict是采用链地址法来解决,dictEntry->next就是指向下个冲突key的节点。

还有一个经常碰到的就是rehash的问题,提到rehash我们还是有点担心性能的。那么Redis实现是非常巧妙的,采用惰性渐进式rehash算法。

在dict struct里有一个ht[2]组数,还有一个rehashidx索引。Redis进行rehash的大致算法是这样的:

首先会开辟一个新的dictht空间,放在ht[2]索引上,此时将rehashidx设置为0,表示开始进入rehash阶段,这个阶段可能会持续很长时间,rehashidx表示dictEntry个数。每次当有对某个ht[1]索引中的key进行访问时,获取、删除、更新,Redis都会将当前dictEntry索引中的所有key rehash到ht[2]字典中。一旦rehashidx=-1表示rehash结束。

5、跳表(skip list)

skip list是Zset的底层数据结构,有着高性能的查找排序能力。

我们都知道一般用来实现带有排序的查找都是用Tree实现,不管是各种变体的B Tree还是B+Tree,本质都是用来做顺序查找。

skip list实现起来简单,性能也与B Tree相接近。

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;


typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

zskiplistNode->zskiplistLevel->span这个值记录了当前节点距离下个节点的跨度。每一个节点会有最大不超过zskiplist->level节点个数,分别用来表示不同跨度与节点的距离。

每个节点会有多个forward向前指针,只有一个backward指针。每个节点会有对象__*obj__和score分值,每个分值都会按照顺序排列。

6、整数集合(int set)

int set整数集合是set数据类型的底层实现数据结构,它的特点和使用场景很明显,只要我们使用的集合都是整数且在一定的范围之内,都会使用整数集合编码。

SADD set:userid 100 200 300
(integer) 3

OBJECT encoding set:userid
"intset"

int set使用一块连续的内存来存储集合数据,它是数组结构不是链表结构。

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

intset->encoding用来确定contents[]是什么类型的整数编码,以下三种值之一:

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

Redis会根据我们设置的值类型动态sizeof出一个对应的空间大小。如果我们集合原来是int16,然后往集合里添加了int32整数将触发升级,一旦升级成功不会触发降级操作。

7、压缩表(zip list)

zip list压缩表是List、Zset、Hash数据类型的底层数据结构之一。它是为了节省内存通过压缩数据存储在一块连续的内存空间中。

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;

它最大的优点就是压缩空间,空间利用率很高。缺点就是一旦出现更新可能就是连锁更新,因为数据在内容空间中都是连续的,最极端情况下就是可能出现顺序连锁扩张。

压缩列表会由多个zlentry节点组成,每一个zlentry记录上一个节点长度和大小,当前节点长度lensize和大小len包括编码encoding。

这取决于业务场景,Redis提供了一组配置,专门用来针对不同的场景进行阈值控制:

hash-max-ziplist-entries 512
hash-max-ziplist-value 64
list-max-ziplist-entries 512
list-max-ziplist-value 64
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

上述配置分别用来配置ziplist作为Hash、List、Zset数据类型的底层压缩阈值控制。

8、Redis Object类型与映射

Redis内部每一种数据类型都是对象化的,也就是我们所说的5种数据类型其实内部都会对应到Redis Object对象,然后再由Redis Object来包装具体的存储数据结构和编码。

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

这是一个很OO的设计,redisObject->type是5种数据类型之一,redisObject->encoding是这个数据类型所使用的数据结构和编码。

我们看下Redis提供的5种数据类型与每一种数据类型对应的存储数据结构和编码。

/* Object types */
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

#define REDIS_ENCODING_RAW 0     
#define REDIS_ENCODING_INT 1    
#define REDIS_ENCODING_HT 2
#define REDIS_ENCODING_ZIPMAP 3
#define REDIS_ENCODING_LINKEDLIST 4
#define REDIS_ENCODING_ZIPLIST 5 
#define REDIS_ENCODING_INTSET 6  
#define REDIS_ENCODING_SKIPLIST 7  
#define REDIS_ENCODING_EMBSTR 8

REDIS_ENCODING_ZIPMAP 3这个编码可以忽略了,在特定的情况下有性能问题,在Redis 2.6版本之后已经废弃,为了兼容性保留。

图是Redis 5种数据类型与底层数据结构和编码的对应关系:

但是这种对应关系在每一个版本中都会有可能发生变化,这也是Redis Object的灵活性所在,有着OO的这种多态性。

redisObject->refcount表示当前对象的引用计数,在Redis内部为了节省内存采用了共享对象的方法,当某个对象被引用的时候这个refcount会加1,释放的时候会减1。
redisObject->lru表示当前对象的空转时长,也就是idle time,这个时间会是Redis lru算法用来释放对象的时间依据。可以通过OBJECT idletime命令查看某个key的空转时长lru时间。

用户评论