第二章 簡單動(dòng)態(tài)字符串 （SDS）

1、SDS的定義

struct sdshdr {
      // 記錄數(shù)組中已經(jīng)使用的字節(jié)數(shù)控，等于SDS所保存的字符串的長度
      int len;

       // 記錄buf數(shù)組中未使用的字節(jié)數(shù)量 
       int free;
       
       // 字節(jié)數(shù)組，用于保存字符串
       char[] buf;
}

比如，free為0，則表示SDS沒有分配任何未使用的空間，len屬性位5，則表示這個(gè)SDS保存了一個(gè)五字節(jié)長的字符串，buf的最后一個(gè)字符為'\0'，這和c的字符串是一樣的；
需要說明的是，在C語言中使用長度為N+1的字符數(shù)組來表示長度為N的字符串，最后一個(gè)空字符為'\0'，表示字符串結(jié)束。

2、SDS和C字符串的區(qū)別

2.1 常數(shù)復(fù)雜度獲取字符串長度

對(duì)于C字符串來說，因?yàn)闆]有記錄字符串長度，所以如果想要知道字符串長度，則需要遍歷一次字符串，這個(gè)操作的時(shí)間復(fù)雜度為O(N)，而SDS中的len屬性記錄了SDS當(dāng)前字符串的長度，所以可以直接獲取，這個(gè)操作的時(shí)間復(fù)雜度是O(1)；而且SDS的len屬性是在操作SDS API的時(shí)候自動(dòng)完成的，不需要自己維護(hù)，所以不需要擔(dān)心安全問題；

2.2 SDS杜絕緩沖區(qū)溢出

因?yàn)镃字符串不記錄自身長度的原因，所以容易造成緩沖區(qū)溢出，比如，有兩個(gè)字符串在內(nèi)存中緊挨著：

...   R E D I S \0 M O N G O D B \0 ...

其中S1為字符串 “REDIS”，s2為字符串 “MONGODB”，C語言中有個(gè)字符串操作函數(shù) strcat(char* dest, har* src) 可以將src字符串拼接到dest字符串的后面，如果dest剩余的內(nèi)存空間無法再容納src，則就會(huì)發(fā)生緩沖區(qū)溢出，比如執(zhí)行：
strcat(S1, "CLUSTER")，內(nèi)存中的S2字符串就會(huì)被覆蓋掉：

...   R E D I S  C L U S T E R \0 ...

而SDS在進(jìn)行字符串修改之前，會(huì)先檢查SDS的空間是否滿足修改所需的空間要求，如果不滿足，則會(huì)先擴(kuò)展SDS的空間，然后再進(jìn)行修改。

2.3 SDS減少修改字符串時(shí)帶來的內(nèi)存重分配次數(shù)

對(duì)于C字符串來說，將字符串變長或者縮短之前，都需要進(jìn)行內(nèi)存重新分配，否則會(huì)出現(xiàn)問題，如果字符串變長之前不進(jìn)行內(nèi)存重新分配，則會(huì)出現(xiàn)緩沖區(qū)溢出問題，如果在縮短字符串之前不進(jìn)行內(nèi)存重分配，則會(huì)發(fā)生內(nèi)存泄漏問題；

SDS使用free屬性來代表buf中還有多少字符可以使用，SDS使用空間預(yù)分配和惰性空間釋放策略來避免這個(gè)問題；

2.3.1 空間預(yù)分配

SDS在需要對(duì)空間進(jìn)行擴(kuò)展的時(shí)候，會(huì)額外擴(kuò)展一些空間，使用free屬性來維護(hù)，避免頻繁分配內(nèi)存；額外分配的內(nèi)存大小由以下公式?jīng)Q定：

• 如果對(duì)SDS進(jìn)行修改之后，SDS的長度（len屬性）將小于1MB，那么程序?qū)⒎峙浜蚻en屬性同樣大小的未使用空間，比如，在SDS進(jìn)行修改之后，len屬性變?yōu)?3字節(jié)，那么程序也會(huì)分配13字節(jié)未使用的空間（free屬性），此時(shí)free和len相等，buf的實(shí)際長度為13 + 1 + 13 = 27字節(jié)；
• 如果對(duì)SDS進(jìn)行修改之后，SDS的長度大于1MB空間，那么SDS會(huì)分配1MB的未使用空間；

2.3.2 惰性空間釋放

在SDS字符串進(jìn)行縮短字符串操作時(shí)，SDS并不會(huì)執(zhí)行內(nèi)存重分配將對(duì)于的空間進(jìn)行回收，而是記錄在free屬性里面，等待后續(xù)字符串?dāng)U大時(shí)使用，這就避免了字符串造成時(shí)的頻繁內(nèi)存操作；當(dāng)然，如果確認(rèn)字符串空間已經(jīng)足夠，那么可以調(diào)用SDS的API進(jìn)行內(nèi)存回收。

2.4 二進(jìn)制安全

C語言中使用空字符'\0'來表示字符串的末尾，也就是字符串中間不能存在空字符串，否則字符串就會(huì)被截?cái)?，而?duì)于一些二進(jìn)制數(shù)據(jù)，難免會(huì)使用到空字符，而C字符串就無法表示這些數(shù)據(jù)，SDS使用buf來存儲(chǔ)字符串，存儲(chǔ)的是什么，讀出來的就是什么，是二進(jìn)制安全的表示方式。所以Redis不僅可以保存字符串，還可以保存二進(jìn)制文件，比如視頻、圖片等。

2.5 兼容部分C字符串函數(shù)

SDS的buf里面存儲(chǔ)的字符串依然保持以'\0'結(jié)尾的慣例，所以可以使用部分C字符串函數(shù)，比如strcat，這樣，SDS就不需要再重復(fù)編寫一遍字符串操作函數(shù)了。

第三章 鏈表

3.1 Redis鏈表實(shí)現(xiàn)的特性

• 雙端鏈表：每個(gè)鏈表節(jié)點(diǎn)帶有prev和next指針，獲取某個(gè)節(jié)點(diǎn)的前置或者后置節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)；
• 無環(huán)：表頭的prev和表尾的next都指向NULL，對(duì)鏈表的訪問以NULL為結(jié)尾；
• 帶表頭指針和表位指針：通過list的head和tail指針，獲取表頭或者表尾的時(shí)間復(fù)雜度為O(1)；
• 帶鏈表長度計(jì)數(shù)器：使用list結(jié)構(gòu)的len屬性來表示鏈表的長度，程序獲取鏈表長度的時(shí)間復(fù)雜度為O(1)
• 多態(tài)：鏈表的每個(gè)節(jié)點(diǎn)使用void*指針來保存節(jié)點(diǎn)的值，并且通過dup、free、match三個(gè)屬性為節(jié)點(diǎn)設(shè)置類型特定函數(shù)，所以鏈表合一用于保存各種不同類型的值；

第四章 字典

字典：又被稱為符號(hào)表、關(guān)聯(lián)數(shù)組、映射（map），是哈希鍵的底層實(shí)現(xiàn)
Redis的字典使用哈希表作為底層實(shí)現(xiàn)；

4.1 哈希表

dict.h/dictht

typedef struct dictht {
    
      // 哈希表數(shù)組
      dictEntry ** table;

      // 哈希表大小
      unsigned long size;

       // 哈希表大小掩碼，用于計(jì)算索引值，總是等于 size - 1
       unsigned long sizemask;

       // 該哈希表已有節(jié)點(diǎn)的數(shù)量
       unsigned long used; 

} dictht;

4.2 哈希表節(jié)點(diǎn)

dictEntry 保存鍵值對(duì)信息。

typedef struct dictEntry {
    
      // 鍵
      void* key;

      // 值
      union {
            void* val;
              ...
       } v;

     // 下一個(gè)哈希節(jié)點(diǎn)，形成鏈表，用于解決哈希沖突的問題
     struct dictEntry* next;

} dictEntry;

4.3字典

dict.h/dict

typedef struct dict {
   
      // 類型特定函數(shù)
      dictType* type;

      // 私有數(shù)據(jù)
      void* privdata;

      // 哈希表
      dicthd ht[2];

      // rehash 索引，當(dāng)rehash不在進(jìn)行時(shí)，值為-1
      int rehashidx;  

} dict;

ht屬性是包含兩個(gè)哈希表的數(shù)組，一般情況下，只有ht[0]會(huì)被使用，ht[1]只有在rehash的時(shí)候才會(huì)用到，rehashidx用于標(biāo)記rehash的進(jìn)度，如果當(dāng)前不在進(jìn)行rehash操作，則rehashidx為-1；

4.4 哈希算法

當(dāng)要將一個(gè)新的鍵值對(duì)添加到字典中時(shí)，需要先根據(jù)鍵值對(duì)的鍵來計(jì)算出哈希值和索引值，然后根據(jù)索引值將包含新鍵值對(duì)的哈希節(jié)點(diǎn)放到對(duì)應(yīng)的位置上去；
計(jì)算哈希值的函數(shù)在字典的type屬性里面；
當(dāng)一個(gè)數(shù)組的長度是2的冪次方時(shí)，有一個(gè)很好的特性是，
index = hash & (len -1)
這可能就是sizemask的作用；

4.5 解決鍵沖突

當(dāng)有兩個(gè)以上的鍵被分配到同一個(gè)索引上的時(shí)候，稱這些鍵發(fā)生了沖突，Redis使用鏈地址法來解決哈希沖突，每個(gè)鍵值對(duì)節(jié)點(diǎn)都是一個(gè)鏈表節(jié)點(diǎn)，包含next指針；

4.6 rehash

隨著操作的不斷執(zhí)行，哈希表保存的鍵值對(duì)會(huì)逐漸的增多或者減少，為了讓哈希表的負(fù)載因子保持在一個(gè)合理的范圍，當(dāng)哈希表的鍵值對(duì)太多或者太少時(shí)，程序需要進(jìn)行rehash操作。

Redis進(jìn)行rehash操作的步驟如下：

• 為字典ht[1]分配空間，分配的大小取決于要執(zhí)行的操作，和ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量（ht[0].used）
  • 如果執(zhí)行的擴(kuò)展操作，那么ht[1]的大小為第一個(gè)大于等于 ht[0].used * 2 的2次冪；
  • 如果執(zhí)行的是收縮操作，那么ht[1]的大小為第一個(gè)大于等于ht[0].used的2次冪；
• 將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上面
• 當(dāng)ht[0]的所有鍵值對(duì)都rehash到ht[1]之后，釋放ht[0]，然后將ht[1]當(dāng)做ht[0]；

4.7 哈希表的收縮與擴(kuò)展

當(dāng)以下條件任意一個(gè)滿足時(shí)，程序會(huì)自動(dòng)開始對(duì)哈希表進(jìn)行擴(kuò)展操作：

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

負(fù)載因子的計(jì)算公式為：
load_factor = ht[0].used / ht[0].size

Redis在執(zhí)行BGSAVE或者BGREWRITEAOF命令時(shí)，需要fork出紫子進(jìn)程，大多數(shù)操作系統(tǒng)采用寫時(shí)復(fù)制的技術(shù)來優(yōu)化進(jìn)程的內(nèi)存使用效率，如果在這個(gè)時(shí)候進(jìn)行rehash，子進(jìn)程也需要寫，如果避免在這個(gè)時(shí)候進(jìn)行擴(kuò)展，則可以最大限度的節(jié)約內(nèi)存。

當(dāng)哈希表的負(fù)載因子小于0.1時(shí)，程序會(huì)自動(dòng)開始對(duì)哈希表進(jìn)行收縮操作。

4.8 漸進(jìn)式rehash

rehash操作并不是一次性完成的，因?yàn)楣１碇械逆I值對(duì)數(shù)量可能非常大，如果一次性完成所有鍵值對(duì)的rehash操作，那么Redis可能會(huì)停止服務(wù)而進(jìn)行rehash，為了避免這個(gè)問題，Redis采用分多次，漸進(jìn)式的完成rehash操作；

