承接上文redis底層字符串編碼設(shè)計(jì)思想簡(jiǎn)介

ziplist數(shù)據(jù)結(jié)構(gòu)

內(nèi)存會(huì)一次性開(kāi)辟一塊大的連續(xù)的空間，來(lái)存放ziplist。

• zlbytes

32bit內(nèi)存空間，表示ziplist占用的字節(jié)總數(shù)

• zltail

32bit內(nèi)存空間，表示ziplist表中最后一項(xiàng)(entry)在ziplist中的偏移字節(jié)數(shù)，通過(guò)zltail可以很方便的找到最后一項(xiàng)，從而可以在ziplist尾端快速的執(zhí)行push或pop操作。

• zllen

16bit內(nèi)存空間，表示ziplist中數(shù)據(jù)項(xiàng)entry的個(gè)數(shù)

• zlend:255

ziplist最后一個(gè)字節(jié)，是一個(gè)結(jié)束標(biāo)記，值固定等于255

• entry

表示真正存放數(shù)據(jù)的數(shù)據(jù)項(xiàng)，長(zhǎng)度不定

• prerawlen

表示上一個(gè)節(jié)點(diǎn)的數(shù)據(jù)長(zhǎng)度信息。

如果前一個(gè)元素的大小prerawlen等于254，用一個(gè)字節(jié)作為標(biāo)記項(xiàng)，在用4個(gè)字節(jié)描述前一個(gè)元素大小。

ziplist額外的信息最多需要5個(gè)字節(jié)存儲(chǔ)，相比quicklist雙端鏈表的一個(gè)元素需要2個(gè)指針16個(gè)字節(jié)來(lái)說(shuō)節(jié)省很多內(nèi)存開(kāi)銷(xiāo)。

• len

entry中數(shù)據(jù)的長(zhǎng)度

• data

表示當(dāng)前元素里面的真實(shí)數(shù)據(jù)，業(yè)務(wù)數(shù)據(jù)存儲(chǔ)，這是一個(gè)非常緊湊的二進(jìn)制數(shù)據(jù)結(jié)構(gòu)。

連續(xù)的內(nèi)存空間也會(huì)存在弊端？

ziplist放入n多個(gè)元素的時(shí)候，再往里面添加元素，都需要分配新的內(nèi)存空間，并且完成數(shù)據(jù)的完整拷貝。元素比較少還好，但如果元素很多的情況下，會(huì)很消耗性能。

那么就需要借助雙端鏈表來(lái)控制ziplist的大小，如果超過(guò)一定的大小，則分裂成兩個(gè)，保證每個(gè)ziplist不能太大。

quicklist的底層是quicklistNode，quicklistNode指向ziplist。

加一些數(shù)據(jù)，比如加入到ziplist里面去，不需要對(duì)數(shù)據(jù)整個(gè)做偏移，因?yàn)閿?shù)據(jù)已經(jīng)分配到不同的ziplist里面去了，修改數(shù)據(jù)，只需要修改某一個(gè)ziplist就可以了。

這是基于雙端鏈表做的優(yōu)化，可以從前往后遍歷，也可以從后往前遍歷。

接下來(lái)看下lpush源碼

pushGenericCommand

先從redis數(shù)據(jù)庫(kù)獲取數(shù)據(jù)

• c->db

db就是要操作的redis數(shù)據(jù)庫(kù)

• c->argv[1]

比如執(zhí)行l(wèi)push命令

lpush alist a b c

argv[0]就是lpush
argv[1]就是alist

根據(jù)key去db中查找數(shù)據(jù)

• key->ptr

key真正所執(zhí)行的字符串

進(jìn)行rehash操作

-1表示沒(méi)有進(jìn)行rehash，不等于-1表示正在進(jìn)行rehash。

做rehash的方法

篩選非空的hash槽

有時(shí)候，hash槽上不一定有數(shù)據(jù)，因?yàn)閔ashtable散列之后有的是空的，如果循環(huán)的時(shí)候發(fā)現(xiàn)有empty_visits=10個(gè)hash槽是空的，就不做rehash了。

這個(gè)while循環(huán)結(jié)束之后，剩下的都是非空的hash槽。

