《Redis设计与实现》读书笔记(二) ——Redis中的字典(Hash)

《Redis设计与实现》读书笔记(二) ——Redis中的字典(Hash)

(原创内容,转载请注明来源,谢谢)

一、概述

字典,又称符号表、关联数组、映射,是一种保存键值对的抽象数据结构。每个键(key)和唯一的值(value)关联,键是独一无二的,通过对键的操作可以对值进行增删改查。

redis中字典应用广泛,对redis数据库的增删改查就是通过字典实现的。即redis数据库的存储,和大部分关系型数据库不同,不采用B+tree进行处理,而是采用hash的方式进行处理。

另外,毫无疑问,redis的hash数据类型也是通过字典方式实现。

二、字典的实现

redis的字典,底层是使用哈希表实现,每个哈希表有多个哈希节点,每个哈希节点保存了一个键值对。

1、哈希表

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

其中,table是一个数组,里面的每个元素指向dictEntry(哈希表节点)结构的指针,dictEntry结构是键值对的结构;size表示哈希表的大小,也是table数组的大小;used表示table目前已有的键值对节点数量;sizemask一直等于size-1,该值与哈希值一起决定一个属性应该放到table的哪个位置。

大小为4的空哈希表结构如下图(左边一列的图)所示:

2、哈希表节点

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

其中,key表示节点的键;union表示key对应的值,可以是指针、uint64_t整数或int64_t整数;next是指向另一个哈希表节点的指针,该指针将多个哈希值相同的键值对连接在一起,避免因为哈希值相同导致的冲突。

哈希表节点如下图(左边第一列是哈希表结构,表节点结构从左边第二列开始)所示:

3、字典

1)dict

typedef structdict{
dictType *type;
void *privdata;
dictht ht[2];
int rehashidx;
}dict;

其中,type用于存放用于处理特定类型的处理函数,下面会提;privdata用于存放私有数据,保存传给type内的函数的数据;rehash是一个索引,当没有在rehash进行时,值是-1;ht是包含两个项的数组,每个项是一个哈希表,一般情况下只是用ht[0],只有在对ht[0]进行rehash时,才会使用ht[1]。

2)dictType

typedef structdictType{
unsigned int (*hashFunction) (const void *key);
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;

该结构体定义了字典的各种操作函数,hashFunction是哈希值计算函数,keyDup是键复制,valDup是值复制,keyCompare是键比较,keyDestructor是键销毁,valDestructor是值销毁。

完整的字典结构如下图所示:

三、哈希算法

要将新的键值对加到字典,程序要先对键进行哈希算法,算出哈希值和索引值,再根据索引值,把包含新键值对的哈希表节点放到哈希表数组指定的索引上。

redis实现哈希的代码是:

hash =dict->type->hashFunction(key);
index = hash& dict->ht[x].sizemask;

算出来的结果中,index的值是多少,则key会落在table里面的第index个位置(第一个位置index是0)。

其中,redis的hashFunction,采用的是murmurhash2算法,是一种非加密型hash算法,其具有高速的特点。

而hash的结果,还需要和sizemask进行二进制的&计算,由于sizemask一直都是size-1,因此保证没有数据的情况下必定放在table的第一个位置,而其后的值按照表格顺序往下排的可能性也很大。

四、键冲突解决

当两个或者以上的键,算出来的第三步的index的值一样,则称为有冲突。

为了解决此问题,redis采用链地址法,每个哈希表节点都有一个指向next的指针,当发生冲突时,直接将当前哈希表节点的next指针指向新的结果。后面如果还有冲突的键,则当前键的next会指向下一个哈希表节点。

五、rehash(重新散列)

随着操作进行,哈希表保存的键值对会增加或减少,为了让哈希表的负载因子(load factor)维持在一个合理范围,当一个哈希表保存的键太多或者太少,需要对哈希表进行扩展或者收缩。扩展或收缩哈希表的过程,就称为rehash。

rehash步骤如下:

1、给字典的ht[1]申请存储空间,大小取决于要进行的操作,以及ht[0]当前键值对的数量(ht[0].used)。假设当前ht[0].used=x。

1)如果是扩展,则ht[1]的值是第一个大于等于x*2的2n的值。例如x是30,则ht[1]的大小是第一个大于等于30*2的2n的值,即64。

2)如果是收缩,则ht[1]的值是第一个大于等于x的2n的值。例如x是30,则ht[1]的大小是第一个大于等于30的2n的值,即32。

2、将保存在ht[0]上面的所有键值对,rehash到ht[1],即对每个键重新采用第三大点哈希算法的方式计算哈希值(index的值),再放到相应的ht[1]的表格指定位置。

3、当ht[0]的所有键值对都rehash到ht[1]后,释放ht[0],并将ht[1]设置为ht[0],再新建一个空的ht[1],用于下一次rehash。

六、rehash条件

1、负载因子(load factor)计算

load_factor =ht[0].used / ht[0].size,即负载因子大小等于当前哈希表的键值对数量,除以当前哈希表的大小。

2、扩展

当以下任一条件满足,哈希表会自动进行扩展操作:

1)服务器目前没有在执行BGSAVE或者BGREWRITEAOF命令,且负载因子大于等于1。

