Redis底层数据结构实现
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编码实现。
embstr编码创建的内存块结构
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”
