前言
以下的內(nèi)容是筆者閱讀學(xué)習(xí)《redis設(shè)計與實現(xiàn)(第二版)》的一個讀書筆記，主要是對書中提到的一些關(guān)鍵點進(jìn)行歸納總結(jié)。此外，配合redis3.0的源碼進(jìn)行學(xué)習(xí)效果更佳。

ch2 簡單動態(tài)字符串

redis沒有直接使用C語言傳統(tǒng)的字符串表示，而是自己構(gòu)建了一種名為簡單動態(tài)字符串（SDS）的抽象類型，并將SDS用作redis的默認(rèn)字符串表示。

在redis里面，C字符串只會作為字符串字面量用在一些無須對字符串值進(jìn)行修改的地方，比如日志打印：

日志打印

當(dāng)redis需要的不僅僅是一個字符串字面量，而時一個可以被修改的字符串值時，redis就會使用SDS來表示字符串值，比如在redis的數(shù)據(jù)庫里面，包含字符串值的鍵值對在底層都是由SDS實現(xiàn)的。

1. SDS的定義

   
   
   SDS的定義
2. SDS與C字符串的區(qū)別

   1. 常數(shù)復(fù)雜度獲取字符串長度
      C字符串并不記錄自身的長度信息，所以為了獲取一個C字符串的長度，程序必須遍歷整個字符串，對遇到的每個字符進(jìn)行計數(shù)，知道遇到代表字符串結(jié)尾的空字符為止，這個操作的復(fù)雜度為O(N)。SDS在len屬性中記錄了本身的長度，所以獲取一個SDS的長度復(fù)雜度為O(1)。

   2. 杜絕緩沖區(qū)溢出
      例如，<string.h>/strcat函數(shù)可以將src字符串的內(nèi)容拼接到dest字符串的末尾。

      strcat
      
      

      C字符串不記錄自身的長度，所以strcat假定用戶在執(zhí)行這個函數(shù)時，已經(jīng)為dest分配了足夠多的內(nèi)存，可以容納src字符串中的所有內(nèi)容，而一旦這個假定不成立，就會產(chǎn)生緩沖區(qū)溢出。

   3. 減少修改字符串時帶來的內(nèi)存重分配次數(shù)
      SDS實現(xiàn)兩種空間優(yōu)化策略：

      • 空間預(yù)分配

        
        
        空間預(yù)分配
      • 惰性空間釋放
        當(dāng)SDS的API需要縮短SDS保存的字符串時，程序并不立即使用內(nèi)存重分配來揮手縮短多出來的字節(jié)，而是使用free屬性將這些字節(jié)的數(shù)量記錄起來，并等待將來使用。

   4. 二進(jìn)制安全
      C字符串中的字符必須符合某種編碼，并且除了字符串的末尾之外，字符串里面不能包含空字符，否則會被認(rèn)為是字符串的結(jié)尾。SDS中用char數(shù)組來保存數(shù)據(jù)，并且使用len屬性來記錄數(shù)據(jù)的長度。

   5. 兼容部分C字符串函數(shù)
      雖然SDS的API都是二進(jìn)制安全的，但他們一樣遵循C字符串以空字符結(jié)尾的慣例，所以保存在SDS的文本數(shù)據(jù)可以重用一部分<string.h>庫定義的函數(shù)。

3. 總結(jié)

   
   
   C字符串與SDS的總結(jié)

ch3 鏈表

1. 鏈表和鏈表節(jié)點的實現(xiàn)
   

   鏈表節(jié)點
   
   雙向鏈表（adlist.h/listNode）
   
   鏈表

2. redis鏈表特性

   • 雙端：鏈表節(jié)點帶有prev和next指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復(fù)雜度都是O(1)
   • 無環(huán)：表頭節(jié)點的pre指針和表尾的next指針都指向NULL，對鏈表的訪問以NULL為終點
   • 帶表頭指針和表尾指針：通過list結(jié)構(gòu)的head指針和tail指針，程序獲取鏈接的表頭節(jié)點和表尾節(jié)點的復(fù)雜度為O(1)
   • 帶鏈表長度計數(shù)器：程序使用list結(jié)構(gòu)的len屬性來對list持有的鏈表節(jié)點進(jìn)行計數(shù)，程序獲取鏈表中節(jié)點數(shù)量的復(fù)雜度O(1)
   • 多態(tài)：鏈表節(jié)點使用void*指針來保存節(jié)點值

ch4 字典

1. redis的字典使用哈希表作為底層實現(xiàn)，一個哈希表里面可以有多個哈希表節(jié)點，而每個哈希表節(jié)點就保存了字典中的一個鍵值對。
   • redis字典使用的哈希表由dict.h/dictht結(jié)構(gòu)定義：
     
     dictht
   • 哈希表節(jié)點：
     
     dictEntry
   • 字典：
     
     dict
     • type：一個指向dictType結(jié)構(gòu)的指針，每個dictType結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對的函數(shù)，redis會為用途不同的字典設(shè)置不同的類型特定函數(shù)。
     • privdata：保存了需要傳給那些類型特定函數(shù)的可選參數(shù)

