簡(jiǎn)單動(dòng)態(tài)數(shù)組（String的底層）

redis的SDS字符串?dāng)?shù)組和C底層的數(shù)組稍有不同。

不同點(diǎn)：通過將字節(jié)數(shù)組進(jìn)一步的封裝，是字符串的數(shù)據(jù)結(jié)構(gòu)變成len,free,buf[]這種形式。類似于ArrayList與普通數(shù)組的不同，主要有以下不同。

redis中SDS數(shù)據(jù)結(jié)構(gòu)

1. 不以遍歷整個(gè)數(shù)組的方式得到數(shù)組長(zhǎng)度，直接從len得到
2. 動(dòng)態(tài)擴(kuò)容機(jī)制

• 空間預(yù)分配
  所謂預(yù)分配其實(shí)就是數(shù)組的容量動(dòng)態(tài)擴(kuò)容，擴(kuò)容規(guī)則是：
  1. 如果SDS小于1MB的話，擴(kuò)容當(dāng)前字節(jié)數(shù)的2倍+1，例如SDS現(xiàn)在為13字節(jié)，擴(kuò)容后的長(zhǎng)度是13 + 13 + 1(用于保留/0)=27字節(jié)。

  2. 如果SDS大于1MB，遍在此基礎(chǔ)上增加1M+1字節(jié)，例如現(xiàn)在為30MB長(zhǎng)度，擴(kuò)容后為30MB + 1MB + 1B。

     
     
     空間預(yù)分配
• 惰性空間釋放
  當(dāng)?shù)讓觔uf數(shù)組的實(shí)際使用小于數(shù)組容量時(shí)候不馬上縮容。

3. 二進(jìn)制安全，由于buf[]數(shù)組是以len查詢長(zhǎng)度的，不以/0作為結(jié)束符號(hào)，所以redis對(duì)于文本的存儲(chǔ)是兼容。

二進(jìn)制安全

4. 兼容C的部分函數(shù)，redis在每個(gè)buf[]數(shù)組末尾都加了/0作為結(jié)束符，所以兼容C的部分函數(shù)。見上圖。

鏈表（list的底層）

記憶點(diǎn)：list底層數(shù)據(jù)結(jié)構(gòu)邏輯:list----listNode
鏈表被廣泛用于實(shí)現(xiàn) redis的各種功能，比如列表鍵、發(fā)布與訂閱、慢查詢、監(jiān)視器等。

1. 每個(gè)鏈表節(jié)點(diǎn)由一個(gè) listNode結(jié)構(gòu)來表示，每個(gè)節(jié)點(diǎn)都有一個(gè)指向前節(jié)點(diǎn)pre和后節(jié)點(diǎn)next的指針．所以 Redis的鏈表實(shí)現(xiàn)是雙端鏈表。
2. 每個(gè)鏈表使用一個(gè)list結(jié)構(gòu)來表示，這個(gè)結(jié)構(gòu)帶有表頭節(jié)點(diǎn)指針head、表尾節(jié)點(diǎn)指針tail，以及鏈表長(zhǎng)度等信息。其中match為比較節(jié)點(diǎn)值和給定值的函數(shù)，dup是復(fù)制節(jié)點(diǎn)值的函數(shù)，free為釋放節(jié)點(diǎn)值的函數(shù)。
3. 因?yàn)殒湵肀眍^節(jié)點(diǎn)的前節(jié)點(diǎn)和表尾節(jié)點(diǎn)的后節(jié)點(diǎn)都指向 null ．所以 redis的鏈表實(shí)現(xiàn)是無環(huán)鏈表。
4. 通過為鏈表設(shè)置不同的類型特定函數(shù)，可以用于保存各種不同類型的值。

由list和listNode結(jié)構(gòu)組成的鏈表

由listNode節(jié)點(diǎn)組成的鏈表

字典（整個(gè)數(shù)據(jù)庫(kù)的實(shí)現(xiàn)）

記憶點(diǎn)：
字典（dict）底層數(shù)據(jù)結(jié)構(gòu)邏輯:dict--[dictht[ ]/ rehashidx]--[dictEntry(table) / size / used]

