Redis源码:Redis源码怎么查看、Redis源码查看顺序、Redis外部数据结构到Redis内部数据结构查看源码顺序、Redis KV存储方式都是基于dict

发布于:2023-01-26 ⋅ 阅读:(23) ⋅ 点赞:(0) ⋅ 评论:(0)

Redis是KV存储机构的,
这种key、 value的存储方式,Redis一般会用hash表来进行存储,Redis的最外层也是使用的hash表,Redis还有一个hash的数据结构,那个叫做内层的hash。那么内层的hash是怎么实现的?

Redis源码怎么查看

可以去官网找你想要的版本:https://redis.io/download/

我用的版本是6.0.16。
首先下载redis压缩包,https://download.redis.io/releases/redis-6.0.16.tar.gz
解压,进入解压后的redis目录下的src文件夹,redis的所有源代码都存放在此。

在这里插入图片描述

Redis源码两个核心文件server.h、dict.h

Redis源码两个核心文件server.h、dict.h,这两个也是最基本的文件。
在Redis中,所有的KV存储方式都是基于dict(外层Hash表,HashTable)这个结构去存储的。

server.h文件

redisObject定义

dictEntry的val可以不同数据结构类型,因此很乱,
所以设计了redisObject统一管理不同类型的val数据结构,
dictEntry的val指向redisObject,
redisObject的*ptr指向对象实际的数据结构

typedef struct redisObject {	/*
								dictEntry的val可以不同数据结构类型,因此很乱,
								所以设计了redisObject统一管理不同类型的val数据结构,
								dictEntry的val指向redisObject,
								redisObject的*ptr指向对象实际的数据结构
								*/
								
    unsigned type:4;			/* 对象的类型,包括OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET */
								
    unsigned encoding:4;		/* 具体的数据结构类型 */
								
    unsigned lru:LRU_BITS; 	    /* 24位,对象最后一次被命令程序访问的时间,与内存回收有关 */
							   /* LRU time (relative to global lru_clock) or
								* LFU data (least significant 8 bits frequency
								* and most significant 16 bits access time). */
								
    int refcount;				/*
								引用计数。
								当refcount为0的时候,表示该对象已经不被任何对象引用,则可以进行垃圾回收了
								*/
								
    void *ptr;					/* 指向对象实际的数据结构,即key所对应的value的数据结构 */
} robj;

redisDb定义