獲取非空hash槽上鏈表的頭節(jié)點(diǎn)

開(kāi)始遍歷鏈表，重新計(jì)算hash值。

這里是進(jìn)行與運(yùn)算，而不是求模運(yùn)算，性能更高。

• size

size大小為2^n

• sizemask

sizemask=size-1=2^n-1

公式

任意數(shù) % 2^n <=> 任意數(shù) & (2^n-1)

即累除法求余數(shù)，一次位運(yùn)算就能計(jì)算出結(jié)果，更加高效。

計(jì)算出key在新的hashtable上的位置之后，將老的hash槽索引指向新的hashtable的表頭，并將老的hash槽上的鏈表遷移到新的hashtable上去，完成了數(shù)據(jù)遷移操作。

遷移過(guò)來(lái)之后，老的hashtable上的元素個(gè)數(shù)減1，新的加1。

一個(gè)hash槽一個(gè)hash槽的遷移數(shù)據(jù)。

判斷老的hashtable中還有沒(méi)有元素，如果沒(méi)有的話，就釋放掉老的hashtable。

將老的hashtable(ht[0])指向新的hashtable(ht[1]),新的hashtable(ht[1])就釋放掉了。

至此，就完成了rehash的過(guò)程。

rehash完之后，接下來(lái)就是查找key的過(guò)程

先從老的hashtable查找(ht[0])，有的話就返回，沒(méi)有的話再查找新的hashtable(ht[1])，還沒(méi)有的話就返回null。

接下來(lái)就是檢查查詢(xún)到數(shù)據(jù)的類(lèi)型

看是否為L(zhǎng)ist數(shù)據(jù)類(lèi)型

lpush alist a b c

如果alist不是List而是string 則會(huì)報(bào)異常提示類(lèi)型不匹配

如果在db中沒(méi)有找到數(shù)據(jù)，則創(chuàng)建一個(gè)quicklist

list數(shù)據(jù)類(lèi)型，底層編碼是quicklist。

接下來(lái)就是把創(chuàng)建好的數(shù)據(jù)添加到字典中了

quicklistSetOptions

設(shè)置每個(gè)ziplist的最大容量，quicklist的數(shù)據(jù)壓縮范圍，提升數(shù)據(jù)的存取效率

• list-max-ziplist-size -2

單個(gè)ziplist節(jié)點(diǎn)最大能存儲(chǔ)8kb，超過(guò)則進(jìn)行分裂，將數(shù)據(jù)存儲(chǔ)在新的ziplist節(jié)點(diǎn)中

默認(rèn)8kb的數(shù)據(jù)可以分鏈

不推薦-5，因?yàn)閿?shù)據(jù)大了往內(nèi)存中添加元素，會(huì)涉及到數(shù)據(jù)的拷貝，導(dǎo)致性能降低。

• list-compress-depth 1

0代表所有節(jié)點(diǎn)，都不進(jìn)行壓縮，1代表從頭節(jié)點(diǎn)往后走一個(gè)，尾節(jié)點(diǎn)往前走一個(gè)不用壓縮，其他的全部壓縮，2，3，4以此類(lèi)推

雙端鏈表內(nèi)存是不連續(xù)的，就會(huì)導(dǎo)致內(nèi)存碎片問(wèn)題，壓縮了之后，就可以做成整塊的內(nèi)存空間了，使得數(shù)據(jù)更加的有規(guī)律，節(jié)省了內(nèi)存空間。

dbAdd

每次訪問(wèn)hashtable都會(huì)做一次rehash的操作。

rehash完之后，求索引值

存放元素：如果正在做rehash，則將新增的元素放入新的hashtable中

采用頭插法，最新添加的，會(huì)被更頻繁的訪問(wèn)

老的hashtable索引指向新創(chuàng)建的元素地址，entry就是新創(chuàng)建的節(jié)點(diǎn)

hashtable指向的就是鏈表的頭部節(jié)點(diǎn)

接下來(lái)把添加的數(shù)據(jù)追加到list中去

創(chuàng)建quicklistNode和ziplist

Set 數(shù)據(jù)類(lèi)型

