Redis 源码分析(3) - 数据结构篇之字典1

在 Redis3.0 中 dict 被称为字典，是用来保存键值对的抽象结构，dict.c 源码中第一行注释写的 Hash Tables Implementation (哈希表实现) ，底层是基于数组与链表的结合方式来实现，并且做了一层封装，阅读全文大体用时3分钟。

基本原理

我们先看下 Redis 字典实现全貌，画了一张图供参考，避免一上来陷入到细节中去

源码实现

我们可以先看下源码实现，如上图所示，外层是字典结构体，它对散列表结构做了一层封装。

dictType 它是判断存储的类型，是指向的是 dictType 结构体【哈希表节点】后面会详细解析 dictType

privdata 记录的是字典需要依赖的数据

iterators 记录的是当前运行的迭代器数量

dictht ht[2] 表示结构体为 2 请大家注意在做初始化阶段会一起初始化两个哈希表，这是用来做 rehash的时候用到的可以做数据重新整理，跟 JVM S0 和 S1 做数据整理的实现思路很相近，我们可以先看下源码实现

typedef struct dict {


   // 类型特定函数
   dictType *type;


   // 私有数据
   void *privdata;


   // 哈希表
   dictht ht[2];


   // rehash 索引
   // 当 rehash 不在进行时，值为 -1
   int rehashidx; /* rehashing not in progress if rehashidx == -1 */


   // 目前正在运行的安全迭代器的数量
   int iterators; /* number of iterators currently running */


} dict;

看 dictht ht[2] 结构体初始化源码实现如下

int _dictInit(dict *d, dictType *type,
       void *privDataPtr)
{
   // 初始化两个哈希表的各项属性值
   // 但暂时还不分配内存给哈希表数组
   _dictReset(&d->ht[0]);
   _dictReset(&d->ht[1]);
...
}

扩展知识

任何内存管理系统要考虑3种问题，在1960年 McCarthy 已经把此问题提出来并分享总结成方法论如下3条，

1）为新对象分配空间

2）确实存活对象

3）回收死亡对象所占用的空间

dictht ht[2];

扩展知识点：后期会讲到，真正的内存分配通常还会考虑到的一些细节维度

字节对齐、空间大小限制、边界标签、堆可解析性、局部性、扩展块保护、跨越映射等，后期将逐一介绍给大家，【欢迎订阅我们的架构日记看源码不迷路 ^-^】

哈希表实现

Redis 所使用的哈希表是由 dict.h 和 dict.c 中定义的，每个字典有两个哈希表，从而实现渐进式 rehash， dict 下一层 dictht的结构图如下

如上图所示，size 表示哈希表大小就是 table 的总大小，table 表示哈希表数组，用于存键值对，used表示已存在的节点数量

对照的源码如下

/*
* 哈希表
*
* 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
*/
typedef struct dictht {
   
   // 哈希表数组
   dictEntry **table;


   // 哈希表大小
   unsigned long size;
   
   // 哈希表大小掩码，用于计算索引值
   unsigned long sizemask;


   // 该哈希表已有节点的数量
   unsigned long used;


} dictht

链表实现

dictht 下一层 dictEntry 的结构图如下

如上图所示，key 存储的键，union为联合，struct dictEntry *next表示指向下一个 哈希表节点，void *val表示值，uint64_t u64表示值是什么的类型的二进制文件，int64_t s64 表示时间

在字典中每个 key 都是独一无二的，通过 key 可以找到对应的值，让我们先来看下实现 ，uint64_t u64 可以存储二进制文件,换句话说，可以存储 String、Hash、List、Set

例如 0b0000000000000000000000000000000000000000000000000000000000000001

源码如下如示

/*
* 哈希表节点
*/
typedef struct dictEntry {
   
   // 键
   void *key;


   // 值
   union {
       void *val;
       uint64_t u64;
       int64_t s64;
  } v;


   // 指向下个哈希表节点，形成链表
   struct dictEntry *next;


} dictEntry;

篇幅原因下篇会继续介绍字典的基本操作实现原理，例如：源码中字典如何初始化、添加元素、查找、修改、删除、字典空间扩容及空间重分配等

参考资料

Redis 设计与实现

The Art of Automatic Memory Managcment

我们的架构日记 关注本公众号，欢迎订阅