您可以捐助,支持我们的公益事业。

1元 10元 50元





认证码:  验证码,看不清楚?请点击刷新验证码 必填



  求知 文章 文库 Lib 视频 iProcess 课程 角色 咨询 工具 讲座 Modeler   Code  
会员   
 
   
 
  
每天15篇文章
不仅获得谋生技能
更可以追随信仰
 
 
     
   
 订阅
  捐助
edis内部数据结构详解之字典(dict)
 
作者:xkey 来源:CSDN 发布于:2015-04-07
1652 次浏览     评价:      
 

本文所引用的源码全部来自Redis2.8.2版本。

Redis中字典dict数据结构与API相关文件是:dict.h, dict.c。

本文讲解的不是很详细,可以同时参考Redis实现与设计一书中字典部分,本文关于字典的核心代码的注释可以参考。

字典,简单说就是存储key-value键值数据,当然value=NULL那么就是集合了。字典通俗来说就是C++ STL中的map,STL中的map是用red-black tree实现的,因为map不仅能够保证key不重复,而且key还是按照字典序存储的,而Redis中的字典并不要求有序,因此为了降低编码的难度使用哈希表作为字典的底层实现。Redis的字典是使用一个桶bucket,通过对key进行hash得到的索引值index,然后将key-value的数据存在桶的index位置,Redis处理hash碰撞的方式是链表,两个不同的key hash得到相同的索引值,那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候,字典不免会退化成多个链表,效率大大降低,Redis采用rehash的方式对桶进行扩容来解决这种退化。

Redis使用的hash算法有以下两种:

1. MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好,具体信息请参考 MurmurHash 的主页:http://code.google.com/p/smhasher/ 。

2. 基 于 djb 算 法 实 现 的 一 个 大 小 写 无 关 散 列 算 法: 具 体 信 息 请 参 考
http://www.cse.yorku.ca/~oz/hash.html 。

字典数据结构

typedef struct dictEntry {//字典的节点  
void *key;
union {//使用的联合体
void *val;
uint64_t u64;//这两个参数很有用
int64_t s64;
} v;
struct dictEntry *next;//下一个节点指针
} dictEntry;

typedef struct dictType {
unsigned int (*hashFunction)(const void *key); //hash函数指针
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 { //字典hash table
dictEntry **table;//可以看做字典数组,俗称桶bucket
unsigned long size; //指针数组的大小,即桶的层数
unsigned long sizemask;
unsigned long used; //字典中当前的节点数目
} dictht;

typedef struct dict {
dictType *type;
void *privdata; //私有数据
dictht ht[2]; //两个hash table
int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引
int iterators; /* number of iterators currently running */ //当前该字典迭代器个数
} dict;

dict数据结构中声明了两个字典hashtable结构dictht,ht[1]在rehash时候使用,后面具体分析。

下图给出整个字典结构,图片来自Redis设计与实现一书:

上图ht[1]为空,说明当然字典没在Rehash状态。

字典的API函数

创建新字典

通过dictCreate函数创建一个新字典dict *dictCreate(dictType *type, void *privDataPtr),一个空字典的示意图如下(图片来自Redis设计与实现一书):

上面已经提起过,ht[1]只在Rehash时使用。

字典添加元素

根据字典当前的状态,将一个key-value元素添加到字典中可能会引起一系列复制的操作:

如果字典未初始化(即字典的0号哈希表ht[0]的table为空),那么需要调用dictExpand函数对它初始化;

如果插入的元素key已经存在,那么添加元素失败;

如果插入元素时,引起碰撞,需要使用链表来处理碰撞;

如果插入元素时,引起程序满足Rehash的条件时,先调用dictExpand函数扩展哈希表的size,然后准备渐进式Rehash操作。

字典添加元素的流程图,来自Redis设计与实现一书

/* Expand or create the hash table */  
int dictExpand(dict *d, unsigned long size)
{
dictht n; /* the new hash table */
unsigned long realsize = _dictNextPower(size); //得到需要扩展到的size

/* the size is invalid if it is smaller than the number of
* elements already inside the hash table */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;

/* Allocate the new hash table and initialize all pointers to NULL */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize * sizeof(dictEntry*));
n.used = 0;

/* Is this the first initialization? If so it's not really a rehashing
* we just set the first hash table so that it can accept keys. */
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}

/* Prepare a second hash table for incremental rehashing */
//准备渐进式rehash,rehash的字典table为0号
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
if (dictIsRehashing(d)) return DICT_OK;

// 如果哈希表为空,那么将它扩展为初始大小
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

/*如果哈希表的已用节点数 >= 哈希表的大小,并且以下条件任一个为真:
1) dict_can_resize 为真
2) 已用节点数除以哈希表大小之比大于 dict_force_resize_ratio
那么调用 dictExpand 对哈希表进行扩展,扩展的体积至少为已使用节点数的两倍
*/
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}

static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;

/* Expand the hash table if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* Compute the key hash value */
h = dictHashKey(d, key);//通过hash函数得到key所在的bucket索引位置
//查找在现有字典中是否出现了该key
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
//如果系统没在rehash则不需要查找ht[1]
if (!dictIsRehashing(d)) break;
}
return idx;
}

dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d);// 尝试渐进式地 rehash 桶中一组元素

/* Get the index of the new element, or -1 if
* the element already exists. */
// 查找可容纳新元素的索引位置,如果元素已存在, index 为 -1
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;

/* Allocate the memory and store the new entry */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 决定该把新元素放在那个哈希表
entry = zmalloc(sizeof(*entry));
//头插法,插入节点
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;

/* Set the hash entry fields. */
dictSetKey(d, entry, key);//关联起key
return entry;
}

/* Add an element to the target hash table */
//添加一个元素
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key);

if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);//关联起value
return DICT_OK;
}

字典Rehash解析

Rehash的触发机制:当每次添加新元素时,都会对工作哈希表ht[0]进行检查,如果used(哈希表中元素的数目)与size(桶的大小)比率ratio满足以下任一条件,将激活字典的Rehash机制:ratio=used / size, ratio >= 1并且dict_can_resize 为真;ratio 大 于 变 量 dict_force_resize_ratio 。

Rehash执行过程:

创建一个比ht[0].used至少两倍的ht[1].table;将原ht[0].table中所有元素迁移到ht[1].table;清空原来ht[0],将ht[1]替换成ht[0]
渐进式Rehash主要由两个函数来进行:

_dictRehashStep:当对字典进行添加、查找、删除、随机获取元素都会执行一次,其每次在开始Rehash后,将ht[0].table的第一个不为空的索引上的所有节点全部迁移到ht[1].table;

dictRehashMilliseconds:由Redis服务器常规任务程序(serverCron)执行,以毫秒为单位,在一定时间内,以每次执行100步rehash操作。

Rehash操作核心函数:

int dictRehash(dict *d, int n) {  
if (!dictIsRehashing(d)) return 0;

while(n--) {
dictEntry *de, *nextde;

/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {//已经完成
zfree(d->ht[0].table);//释放ht[0].table
d->ht[0] = d->ht[1]; //这里ht[0]与ht[1]都不是指针,直接赋值就替换了
_dictReset(&d->ht[1]);//将ht[1].table设置为null
d->rehashidx = -1;
return 0;
}

/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned)d->rehashidx);
//找到第一个不为空的数组
while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
//指向该链表头
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {//遍历链表
unsigned int h;

nextde = de->next;
/* Get the index in the new hash table */
//得到在ht[1]中的索引号,通过相应的hash函数
h = dictHashKey(d, de->key) & d->ht[1].sizemask;

// 添加节点到 ht[1] ,调整指针,采用的是头插法
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;//设置为空
d->rehashidx++;
}
return 1;
}

小结

Redis中的字典数据结构使用哈希表来实现,用来存储key-value键值元素;

字典使用两个哈希表,一般只使用ht[0],只有当Rehash时候才使用ht[0];

哈希表采用链表的方式解决键碰撞问题;

Redis的Rehash操作是渐进式的,服务器程序会主动Rehash,在查找、添加、删除元素等操作时也会在Rehash进行时执行一次rehash操作。

字典的内容实在太多,操作比较繁琐,应该是Redis中最复杂的底层数据结构了,本文分析的绝对不够深入,希望以后有时间再修改吧,暂时先这样。到目前为止,Redis六种内部数据结构,同时也是底层操作的实现讲解全部结束,后面的文章将进入五种基本数据类型指令的实现,字符串(String)、哈希表(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set)的各种指令的实现。

我自己对Redis2.8.2源码的注释,有时间找个机会放出来。

最后感谢黄健宏(huangz1990)的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。

   
1652 次浏览  评价: 差  订阅 捐助
相关文章

我们该如何设计数据库
数据库设计经验谈
数据库设计过程
数据库编程总结
 
相关文档

数据库性能调优技巧
数据库性能调整
数据库性能优化讲座
数据库系统性能调优系列
相关课程

高性能数据库设计与优化
高级数据库架构师
数据仓库和数据挖掘技术
Hadoop原理、部署与性能调优
 

MySQL索引背后的数据结构
MySQL性能调优与架构设计
SQL Server数据库备份与恢复
让数据库飞起来 10大DB2优化
oracle的临时表空间写满磁盘
数据库的跨平台设计
更多...   


并发、大容量、高性能数据库
高级数据库架构设计师
Hadoop原理与实践
Oracle 数据仓库
数据仓库和数据挖掘
Oracle数据库开发与管理


GE 区块链技术与实现培训
航天科工某子公司 Nodejs高级应用开发
中盛益华 卓越管理者必须具备的五项能力
某信息技术公司 Python培训
某博彩IT系统厂商 易用性测试与评估
中国邮储银行 测试成熟度模型集成(TMMI)
中物院 产品经理与产品管理
更多...   
 
 
 
 
 
每天2个文档/视频
扫描微信二维码订阅
订阅技术月刊
获得每月300个技术资源
 
 

关于我们 | 联系我们 | 京ICP备10020922号 京公海网安备110108001071号