redis数据结构存储Dict设计细节（redis的设计与实现笔记）

时间：2021-12-28 20:34:36

说到redis的Dict(字典)，虽说算法上跟市面上一般的Dict实现没有什么区别，但是redis的Dict有2个特殊的地方那就是它的rehash（重新散列）和它的字典节点单向链表。

以下是dict用到的结构：

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[];   //两个hash table

    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引

    int iterators; /* number of iterators currently running */ //当前该字典迭代器个数

} dict;   

由于楼主算法能力有限：所以对哈希算法没有太深的了解，所以在这里算法就不详写了，大家有兴趣可以百度。

当运用哈希算法计算出 k0的索引 ，redis就会插入到指定的位置

redis数据结构存储Dict设计细节（redis的设计与实现笔记）

当k2和k1出现计算出键索引相同的情况下，这时候redis的dictEntry(字典节点)有一个next属性（单项链表），redis会把冲突键索引的元素排到后插入数据的前面，从而解决了这个问题

redis数据结构存储Dict设计细节（redis的设计与实现笔记）

现在如果在插入2条元素，此时数据量已经超过dict的负载了，redis就会启用rehash，虽然是rehash操作但是redis是采用了渐进式操作，并不是一下子内存不够用了 就直接操作内存，然后全部转移数据，这样会导致操作很耗时，redis考虑到了这一点，然后

先把ht[1]另一张dict结构中扩容一个数量为ht[0].used*2的dictEntry数组，然后把2条数据通过哈希算法加入到这个数组中。

redis数据结构存储Dict设计细节（redis的设计与实现笔记）

然后把上面的元素一个个异步渐渐移动到下面的数组中，在这个过程中如果客户端去操作元素时，如果在ht[0]中检查找不到建，就会去检查ht[1]中是否有指定的键，从而不影响数据的使用，而且可以避免一次性操作rehash带来的耗时问题，最后reshash完成了，就直接把ht[1]和ht[0]切换位置并且清空弃用的哈希节点数组，从而完成所有操作。

redis数据结构存储Dict设计细节（redis的设计与实现笔记）

redis数据结构存储Dict设计细节（redis的设计与实现笔记）

随机推荐

  1. Ubuntu（基于Ubuntu）中常用的apt和dpkt命令

    apt-get sudo apt-get install package 安装包   sudo apt-get -f install 修复安装”-f = ——fix-missing”   sudo a ...

  2. 在Linux下禁用IPv6的方法小结

    在Linux下禁用IPv6的方法小结--http://www.jb51.net/LINUXjishu/335724.html 这篇文章主要介绍了在Linux下禁用IPv6的方法小结,禁用IPv6的操作 ...

  3. 1.本周的作业请参照此文：http://www.ruanyifeng.com/blog/2015/12/git-workflow.html 制定本组项目的GitHub版本更新流程---答题者：徐潇瑞

    首先,介绍一下gitflow,它是最早诞生.并得到广泛采用的一种工作流程.如果采用git flow开发流程,那么项目存在两个常设分支,一个叫主分支master,另一个叫开发分支develop.mast ...

  4. ecshop修改后台访问地址

    本文转自‘做个好男人’的博客. 打开data/config.php,找到define(’ADMIN_PATH’,’admin’),这里是定义后台目录的地方,把其中的admin换成你的后台自定义目录,如 ...

  5. linux keepalived+LVS 实现mysql 从库负载均衡

    前情提要: 参考链接: http://www.osyunwei.com/archives/7464.html ps:以上为本次操作的主要参考资料,非常感谢此文作者的贡献,我的随笔的主要目的是 说明在使 ...

  6. Zabbix_server.conf 的性能调优

    Zabbix安装完成后,模板里面有一个Template App Zabbix Server,添加到zabbix服务器里. 过个一两天,查看以下的图表(在Graphs里面). Zabbix cache ...

  7. JS之跨域

    今天学了跨域,迫不及待想跟大家分享!不妥之处希望大家指正. 首先来明确一下"跨域"这个概念. 跨域指的是,到外域去取数据.那什么是"外域"呢?我们先来了解同域. ...

  8. Result consisted of more than one row 错误的解决

    创建MySql的存储过程时,发生“Result consisted of more than one row”的错误. 存储过程的代码如下: )) BEGIN SELECT PetName into ...

  9. OpenWrt opkg 在线源默认配置

    dest root /dest ram /tmplists_dir ext /var/opkg-listsoption overlay_root /overlaysrc/gz barrier_brea ...

  10. Linux 程序启停脚本

    start.sh #!/bin/sh java -jar ./program.jar & echo $! > /var/run/program.pid stop.sh #!/bin/sh ...

相关文章