Redis源码解析2

pennate

DICT数据结构
　　（转载请注明出处：http://www.iyunv.com/curve/archive/2012/09/18/2685076.html）
　　Dict其实就是一个hash表，但在Redis中，已经存在一种叫“Hash”的数据结构，所以，就把Hash表改名成Dict吧。。。
Dict是Redis进行键值处理的灵魂，不管多大的数据量，始终维持O(1)的时间复杂度（排除bucket下链表很长的情况）   
全局保存的所有key，都存在于一个Dict中   
而且别的数据结构，比如set、hash也可能会用到Dict
　　Dict实现于 dict.h  dict.c 两个文件中
　　其类型定义如下图：

　　1. dict：表示一个独立的dict结构，提供给外部使用



1 typedef struct dict {
2     dictType *type;  // 定义了元素操作的回调函数
3     void *privdata;
4     dictht ht[2]; // 每个dict有两个dictht结构，一个是主操作对象，一个是辅助操作对象，在Rehash时进行数据转移
5     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
6     int iterators; /* number of iterators currently running */
7 } dict;
　　2. dictht：表示一个独立的dict容器，内部使用，外部程序不建议直接操作该结构



1 typedef struct dictht {
2     dictEntry **table; //容纳entry的二维数组
3     unsigned long size; //bucket的数量（bucket是次于table的一级数组，其下挂载了一个entry链表）
4     unsigned long sizemask; //对hashid进行取模的模数
5     unsigned long used; //该结构中entry的总数量
6 } dictht;
　　3. dictEntry：数据结点，其实就是一个kv键值对，还包含一个next指针



1 typedef struct dictEntry {
2     void *key;
3     void *val;
4     struct dictEntry *next;
5 } dictEntry;
　　4. dictType：定义了一组回调函数，进行数据结点的操作



typedef struct dictType {
unsigned int (*hashFunction)(const void *key);  // 生成hashid
void *(*keyDup)(void *privdata, const void *key); //生成key
void *(*valDup)(void *privdata, const void *obj); //生成val
int (*keyCompare)(void *privdata, const void *key1, const void *key2); //key比较
void (*keyDestructor)(void *privdata, void *key); //销毁key
void (*valDestructor)(void *privdata, void *obj); //销毁val
} dictType;
　　

　　

DICT操作

　　Redis中的dict是一个标准的 “bucket + 开链” 的哈希表
并未进行更复杂的处理
包括防止哈希冲突导致开链过长的问题，也没有考虑
如果精心构造一串key来打redis，很容易打死的
所以，企业级应用的同学们，如果你的Redis服务对用户比较Open，别下个源码就用了，还是动手改改HashFunction再用吧！
　　
　　Redis用两个dictht结构，作用是为了能够渐进地导数据，防止Rehash时阻塞时间太长
这种做法在memcache中就已经用了，不过memcache中是开辟一个线程专门做rehash而已
相比之下，不开线程的处理方式不用锁，BUG更少一些
　　

命名空间
　　Redis中的Dict分为两类：
　　1. 系统级Dict，具有全局的命名空间，其定义如下：



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;
　　2. 应用级Dict，由metadata数据结构自己维护，主要是一些 set、hash结构中的dict
　　如下图：


Rehash
　　当满足以下条件时，会启动Rehash



1 // 当有效空间使用率 < 10%时，
2 // 该函数返回true，进行空间回收
3 int htNeedsResize(dict *dict) {
4     long long size, used;
5
6     size = dictSlots(dict);
7     used = dictSize(dict);
8     return (size && used && size > DICT_HT_INITIAL_SIZE &&
9             (used*100/size < REDIS_HT_MINFILL));
10 }
　　



1 // 当有效空间使用率 > 100%时，
2 // 该函数返回OK，进行dict扩容
3 static int _dictExpandIfNeeded(dict *d)
4 {
5     ... ...
6
7     if (d->ht[0].used >= d->ht[0].size &&
8         (dict_can_resize ||
9          d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
10     {
11         return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
12                                     d->ht[0].size : d->ht[0].used)*2);
13     }
14     return DICT_OK;
15 }
　　
　　Rehash启动后，就要开始进行Rehash操作了
但是，Rehash的代价是很大的，特别是当容量超过千万级以后，往往会耗费数十秒来进行操作（视机器性能）
所以，Redis采用了渐进式的Rehash，把操作分片，一步步来，总不能阻塞用户响应吧
　　根据Dict的类型不同，会采用不同的Rehash策略：
1. 全局性的DICT结构（就是全局命名空间中的key），会周期性的进行rehash，每次进行 1ms
    而且，不受稍后提到的 SafeIterator的干扰，可以一直执行（但是，不受干扰是一回事，在iterator循环空间中，还是得用Safe模式的，所以，源码中也会看到大量针对全局dict的SafeIterator，这一点需要理解一下）
    毕竟，全局的，是重要的嘛，挤也要挤出1ms来，用吧！而且还甭想打扰它，别不服气了
