一、redis的基本存储结构
内存数据库：redisDb
键值对：dict
键值对的数据类型：dictType
键值对实体：dictEntry
二、数据库redisDb
typedef struct redisDb { 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. */ clusterSlotToKeyMapping *slots_to_keys; /* Array of slots to keys. Only used in cluster mode (db 0). */ } redisDb;
dict *dict用来组织所有数据的键值对(dict)dict *expires过期的dictdict *blocking_keys阻塞的dict (比如BRPOP等命令，会阻塞，只有当要取的数组结构不为空，才会解除阻塞)dict *ready_keys解除阻塞的dictdict *watched_keys监控(watch)的dict （事务前可以加watch）
三、哈希表dict
struct dict { dictType *type; dictEntry **ht_table[2]; unsigned long ht_used[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ /* Keep small vars at end for optimal (minimal) struct padding */ int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */ signed char ht_size_exp[2];//* exponent of size. (size = 1<<exp) */ };
dictType *type键值对的类型，可以进行自定义（hash，key，val操作），使得dict能够存储任意类型的数据dictEntry **ht_table[2]首先，先看dictEntry,这是一个dict实体，也就是说存放的是键值对，那么dictEntry **ht_table就可以理解为一张哈希表(数组，有1个*号)，哈希表中的元素是一个指针（第2个*号），dictEntry **ht_table这个哈希表是通过,数组+哈希函数(指针)的方式组织起来的。 那么dictEntry **ht_table[2]就很好理解了，也就是两张哈希表(为了做rehash)。ht_used[2]:两张哈希表中，分别使用了多少（比如数组长度16,只使用了10）rehashidx：记录 rehash 进度的标志（每移动一个桶,rehashidx++），值为 -1 表示 rehash 未进行。pauserehashrehash是否暂停ht_size_exp[2]:以ht_size_exp[0]为例，这是哈希表的长度，长度是2的倍数，因为这样可以将n%size优化成n&(size-1)从而加快运算速度
四、哈希数据类型dictType
dictType中是一个存放函数的结构体，定义了一些函数指针。
可以通过设置自定义函数，使得dict的key和value能够存储任何类型的数据
typedef struct dictType { uint64_t (*hashFunction)(const void *key);//哈希函数 void *(*keyDup)(dict *d, const void *key);//复制key void *(*valDup)(dict *d, const void *obj);//复制val int (*keyCompare)(dict *d, const void *key1, const void *key2);//比较key void (*keyDestructor)(dict *d, void *key);//删除key void (*valDestructor)(dict *d, void *obj);//删除val int (*expandAllowed)(size_t moreMem, double usedRatio); /* Allow a dictEntry to carry extra caller-defined metadata. The * extra memory is initialized to 0 when a dictEntry is allocated. */ size_t (*dictEntryMetadataBytes)(dict *d); } dictType;
五、哈希实体（键值对）dictEntry
存放键值对
哈希冲突：当哈希表中数据增加，新增的数据 key 哈希计算出的哈希值和老数据 key 的哈希值会在同一个哈希桶中，也就是说多个 key 对应同一个哈希桶
next中存储的是哈希值相同的key/val对（出现哈希冲突），使用拉链法，通过链表串起来。
链式哈希会产生一个问题，随着哈希表数据越来越多，哈希冲突越来越多，单个哈希桶链表上数据越来越多
typedef struct dictEntry { void *key;//键 union { void *val; uint64_t u64; int64_t s64; double d; } v;//值 struct dictEntry *next; /* Next entry in the same hash bucket. */ void *metadata[]; /* An arbitrary number of bytes (starting at a * pointer-aligned address) of size as returned * by dictType's dictEntryMetadataBytes(). */ } dictEntry;
