承接上文redis底層字符串編碼設計思想簡介

ziplist數據結構

內存會一次性開辟一塊大的連續(xù)的空間，來存放ziplist。

• zlbytes

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

• zltail

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

• zllen

16bit內存空間，表示ziplist中數據項entry的個數

• zlend:255

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

• entry

表示真正存放數據的數據項，長度不定

• prerawlen

表示上一個節(jié)點的數據長度信息。

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

ziplist額外的信息最多需要5個字節(jié)存儲，相比quicklist雙端鏈表的一個元素需要2個指針16個字節(jié)來說節(jié)省很多內存開銷。

• len

entry中數據的長度

• data

表示當前元素里面的真實數據，業(yè)務數據存儲，這是一個非常緊湊的二進制數據結構。

連續(xù)的內存空間也會存在弊端？

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

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

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

加一些數據，比如加入到ziplist里面去，不需要對數據整個做偏移，因為數據已經分配到不同的ziplist里面去了，修改數據，只需要修改某一個ziplist就可以了。

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

接下來看下lpush源碼

pushGenericCommand

先從redis數據庫獲取數據

• c->db

db就是要操作的redis數據庫

• c->argv[1]

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

lpush alist a b c

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

根據key去db中查找數據

• key->ptr

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

進行rehash操作

-1表示沒有進行rehash，不等于-1表示正在進行rehash。

做rehash的方法

篩選非空的hash槽

有時候，hash槽上不一定有數據，因為hashtable散列之后有的是空的，如果循環(huán)的時候發(fā)現有empty_visits=10個hash槽是空的，就不做rehash了。

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

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

開始遍歷鏈表，重新計算hash值。

這里是進行與運算，而不是求模運算，性能更高。

• size

size大小為2^n

• sizemask

sizemask=size-1=2^n-1

公式

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

即累除法求余數，一次位運算就能計算出結果，更加高效。

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

遷移過來之后，老的hashtable上的元素個數減1，新的加1。

一個hash槽一個hash槽的遷移數據。

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

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

至此，就完成了rehash的過程。

rehash完之后，接下來就是查找key的過程

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

接下來就是檢查查詢到數據的類型

看是否為List數據類型

lpush alist a b c

如果alist不是List而是string 則會報異常提示類型不匹配

如果在db中沒有找到數據，則創(chuàng)建一個quicklist

list數據類型，底層編碼是quicklist。

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

quicklistSetOptions

設置每個ziplist的最大容量，quicklist的數據壓縮范圍，提升數據的存取效率

• list-max-ziplist-size -2

單個ziplist節(jié)點最大能存儲8kb，超過則進行分裂，將數據存儲在新的ziplist節(jié)點中

默認8kb的數據可以分鏈

不推薦-5，因為數據大了往內存中添加元素，會涉及到數據的拷貝，導致性能降低。

• list-compress-depth 1

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

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

dbAdd

每次訪問hashtable都會做一次rehash的操作。

rehash完之后，求索引值

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

采用頭插法，最新添加的，會被更頻繁的訪問

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

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

接下來把添加的數據追加到list中去

創(chuàng)建quicklistNode和ziplist

Set 數據類型

set語義上來說是無序的

上面這種整數的、元素不多的是通過有序的數據結構實現的

基于上面都是整數元素的基礎上添加一個字符串元素，返回結果是1，因為只添加進去一個元素。

此時的編碼是hashtable，因為字符串數據的那個元素沒有辦法用整型值編碼的時候，會重新轉換成一個hashtable。

此時就變成無序的了，因為hashtable本身就是無序的數據結構。

Set為無序，自動去重的集合數據類型，Set數據結構底層實現為一個value為null的字典(dict)，當數據可以用整型表示時，Set集合將被編碼為intset數據結構。以下兩個條件任意滿足一個，Set將用hashtable存儲數據

• 元素個數大于set-max-intset-entries

set-max-intset-entries 512 intset能存儲的最大元素個數，超過則用hashtable編碼

• 元素無法用整型表示

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

sadd源碼

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

