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

相关文章

来自专栏林冠宏的技术文章

Deque的部分成员函数 解析,关于这个类,百度有很多解析,唯独没有其函数介绍

函数 描述 c.assign(beg,end) c.assign(n,elem) 将[beg; end)区间中的数据赋值给c。 ...

1748
来自专栏coderhuo

移位溢出

实际项目中需要计算SD卡中某个目录的大小,并判断该目录所占空间是否超过SD卡总容量的一半。 测试过程中经常发现误报,该目录所占空间远小于SD卡容量一半的时候,...

692
来自专栏Python小白进阶之旅

Python数据类型:双端队列deque-比列表list性能更高的一种数据类型

说到容器类型,大家第一时间想到的多半是list,而list确实也能解决大部分的需要,但碰到列表内的数据量相当大的时候,性能问题就显得尤为重要;再或者列表被恶意注...

1043
来自专栏Java3y

【3y】从零单排学Redis【青铜】

最近在学Redis,我相信只要是接触过Java开发的都会听过Redis这么一个技术。面试也是非常高频的一个知识点,之前一直都是处于了解阶段。秋招过后这段时间是没...

934
来自专栏Python数据科学

如何用Python递归地思考问题?

递归是一个很经典的算法,在实际中应用广泛,也是面试中常常会提到的问题。本文就递归算法介绍如何在Python中实现递归的思想,以及递归在Python中使用时的一些...

1585
来自专栏信安之路

【作者投稿】奇葩webshell技巧

前段时间看XDCTF的一道web题,发现了一种很奇特的构造webshell的方法。

960
来自专栏白驹过隙

Redis - set类型操作

34913
来自专栏Python研发

Memcached·Redis缓存的基本操作

Memcached 是一个高性能的分布式内存对象缓存系统,用于动态Web应用以减轻数据库负载。它通过在内存中缓存数据和对象来减少读取数据库的次数,从而提高动态、...

1174
来自专栏desperate633

深入Redis的List

Redis列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)

893
来自专栏用户2442861的专栏

网易2011笔试题详解

http://blog.csdn.net/silangquan/article/details/18051675

371

扫码关注云+社区