下面是Redis進(jìn)行漸進(jìn)式rehash的詳細(xì)步驟：

• 為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表
• 在字典中維護(hù)一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它的值設(shè)置為0，表示rehash工作正式開始；
• 在rehash進(jìn)行期間，每次對(duì)字典的訪問操作，程序除了執(zhí)行指定的操作之外，還會(huì)順帶將ht[0]哈希表在rehashidx索引上的鍵值對(duì)rehash到ht[1]，當(dāng)rehash完成之后，rehashidx + 1，表示下一次rehash操作的鍵值對(duì)索引是rehashidx + 1
• 隨著字典的不斷操作，到某個(gè)時(shí)間點(diǎn)，ht[0]上的所有鍵值對(duì)都會(huì)rehash到ht[1]，此時(shí)設(shè)置rehashidx = -1，表示rehash已經(jīng)完成；

在rehash期間，字典會(huì)同時(shí)持有ht[0]和ht[1]兩張哈希表，對(duì)于查找來說，會(huì)現(xiàn)在ht[0]找，找不到再去ht[1]找， 對(duì)于刪除操作也是需要操作兩張哈希表，而對(duì)于插入操作，所有新插入的鍵值對(duì)只會(huì)在ht[1]里面，所以保證了ht[0]里面的鍵值對(duì)只減不增，這樣rehash總是會(huì)結(jié)束。

第五章 跳躍表

跳躍表是有序列表的底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，Redis的跳躍表實(shí)現(xiàn)包括zskiplist和zskiplistNode兩個(gè)結(jié)構(gòu)，每個(gè)跳躍表的層高都是1~32之間的隨機(jī)數(shù)，在同一個(gè)跳躍表中，每一個(gè)節(jié)點(diǎn)的成員變量必須唯一（類似于Set），當(dāng)多個(gè)節(jié)點(diǎn)的分值相同時(shí)，節(jié)點(diǎn)按照成員對(duì)象的大小進(jìn)行排序。

https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
https://juejin.im/post/57fa935b0e3dd90057c50fbc

下面是一個(gè)跳躍表圖片：

skiplist

查找的時(shí)候先從最高層開始找，逐漸二分下降層數(shù)，整體上就是一個(gè)二分查找算法的最佳實(shí)踐。

下面是一個(gè)再跳躍表里面查找23這個(gè)值的例子：

search in skiplist

第六章 整數(shù)集合

• 整數(shù)集合是集合鍵的底層實(shí)現(xiàn)之一；
• 整數(shù)集合的底層實(shí)現(xiàn)為數(shù)組，這個(gè)數(shù)組以有序，無重復(fù)的方式存儲(chǔ)集合元素，當(dāng)有需要的時(shí)候會(huì)改變數(shù)組的類型（encode）
• 升級(jí)操作為整數(shù)集合帶來了操作上的靈活性，并且盡可能的節(jié)約了內(nèi)存；
• 整數(shù)集合只支持升級(jí)操作，不支持降級(jí)操作

第七章 壓縮列表

壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)列表鍵只包含少量的列表項(xiàng)，并且每個(gè)列表項(xiàng)要么就是小整數(shù)值，要么就是簡短的字符串，那么Redis就會(huì)使用壓縮列表來進(jìn)行實(shí)現(xiàn)；
當(dāng)一個(gè)哈希鍵只包含少量鍵值對(duì)，并且每個(gè)鍵值對(duì)的鍵和值要么是小整數(shù)，要么是簡短的字符串，那么Redis就會(huì)使用壓縮列表來實(shí)現(xiàn)哈希鍵。
壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的一種順序存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。

第八章 對(duì)象

Redis基于前面介紹的那些數(shù)據(jù)結(jié)構(gòu)，構(gòu)建了一個(gè)對(duì)象系統(tǒng)，這個(gè)系統(tǒng)包括字符串對(duì)象、列表對(duì)象、哈希對(duì)象、集合對(duì)象和有序集合對(duì)象五種類型的對(duì)象。
Redis通過引用計(jì)數(shù)技術(shù)，當(dāng)程序不再使用某個(gè)對(duì)象時(shí)，這個(gè)對(duì)象所占用的內(nèi)存就會(huì)被自動(dòng)釋放，還基于引用計(jì)數(shù)實(shí)現(xiàn)了對(duì)象共享機(jī)制，從而來實(shí)現(xiàn)節(jié)約內(nèi)存的目的。
Redis的對(duì)象還記錄了訪問時(shí)間，這個(gè)信息可以用于計(jì)算數(shù)據(jù)庫鍵的空轉(zhuǎn)時(shí)間，空轉(zhuǎn)時(shí)間較長的那些對(duì)象有可能被服務(wù)器刪除掉。

8.1 對(duì)象類型和編碼

Redis使用對(duì)象來表示數(shù)據(jù)庫中的鍵值對(duì)，每當(dāng)我們?cè)跀?shù)據(jù)庫中新創(chuàng)建一個(gè)鍵值對(duì)時(shí)，我們至少會(huì)創(chuàng)建兩個(gè)對(duì)象，一個(gè)鍵對(duì)象和一個(gè)值對(duì)象。Redis使用redisObject來表示對(duì)象：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    
    // 指向底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針
    void *ptr;
} robj;

8.1.1 類型

對(duì)象的type屬性記錄了對(duì)象的類型，這個(gè)屬性值可以是下面幾種中的一個(gè)：

REDIS_STRING        ：字符串對(duì)象
REDIS_LIST              ：列表對(duì)象  
REDIS_HASH            ：哈希對(duì)象
REDIS_SET               ：集合對(duì)象
REDIS_ZSET             ：有序集合對(duì)象

在Redis中，鍵值對(duì)的鍵總是一個(gè)字符串對(duì)象，而值可以是上面說到的五種對(duì)象之一，可以使用TYPE命令來查看一個(gè)鍵值對(duì)的值的對(duì)象類型。

8.1.2 編碼

編碼決定了底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?？梢酝ㄟ^OBJECT ENCODING 命令來查看編碼信息；Redis沒有將一種類型關(guān)聯(lián)到一種特定類型的編碼上，極大的提升了Redis的靈活性和效率，Redis可以根據(jù)對(duì)象的特征進(jìn)行不同的編碼，比如，在一個(gè)列表鍵包含較少的列表項(xiàng)時(shí)，Redis就會(huì)使用壓縮列表來實(shí)現(xiàn)，而當(dāng)壓縮列表不再適應(yīng)的情況下，就會(huì)使用列表來實(shí)現(xiàn)。

8.2 字符串對(duì)象

字符串對(duì)象的編碼可以是int、raw或者embstr。

• 如果一個(gè)字符串保存的是整數(shù)值，那么編碼就是int；
• 如果字符串對(duì)象保存的是一個(gè)字符串，并且字符串長度大于32字節(jié)，那么就會(huì)使用SDS來表示，編碼為raw；
• 如果字符串對(duì)象保存的是一個(gè)長度小于等于32字節(jié)的字符串，那么就會(huì)使用embstr編碼來保存；
• 如果保存的是浮點(diǎn)數(shù)，那么也是使用字符串的方式保存；

embstr編碼和raw的效果是一樣的，但是embstr使用一次內(nèi)存分配/回收來管理RedisObject結(jié)構(gòu)和sdshdr結(jié)構(gòu)，而raw會(huì)調(diào)用兩次內(nèi)存分配。并且embstr的redisObject和sdshdr是連續(xù)分布的，所以可以更好的利用緩存帶來的優(yōu)勢。

8.3 列表對(duì)象

列表對(duì)象的編碼可以是ziplist或者linkedlist。當(dāng)列表對(duì)象可以同時(shí)滿足下面兩個(gè)條件時(shí)，使用ziplist來保存：

• 列表對(duì)象保存的所有字符串長度都小于64字節(jié)；
• 列表對(duì)象保存的元素?cái)?shù)量少于512個(gè)；
  如果不能滿足這兩個(gè)對(duì)象，則使用linkedlist來實(shí)現(xiàn)；對(duì)于使用ziplist的列表對(duì)象，如果其中一個(gè)條件不再滿足的時(shí)候，就會(huì)進(jìn)行編碼轉(zhuǎn)換，轉(zhuǎn)換成使用linkedlist來進(jìn)行保存。

8.4 哈希對(duì)象

哈希對(duì)象的編碼可以是ziplist或者h(yuǎn)ashtable，當(dāng)哈希對(duì)象可以同時(shí)滿足下面兩個(gè)條件時(shí)，使用ziplist，否則使用hashtab：

• 哈希對(duì)象保存的所有鍵值對(duì)的鍵和值的字符串長度都小于64字節(jié)；
• 哈希對(duì)象保存的鍵值對(duì)數(shù)量小于512個(gè)；

8.5 集合對(duì)象

集合對(duì)象的編碼可以是intset、hashtable，當(dāng)集合對(duì)象可以同時(shí)滿足下面兩個(gè)條件時(shí)，使用intset，否則使用hashtabe：

• 集合對(duì)象保存的所有元素都是整數(shù)值；
• 集合對(duì)象保存的元素?cái)?shù)量不超過512個(gè)；

8.6 有序集合對(duì)象

有序集合對(duì)象的編碼可以是ziplist或者skiplist，在Redis中，同時(shí)使用了跳躍表和字典來實(shí)現(xiàn)有序集合，zset的zsl屬性是一個(gè)跳躍表，它按照元素的分值從小打到的保存元素，這樣就可以實(shí)現(xiàn)比如范圍操作之類的功能，而zset的dict屬性使用字段來存儲(chǔ)了集合的成員到分值的映射，這樣基于成員查找分值的時(shí)間復(fù)雜度就是O(1)，同時(shí)需要說明的是，Redis使用對(duì)象共享技術(shù)，所以同時(shí)使用跳躍表和字典不會(huì)造成內(nèi)存浪費(fèi)。

同時(shí)使用跳躍表和字典來實(shí)現(xiàn)有序集合，主要是為了實(shí)現(xiàn)效率上的考慮，如果只使用字典來實(shí)現(xiàn)，那么雖然根據(jù)成員查詢分值的時(shí)間復(fù)雜度是O(1)，但是因?yàn)樽值湟詿o序的方式存儲(chǔ)元素，所以在執(zhí)行范圍操作的時(shí)候，就需要先排序再操作，時(shí)間復(fù)雜度是O(NlogN)，還要?jiǎng)?chuàng)建一個(gè)額外的數(shù)組來存儲(chǔ)排序后的元素（O(N)），如果只使用跳躍表，那么雖然范圍查找沒問題，但是基于成員查詢分值的操作就會(huì)從O(1)提升到O(N)，所以同時(shí)使用兩種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。

當(dāng)有序集合對(duì)象可以同時(shí)滿足下面兩個(gè)條件時(shí)，對(duì)象使用ziplist來實(shí)現(xiàn)，否則使用skiplist來實(shí)現(xiàn)：

• 有序集合保持的元素?cái)?shù)量小于128個(gè)；
• 有序集合保存的所有元素的長度小于64字節(jié)；

8.8 內(nèi)存回收

Redis使用引用計(jì)數(shù)來實(shí)現(xiàn)對(duì)象跟蹤，對(duì)象的引用計(jì)數(shù)會(huì)隨著對(duì)象的使用而發(fā)生變化：

• 在創(chuàng)建一個(gè)新對(duì)象時(shí)，引用計(jì)數(shù)的值會(huì)被初始化為1；
• 當(dāng)一個(gè)對(duì)象被一個(gè)程序引用時(shí)，它的引用計(jì)數(shù)值會(huì)加1；
• 當(dāng)對(duì)象不再被一個(gè)程序使用時(shí)，它的引用計(jì)數(shù)會(huì)減1；
• 當(dāng)對(duì)象的引用計(jì)數(shù)變?yōu)?時(shí)，對(duì)象所占用的內(nèi)存會(huì)被釋放；

