redis 字典的实现

作者:张鹏

最近研究了一下redis里面字典的实现,redis作为高效的内存存储而被广泛使用,内部实现的db结构以及多种高效的数据结构,其底层基本上就是靠字典来实现。而其字典数据结构是基于哈希表来实现的,其中一些特性的实现十分精妙。

1.数据结构

节点数据结构

因为是基于开链法的哈希表实现,所以需要维护了一个next节点

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

哈希表数据结构

其中size是当前哈希表的大小,used是当前使用的大小,size会根据当前used的大小来做相应的调整,调整的过程就是字典动态扩容的过程,具体过程下面会描述。sizemask=size-1,是用来做掩码的,哈希算法算出的index,通过index&sizemask操作来代替除留余数,这么做的原因是&操作比%更快。

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

字典数据结构

type是函数指针类型,封装了哈希函数,key比较函数,释放内存函数等等。一个高效的哈希函数能保证哈希的结果尽量均匀分布,redis中的字符串哈希算法便是著名的开源算法MurmurHash2,但是因为上层的有不同的数据结构,所以实现了不同的哈希函数。字典中维护两张哈希表,主要是用来做动态rehash的,rehashidx便是两张表动态rehash的索引。iterators是当前迭代器的个数,具体后面会详细介绍。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

字典定义整体的结构图如下:

2.特性介绍

redis的字典实现了很多特别的东西,花式造轮子的根本原因还是从时间与空间上做考量。

动态扩容/缩容

redis的数据都是放在第一张哈希表中ht[0]中的,所谓的动态扩容就是说ht[0]那张哈希表快不够用的时候,目前是used/size > 5的时候,使用ht[1]来扩大哈希表的容量。这其中有两种方式,一种是redis提供了显示的扩容的接口dictExpand,供外部调用,另外一种是在添加数据的时候调用_dictExpandIfNeeded,以此来判断是否需要扩容。缩容就是当前哈希表使用率 used/size 低于某个值时,目前这个值是10%,利用ht[1]缩小哈希表的容量。扩容和缩容的操作就是rehash的过程。

rehash+渐进式

rehash就是将第一张ht[0]的数据迁移到ht[1]的过程,rehash实现了两种策略,一种是在定时器的每个tick里面,执行databasesCron操作的时候,还有一种是在增加查找删除等字典操作的时候执行,这样的过程可以保证rehash的时候不会阻塞redis服务器,对用户来说,也是无感知的。rehash的过程中维护了一个索引,就是上面介绍的字典结构中的rehashidx,使用这个索引遍历ht[0],将数据无缝迁移到ht[1]。因为在rehash中的任何时刻,一个节点只能存在其中一张哈希表中,所以每次操作都需要处理两张表。

迭代器

redis里面的字典实现了两种迭代器,一种是安全的迭代器,一种是普通的迭代器。所谓安全就是指在迭代的过程中可以执行添加查找等操作,非安全的迭代器就是只能执行迭代操作。其实本质上就是安全的迭代器会给dict设置iterators++(dict里面的变量),这样字典的各种操作就不会执行rehash操作,如果在迭代的过程中执行了rehash,迭代索引就会错乱。

3.接口介绍

dict *dictCreate(dictType *type, void *privDataPtr);

创建字典,目前redis中用到字典的地方有很多,包括全量的key,超时的key等等db中的kv, 命令回调表,hash结构,set结构,sortset结构等等。

int dictAdd(dict *d, void *key, void *val);

添加数据,前面说到会执行rehash操作,并且如果字典底层正在rehash,索引的计算会读取两张表来判断,并且数据只会添加到第二张表里面。

dictEntry *dictFind(dict *d, const void *key)

查找数据,和添加数据很类似,唯一的区别是查找数据的时候不会计算是否需要扩容。

int dictDelete(dict *d, const void *key);

删除数据,和添加数据的过程类似,但是在删除数据的过程中不做缩容操作,缩容是上层负责主动调用缩容接口htNeedsResize和dictResize。

dictEntry *dictNext(dictIterator *iter)

迭代字典,搭配dictGetIterator或者dictGetSafeIterator操作,前面有说到安全迭代器和非安全迭代器的区别,非安全的迭代器在初次迭代的时候会计算一个哈希值,释放迭代器的时候assert这个哈希值是否被改变了。

总结

redis字典的实现有很多有趣的特性,包括动态扩容缩容,渐进式rehash等,所有这些特性的出发点都是基于充分使用内存的角度去考虑。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏gaoqin31

设计模式之 UML

今年接手的一个计费项目让我痛苦不堪,里面到处充斥着重复冗余的代码,一个简单的需求往往需要改n个地方,而且很多改动牵一发动全身,这个项目涉及到支付,出问题就是损失...

572
来自专栏Android机动车

Socket TCP协议 实时通信的粘包处理之Java与C++实现

详细内容请阅读 http://blog.csdn.net/zhangxinrun/article/details/6721495

912
来自专栏有趣的django

PYTHON面试

大部分的面试问题,有最近要找事的老铁吗?  python语法以及其他基础部分 可变与不可变类型;  浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来...

3957
来自专栏恰同学骚年

《代码的未来》读书笔记:内存管理与GC那点事儿

  近年来,我们的电脑内存都有好几个GB,也许你的电脑是4G,他的电脑是8G,公司服务器内存是32G或者64G。但是,无论内存容量有多大,总归不是无限的。实际上...

531
来自专栏有趣的django

python开发面试问题

python语法以及其他基础部分 可变与不可变类型;  浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来设计,如何实现;  __new__() 与 __...

4108
来自专栏知识分享

关于原子哥ENC28J60网络通信模块接收数据代码的一点疑惑

---恢复内容开始--- 这几天做STM32的ENC28J60网络通信模块,自己在原子哥的代码上进行修改测试,,发现一个问题,电脑和板子进行通信的时候总隔一段时...

3418
来自专栏二进制文集

Java 与 C/C++ 的编译器对比

这两天重温了周志明的《深入理解Java虚拟机》第2版,发现第11章第4节关于 Java 编译器的内容写得太棒了~本文完全摘自《深入理解Java虚拟机》第2版 0...

686
来自专栏决胜机器学习

设计模式专题(二)——策略模式

设计模式专题(二)——策略模式 (原创内容,转载请注明来源,谢谢) 一、概述 1、含义 策略模式(Strategy)是一种定义了各类算法的模式,其将各种算法...

3258
来自专栏张善友的专栏

Redis应用场景

Redis开创了一种新的数据存储思路,使用Redis,我们不用在面对功能单调的数据库时,把精力放在如何把大象放进冰箱这样的问题上,而是利用Redis灵活多变的数...

2016
来自专栏一名合格java开发的自我修养

Java IO 装饰者模式

  装饰模式以对客户端透明的方式动态地给一个对象附加上更多的责任。换言之,客户端并不会觉得对象在装饰前和装饰后有什么不同。

712

扫码关注云+社区