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这个结构去存储的。

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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;
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
1
2
3
4
5
6
7
8
9
10

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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
1
2
3
4
5
6
7

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[];			 /* 字符串真正的值，它是用字符数组来进行存储的 */
};
1
2
3
4
5
6
7
8
9
10
11
12

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

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

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

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

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

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