8.9 對(duì)象共享

當(dāng)A和B需要的對(duì)象一樣時(shí)，Redis就會(huì)使用對(duì)象共享技術(shù)，不會(huì)創(chuàng)建多個(gè)對(duì)象，而是會(huì)復(fù)用現(xiàn)有的對(duì)象。Redis只會(huì)共享包含整數(shù)值的字符串對(duì)象，因?yàn)槠渌淖址畬?duì)象的對(duì)比需要消耗更多的CPU，得不償失；

8.10 對(duì)象的空轉(zhuǎn)時(shí)常

每個(gè)對(duì)象都會(huì)記錄對(duì)象最后一次被訪問的時(shí)間戳，當(dāng)執(zhí)行命令OBJECT IDLETIME時(shí)，就是將當(dāng)前時(shí)間減去對(duì)象的這個(gè)時(shí)間戳，需要注意的是，這個(gè)命令執(zhí)行時(shí)，對(duì)象的lru（最后訪問時(shí)間戳）不會(huì)被更新?？辙D(zhuǎn)時(shí)間還可以用于Redis服務(wù)器淘汰鍵值對(duì)，如果開啟了maxmemory選項(xiàng)，并且服務(wù)器用于回收內(nèi)存的算法為valatile-lru或者allkeys-lru時(shí)，那么服務(wù)器占用的內(nèi)存數(shù)超過maxmemory時(shí)，就會(huì)將空轉(zhuǎn)時(shí)間較長的部分鍵值對(duì)優(yōu)先釋放內(nèi)存；

第九章 數(shù)據(jù)庫

Redis默認(rèn)情況下會(huì)初始化16個(gè)數(shù)據(jù)庫，每個(gè)數(shù)據(jù)庫由redisDb結(jié)構(gòu)表示。
每個(gè)Redis客戶端都會(huì)有自己的目標(biāo)數(shù)據(jù)庫，在客戶端執(zhí)行讀寫數(shù)據(jù)庫的時(shí)候，目標(biāo)數(shù)據(jù)庫就會(huì)成員操作對(duì)象。默認(rèn)情況下，目標(biāo)數(shù)據(jù)庫為0號(hào)數(shù)據(jù)庫，可以通過執(zhí)行SELECT命令來切換數(shù)據(jù)庫；在服務(wù)器內(nèi)部的redisClient結(jié)構(gòu)的db屬性記錄了客戶端當(dāng)前的目標(biāo)數(shù)據(jù)庫，這個(gè)屬性是指向redisDb結(jié)構(gòu)的指針；

Redis的redisDb結(jié)構(gòu)里面有一個(gè)dict屬性，它記錄了數(shù)據(jù)庫中的所有鍵值對(duì)，我們將這個(gè)字段稱為鍵空間。

Redis的redisDb結(jié)構(gòu)中的expires字典保存了數(shù)據(jù)庫中所有鍵的過期時(shí)間，我們稱這個(gè)字典為過期字典，當(dāng)執(zhí)行了為鍵值對(duì)設(shè)置過期時(shí)間的命令之后，就會(huì)在expires字典里面插入一個(gè)新的鍵值對(duì)，值為過期時(shí)間。當(dāng)為某個(gè)鍵移除過期時(shí)間時(shí)，相應(yīng)的也會(huì)在過期字典里面將其刪掉。

9.1 過期鍵刪除策略

如果一個(gè)鍵過期了，那么它被刪除的策略有三種：

• 定時(shí)刪除：在設(shè)置鍵的過期時(shí)間的同時(shí)，設(shè)置一個(gè)定時(shí)器，定時(shí)器在鍵的過期時(shí)間來臨時(shí)，立即刪除鍵；
• 惰性刪除：放任鍵過期不管，但是每次從鍵空間中獲取鍵時(shí)，都檢查鍵是否已經(jīng)過期，如果過期的話，則刪除鍵，否則返回；
• 定期刪除：每隔一段時(shí)間，就對(duì)數(shù)據(jù)庫進(jìn)行一次檢查，刪除里面的過期鍵，至于要?jiǎng)h除多少鍵，以及檢查多少個(gè)數(shù)據(jù)庫，則由算法決定；

定時(shí)刪除對(duì)內(nèi)存最優(yōu)化，那些過期的鍵都能及時(shí)被清理，而如果有大量的鍵需要清理則對(duì)CPU不太友好，需要大量的CPU時(shí)間；惰性刪除對(duì)內(nèi)存不太友好，但是對(duì)CPU友好；定期刪除策略是對(duì)前兩種策略的折中方案：

• 定期刪除策略每隔一段時(shí)間執(zhí)行一次過期鍵刪除操作，并通過限制刪除操作執(zhí)行的時(shí)常和頻率來減少刪除操作對(duì)CPU時(shí)間的影響；
• 除此之外，通過定期刪除過期鍵，可以減少過期鍵帶來的內(nèi)存浪費(fèi)；

Redis實(shí)際使用的是惰性刪除和定期刪除兩種策略，服務(wù)器可以很好的在合理使用CPU和避免內(nèi)存空間浪費(fèi)之間取得平衡；

9.1.1 惰性刪除策略的實(shí)現(xiàn)

過期鍵的惰性刪除由db.c/expireIfNeeded函數(shù)實(shí)現(xiàn)，所有讀寫Redis數(shù)據(jù)庫的命令在執(zhí)行之前都會(huì)調(diào)用這個(gè)函數(shù)進(jìn)行鍵過期檢查；

• 如果輸入鍵已經(jīng)過期，那么函數(shù)將輸入鍵從數(shù)據(jù)庫中刪除；
• 如果輸入鍵不過期，那么這個(gè)函數(shù)什么也不做；

9.1.2 定期刪除策略的實(shí)現(xiàn)

定期刪除由redis.c/activeExpieCycle函數(shù)實(shí)現(xiàn)，每當(dāng)Redis的服務(wù)器周期性的執(zhí)行serverCorn函數(shù)時(shí)，activeExpieCycle函數(shù)也會(huì)被調(diào)用，它在規(guī)定的時(shí)間內(nèi)，分多次遍歷服務(wù)器中的各個(gè)數(shù)據(jù)庫，從數(shù)據(jù)庫的expires字典中隨機(jī)檢查一部分鍵的過期時(shí)間，并刪除其中的過期鍵。

9.2 AOF、RDB和復(fù)制功能對(duì)過期鍵的處理

9.2.1 生成RDB文件

在執(zhí)行SAVE或者BGSACE命令時(shí)，程序會(huì)對(duì)數(shù)據(jù)庫中的鍵進(jìn)行檢查，已經(jīng)過期的鍵不會(huì)被保存到數(shù)據(jù)庫中；

9.2.2 載入RDB文件

在啟動(dòng)Redis服務(wù)器時(shí)，如果服務(wù)器開啟了RDB功能，那么服務(wù)器將對(duì)RDB文件進(jìn)行載入：

• 如果服務(wù)器以主服務(wù)器模式運(yùn)行，那么在載入RDB文件時(shí)，程序會(huì)對(duì)保存的鍵進(jìn)行檢查，未過期的鍵會(huì)被保存到數(shù)據(jù)庫中，而過期的鍵則會(huì)被忽略。
• 如果服務(wù)器以從服務(wù)器運(yùn)行，那么在載入RDB文件時(shí)，文件中保存的所有鍵都會(huì)被載入到數(shù)據(jù)庫中，不過，因?yàn)橹鞣?wù)器在進(jìn)行數(shù)據(jù)同步時(shí)，從服務(wù)器的數(shù)據(jù)庫就會(huì)被清空，所以一般來講對(duì)從服務(wù)器也沒有影響。

9.2.3 AOF文件寫入

如果鍵過期被惰性刪除或者定期刪除了，那么會(huì)向AOF文件寫入一條DEL命令，來顯示的記錄該鍵已經(jīng)被刪除；

9.2.4 復(fù)制

當(dāng)服務(wù)器運(yùn)行在復(fù)制模式下時(shí)，從服務(wù)器的過期鍵刪除動(dòng)作由主服務(wù)器控制：

• 主服務(wù)器在刪除一個(gè)過期鍵之后，會(huì)顯示的向所有從服務(wù)器發(fā)送一條DEL命令，告訴從服務(wù)器刪除這個(gè)過期鍵；
• 從服務(wù)器沒有權(quán)利刪除過期鍵，所以從服務(wù)器在遇到過期鍵時(shí)不會(huì)刪除過期鍵，它會(huì)等待主服務(wù)器來控制自己。

第十章 RDB持久化

RDB文件會(huì)將當(dāng)前Redis數(shù)據(jù)庫中的所有鍵值對(duì)記錄到一個(gè)二進(jìn)制文件中，有兩個(gè)命令可以生成RDB文件，SAVE和BGSAVE；

SAVE命令會(huì)阻塞服務(wù)器進(jìn)程，直到RDB文件生成完成，BGSAVE則會(huì)派生出一個(gè)子進(jìn)程來負(fù)責(zé)生成RDB文件，而主進(jìn)程依然可以處理Redis的其他命令。RDB文件的載入沒有命令，是Redis在啟動(dòng)的時(shí)候自動(dòng)完成的，只要Redis檢測到RDB文件，就會(huì)自動(dòng)載入RDB文件到內(nèi)存，需要注意的是，因?yàn)锳OF文件的更新頻率更高，所以：

• 如果服務(wù)器開啟了AOF持久化功能，那么服務(wù)器會(huì)優(yōu)先使用AOF文件來還原數(shù)據(jù)庫；
• 只有在AOF功能處于關(guān)閉狀態(tài)，服務(wù)器才會(huì)使用RDB文件來還原數(shù)據(jù)庫；

第十一章 AOF持久化

AOF和RDB不一樣，AOF保存的是執(zhí)行過的命令，Redis會(huì)將所有執(zhí)行過寫命令追加到AOF文件中去，啟動(dòng)Redis服務(wù)器的時(shí)候恢復(fù)這個(gè)數(shù)據(jù)庫；

AOF分為命令追加、文件寫入、文件同步三個(gè)部分；

11.1 命令追加

當(dāng)AOF持久化功能處于打開狀態(tài)時(shí)，服務(wù)器在執(zhí)行完一個(gè)命令之后，會(huì)按照協(xié)議格式將被執(zhí)行的命令追加到服務(wù)器狀態(tài)的aof_buf緩沖區(qū)的末尾；

11.2 文件寫入 與同步

Redis的服務(wù)器其實(shí)就是一個(gè)事件循環(huán)，包括文件循環(huán)和時(shí)間循環(huán)，服務(wù)器在處理文件事件時(shí)可能會(huì)往aof_buf里面寫入內(nèi)容，所以在每次結(jié)束一次循環(huán)之前，會(huì)調(diào)用flushAppendOnlyFile函數(shù)，考慮是否需要將aof_buf里面的內(nèi)容保存到AOF文件里面去。flushAppendOnlyFile函數(shù)的行為由appendfasync選項(xiàng)的值來決定：

• always：將aof_buf里面的內(nèi)容寫入并同步到AOF文件；
• everysec：將aof_buf里面的內(nèi)容寫入到AOF文件，如果上次同步aof文件的時(shí)間距離現(xiàn)在超過1秒，那么再次對(duì)AOF文件進(jìn)行同步，并且這個(gè)事情由一個(gè)專門的線程負(fù)責(zé)；
• no：將aof_buf里面的內(nèi)存寫入到AOF文件，但并不對(duì)AOF文件進(jìn)行同步，何時(shí)同步由操作系統(tǒng)決定；

默認(rèn)為everysec。

11.3 AOF重寫

