redis对象——5种基本类型实现原理

Redis主要支持的数据类型有5种：String ，Hash ，List ，Set ，和 Sorted Set。

redis对象

一、对象类型与编码

1.1. realObject对象结构

Redis使用 string list zset hash set 五大数据类型来存储键和值。在每次生成一个键值对时，都会生成两个对象，一个储存键一个储存值。redis定义了RealObject结构体。

typedef struct redisObject {
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    /* lru time (relative to server.lruclock) */
    unsigned lru:LRU_BITS; 
    //引用计数
    int refcount;
   //指向底层实现数据结构的指针
    void *ptr;
} robj;

1.1.1. type

redis 的对象有五种类型，分别是string list zset hash set，type就是用来标识这五种类型的。

/* Object types */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

注：在redis中，键总是一个字符串对象，而值可以是字符串、列表、集合等对象。

1.1.2.编码类型encoding

redis的对象的实际编码方式由encoding参数指定，也就是ptr指针指向的数据以何种底层实现存放。

`/* Objects encoding. Some kind of objects like Strings and Hashes can be`

`* internally represented in multiple ways. The 'encoding' field of the object`

`* is set to one of this fields for this object. */`

`#define OBJ_ENCODING_RAW 0     ``/* Raw representation -- 简单动态字符串sds*/`

`#define OBJ_ENCODING_INT 1     ``/* Encoded as integer -- long类型的整数*/`

`#define OBJ_ENCODING_HT 2      ``/* Encoded as hash table -- 字典dict*/`

`#define OBJ_ENCODING_ZIPMAP 3  ``/* Encoded as zipmap -- 3.2.5版本后不再使用 */`

`#define OBJ_ENCODING_LINKEDLIST 4 ``/* Encoded as regular linked list -- 双向链表*/`

`#define OBJ_ENCODING_ZIPLIST 5 ``/* Encoded as ziplist -- 压缩列表*/`

`#define OBJ_ENCODING_INTSET 6  ``/* Encoded as intset -- 整数集合*/`

`#define OBJ_ENCODING_SKIPLIST 7  ``/* Encoded as skiplist -- 跳表*/`

`#define OBJ_ENCODING_EMBSTR 8  ``/* Embedded sds string encoding -- embstr编码的sds*/`

`#define OBJ_ENCODING_QUICKLIST 9 ``/* Encoded as linked list of ziplists -- 由双端链表和压缩列表构成的高速列表*/`

可以通过 object encoding key 指令查看值对象的编码

对象的编码

1.1.3. 访问时间lru

表示该对象最后一次被访问的时间，占用24bit。保存该值的目的是为了计算对象的空转时长，便于决定是否应该释放该键。

1.1.4.引用计数refcount

c语言不具备自动内存回手机制，所以为每个对象设定了引用计数。

当创建一个对象时，记为1；
当被一个新的程序使用时，引用计数++；
不再被一个程序使用时，引用计数--；
当引用计数为0时，释放该对象，回收内存。

void decrRefCount(robj *o) {
    // 引用计数为小于等于0，报错
    if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
    // 引用计数等于1，减1后为0
    // 须要释放整个redis对象
    if (o->refcount == 1) {
        switch(o->type) {
        // 依据对象类型。调用不同的底层函数对对象中存放的数据结构进行释放
        case OBJ_STRING: freeStringObject(o); break;
        case OBJ_LIST: freeListObject(o); break;
        case OBJ_SET: freeSetObject(o); break;
        case OBJ_ZSET: freeZsetObject(o); break;
        case OBJ_HASH: freeHashObject(o); break;
        default: serverPanic("Unknown object type"); break;
        }
        // 释放redis对象
        zfree(o);
    } else {
        // 引用计数减1
        o->refcount--;
    }
}

1.1.5.ptr指向实际存放的对象

指向底层实现数据结构的指针。

二、字符串类型

字符串是 Redis最基本的数据类型，Redis 中字符串对象的编码可以是 int，raw 或者 embstr 中的某一种，分别介绍如下：

