String
使用SDS（simple dynamic string）實(shí)現(xiàn)损俭。
3.2版本前
struct sdshdr {
//長(zhǎng)度
int len;
//剩余長(zhǎng)度
int free;
//數(shù)據(jù)本體
char buf[];
}
3.2版本以后
主要有以下幾個(gè)字段
- len 長(zhǎng)度蛙奖，有uint8_t、uint16_t杆兵、uint64_t 這幾種類型
- alloc 已經(jīng)分配的空間雁仲，有uint8_t、uint16_t琐脏、uint64_t 這幾種類型
- unsigned char flags 表示類型攒砖，在最小長(zhǎng)度中還會(huì)使用len的功能
- char buf[] 具體數(shù)據(jù)存儲(chǔ)的地方
詳細(xì)情況如下所示
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];// buf[0]: z: 0101001
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
擴(kuò)容策略
字符串在長(zhǎng)度小于1M之前，擴(kuò)容空間采用加倍策略日裙，也就是保留100%的冗余空間吹艇。
當(dāng)長(zhǎng)度超過(guò)1M之后，為了避免加倍后的冗余空間過(guò)大而導(dǎo)致浪費(fèi)昂拂，每次擴(kuò)容只會(huì)多分配1M大小的冗余空間受神。
為什么不直接使用原生C語(yǔ)言的字符串
- 原生C語(yǔ)言字符串是通過(guò)\0結(jié)尾，想要知道字符串長(zhǎng)度政钟，需要通過(guò)O(n)的時(shí)間復(fù)雜度的strlen標(biāo)準(zhǔn)函數(shù)庫(kù)來(lái)獲嚷房恕（遍歷掃描），Redis是單線程的养交，性能需要做優(yōu)化。
- redis作為開源中間件瓢宦，可能接受很多類型語(yǔ)言的調(diào)用碎连，其他類型語(yǔ)言如果將\0作為字符串的一部分提供給redis，若此時(shí)reids使用C語(yǔ)言原生庫(kù)驮履，則無(wú)法支持鱼辙。
List
舊版本：數(shù)據(jù)量少時(shí)候用ziplist廉嚼，數(shù)據(jù)量多的時(shí)候使用linkedlist
新版本：使用QuickList 參見(jiàn)下文
Hash（字典）
存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)
zipList
當(dāng)數(shù)據(jù)量比較小或者單個(gè)元素比較小時(shí)，底層用zipList存儲(chǔ)倒戏。
hash-max-ziplist-entries 512 ziplist元素超過(guò)512怠噪，將其改為hashtable編碼
hash-max-ziplist-value 64 單個(gè)元素大小超過(guò)64byte時(shí)，將其改為hashtable編碼
dict
struct dict {
dictht ht[2]
}
dict結(jié)構(gòu)內(nèi)部包含兩個(gè)hashtable杜跷，通常情況下只會(huì)使用一個(gè)hashtable傍念。在dict擴(kuò)容縮容的時(shí)候，需要重新分配hashtable葛闷，然后進(jìn)行漸進(jìn)式搬遷憋槐，這個(gè)時(shí)候兩個(gè)hashtable存儲(chǔ)的分別是舊的hashtable和新的hashtable。待搬遷結(jié)束后淑趾，舊的hashtable被刪除阳仔，新的hashtable取而代之。hashtable的結(jié)構(gòu)和java的hashmap幾乎是一樣的扣泊，通過(guò)鏈表的方式解決hash沖突近范，第一維是數(shù)據(jù)，第二維是鏈表延蟹。數(shù)據(jù)中存儲(chǔ)的是第二維鏈表的第一個(gè)元素的指針顺又。
漸進(jìn)式搬遷
大字典的擴(kuò)容是比較耗時(shí)間的，需要重新申請(qǐng)新的數(shù)組等孵，然后將舊字典所有鏈表中的元素重新掛接到像新的數(shù)組下面稚照，這是一個(gè)O(n)級(jí)別的操作，會(huì)非常耗時(shí)俯萌，所以redis使用漸進(jìn)式rehash小步搬遷果录，在hset 和hdel命令中埋伏了搬遷操作。如果客戶端空閑了咐熙，沒(méi)有后續(xù)命令弱恒，則redis會(huì)在定時(shí)任務(wù)中搬遷。
擴(kuò)容條件
正常情況下棋恼，當(dāng)hash表中的元素的個(gè)數(shù)等于第一維數(shù)組的長(zhǎng)度時(shí)返弹，就會(huì)開始擴(kuò)容，擴(kuò)容的新組是原數(shù)組大小的2倍爪飘。不過(guò)若Redis正在做bgsave义起，為了減少內(nèi)存頁(yè)的過(guò)多分離（copy on write），Redis盡量不去擴(kuò)容（dict_can_resize）师崎，但是如果hash表已經(jīng)非常滿了默终，元素的個(gè)數(shù)已經(jīng)達(dá)到了第一維數(shù)組長(zhǎng)度的5倍（dict_forece_resize_ratio），說(shuō)明hash表已經(jīng)過(guò)于擁擠了，這個(gè)時(shí)候就會(huì)強(qiáng)制擴(kuò)容齐蔽。
縮容條件
當(dāng)hash表因?yàn)樵氐闹麈I刪除變得越來(lái)越稀疏時(shí)两疚，Redis會(huì)對(duì)hash進(jìn)行縮容來(lái)減少hash表的第一維數(shù)組空間占用『危縮容條件是元素個(gè)數(shù)低于數(shù)組長(zhǎng)度的10%诱渤。縮容不會(huì)考慮Redis是否正在做bgsave
Set
intset
當(dāng)set集合容納單元素都是整數(shù)并且元素個(gè)數(shù)比較少時(shí)谈况，使用intset來(lái)存儲(chǔ)元素
set-max-int-set-entries 512 intset能存儲(chǔ)的最大元素個(gè)數(shù)勺美，超過(guò)則使用hashtable編碼
圖示
hashtable
與Hash相同，不過(guò)value都是null
ZSet(Sorted Set)
數(shù)據(jù)量少的時(shí)候鸦做，用ziplist實(shí)現(xiàn)
數(shù)據(jù)量多的時(shí)候励烦，zset內(nèi)部實(shí)現(xiàn)是一個(gè)hash字典加一個(gè)跳躍鏈表（skiplist）
ZipList（壓縮列表）
設(shè)計(jì)目的是為了提高存儲(chǔ)效率∑糜眨可以用于存儲(chǔ)字符串或整數(shù)坛掠，其中整數(shù)是按真正的二進(jìn)制表示進(jìn)行編碼的，而不是編碼成字符串序列治筒。ziplist能以O(shè)(1)的時(shí)間復(fù)雜度在表的兩端提供push和pop操作屉栓。
圖示
增加元素
插入一個(gè)新元素需要realloc擴(kuò)展內(nèi)存，取決于內(nèi)存分配器的算法和當(dāng)前的ziplist耸袜，如果realloc可能需要重新分配新的內(nèi)存空間友多，并將之前的內(nèi)容一次性拷貝到新的地址，也可在原有的地址上進(jìn)行擴(kuò)容堤框。
級(jí)聯(lián)更新
由于每個(gè)entry都會(huì)有一個(gè)prerawlan域滥，如果內(nèi)容小于254，則prerawlen使用一個(gè)字節(jié)蜈抓，否則就是5個(gè)字節(jié)启绰。那么某個(gè)entry進(jìn)過(guò)了修改操作從253字節(jié)變成了254字節(jié)，那么它的下一個(gè)entry的prerawlen就需要更新沟使，從1個(gè)字節(jié)擴(kuò)展到5個(gè)字節(jié)：如果這個(gè)entry的長(zhǎng)度本來(lái)也是253字節(jié)委可，那么后面的entry的prerawlen字段還得繼續(xù)更新。
如果ziplist里面的每個(gè)entry加好都存儲(chǔ)了253字節(jié)的內(nèi)容腊嗡，那么第一個(gè)entry內(nèi)容的修改就會(huì)導(dǎo)致后續(xù)所有entry的級(jí)聯(lián)更新着倾。
未來(lái)發(fā)展
可能會(huì)被listpack（緊湊列表）代替
quickList（快速列表）
ziplist和linkedlist的混合體
圖示
每個(gè)ziplist存儲(chǔ)多少元素
quicklist內(nèi)部默認(rèn)單個(gè)ziplist長(zhǎng)度為8k字節(jié)，超出了這個(gè)字節(jié)長(zhǎng)度燕少，就會(huì)起一個(gè)新的ziplist卡者。ziplist的長(zhǎng)度由配置list-max-ziplist-size決定
壓縮深度
quicklist默認(rèn)的壓縮深度是0，也就是不壓縮棺亭。實(shí)際壓縮深度由配置參數(shù)list-compress-depth決定虎眨。為了支持快讀的push/pop操作蟋软，queicklist的首尾兩個(gè)ziplist不壓縮镶摘，此時(shí)深度為1嗽桩。如果深度為2，就表示quicklist首尾第一個(gè)ziplist以及首尾第二個(gè)ziplist都不壓縮凄敢。
Skiplist（跳躍鏈表）
類似于跳表的結(jié)構(gòu)碌冶，不同點(diǎn)如下
圖示
查找過(guò)程
類似于跳表
隨機(jī)層高
對(duì)于新插入節(jié)點(diǎn)，都需要調(diào)用一個(gè)隨機(jī)算法給他分配一個(gè)合理的層高涝缝，每層晉升概率大概是50%.
redis標(biāo)準(zhǔn)源碼中晉升概率只有25%扑庞，相對(duì)官方跳躍鏈表更加扁平化。
插入過(guò)程
首先我們?cè)谒阉骱线m的插入點(diǎn)的過(guò)程中將[搜索路徑]摸出來(lái)了拒逮，然后就可以開始創(chuàng)建新節(jié)點(diǎn)了罐氨，創(chuàng)建的時(shí)候需要給這個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)層數(shù)，再將搜索路徑上的節(jié)點(diǎn)和這個(gè)新節(jié)點(diǎn)通過(guò)向前向后指針串起來(lái)滩援。如果分配的新節(jié)點(diǎn)的高度高于當(dāng)前跳躍列表最大高度栅隐，就要更新一下跳躍列表的最大高度。
更新過(guò)程
當(dāng)我們調(diào)用zadd方法時(shí)玩徊，如果對(duì)應(yīng)的value不存在租悄，就是插入過(guò)程。如果value已經(jīng)存在了恩袱，只是調(diào)整一下score值泣棋，就是更新過(guò)程。如果score值不會(huì)帶來(lái)排序位置改變畔塔，那么更新就能返回潭辈。（該邏輯已經(jīng)被redis官方接受）如果排序位置改變了，就需要調(diào)整位置澈吨。
調(diào)整位置
簡(jiǎn)單的策略就是先刪除值把敢，再插入這個(gè)元素，需要經(jīng)過(guò)兩次路徑搜索棚辽。
如何計(jì)算排名
redis在skiplist的forward指針上進(jìn)行了優(yōu)化技竟，給每個(gè)forward指針都增加了span屬性，span是跨度的意思屈藐，表示從前一個(gè)節(jié)點(diǎn)沿著當(dāng)前層的forward指針跳到當(dāng)前這個(gè)節(jié)點(diǎn)中間會(huì)跳過(guò)多少個(gè)節(jié)點(diǎn)榔组。redis在插入刪除操作時(shí)會(huì)更新span值。這樣在計(jì)算一個(gè)元素的排名時(shí)联逻，只需要將搜索路徑上進(jìn)過(guò)的所有節(jié)點(diǎn)span值進(jìn)行疊加搓扯，就可以計(jì)算出元素的最終rank值。
