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 条评论
登录 后参与评论

相关文章

来自专栏java思维导图

Java 10 已发布!时隔 6 月带来 109 项新特性

关键时刻,第一时间送达! 期待已久,没有跳票的 Java 10 已正式发布! ? 为了更快地迭代,以及跟进社区反馈,Java 的版本发布周期变更为了每六个月一次...

2847
来自专栏PHP在线

PHP 底层的运行机制与原理

原文出处: nowamagic 欢迎分享原创到伯乐头条 PHP说简单,但是要精通也不是一件简单的事。我们除了会使用之外,还得知道它底层的工作原理。 PHP是...

3327
来自专栏屈定‘s Blog

设计模式--Builder模式的思考

在日常开发中总是会遇到多参数的情况,那么对于多参数,尤其是可选参数众多的情况,可能有如下的一些解决方案.

1729
来自专栏沈唁志

基于ThinkPHP中App(通信)接口开发封装JSON数据 并读取JSON数据的封装

5942
来自专栏Python

python常用模块

 python常用模块 什么是模块?    常见的场景:一个模块就是一个包含了python定义和声明的文件,文件名就是模块名字加上.py的后缀。    但其实i...

24910
来自专栏鸿的学习笔记

计算机基础小整理

一、CPU 在平时写的程序可以视为数据和指令的组合体,所有的程序都是copy了一份到内存中才能运行,内存地址是指在内存中保存命令和数据的场所,通过地址来标记和指...

802
来自专栏大内老A

WCF技术剖析之十九:深度剖析消息编码(Encoding)实现(上篇)

消息作为WCF进行通信的唯一媒介,最终需要通过写入传输层进行传递。而对消息进行传输的一个前提或者是一项必不可少的工作是对消息进行相应的编码。WCF提供了一系列可...

1826
来自专栏逸鹏说道

ConcurrentDictionary 对决 Dictionary+Locking

在 .NET 4.0 之前,如果我们需要在多线程环境下使用 Dictionary 类,除了自己实现线程同步来保证线程安全之外,我们没有其他选择。 很多开发人员肯...

2917
来自专栏DOTNET

.NET MongoDB Driver 2.2 API注释

主要内容 1 MongoClient   1.1构造函数   1.2 方法 2 IMongoDatabase 3 IMongoCollection 4 IMon...

3516
来自专栏精讲JAVA

JDK 10 的 109 项新特性

虽然感觉 JDK9 发布才仅仅几周的时间,然而,随着新的 OpenJDK 的发布节奏,JDK10 已经到达发布候选里程碑阶段。

1242

扫码关注云+社区