int 编码：保存long 型的64位有符号整数
embstr 编码：保存长度小于44字节的字符串
raw 编码：保存长度大于44字节的字符串

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

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

编码的好处：

其中buf[]结束并不依赖于‘\0’,使用len判断结束，可以保存二进制流对象。其中buf[]是一个柔性数组。
预分配，可以减少修改字符串长度增长时造成的再次分配。

2.1 OBJ_ENCODING_INT

命令示例： set foo 123

当字符串键值的内容可以用一个 64位有符号整形 来表示时，Redis会将键值转化为 long型来进行存储，此时即对应 OBJ_ENCODING_INT 编码类型。

OBJ_ENCODING_INT 编码类型内部的内存结构可以形象地表示如下：

set foo 123 时键值的内存结构

而且 Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象，这就意味着如果 set字符串的键值在 0~10000 之间的话，则可以 直接指向共享对象 而不需要再建立新对象，此时键值不占空间！

因此，当执行如下指令时：

set key1 100
set key2 100

其实 key1 和 key2 这两个键值都直接引用了一个 Redis 预先已建立好的共享 redisObject 对象，就像下面这样：

共享对象

源码之前，了无秘密，我们再对照下面的源码，来理解一下上述过程

INT编码的源码

2.2 OBJ_ENCODING_RAW

指令示例： set foo abcdefghijklmnopqrstuvwxyzabcdeffasdffsdaadsx

正如指令示例，当字符串的键值为长度大于 44 的 超长字符串 时，Redis 则会将键值的内部编码方式改为 OBJ_ENCODING_RAW 格式，这与上面的 OBJ_ENCODING_EMBSTR 编码方式的不同之处在于此时动态字符串 sds 的内存与其依赖的 redisObject 的 内存不再连续 了，以 set foo abcdefghijklmnopqrstuvwxyzabcdeffasdffsdaadsx 为例，其键值的内存结构如下所示：

set foo abcdefghijklmnopqrstuvwxyzabcdeffasdffsdaadsx时键值的内存结构

2.3 OBJ_ENCODING_EMBSTR

2.3.1 低版本redis的OBJ_ENCODING_EMBSTR字符串长度39

从Redis 3.0 版本开始，字符串引入了embstr编码方式，长度小于OBJ_ENCONDING_EMBSTR_SIZE_LIMIT的字符串将以EMBSTR方式存储。

EMBSTR方式的意思是 embedded string，字符串的空间由redisObject和sdshdr组成，两者分配在同一个内存块中。

redis中内存分配使用的是jemalloc，jemalloc分配内存的时候是按照8,16,32,64作为块的单位进行分配的。为了保证采用这种编码方式的字符串能被jemalloc分配在同一个块(chunk)中，该块长度不能超过64，故字符串长度限制OBJ_ENCONDING_EMBSTR_SIZE_LIMIT = 64 - sizeof('\0') -sizeof(robj) -sizeof(sdshdr) =64-1-16-8=39。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

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

这样可以有效减少内存分配的次数，提高内存分配的效率，降低碎片率。

2.3.2 版本3.2之后redis的OBJ_ENCODING_EMBSTR字符串长度44

版本3.2之前，sdshdr使用unsigned记录了len和free，但对于短的sds浪费不少空间(两个unsigned int 8个字节)。

redis3.2后将单位unsigned int 变成了uint8_t（还加了一个char flags）这样更加优化小sds的内存使用。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

struct sdshdr8 {
    uint8_t len;
    uint8_t free;
    char flags
    char buf[];
};

sdshdr8与之前的sdshdr相比正好减少了5个字节（sdsdr8 = uint8_t * 2 + char = 1*2+1 = 3, sdshdr = unsigned int * 2 = 4 * 2 = 8）,所以其能容纳的字符串长度增加了5个字节变成了44。

set foo abc时的键值内存结构

三、列表类型

列表类型内部使用双向链表实现。内部数据结构如下图。

列表数据结构

3.1. 编码转换

value对象内部以linkedlist或者ziplist来实现。

3.1.1 redis3.2之前