set語(yǔ)義上來(lái)說(shuō)是無(wú)序的

上面這種整數(shù)的、元素不多的是通過(guò)有序的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的

基于上面都是整數(shù)元素的基礎(chǔ)上添加一個(gè)字符串元素，返回結(jié)果是1，因?yàn)橹惶砑舆M(jìn)去一個(gè)元素。

此時(shí)的編碼是hashtable，因?yàn)樽址當(dāng)?shù)據(jù)的那個(gè)元素沒(méi)有辦法用整型值編碼的時(shí)候，會(huì)重新轉(zhuǎn)換成一個(gè)hashtable。

此時(shí)就變成無(wú)序的了，因?yàn)閔ashtable本身就是無(wú)序的數(shù)據(jù)結(jié)構(gòu)。

Set為無(wú)序，自動(dòng)去重的集合數(shù)據(jù)類(lèi)型，Set數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)為一個(gè)value為null的字典(dict)，當(dāng)數(shù)據(jù)可以用整型表示時(shí)，Set集合將被編碼為intset數(shù)據(jù)結(jié)構(gòu)。以下兩個(gè)條件任意滿足一個(gè)，Set將用hashtable存儲(chǔ)數(shù)據(jù)

• 元素個(gè)數(shù)大于set-max-intset-entries

set-max-intset-entries 512 intset能存儲(chǔ)的最大元素個(gè)數(shù)，超過(guò)則用hashtable編碼

• 元素?zé)o法用整型表示

intset就是一個(gè)數(shù)組，有序，都是整形元素。通過(guò)二分查找來(lái)判斷某個(gè)元素是否存在。用整型數(shù)組更節(jié)省空間。

sadd源碼

從server.c 文件中的 redisCommand redis命令集合中找到sadd

查詢(xún)r(jià)edis db中是否存在set集合

如果不存在的話，則創(chuàng)建set集合

判斷字符串是否可以轉(zhuǎn)換成long，如果可以則創(chuàng)建intset

創(chuàng)建intset集合

數(shù)據(jù)類(lèi)型是set，數(shù)據(jù)編碼是intset

否則創(chuàng)建hashtable

set集合創(chuàng)建好之后，將set添加到db中

dictAddRaw

如果數(shù)據(jù)編碼是hashtable

值設(shè)置為NULL

intset

如果是數(shù)字，則追加到intset中去

intsetAdd

intsetValueEncoding

判斷下數(shù)據(jù)范圍，3種類(lèi)型的數(shù)組，16個(gè)bit位的，32bit位，64bit位的，判斷下追加的值屬于哪個(gè)范圍，就用對(duì)應(yīng)的數(shù)組，這是為了節(jié)省內(nèi)存空間，根據(jù)數(shù)據(jù)的范圍去創(chuàng)建不同的數(shù)組，如果數(shù)據(jù)量非常大的話，就用大一點(diǎn)的位數(shù)去創(chuàng)建數(shù)組。

如果范圍比現(xiàn)有的范圍還大的話，就進(jìn)行升級(jí)，如果超過(guò)了32位就用64位，超過(guò)了16位，就用32位的數(shù)組。

如果小于現(xiàn)有的編碼長(zhǎng)度的話

查詢(xún)下數(shù)據(jù)在當(dāng)前intset中是否存在，intset也會(huì)自動(dòng)去重，已經(jīng)存在的話，就直接返回。

intsetSearch

這里使用的是二分查找，break就是終止了，然后判斷是否存在

往右移動(dòng)一位就是除以2

相等就是存在，否則就是不存在，不存在的話，就記錄下position，這樣就知道下一次數(shù)據(jù)放在哪個(gè)位置了。

因?yàn)橐砑釉兀砸匦聰U(kuò)容

擴(kuò)容之后，在對(duì)應(yīng)的position上把添加的元素放進(jìn)去

根據(jù)數(shù)據(jù)的長(zhǎng)度采用不同的存儲(chǔ)類(lèi)型來(lái)存放

Set 數(shù)據(jù)類(lèi)型底層intset編碼

