Redis源码解析2
DICT数据结构 Dict其实就是一个hash表,但在Redis中,已经存在一种叫Hash的数据结构,所以,就把Hash表改名成Dict吧。。。 Dict是Redis进行键值处理的灵魂,不管多大的数据量,始终维持O(1)的时间复杂度(排除bucket下链表很长的情况) 全局保存的所有key,
DICT数据结构
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 { *privdata; rehashidx; iterators; } dict;
2. dictht:表示一个独立的dict容器,内部使用,外部程序不建议直接操作该结构
1 typedef struct dictht { unsigned unsigned unsigned } 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 *(*keyDup)(*(*valDup)((*keyCompare)(*key2); (*keyDestructor)((*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; dict *expires; dict *blocking_keys; dict *io_keys; dict *watched_keys; id; } redisDb;
2. 应用级Dict,由metadata数据结构自己维护,主要是一些 set、hash结构中的dict
如下图:
当满足以下条件时,会启动Rehash
1 // 当有效空间使用率 htNeedsResize(dict *dict) { 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%时, _dictExpandIfNeeded(dict *d) 4 { 5 ... ... (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
但别高兴太早,每次只触发一条而已,所以,慢慢来吧~~
由于Dict内部结构的复杂性,虚拟主机,提供一个遍历所有数据的iterator,是非常必要的
Dict提供两种Iterator:
1. dictGetIterator:普通iter,在遍历时不可对dict做更多操作,否则会引起数据遗漏或重复
2. dictGetSafeIterator:安全iter,什么操作都能做,安全的,你懂的。
可以参考上图理解这一点,不再赘述
DictTypedictType 定义了dict的操作行为。Redis预定义了一组dictType,规范各种类型dict的操作
相关代码如下: