Redis源码学习之字典

  • 字典在Redis中的应用场景

字典在Redis中可以说无处不在,核心主要是以下两个

1.Redis数据库

2.Redis哈希对象的底层实现之一

  • 字典数据结构

1.字典结构体

//字典
type dict struct {
	//字典类型函数
	dType *dictType
	//私有数据
	privateData interface{}
	//两张哈希表,用于渐进式rehash
	ht [2]*dictht
	//rehash索引,-1代表没有执行rehash
	rehashidx int32
	//目前正在运行的安全迭代器的数量
	iterators uint32
}

在字典结构体中,包含了一组字典函数(dictType),通过封装的方法处理对应的操作,通常在字典初始化的时候对其进行配置。

//字典类型特定函数
type dictType struct {
	//计算哈希值的函数
	hashFunction func(key interface{}) uint32
	//复制键的函数
	keyDup func(privateData, key interface{}) interface{}
	//复制值的函数
	valDup func(privateData, key interface{}) interface{}
	//对比键的函数
	keyCompare func(privateData, key1, key2 interface{}) bool
	//释放键的函数
	keyDestructor func(privateData, key interface{})
	//释放值的函数
	valDestructor func(privateData, key interface{})
}

例如,计算某个key的哈希值时,就需要调用hashFunction,可见这个方法是必须配置的。在Redis中使用的是MurmurHash2算法。

//计算哈希值
func (d *dict) HashKey(key interface{}) uint32 {
	return d.dType.hashFunction(key)
}

除了一组函数之外,还可以配置字典的私有数据,透传到配置函数中进行逻辑计算。

字典还包括两张哈希表,以固定长度数组的形式保存(ht字段),这里为什么是两张哈希表,我们在【渐进式Rehash】中会说道,对应的哈希表结构体如下图所示:

//哈希表
type dictht struct {
	//哈希表桶数组
	table []*dictEntry
	//哈希表中桶的个数
	size uint32
	//哈希表桶个数掩码,用于计算桶的索引号,总是等于size-1
	sizemask uint32
	//哈希表已有节点数量
	used uint32
}

从代码中可以看到,哈希表的table字段是一个键值对(*dictEntry)类型的slice,相当于一张哈希表包含若干个桶;size字段就代表桶的个数;sizemask等于size-1,表示桶个数掩码,与上文中计算的哈希值可以计算出某个key所属桶的索引号;used字段表示目前哈希表已有节点个数,即使是所有桶都有数据,used和size的值也是大概率不相等的,后文会解释原因。

在最底层就是键值对了,结构体如下图所示:

//键值对节点
type dictEntry struct {
	//键
	key interface{}
	//值
	value interface{}
	//指向下个哈希表节点,形成单链表
	next *dictEntry
}

结构很简单,key和value分别代表键和值,使用接口类型也可以体现其多态性。next字段指向下一个键值对节点,从而每个桶中存放的就是一个键值对类型的单链表了,这里也就说明了Redis处理键冲突的方法是使用【链地址法】,同时这也可以回答上文中used和size值大概率不相等的问题了。

最终,Redis字典的整体结构我们就有了整体概貌了,如下图所示,即dict>dictht>dictEntry。

我们再画的简单直白一点:

  • 字典操作

1.渐进式Rehash

首先,什么是Rehash?Rehash顾名思义,就是重新计算原有key的哈希值,重新将其分配到对应的桶里。那么为什么要做Rehash?主要是因为随着对于某个字典的不断操作,键值对的数量逐步的增多或者减少,使得哈希表的负载因子主键的偏离最优范围,导致哈希表性能降低,所以为了使哈希表的负载因子能够维持在一个合理范围,就需要Rehash了。

那么,Rehash就Rehash好了,为什么还要叫【渐进式】呢?这就是Redis设计的哈希表的核心所在了,Redis由于单线程的模型,不会因为某张哈希表负载因子偏离正常范围而一次性把整张哈希表进行Rehash操作,因为这样会阻塞住其他操作,导致这一段时间内服务不可用,所以采用了所谓的【渐进式】Rehash,也就是在对某张需要Rehash的字典执行某些操作的时候,以桶为单位逐步进行Rehash,直到所有的桶都执行完成来结束这次Rehash行为。

现在我们就可以解释前文中提到的dict结构中为什么有固定长度为2的哈希表数组了,我们将其称为【0号哈希表】和【1号哈希表】,在没有进行Rehash行为时,只有0号哈希表有键值对节点,而1号哈希表是空的,而一旦开始Rehash行为,0号哈希表和1号哈希表都会有节点,其中1号哈希表就是根据0号哈希表的节点个数创建出来的新的哈希表,来保证负载因子合理。当完成Rehash的时候,0号哈希表是空的,1号哈希表包含了所有的键值对,最终再把1号哈希表rename成0号哈希表,1号哈希表置空,恢复到未Rehash的状态,来准备下一次的Rehash。说了这么多,我感觉不如一张状态转移图来的实在:

此外,Redis还对Rehash的时机进行了定义:

1.在扩容层面上,常规情况下,Redis认为哈希表节点数量与哈希表节点桶的个数应该是1:1的关系,一旦0号哈希表used/size>1,则需要进行Rehash扩容;此外还有一种特殊情况,就是redis在fork出子进程执行持久化等操作时,Redis会提高哈希因子触发Rehash的门槛,即used/size>5的时候才会进行,这是因为现代操作系统对于fork系统调用都会使用COW(写时复制)技术进行优化,因此在此时进行Rehash就会增加整个系统的负担,得不偿失。

2.在缩容层面上,当used/size<0.1时就会被触发。

说了这么多,上个Rehash的底层代码:

//按步长进行rehash,以桶为单位,每一步都迁移某个桶里的所有哈希节点
//返回1表示rehash未完成
//返回0表示已经完成或者不在rehash进行中
func (d *dict) Rehash(step uint32) int {
	//不在rehash执行中直接返回
	if !d.IsReHashing() {
		return 0
	}

	//按步长进行迁移
	for ; step > 0; step-- {
		//首先判断0号哈希表是否还有已使用的桶,没有的话证明rehash完毕
		if d.ht[0].used == 0 {
			//永远以0号哈希表作为标准表
			d.ht[0] = d.ht[1]
			//初始化1号哈希表,用作下一次rehash
			d.ht[1].reset()
			//设置rehash表示为-1表示未执行rehash
			d.rehashidx = -1
			return 1
		}

		//如果0号哈希表的rehash索引大于表长度,说明有问题
		if d.ht[0].size < uint32(d.rehashidx) {
			d.rehashidx = 0
			return 0
		}

		//rehash没有完毕,则按rehashidx的值遍历0号哈希表中的桶
		//找到下一个不为空的桶
		for ; d.ht[0].table[d.rehashidx] == nil; d.rehashidx++ {
		}
		//获取桶里面的第一个节点
		for de := d.ht[0].table[d.rehashidx]; de != nil; {
			//需要把0号哈希表de的next节点临时保存下来
			oldNextDe := de.next
			//计算hash索引
			index := d.HashKey(de.key) & d.ht[1].sizemask
			//插入到1号哈希表的index号桶的表头
			de.next = d.ht[1].table[index]
			d.ht[1].table[index] = de
			//维护两张表的used字段
			d.ht[0].used--
			d.ht[1].used++
			//de设置为0号表的next节点
			de = oldNextDe
		}

		//将0号哈希表已迁移的桶置空
		d.ht[0].table[d.rehashidx] = nil
		//更新rehashidx,指向下一个桶
		d.rehashidx++
	}

	//走到这里证明还没有rehash完成
	return 0
}

说完渐进式Rehash,实际上整个字典最核心的地方就完事了,剩下的操作都不是很复杂了。

2.添加键值对节点

