Redis是KVstorage organization,
这种key、 value的存储方式,Redis一般会用hashtable for storage,RedisThe outermost layer is also usedhash表,Redis还有一个hash的数据结构,That's called the inner layerhash.那么内层的hash是怎么实现的？

Redis源码怎么查看

You can go to the official website to find the version you want：https://redis.io/download/

我用的版本是6.0.16.
首先下载redis压缩包,https://download.redis.io/releases/redis-6.0.16.tar.gz
解压,进入解压后的redis目录下的src文件夹,redisAll source code for .

RedisSource two core filesserver.h、dict.h

RedisSource two core filesserver.h、dict.h,These two are also the most basic files.

server.h文件

redisObject定义

dictEntry的valThere can be different data structure types,so messy,
所以设计了redisObjectUnified management of different typesval数据结构,
dictEntry的val指向redisObject,
redisObject的*ptr指向对象实际的数据结构

typedef struct redisObject {
    	/*
								dictEntry的valThere can be different data structure types,so messy,
								所以设计了redisObjectUnified management of different typesval数据结构,
								dictEntry的val指向redisObject,
								redisObject的*ptr指向对象实际的数据结构
								*/
								
    unsigned type:4;			/* 对象的类型,包括OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET */
								
    unsigned encoding:4;		/* The specific data structure type */
								
    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,dictlook at the definitiondict.h那个文件 */	
							
    dict *dict;                 /* The keyspace for this DB */	
								/* 所有的键值对 */
								
    dict *expires;              /* Timeout of keys with a timeout set */
								/* A key-value pair with an expiration time 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 */
							/* The number of iterators currently in use */
} 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(That translates to a dictionary entry),定义key和value

typedef struct dictEntry {
    	/* dictEntry(That translates to a dictionary entry),也就是为什么RedisAlso called remote dictionary service */
							
    void *key;				/* key关键字定义：
							   ①是一个指针,指向key的存储.
							   ②Redis中所有的key都是字符串(RedisIt implements the string structure itself,叫做SDS)
							*/
    union {
    
        void *val;			/* value关键字定义：
							   ①是一个指针,指向valueunified storage object,redisObject.
							   ②Redis中valCan be of various data structure types(list、set、string...),
							   统一由redisObject来进行管理
							*/
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;	/* 指向下一个键值对节点 */
} dictEntry;

sds.h文件：简单动态字符串,RedisString implemented by yourself,所有的key都是SDS结构

SDS（Simple Dynamic String）：简单动态字符串,Redis会根据String类型的value长度,去选择合适的sdshdrnumber structure to store thisvalue.

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

SDS（Simple Dynamic String）：简单动态字符串,Redis会根据String类型的value长度,去选择合适的sdshdrnumber structure to store thisvalue,Such a design can save memory space.

# 换算：
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,The maximum that can be used is512M,那么它的value字符类型,也是String,最大也是512M.
sdshdr32,sdshdr64so big by definition,But you may not be able to use all of them,这也是RedisA reserved idea,give you enough space,In the future, it may be used so much.

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

struct __attribute__ ((__packed__)) sdshdr8 {
    
    uint8_t len; /* used */
				 /* 当前字符数组的长度,Having this value makes getting the length of characters in complexityO(1),不用向CTraversing from the beginning to the end of the character array of the languageO(N) */
				 
    uint8_t alloc; /* excluding the header and null terminator */
				   /* 当前字符数组总共分配的内存大小 */
	
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
						 /* 当前字符数组的属性、用来标识到底是sdshdr8还是sdshdr16等 */
						 
    char buf[];			 /* 字符串真正的值,It is stored in a character array */
};

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

CThere are no strings in the language,It has an array of characters,有以下特点：

1. 内存空间预先分配
2. 获取字符长度（That is, the length of the character array）It needs to be traversed from beginning to end,时间复杂度O(n)
3. CThe language's character array memory allocation was fixed,长度变更引起内存重新分配
4. 用’\0’判断字符串结束（If your save content happens to contain ,Also considered to be the end）

所以RedisImplemented own strings based on character arraysSDS：简单动态字符串

RedisEach data structure command、源码分析、应用场景

Redis源码-String：Redis String命令、Redis String存储原理、RedisThree encoding types of strings、Redis String SDS源码解析、Redis String应用场景