redis之字符串命令源碼解析（二）
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-11-22 08:40:07 閱讀次數(shù)：2645次
形象化設(shè)計(jì)模式實(shí)戰(zhàn) HELLO!架構(gòu)
redis命令源碼解析
在redis之字符串命令源碼解析（1）中講了get的簡(jiǎn)單實(shí)現(xiàn)，并沒(méi)有對(duì)如何取到數(shù)據(jù)做深入分析，這里將深入。
1、redisObject 數(shù)據(jù)結(jié)構(gòu)，和Redis 的數(shù)據(jù)類型
（1）中說(shuō)set test "hello redis"，“hello redis”會(huì)終究保存在robj中，redisObject是Redis的核心，http://www.jyygyx.com/db/的每一個(gè)鍵、值，和Redis本身處理的參數(shù)都表示為這類數(shù)據(jù)類型，其結(jié)構(gòu)以下：
/* The actual Redis Object */
/*
* Redis 對(duì)象
*/
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)⑴) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
// 類型，冒號(hào)后面跟數(shù)字，表示包括的位數(shù)，這樣更節(jié)省內(nèi)存
unsigned type:4;
// 編碼
unsigned encoding:4;
// 對(duì)象最后1次被訪問(wèn)的時(shí)間
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 援用計(jì)數(shù)
int refcount;
<span style="color:#ff0000;">// 指向?qū)嶋H值的指針,指向上節(jié)的sdshdr->buf，而不是sdshdr，這還要?dú)w因于sds.c中的方法sdsnewlen返回的buf部份，而不是全部sdshdr</span>
void *ptr;
} robj;
對(duì)象類型有：
#define REDIS_STRING 0 // 字符串
#define REDIS_LIST 1 // 列表
#define REDIS_SET 2 // 集合
#define REDIS_ZSET 3 // 有序集
#define REDIS_HASH 4 // 哈希表
對(duì)象編碼有：
#define REDIS_ENCODING_RAW 0 // 編碼為字符串
#define REDIS_ENCODING_INT 1 // 編碼為整數(shù)
#define REDIS_ENCODING_HT 2 // 編碼為哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 編碼為zipmap
#define REDIS_ENCODING_LINKEDLIST 4 // 編碼為雙端鏈表
#define REDIS_ENCODING_ZIPLIST 5 // 編碼為緊縮列表
#define REDIS_ENCODING_INTSET 6 // 編碼為整數(shù)集合
#define REDIS_ENCODING_SKIPLIST 7 // 編碼為跳躍表
2、內(nèi)部數(shù)據(jù)結(jié)構(gòu)之dict（俗稱字典）
1.1 dict結(jié)構(gòu)
Redis使用的是高效且實(shí)現(xiàn)簡(jiǎn)單的哈希作為字典的底層實(shí)現(xiàn)。
dict.h中定義以下：
/*
* 字典
*/
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當(dāng) rehash 不在進(jìn)行時(shí)，值為 ⑴
int rehashidx; /* rehashing not in progress if rehashidx == ⑴ */
// 目前正在運(yùn)行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
哈希表dictht的結(jié)構(gòu)：
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
/*
* 哈希表
*
* 每一個(gè)字典都使用兩個(gè)哈希表，從而實(shí)現(xiàn)漸進(jìn)式 rehash 。
*/
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼，用于計(jì)算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dictht;
哈希表數(shù)組dictEntry的結(jié)構(gòu)：/*
* 哈希表節(jié)點(diǎn)
*/
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個(gè)哈希表節(jié)點(diǎn)，構(gòu)成鏈表
struct dictEntry *next;
} dictEntry;
那末1個(gè)dict可以圖解表示為：
由圖可清晰地看出redis字典哈希表所使用的哈希碰撞解決方法是鏈地址法，這個(gè)方法就是使用鏈表將多個(gè)哈希值相同的節(jié)點(diǎn)串聯(lián)在1起，從而解決沖突問(wèn)題。
1.2 dict實(shí)現(xiàn)setCommand
set命令終究會(huì)調(diào)用dict.c中的dictAdd方法將test => "hello redis" 保存到字典中
/* Add an element to the target hash table */
/*
* 嘗試將給定鍵值對(duì)添加到字典中
*
* 只有給定鍵 key 不存在于字典時(shí)，添加操作才會(huì)成功
*
* 添加成功返回 DICT_OK ，失敗返回 DICT_ERR
*
* 最壞 T = O(N) ，平灘 O(1)
*/
int dictAdd(dict *d, void *key, void *val)
{
// 嘗試添加鍵到字典，并返回包括了這個(gè)鍵的新哈希節(jié)點(diǎn)
// T = O(N)
dictEntry *entry = dictAddRaw(d,key);
// 鍵已存在，添加失敗
if (!entry) return DICT_ERR;
// 鍵不存在，設(shè)置節(jié)點(diǎn)的值
// T = O(1)
dictSetVal(d, entry, val);
// 添加成功
return DICT_OK;
}
全部set可簡(jiǎn)略以下圖（此圖省去了許多其它操作）：
從圖中你會(huì)發(fā)現(xiàn)，其實(shí)key的過(guò)期時(shí)間就相當(dāng)因而key的另外一個(gè)val，保存在另外一個(gè)dict中，簡(jiǎn)單地說(shuō)就是有兩個(gè)dict，1個(gè)是key=>value，1個(gè)是key=>expire。
1.3 dict哈希表的rehash
dict有兩個(gè)ht，就是每一個(gè)字典有兩個(gè)哈希表，為毛要有兩個(gè)，其作用是對(duì)dict進(jìn)行擴(kuò)容和收縮，由于如果節(jié)點(diǎn)數(shù)量比哈希表的大小要大很多的話，那末哈希表就會(huì)退化成多個(gè)鏈表，哈希表本身的性能優(yōu)勢(shì)就不再存在。
dict.c中的_dictExpandIfNeeded方法對(duì)哈希表什么時(shí)候可rehash作了判斷：
// 1下兩個(gè)條件之1為真時(shí)，對(duì)字典進(jìn)行擴(kuò)大
// 1）字典已使用節(jié)點(diǎn)數(shù)和字典大小之間的比率接近 1：1
// 并且 dict_can_resize 為真
// 2）已使用節(jié)點(diǎn)數(shù)和字典大小之間的比率超過(guò) dict_force_resize_ratio（默許值為5）
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
// 新哈希表的大小最少是目前已使用節(jié)點(diǎn)數(shù)的兩倍
// T = O(N)
return dictExpand(d, d->ht[0].used*2);
<span style="white-space:pre"> </span>//dictExpand的進(jìn)程就是獲得ht[0]的size,然后copy到ht[1]中，就是table大小是目錄使用節(jié)點(diǎn)數(shù)的兩倍。最后再將rehashidx設(shè)為0，標(biāo)識(shí)著可以進(jìn)行rehash了
}
rehash的代碼這里不貼出，由于實(shí)現(xiàn)簡(jiǎn)單，大致的進(jìn)程是
1. 釋放ht[0] 的空間；
2. 用ht[1] 來(lái)代替ht[0] ，使原來(lái)的ht[1] 成為新的ht[0] ；
3. 創(chuàng)建1個(gè)新的空哈希表，并將它設(shè)置為ht[1] ；
4. 將字典的rehashidx 屬性設(shè)置為⑴ ，標(biāo)識(shí)rehash 已停止；
但我在看源代碼時(shí)，發(fā)現(xiàn)其實(shí)不是1將rehashidx設(shè)為0就進(jìn)行rehash操作的，而是當(dāng)再次dictAdd時(shí)，才dictRehash(d,1)，第2個(gè)參數(shù)是1，也就是說(shuō)每次rehash只會(huì)對(duì)單個(gè)索引上的節(jié)點(diǎn)進(jìn)行遷移，這類做法幾近不會(huì)消耗甚么時(shí)間，客戶端可以快速的得到響應(yīng)。固然這類除這類方式進(jìn)行rehash外，Redis還有個(gè)定時(shí)任務(wù)調(diào)用dictRehashMilliseconds方法，在規(guī)定的時(shí)間內(nèi)，盡量地對(duì)http://www.jyygyx.com/db/字典中那些需要rehash的字典進(jìn)行rehash，從而加速rehash的進(jìn)程。
現(xiàn)在我知道Redis其實(shí)不是1下子就rehash完成，而是需要1定時(shí)間的，那末如果客戶端在這段時(shí)間內(nèi)向Redis發(fā)送get set del要求，那Redis會(huì)如何處理，從而保證數(shù)據(jù)的完全和正確呢？
? 由于在rehash 時(shí)，字典會(huì)同時(shí)使用兩個(gè)哈希表，所以在這期間的所有查找、刪除等操作，除在ht[0] 上進(jìn)行，還需要在ht[1] 上進(jìn)行。
? 在履行添加操作時(shí)，新的節(jié)點(diǎn)會(huì)直接添加到ht[1] 而不是ht[0] ，這樣保證ht[0] 的節(jié)點(diǎn)數(shù)量在全部rehash 進(jìn)程中都只減不增。
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
