我们知道 Redis 常用的五种类型有： String 、Hash、List 、 Set 、 Ordered Set ，但是对于内部是怎么扭转的大部分都不太清楚。

一、redis 内部内存管理

大致如下图

1、redisDb

redisDb 就是数据库实例，存储了真实的数据，每个 Redis 实例都会有 16 个 redisDb。

redisDb 结构定义如下

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

有 8 个参数：

• dict：dict 是用来存储数据的，当前 DB 下的所有数据都存放在这里。

• expires：存储 key 与过期时间的映射。

• blocking_keys：存储处于阻塞状态的 key 及 client 列表。

• 比如执行阻塞命令 blpop、brpop 或者 brpoplpush 时，如果list为空，将该 client 添加到 DB 中 blocking_keys 这个阻塞 dict。

• ready_keys：存储解除阻塞的 Key。

• 当其他调用方向某个 key 对应 list 中增加元素时，检测是否 client 阻塞在这个 key 上，即 blocking_keys 中是否包含这个 key，有则会将这个 key 加入 read_keys 列表中。

• watched_keys：当 client 使用 watch 指令来监控 key 时，这个 key 和 client 就会被保存到 watched_keys 这个 dict 中。

• id：数据库编号。

2、Dict

dict 数据结构在 Redis 中非常的重要，你可以看到在 redisDb 中，8 个字段中有 5 个是 dict。

dict 结构体定义如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

dict 本身是比较简单的，有三个字段比较重要

• type：用于保存 hash 函数及 key/value 赋值、比较函数。

• ht[2]：用来存储数据的数组。默认 0 号数组，如果 0 号哈希表元素过多，则分配一个 2 倍 0 号哈希表大小的空间给 1 号哈希表，逐步进行迁移。

• rehashidx：用来做标志迁移位置。

3、Dictht & DictEntry

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;

dictEntry 是真正挂载数据的节点，跟 Java 中的 Map 有一点像，采用 key-value 的映射方式。key 采用的是 sds 结构的字符串，value 为存储各种数据类型的 redisObject  结构。

以上了解即可，redisObject 是重点。

二、redisObject

Redis 内部使用一个 redisObject 对象来表示所有的 key 和 value。

redisObject 结构体定义如下：

typedef struct redisObject {
    unsigned type:4;		 	// 刚刚好32 bits，对象的类型，字符串/列表/集合/哈希表
    unsigned encoding:4;	// 编码方式，Redis 为了节省空间，提供多种方式来保存一个数据
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or		 当内存紧张，淘汰数据的时候用到
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;					// 引用计数
    void *ptr;						// 数据指针
} robj;

redisObject 结构体就 5 个字段

1、type 类型（类型）

type 表示的是 Redis 对象的数据类型，代表这条数据是什么类型，目前 Redis 有 7 种类型 ，分别为：

• OBJ_STRING ：字符串对象。

• OBJ_LIST ：列表对象。

• OBJ_SET ：集合对象。

• OBJ_ZSET ：有序集合对象。

• OBJ_HASH ：哈希对象。

• OBJ_MODULE ：模块对象。

• OBJ_STREAM ：消息队列/流对象。

2、encoding（编码）

encoding 是 Redis 对象的内部编码方式，数据内部是以哪种数据结构存放的。目前 Redis 中有 10 种编码 方式，如下：

• OBJ_ENCODING_RAW 

• OBJ_ENCODING_INT 

• OBJ_ENCODING_HT 

• OBJ_ENCODING_ZIPLIST 

• OBJ_ENCODING_ZIPMAP 

• OBJ_ENCODING_SKIPLIST 

• OBJ_ENCODING_EMBSTR 

• OBJ_ENCODING_QUICKLIST 

• OBJ_ENCODING_STREAM 

• OBJ_ENCODING_INTSET 

3、LRU（淘汰机制）

LRU 存储的是淘汰数据用的 LRU 时间或 LFU 频率及时间的数据。

4、refcount（引用计数）

refcount 记录 Redis 对象的引用计数，用来表示对象被共享的次数，共享使用时加 1，不再使用时减 1，当计数为 0 时表明该对象没有被使用，就会被释放，回收内存。

5、ptr（真实引用）

ptr 是真实数据存储的引用，它指向对象的内部数据结构。比如一个 string 的对象，内部可能是 sds 数据结构，那么 ptr 指向的就是 sds，除此之外，ptr 还可能指向 ziplist 、 quicklist 、 skiplist 。

三、Redis 内存常用的四种数据结构

1、SDS（简单动态字符串）

Redis没有直接使用传统语言的字符串表示，而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。

为了较少开销 sds 定义了 5 种结构体 ，分别为： sdshdr5 、 sdshdr8 、 sdshdr16 、 sdshdr32 、 sdshdr64 。

在存储的时候 sds 会根据字符串实际的长度，选择不同的数据结构，以更好的提升内存效率。

5 种结构体的源代码如下：

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

除了 sdshdr5 之外，其他的几个数据结构都包含 4 个字段：

• len ：字符串的长度。

• alloc ：给字符串分配的内存大小。

• flags ：当前字节数组的属性。

• buf ：存储字符串真正的值和一个结束符 \0 。

在 redisObject 的编码字段中 sds 数据结构有三种编码方式，分别为 INT 、 RAW 、 EMBSTR 。

INT 就相对比较简单，ptr 直接指向了具体的数据。在这里就简单的说一说 RAW 和 EMBSTR 的区别。

在 Redis 源码中说明。当保存的字符串长度 小于等于 44  ，采用的是 embstr 编码格式，否则采用 RAW  编码方式。（具体的长度可能每个版本定义不一样）

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

