本文簡(jiǎn)單記錄redis目前支持的5種數(shù)據(jù)類型。和他們底層的數(shù)據(jù)結(jié)構(gòu)以及需要關(guān)注的點(diǎn)冤竹。
基礎(chǔ)結(jié)構(gòu)和底層類型
類型STRING
三種底層類型 分別是
int,embstr,raw
如果是純數(shù)字墩衙，使用int表示闸氮，如果保存的是字符串，并且小于39個(gè)字節(jié)货抄，則使用embstr結(jié)構(gòu)表示述召，否則 使用raw類型表示秽浇。
首先使用數(shù)字類型表示一個(gè)健肯定是最節(jié)省內(nèi)存的。并且進(jìn)行比較和共享等操作也是復(fù)雜度最低的贯莺。所以如果是數(shù)字則優(yōu)先使用int結(jié)構(gòu)表示
如果是字符串孙咪，要注意 ： embstr是針對(duì)短字符串的一種優(yōu)化編碼方式，這個(gè)編碼和raw編碼一樣 都使用redisObject和sdshdr結(jié)構(gòu)來(lái)表示字符串對(duì)象夺刑。但是raw編碼會(huì)調(diào)用兩次內(nèi)存分配函數(shù)來(lái)分別創(chuàng)建redisObject結(jié)構(gòu)和sdshdr結(jié)構(gòu)缅疟。而embstr編碼則通過(guò)調(diào)用一次內(nèi)存分配函數(shù)來(lái)分配一塊連續(xù)的空間，空間依次包含redisObject和sdshdr兩個(gè)結(jié)構(gòu)遍愿。因此可以說(shuō)使用embstr能夠提升性能存淫，內(nèi)存釋放也比較快。另外使用的是連續(xù)的內(nèi)存沼填，也能有效利用緩存桅咆。
可以使用命令：object encoding $key 這個(gè)命令來(lái)查看某個(gè)key具體使用的是哪種結(jié)構(gòu)。
struct sdshdr {
//記錄buf數(shù)組已經(jīng)使用的字節(jié)數(shù)量坞笙，等于sds所保存的字符串長(zhǎng)度
int len;
//記錄buf數(shù)組種未使用的字節(jié)數(shù)量
int free;
//字節(jié)數(shù)組岩饼，用于保存字符串
char buf[];
};
另外，sds可以通過(guò)一些方式減少字符串修改所帶來(lái)的內(nèi)存重分配次數(shù)薛夜。從而獲得更好的性能
- 空間預(yù)分配
可以看到上面的結(jié)構(gòu)有一個(gè)free字段籍茧。如果對(duì)sds修改之后，sds的長(zhǎng)度（len）小于1M梯澜，那么程序分配和len屬性相同大小的未使用空間（free)
如果修改sdks之后寞冯，它的長(zhǎng)度大于1M，那么程序會(huì)分配和1M的未使用空間腊徙。通過(guò)這個(gè)預(yù)分配简十，redis可以減少連續(xù)執(zhí)行執(zhí)行字符串增長(zhǎng)操作所需要的內(nèi)存重新分配的次數(shù)。 - 惰性空間釋放
這個(gè)特性用于優(yōu)化sds的字符串縮短操作撬腾。當(dāng)sds需要縮短保存的字符串時(shí)螟蝙，程序不會(huì)立即執(zhí)行內(nèi)存重分配來(lái)?yè)]手多出來(lái)的字節(jié)。而是使用free屬性吧這些字節(jié)數(shù)量記錄起來(lái)民傻，等待將來(lái)使用胰默。
二進(jìn)制安全相關(guān)
所有的sds的api提供的是以二進(jìn)制的方式來(lái)處理sds存放在buf里面的數(shù)據(jù)的。并沒(méi)有做任何的限制或者過(guò)濾漓踢。存入的時(shí)候時(shí)什么牵署，取出的時(shí)后就是什么。
類型LIST
兩種底層數(shù)據(jù)結(jié)構(gòu)
ziplist,linkedlist
當(dāng)列表的對(duì)象同時(shí)滿足下面兩個(gè)條件的時(shí)候喧半，列表對(duì)象會(huì)使用ziplist編碼：
- 列表對(duì)象保存的所有字符串元素長(zhǎng)度都小于64字節(jié)
- 列表對(duì)象保存的元素?cái)?shù)量小于512個(gè)
鏈表特性
- 雙端：鏈表節(jié)點(diǎn)帶有prev 和 next指針奴迅，獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的復(fù)雜度都是O(1).
- 無(wú)環(huán)：表頭的prev和表尾的next指針指向的都是null，對(duì)鏈表的訪問(wèn)以null作為終點(diǎn)挺据。
- 獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)以及長(zhǎng)度屬性的時(shí)間復(fù)雜度都是O(1)
壓縮列表
壓縮列表時(shí)redis為了節(jié)約內(nèi)存而開發(fā)的取具，是由一系列的特殊編碼的連續(xù)內(nèi)存塊組成的順序行內(nèi)存結(jié)構(gòu)脖隶。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值暇检。
- 結(jié)構(gòu)
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
|---|
- 說(shuō)明
| 屬性 | 類型 | 長(zhǎng)度 | 用途 |
|---|---|---|---|
| zlbytes | unit32_t | 4字節(jié) | 記錄壓縮列表占用內(nèi)存字節(jié)數(shù) |
| zltail | uint32_t | 4 | 記錄壓縮列表尾節(jié)點(diǎn)距離壓縮列表的其實(shí)地址由多少字節(jié)：通過(guò)這個(gè)偏移量产阱，程序可以直接定位尾節(jié)點(diǎn)的地址 |
| zllen | uint32_t | 2 | 記錄了壓縮列表的節(jié)點(diǎn)數(shù)量 |
| entryX | 列表節(jié)點(diǎn) | 不定 | 各個(gè)節(jié)點(diǎn)，長(zhǎng)度由保存的內(nèi)容決定 |
| zlend | uint8_t | 1 | 特殊值：0xff(255) ,標(biāo)記壓縮列表的結(jié)束 |
類型HASH
兩種底層結(jié)構(gòu)
ziplist,hash
當(dāng)hash對(duì)象滿足下面兩個(gè)條件的時(shí)候块仆，hash才使用ziplist編碼
- hash對(duì)象所保存的所有鍵值對(duì)的健和值的字符串長(zhǎng)度都<64字節(jié)构蹬。
- hash對(duì)象保存的鍵值對(duì)數(shù)量小于512個(gè)
ziplist編碼的hash對(duì)象使用壓縮列表作為底層實(shí)現(xiàn)。每當(dāng)有新的對(duì)象加入到hash對(duì)象時(shí)悔据，程序先將保存了健的壓縮列表節(jié)點(diǎn)推入壓縮列表尾部庄敛。再將保存了值的壓縮列表節(jié)點(diǎn)推到尾部。因此：
保存了同一鍵值對(duì)的兩個(gè)節(jié)點(diǎn)總是緊湊的挨在一起蜜暑。健的節(jié)點(diǎn)在前铐姚，值的節(jié)點(diǎn)在后； ziplist的結(jié)構(gòu)參看上一小結(jié)肛捍。
字典是由hash表實(shí)現(xiàn)的，hash表里面保存的是hash節(jié)點(diǎn)的數(shù)組之众。先看hash的結(jié)構(gòu)
//redis 字典所使用的hash表結(jié)構(gòu)
typedef struct dictht {
//hash表數(shù)組
dictEntry **table;
//hash表大小
unsigned long size;
//hash表大小掩碼拙毫，用于計(jì)算索引
unsigned long sizemask;
//該hash表 已經(jīng)有的節(jié)點(diǎn)數(shù)量
unsigned long used;
}
//hash 表結(jié)構(gòu)用到的hash表節(jié)點(diǎn)的結(jié)構(gòu)
typedef struct dictEntry {
//健
void *key;
//值
union{
void *val;
uint64_t u64;
int64_t s64;
}
//指向下一個(gè)節(jié)點(diǎn) ，形成一個(gè)鏈表
struct dictEntry *next;
}
字典結(jié)構(gòu)如下 棺禾，使用了hash的類型
typedef struct dict{
//類型特定函數(shù)
dictType *type;
//私有數(shù)據(jù)
void *privdata;
//hash表
dictht ht[2];
//rehash 索引 當(dāng)rehash沒(méi)有在進(jìn)行是缀蹄，值為-1
int trehashidx;
}
hash表的擴(kuò)展和收縮
當(dāng)一下條件被滿足時(shí)，程序會(huì)對(duì)hash表執(zhí)行擴(kuò)展：
- 服務(wù)器目前沒(méi)有在執(zhí)行bgsave或者bgrewriteaof命令膘婶，并且hash表的負(fù)載因子大于1
- 服務(wù)器目前正在執(zhí)行bgsave或者bgrewriteaof命令缺前，并且hash表的負(fù)載因子大于
負(fù)載銀子計(jì)算公式：
負(fù)載因子 = hash表已保存的節(jié)點(diǎn)數(shù)量 / hash表大小
另一方面： 當(dāng)hash表的負(fù)載因子小于0.1時(shí)，程序自動(dòng)執(zhí)行收縮操作悬襟。
rehash
從上面的字典的數(shù)據(jù)接口衅码，可以看到dict由2個(gè)大小。ht屬性是一個(gè)包含2個(gè)項(xiàng)的數(shù)組脊岳。每個(gè)項(xiàng)都是dictht hash表逝段，一般情況下，字典只使用ht[0] hash表割捅，ht[1]hash表只會(huì)在對(duì)ht[0]進(jìn)行 rehash的情況下使用奶躯。
對(duì)hash表進(jìn)行rehash的步驟
- 為字典的ht[1]hash表分配空間，這個(gè)hash表的空間的大小取決于要執(zhí)行的操作亿驾，以及ht[0]當(dāng)前包含的鍵值對(duì)的數(shù)量（ht[0].used的值）
- 如果執(zhí)行的時(shí)擴(kuò)展操作嘹黔，那么ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2的n次冪
- 如果執(zhí)行的是收縮操作，那么ht[1]的大小為第一個(gè)大于等于ht[0]的2的n次冪
- 將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上面：rehash指的是重新計(jì)算健的hash值和索引值莫瞬，然后將健放到ht[1]對(duì)應(yīng)的hash表指定位置上儡蔓。
- 當(dāng)ht[0]包含的所有鍵值對(duì)都遷移到了ht[1]之后(ht[0]為空表)醉锄，釋放ht[0],將ht[1]設(shè)置為ht[0],并在ht[1]設(shè)置為一個(gè)空白hash表，為下一次rehash做準(zhǔn)備
上面的操作實(shí)際上是漸進(jìn)式執(zhí)行的浙值。因?yàn)橐粋€(gè)hash可能有上億元素恳不，如果一下子執(zhí)行，會(huì)導(dǎo)致服務(wù)器卡頓或者段時(shí)間無(wú)法提供服務(wù)开呐。rehash開始的時(shí)候 烟勋，會(huì)吧rehashidx設(shè)置為0，表示rehash開始了筐付。在rehash進(jìn)行期間卵惦，增加、刪除瓦戚、查找沮尿、更新等操作，會(huì)順帶對(duì)ht[0]的rehashidx屬性值加一较解，等全部完成畜疾。rehashidx會(huì)值-1.
在執(zhí)行rehash期間 ，外部的訪問(wèn)印衔。 對(duì)字典進(jìn)行刪除啡捶，查找，更新等操作會(huì)在兩個(gè)hash表上進(jìn)行奸焙。增加操作會(huì)在ht[1]上進(jìn)行瞎暑。保證ht[0]上沒(méi)有任何添加操作。
類型SET
底層數(shù)據(jù)結(jié)構(gòu)
intset,hash
當(dāng)集合中的元素都是整數(shù)的時(shí)候与帆，使用intset作為底層實(shí)現(xiàn)了赌。intset條件如下
- 集合對(duì)象保存的所有元素都是整數(shù)值
- 集合對(duì)象保存的元素?cái)?shù)量不會(huì)超過(guò)512個(gè)
整數(shù)集合的數(shù)據(jù)結(jié)構(gòu)
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素?cái)?shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}
contents 數(shù)組是整數(shù)集合的底層實(shí)現(xiàn):整數(shù)集合的每個(gè)元素都是contents數(shù)組的一個(gè)item，各個(gè)item在數(shù)組中按值的大小從小到大排列玄糟，并且不包含重復(fù)項(xiàng)勿她。
類型ZSET
底層數(shù)據(jù)結(jié)構(gòu)
ziplist,skiplist+hash
當(dāng)zset滿足下面條件時(shí)，使用ziplist結(jié)構(gòu)
- 集合元素小于128個(gè)
- 集合的所有元素成員長(zhǎng)度小于64字節(jié)
ziplist作為底層實(shí)現(xiàn)的時(shí)候茶凳，每個(gè)元素使用2個(gè)挨在一起的壓縮列表來(lái)保存嫂拴，第一個(gè)節(jié)點(diǎn)是成員（member),第二個(gè)節(jié)點(diǎn)是分值（score）。壓縮列表內(nèi)的集合元素按照大小從小到大排序贮喧，分值較小的元素排在表頭為止筒狠，反之在表尾。
skiplist作為底層實(shí)現(xiàn)的時(shí)候箱沦，一個(gè)zset同時(shí)包含一個(gè)字典和一個(gè)跳表
typedef struct zset{
zskiplist *zsl;
dict *dict;
}
這種結(jié)構(gòu)中辩恼，zsl跳表按分值從小到大保存了所有的集合元素，每個(gè)跳表節(jié)點(diǎn)都保存了一個(gè)集合元素：跳表節(jié)點(diǎn)的object保存了元素的成員，而節(jié)點(diǎn)的score保存了分值灶伊。通過(guò)這個(gè)跳表疆前，程序可以進(jìn)行有序的范圍型操作，比如
zrank,zrange就是使用跳表api實(shí)現(xiàn)聘萨。
另外dict為有序集合創(chuàng)建了一個(gè)從成員到分值的映射竹椒，字典中每個(gè)鍵值都保存了一個(gè)集合元素。通過(guò)這個(gè)字典米辐，程序可以通過(guò)O(1)的復(fù)雜度獲取分值（zscore）胸完。雖然它使用2個(gè)結(jié)構(gòu)來(lái)保存數(shù)據(jù)，但是兩種結(jié)構(gòu)會(huì)通過(guò)指針來(lái)共享相同元素的成員和分值翘贮，所以不會(huì)浪費(fèi)額外的內(nèi)存赊窥。
跳表
- 跳表是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過(guò)每個(gè)節(jié)點(diǎn)種維持多個(gè)其他節(jié)點(diǎn)的指針狸页，從而達(dá)到快速訪問(wèn)的目的锨能。
- 跳表支持平均O(logN),最壞O(N)的復(fù)雜度查找節(jié)點(diǎn)，還可以通過(guò)順序操作來(lái)批量處理節(jié)點(diǎn)芍耘。
- 大部分情況下址遇，跳表的效率可以和平衡樹媲美，并且跳表的實(shí)現(xiàn)比平衡樹簡(jiǎn)單齿穗。
更多跳表的介紹參考
https://blog.csdn.net/pcwl1206/article/details/83512600
