分类： LINUX
2012-05-08 15:22:14
转载于：
Redis: A persistent key-value database with built-in net interface written in ANSI-C for Posix systems
1 Redis 内存存储结构本文是基于 Redis-v2.2.4 版本进行分析.
1.1 Redis 内存存储总体结构Redis 是支持多key-value数据库(表)的,并用 RedisDb 来表示一个key-value数据库(表). redisServer 中有一个 redisDb *db; 成员变量, RedisServer 在初始化时,会根据配置文件的 db 数量来创建一个 redisDb 数组. 客户端在连接后,通过 SELECT 指令来选择一个 reidsDb,如果不指定,则缺省是redisDb数组的第1个(即下标是 0 ) redisDb. 一个客户端在选择 redisDb 后,其后续操作都是在此 redisDb 上进行的. 下面会详细介绍一下 redisDb 的内存结构.
redis 的内存存储结构示意图
redisDb 的定义:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
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;
struct |
redisDb 中 ,dict 成员是与实际存储数据相关的. dict 的定义如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 |
typedef struct dictEntry
{
void *key;
void *val;
struct dictEntry *next;
} dictEntry;
typedef struct dictType
{
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht
{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
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; |
dict 是主要是由 struct dictht 的 哈唏表构成的, 之所以定义成长度为2的( dictht ht[2] ) 哈唏表数组,是因为 redis 采用渐进的 rehash,即当需要 rehash 时,每次像 hset,hget 等操作前,先执行N 步 rehash. 这样就把原来一次性的 rehash过程拆散到进行, 防止一次性 rehash 期间 redis 服务能力大幅下降. 这种渐进的 rehash 需要一个额外的 struct dictht 结构来保存.
struct dictht 主要是由一个 struct dictEntry 指针数组组成的, hash 表的冲突是通过链表法来解决的.
struct dictEntry 中的 key 指针指向用 sds 类型表示的 key 字符串, val 指针指向一个 struct redisObject 结构体, 其定义如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82 |
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 占 4 bit,用来表示 key-value 中 value 值的类型,目前 redis 支持: string, list, set,zset,hash 5种类型的值.
/* Object types */
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
#define REDIS_VMPOINTER 8
// storage 占 2 bit ,表示 此值是在 内存中,还是 swap 在硬盘上.
// encoding 占 4 bit ,表示值的编码类型,目前有 8种类型:
/* 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 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 */
/* 如 type 是 REDIS_STRING 类型的,则其值如果是数字,就可以编码成 REDIS_ENCODING_INT,以节约内存.
* 如 type 是 REDIS_HASH 类型的,如果其 entry 小于配置值: hash-max-zipmap-entries 或 value字符串的长度小于 hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储.
* 如 type 是 REDIS_LIST 类型的,如果其 entry 小于配置值: list-max-ziplist-entries 或 value字符串的长度小于 list-max-ziplist-value, 则可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存; 否则采用 REDIS_ENCODING_LINKEDLIST 来存储.
* 如 type 是 REDIS_SET 类型的,如果其值可以表示成数字类型且 entry 小于配置值set-max-intset-entries, 则可以编码成 REDIS_ENCODING_INTSET 类型存储,以节约内存; 否则采用 Dict类型来存储.
* lru: 是时间戳
* refcount: 引用次数
* void * ptr : 指向实际存储的 value 值内存块,其类型可以是 string, set, zset,list,hash ,编码方式可以是上述 encoding 表示的一种.
* 至于一个 key 的 value 采用哪种类型来保存,完全是由客户端的指令来决定的,如 hset ,则值是采用REDIS_HASH 类型表示的,至于那种编码(encoding),则由 redis 根据配置自动决定.
*/ |
Dict 结构在<1.1Redis 内存存储结构>; 已经描述过了,这里不再赘述.
1.3 zipmap 结构如果redisObject的type 成员值是 REDIS_HASH 类型的,则当该hash 的 entry 小于配置值: hash-max-zipmap-entries 或者value字符串的长度小于 hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储.
zipmap 其实质是用一个字符串数组来依次保存key和value,查询时是依次遍列每个 key-value 对,直到查到为止. 其结构示意图如下:
为了节约内存,这里使用了一些小技巧来保存 key 和 value 的长度. 如果 key 或 value 的长度小于ZIPMAP_BIGLEN(254),则用一个字节来表示,如果大于ZIPMAP_BIGLEN(254),则用5个字节保存,第一个字节为保存ZIPMAP_BIGLEN(254),后面4个字节保存 key或value 的长度.
插入 key-value 对 (“age”,30)
插入 key-value 对 (“nick”,”tide”), 后可以看到 empty_len 为1 ,
如果redisObject的type 成员值是 REDIS_LIST 类型的,则当该list 的 elem数小于配置值: hash-max-ziplist-entries 或者elem_value字符串的长度小于 hash-max-ziplist-value, 则可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存. 否则采用 Dict 来存储.
ziplist 其实质是用一个字符串数组形式的双向链表. 其结构示意图如下:
可以通过 prevrawlen 和 currawlen&encoding 来遍列 ziplist.
ziplist 还能到一些小技巧来节约内存.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 |
typedef struct listNode
{
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct listIter
{
listNode *next;
int direction;
} listIter;
typedef struct list
{
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned int len;
} list; |
常见的双向链表,不作分析.
1.6 intset 结构intset 是用一个有序的整数数组来实现集合(set). struct intset 的定义如下:
|
1
2
3
4
5
6
7
8
9
10
11 |
typedef struct intset
{
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset; |
首先，介绍一下 skip list 的概念，然后再分析 zset 的实现.
1.7.1 Skip List 介绍 1.7.1.1 有序链表1) Searching a key in a Sorted linked list
|
1
2
3
4
5
6
7 |
//Searching an element x
cell *p =head ;
while (p->next->key < x ) p=p->next ;
return p ; |
Note: we return the element proceeding either the element containing x, or the smallest element with a key larger than x (if x does not exists)
2) inserting a key into a Sorted linked list
|
1
2
3
4
5
6
7
8
9
10
11 |
//To insert 35 -
p=find(35);
CELL *p1 = (CELL *) malloc(sizeof(CELL));
p1->key=35;
p1->next = p->next ;
p->next = p1 ; |
3) deleteing a key from a sorted list
|
1
2
3
4
5
6
7
8
9 |
//To delete 37 -
p=find(37);
CELL *p1 =p->next;
p->next = p1->next ;
free(p1); |
SKIP LIST : A data structure for maintaing a set of keys in a sorted order.
Consists of several levels.
All keys appear in level 1
Each level is a sorted list.
If key x appears in level i, then it also appears in all levels below i
An element in level i points (via down pointer) to the element with the same key in the level below.
In each level the keys and appear. (In our implementation, INT_MIN and INT_MAX
Top points to the smallest element in the highest level.
1.7.1.3 SkipList(跳跃表)操作1) An empty SkipList
2) Finding an element with key x
|
1
2
3
4
5
6
7
8
9
10
11
12
13 |
p=top
While(1)
{
while (p->next->key < x ) p=p->next;
If (p->down == NULL ) return p->next
p=p->down ;
} |
Observe that we return x, if exists, or succ(x) if x is not in the SkipList
3) Inserting new element X
Determine k the number of levels in which x participates (explained later)
Do find(x), and insert x to the appropriate places in the lowest k levels. (after the elements at which the search path turns down or terminates)
Example – inserting 119. k=2
If k is larger than the current number of levels, add new levels (and update top)
Example – inser(119) when k=4
Determining k
k – the number of levels at which an element x participate.
Use a random function OurRnd() — returns 1 or 0 (True/False) with equal probability.
k=1 ;
While( OurRnd() ) k++ ;
Deleteing a key x
Find x in all the levels it participates, and delete it using the standard ‘delete from a linked list’ method.
If one or more of the upper levels are empty, remove them (and update top)
Facts about SkipList
The expected number of levels is O( log n )
(here n is the numer of elements)
The expected time for insert/delete/find is O( log n )
The expected size (number of cells) is O(n )
1.7.2 redis SkipList 实现/* ZSETs use a specialized version of Skiplists */
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 |
typedef struct zskiplistNode
{
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel
{
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist
{
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
typedef struct zset
{
dict *dict;
zskiplist *zsl;
} zset; |
zset 的实现用到了2个数据结构: hash_table 和 skip list (跳跃表),其中 hash table 是使用 redis 的 dict 来实现的,主要是为了保证查询效率为 O(1),而 skip list (跳跃表) 是用来保证元素有序并能够保证 INSERT 和 REMOVE 操作是 O(logn)的复杂度。
1) zset初始化状态
createZsetObject函数来创建并初始化一个 zset
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
robj *createZsetObject(void)
{
zset *zs = zmalloc(sizeof(*zs));
robj *o;
zs->dict = dictCreate(&zsetDictType,NULL);
zs->zsl = zslCreate();
o = createObject(REDIS_ZSET,zs);
o->encoding = REDIS_ENCODING_SKIPLIST;
return o;
} |
zslCreate()函数用来创建并初如化一个 skiplist。 其中，skiplist 的 level 最大值为 ZSKIPLIST_MAXLEVEL=32 层。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 |
zskiplist *zslCreate(void)
{
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
} |
2) ZADD myzset 1 “one”
ZADD 命令格式：
ZADD key score member
3) ZADD myzset 3 “three”
4) ZADD myzset 2 “two”