使用ziplist（压缩列表）编码必须同时满足：

当list的元素个数小于512个
单个元素的长度小于64字节

否则就会采用linkedlist（双向链表）结构。

3.1.2. redis3.2之后

链表完全采用quicklist。

3.2.OBJ_ENCODING_ZIPLIST

Ziplist 压缩列表是一种紧凑编码格式，总体思想是时间换空间，即以部分读写性能为代价，来换取极高的内存空间利用率，因此只会用于 字段个数少，且字段值也较小 的场景。

压缩列表内存利用率极高的原因与其连续内存的特性是分不开的，其典型的内存结构可以用下图形象地展示出来：

ZIPLIST 内存模型

所以如果用 Ziplist来存储 Redis的散列类型的话，元素的排列方式就变成了如下图所示的形象示意图：即key和value都是逻辑连续内存：

用 Ziplist来存储 Redis的散列类型

3.3.OBJ_ENCODING_LINKEDLIST 和 OBJ_ENCODING_QUICKLIST

在redis 3.2之前一般的链表采用LINKEDLIST编码。

在redis 3.2版本开始，所有的链表都采用QUICKLIST编码。

两者都是使用基本的双端链表数据结构，区别是QUICKLIST每个结点的值都是使用ZIPLIST进行存储的。

// 3.2版本之前
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;
// 3.2版本
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又包含四个数据项，那么对外表现上，这个list就总共包含12个数据项。这样的设计，实际上是对于时间和空间的一种折中。

linkedlist便于在表的两端进行push和pop操作，但是它的内存开销较大。首先，它的每个节点除了要保存数据之外还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，容易产生内存碎片，还容易造成抖动。
ziplist由于是一整块连续的内存，存储效率很高，但不利于添加和删除操作，每次都会重新realloc，尤其是当ziplist很长的时候，一次realloc造成的开销特别的大，查询的开销也特别的大。

于是quicklist集合了两个结构的有点，但多少是合理的长度呢，redis系统中用户可以自定义这个值。

`list-``max``-ziplist-``size` `-2`

这个参数可正可负，取正值 n 的时候，这个正值表示的就是每个ziplist的长度最多不能超过n。

当取复制的时候只能取 -1 ~ -5 这五个值，表示按照字节数来限定每个ziplist节点的长度。

-1 每个quicklist节点大小不能超过4Kb
-2 每个quicklist节点大小不能超过8Kb
-3 每个quicklist节点大小不能超过16Kb
-4 每个quicklist节点大小不能超过32Kb
-5 每个quicklist节点大小不能超过64Kb

3.3.1. 节点的压缩

另外，quicklist的设计目标是用来存储很长的数据链表的，当链表很长的时候，最容易被访问的是两端的数据，中间的数据被访问的概率比较低，如果应用场景符合这个特点，list还提供了一个选项，可以把中间的数据节点进行压缩，而两边不被压缩，参数

`list-compress-depth 0`

就是用来完成这个设置的，数值表示两边不被压缩的节点个数

其中 0 是个特殊值，表示都不压缩，这是 redis的默认值。
1表示quicklist两端各有1个节点不压缩，中间的节点压缩。
2表示quicklist两端各有2个节点不压缩，中间的节点压缩
3......
对于quicklist的压缩算法，采用LZF---一种无损压缩算法。https://www.cnblogs.com/pengze0902/p/5998843.html

3.3.2. quicklist的数据结构(quicklist.h)

`/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.`

`* We use bit fields keep the quicklistNode at 32 bytes.`

`* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).`

`* encoding: 2 bits, RAW=1, LZF=2.`

`* container: 2 bits, NONE=1, ZIPLIST=2.`

`* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.`

`* attempted_compress: 1 bit, boolean, used for verifying during testing.`

`* extra: 12 bits, free for future use; pads out the remainder of 32 bits */`

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;

`/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.`

`* 'sz' is byte length of 'compressed' field.`

`* 'compressed' is LZF data with total (compressed) length 'sz'`

`* NOTE: uncompressed length is stored in quicklistNode->sz.`

`* When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */`

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