普通狀態(tài)下的dict

根據(jù)hash值和sizemark計(jì)算出索引值，采用拉鏈法解決hash沖突

k1與k2發(fā)生hash沖突

rehash擴(kuò)容方式--漸進(jìn)式（為了保證性能）
隨著操作的不斷執(zhí)行，哈希表保存的鍵值對(duì)會(huì)逐漸地增多或者減少，為了讓哈希表的負(fù)載因子(load factor）維持在一個(gè)合理的范圍之內(nèi)，當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或者太少時(shí)，程序需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮。

1. 擴(kuò)容數(shù)量：ht[0].used2,并通過取近似保證其為2^n冪，例如ht[0].used=10，ht[0].used2=20，此時(shí)應(yīng)取32為大于20的第一個(gè)2^n -- 2^5作為新的容量。
2. 擴(kuò)容時(shí)機(jī)：
   1. 服務(wù)器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令 ，并且哈希表的負(fù)載因子大于等于1。
   2. 服務(wù)器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令 ，并且哈希表的負(fù)載因子大于等于5。
      其中哈希表的負(fù)載因子可以通過公式：
      負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量/哈希表大小
      擴(kuò)容產(chǎn)生不同的原因在于Redis在持久化的時(shí)候需要?jiǎng)?chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程，而大多數(shù)操作系統(tǒng)都采用寫時(shí)復(fù)制（copy-on-write)技術(shù)來優(yōu)化了進(jìn)程的使用效率，所以在子進(jìn)程存在期間，服務(wù)器會(huì)提高執(zhí)行擴(kuò)展操作所需要的負(fù)載因子，從而盡可能地避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展操作，這可以避免不必要的內(nèi)存寫人操作，最大限度地節(jié)約內(nèi)存。換言之就是持久化的時(shí)候?qū)?nèi)存的消耗比較大，而redis希望提高在持久化的時(shí)候擴(kuò)容的閾值以保證內(nèi)存的充足。
      另一方面，當(dāng)哈希表的負(fù)載因子小于0.1時(shí)，程序自動(dòng)開始對(duì)哈希表執(zhí)行收縮操作。
3. rehash的過程

執(zhí)行rehash之前的字典

為ht1準(zhǔn)備dictEntry對(duì)象，準(zhǔn)備將數(shù)據(jù)遷移到此size更大的表

這里需要說明的是為了保證redis的性能擴(kuò)容不是一次性就完成的，而是隨著之后的每次操作進(jìn)行。redis每執(zhí)行一次增刪改才做，數(shù)據(jù)遷移一部分。這就是redis的漸進(jìn)式rehash。

循序漸進(jìn)的把ht0的數(shù)據(jù)遷移到ht1上

將ht1替換成ht0，并把原來的ht0釋放,并創(chuàng)建一個(gè)新的空的ht1，完成數(shù)據(jù)的遷移擴(kuò)容

4. rehash時(shí)的操作
   因?yàn)樵谶M(jìn)行漸進(jìn)式rehash的過程中，字典會(huì)同時(shí)使用ht[0] 和ht[1]兩個(gè)哈希表，所以在漸進(jìn)式rehash進(jìn)行期間，字典的刪除（delete)、査找（find）、更新（update) 等操作會(huì)在兩個(gè)哈希表上進(jìn)行。例如，要在字典里面査找一個(gè)鍵的話，程序會(huì)先在ht[0]里面進(jìn)行査找，如果沒找到的話，就會(huì)繼續(xù)到ht[1]里面進(jìn)行査找。
   另外，在漸進(jìn)式rehash執(zhí)行期間，新添加到字典的鍵值對(duì)一律會(huì)被保存到ht[1]里面，而ht[0]則不再進(jìn)行任何添加操作，這一措施保證了ht[0]包含的鍵值對(duì)數(shù)量會(huì)只減不增，并隨著rehash操作的執(zhí)行而最終變成空表。

未完待續(xù)。。。