Home  >  Article  >  Database  >  Redis源码解析2

Redis源码解析2

WBOY
WBOYOriginal
2016-06-07 17:56:351152browse

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

当满足以下条件时,会启动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
    但别高兴太早,每次只触发一条而已,所以,慢慢来吧~~

    

Iterator

由于Dict内部结构的复杂性,虚拟主机,提供一个遍历所有数据的iterator,是非常必要的

Dict提供两种Iterator:

1. dictGetIterator:普通iter,在遍历时不可对dict做更多操作,否则会引起数据遗漏或重复

2. dictGetSafeIterator:安全iter,什么操作都能做,安全的,你懂的。

可以参考上图理解这一点,不再赘述

DictType

dictType 定义了dict的操作行为。Redis预定义了一组dictType,规范各种类型dict的操作

相关代码如下:

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn