前言

随着工作年限的增加,我们已经逐渐不再满足会用redis即可了,更希望深究redis底层的设计思想,实现方案,通过源码中精妙的设计,来帮助我们更好的设计,优化业务项目。本文是博主从网上搜的一些学习视频,加上自己的理解而创作的。本人水平有限,如有误导,欢迎斧正,一起学习,共同进步!


一、redis为什么快?

1、高速的存储介质 基于内存
2、优良的底层数据结构 时间复杂度 O(1) ,hashMap结构
3、高效的网络io模型 io模型的高效。epoll、select、kqueue、evport
4、高效的线程模型 执行线程是单线程,(io线程可能是多个线程,但是执行线程一定是1个。redis6.0以后,io线程是多线程,执行线程还是单线程)

二、redis的底层数据结构

redis的底层是一个数组。数组的时间复杂度是 O(1),不管查数组中的某个元素,都会很快。redis的底层是 hashTable,其实是数组,叫了个hashTable的名字。因为redis都是一个key 一个v的格式嘛。然后主结构的数组,就是存的 key 的hash函数的值。就是对key进行求hash,然后在对数组的长度求模。然后将元素存到指定的位置上(是不是有点像hashMap的主结构)。
redis采用链表法解决hash冲突。链表法也有头插法和尾插发的区别。redis是使用的头插法。原因是既然使用redis,肯定是觉得是个高频使用的,不是高频使用的直接放数据库就行,没必要放redis,既然是高频使用的,放在链表的头部,能更快的被查找,使用。

2.1、redis的底层存储的扩容机制

上面已经说了,redis的底层是hashtable,也就是数组。redis的hashtable(主结构数组)也会进行扩容,因为链表一旦长了,肯定就会影响查询的效率了。

2.1.1、扩容时间

既然是扩容,那是啥时候才会进行扩容呢?当hashTable存的元素已经超过了数组的长度的时候,就会进行扩容。

2.1.2、扩容多大

既然是扩容,那扩容多少呢?扩容一倍。比如说原先hashTable的容量是8,扩容后变成了16。当然,扩容后还有一个rehash的过程,

2.1.3、扩容后的rehash

rehash是说,讲原先数组(hashTable)中的元素,移动到扩容后的新的数组的位置中去。比如说原先 hash(key) % hashtable.size() = 某一个位置。 你的hashtable从8变成了16,那具体的存的位置肯定会改变,当然,也可能不会变。比如说原先数组的长是8,key的hash对8求模,是在第4个元素。扩容后了,key的hash对16求模。结果有可能还是第4个元素,也可能不是。具体看第几个元素来判断会不会移动。

2.1.4、何时进行rehash

那么什么时候进行rehash呢,也分为两种。

  • 主动:我访问一次数据的时候(不管是get也好,set也好,都会去访问一下hashtable,因为整个数据的索引都是通过hashtable来管理的),就做一下rehash。从低往高挨着去搬hash巢。一次搬一个巢,一个巢里可能有多个元素。而且他是按顺序去搬,并不是搬你要访问的那个

  • 被动:默认会轮询的搬hash巢,默认是搬100个。之所以只搬运100个hash巢,因为hash巢可能会非常大,你都同时搬运的话,可能会造成线程的卡顿,而对于redis这种内存型数据库来说,线程卡顿是业务上不可接受的。

2.1.5、俩hashtable访问那个呢?

那比如扩容的时候,有俩hashtable。因为redis的底层扩容的时候,是直接复制出来一个2倍的hashtable,然后把原始的hashtable的元素慢慢移动到第二个hashtable中去。因此比如访问的时候,那是访问第一个的hashtable还是第二个的hashtable呢,是先访问老的hashtable,如果有的话,直接拿到数据了,如果没有,就去新的hashtable中去拿。并且如果此时有新的元素加入进来了,就会去存入新的hashtable中,而不会再存到旧的hashtable中去。

2.2、redis的key的底层数据类型(sds)

redis是一个键值对的数据库,redis的值,可以是 string、list、set、zset、hash、bitmap、geospatial、hyperloglog。redis的键呢?redis的键可以是 string、int、double、图片、视频、音频、文件等等。但是,这些都是表象,都是客户端传给redis服务器的传值,具体的类型是由redis-server服务器来决定的。但是,不管是什么类型的key,redis的底层,存的都是string对象。也就是说,redis所有的键,都是string类型的

2.2.1、sds(Simple dynamic string)

redis是c语言写的,虽然redis是c语言写的,但是他却没有直接用c语言的数据结构。它自定义了一个 SDS (Simple dynamic string)的数据类型。c语言中的string是怎么表示的呢?是用一个char类型的数组来表示的,而且编译器会自动加一个 \0 来表示结束。
比如你有一个String类型的数据: dazeng
char [] data = “dazeng”; c语言的编译器,会自动的变成:
char [] data = “dazeng\0”; 去给最后加一个 \0。

2.2.2、sds诞生的原因

之所以要自定义 sds (simple dynamic string),是因为有的字符串中可能就有会 \0 这样的特殊字符,那你在用c语言中的 \0 来表示结尾,就不行了。就会中断,\0后面的字符就会被丢弃,这样显然是不行的。

2.2.3、sds的数据结构

比如说,一个da\0zeng的字符串, char [] buf =“da\0zeng” // 其中 \0 占一个字节
底层是sds结构(redis3.0版本):

	int len:7			// 数据的长度。不在依赖于\0去当做数据结尾,而是去查数据的长度,去截断。
	int free				// redis3.0以后是改成了alloc,也是因为int浪费空间,
    buf[14]=dazeng123		// 真正要存的 业务数据
		
  • len表示数据的长度。这样比较浪费空间,因为redis用的时候,大都是用的string(可能百分之80,90都是用的string)。然后你string的底层是sds,sds的int类型是4字节,4字节是能存 2^32 -1 的长度,好几亿,肯定不会有业务数据有好几亿的长度,所以会很浪费。虽然没毛病,却会很浪费内存。往往我们1个字节, 2^7 -1 的长度,就已经能很好的满足我们的业务需求了。

  • free是表示剩余的空间长度。也是一样的,因为redis的string增加的时候,比如说原先叫 dazeng,现在希望改成 dazeng1 。那么他的长度,可不是从6变成7。而是,希望变成7,就是 72=14。给他分配14的长度(其实这个2倍,也是看的大小,如果小于1m,则直接是翻倍扩容,如果是超过了1m,则是1m1m的加。1M=10241024*Char。Char可以是5bits/8bits/16bits/32bits/64bits)。那你用了7,14的长度用了7,还剩下7,你的free就是7,下次改成 dazeng12 8的长度的时候,就不用从新开辟内存空间,从新去扩容了。

2.2.4、sds扩容原理

大小小于1M的时候,翻倍扩容;大于1M的时候,1M,1M的增加。其实上面已经说完了。比如说原先叫 dazeng,现在希望改成 dazeng1 。那么他的长度,可不是从6变成7。而是,希望变成7,就是 72=14。给他分配14的长度(其实这个2倍,也是看的大小,如果小于1m,则直接是翻倍扩容,如果是超过了1m,则是1m1m的加。1M=10241024*Char。Char可以是5bits/8bits/16bits/32bits/64bits)。那你用了7,14的长度用了7,还剩下7,你的free就是7,下次改成 dazeng12 8的长度的时候,就不用从新开辟内存空间,从新去扩容了。其实扩容后,也会自动的在字符串后面加一个 \0 ,因为redis毕竟是c语音写的,还是会尽可能的兼容c语言的语法的。

2.2.5、redis3.0以后对底层sds的优化

redis的6.0版本中,都是:

sdshdr5		// 长度是  0 - 2^5 -1 
sdshdr8		// 长度是  0 - 2^8 -1 
sdshdr16	// 长度是  0 - 2^16 -1 
sdshdr32	// 长度是  0 - 2^32 -1 