因?yàn)锳OF持久化是通過保存redis執(zhí)行的命令來實(shí)現(xiàn)的，隨著服務(wù)器運(yùn)行，這個(gè)文件會(huì)越來越大，甚至?xí)绊憆edis服務(wù)器，所以需要重寫AOF文件，重寫是通過讀取redis當(dāng)前數(shù)據(jù)庫狀態(tài)來實(shí)現(xiàn)的；比如原來一個(gè)列表是通過10次添加元素構(gòu)成的，重寫之后只需要一條命令即可，大大縮短了命令的數(shù)量。

AOF重寫需要執(zhí)行大量的寫入操作，所以這個(gè)函數(shù)的線程將長時(shí)間阻塞，這就會(huì)影響redis服務(wù)器處理正常的請(qǐng)求，所以AOF重寫的任務(wù)被設(shè)計(jì)成一個(gè)后臺(tái)進(jìn)程來完成；

不過，這里需要注意的是，子進(jìn)程在進(jìn)行AOF重寫的時(shí)候，主進(jìn)程還在繼續(xù)處理請(qǐng)求，而新的命令可能會(huì)對(duì)現(xiàn)有的數(shù)據(jù)庫狀態(tài)進(jìn)行變更，從而使得當(dāng)前的數(shù)據(jù)庫狀態(tài)和重寫后的AOF文件所保存的數(shù)據(jù)庫狀態(tài)不一致，為了解決這個(gè)問題，Redis服務(wù)器設(shè)置了一個(gè)AOF重寫緩沖區(qū)，這個(gè)緩存區(qū)在服務(wù)器創(chuàng)建子進(jìn)程之后開始使用，當(dāng)Redis服務(wù)器執(zhí)行完一個(gè)寫命令之后，它會(huì)同時(shí)將這個(gè)寫命令發(fā)送給AOF緩沖區(qū)和AOF重寫緩沖區(qū)，當(dāng)子進(jìn)程完成AOF重寫工作之后，它會(huì)向父進(jìn)程發(fā)送一個(gè)信號(hào)，父進(jìn)程在接收到這個(gè)信號(hào)之后，會(huì)進(jìn)程信號(hào)處理：

• 將AOF重寫緩沖區(qū)中的內(nèi)容全部寫入到新的AOF文件中；
• 對(duì)新的AOF文件進(jìn)行改名，原子的覆蓋原來的AOF文件；

第十二章 事件

Redis服務(wù)器是一個(gè)事件驅(qū)動(dòng)的程序，服務(wù)器需要處理兩類事件：

• 文件事件：也就是I/O事件，比如客戶端的連接上的讀寫請(qǐng)求；
• 時(shí)間事件：某些操作（比如serverCorn）需要在給定的時(shí)間點(diǎn)運(yùn)行，這就是時(shí)間事件；

12.1 文件事件

Redis基于Reactor模式開發(fā)了自己的事件處理器，這個(gè)處理器被稱為文件事件處理器（file event handler）

• 文件事件處理器使用I/O多路復(fù)用技術(shù)，同時(shí)監(jiān)聽多個(gè)套接字，并根據(jù)套接字目前執(zhí)行的任務(wù)設(shè)置不同的事件處理器；
• 當(dāng)被監(jiān)聽的套接字上有讀寫事件發(fā)生時(shí)，文件事件處理器就會(huì)調(diào)用相應(yīng)的處理器來處理這些事件；

12.2 時(shí)間事件

服務(wù)器將所有的時(shí)間事件都放在一個(gè)無序列表里面，每當(dāng)時(shí)間事件執(zhí)行器運(yùn)行時(shí)，它就遍歷整個(gè)列表，查找所有已到達(dá)的時(shí)間事件，并調(diào)用相應(yīng)的時(shí)間處理器。一般情況下服務(wù)器只會(huì)執(zhí)行serverCorn一個(gè)時(shí)間事件。

第十五章 復(fù)制

在Redis中，可以執(zhí)行SLAVEOF命令或者設(shè)置slaveof選項(xiàng)，讓一個(gè)服務(wù)器復(fù)制另外一個(gè)服務(wù)器，我們稱呼被復(fù)制的服務(wù)器為主服務(wù)器（master），而對(duì)主服務(wù)器進(jìn)行復(fù)制的則成為從服務(wù)器（slave）。

15.1 舊版本復(fù)制功能的實(shí)現(xiàn)（2.8版本之前）

Redis的復(fù)制分為同步（sync）和命令傳播（command propagate）兩個(gè)操作：

• 同步：同步操作用于將從服務(wù)器的數(shù)據(jù)庫狀態(tài)更新至服務(wù)器所處的數(shù)據(jù)庫狀態(tài)；
• 命令傳播：命令傳播用于在主服務(wù)器的數(shù)據(jù)庫狀態(tài)被修改，導(dǎo)致主從服務(wù)器數(shù)據(jù)庫狀態(tài)不一致時(shí)，讓主從服務(wù)器的數(shù)據(jù)庫重新回到一致狀態(tài)；

15.1.1 同步（sync）

當(dāng)客戶端向從服務(wù)器發(fā)送SLAVEOF命令，要求復(fù)制主服務(wù)器時(shí)，從服務(wù)器首先需要執(zhí)行同步操作，首先將從服務(wù)器的數(shù)據(jù)庫狀態(tài)更新到主服務(wù)器一致。
從服務(wù)器通過向主服務(wù)器發(fā)送SYNC命令來完成同步操作，以下是SYNC命令的執(zhí)行步驟：

• 從服務(wù)器向主服務(wù)器發(fā)送SYNC命令；
• 收到SYNC命令的主服務(wù)器開始執(zhí)行BGSAVE命令，在后臺(tái)生成一個(gè)RDB文件，并使用一個(gè)緩沖區(qū)記錄從現(xiàn)在開始執(zhí)行的所有寫命令；
• 當(dāng)主服務(wù)器的BGSAVE命令執(zhí)行完成時(shí)，主服務(wù)器會(huì)將生成的RDB文件發(fā)送給從服務(wù)器，從服務(wù)器接收并載入這個(gè)RDB文件；
• 主服務(wù)器將記錄在緩存區(qū)里面的所有寫命令發(fā)送給從服務(wù)器，從服務(wù)器執(zhí)行這些寫命令，將自己的狀態(tài)更新至主服務(wù)器當(dāng)前的狀態(tài)。

15.1.2 命令傳播（command propagate）

當(dāng)同步操作完成之后，主從服務(wù)器兩者的數(shù)據(jù)庫狀態(tài)將達(dá)到一致狀態(tài)，但是這種狀態(tài)并不是一成不變的，如果主服務(wù)器的數(shù)據(jù)庫被改變，則一致就不再存在。

為了讓從服務(wù)器和主服務(wù)器保持一致，主服務(wù)器需要對(duì)從服務(wù)器執(zhí)行命令傳播，主服務(wù)器會(huì)將自己執(zhí)行的寫命令，也就是會(huì)造成主從數(shù)據(jù)庫狀態(tài)不一致的命令，發(fā)送給從服務(wù)器執(zhí)行，當(dāng)從服務(wù)器執(zhí)行之后，主從數(shù)據(jù)庫狀態(tài)又會(huì)變成一致。

15.2 舊版（2.8版本之前）復(fù)制功能的缺陷

在Redis中，從服務(wù)器對(duì)主服務(wù)器的復(fù)制可以分為以下兩種情況：

• 初次復(fù)制：從服務(wù)器以前沒用復(fù)制過任何主服務(wù)器，或者從服務(wù)器當(dāng)前要復(fù)制的主服務(wù)器和上一次復(fù)制的主服務(wù)器不同；
• 斷線后重新復(fù)制：處于命令傳播階段的主從服務(wù)器因?yàn)榫W(wǎng)絡(luò)原因中斷了復(fù)制，但從服務(wù)器通過自動(dòng)重連連接上了主服務(wù)器，并繼續(xù)復(fù)制主服務(wù)器；

對(duì)于初次復(fù)制來說，舊版復(fù)制功能沒有問題，但是對(duì)于斷線重連后的復(fù)制，舊版雖然也可以讓主從服務(wù)器重新回到一致狀態(tài)，但是效率卻非常低。因?yàn)閿嗑€重連后從服務(wù)器將重新進(jìn)行同步，執(zhí)行SYNC命令，這個(gè)命令是消除消耗資源的。

15.3 新版復(fù)制功能的實(shí)現(xiàn)

為了解決舊版復(fù)制功能在處理斷線重新復(fù)制情況下的低效問題，從Redis 2.8開始，使用PSYNC命令進(jìn)行復(fù)制中的同步操作，PSYC命令有完整重同步和部分重同步兩種模式：

• 完整重同步用于初次復(fù)制的情況：完整重同步和SYNC命令操作基本是一樣的；
• 部分重同步用于斷線后重復(fù)制的情況：當(dāng)從服務(wù)器斷線后重新連接到主服務(wù)器，如果條件允許，主服務(wù)器可以將斷線期間執(zhí)行過的寫命令發(fā)送給從服務(wù)器，就可以將從服務(wù)器的數(shù)據(jù)庫更新成和主服務(wù)器一致；

15.4 部分重同步實(shí)現(xiàn)

部分重同步由三部分組成

• 主服務(wù)器的復(fù)制偏移量和從服務(wù)器的復(fù)制偏移量（replication offset）
• 主服務(wù)器的復(fù)制積壓緩沖區(qū)（replication backlog）
• 服務(wù)器的運(yùn)行ID（run ID）

15.4.1 復(fù)制偏移量

執(zhí)行復(fù)制的雙方會(huì)分別維護(hù)一個(gè)復(fù)制偏移量：

• 主服務(wù)器每次向從服務(wù)器傳播N個(gè)字節(jié)的數(shù)據(jù)時(shí)，就將自己的復(fù)制偏移量加上N；
• 從服務(wù)器每次收到主服務(wù)器傳播來的N字節(jié)數(shù)據(jù)時(shí)，就將自己的復(fù)制偏移量加上N；

通過對(duì)比主從服務(wù)器的復(fù)制偏移量，可以很容易的發(fā)現(xiàn)主從數(shù)據(jù)庫是否一致：

15.4.2 復(fù)制積壓緩沖區(qū)

復(fù)制積壓緩沖區(qū)是主服務(wù)器維護(hù)的一個(gè)固定長度的FIFO隊(duì)列，默認(rèn)大小為1Mb；當(dāng)主服務(wù)器在進(jìn)行命令傳播時(shí)，它不僅會(huì)將寫命令發(fā)送給從服務(wù)器，還會(huì)將寫命令入隊(duì)到復(fù)制積壓緩沖區(qū)里面。

因此，復(fù)制積壓緩沖區(qū)會(huì)保持這一部分最近傳播的寫命令，并且賦值積壓緩沖區(qū)會(huì)為隊(duì)列中的每個(gè)字節(jié)記錄相應(yīng)的復(fù)制偏移量。當(dāng)斷線后從服務(wù)器重新連接上主服務(wù)器，從服務(wù)器會(huì)通過PSYNC命令將自己的復(fù)制偏移量發(fā)送給主服務(wù)器，主服務(wù)器會(huì)根據(jù)這個(gè)偏移量來決定執(zhí)行何種同步：

• 如果offset偏移量之后的數(shù)據(jù)任然存在于復(fù)制積壓緩沖區(qū)里面，那么主服務(wù)器對(duì)從服務(wù)器執(zhí)行部分重同步操作；
• 否則，就會(huì)執(zhí)行完整重同步操作，這和SYNC命令是一樣的；

15.4.3 服務(wù)器運(yùn)行ID

除了復(fù)制偏移量和復(fù)制積壓緩沖區(qū)，還需要服務(wù)器運(yùn)行ID，才能實(shí)現(xiàn)PSYNC部分重同步功能；

