Redis数据DB
Redis是一个一个的DB，那么这个DB到底是一个什么样构造的数据呢？
如下是Redis官网的源码（5.0）
/* Redis数据库示意。有多个数据库标识从0(默认数据库)到配置的最大值的整数数据库。数据库号是构造中的“id”字段*/typedef struct redisDb { dict *dict; /* 这个数据库的键空间（字典类型） */ dict *expires; /* 设置超时的键的超时 */ dict *blocking_keys; /* 客户端期待数据的密钥(BLPOP) */ dict *ready_keys; /* 接管到推送的阻塞键 */ dict *watched_keys; /* EXEC CAS的监督键 */ int id; /* 数据库ID */ long long avg_ttl; /* 均匀TTL，仅用于统计 */ list *defrag_later; /* 要一一进行磁盘整顿的键名列表 */} redisDb;咱们能够看到Redis的数据库次要的数据是寄存在字典中的
Redis数据Dict字典
官网源码地址：https://github.com/redis/redi...
咱们找到dict字典的定义：
// 字典类型数据定义typedef struct dict { dictType *type; /* 字典类型数组 */ void *privdata; /* 公有数据 */ dictht ht[2]; /* 字典Hash表数组 */ long rehashidx; /* 如果 rehashidx == -1，示意没有进行Rehash,如果为负数示意有ReHash操作 */ unsigned long iterators; /* 以后正在运行的迭代器数 */} dict;次要的数据是寄存在咱们的字典Hash表数组中的咱们在来看一下这个dictht，字典Hash表
// 字典Hash表类型数据定义typedef struct dictht { dictEntry **table; /* Hash表，寄存一个又一个的字典元素,实际上是一个数组 */ unsigned long size; /* 哈希表大小，即哈希表数组大小 */ unsigned long sizemask; /* 哈希表大小掩码，总是等于size-1，次要用于计算索引 */ unsigned long used; /* 已应用节点数，即已应用键值对数 */} dictht;那么更加次要的就是咱们的每一个字典的元素，示意咱们寄存的元素数据
// 字典元素类型数据定义typedef struct dictEntry { // 无类型指针，Key指向Val值 void *key; // 值，是一个专用体,他有可能是一个指针，或者一个64位正整数，或者64位int，浮点数 union { // 值指针 void *val; // 64位正整数 uint64_t u64; // 64位int int64_t s64; // 浮点数 double d; } v; // next节点，每一个dictEntry都是一个链表，用于解决Hash抵触 struct dictEntry *next;} dictEntry;Redis解决Hash抵触
咱们晓得上方的dict，有两个Hash表 ，那么为什么咱们要放两个Hash表呢？
答案就是咱们Redis的Hash表在进行扩容的时候须要用到的，那么上面咱们来看一下源码中的解释吧。
int dictRehash(dict *d, int n);
源码地位：https://github.com/redis/redi...
首先咱们必定须要晓得咱们是在哪一步进行扩容的，必定是在咱们产生Add操作的时候咱们定位到Add的办法：
/* 增加一个元素到指标哈希表 */int dictAdd(dict *d, void *key, void *val){ // 向字典中增加key dictEntry *entry = dictAddRaw(d,key,NULL); if (!entry) return DICT_ERR; // 而后设置节点的值 dictSetVal(d, entry, val); return DICT_OK;}而后咱们定位到dictAddRaw，这一步应用链表解决Hash抵触
/* 低级增加或查找: * 此函数增加了元素，但不是设置值而是将dictEntry构造返回给用户，这将确保按需填写值字段. * * 此函数也间接公开给要调用的用户API次要是为了在哈希值外部存储非指针，例如: * entry = dictAddRaw(dict,mykey,NULL); * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); * * 返回值: * * 如果键曾经存在，则返回NULL，如果不存在，则应用现有条目填充“ * existing”. * 如果增加了键，则哈希条目将返回以由调用方进行操作。 */dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){ long index; dictEntry *entry; dictht *ht; // 判断是否正在ReHash，如果须要则调用_dictRehashStep（后续ReHash中的步骤），每次ReHash一条数据，直到实现整个ReHash if (dictIsRehashing(d)) _dictRehashStep(d); /* 获取新元素的索引,依据Key计算索引，并且判断是否须要进行扩容ReHash(！！！重点)（第一次ReHash调用） */ if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) return NULL; /* 解决Hash抵触，以及ReHash时效率问题 */ /* 分配内存并存储新条目。假如在数据库系统中更有可能更频繁地拜访最近增加的条目，则将元素插入顶部 */ // 判断是否须要ReHash，如果是那么以后的HashTable为字典下的第二个，如果不须要扩容则应用原来的的 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 创立元素,分配内存 entry = zmalloc(sizeof(*entry)); // 进行元素链表操作，元素的下一个节点指向Hash表中的相应索引，如果以前这个下标有元素则链到以后元素前面 entry->next = ht->table[index]; // Hash表节点索引设置为本人，替换原来的元素 ht->table[index] = entry; ht->used++; /* 设置这个Hash元素的Key. */ dictSetKey(d, entry, key); return entry;}看完了Hash抵触的解决形式咱们再来看一下扩容，首先咱们看一下dictIsRehashing，是如何判断须要进行ReHash的
ReHash解决扩容ReHash过程
// 如果字典的rehashidx不是-1，那就示意须要进行Hash扩容 dictIsRehashing(d) ((d)->rehashidx != -1)那么在什么中央批改了rehashidx呢，就是在咱们计算Index的时候
/* 返回可用插槽填充的索引,依据“Key”的哈希计算，如果Key曾经存在，则返回-1 * 请留神，如果咱们正在从新哈希表，索引总是在第二个（新）哈希表的上下文中返回，也就是ht[1] */static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){ unsigned long idx, table; dictEntry *he; if (existing) *existing = NULL; /* 如果须要，扩容哈希表，如果失败返回-1（ReHash扩容机制） */ if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; /* 从两个Hash表进行查问，可能这个Key放入了第二个哈希表 */ for (table = 0; table <= 1; table++) { /* 依据数组长度 - 1 而后取模计算卡槽 */ idx = hash & d->ht[table].sizemask; /* 依据Hash表获取元素，并且判断这个Key有没有在Hash表外面，如果存在返回-1 */ he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) { if (existing) *existing = he; return -1; } he = he->next; } // 如果不在ReHash，间接返回第一个Hash表的index卡槽，如果是ReHash那么就把idx放入第二个Hash表 if (!dictIsRehashing(d)) break; } return idx;}此处开始判断是否须要进行扩容
/* 如果须要，扩容Hash表 */static int _dictExpandIfNeeded(dict *d){ /* 如果曾经在ReHash中了，间接返回 */ if (dictIsRehashing(d)) return DICT_OK; /* 如果哈希表为空，将其开展到初始大小。初始大小4 */ if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); /* 如果咱们的曾经应用的元素个数和Hash表数组长度达到 1：1 比率，那么就要进行扩容了 （全局设置）或者咱们应该防止它， 但之间的比率元素/存储桶超过"平安"阈值，咱们调整大小加倍存储桶的数量 */ /* 简略来说就是咱们应用的元素等于数组的长度那么咱们就扩容Hash表，容量扩容一倍 */ if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, d->ht[0].used*2); } return DICT_OK;}将第二张Hash表从新初始化，后续ReHash中的元素都会放入第二张Hash表
/* 扩容或者创立Hash表 */int dictExpand(dict *d, unsigned long size){ /* 如果正在ReHash，或者应用数量大于原size * 2，返回-1 */ if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; dictht n; /* 新的哈希表 */ unsigned long realsize = _dictNextPower(size); /* 从新大小重为雷同的表大小没有用途，返回-1 */ if (realsize == d->ht[0].size) return DICT_ERR; /* 调配新的哈希表并初始化所有指向 NULL 的指针 */ n.size = realsize; n.sizemask = realsize-1; /* 分配内存扩容空间 */ n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; /* 这是第一次初始化吗？如果是这样，它不是真正的重述，咱们只是设置第一个哈希表，以便它能够承受键。 */ if (d->ht[0].table == NULL) { d->ht[0] = n; return DICT_OK; } /* 筹备第二个哈希表以进行增量重哈希，将第二个长期寄存的Hash表从新初始化，开始ReHash操作 */ d->ht[1] = n; d->rehashidx = 0; return DICT_OK;}ReHash过程是指咱们将状态设置为了ReHash，并且将新增的元素写入到了第二张Hash表，这个时候咱们就须要将第二张Hash表和第一张Hash表
/* 字典ReHash操作，每次第一个参数示意字典，第二个参数示意每次ReHash的数量，例如100扩容至两百，如果没有Hash抵触，咱们须要传入100能力实现ReHash */int dictRehash(dict *d, int n) { int empty_visits = n*10; /* 可拜访的最大空桶数 */ /* 不在ReHash过程间接返回 */ if (!dictIsRehashing(d)) return 0; /* ReHash 第二张表时会先 */ while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; /* 请留神，rehashidx不会溢出，因为咱们确信还有更多元素，因为ht [0] .used！= 0*/ assert(d->ht[0].size > (unsigned long)d->rehashidx); // 如果卡槽是空的那么从ReHashIndex开始自增，因为须要遍历，rehashidx从开始被默认置为0，如果须要将原来的Hash表实现ReHash，就须要从0遍历残缺张Hash表 while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; // 如果查找了n * 10个卡槽还是为空的话那么咱们返回1，不执行操作 if (--empty_visits == 0) return 1; } // 获取原来的ht[0]的相应卡槽的Hash表 de = d->ht[0].table[d->rehashidx]; /* 而后将卡槽中的Key Value 都放入 ht[1] 示意将数据从ht[0] 挪动到 ht[1]*/ while(de) { uint64_t h; nextde = de->next; /* 获取新哈希表中的索引 */ h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } // 如果为空那么持续+1，晓得ht[0]的表变成空的 d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } // 实现ReHash，示意将ht[0]所有数据曾经挪动到ht[1]，而后将ht[1] 赋值给ht[0]，而后清空ht[1]，一次ReHash操作实现 /* 查看咱们是否曾经从新ReHash了第一张Hash表.. */ if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } /* 返回数据，这一步通常因为ReHash没有执行完，只ReHash了一部分（未实现ReHash） */ // 返回1示意给定时工作循环调度，while条件，示意没有ReHash实现 return 1;}并且有任务调度ReHash
在Server中https://github.com/redis/redi...
/* 数据库定时工作 */void databasesCron(void) {/* Rehash */ if (server.activerehashing) { for (j = 0; j < dbs_per_call; j++) { // 数据库ReHash int work_done = incrementallyRehash(rehash_db); if (work_done) { break; } else { /* If this db didn't need rehash, we'll try the next one. */ rehash_db++; rehash_db %= server.dbnum; } } }// 每个数据库每次执行1毫秒的ReHashint incrementallyRehash(int dbid) { /* Keys dictionary */ if (dictIsRehashing(server.db[dbid].dict)) { dictRehashMilliseconds(server.db[dbid].dict,1); return 1; /* 曾经应用了毫秒作为循环周期。... */ } /* Expires */ if (dictIsRehashing(server.db[dbid].expires)) { dictRehashMilliseconds(server.db[dbid].expires,1); return 1; /* 曾经应用了毫秒作为循环周期。... */ } return 0;} /* Rehash在ms+"delta"毫秒。delta值较大,小于0，大多数状况下小于1。准确上界取决于dictRehash(d,100)的运行工夫 */int dictRehashMilliseconds(dict *d, int ms) { if (d->iterators > 0) return 0; // 记录开始同步 long long start = timeInMilliseconds(); // 记录ReHash的数量 int rehashes = 0; // 每次ReHash100条数据 while(dictRehash(d,100)) { rehashes += 100; // 如果执行到指定工夫 例如 一毫秒，以后工夫 - 开始工夫 > 1毫秒，则间接Break if (timeInMilliseconds()-start > ms) break; } return rehashes;}