前言
本章接著上一節(jié)繼續(xù)介紹 Redis 的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)中的Hash字典.
基本介紹
Hash 也可以用來(lái)存儲(chǔ)用戶信息,和 String 不同的是 Hash 可以對(duì)用戶信息的每個(gè)字段單獨(dú)存儲(chǔ),String 則需要序列化用戶的所有字段后存儲(chǔ).并且 String 需要以整個(gè)字符串的形式獲取用戶,而 hash可以只獲取部分?jǐn)?shù)據(jù),從而節(jié)約網(wǎng)絡(luò)流量.不過(guò) hash 內(nèi)存占用要大于 String,這是 hash 的缺點(diǎn).
> hset books java "Effective java"
(integer) 1
> hset books golang "concurrency in go"
(integer) 1
> hget books java
"Effective java"
> hset user age 17
(integer) 1
>hincrby user age 1 #單個(gè) key 可以進(jìn)行計(jì)數(shù) 和 incr 命令基本一致
(integer) 18
Redis 中的 Hash和 Java的 HashMap 更加相似,都是數(shù)組+鏈表的結(jié)構(gòu).當(dāng)發(fā)生 hash 碰撞時(shí)將會(huì)把元素追加到鏈表上.值得注意的是在 Redis 的 Hash 中 value 只能是字符串.
內(nèi)部原理
看完基本介紹之后,我們先來(lái)了解下 hash 的內(nèi)部結(jié)構(gòu).第一維是數(shù)組,第二維是鏈表.組成一個(gè) hashtable.
部分源碼:
struct dictht {
dictEntry **table; //entry 數(shù)組
long size; //數(shù)組長(zhǎng)度
long used //數(shù)組中的元素個(gè)數(shù)
...
}
struct dictEntry{
void *key; //hash 的 key
void *val; //hash 的 value
dictEntry *next; //下一個(gè)dictEntry 鏈表結(jié)構(gòu)
}
在 Java 中 HashMap 擴(kuò)容是個(gè)很耗時(shí)的操作,需要去申請(qǐng)新的數(shù)組,為了追求高性能,Redis 采用了漸進(jìn)式 rehash 策略.這也是 hash 中最重要的部分.
漸進(jìn)式 rehash
在 hash 的內(nèi)部包含了兩個(gè)hashtable,一般情況下只是用一個(gè).如圖所示:
在擴(kuò)容的時(shí)候 rehash 策略會(huì)保留新舊兩個(gè) hashtable 結(jié)構(gòu),查詢時(shí)也會(huì)同時(shí)查詢兩個(gè) hashtable.Redis會(huì)將舊 hashtable 中的內(nèi)容一點(diǎn)一點(diǎn)的遷移到新的 hashtable 中,當(dāng)遷移完成時(shí),就會(huì)用新的 hashtable 取代之前的.當(dāng) hashtable 移除了最后一個(gè)元素之后,這個(gè)數(shù)據(jù)結(jié)構(gòu)將會(huì)被刪除.如圖所示:
數(shù)據(jù)搬遷的操作放在 hash 的后續(xù)指令中,也就是來(lái)自客戶端對(duì) hash 的指令操作.一旦客戶端后續(xù)沒(méi)有指令操作這個(gè) hash.Redis就會(huì)使用定時(shí)任務(wù)對(duì)數(shù)據(jù)主動(dòng)搬遷.
正常情況下,當(dāng) hashtable 中元素的個(gè)數(shù)等于數(shù)組的長(zhǎng)度時(shí),就會(huì)開始擴(kuò)容,擴(kuò)容的新數(shù)組是原數(shù)組大小的 2 倍.如果 Redis 正在做 bgsave(持久化) 時(shí),可能不會(huì)去擴(kuò)容,因?yàn)橐獪p少內(nèi)存頁(yè)的過(guò)多分離(Copy On Write).但是如果 hashtable 已經(jīng)非常滿了,元素的個(gè)數(shù)達(dá)到了數(shù)組長(zhǎng)度的 5 倍時(shí),Redis 會(huì)強(qiáng)制擴(kuò)容.
當(dāng)hashtable 中元素逐漸變少時(shí),Redis 會(huì)進(jìn)行縮容來(lái)減少空間占用,并且縮容不會(huì)受 bgsave 的影響,縮容條件是元素個(gè)數(shù)少于數(shù)組長(zhǎng)度的 10%.