每個(gè)Redis服務(wù)器，無論是主服務(wù)器還是從服務(wù)器，都會(huì)有一個(gè)自己的運(yùn)行ID；這個(gè)運(yùn)行ID從服務(wù)器啟動(dòng)時(shí)自動(dòng)生成，由40個(gè)隨機(jī)的十六進(jìn)制字符組成。

當(dāng)從服務(wù)器初次復(fù)制主服務(wù)器時(shí)，主服務(wù)器會(huì)將自己的運(yùn)行ID傳送給從服務(wù)器，而從服務(wù)器會(huì)將這個(gè)ID保存起來。當(dāng)從服務(wù)器斷線并重新連接上主服務(wù)器時(shí)，從服務(wù)器向當(dāng)前連接的主服務(wù)器發(fā)送這個(gè)ID：如果主服務(wù)器發(fā)現(xiàn)這個(gè)ID和自己一樣，那么可以執(zhí)行部分重同步功能，否則說明這是一個(gè)新的從服務(wù)器，需要執(zhí)行完整重同步。

15.5 復(fù)制的實(shí)現(xiàn)

• 設(shè)置主服務(wù)器的地址和端口
• 和主服務(wù)器建立套接字連接
• 向主服務(wù)器發(fā)送PING命令
• 主服務(wù)器進(jìn)行身份驗(yàn)證
• 從服務(wù)器向主服務(wù)器發(fā)送端口信息
• 同步
• 命令傳播
• 心跳檢測（每秒一次）
  • 檢測主從服務(wù)器的網(wǎng)絡(luò)連接狀態(tài)
  • 輔助實(shí)現(xiàn)min-slaves配置，就是最少需要幾個(gè)slave（當(dāng)然還可以配置如果所有的slave的延時(shí)都大于多少時(shí)）拒絕執(zhí)行寫命令；
  • 檢測命令丟失，在網(wǎng)絡(luò)傳輸中命令傳播可能丟失，通過offset主服務(wù)器就會(huì)發(fā)現(xiàn)這種問題，將數(shù)據(jù)重傳；

第十六章 Sentinel

Sentinel（哨兵）是Redis高可用解決方案，由一個(gè)或多個(gè)Sentinel實(shí)例組成的Sentinel系統(tǒng)可以監(jiān)視任意多個(gè)主服務(wù)器，以及這些主服務(wù)器的從服務(wù)器，當(dāng)監(jiān)視的主服務(wù)器下線時(shí)，自動(dòng)將下線主服務(wù)器屬下的某個(gè)從服務(wù)器升級(jí)為新的主服務(wù)器。

當(dāng)主服務(wù)器的下線時(shí)長超過用戶設(shè)定的閾值時(shí)，Sentinel系統(tǒng)就會(huì)對(duì)主服務(wù)器進(jìn)行故障轉(zhuǎn)移操作：

• 首先，Sentinel會(huì)挑選出一個(gè)故障主服務(wù)器下面的其中一個(gè)從服務(wù)器，并將這個(gè)從服務(wù)器升級(jí)為主服務(wù)器；
• 之后，Sentinel系統(tǒng)會(huì)向故障主服務(wù)器的所有從服務(wù)器發(fā)送新的復(fù)制命令，讓他們成為新的主服務(wù)器的從服務(wù)器，當(dāng)所有的從服務(wù)器都開始復(fù)制新的主服務(wù)器時(shí)，故障轉(zhuǎn)移操作完畢；
• 另外，Sentinel系統(tǒng)還會(huì)繼續(xù)監(jiān)視已下線的服務(wù)器，如果它重新上線，那么會(huì)讓他成為新的主服務(wù)器的從服務(wù)器；

16.1 啟動(dòng)并初始化Sentinel

當(dāng)一個(gè)Sentinel啟動(dòng)時(shí)，他需要執(zhí)行以下步驟：

• 初始化服務(wù)器

Sentinel本質(zhì)上只是一個(gè)運(yùn)行在特殊模式下的Redis服務(wù)器，所以啟動(dòng)Sentinel的第一步，就是初始化一個(gè)普通的Redis服務(wù)器，但是不需要像普通Redis服務(wù)器那樣載入RDB文件之類的操作，因?yàn)樗恍枰褂肦edis數(shù)據(jù)庫功能；

• 將普通Redis服務(wù)器使用的代碼替換成Sentinel專用的代碼

• 初始化Sentinel狀態(tài)

• 根據(jù)給定的配置文件，初始化Sentinel的監(jiān)視主服務(wù)器列表

• 創(chuàng)建連向主服務(wù)器的網(wǎng)絡(luò)連接

16.2 獲取主服務(wù)器信息

Sentinel默認(rèn)會(huì)以十秒一次的頻率通過命令連接向被監(jiān)視的主服務(wù)器發(fā)送INFO命令，通過分析主服務(wù)器返回的INFO命令回復(fù)，Sentinel可以獲取以下兩方面的信息：

• 一方面是關(guān)于主服務(wù)器本身的信息，比如runID；
• 另一方面是關(guān)于該主服務(wù)器下的從服務(wù)器的信息，根據(jù)這些信息，Sentinel就可以自動(dòng)發(fā)現(xiàn)從服務(wù)器；

16.3 獲取從服務(wù)器信息

Sentinel默認(rèn)也會(huì)以十秒一次的頻率通過命令通道向從服務(wù)器發(fā)送INFO命令，獲取從服務(wù)器的信息。

16.4 向主服務(wù)器和從服務(wù)器發(fā)送信息

在默認(rèn)情況下，Sentinel會(huì)以每兩秒一次的頻率，通過命令連接，向所有被監(jiān)視的Redis服務(wù)器發(fā)送一個(gè)命令，向服務(wù)器的sentinel:hello頻道發(fā)送一條信息；

16.5 接收來自被監(jiān)視服務(wù)器的頻道信息

Sentinel不僅會(huì)向所有被監(jiān)視的Redis服務(wù)器發(fā)送頻道信息，還會(huì)接收頻道信息，如果一個(gè)Redis服務(wù)器被多個(gè)Sentinel實(shí)例監(jiān)視，那么一個(gè)Sentinel向某個(gè)被監(jiān)視的Redis服務(wù)器發(fā)送的頻道信息，會(huì)被其他所有監(jiān)視這個(gè)Redis服務(wù)器的Sentinel實(shí)例接收到，這些Sentinel接收到不是自己發(fā)送的頻道信息之后，會(huì)對(duì)其他Sentinel發(fā)送的頻道信息進(jìn)行解析；

16.5.1 更新sentinels字典

Sentinel為主服務(wù)器創(chuàng)建的sentinels字段保存了所有監(jiān)視這個(gè)Redis服務(wù)器的Sentinel的資料：

• sentinels字典的鍵是Sentinel的名字，格式為ip:port
• sentinels字典的值是對(duì)應(yīng)的Sentinel實(shí)例結(jié)構(gòu)

16.5.2 創(chuàng)建連向其他Sentinel的命令連接

當(dāng)Sentinel通過頻道信息發(fā)現(xiàn)一個(gè)新的Sentinel時(shí)，不僅會(huì)在sentinels 字典中未該Sentinel創(chuàng)建相應(yīng)的實(shí)例結(jié)構(gòu)，還會(huì)創(chuàng)建一個(gè)連接到這個(gè)Sentinel的命令連接，最終監(jiān)視同一個(gè)Redis服務(wù)器的所有Sentinel實(shí)例會(huì)成為一個(gè)網(wǎng)狀結(jié)構(gòu)；

16.6 檢測主觀下線狀態(tài)

默認(rèn)情況下，Sentinel會(huì)以每秒一次的頻率向所有它創(chuàng)建了命令連接的實(shí)例（包括主從服務(wù)器，其他Sentinel）發(fā)送PING命令，并通過實(shí)例返回來判斷實(shí)例是否在線；

在Sentinel配置文件中有一個(gè)配置：down-after-milliseconeds，如果一個(gè)實(shí)例在down-after-milliseconeds毫秒后依然沒有返回有效的PING回應(yīng)，那么Sentinel就會(huì)判斷該實(shí)例為下線；

16.7 檢測客觀下線狀態(tài)

當(dāng)Sentinel將一個(gè)主服務(wù)器判斷為主觀下線后，為了確認(rèn)這個(gè)服務(wù)器是否真的下線，它會(huì)詢問所有監(jiān)視這個(gè)服務(wù)器的Sentinel，看看其他Sentinel是否也認(rèn)為這個(gè)服務(wù)器已經(jīng)下線，如果從其他Sentinel那里得到了足夠數(shù)量的下線判斷后（這個(gè)數(shù)量是配置的），Sentinel就會(huì)認(rèn)為服務(wù)器為客觀下線，并會(huì)對(duì)該主服務(wù)器進(jìn)行故障轉(zhuǎn)移操作。不同的Sentinel對(duì)主服務(wù)器的下線判斷可能不一樣，這個(gè)是因?yàn)椴煌腟entinel配置可能是不一樣的。

16.8 選舉領(lǐng)頭Sentinel

當(dāng)一個(gè)主服務(wù)器被判定為客觀下線時(shí)，監(jiān)視這個(gè)下線主服務(wù)器的各個(gè)Sentinel會(huì)進(jìn)行協(xié)商，選舉出一個(gè)領(lǐng)頭Sentinel，負(fù)責(zé)執(zhí)行故障轉(zhuǎn)移操作：

• 所有在線的Sentinel都有資格成為領(lǐng)頭Sentinel；
• 每次選舉之后，不論選舉是否成功，所有Sentinel的紀(jì)元都會(huì)增加1（一個(gè)計(jì)數(shù)器）
• 每個(gè)發(fā)現(xiàn)主服務(wù)器進(jìn)入客觀下線的Sentinel都會(huì)要求別人選舉自己成為領(lǐng)頭
• 最想向目標(biāo)Sentinel發(fā)送選舉自己要求的Sentinel將獲得選舉，其他后來的選舉要求將被目標(biāo)Sentinel拒絕；
• 如果某個(gè)Sentinel被半數(shù)以上的Sentinel設(shè)置為leader，那么這個(gè)Sentinel將成為leader；
• 如果在給定的時(shí)間內(nèi)沒有選舉出一個(gè)領(lǐng)頭Sentinel，那么就會(huì)過一段時(shí)間再繼續(xù)選舉，直到產(chǎn)生leader；

16.9 故障轉(zhuǎn)移

在選舉產(chǎn)生領(lǐng)頭Sentinel之后，領(lǐng)頭Sentinel就會(huì)對(duì)已下線的主服務(wù)器執(zhí)行故障轉(zhuǎn)移操作：

• 在已下線的主服務(wù)器的所有從服務(wù)器里，挑選出一個(gè)從服務(wù)器，并將其轉(zhuǎn)換為新的主服務(wù)器；
• 讓已下線的主服務(wù)器的所有從服務(wù)器改為復(fù)制新的主服務(wù)器；
• 將已下線服務(wù)器作為新的主服務(wù)器的從服務(wù)器，當(dāng)這個(gè)舊的主服務(wù)器開始重新上線時(shí)，他就會(huì)成為新的主服務(wù)器的從服務(wù)器；

16.9.1 選出新的主服務(wù)器

故障轉(zhuǎn)移的第一步就是需要在故障的主服務(wù)器的所有從服務(wù)器中挑選一個(gè)狀態(tài)良好、數(shù)據(jù)完整的從服務(wù)器，然后向這個(gè)從服務(wù)器發(fā)送SLAVEOF no one命令，將這個(gè)從服務(wù)器轉(zhuǎn)換成主服務(wù)器；

領(lǐng)頭Sentinel會(huì)將已下線的Sentinel服務(wù)器的所有從服務(wù)器保存在一個(gè)列表里面，然后按照下面的規(guī)則過濾：