typedef struct redisDb {		/* redisDb里面存的就是dict,dict的定义去看dict.h那个文件 */	
							
    dict *dict;                 /* The keyspace for this DB */	
								/* 所有的键值对 */
								
    dict *expires;              /* Timeout of keys with a timeout set */
								/* 设置了过期时间的的键值对 */
								
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

dict.h文件

dict定义:引用dictht

typedef struct dict {
    dictType *type;			/* 字典类型 */
							
    void *privdata;			/* 私有数据 */
							
    dictht ht[2];			/* 一个字典有两个哈希表:dictht */
							
    long rehashidx; 		/* rehashing not in progress if rehashidx == -1 */
							/* rehash索引 */
							
    unsigned long iterators;/* number of iterators currently running */
							/* 当前正在使用的的迭代器数量 */
} dict;

dictht定义:Redis定义的hash表,引用dictEntry

typedef struct dictht {		/* Redis定义的hash表:dictht */
							
    dictEntry **table;		/* 哈希表数组,dictEntry */
							
    unsigned long size;		/* 哈希表大小 */
							
    unsigned long sizemask;	/* 掩码大小,用于计算索引值。总是等于size-1 */
							
    unsigned long used;		/* 已有节点数 */
} dictht;

dictEntry定义:dictEntry(翻译过来就是字典条目),定义key和value

typedef struct dictEntry {	/* dictEntry(翻译过来就是字典条目),也就是为什么Redis又叫远程字典服务 */
							
    void *key;				/* key关键字定义:
							   ①是一个指针,指向key的存储.
							   ②Redis中所有的key都是字符串(Redis自身实现了字符串结构,叫做SDS)
							*/
    union {
        void *val;			/* value关键字定义:
							   ①是一个指针,指向value的统一存储对象,redisObject.
							   ②Redis中val可以是多种数据结构类型的(list、set、string...),
							   统一由redisObject来进行管理
							*/
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;	/* 指向下一个键值对节点 */
} dictEntry;

Redis的KV存储方式-dict、dictht、dictEntry关系图

外层的KV存储的HashTable(dict),结构如下
请添加图片描述

sds.h文件:简单动态字符串,Redis自己实现的字符串,所有的key都是SDS结构

SDS(Simple Dynamic String):简单动态字符串,Redis会根据String类型的value长度,去选择合适的sdshdr数结构来存储这个value。

SDS是什么:简单动态字符串

SDS(Simple Dynamic String):简单动态字符串,Redis会根据String类型的value长度,去选择合适的sdshdr数结构来存储这个value,这样的设计可以节省内存空间。

在这里插入图片描述

# 换算:
2^10=1024byte=1kb
2^20=1MB
2^30=1GB
2^40=1TB
2^50=1PB
2^60=1EB

sdshdr5:2^5=32byte(不用)
sdshdr8:2^8=256byte
sdshdr16:2^16=65536byte=64kb
sdshdr32:2^32=4GB
sdshdr64:2^64=16EB

Redis的key是字符类型,即String,最大可以用得到是512M,那么它的value字符类型,也是String,最大也是512M。
sdshdr32,sdshdr64定义的这么大,但你未必能用得到全部,这也是Redis预留的一种思想,给你足够多的空间,未来可能就用的到这么大了。

sds.h文件的sdshdr8的源码截取

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
				 /* 当前字符数组的长度,有这个值使得获取字符长度的复杂度变为O(1),不用向C语言的字符数组那样从头至尾遍历O(N) */
				 
    uint8_t alloc; /* excluding the header and null terminator */
				   /* 当前字符数组总共分配的内存大小 */
	
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
						 /* 当前字符数组的属性、用来标识到底是sdshdr8还是sdshdr16等 */
						 
    char buf[];			 /* 字符串真正的值,它是用字符数组来进行存储的 */
};

Redis为什么要用SDS来实现字符串?

C语言里面也是没有字符串的,它有的是字符数组,有以下特点:

  1. 内存空间预先分配
  2. 获取字符长度(即字符数组的长度)需要从头到尾先遍历一遍,时间复杂度O(n)
  3. C语言的字符数组内存分配是固定的,长度变更引起内存重新分配
  4. 用’\0’判断字符串结束(如果你存的内容恰好包含,也会认为是结束)

所以Redis基于字符数组实现了自己的字符串SDS:简单动态字符串

C字符数组 SDS
获取字符长度的复杂度O(N) 获取字符长度的复杂度O(1),因为SDS中uint8_t len存储当前字符数组的长度
API是不安全的,可能会造成称缓冲区溢出 API是安全的,不会造成称缓冲区溢出,简单动态字符串可以扩容,而且不需要预先分配,因此不会产生内存溢出
修改字符长度N次必然需要执行N次内存重新分配 修改字符长度N次最多需要执行N次内存重新分配,SDS里面有一个特殊的设计,叫做空间的预分配和惰性的空间释放,不管是获取内存还是释放内存都不是及时的,所以性能会提升
只能保存文本数据 可以保存文本数据或者二进制数据
可以使用所有<string.h>库中的函数 可以使用部分<string.h>库中的函数

Redis各数据结构命令、源码分析、应用场景

Redis源码-String:Redis String命令、Redis String存储原理、Redis String三种编码类型、Redis字符串SDS源码解析、Redis String应用场景

Redis源码-Hash:Redis String与Hash的区别、Redis Hash存储原理、Redis Hash命令、 Redis Hash存储底层编码、Redis Hash应用场景

Redis源码-List:Redis List存储原理、Redis List命令、 Redis List存储底层编码quicklist、Redis List应用场景

Redis源码-Set:Redis Set存储原理、Redis Set集合操作命令、Redis Set两种存储底层编码intset+hashtable、Redis Set应用场景

Redis源码-ZSet:Redis ZSet存储原理、Redis ZSet命令、 Redis ZSet两种存储底层编码ziplist/dict+skiplist、Redis ZSet应用场景


网站公告

欢迎关注微信公众号

今日签到

点亮在社区的每一天
签到