Redis底层数据结构实现 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属性值，会在追加前重新进行内存空间分配。