• 刪除列表中出于下線或者斷線狀態(tài)的服務(wù)器，保證剩余的從服務(wù)器都是正常在線的；
• 刪除列表中所有最近五秒內(nèi)沒有回復(fù)過領(lǐng)頭Sentinel的INFO命令的從服務(wù)器，保證剩余的從服務(wù)器都是最近成功進(jìn)行過通信的；
• 刪除所有與已下線服務(wù)器連接斷開超過 down-after-milliseconds * 10 毫秒的從服務(wù)器，保證剩余的從服務(wù)器沒有過早的與主服務(wù)器斷開連接，也就是保證剩余的從服務(wù)器保存的數(shù)據(jù)都是比較新的；

之后，領(lǐng)頭Sentinel對(duì)列表中剩余的從服務(wù)器進(jìn)行優(yōu)先級(jí)處理，取得優(yōu)先級(jí)最高的一個(gè)從服務(wù)器，稱為最終被挑選出來的從服務(wù)器。

排序的規(guī)則是：

首先看服務(wù)器優(yōu)先級(jí)，然后是復(fù)制偏移量，最后是服務(wù)器運(yùn)行ID；

16.9.2 修改從服務(wù)器的復(fù)制目標(biāo)

16.9.3 將舊的主服務(wù)器變?yōu)閺姆?wù)器

最后，需要注意的是，Sentinel只會(huì)和主服務(wù)器和從服務(wù)器創(chuàng)建命令連接和訂閱連接，Sentinel之間則只創(chuàng)建命令連接。

第十七章 集群

Redis集群是Redis提供的分布式解決方案，復(fù)制（replication）提供了主從數(shù)據(jù)庫方案，Sentinel提供了高可用（故障轉(zhuǎn)移）方案，而Redis集群則在此基礎(chǔ)上提供了負(fù)載均衡（通過分片）的分布式方案。

集群主要包括下面一些內(nèi)容：節(jié)點(diǎn)、槽指派、命令執(zhí)行、重新分片、轉(zhuǎn)向、故障轉(zhuǎn)移、消息等；

17.1 節(jié)點(diǎn)

一個(gè)Redis集群由多個(gè)節(jié)點(diǎn)組成（node），在剛開始的時(shí)候，每個(gè)節(jié)點(diǎn)都是相互獨(dú)立的，他們都處于一個(gè)只包含自己的集群當(dāng)中，我們可以通過CLUSTER MEET <ip> <port> 命令來完成這個(gè)工作，當(dāng)向一個(gè)節(jié)點(diǎn)執(zhí)行這個(gè)命令時(shí)，可以讓當(dāng)前節(jié)點(diǎn)將ip和port所代表的節(jié)點(diǎn)添加到當(dāng)前集群中；

一個(gè)節(jié)點(diǎn)就是一個(gè)運(yùn)行在集群模式的Redis服務(wù)器，Redis服務(wù)器會(huì)在啟動(dòng)的時(shí)候根據(jù)cluster-enbale配置是否為yes來確定是否開啟集群模式；集群模式的Redis服務(wù)器依然會(huì)繼續(xù)使用單機(jī)模式下的Redis服務(wù)器組件，比如復(fù)制等功能；

clusterNode結(jié)構(gòu)是一個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：

typedef struct clusterNode {
    mstime_t ctime; /* Node object creation time. */
    char name[CLUSTER_NAMELEN]; /* Node name, hex string, sha1-size */
    int flags;      /* CLUSTER_NODE_... */
    uint64_t configEpoch; /* Last configEpoch observed for this node */
    unsigned char slots[CLUSTER_SLOTS/8]; /* slots handled by this node */
    int numslots;   /* Number of slots handled by this node */
    int numslaves;  /* Number of slave nodes, if this is a master */
    struct clusterNode **slaves; /* pointers to slave nodes */
    struct clusterNode *slaveof; /* pointer to the master node. Note that it
                                    may be NULL even if the node is a slave
                                    if we don't have the master node in our
                                    tables. */
    mstime_t ping_sent;      /* Unix time we sent latest ping */
    mstime_t pong_received;  /* Unix time we received the pong */
    mstime_t fail_time;      /* Unix time when FAIL flag was set */
    mstime_t voted_time;     /* Last time we voted for a slave of this master */
    mstime_t repl_offset_time;  /* Unix time we received offset for this node */
    mstime_t orphaned_time;     /* Starting time of orphaned master condition */
    long long repl_offset;      /* Last known repl offset for this node. */
    char ip[NET_IP_STR_LEN];  /* Latest known IP address of this node */
    int port;                   /* Latest known clients port of this node */
    int cport;                  /* Latest known cluster port of this node. */
    clusterLink *link;          /* TCP/IP link with this node */
    list *fail_reports;         /* List of nodes signaling this as failing */
} clusterNode;

每個(gè)節(jié)點(diǎn)都保存這一個(gè)clusterState：

typedef struct clusterState {
    clusterNode *myself;  /* This node */
    uint64_t currentEpoch;
    int state;            /* CLUSTER_OK, CLUSTER_FAIL, ... */
    int size;             /* Num of master nodes with at least one slot */
    dict *nodes;          /* Hash table of name -> clusterNode structures */
    dict *nodes_black_list; /* Nodes we don't re-add for a few seconds. */
    clusterNode *migrating_slots_to[CLUSTER_SLOTS];
    clusterNode *importing_slots_from[CLUSTER_SLOTS];
    clusterNode *slots[CLUSTER_SLOTS];
    uint64_t slots_keys_count[CLUSTER_SLOTS];
    rax *slots_to_keys;
    /* The following fields are used to take the slave state on elections. */
    mstime_t failover_auth_time; /* Time of previous or next election. */
    int failover_auth_count;    /* Number of votes received so far. */
    int failover_auth_sent;     /* True if we already asked for votes. */
    int failover_auth_rank;     /* This slave rank for current auth request. */
    uint64_t failover_auth_epoch; /* Epoch of the current election. */
    int cant_failover_reason;   /* Why a slave is currently not able to
                                   failover. See the CANT_FAILOVER_* macros. */
    /* Manual failover state in common. */
    mstime_t mf_end;            /* Manual failover time limit (ms unixtime).
                                   It is zero if there is no MF in progress. */
    /* Manual failover state of master. */
    clusterNode *mf_slave;      /* Slave performing the manual failover. */
    /* Manual failover state of slave. */
    long long mf_master_offset; /* Master offset the slave needs to start MF
                                   or zero if stil not received. */
    int mf_can_start;           /* If non-zero signal that the manual failover
                                   can start requesting masters vote. */
    /* The followign fields are used by masters to take state on elections. */
    uint64_t lastVoteEpoch;     /* Epoch of the last vote granted. */
    int todo_before_sleep; /* Things to do in clusterBeforeSleep(). */
    /* Messages received and sent by type. */
    long long stats_bus_messages_sent[CLUSTERMSG_TYPE_COUNT];
    long long stats_bus_messages_received[CLUSTERMSG_TYPE_COUNT];
    long long stats_pfail_nodes;    /* Number of nodes in PFAIL status,
                                       excluding nodes without address. */
} clusterState;

這個(gè)結(jié)構(gòu)記錄著當(dāng)前節(jié)點(diǎn)的視角下集群目前所處的狀態(tài)。

17.1.1 CLUSTER MEET命令的實(shí)現(xiàn)

通過向節(jié)點(diǎn)A發(fā)送CLUSTER MEET命令，可以讓節(jié)點(diǎn)A將另外一個(gè)節(jié)點(diǎn)B添加到節(jié)點(diǎn)A當(dāng)前所在的集群里面，收到命令的節(jié)點(diǎn)A將于節(jié)點(diǎn)B進(jìn)行握手，以此來確認(rèn)彼此的存在：

• （1） 節(jié)點(diǎn)A會(huì)為節(jié)點(diǎn)B創(chuàng)建一個(gè)clusterNode結(jié)構(gòu)，并將該結(jié)構(gòu)添加到自己的clusterState.nodes字典里面；
• （2）之后，節(jié)點(diǎn)A將給節(jié)點(diǎn)B發(fā)送一條MEET消息；
• （3）節(jié)點(diǎn)B接收到節(jié)點(diǎn)A發(fā)送的MEET消息，B會(huì)為A創(chuàng)建一個(gè)clusterNode結(jié)構(gòu)，并將該結(jié)構(gòu)添加到自己的clusterState.nodes字典里面；
• （4）之后，節(jié)點(diǎn)B將給節(jié)點(diǎn)A返回一條PONG消息；
• （5）節(jié)點(diǎn)A收到B的PONG消息，A就知道B已經(jīng)成功的接收到自己的消息了；
• （6）之后，節(jié)點(diǎn)A將給B發(fā)送一條PING消息；
• （7）節(jié)點(diǎn)B收到A的PING消息，B就知道A已經(jīng)接收到自返回的PONG消息，握手結(jié)束；
• （8）之后，節(jié)點(diǎn)A會(huì)將B的信息通過Gossip協(xié)議傳播給集群中的其他節(jié)點(diǎn)，讓其他節(jié)點(diǎn)也與B握手，最終，經(jīng)過一段時(shí)間，節(jié)點(diǎn)B會(huì)被集群中的所有節(jié)點(diǎn)認(rèn)識(shí)；

17.2 槽指派

Redis集群通過分片的方式來保存數(shù)據(jù)庫中的鍵值對(duì)，集群的整個(gè)數(shù)據(jù)庫被分為16384（2^14）個(gè)槽（slot），數(shù)據(jù)庫中的每個(gè)鍵都屬于這16384個(gè)槽中的一個(gè)，集群中的每個(gè)節(jié)點(diǎn)可以處理0個(gè)或最多16384個(gè)槽；
當(dāng)數(shù)據(jù)庫中的16384個(gè)槽都被處理時(shí)，集群狀態(tài)出于上線狀態(tài)（ok），如果數(shù)據(jù)庫中任意一個(gè)槽沒有被處理，那么集群出于下線狀態(tài)（fail）；

可以通過命令 CLUSTER ADDSLOTS命令將一個(gè)或者多個(gè)槽指派給某個(gè)節(jié)點(diǎn)負(fù)責(zé)；

節(jié)點(diǎn)的clusterNode結(jié)構(gòu)的slots 屬性和 numslots 記錄了節(jié)點(diǎn)負(fù)責(zé)處理那些槽，slots屬性是一個(gè)二進(jìn)制位數(shù)組，這個(gè)數(shù)組的長度是16384 / 8 = 2048個(gè)字節(jié)，一共包含16384個(gè)二進(jìn)制位。

Redis以0為起始索引，16383為終止索引，對(duì)slots數(shù)組中的16384個(gè)二進(jìn)制位進(jìn)行編號(hào)，并根據(jù)第i位上的二進(jìn)制值來判斷槽是否是該節(jié)點(diǎn)負(fù)責(zé)；

一個(gè)節(jié)點(diǎn)會(huì)將自己負(fù)責(zé)的槽信息發(fā)送給其他集群中的節(jié)點(diǎn)，以此來告訴其他節(jié)點(diǎn)自己負(fù)責(zé)哪些槽；節(jié)點(diǎn)A通過消息接收到節(jié)點(diǎn)B負(fù)責(zé)的槽信息，會(huì)在A節(jié)點(diǎn)自己的clusterState.nodes字典里面找到B對(duì)應(yīng)的clusterNode結(jié)構(gòu)，并對(duì)其中的slots屬性進(jìn)行更新，因?yàn)榧褐械拿總€(gè)節(jié)點(diǎn)都會(huì)將自己的slots數(shù)組發(fā)送給其他節(jié)點(diǎn)，所以集群中的所有節(jié)點(diǎn)都知道16384個(gè)槽都是由哪些節(jié)點(diǎn)負(fù)責(zé)的；