`/* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.`

`* 'count' is the number of total entries.`

`* 'len' is the number of quicklist nodes.`

`* 'compress' is: -1 if compression disabled, otherwise it's the number`

`*                of quicklistNodes to leave uncompressed at ends of quicklist.`

`* 'fill' is the user-requested (or default) fill factor. */`

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;

quicklistNode结构代表quicklist的一个节点

prev 指向前一个节点
next 指向后一个节点
zl 数据指针。如果当前节点没有被压缩，它指向一个ziplist；否则，它指向一个quicklistLZF结构
sz 表示zl指向的ziplist的总大小，如果他被压缩了，那么它指压缩前的ziplist大小。
count表示ziplist里面包含的数据项的个数，
encoding 表示ziplist是否被压缩
container 保留字段，表示一个quicklistNode是直接存数据，还是使用ziplist存数据，或者采用其他结构类存数据。但是在目前实现中是一个固定值2，表示ziplist存数据
recompress 这个节点之前被压缩没有，当我们使用lindex这样的命令查看某一项本来被压缩的数据时，需要把数据暂时解压，这时就设置recompress=1 做一个标记，等空闲时候再次把数据重新压缩。
attemped_compress
extra 其他扩展字段目前弃用

quicklistLZF结构表示一个被压缩的ziplist。

sz 表示压缩后的ziplist大小
compress 柔性数组（flexible array member）存放数据压缩后的ziplist字节数组

quicklist是真正的保存quicklist的结构

count 所有ziplist数据项的总和
len quicklistNode节点的个数
fill ziplist大小的摄者存放 list-max-ziplist-size
compress 节点压缩深度存放 list-compress-depth

上图为一个quicklist结构图对应的fill和compress 配置为

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

其中左右两端各有两个黄色节点，是没有被压缩的，他们的数据指针zl直接指向ziplist结构。中间的蓝色节点是lzf压缩过的，zl指针指向quicklistLZF结构。

左侧头结点上的ziplist有两项数据，右侧头结点有1项。

3.3.3. quicklist插入

头尾节点插入时，如果对应节点的ziplist大小没有超过限制，则新数据直接被插入对应ziplist；如果超过限制，那么新建一个quicklistNode节点，把待插入节点插入新的ziplist中。
如果插入的位置是链表中间部分，当插入位置所在的ziplist没达到大小限制，直接插入对应ziplist；
当所在的ziplist大小超过了限制，但插入的位置在ziplist两端，如果相邻节点的ziplist没有超过大小限制，那么就插入相邻节点
如果相邻节点的大小超过了限制，那么新建一个quicklistNode，插入对应节点
对其他情况，需要吧当前ziplist分裂成两个节点，然后在其中一个节点中插入数据。

可参见https://www.jianshu.com/p/0df2b3cb749f

四、hash类型

hash类型

4.1.hash的数据结构

map提供两种结构来存储：

hashtable
ziplist

4.2.编码转换

同时满足以下两个条件，使用ziplist编码：

键值对的键和值字符串长度小于64字节
键值对数量小于512个

否则使用hashtable。

这里成员"较少"，成员值"较小"的标准可以通过如下配置项进行配置：

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

Redis 默认给出了默认值，当然用户可根据实际情况自行配置。

4.3.OBJ_ENCODING_ZIPLIST

同上

4.3.OBJ_ENCODING_HT

OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构，或称为字典结构，其可以实现O(1)复杂度的读写操作，因此效率很高。

在 Redis内部，从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的，关系如下：

Redis哈希嵌套关系

这一关系我们可以从 Redis哈希表定义部分的源码来看出：

image

下面来详解一下各个部分：

关于哈希节点（dictEntry）

dictEntry

关于哈希表（dictht）和字典（dict）

dictht 和 dict

关于dictType

dictType

Redis如何计算Hash值

Redis计算Hash的源代码如下：

计算Hash值

这是一个 C语言宏定义，其实幕后真正承担 Hash值计算的是上面介绍的 dictType结构体中的函数指针 hashFunction。