　　2. 应用级DICT结构（就是用户自定义的一些DICT），Redis会采取一种 Lazy Rehash 的策略
    所谓 Lazy Rehash，就是用得越多，处理得越快；用得越少，处理得越慢
    什么叫“用”呢？
    很好理解，“增删查”操作都叫用，源码里对应：dictAdd、dictGenericDelete、dictFind、dictGetRandomKey操作，都会促发_dictRehashStep函数进行Rehashing
    但别高兴太早，每次只触发一条而已，所以，慢慢来吧~~
　　


Iterator
　　由于Dict内部结构的复杂性，提供一个遍历所有数据的iterator，是非常必要的
　　Dict提供两种Iterator:
　　1. dictGetIterator：普通iter，在遍历时不可对dict做更多操作，否则会引起数据遗漏或重复
　　2. dictGetSafeIterator：安全iter，什么操作都能做，安全的，你懂的。
　　可以参考上图理解这一点，不再赘述

DictType
　　dictType 定义了dict的操作行为。Redis预定义了一组dictType，规范各种类型dict的操作
　　相关代码如下：



1 /* set集合 */
2 dictType setDictType = {
3     dictEncObjHash,            /* hash function */
4     NULL,                      /* key dup */
5     NULL,                      /* val dup */
6     dictEncObjKeyCompare,      /* key compare */
7     dictRedisObjectDestructor, /* key destructor */
8     NULL                       /* val destructor */
9 };
10
11 /* zset集合 */
12 dictType zsetDictType = {
13     dictEncObjHash,            /* hash function */
14     NULL,                      /* key dup */
15     NULL,                      /* val dup */
16     dictEncObjKeyCompare,      /* key compare */
17     dictRedisObjectDestructor, /* key destructor */
18     NULL                       /* val destructor */
19 };
20
21 /* 全局key存储空间 */
22 dictType dbDictType = {
23     dictSdsHash,                /* hash function */
24     NULL,                       /* key dup */
25     NULL,                       /* val dup */
26     dictSdsKeyCompare,          /* key compare */
27     dictSdsDestructor,          /* key destructor */
28     dictRedisObjectDestructor   /* val destructor */
29 };
30
31 /* 全局过期对象存储空间 */
32 dictType keyptrDictType = {
33     dictSdsHash,               /* hash function */
34     NULL,                      /* key dup */
35     NULL,                      /* val dup */
36     dictSdsKeyCompare,         /* key compare */
37     NULL,                      /* key destructor */
38     NULL                       /* val destructor */
39 };
40
41 /* 命令对象 */
42 dictType commandTableDictType = {
43     dictSdsCaseHash,           // 命令是大小写不敏感的
44     NULL,                      /* key dup */
45     NULL,                      /* val dup */
46     dictSdsKeyCaseCompare,     // 命令是大小写不敏感的
47     dictSdsDestructor,         /* key destructor */
48     NULL                       /* val destructor */
49 };
50
51 /* hash结构 */
52 dictType hashDictType = {
53     dictEncObjHash,             /* hash function */
54     NULL,                       /* key dup */
55     NULL,                       /* val dup */
56     dictEncObjKeyCompare,       /* key compare */
57     dictRedisObjectDestructor,  /* key destructor */
58     dictRedisObjectDestructor   /* val destructor */
59 };
60
61 /* val为链表的dict结构
62    主要是 expire、watch、pubsub 等功能会用到*/
63 dictType keylistDictType = {
64     dictObjHash,                /* hash function */
65     NULL,                       /* key dup */
66     NULL,                       /* val dup */
67     dictObjKeyCompare,          /* key compare */
68     dictRedisObjectDestructor,  /* key destructor */
69     dictListDestructor          /* val destructor */
70 };