這里需要注意的一點(diǎn)是，如果只將16384個(gè)槽記錄在clusterNode的slots數(shù)組里，那么如果需要知道第i個(gè)槽是哪個(gè)節(jié)點(diǎn)負(fù)責(zé)的，就需要遍歷clusterState.nodes字典中的所有clusterNode.slots數(shù)組，這個(gè)負(fù)責(zé)度為O(N)，所以，clusterState.slots數(shù)組會(huì)保存每一個(gè)槽是由哪個(gè)節(jié)點(diǎn)負(fù)責(zé)的。這樣的話，如果想要檢測槽i是否已經(jīng)被指派，只需要檢測clusterState.slots數(shù)組的第i個(gè)項(xiàng)即可；
當(dāng)然，是否只需要在clusterState.slots數(shù)組就可以了呢？clusterNode.slots是否還需要呢？答案是需要的，因?yàn)楣?jié)點(diǎn)需要將自己負(fù)責(zé)的slots傳播給其他節(jié)點(diǎn)，現(xiàn)在只需要將clusterNode.slots發(fā)送出去即可，但是如果沒有clusterNode.slots，就需要在clusterStste.slots里面遍歷，找出所有某個(gè)節(jié)點(diǎn)負(fù)責(zé)的slot，然后再發(fā)送給其他節(jié)點(diǎn)，這就有點(diǎn)麻煩了；

17.3 在集群中執(zhí)行命令

在對(duì)集群中的16384個(gè)槽都指派完成之后，集群就進(jìn)入上線狀態(tài)，這時(shí)客戶端就可以向集群發(fā)送數(shù)據(jù)命令了；

當(dāng)客戶端向節(jié)點(diǎn)發(fā)送數(shù)據(jù)庫相關(guān)命令時(shí)，接收到命令的節(jié)點(diǎn)會(huì)計(jì)算出命令要處理的數(shù)據(jù)庫鍵屬于哪個(gè)槽：

• 如果這個(gè)槽是自己負(fù)責(zé)的，那么節(jié)點(diǎn)直接執(zhí)行這個(gè)命令；
• 如果鍵所在的槽不是當(dāng)前節(jié)點(diǎn)負(fù)責(zé)的，那么節(jié)點(diǎn)會(huì)向客戶端返回一個(gè)MOVED錯(cuò)誤，指引客戶端轉(zhuǎn)向正確的節(jié)點(diǎn)執(zhí)行命令；

節(jié)點(diǎn)首先需要計(jì)算出鍵所對(duì)應(yīng)的槽，Redis使用CRC16（key） & 16383來計(jì)算這個(gè)值，當(dāng)節(jié)點(diǎn)計(jì)算出鍵所對(duì)應(yīng)的槽之后，節(jié)點(diǎn)就會(huì)檢查自己在數(shù)組clusterState.slots的第i項(xiàng)是否是自己，如果是，則說明這個(gè)鍵是由自己負(fù)責(zé)的，否則，會(huì)指引客戶端轉(zhuǎn)向clusterState.slots[i]所指向的節(jié)點(diǎn)執(zhí)行命令；

需要注意的是，節(jié)點(diǎn)只能使用0號(hào)數(shù)據(jù)庫，而單機(jī)則沒有這個(gè)限制；

17.4 重新分片

Redis集群的重新分片操作可以將任意已經(jīng)分配給某個(gè)節(jié)點(diǎn)的槽改為指派給其他的另外一個(gè)節(jié)點(diǎn)，重新分片操作可以在線進(jìn)行，不需要下線，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)都可以繼續(xù)處理命令請(qǐng)求；

Redis集群的重新分片操作由Redis的集群管理軟件redis-trib執(zhí)行，redis-trib對(duì)集群的單個(gè)槽slot進(jìn)行重新分片的步驟如下：

• （1）redis-trib向目標(biāo)節(jié)點(diǎn)發(fā)送CLUSTER SETSLOT <slot> IMPORTING <source_id>命令，讓目標(biāo)節(jié)點(diǎn)準(zhǔn)備好從源節(jié)點(diǎn)導(dǎo)入屬于槽slot的鍵值對(duì)；
• （2）redis-trib對(duì)源節(jié)點(diǎn)發(fā)送CLUSTER SETSLOT <slot> MIGRATING <target_id>命令，讓源節(jié)點(diǎn)準(zhǔn)備好將屬于槽slot的鍵值對(duì)遷移到目標(biāo)節(jié)點(diǎn)；
• （3）redis-trib向源節(jié)點(diǎn)發(fā)送CLUSTER GETKEYSINSLOT <slot> <count>命令，獲取最多count個(gè)屬于槽slot的鍵值對(duì)的鍵名字；
• （4）對(duì)于步驟3得到的每個(gè)鍵，redis-trib都將向源節(jié)點(diǎn)發(fā)送命令，原子的將這些鍵遷移到目標(biāo)節(jié)點(diǎn)；
• （5）重復(fù)步驟3和4，直到源節(jié)點(diǎn)保存的所有屬于槽slot的鍵值對(duì)都被遷移到目標(biāo)節(jié)點(diǎn)為止；
• （6）redis-trib會(huì)向集群中的任意一個(gè)節(jié)點(diǎn)發(fā)送CLUSTER SETSLOT <slot> NODE <taregt_id>命令，將槽slot指派給目標(biāo)節(jié)點(diǎn)，這一信息會(huì)通過消息發(fā)送給集群中的所有節(jié)點(diǎn)，最終集群中的所有節(jié)點(diǎn)都將知道槽slot已經(jīng)指派給了目標(biāo)節(jié)點(diǎn)；

17.5 ASK錯(cuò)誤

在進(jìn)行重新分片的過程中，因?yàn)榧赫Ｔ诰€，所以可能出現(xiàn)一種情況，屬于被遷移槽的一部分鍵在源節(jié)點(diǎn)中，而另一部分已經(jīng)遷移到目標(biāo)節(jié)點(diǎn)，這時(shí)候如果客戶端向源節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)庫操作命令，而這個(gè)被操作的鍵剛好在被遷移的鍵中時(shí)：

• 源節(jié)點(diǎn)會(huì)現(xiàn)在自己的數(shù)據(jù)庫中查找給定的鍵，如果找到了，那么就直接處理；
• 如果沒找到，那么源節(jié)點(diǎn)會(huì)向客戶端返回一個(gè)ASK錯(cuò)誤，指引客戶端向目標(biāo)節(jié)點(diǎn)發(fā)起請(qǐng)求；

ASK錯(cuò)誤和MOVED錯(cuò)誤的區(qū)別：

• MOVED錯(cuò)誤表示槽的負(fù)責(zé)權(quán)已經(jīng)從一個(gè)節(jié)點(diǎn)轉(zhuǎn)向另外一個(gè)節(jié)點(diǎn)了，所以在客戶端收到MOVED錯(cuò)誤之后，客戶端每次都可以使用轉(zhuǎn)向后的節(jié)點(diǎn)；
• ASK錯(cuò)誤是一種臨時(shí)方案，是一次性的，ASK錯(cuò)誤之后應(yīng)該會(huì)出現(xiàn)一次MOVED錯(cuò)誤；

17.6 復(fù)制與故障轉(zhuǎn)移

Redis集群的節(jié)點(diǎn)分為主節(jié)點(diǎn)（master）和從節(jié)點(diǎn)（slave），主節(jié)點(diǎn)負(fù)責(zé)處理槽，而從節(jié)點(diǎn)負(fù)責(zé)復(fù)制某個(gè)主節(jié)點(diǎn)，并在主節(jié)點(diǎn)下線時(shí)代替主節(jié)點(diǎn)；

向一個(gè)節(jié)點(diǎn)發(fā)送CLUSTER REPLICATION <node_id>，可以讓收到命令的節(jié)點(diǎn)對(duì)主節(jié)點(diǎn)進(jìn)行復(fù)制：

• 接收到命令的節(jié)點(diǎn)首先會(huì)在自己的clusterState.modes字典中找到主節(jié)點(diǎn)的clusterNode結(jié)構(gòu)，然后將自己的clusterState.myself.slaveof指針指向這個(gè)clusterNode，以此來表示當(dāng)前節(jié)點(diǎn)正在復(fù)制這個(gè)主節(jié)點(diǎn)；
• 然后會(huì)修改自己的clusterState.myself.flags中的屬性，關(guān)閉原本的master屬性，打開slave屬性，表示節(jié)點(diǎn)變成一個(gè)從節(jié)點(diǎn)；
• 然后，會(huì)復(fù)用復(fù)制的代碼對(duì)master節(jié)點(diǎn)進(jìn)行復(fù)制；

一個(gè)節(jié)點(diǎn)成為從節(jié)點(diǎn)，并開始復(fù)制某個(gè)主節(jié)點(diǎn)這個(gè)消息會(huì)被集群的其他節(jié)點(diǎn)知道，集群中的所有節(jié)點(diǎn)都會(huì)在代表主節(jié)點(diǎn)的clusterNode.slaves屬性中記錄正在復(fù)制該節(jié)點(diǎn)的從節(jié)點(diǎn)信息；

集群中的每個(gè)節(jié)點(diǎn)都會(huì)定期向其他節(jié)點(diǎn)發(fā)送PING消息，以此來檢測對(duì)方是都還在線，如果接收PING消息的節(jié)點(diǎn)沒有在規(guī)定時(shí)間內(nèi)返回PONG消息，那么發(fā)送PING消息的節(jié)點(diǎn)就會(huì)將接受PING消息的節(jié)點(diǎn)標(biāo)記為疑似下線（probable fail ，PFAIL）；
集群中的每個(gè)節(jié)點(diǎn)都會(huì)通過互相發(fā)送消息來交互集群各個(gè)節(jié)點(diǎn)的狀態(tài)信息，如果一個(gè)集群里面超過半數(shù)以上負(fù)責(zé)處理槽的主節(jié)點(diǎn)將某個(gè)節(jié)點(diǎn)標(biāo)記為疑似下線狀態(tài)，那么這個(gè)主節(jié)點(diǎn)將被標(biāo)記為下線，將這個(gè)主節(jié)點(diǎn)標(biāo)記為下線的節(jié)點(diǎn)將會(huì)向集群廣播這個(gè)消息，所有收到這條消息的節(jié)點(diǎn)都會(huì)立即標(biāo)記這個(gè)節(jié)點(diǎn)已下線。

當(dāng)一個(gè)從節(jié)點(diǎn)發(fā)現(xiàn)自己復(fù)制的主節(jié)點(diǎn)已下線時(shí)，從節(jié)點(diǎn)開始對(duì)下線主節(jié)點(diǎn)進(jìn)行故障轉(zhuǎn)移操作：

• （1）在所有復(fù)制主節(jié)點(diǎn)的從節(jié)點(diǎn)里面會(huì)有一個(gè)從節(jié)點(diǎn)被選中；
• （2）選中的從節(jié)點(diǎn)執(zhí)行SLAVE no one命令，成為新的主節(jié)點(diǎn)；
• （3）新的主節(jié)點(diǎn)會(huì)認(rèn)領(lǐng)所有下線主節(jié)點(diǎn)的槽指派；
• （4）新的主節(jié)點(diǎn)向集群廣播一條PONG消息，集群中的其他節(jié)點(diǎn)會(huì)基于這條消息知道這個(gè)節(jié)點(diǎn)成為了新的主節(jié)點(diǎn)，并接管了原來主節(jié)點(diǎn)下的所有從節(jié)點(diǎn)；
• （5）新的主節(jié)點(diǎn)開始處理自己負(fù)責(zé)的槽的相關(guān)命令，故障轉(zhuǎn)移完成；

選舉新的主節(jié)點(diǎn)的步驟為：