2)服务器目前正在在执行BGSAVE或者BGREWRITEAOF命令,且负载因子大于等于5。

要判断是否在进行bgsave或bgwriteaof,是因为这两个命令执行过程中,redis需要创建当前服务器进程的子进程,而大多数操作系统又都是用写时复制(copy-on-write)技术优化子进程的使用效率。

因此,在执行这两个命令期间,redis会提高哈希表扩展操作的负载因子,以避免不必要的数据写入内存(例如ht[1]建立好而ht[0]尚未清空清空下,同时存在两份数据),最大限度节约内存。

3、收缩

当负载因子小于0.1时,redis自动开始哈希表的收缩工作。

4、copy-on-write简介

写时复制技术,是操作系统层面,为了提升性能而进行的一个策略。

策略如下:每次写文件操作,都写在特定大小的一块内存中(磁盘缓存),并不是直接写到磁盘中。只有当我们关闭文件时,才写到磁盘上(这就是为什么如果文件不关闭,所写的东西会丢失的原因)。更有甚者是文件关闭时都不写磁盘,而一直等到关机或是内存不够时才写磁盘,Unix就是这样一个系统,如果非正常退出,那么数据就会丢失,文件就会损坏。

写时复制技术,大大降低了磁盘I/O的次数,而I/O往往是性能瓶颈,这样一来就最大程度上避免了此瓶颈。

七、渐进式rehash

redis对ht[0]扩展或收缩到ht[1]的过程,并不是一次性完成的,而是渐进式、分多次的完成,以避免如果哈希表中存有大量键值对,一次性复制过程中,占用资源较多,会导致redis服务停用的问题。

渐进式rehash过程如下:

1、为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两张哈希表。

2、将字典中的rehashidx设置成0,表示正在rehash。rehashidx的值默认是-1,表示没有在rehash。

3、在rehash进行期间,程序处理正常对字典进行增删改查以外,还会顺带将ht[0]哈希表上,rehashidx索引上,所有的键值对数据rehash到ht[1],并且rehashidx的值加1。

4、当某个时间节点,全部的ht[0]都迁移到ht[1]后,rehashidx的值重新设定为-1,表示rehash完成。

渐进式rehash采用分而治之的工作方式,将哈希表的迁移工作所耗费的时间,平摊到增删改查中,避免集中rehash导致的庞大计算量。

在rehash期间,对哈希表的查找、修改、删除,会先在ht[0]进行。如果ht[0]中没找到相应的内容,则会去ht[1]查找,并进行相关的修改、删除操作。而增加的操作,会直接增加到ht[1]中,目的是让ht[0]只减不增,加快迁移的速度。

八、总结

字典在redis中广泛应用,包括数据库和hash数据结构。每个字典有两个哈希表,一个是正常使用,一个用于rehash期间使用。当redis计算哈希时,采用的是MurmurHash2哈希算法。哈希表采用链地址法避免键的冲突,被分配到同一个地址的键会构成一个单向链表。在rehash对哈希表进行扩展或者收缩过程中,会将所有键值对进行迁移,并且这个迁移是渐进式的迁移。

——written by linhxx 2017.08.29

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coder修行路

Nginx location 匹配顺序整理

Nginx location模块整理 具体的Nginx安装就不在这里描述了,这里只是为了对location的描述 Nginx环境 a. 查看当前系统cat /e...

35370
来自专栏开源优测

[快学Python3]XML解析处理 - Element Tree

概述 本文就是python xml解析进行讲解,在python中解析xml有很多种方法,本文通过实例来讲解如何使用ElementTree来解析xml。对于其他的...

47480
来自专栏架构说

缓存策略之LRU实现及分析

LRU定义 Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间...

347100
来自专栏DOTNET

.Net多线程编程—并发集合

并发集合 1 为什么使用并发集合? 原因主要有以下几点: System.Collections和System.Collections.Generic名称空间中所...

35870
来自专栏前端杂货铺

深入seajs源码系列三

入口方法        每个程序都有个入口方法,类似于c的main函数,seajs也不例外。系列一的demo在首页使用了seajs.use(),这便是入口方法。...

28760
来自专栏Laoqi's Linux运维专列

case 判断

30380
来自专栏大内老A

ASP.NET MVC的Model元数据提供机制的实现

在前面的介绍中我们已经提到过表示Model元数据的ModelMetadata对象最终是通过一个名为ModelMetadataProvider的组件提供的,接下来...

22860
来自专栏耕耘实录

PHP学习笔记(1)--基础知识篇

有两种通过 PHP 来输出文本的基础指令:echo 和 print。在上面的例子中,我们使用了 echo 语句来输出文本 "Hello World"。

17530
来自专栏瓜大三哥

文件地址映射之yaffs_GetTnode

yaffs文件系统在更新文件数据的时候,会分配一块新的chunk,也就是说,同样的文件偏移地址,在该地址上的数据更新前和更新后,其对应的flash上的存储地址是...

20760
来自专栏张戈的专栏

Linux运维基础技能: 脚本编程与Linux命令

本系列文章一共三篇,分别为《脚本编程与 Linux 命令》、《接入层与网络基础》和《 MySQL 与 SQL 优化》,由腾讯高级工程师 luaruan(阮永顺)...

24120

扫码关注云+社区

领取腾讯云代金券