整數(shù)集合是一個(gè)有序的，存儲(chǔ)整型數(shù)據(jù)的結(jié)構(gòu)，整型集合在redis中可以保存int16_t,int32_t,int64_t類(lèi)型的整型數(shù)據(jù)，并且可以保證集合中不會(huì)出現(xiàn)重復(fù)數(shù)據(jù)。

Hash 數(shù)據(jù)類(lèi)型

Hash數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)是一個(gè)字典（dict），也是RedisDB用來(lái)存儲(chǔ)K-V的數(shù)據(jù)結(jié)構(gòu)，當(dāng)數(shù)據(jù)量比較小，或者單個(gè)元素比較小時(shí)，底層用ziplist存儲(chǔ)。數(shù)據(jù)大小和元素閾值可以通過(guò)如下參數(shù)設(shè)置：

• hash-max-ziplist-entries 512

ziplist元素個(gè)數(shù)超過(guò)512，將改為hashtable編碼

• hash-max-ziplist-value 64

單個(gè)元素大小超過(guò)64byte時(shí)，將改為hashtable編碼

按照放入順序存取

Hash數(shù)據(jù)類(lèi)型ziplist編碼

用hash去存儲(chǔ)K-V的時(shí)候，比如name、age，一個(gè)鍵值對(duì)拆成2個(gè)元素放到一個(gè)ziplist里面，從而更有效的利用內(nèi)存。

單個(gè)元素超過(guò)64字節(jié)，就會(huì)變成無(wú)序的hashtable編碼存儲(chǔ)

有序的ZSet

zset/sorted_set數(shù)據(jù)類(lèi)型

ZSet是有序的，自動(dòng)去重的集合數(shù)據(jù)類(lèi)型，ZSet數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)為字典(dict)+跳表(skiplist)，當(dāng)數(shù)據(jù)比較少時(shí)，用ziplist編碼結(jié)構(gòu)存儲(chǔ)

• zset-max-ziplist-entries 128

元素個(gè)數(shù)超過(guò)128，將用skiplist編碼

• zset-max-ziplist-value 64

單個(gè)元素超過(guò)64byte，將用skiplist

0,2表示排名；withscores表示分值打印

當(dāng)數(shù)據(jù)量比較小的時(shí)候，編碼是緊湊的連續(xù)空間，對(duì)內(nèi)存利用率高，可自動(dòng)去重。

當(dāng)數(shù)據(jù)量比較大的時(shí)候，底層編碼就變成了skiplist 跳表

skiplist 跳表數(shù)據(jù)結(jié)構(gòu)

這是一個(gè)有序的鏈表，想要找元素79，挨個(gè)遍歷才能找到，時(shí)間復(fù)雜度是O(n)。

在數(shù)據(jù)層基礎(chǔ)之上提一個(gè)索引層出來(lái)，每隔一個(gè)元素就提一個(gè)索引出來(lái)，用索引幫助查詢(xún)數(shù)據(jù)，在索引層直到找到比79大的數(shù)據(jù)，就不往后找了即索引層找到78，下沉到數(shù)據(jù)層78，再往后找一個(gè)就是79了，這樣就會(huì)跳過(guò)很多的元素，提高查詢(xún)效率。

再提一個(gè)索引層2

再提一個(gè)索引層3

時(shí)間復(fù)雜度分析

數(shù)據(jù)： n

index 1 n/2

index 2 n/2^2

index 3 n/2^3

index k n/2^k

每添加一個(gè)索引層就減少一半的數(shù)據(jù)量即索引第三層是索引第二層的一半，索引第二層是索引第一層的一半，索引第一層是數(shù)據(jù)層的一半。

每一層都只需要常數(shù)級(jí)別查詢(xún)次數(shù)即可，該查詢(xún)次數(shù)就是層高。

根據(jù)數(shù)據(jù)歸納法，假設(shè)索引層最頂層有2個(gè)數(shù)據(jù)，即n/2^k=2 => 2^k=n/2 => k= log_2 n

以2為底，n的對(duì)數(shù)即log n的時(shí)間復(fù)雜度。

zadd源碼

查詢(xún)zset，如果沒(méi)有，則創(chuàng)建一個(gè)跳表或zskiplist