之所以出现了sdshdr5,sdshdr8,sdshdr16,是因为我们只用int类型去表示长度,是比较浪费的。所以才会出现,hdr8,hdr16之类的数据类型。可以用相对更小的空间去描述我们的数据。用 sdshrd5 去描述头部数据。什么是头部数据呢,就是不是真正的业务数据buf,而是去描述业务数据的长度的,叫头部数据(比如说sds结构中的 len就是头部数据),sdshdr5举例,他用一个char类型的flags去表示,char只占一个byte,一个byte又是8个bit位。做了更多的优化。一个byte中,也拆分为两部分,第一部分当做类型,第二部分当做业务数据的长度。

三、redis的底层数据库设计?

在redis.conf 中。databases 16 其实就代表 有16个库,底层是个数组;数据库对应的结构:在server.h的文件中,有个redisDb的结构。

3.1、redis的底层存储结构

3.1.1、redisDb

在这里插入图片描述
其中
dist:是存全部的键值对的空间(最核心的点)
expires:是做一些 过期时间 的处理的
blocking_keys:是一些阻塞的api
ready_keys:一些键的锁,接受消息的时候的一些处理
watched_keys:事务的一些命令 的存储

3.1.2、dist

在这里插入图片描述
其中,下面这三是核心
dictType: 是字典类型,
dictht:其实就是一个hashTable(上面所说的数组),字典的hashtable。注意,它是个数组,数组里面单个元素是dictht。下面会详细介绍dictht
rehashidx:这个就是rehash的时候,已经rehash到了哪个的哈希巢了。

3.1.3、dictType

在这里插入图片描述
核心的是
hashFunction:hash函数,因为键要找到对应的hash巢的话,是通过这个hashfunction来找到对应的巢的
keyCompare:是键做比较的。因为如果两个键的hashCode一致,也不一定是hash冲突,也有可能这俩键是一样的,那就应该直接覆盖,不一样的情况下,才是hash冲突,就链表加就行。

3.1.4、dictht

在这里插入图片描述
table:指向的就是一个hash表的地址(键值对的真正的数据结构)
size:是hash表的长度
sizemask:是size的长度-1,是一个小优化,为了求模的时候更快
used:hashtable中一共有多少个元素

3.1.5、dictEntry

dictht中的 table的数据结构
在这里插入图片描述
key:string类型的key
v:是一个union的数据类型的指针。union的意思是,我有许多类型,但是同一时间,我只会有一个数据类型。比如说是val的话,就是指向的一个redisObject对象
next:是产生hash冲突的时候,next的指针,指向下一个的地址。

3.1.6、redisObject

在这里插入图片描述
type:是说这个对象是个什么样的类型,是string呢,还是list呢还是hash,set,bitmap之类的类型
encoding:是说编码。即使是相同的类型的话,底层是有可能会是不同的编码(值的长度不一样,编码方式会不同)。
lru:是和内存淘汰算法相关的一些处理
refcount:引用计数法相关的一个判断对象是否存活用的(因为redis是c写的,需要自己管理内存)
ptr:是真正的指向内存中的某一个区域,这个区域是用来存键值对的真正的数据的

3.2、数据库的总体理解图

在这里插入图片描述

  1. redisDb是数据库存的结构,通俗的话,就是最外层的存储结构
  2. dist是用来存储所有的数据的键值对的结构,dict中有type、dictht这俩重要的结构。其中type是存类型的,dictht是用来存数据的,之所以要有俩,是为了渐变式的rehash用的。(正常情况下,没有用到rehash的时候,同一时间,只会有一个hashtable)。rehash的时候,会创建一个比原来大一倍的空间
  3. 会根据数据的类型,数据的大小,来确认一个编码方式,然后存储到redisObject中去。
  4. redisObject的ptr又是一个sds的数据结构

四、总结

以上就是今天要讲的内容,本文仅仅简单介绍了redis的底层存储结构,而一些精妙的设计思想,例如redis的sdshdr8,sdshdr16来节省空间、redis的int类型的ptr不是指针信息而是直接是内容来减少一次磁盘io操作、等等这种设计思想上的精妙,是值得我们沉下心思去学习的。

Logo

华为云1024程序员节送福利,参与活动赢单人4000元礼包,更有热门技术干货免费学习

更多推荐