查詢redis db中是否存在set集合

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

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

創(chuàng)建intset集合

數據類型是set，數據編碼是intset

否則創(chuàng)建hashtable

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

dictAddRaw

如果數據編碼是hashtable

值設置為NULL

intset

如果是數字，則追加到intset中去

intsetAdd

intsetValueEncoding

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

如果范圍比現有的范圍還大的話，就進行升級，如果超過了32位就用64位，超過了16位，就用32位的數組。

如果小于現有的編碼長度的話

查詢下數據在當前intset中是否存在，intset也會自動去重，已經存在的話，就直接返回。

intsetSearch

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

往右移動一位就是除以2

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

因為要添加元素，所以要重新擴容

擴容之后，在對應的position上把添加的元素放進去

根據數據的長度采用不同的存儲類型來存放

Set 數據類型底層intset編碼

整數集合是一個有序的，存儲整型數據的結構，整型集合在redis中可以保存int16_t,int32_t,int64_t類型的整型數據，并且可以保證集合中不會出現重復數據。

Hash 數據類型

Hash數據結構底層實現是一個字典（dict），也是RedisDB用來存儲K-V的數據結構，當數據量比較小，或者單個元素比較小時，底層用ziplist存儲。數據大小和元素閾值可以通過如下參數設置：

• hash-max-ziplist-entries 512

ziplist元素個數超過512，將改為hashtable編碼

• hash-max-ziplist-value 64

單個元素大小超過64byte時，將改為hashtable編碼

按照放入順序存取

Hash數據類型ziplist編碼

用hash去存儲K-V的時候，比如name、age，一個鍵值對拆成2個元素放到一個ziplist里面，從而更有效的利用內存。

單個元素超過64字節(jié)，就會變成無序的hashtable編碼存儲

有序的ZSet

zset/sorted_set數據類型

ZSet是有序的，自動去重的集合數據類型，ZSet數據結構底層實現為字典(dict)+跳表(skiplist)，當數據比較少時，用ziplist編碼結構存儲

• zset-max-ziplist-entries 128

元素個數超過128，將用skiplist編碼

• zset-max-ziplist-value 64

單個元素超過64byte，將用skiplist

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

當數據量比較小的時候，編碼是緊湊的連續(xù)空間，對內存利用率高，可自動去重。

當數據量比較大的時候，底層編碼就變成了skiplist 跳表

skiplist 跳表數據結構

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

在數據層基礎之上提一個索引層出來，每隔一個元素就提一個索引出來，用索引幫助查詢數據，在索引層直到找到比79大的數據，就不往后找了即索引層找到78，下沉到數據層78，再往后找一個就是79了，這樣就會跳過很多的元素，提高查詢效率。

再提一個索引層2

再提一個索引層3

時間復雜度分析

數據： n

index 1 n/2

index 2 n/2^2

index 3 n/2^3

index k n/2^k

每添加一個索引層就減少一半的數據量即索引第三層是索引第二層的一半，索引第二層是索引第一層的一半，索引第一層是數據層的一半。

每一層都只需要常數級別查詢次數即可，該查詢次數就是層高。

根據數據歸納法，假設索引層最頂層有2個數據，即n/2^k=2 => 2^k=n/2 => k= log_2 n

以2為底，n的對數即log n的時間復雜度。

zadd源碼

查詢zset，如果沒有，則創(chuàng)建一個跳表或zskiplist

• 創(chuàng)建跳表zskiplist

• 創(chuàng)建ziplist

zset是復合型數據結構:字典+跳表

字典可以最快速的索引到記錄，跳表存儲的是有序的數據。

zscore O(1)的時間復雜度，通過元素拿到分值，查詢效率高效是源于zset的dict字典數據結構。

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

zskiplist

• skiplistNode *header, *tail

雙向指針

1、可以從前往后遍歷

升序

2、也可以從后往前遍歷

倒序

• long length

元素個數

• int level

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

zskiplistNode

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

zskiplist數據結構補充說明

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

舉例說明：

假設要找score為5的元素

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

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

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

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