• 創(chuàng)建跳表zskiplist

• 創(chuàng)建ziplist

zset是復(fù)合型數(shù)據(jù)結(jié)構(gòu):字典+跳表

字典可以最快速的索引到記錄，跳表存儲(chǔ)的是有序的數(shù)據(jù)。

zscore O(1)的時(shí)間復(fù)雜度，通過(guò)元素拿到分值，查詢(xún)效率高效是源于zset的dict字典數(shù)據(jù)結(jié)構(gòu)。

dict里面存儲(chǔ)的是索引，不是真正的值，真正的值只有一份，是由dict和zskiplist共享，盡量減少存儲(chǔ)空間的前提下提升訪問(wèn)速度。

zskiplist

• skiplistNode *header, *tail

雙向指針

1、可以從前往后遍歷

升序

2、也可以從后往前遍歷

倒序

• long length

元素個(gè)數(shù)

• int level

索引最高的層高。在redis中索引層的索引沒(méi)有那么規(guī)律，而是用隨機(jī)數(shù)生成的。

zskiplistNode

• sds ele 元素
• double score 分值
• zskiplistNode *backward; 同類(lèi)型指針，指向后面的節(jié)點(diǎn)
• zskiplistLevel level[] 索引層是個(gè)數(shù)組
• zskiplistLevel.zskiplistNode 指向前面的節(jié)點(diǎn)
• long span 兩個(gè)索引層之間的間隔

zskiplist數(shù)據(jù)結(jié)構(gòu)補(bǔ)充說(shuō)明

• header指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的層高始終為64層
• level保存跳表中節(jié)點(diǎn)層數(shù)最高值，但是不計(jì)算頭結(jié)點(diǎn)的層高
• length保存跳表中節(jié)點(diǎn)個(gè)數(shù)，但是不包括頭結(jié)點(diǎn)
• tail指向尾節(jié)點(diǎn)

舉例說(shuō)明：

假設(shè)要找score為5的元素

（1）首先從頭結(jié)點(diǎn)的最高層（也就是64層）開(kāi)始查找，但是由于頭指針中保存了當(dāng)前跳表的最高層數(shù)，所以直接從頭結(jié)點(diǎn)的level層開(kāi)始查找即可。如果zkiplistLevel的forward為NULL，則繼續(xù)向下

（2）直到頭結(jié)點(diǎn)中第5層的zskiplistLevel的forward不為空，它指向了第6個(gè)節(jié)點(diǎn)的第5層，但是這個(gè)節(jié)點(diǎn)的score為6，大于5，所以還要從頭結(jié)點(diǎn)向低層繼續(xù)查找

（3）頭結(jié)點(diǎn)中第4層的zskiplistLevel的forward指向第3個(gè)節(jié)點(diǎn)的第4層，這個(gè)節(jié)點(diǎn)的score為3，小于4，繼續(xù)從這個(gè)節(jié)點(diǎn)的forward向后遍歷。它的forward指向第6個(gè)節(jié)點(diǎn)的第4層，這個(gè)節(jié)點(diǎn)的score為6，大于5，所以還要從前一個(gè)score為3的節(jié)點(diǎn)向低層繼續(xù)查找

（4）第3個(gè)節(jié)點(diǎn)第3層的zskiplistLevel的forward指向第5個(gè)節(jié)點(diǎn)的第3層，而它的score正好為5，查找成功

求元素79的排名，每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)就計(jì)算它之間的span，就能算出它的排名。

將生成好的zset放入db中

先rehash，然后存儲(chǔ)在hashtable中去。

然后就是計(jì)算分值并往zset中添加元素

• 往ziplist添加元素

• 往跳表中添加元素

從跳表字典中查找記錄

時(shí)間復(fù)雜度是O(1)。

如果de不為空，說(shuō)明元素之前已存在了，此時(shí)如果是setnx，則會(huì)直接抱異常，否則可以修改它的值。

如果兩個(gè)值不相等，先刪除再插入數(shù)據(jù)。

zslUpdateScore

Redis中的做法比較簡(jiǎn)單，先找到待修改的節(jié)點(diǎn)，直接刪除，然后插入修改后的新的節(jié)點(diǎn)。