添加键值对的时候,如果字典正在进行Rehash中,则会进行单步Rehash。然后会判断添加的键值对的key是否在字典中存在,如果存在则返回错误;如果不存在就通过哈希算法和桶掩码计算出这个键值对所属的桶,并将其添加到这个桶存放的键值对链表的表头。这里需要注意的是,我们需要判断当前字典是否正在进行Rehash,如果是的话,则新的键值对会被放到1号哈希表(即扩容或缩容后的哈希表)。

/*
 * 尝试将给定键值对添加到字典中
 * 最坏 T = O(N) ,平均 O(1)
 */
func (d *dict) Add(key, value interface{}) int {
	//判断key是否已经存在
	de := d.AddRaw(key)

	//如果存在则返回DICT_ERR
	if nil == de {
		return DICT_ERR
	}

	//设置值
	d.setVal(de, value)

	return DICT_OK
}

/*
 * 尝试将键插入到字典中
 * 如果键已经在字典存在,那么返回nil
 * 如果键不存在,那么程序创建新的哈希节点,
 * 将节点和键关联,并插入到字典,然后返回节点本身。
 * T = O(N)
 */
func (d *dict) AddRaw(key interface{}) *dictEntry {
	//如果字典正在rehash进程中
	//则执行单步rehash
	if d.IsReHashing() {
		d.rehashStep()
	}

	//键存在则直接返回
	if _, isExist := d.keyIndex(key); isExist {
		return nil
	}

	//为该节点分配空间
	de := &dictEntry{}
	d.setKey(de, key)

	//如果在rehash进程中,则插入1号表,否则插入0号表
	var ht *dictht
	if d.IsReHashing() {
		ht = d.ht[1]
	} else {
		ht = d.ht[0]
	}
	//计算桶的索引
	idx := d.HashKey(key) & ht.sizemask
	//插入到该桶的头部
	de.next = ht.table[idx]
	ht.table[idx] = de
	//更新节点数
	ht.used++

	return de
}

3.通过key查找某个键值对

查找某个键值对也会触发单步Rehash。然后会计算出这个key的哈希值,然后再字典中通过key比对函数进行查找,这里需要特别指出的是,只有在字典在0号表中没有找到并且字典正在Rehash中的时候,才会去1号表找这个键值对,这也体现出了0号表永远作为标准表的地位和Redis对于性能要求上的优雅与极致。

/*
 * 通过key查找entry
 */
func (d *dict) Find(key interface{}) *dictEntry {
	//未初始化的字典直接返回
	if d.ht[0].size == 0 {
		return nil
	}

	//如果允许的话,执行单步rehash
	if d.IsReHashing() {
		d.rehashStep()
	}

	//计算key对应的哈希值
	h := d.HashKey(key)

	//返回的entry
	var de *dictEntry = nil

	//在哈希表中进行查找
	for tableNum := 0; tableNum <= 1; tableNum++ {
		//计算索引值
		idx := h & d.ht[tableNum].sizemask
		//在idx这个桶中查找
		for current := d.ht[tableNum].table[idx]; nil != current; current = current.next {
			if d.CompareKeys(current.key, key) {
				de = current
				break
			}
		}

		//如果没有在rehash进程中,则无需查找1号哈希表
		if !d.IsReHashing() {
			break
		}
	}

	return de
}

4.修改某个key对应的value

相对来说比较简单,Redis首先通过Add方法尝试新添加一个节点,如果加不进去则证明key已经存在,则直接用新值覆盖原值即可。这里需要注意,源码中还专门对于value做了释放内存的操作,体现了Redis对于内存管理的精细化。

/*
 * 用新值替换key的原值
 * 如果key是新的,则返回1
 * 如果key是旧的,则返回0
 */
func (d *dict) Replace(key, value interface{}) int {
	//先尝试添加一个节点进去
	if d.Add(key, value) == DICT_OK {
		return 1
	}

	//如果节点存在,找到这个节点
	de := d.Find(key)
	//新值覆盖原值
	d.setVal(de, value)
	return 0
}

5.删除某个key

有了上面的经验,详细删除操作已经难不倒你了。需要指出的是,删除操作也会触发单步Rehash。

/*
 * 根据key删除节点
 */
func (d *dict) genericDelete(key interface{}, nofree bool) int {
	//如果字典还没有初始化,直接返回
	if d.ht[0].size == 0 {
		return DICT_ERR
	}

	//如果条件允许,执行单步rehash
	if d.IsReHashing() {
		d.rehashStep()
	}

	//通过key计算哈希值
	h := d.HashKey(key)

	//在表中进行查找
	for tableNum := 0; tableNum <= 1; tableNum++ {
		//计算桶的idx
		idx := h & d.ht[tableNum].sizemask
		//在该桶中进行查找
		var pre *dictEntry = nil
		var current = d.ht[tableNum].table[idx]
		for nil != current {
			if d.CompareKeys(current.key, key) { //found
				if pre == nil { //删除的是该桶的头节点
					d.ht[tableNum].table[idx] = current.next
				} else {
					pre.next = current.next
				}

				//释放删除节点的内存空间
				if !nofree {
					d.freeKey(current)
					d.freeVal(current)
				}
				current = nil

				//更新现有节点数
				d.ht[tableNum].used--

				return DICT_OK
			}
			//节点前进
			pre = current
			current = current.next
		}

		//只有在rehash中,才有必要查1号哈希表
		if !d.IsReHashing() {
			break
		}
	}

	//没找到该节点
	return DICT_ERR
}
  • 综述

通过对于Redis字典的源码学习,进一步对于Redis有了深刻的认识,佩服与作者编码功底的同时,也感慨其对于性能要求的极致。字典的核心在于渐进式Rehash,Redis通过以平摊复杂度的思想(实际上是一种分治思想)找到了属于自己的Rehash策略。此外,源码中还有着各种面向对象思想的体现,着实值得一读再读!

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏申龙斌的程序人生

Eclipse油藏模型解析程序

2010年的时候,三维可视化项目中要读取eclipse建模软件产生的三维模型网格数据,经过连续多天的奋战,终于搞明白eclipse数模软件输出的egrid、in...

3097
来自专栏李海辰的专栏

Unity引擎资源管理代码分析 ( 2 )

上一篇《Unity 引擎资源管理代码分析 ( 1 ) 》讲解了 Unity 引擎资源管理代码的类型设计架构和 Resources.Load 接口的实现,本文将...

7944
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.7节C风格数据结构内存布局之结构体数组

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

771
来自专栏SDNLAB

Open vSwitch系列之数据结构解析深入分析ofpbuf

上一篇我们分析了hmap,hamp可以说是Open vSwitch中基石结构,很多Open vSwitch中数据结构都依赖hmap。本篇我们来分析一下ofpbu...

3788
来自专栏对角另一面

lodash源码分析之数组的差集

本文为读 lodash 源码的第十七篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

1244
来自专栏祥子的故事

Python编程快速上手 让繁琐工作自动化 | 第三章 :实践项目

3096
来自专栏数据结构与算法

P1965 转圈游戏

题目描述 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 ...

3648
来自专栏开发与安全

从零开始学C++之虚继承和虚函数对C++对象内存模型造成的影响(类/对象的大小)

首先重新回顾一下关于类/对象大小的计算原则: 类大小计算遵循结构体对齐原则 第一个数据成员放在offset为0的位置 其它成员对齐至min(sizeof(me...

2230
来自专栏犀利豆的技术空间

Redis 的基础数据结构(二) 整数集合、跳跃表、压缩列表

上篇文章写了 Redis 基础数据结构的可变字符串、链表、字典。大家可以点击链接查看。今天我们继续研究 Redis 的基础数据结构。

983
来自专栏Java后端技术栈

8 张图理解 Java

一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

691

扫码关注云+社区

领取腾讯云代金券