而该 hashFunction函数指针在初始化时会对应被赋值为一个个真实的计算 Hash值的实际函数，就像下面这样：

hashFunction 函数指针赋值

Redis如何计算存取索引Index值

Index值的计算依赖于上面计算得出的 Hash值，代码如下：

Redis计算索引Index值的源码

五、集合类型

不能有重复数据，
同时集合类型中的数据是无序的
集合类型和列表类型的最大的区别是
- 有序性
  - 列表有序
- 唯一性
  - 集合唯一
使用的值为空的散列表(hash table)，
- 所以这些操作的时间复杂度都是O(1).

5.1.hash数据结构

hash数据结构

intset
hashtable

5.2.编码转换

同时满足以下两个条件，使用intset编码：

集合所有元素为整型
集合元素数量小于512个
否则使用hashtable编码。

5.3 OBJ_ENCODING_INTSET

redis中使用intset实现数量较少数字的set。

set-max-intset-entries 512

实际上 intset是一个由整数组成的有序集合，为了快速查找元素，数组是有序的，用二分查找判断一个元素是否在这个结合上。在内存分配上与ziplist类似，用一块连续的内存保存数组元素，并且对于大整数和小证书采用了不同的编码。

结构如下

//intset.h
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 用两个字节存储，即两个contents数组位置 INTSET_ENC_INT32表示4个字节 INTSET_ENC_INT64表示8个字节)

length 表示inset中元素的个数

contents 柔性数组，表示存储的实际数据，数组长度 = encoding * length。
另外，intset可能会随着数据的添加改编他的编码，最开始创建的inset使用 INTSET_ENC_INT16编码。如果要添加的元素编码比当前intset的编码大。调用intsetUpgradeAndAdd将intset的编码进行增长，然后插入。

如上图 intset采用小端存储。

5.4 OBJ_ENCODING_HT

同上

六、有序集合

有序集合类型为集合中的每个元素都关联了一个分数

6.1.hash数据结构

ziplist
skiplist+hashtable来实现

跳跃表是一种随机化的数据结构
在查找、插入和删除这些字典操作上
其效率可比拟于平衡二叉树（如红黑树）

6.2.编码转换

同时满足以下两个条件，使用ziplist编码：

有序集合所有元素成员长度小于64字节
有序集合元素数量小于128个
否则使用skiplist编码。

6.3. OBJ_ENCODING_ZIPLIST

同上

6.4. OBJ_ENCODING_SKIPLIST

redis里面是用skiplist是为了实现zset这种对外的数据结构。zset提供的操作非常丰富，可以满足许多业务场景，同时也意味着zset相对来说实现比较复杂。

6.4.1. skiplist数据结构简介

如图，跳表的底层是一个顺序链表，每隔一个节点有一个上层的指针指向下下一个节点，并层层向上递归。这样设计成类似树形的结构，可以使得对于链表的查找可以到达二分查找的时间复杂度。

按照上面的生成跳表的方式上面每一层节点的个数是下层节点个数的一半，这种方式在插入数据的时候有很大的问题。就是插入一个新节点会打乱上下相邻两层链表节点个数严格的2:1的对应关系。如果要维持这种严格对应关系，就必须重新调整整个跳表，这会让插入/删除的时间复杂度重新退化为O(n)。

为了解决这一问题，skiplist他不要求上下两层链表之间个数的严格对应关系，他为每个节点随机出一个层数。比如，一个节点的随机出的层数是3，那么就把它插入到三层的空间上，如下图。

那么，这就产生了一个问题，每次插入节点时随机出一个层数，真的能保证跳表良好的性能能么?

首先跳表随机数的产生，不是一次执行就产生的，他有自己严格的计算过程，

首先每个节点都有最下层(第1层)指针
如果一个节点有第i层指针，那么他有第i层指针的概率为p。
节点的最大层数不超过MaxLevel

我们注意到，每个节点的插入过程都是随机的，他不依赖于其他节点的情况，即skiplist形成的结构和节点插入的顺序无关。

这样形成的skiplist查找的时间复杂度约为O(log n)。