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

相关文章

来自专栏咸鱼不闲

fastjson 重复引用和循环引用问题

数据传输使用json格式再方便不过了。 fastjson 由阿里巴巴那伙人使用Java语言编写,号称最快的JSON库 前两天遇到一个问题 后台的数据转化为jso...

834
来自专栏微信公众号:Java团长

详解Java类的生命周期

最近有位细心的朋友在阅读笔者的文章时,对java类的生命周期问题有一些疑惑,笔者打开百度搜了一下相关的问题,看到网上的资料很少有把这个问题讲明白的,主要是因为目...

662
来自专栏JavaEE

java基础知识02

1、String字符串: 字符串一旦被初始化,就不可以被改变,存放在方法区中的常量池中。用length()方法获取长度。

472
来自专栏java一日一条

Java类的生命周期详解

最近有位细心的朋友在阅读笔者的文章时,对java类的生命周期问题有一些疑惑,笔者打开百度搜了一下相关的问题,看到网上的资料很少有把这个问题 讲明白的,主要是因为...

543
来自专栏向治洪

java虚拟机构造原理

 Java虚拟机的生命周期 一个运行中的Java虚拟机有着一个清晰的任务:执行Java程序。程序开始执行时他才运行,程序结束时他就停止。你在同一台机器上运行三...

1826
来自专栏用户2442861的专栏

java类加载过程

转载请注明出处:http://blog.csdn.net/ns_code/article/details/17881581

411
来自专栏好好学java的技术栈

“面试不败计划”:集合、日期、异常、序列化、其他知识点

912
来自专栏CSDN技术头条

Redis为什么这么快?一文深入了解Redis!

来源:http://www.cnblogs.com/kismetv/p/8654978.html

763
来自专栏Fish

android文件存储

为了输出数据,要把list中存储的写到一个txt文件里,就顺手学了一下 文件存储的方法,说是学,其实又是百度之后复制粘贴。不过学到了一个关于java中的一个知识...

2009
来自专栏java、Spring、技术分享

JVM学习笔记

  java引用类型分为四种:类、接口、数组类和泛型参数。其中泛型参数会在编译过程中被擦除。因此 Java 虚拟机实际上只有前三种。在类、接口和数组类中,数组类...

832

扫码关注云+社区