找新增元素的位置：遍歷所有的索引層，找位置。

判斷分值在什么地方，如果在原來(lái)元素的位置，不用移動(dòng)元素，更新分值即可。

比如

將b元素的分值由200修改成201，其他元素沒(méi)有變化，排名不變。

將b由200修改成301，排名發(fā)生變化

刪除原來(lái)的元素，再插入新的

刪除邏輯 zslDeleteNode

（1）找到待刪除的節(jié)點(diǎn)，刪除節(jié)點(diǎn)，更新前面節(jié)點(diǎn)的跨度和跳表最大層高

（2）更新新節(jié)點(diǎn)的各層的forward以及backward指針

新增邏輯 zslInsert

（1）首先，插入結(jié)點(diǎn)時(shí)，都會(huì)隨機(jī)為新的節(jié)點(diǎn)分配一個(gè)小于64的層數(shù)，并且層數(shù)越小概率越大，層數(shù)越高概率越小

（2）查找到小于待插入score的分?jǐn)?shù)值中最大的那個(gè)節(jié)點(diǎn)，如果score相等，則通過(guò)value比較

（3）在找到的節(jié)點(diǎn)后面插入新的節(jié)點(diǎn)。同時(shí)更新前面節(jié)點(diǎn)的跨度和跳表最大層高

（4）更新新節(jié)點(diǎn)的各層的forward以及backward指針

插入節(jié)點(diǎn)，最關(guān)鍵在于索引層的創(chuàng)建和指針的關(guān)聯(lián)關(guān)系

第一步：找插入的位置

第二步：創(chuàng)建索引層

在創(chuàng)建節(jié)點(diǎn)之前，先創(chuàng)建索引層，通過(guò)隨機(jī)算法生成

while循環(huán)的條件是隨機(jī)數(shù)random 小于 P=1/4 ，結(jié)束循環(huán)的條件是1-P

1、

level=1 第一層索引的生成概率即生成完第一層索引循環(huán)就結(jié)束的概率是1-P=3/4

2、

level=2 第二層索引的生成概率即生成完第二層索引循環(huán)就結(jié)束的概率是 P*(1-P)

• 第一次level=1 生成第一層索引的概率是1/4
• 第二次level=2 生成第二層索引的概率是3/4

3、

level=3 第三層索引的生成概率是 P^2 * (1-P)

• 第一次level=1 生成第一層索引的概率是1/4
• 第二次level=2 生成第二層索引的概率是1/4
• 第三次level=3 生成第三層索引的概率是3/4

綜上：層數(shù)越高，生成的概率越低，導(dǎo)致越高層的索引就越少，越低層的索引更多。

層數(shù)越高，出現(xiàn)的概率越低，節(jié)點(diǎn)越少，能夠一次性判別的元素更多。

創(chuàng)建好索引之后，每個(gè)索引的初始化參數(shù)都設(shè)置好，包括span的重新設(shè)置。

第三步: 創(chuàng)建節(jié)點(diǎn)

索引層作為參數(shù)傳遞進(jìn)入

節(jié)點(diǎn)創(chuàng)建好之后，再更新節(jié)點(diǎn)關(guān)系，包括頭節(jié)點(diǎn)指向它的關(guān)系、和兩邊節(jié)點(diǎn)之間的關(guān)系都需要重新創(chuàng)建、span的重新計(jì)算

再把對(duì)應(yīng)的統(tǒng)計(jì)數(shù)據(jù)++，因?yàn)樾略隽艘粋€(gè)元素

Redis高級(jí)數(shù)據(jù)類(lèi)型BitMap位圖

bit是計(jì)算機(jī)最小的存儲(chǔ)單元，取值為0和1。

bitmap提供了對(duì)bit位的設(shè)值、操作、統(tǒng)計(jì)的命令，通常被用來(lái)在極小的空間消耗下通過(guò)位運(yùn)算（AND/OR/XOR/NOT）來(lái)實(shí)現(xiàn)對(duì)狀態(tài)的操作，常見(jiàn)的使用場(chǎng)景：