普通狀態(tài)下的字典

2. 哈希算法
   當(dāng)要將一個新的鍵值對添加到字典里面時，程序需要先根據(jù)鍵值對的鍵計算出哈希值和索引值，然后根據(jù)索引值，將包含新鍵值對的哈希表節(jié)點放到哈希表數(shù)組的指定索引上面。

3. 解決鍵沖突
   當(dāng)由兩個或以上數(shù)量的鍵被分配到哈希表數(shù)組的同一個索引上面時，我們稱這些鍵發(fā)生了沖突。

   redis的哈希表使用鏈地址發(fā)來解決鍵沖突，沒個哈希表節(jié)點都有一個next指針，多個哈希表節(jié)點可以以用next指針構(gòu)成一個單向鏈表，被分配到同一個索引上的多個節(jié)點可以用這個單向鏈表連接起來。

   因為dictEntry節(jié)點組成的鏈表沒有指向鏈表表尾的指針，所以為了速度考慮，程序總是將新節(jié)點添加到鏈表的表頭位置，排在其他已有節(jié)點的前面。

4. rehash
   隨著操作的不斷執(zhí)行，哈希表保存的鍵值對會逐漸增多或者逐漸減少，為了讓哈希表的負(fù)載因子維持在一個合理的范圍之內(nèi)，當(dāng)哈希表保存的鍵值對數(shù)量太多或者太少時，程序要對哈希表進(jìn)行相應(yīng)的擴(kuò)展或收縮。
   過程：

   1. 為字典的ht[1]哈希表分配空間，空間的大小取決于要執(zhí)行的操作以及ht[0]當(dāng)前包含的鍵值對數(shù)量
      • 擴(kuò)展：ht[1]的大小為第一個大于等于ht[0].used*2的2^n
      • 收縮：ht[1]的大小第一個大于等于ht[0].used的2^n
   2. 將保存在ht[0]中所有的鍵值對rehash到ht[1]上面：rehash指的是重新計算鍵的哈希值和索引值，然后將鍵值對放置到ht[1]哈希表的指定位置上。
   3. 當(dāng)ht[0]包含的所有鍵值對都遷移到ht[1]之后，釋放ht[0]，將ht[1]設(shè)置為ht[0]，并在ht[1]上新創(chuàng)建一個空白哈希表，為下一次rehash做準(zhǔn)備。

5. 哈希表的擴(kuò)展與收縮
   當(dāng)以下條件中的任意一個被滿足時，程序會自動對哈希表執(zhí)行擴(kuò)展操作：

   1. 服務(wù)器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于1
   2. 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于5

   負(fù)載因子 = 哈希表已保存節(jié)點數(shù)量 / 哈希表大小
   

   在執(zhí)行BGSAVE命令或BGREWRITEAOF命令的過程中，redis需要創(chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程，而大多數(shù)操作系統(tǒng)都采用寫時拷貝（copy-on-write）技術(shù)來優(yōu)化子進(jìn)程使用效率，所以在子進(jìn)程存在期間，服務(wù)器會提高擴(kuò)展操作所需的負(fù)載因子，盡量避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展操作，避免不必要的內(nèi)存寫入操作，最大限度節(jié)約內(nèi)存。

   3. 當(dāng)負(fù)載因子小于0.1時，程序自動開始對哈希表執(zhí)行收縮操作。

6. 漸進(jìn)式rehash
   擴(kuò)展或收縮哈希表需要將ht[0]里面的所有鍵值對rehash到ht[1]里面，但是這個rehash動作并不是一次性、集中式地完成的，而是分多次、漸進(jìn)式地完成的。若一次性完成，當(dāng)哈希表里的鍵值對數(shù)量十分大（百萬、千萬級），龐大的計算量可能會導(dǎo)致服務(wù)器在一段時間內(nèi)停止服務(wù)。
   redis采用漸進(jìn)式rehash，步驟如下：

   1. 為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表
   2. 在字典中維持一個rehashidx，并將它的值設(shè)置為0，表示rehash工作正式開始。
   3. 在rehash期間，每次對字典執(zhí)行添加、刪除、查找或者更新操作時，程序除了執(zhí)行指定的操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當(dāng)rehash工作完成之后，程序?qū)ehashidx屬性的增一
   4. 隨著字典操作的不斷執(zhí)行，最終在某個時間上，ht[1]的所有鍵值對都會被rehash至ht[1]，這是將rehashidx設(shè)置為-1，表示rehash操作完成。

   在漸進(jìn)式rehash期間，字典會同時使用ht[0]和ht[1]兩個哈希表，所以在漸進(jìn)式rehash期間，字典的刪除、查找、更新等操作會在兩個哈希表上進(jìn)行。

待續(xù)...

如果覺得還不錯，關(guān)注公眾號獲取更多優(yōu)質(zhì)文章 ~

微信搜一搜 四方云和