• （1）在每次選舉中，負(fù)責(zé)處理槽的主節(jié)點(diǎn)有一次投票機(jī)會(huì)；
• （2）當(dāng)從節(jié)點(diǎn)發(fā)現(xiàn)自己正在復(fù)制的主節(jié)點(diǎn)已下線時(shí)，它會(huì)向集群廣播一條消息，要求所有具備選舉權(quán)的節(jié)點(diǎn)給自己投票；
• （3）接收到這條消息的節(jié)點(diǎn)，如果是負(fù)責(zé)處理槽的主節(jié)點(diǎn)，并且自己還沒有投票，那么就會(huì)給這個(gè)節(jié)點(diǎn)投票；
• （4）如果一個(gè)從節(jié)點(diǎn)收集到大于集群主節(jié)點(diǎn)數(shù)量一半的票數(shù)，那么這個(gè)從節(jié)點(diǎn)就選舉為新的主節(jié)點(diǎn)；
• （5）如果一個(gè)紀(jì)元里面沒有從節(jié)點(diǎn)獲得的票數(shù)符合要求，那么就會(huì)進(jìn)入下一個(gè)紀(jì)元；

17.7 消息

消息類型：MEET PING PONG FAIL PUBLISH

gossip
redis cluster something

第十九章 事務(wù)

Redis通過MULTI、EXEC、WATCH等命令實(shí)現(xiàn)事務(wù)功能，事務(wù)提供了一種將多個(gè)命令請(qǐng)求打包，然后一次性的，按順序的執(zhí)行多個(gè)命令的機(jī)制，并且在事務(wù)執(zhí)行期間，服務(wù)器不會(huì)中斷事務(wù)而去執(zhí)行其他客戶端的請(qǐng)求，它會(huì)將事務(wù)中的命令都執(zhí)行完成，然后才去執(zhí)行其他客戶端的命令；

19.1 事務(wù)

一個(gè)事務(wù)從開始到結(jié)束通常會(huì)經(jīng)歷以下三個(gè)階段：

• 事務(wù)開始

MULTI命令可以讓執(zhí)行該命令的客戶端從非事務(wù)狀態(tài)切換到事務(wù)狀態(tài)，這一切換是通過在客戶端狀態(tài)的flags屬性打開REDIS_MULTI標(biāo)志來完成；

• 命令入隊(duì)

如果一個(gè)客戶端處于非事務(wù)狀態(tài)時(shí)，那么這個(gè)客戶端發(fā)送的命令就會(huì)立即被執(zhí)行，否則就會(huì)有不同的執(zhí)行路徑：

• 如果客戶端發(fā)送的命令是EXEC DISCARD WATCH MULTI四個(gè)命令中的一個(gè)，那么服務(wù)器立即執(zhí)行這個(gè)命令；
• 否則，就會(huì)將客戶端的命令放到一個(gè)事務(wù)隊(duì)列里面，然后給客戶端返回QUEUED回復(fù)；

• 事務(wù)執(zhí)行

當(dāng)一個(gè)處于事務(wù)狀態(tài)的客戶端向服務(wù)器發(fā)送EXEC命令時(shí)，這個(gè)命令將被立即執(zhí)行，服務(wù)器會(huì)遍歷這個(gè)客戶端的事務(wù)隊(duì)列，執(zhí)行隊(duì)列里面保存的所有命令，最后將執(zhí)行命令的結(jié)果全部返回給客戶端。

19.2 WATCH命令的實(shí)現(xiàn)

WATCH是一個(gè)樂觀鎖，它可以在EXEC執(zhí)行前，監(jiān)視任意數(shù)量的數(shù)據(jù)庫鍵，并在EXEC執(zhí)行時(shí)，檢查被監(jiān)視的鍵是否至少有一個(gè)已經(jīng)被修改過了，如果是的話，服務(wù)器將拒絕執(zhí)行事務(wù)，并向客戶端返回事務(wù)執(zhí)行失敗的空回復(fù)。

19.3 Redis事務(wù)的ACID性質(zhì)

19.3.1 A（原子性）

原子性指的是數(shù)據(jù)庫事務(wù)將多個(gè)操作當(dāng)做一個(gè)整體執(zhí)行，要么都執(zhí)行，要么一個(gè)也不執(zhí)行，對(duì)于Redis來說，要么全部執(zhí)行Redis事務(wù)隊(duì)列中的所有命令，要么一個(gè)也不執(zhí)行，所以具備原子性；

需要注意的是，Redis的事務(wù)與傳統(tǒng)關(guān)系型數(shù)據(jù)庫事務(wù)的最大區(qū)別就是Redis不支持事務(wù)回滾，即使事務(wù)隊(duì)列中的某個(gè)命令在執(zhí)行時(shí)出錯(cuò)，事務(wù)也不會(huì)停止，會(huì)繼續(xù)執(zhí)行下去，直到將事務(wù)中的命令全部執(zhí)行完成；

19.3.1 C（一致性）

一致性是指，如果數(shù)據(jù)庫在執(zhí)行事務(wù)之前是一致的，那么事務(wù)執(zhí)行之后也應(yīng)該是一致的，無論事務(wù)是否執(zhí)行成功。一致是指數(shù)據(jù)符合數(shù)據(jù)庫本身的定義，沒有包含非法或者無效的錯(cuò)誤數(shù)據(jù)：

• 入隊(duì)錯(cuò)誤：如果命令在入隊(duì)的時(shí)候出現(xiàn)了比如命令不存在等錯(cuò)誤，那么Redis將拒絕執(zhí)行這個(gè)事務(wù)；
• 執(zhí)行錯(cuò)誤，執(zhí)行錯(cuò)誤一般是對(duì)數(shù)據(jù)庫鍵執(zhí)行了錯(cuò)誤的類型操作導(dǎo)致，這種錯(cuò)誤會(huì)被Redis識(shí)別并進(jìn)行錯(cuò)誤處理，這些命令不會(huì)對(duì)數(shù)據(jù)庫進(jìn)行任何修改，所以不會(huì)造成影響
• 服務(wù)器停機(jī)：服務(wù)器停機(jī)之后，如果開啟了Redis持久化，那么服務(wù)器重啟之后會(huì)將數(shù)據(jù)庫狀態(tài)還原到一個(gè)一致的狀態(tài)，如果沒有開啟持久化，那么Redis重啟之后數(shù)據(jù)庫是空白的，是一致的狀態(tài)；

19.3.1 I （隔離性）

事務(wù)的隔離性是指，即使數(shù)據(jù)庫中多個(gè)事務(wù)并發(fā)的執(zhí)行，各個(gè)事務(wù)之間也不會(huì)互相影響，并且在并發(fā)狀態(tài)下執(zhí)行的事務(wù)和串行執(zhí)行的事務(wù)產(chǎn)生的結(jié)果一致；

對(duì)于Redis來說，它使用單線程的方式執(zhí)行事務(wù)（以及事務(wù)隊(duì)列中的命令），并且服務(wù)器保證，在執(zhí)行事務(wù)期間，不會(huì)對(duì)事務(wù)進(jìn)行中斷，因此，Redis事務(wù)總是以串行的方式執(zhí)行的；

19.3.1 D（耐久性）

事務(wù)的耐久性是指，當(dāng)一個(gè)事物執(zhí)行完畢時(shí)，執(zhí)行這個(gè)事務(wù)所得的結(jié)果已被保存到永久存儲(chǔ)介質(zhì)里面了，即使服務(wù)器停機(jī)，執(zhí)行事務(wù)的結(jié)果也不會(huì)丟失。

https://cloud.tencent.com/developer/article/1189074
https://juejin.im/post/5cc165816fb9a03202221dd5
https://mp.weixin.qq.com/s?__biz=MzU5ODUwNzY1Nw==&mid=2247484155&idx=1&sn=0c73f45f2f641ba0bf4399f57170ac9b&scene=21#wechat_redirect

Redis分布式鎖

• （1） setnx (set if not exist)

public boolean tryLock_with_lua(String key, String UniqueId, int seconds) {
    String lua_scripts = "if redis.call('setnx',KEYS[1],ARGV[1]) == 1 then" +
            "redis.call('expire',KEYS[1],ARGV[2]) return 1 else return 0 end";
    List<String> keys = new ArrayList<>();
    List<String> values = new ArrayList<>();
    keys.add(key);
    values.add(UniqueId);
    values.add(String.valueOf(seconds));
    Object result = jedis.eval(lua_scripts, keys, values);
    //判斷是否成功
    return result.equals(1L);
}

*（2） SET key value[EX seconds][PX milliseconds][NX|XX]

• EX seconds: 設(shè)定過期時(shí)間，單位為秒
• PX milliseconds: 設(shè)定過期時(shí)間，單位為毫秒
• NX: 僅當(dāng)key不存在時(shí)設(shè)置值
• XX: 僅當(dāng)key存在時(shí)設(shè)置值

• （3） RedLock

在Redis的分布式環(huán)境中，我們假設(shè)有N個(gè)Redis master。這些節(jié)點(diǎn)完全互相獨(dú)立，不存在主從復(fù)制或者其他集群協(xié)調(diào)機(jī)制。我們確保將在N個(gè)實(shí)例上使用與在Redis單實(shí)例下相同方法獲取和釋放鎖?，F(xiàn)在我們假設(shè)有5個(gè)Redis節(jié)點(diǎn)，同時(shí)我們需要在5臺(tái)服務(wù)器上面運(yùn)行這些Redis實(shí)例，這樣保證他們不會(huì)同時(shí)都宕掉。

為了取到鎖，客戶端應(yīng)該執(zhí)行以下操作:

• 獲取當(dāng)前Unix時(shí)間，以毫秒為單位。
• 依次嘗試從5個(gè)實(shí)例，使用相同的key和具有唯一性的value（例如UUID）獲取鎖。當(dāng)向Redis請(qǐng)求獲取鎖時(shí)，客戶端應(yīng)該設(shè)置一個(gè)網(wǎng)絡(luò)連接和響應(yīng)超時(shí)時(shí)間，這個(gè)超時(shí)時(shí)間應(yīng)該小于鎖的失效時(shí)間。例如你的鎖自動(dòng)失效時(shí)間為10秒，則超時(shí)時(shí)間應(yīng)該在5-50毫秒之間。這樣可以避免服務(wù)器端Redis已經(jīng)掛掉的情況下，客戶端還在死死地等待響應(yīng)結(jié)果。如果服務(wù)器端沒有在規(guī)定時(shí)間內(nèi)響應(yīng)，客戶端應(yīng)該盡快嘗試去另外一個(gè)Redis實(shí)例請(qǐng)求獲取鎖。
• 客戶端使用當(dāng)前時(shí)間減去開始獲取鎖時(shí)間（步驟1記錄的時(shí)間）就得到獲取鎖使用的時(shí)間。當(dāng)且僅當(dāng)從大多數(shù)（N/2+1，這里是3個(gè)節(jié)點(diǎn)）的Redis節(jié)點(diǎn)都取到鎖，并且使用的時(shí)間小于鎖失效時(shí)間時(shí)，鎖才算獲取成功。
• 如果取到了鎖，key的真正有效時(shí)間等于有效時(shí)間減去獲取鎖所使用的時(shí)間（步驟3計(jì)算的結(jié)果）。
• 如果因?yàn)槟承┰颍@取鎖失?。]有在至少N/2+1個(gè)Redis實(shí)例取到鎖或者取鎖時(shí)間已經(jīng)超過了有效時(shí)間），客戶端應(yīng)該在所有的Redis實(shí)例上進(jìn)行解鎖（即便某些Redis實(shí)例根本就沒有加鎖成功，防止某些節(jié)點(diǎn)獲取到鎖但是客戶端沒有得到響應(yīng)而導(dǎo)致接下來的一段時(shí)間不能被重新獲取鎖）。

無論如何，在解鎖的時(shí)候需要check設(shè)置的value，這應(yīng)該是一個(gè)唯一的值，不是每個(gè)客戶端都可以解鎖，只有設(shè)置這個(gè)可以的客戶端才能解鎖。