Redis数据结构分析

Acfe

Redis有
内存数据库的赞誉，其支持一下几种数据结构：

1.      



String

2.      



Hashes

3.      



List

4.      



Set

本文从源代码角度来分析各种数据结构在
Redis
内部是如何存储和读取的。

在介绍各种数据结构之前，首先来介绍下
redisObject
这个
Struct
，
String
，
Hash
，
List
和
Set
在
Redis
内部都是以
redisObject
来存储的

 

/* A redis object, that is a type able to hold a string / list / set */
/* The actual Redis Object */
#define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */
typedef struct redisObject {
unsigned type:4;
unsigned storage:2;     /* REDIS_VM_MEMORY or REDIS_VM_SWAPPING */
unsigned encoding:4;
unsigned lru:22;        /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;
/* VM fields are only allocated if VM is active, otherwise the
* object allocation function will just allocate
* sizeof(redisObjct) minus sizeof(redisObjectVM), so using
* Redis without VM active will not have any overhead. */
} robj;
 
type:String, Hash,List,Set,Sorted set;

storage:
这个参数只是在VM
开启后才能用到，当VM
有很大的性能问题，基本不建议开启；


encoding:

编码方式: raw/int/ht/zmap/linkedlist/ziplist/intset
；



 
lru
：LRU
期限，Redis
默认的LRU
时间是1.5
年，所有基本不需要考虑key
被LRU
掉的问题

refcount:
被引用的次数，因为Redis
有shareObject
的概念，目前只支持共享StringObject
。Redis
的共享对象有两大类比：第一类：Redis server
的各种操作需要经常用到的各类对象，如：Redis Command
的分隔符 "\r\n",
用于Redis command
的reply
的"+OK\r\n"
或者"-ERR\r\n"
等对象，因为在Redis
的各种操作这类对象要被频繁使用，所以就在启动 Redis
的时候创建好，然后共用这些对象，减少时间成本和空间成本；第二，类的共享对象就是对应于数字的StringObject
，如：Set "olylakers1" 1234;
Set "olylakes2" 1234;
在Redis
内部，"olylakers1"
和"olylakers2"
这两个key
都指向由数字1234
转化的StringObject
。这
样在海量数据和特定存储内容下，可以节省大量的内存空间。可用通过REDIS_SHARED_INTEGERS
这个参数来指定Redis
启动的时候创建多 少个第二类共享对象，默认的参数是10000
，即创建的StrongObject
个取值范围是0-9999
之间。

Ptr
：对象数据；

 

redisObjects
都是存放在redisDb
里面的，Redis
默认的是创建16
个db
：

 

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 *io_keys;              /* Keys with clients waiting for VM I/O */
dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
int id;
} redisDb;
 
        redisDb
维护了各种dict
，所以说redis
内部基本的数据存储结构就是一个dict
，dict
就是一个字典的数据结构，比较特殊的就是每个dict
含有两个table
，即两个dictht
，这是为了实现增量rehashe
准备的，当redis
的dict
在进行rehashe
的时候，新的数据插将被添加到dictht ht[1]
当中，反之则添加到ht[0]
中

 

typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
 
Redis
在响应各种命令的时候，把接收到的命令参数（key
和value
等）都转化成type=
REDIS_STRING
的redisObject
，最终执行命令将key
和value
存储到redisDb
的dict
的时候，存储的形式和内容是不相同的：在dict
里面，key
存储的是redisObject
里面的prt
所指向的数据，而value
存储的则是和命令对应的redisObject
，如执行list
的命令lpush listname content
，redisDb
里面，存放的一条记录key
为内容listname
的字符串，而value
（此value
不是命令对应的value
）存储的则是一个redisObject
（type= REDIS_ENCODING_ZIPLIST
， prt=ziplist
），然后把content
对应的内容add
到ziplist
上。

最后通过一张图来展示Redis内部DB的实现和其支持的各种data types在redis DB内的存储方式
Redis DB & data types