1. 简介

Redis是一个基于内存的非关系型的键值对数据库，因它基于内存的特性所以它的速度比传统的关系型数据库快，除此之外它还具有许多特性：

支持事务
支持AOF和RDB持久化
支持多种数据数据结构
流水线、发布\订阅功能
主从复制
内存回收

本文讲的是Redis丰富的数据结构的实现原理

实现

五种基本类型

Redis是一个键值对数据库，而键都是字符串（Redis内部实现的简单动态字符串）类型，值有5种基本类型，分别是：

STRING（字符串）
LIST（列表）
SET（集合）
ZSET（有序集合）
HASH（哈希）

不同类型的不同实现

类型	编码
STRING（字符串）	INT（整型）
STRING（字符串）	EMBSTR（简单动态字符串）
STRING（字符串）	RAW（简单动态字符串）
LIST（列表）	QUICKLIST（快表）
LIST（列表）	LINKEDLIST（快表）
SET（集合）	INTSET（整数集合）
SET（集合）	HT（哈希表）
ZSET（有序集合）	ZIPLIST（压缩列表）
ZSET（有序集合）	SKIPLIST（跳表）
HASH（哈希）	ZIPLIST（压缩列表）
HASH（哈希）	HT（哈希表）

redisObject

在Redis中，这5种基本类型的对象都是封装在robj这个结构体中，源码如下：

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;

// 通过调用createObject方法可以创建其对象
robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}

下面解释下各个属性：

type

该属性表示对象的类型，占4个bit，源码如下：

#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

在Redis中通过使用TYPE命令可以获得其类型

127.0.0.1:6379> TYPE key

string

encoding

该属性表示该类型的对象具体的实现，这样做的目的是为了使在不同场景下灵活使用不同的数据结构

#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

在Redis中通过使用OBJECT ENCODING命令可以获得其编码

127.0.0.1:6379> OBJECT ENCODING key

“embstr”

lru

该属性记录该对象最近一次被访问的时间，如果服务器打开了maxmemory选项，并且服务器用于内存回收的算法为volatile-lru或allkeys-lru，当占用内存超过maxmemory设置的上限时，最早被访问的会先被释放。

在Redis中通过使用OBJECT IDLETIME命令可以获得其lru时间

127.0.0.1:6379> OBJECT IDLETIME key

(integer) 10155

refcount

该属性有两个作用：

用于引用计数实现内存回收，该属性值表示对象被多少个程序引用，当对象被创建时，该属性值为1，当该值为0时对象占用的内存会被回收。
用于对象共享，比如Redis在初始化服务器时就会创建0到9999的字符串对象用于对象共享，每当使用set命令创建一个新字符串对象，如果要创建的字符串已经存在则将指向值的指针指向该字符串对象，并将该对象的refcount加1。

127.0.0.1:6379> OBJECT REFCOUNT key

(integer) 2

REDIS_STRING（字符串）

Redis的字符串一共有三种实现方式，分别适用于不同场景，其中有一种实现是简单动态字符串，简称SDS，下面的结构体sdshdr就表示一个SDS，它具有以下几个优点：

常数时间获取字符串长度
自动扩容
预分配空间以减少内存重新分配次数
二进制安全
重用部分C语言函数库

struct sdshdr {
 // buf 中已占用空间的长度
 int len;

 // buf 中剩余可用空间的长度
 int free;

 // 数据空间
 char buf[];
};

INT

当字符串保存的是一个可以用long类型来表示的整数时，那么robj对象里的属性ptr的类型void *就会被替换为long，而encoding的值会设置为int表示该字符串的实现方式是整型。

127.0.0.1:6379> SET key 88

OK

127.0.0.1:6379> OBJECT ENCODING key

“int”

EMBSTR

在目前最新版本中，当字符串保存的是一个小于等于44个字节的字符串时，那么robj对象里的属性ptr就会指向一个SDS对象，而encoding的值会设置为embstr表示该字符串的实现方式是SDS（简单动态字符串）。embstr是一种用来保存短字符串的编码方式，embstr编码通过调用一次内存分配函数来创建一块连续的内存空间，即redisObject对象和它的ptr指针指向的SDS对象是连续的。不过embstr编码的字符串对象是只读性的，一旦对其指向APPEND命令追加字符串会导致其变为raw编码实现。

127.0.0.1:6379> SET key value

OK

127.0.0.1:6379> OBJECT ENCODING key

“embstr”

RAW

在目前最新版本中，当字符串对象保存的是一个超过44个字节的字符串时，那么robj对象里的属性ptr就会指向一个SDS对象，而encoding的值会设置为raw表示该字符串的实现方式是SDS（简单动态字符串）。raw编码的字符串对象是可读可写的，对其指向APPEND命令追加字符串会不会导致其实现改变，如果追加的字符串的长度超过其free属性值，会在追加前重新进行内存空间分配。

127.0.0.1:6379> SET key value

OK

127.0.0.1:6379> OBJECT ENCODING key

“raw”

Redis底层数据结构实现

2018-11-15
Redis