embstr 和 raw 编码方式最主要的区别是在内存分配的时候。

• embstr  编码是专门用于保存短字符串的一种优化编码方式。

• raw  编码调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间，空间依次包含 redisObject 和 sdshdr 两个结构。

embstr 编码

raw 编码

2、ziplist（压缩列表）

ziplist 是专门为了节约内存，并减少内存碎片而设计的数据结构，ziplist是一块连续的内存空间，可以连续存储多个元素，没有冗余空间，是一种连续内存数据块组成的顺序型内存结构。

ziplist 主要包含 5 个部分：

• zlbytes ：ziplist所占用的总内存字节数。

• zltail ：尾节点到起始位置的字节数。

• zllen ：总共包含的节点/内存块数。

• entry ：ziplist 保存的各个数据节点，这些数据点长度随意。

• zlend ：一个魔数 255，用来标记压缩列表的结束。

一个包含 4 个元素的 ziplist，总占用字节是 100bytes，该 ziplist 的起始元素的指针是 p，zltail 是 80，则第 4 个元素的指针是 P+80。

ziplist 的存储节点是 zlentry，结构体定义如下：

typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

zlentry 结构体中有 6 个字段：

• prevRawLen ：前置节点长度。

• preRawLenSize ：编码 preRawLen 需要字节数。

• len ：当前节点长度。

• lensize ：编码 len 所需要字节数。

• encoding ： 当前节点所用编码类型。

• entryData ：当前节点数据。

由于 ziplist 是连续紧凑存储，没有冗余空间，所以插入新的元素需要扩展内存，如果 ziplist 占用空间太大，realloc 重新分配内存和拷贝的开销就会很大，所以 ziplist 不适合存储过多元素，也不适合存储过大的字符串。

ziplist  是 hash、sorted set 数据类型的内部存储结构之一

• 对于 hash 来说，元素不超过 512  个且值不超过 64个字节，会使用 ziplist l来存储，我们可以通过修改 hash-max-ziplist-entries 、 hash-max-ziplist-value  参数来控制。

• 对于 sorted set 来说，元素不超过 128 个且值不超过 64 字节，使用 ziplist 来存储，可以通过调整 zset-max-ziplist-entries 、 zset-max-ziplist-value  来控制。

3、quicklist（快速列表）

quicklist  数据结构是 Redis 在 3.2 之后 引入的，用来替换 linkedlist 。因为 linkedlist 每个节点有前后指针，要占用 16 字节，而且每个节点独立分配内存，很容易加剧内存的碎片化。

而 ziplist  由于紧凑型存储，增加元素需要 realloc，删除元素需要内存拷贝，天然不适合元素太多、value 太大的存储，quicklist 也就诞生了。

quicklist 相关结构体定义如下：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long 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 结构图

quicklist 整体结构还是比较简单的，它是一个基于 ziplist 的双向链表。将数据分段存储到 ziplist，然后将这些 ziplist 用双向指针连接。

quicklist 结构体说明：

• head、tail ：两个指向第一个和最后一个 ziplist 节点的指针。

• count ：quicklist 中所有的元素个数。

• len ：ziplist 节点的个数。

• compress ：LZF 算法的压缩深度。

quicklistNode 结构体就更简单的了

quicklistNode 主要包含一个 prev/next  双向指针，以及一个 ziplist  节点。单个 ziplist 节点可以存放多个元素。

quicklist  是 list  列表的内部数据结构，quicklist 从头尾读写数据很快，时间复杂度为 O(1)。从中间任意位置插入或读写元素，速度较慢，时间复杂度为 O(n)。

4、zskiplist（跳跃表）

在 Java 中也有跳跃表，跳跃表 zskiplist 是一种有序数据结构，它通过在每个节点维持多个指向其他节点的指针，从而可以加速访问。

在大部分场景，跳跃表的效率和平衡树接近，跳跃表支持平均 O(logN) 和最差 O(n) 复杂度的节点查找，并且跳跃表的实现比平衡树要简单。

但是在 Redis 中 zskiplist 只有在以下两种情况下会使用到跳跃表：

• 在 sorted set 数据类型中，如果元素数较多或元素长度较大，则使用跳跃表作为内部数据结构。默认 元素数超过 128  或者最大 元素长度超过 64 ，此时有序集合就采用 zskiplist  进行存储。

• 在集群结点中用作内部数据结构。

在 Redis 中，跳跃表主要有 zskiplistNode 和 zskiplist 组合，定义如下：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

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

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

跳跃表 zskiplist 结构比较简单，有 4 个字段：

• header ：指向跳跃表的表头节点。

• tail ：指向跳跃表的表尾节点。

• length ：表示跳跃表的长度，它是跳跃表中不包含表头节点的节点数量。

• level ：目前跳跃表内，除表头节点外的所有节点中，层数最大的那个节点的层数。

跳跃表的节点 zskiplistNode 要相对复杂一些。不过也只有 4 个字段：

• ele：节点对应的 sds 值，在 zset 有序集合中就是集合中的 field 元素。

• score ：节点的分数，通过 score，跳跃表中的节点自小到大依次排列。

• backward ：指向当前节点的前一个节点的指针。

• level ：节点中的层，每个节点一般有多个层。每个 level 层都带有两个属性，一个是 forwad 前进指针，它用于指向表尾方向的节点；另外一个是 span 跨度，它是指 forward 指向的节点到当前节点的距离。

跳跃表的思想比较简单，以空间换时间，可以实现快速查找。

四、总结

参考内容

• 《Redis 设计与实现》

• https://blog.csdn.net/sihai12345/article/details/109465772

未经允许请勿转载：程序喵 » Redis 数据内部存储的数据结构