Redis對(duì)象
在了解Redis數(shù)據(jù)結(jié)構(gòu)的時(shí)候我們會(huì)學(xué)習(xí)到簡(jiǎn)單動(dòng)態(tài)字符串，壓縮鏈表等俐镐。
但Redis并沒(méi)有直接使用這些數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)鍵值對(duì)數(shù)據(jù)庫(kù)，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個(gè)對(duì)象系統(tǒng)彭雾，這個(gè)系統(tǒng)包含字符串對(duì)象抄沮、列表對(duì)象、哈希對(duì)象粥庄、集合對(duì)象和有序集合對(duì)象這五種類(lèi)型的對(duì)象丧失。Redis使用對(duì)象表示鍵和值，每次新建一個(gè)鍵值對(duì)時(shí)惜互，我們就創(chuàng)建了兩個(gè)對(duì)象布讹。
集合對(duì)象
intset編碼
創(chuàng)建一個(gè)intset編碼的集合對(duì)象
127.0.0.1:6379> sadd nums 1 2 3 5
(integer) 4
127.0.0.1:6379>
127.0.0.1:6379> type nums
set
127.0.0.1:6379> object encoding nums
"intset"
所有元素都被直接包含在一個(gè)整數(shù)集合里
hashtable編碼
當(dāng)傳入字符時(shí)训堆，變?yōu)閔ashtable編碼
127.0.0.1:6379> sadd nums "hello"
(integer) 1
127.0.0.1:6379> object encoding nums
"hashtable"
hashtable編碼的集合對(duì)象底層由字典實(shí)現(xiàn)描验。字典的鍵就是集合的內(nèi)容，值為null坑鱼。
Redis字典的底層實(shí)現(xiàn)
redis字典所使用的hash表結(jié)構(gòu)
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
//哈希表大小掩碼膘流，用于計(jì)算索引值
//總是等于size-1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dictht;
table屬性是一個(gè)數(shù)組絮缅，數(shù)組中的每個(gè)元素都是一個(gè)指向dictEntry結(jié)構(gòu)的指針，每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對(duì)呼股。size屬性記錄了哈希表的大小耕魄，也即是table數(shù)組的大小，而used屬性則記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對(duì)）的數(shù)量彭谁。sizemask屬性的值總是等于size-1吸奴，這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到table數(shù)組的哪個(gè)索引上面。
一個(gè)空的hash表
dictEntry*[4]是一個(gè)數(shù)組缠局，數(shù)組里的每一元素都指向一個(gè)dictEntry結(jié)構(gòu)则奥，dictEntry包含3個(gè)屬性，key狭园，value逞度，發(fā)生散列沖突時(shí)指向下一個(gè)節(jié)點(diǎn)的指針next。結(jié)構(gòu)如下妙啃，看得出是使用鏈地址法解決散列沖突档泽。
redis的字典是通過(guò)hash表來(lái)實(shí)現(xiàn)的
redis字典結(jié)構(gòu)
typedef struct dict {
// 類(lèi)型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
//當(dāng)rehash不在進(jìn)行時(shí)，值為-1
in trehashidx;
/* rehashing not in progress if rehashidx == -1 */
} dict;
type屬性和privdata屬性是針對(duì)不同類(lèi)型的鍵值對(duì)揖赴，為創(chuàng)建多態(tài)字典而設(shè)置的：·type屬性是一個(gè)指向dictType結(jié)構(gòu)的指針馆匿，每個(gè)dictType結(jié)構(gòu)保存了一簇用于操作特定類(lèi)型鍵值對(duì)的函數(shù)，Redis會(huì)為用途不同的字典設(shè)置不同的類(lèi)型特定函數(shù)燥滑〗ケ保·而privdata屬性則保存了需要傳給那些類(lèi)型特定函數(shù)的可選參數(shù)。
而redis字典保存兩個(gè)hash表铭拧，當(dāng)我們新建一個(gè)redis字典時(shí)赃蛛，默認(rèn)使用ht[0] hash表，結(jié)構(gòu)如下
redis字典為什么要維護(hù)兩個(gè)hash表搀菩？
redis字典為了控制創(chuàng)建的hash表的空間開(kāi)銷(xiāo)呕臂，redis會(huì)動(dòng)態(tài)調(diào)整hash表的空間大小，當(dāng)ht[0]的長(zhǎng)度滿(mǎn)了肪跋，這里的ht[0]滿(mǎn)了并不是指dictEntry數(shù)組里面每一個(gè)元素都存儲(chǔ)了一個(gè)dictEntry歧蒋，而是dictht的used和size相同，可能有部分dictEntry會(huì)發(fā)生散列沖突的州既。
此時(shí)再向字典添加元素谜洽，此時(shí)redis字典就會(huì)進(jìn)行擴(kuò)容。
首先對(duì)ht[1進(jìn)行擴(kuò)容吴叶，擴(kuò)容的大小為比當(dāng)前當(dāng)前容量大的2的n次方阐虚，目標(biāo)大小必須為2的n次方，這樣系統(tǒng)進(jìn)行內(nèi)存分配的效率才有保證蚌卤，比如當(dāng)前容量ht[0]的容量為4实束，那么擴(kuò)容的大小就應(yīng)該為2的3次方也就是8.再將ht[0]的內(nèi)容遷移到ht[1]此時(shí)redis字典的結(jié)構(gòu)如下
這樣就可以減少hash表的內(nèi)存占用贸宏，不夠的時(shí)候就擴(kuò)容hash表。這種方法雖然節(jié)約了內(nèi)存磕洪，但如果hash表已經(jīng)很長(zhǎng)了的時(shí)候，此時(shí)再擴(kuò)容它的內(nèi)存再分配的規(guī)慕肓可能就會(huì)很大析显，造成性能影響。因此签赃，為了避免rehash對(duì)服務(wù)器性能造成影響谷异，服務(wù)器不是一次性將ht[0]里面的所有鍵值對(duì)全部rehash到ht[1]，而是分多次锦聊、漸進(jìn)式地將ht[0]里面的鍵值對(duì)慢慢地rehash到ht[1]歹嘹。
以下是哈希表漸進(jìn)式rehash的詳細(xì)步驟：
1）為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表孔庭。
2）在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx尺上，并將它的值設(shè)置為0，表示rehash工作正式開(kāi)始圆到。
3）在rehash進(jìn)行期間怎抛，每次對(duì)字典執(zhí)行添加、刪除芽淡、查找或者更新操作時(shí)马绝，程序除了執(zhí)行指定的操作以外，還會(huì)順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]挣菲，當(dāng)rehash工作完成之后富稻，程序?qū)ehashidx屬性的加一。
4）隨著字典操作的不斷執(zhí)行白胀，最終在某個(gè)時(shí)間點(diǎn)上椭赋，ht[0]的所有鍵值對(duì)都會(huì)被rehash至ht[1]，這時(shí)程序?qū)ehashidx屬性的值設(shè)為-1或杠，表示rehash操作已完成纹份。
集合的相關(guān)命令
