什麼是集群

能夠對外提供相同服務的多台伺服器組成的集合。

為什麼要建立集群

1.從可用性角度考慮，如果只有一臺機器提供服務，一旦出現故障，那麼整個服務不可用。

2.從容量角度考慮，當服務訪問量上升，單台機器無法支撐訪問量時，必然要擴容。

如何建立集群

當有新的節點要加入集群時，客戶端可以任選集群中的一個節點，比如A，跟新節點B通過握手建立連接，然後A會將B加入的信息通過Gossip消息通知給集群中的其他節點，其他節點也通過握手跟新節點建立連接。

這裡面有幾個問題需要回答：

如何進行握手？

如何進行集群狀態同步？

如何保存/定址鍵值對？

如何進行擴容？

如何進行故障轉移？

集群數據結構

在介紹具體功能之前，我們先介紹一下集群的數據結構。

typedef struct clusterState {
    // 指向當前節點的指針
    clusterNode *myself;
    // 集群當前的配置紀元，用於實現故障轉移
    unit64_t currentEpoch;
    // 集群當前的狀態：是線上還是下線
    int state;
    // 集群中至少處理著一個槽的節點的數量
    int size;
    // 集群節點名單（包括myself節點），字典的鍵為節點的名字，字典的值為節點對應的clusterNode結構
    dict *nodes;
    // 記錄了集群中所有16384個槽的指派信息
    clusterNode *slots[16384];
    // 使用跳躍表保存槽和鍵之間的關係
    zskiplist *slots_to_keys;
    // 記錄當前節點正在從其他節點倒入的槽
    clusterNode *importing_slots_from[16384];
    // 記錄當前節點正在遷移至其他節點的槽
    clusterNode *migrating_slots_to[16384];

} clusterState;

struct clusterNode {
    // 創建節點的時間
    mstime_t ctime;
    // 節點的名字，由40個字十六進位字元串組成
    char name[REDIS_CLUSTER_NAMELEN];
    // 節點的標識，使用各種不同的標識值記錄節點的角色（比如主節點或者從節點），以及節點目前所處的狀態（比如線上或者下線）
    int flags;
    // 節點當前的配置紀元，用於實現故障轉移
    uint64_t configEpoch;
    // 節點IP地址
    char ip[REDIS_IP_STR_LEN];
    // 節點的埠號
    int port;
    // 保存連接節點所需的有關信息
    clusterLink *link;
    // 二進位位數組，記錄節點負責處理哪些槽
    unsigned char slots[16384/8];
    // 記錄節點負責處理的槽的數量，即是slots數組中值為1的二進位位的數量
    int numslots;
    // 如果這是個從節點，指向要複製的主節點的clusterNode結構
    struct clusterNode *slaveof;
    // 正在複製這個主節點的從節點數量
    int numslaves;
    // 一個數據組，每個數組項指向一個正在複製這個主節點的從節點的clusterNode結構
    struct clusterNode **slaves;
    // 一個鏈表，記錄了所有其他節點對該節點的下線報告， 每個下線報告由一個clusterNodeFailReport結構表示
    list *fail_reports;

};

typedef struct clusterLink {
    // 連接的創建時間
    mstime_t ctime;
    // TCP 套接字描述符
    int fd;
    // 輸出緩衝區，保存著待發送給其他節點的消息（message）
    sds sndbuf;
    // 輸入緩衝區，保存著從其他節點接收到的消息
    sds rcvbuf;
    // 與這個連接相關聯的節點，如果沒有的話就為NULL
    struct clusterNode *node;
} clusterLink;

struct clusterNodeFailReport {
    // 報告目標節點已經下線的節點
    struct clusterNode *node;
    // 最後一次從node節點收到下線報告的時間
    // 程式使用這個時間戳來檢查下線報告是否過期
    // （與當前時間戳相差太久的下線報告會被刪除）
    mstime_t time;
}

每個Redis伺服器上都維護一個集群狀態對象clusterState，記錄了集群狀態、集群版本號、當前節點、集群中所有的節點名單、槽指派信息、槽和鍵的關係、槽遷移信息，這些信息會在相應的場景中用到。

如何進行握手

通過MEET命令實現節點之間握手建聯。

命令格式：

CLUSTER MEET <ip> <port>

首先客戶端向節點A發送MEET命令，將節點B加入到A的集群狀態對象中。然後A再向B發送MEET命令，將節點A加入到B的集群狀態對象中，然後B向A發送一個PONG消息作為響應，A收到B的PONG消息再回覆一個PING消息作為響應，這樣通過3次握手，A跟B建立了連接。然後A通過Gossip消息廣播給集群中的其他節點，其他節點以同樣的方式跟B建立連接。

握手的過程：

假設節點A的IP、埠分別為127.0.0.1:7000，節點B的IP、埠分別為127.0.0.1:7001，節點C的IP、埠分別為127.0.0.1:7002，以下展示的是節點A的集群狀態對象clusterState。

如何進行狀態同步

剛剛講到節點之間通過Gossip消息進行狀態同步，感興趣的可以瞭解一下Gossip協議介紹。

https://blog.csdn.net/qq_43590614/article/details/115131473

https://zhuanlan.zhihu.com/p/162970961

集群如何保存鍵值對

槽指派

集群的整個資料庫被分為16384個槽，每個鍵值對都屬於這16384個槽中的一個，每個節點可以處理0個或最多16384個槽。

當資料庫中16384個槽都有節點在處理時，集群處於上線狀態；相反地，如果有任何一個槽沒有節點處理，那麼集群處於下線狀態。

通過CLUSTER ADDSLOTS <slot> [slot ...]命令將槽指派給節點負責。

舉例：

將槽0-5000指派給節點7000負責：

127.0.0.1:7000> CLUSTER ADDSLOTS 0 1 2 ... 5000

將槽5001-10000指派給節點7001負責：

127.0.0.1:7001> CLUSTER ADDSLOTS 5001 5002 5003 ... 10000

將槽10001-16383指派給節點7002負責：

127.0.0.1:7002> CLUSTER ADDSLOTS 10001 10002 10003 ... 16383

進行槽指派前執行CLUSTER INFO：

127.0.0.1:7000> CLUSTER INFO

cluster_state:fail

進行槽指派後執行CLUSTER INFO：

127.0.0.1:7000> CLUSTER INFO

cluster_state:ok

說明槽指派完成後，集群進入上線狀態。

接下來介紹節點保存槽指派信息的方法，以及節點之間傳播槽指派信息的方法。

所謂槽，其實就是二進位位，節點用二進位數組來保存槽信息。

struct clusterNode {
    // ...
    
    // 二進位位數組，記錄節點負責處理哪些槽
    unsigned char slots[16384/8];
    // 記錄節點負責處理的槽的數量，即是slots數組中值為1的二進位位的數量
    int numslots;
    
    // ...
};

如果slots數組在索引i上的二進位位的值為1，那麼表示節點負責處理槽i。

如果slots數組在索引i上的二進位位的值為0，那麼表示節點不負責處理槽i。

傳播節點的槽指派信息

節點除了會將自己負責處理的槽信息記錄在clusterNode結構的slots屬性和numslots屬性之外，還會將自己的slots數組通過消息發送給集群中的其他節點，來告訴其他節點自己目前負責處理哪些槽。

當節點A通過消息從節點B那裡接收到節點B的slots數組時，節點A會在自己的clusterState.nodes字典中查找節點B對應的clusterNode結構，並對結構中的slots數組進行保存或者更新。

這樣集群中的每個節點都會知道資料庫中的16384個槽分別被指派給了哪些節點。

記錄集群所有槽的指派信息：

typedef struct clusterState {
    // ...
    
    // 記錄了集群中所有16384個槽的指派信息
    clusterNode *slots[16384];
    
    // ...
} clusterState;

slots數組包含16384個項，每個數組項都是一個指向clusterNode結構的指針：

如果slots[i]指針指向NULL，那麼表示槽i尚未指派給任何節點。

如果slots[i]指針指向一個clusterNode結構，那麼表示槽i已經指派給了clusterNode結構所代表的節點。

集群如何定址鍵值對

當客戶端向節點發送資料庫鍵命令，節點會計算出鍵屬於哪個槽，再判斷這個槽是否指派給了自己：

• 如果鍵所在槽指派給了當前節點，那麼節點直接執行這個命令；
• 如果鍵所在槽沒有指派給當前節點，那麼節點會向客戶端返回一個MOVED錯誤，將客戶端重定向到正確的節點，並再次發送之前要執行的命令。

判斷流程如下：

計算鍵屬於哪個槽

def slot_number(key):
    return CRC16(key) & 16383

先計算key的CRC16校驗碼，再對16383取餘，計算出一個介於0-16383之間的整數作為鍵的槽號。

判斷槽是否由當前節點負責處理

判斷clusterState.slots[i]對應的節點是否等於clusterState.myself，如果等於，由當前節點處理；不等於，返回MOVED錯誤，指向clusterState.slots[i]對應的節點。

MOVED錯誤

當節點發現鍵所在的槽不是由自己處理時，會向客戶端返回一個MOVED錯誤，並將客戶端重定向到正確的節點。

MOVED錯誤的格式：

MOVED <slot> <ip>:<port>

其中slot為鍵所在的槽，ip和port為負責處理槽的節點IP和埠號。

例如：

MOVED 10086 127.0.0.1：7002

表示槽10086由IP為127.0.0.1，埠號為7002的節點處理。

集群擴容/縮容如何重新分片

當集群需要擴容或縮容時，機器數變了，為了保證槽分佈均勻，需要對槽重新指派，並且屬於槽的鍵值對也要做相應的遷移。

重新分片操作可以線上進行，在重新分片的過程中，集群不需要下線，並且源節點和目標節點都可以繼續處理命令請求。

重新分片的實現原理

ASK錯誤

在進行重新分片過程中，源節點的某個槽正在進行遷移，屬於被遷移槽的一部分鍵值對保存在源節點裡面，另一部分鍵值對保存在目標節點裡面。這時候如果節點收到一個關於鍵的命令，需要判斷鍵所屬的槽是否發生遷移。

集群執行命令的完整過程（考慮MOVED錯誤和ASK錯誤）：

集群如何進行故障轉移

節點N1、N4、N7是主節點，節點N2、N3、N5、N6、N8、N9為從節點。

集群進行故障檢測到N1進入下線狀態：

集群通過選舉演算法，從N1的從節點中選出新的主節點，比如N2被選為新的主節點：

當節點N1重新上線，成為N2的從節點：

這裡涉及到幾個重要的過程，故障檢測、故障轉移、選舉主節點、設置從節點，下麵詳細說明。

故障檢測

集群中每個節點都會定期向其他節點發送PING消息，來檢測對方是否線上，如果接收PING消息的節點沒有在規定時間內返回PONG消息，那麼發送PING消息的節點就會將接收PING消息的節點標記為疑似下線（probable fail，PFAIL）。

集群中各個節點會通過互相發送消息的方式來交換集群中各個節點的狀態，例如某個節點是處於線上狀態、疑似下線狀態（PFAIL），還是已下線狀態（FAIL）。

當一個節點A收到B的消息，B認為C疑似下線，A會在clusterState.nodes中找到C對應的clusterNode結構，將B的下線報告添加到clusterNode中的fail_reports鏈表裡面。

如果A發現C的fail_reports中有超過半數的節點的下線報告，那麼A會將C標記為已下線（FAIL），並將C已下線的消息廣播給集群中的其他節點，所有收到FAIL消息的節點都會將C標記為已下線。

（1）N4檢測N1心跳失敗，生成N1的心跳失敗記錄。

（2）N7檢測N1心跳失敗，生成N1的心跳失敗記錄。

（3）N4、N7之間互相交換消息，N4收到N7的消息，合併心跳失敗記錄。

（4）N4檢測到超過半數節點的下線報告，標記N1為已下線，並廣播給其他節點。

故障轉移

當一個從節點發現自己正在複製的主節點進入了已下線狀態時，從節點將開始對下線主節點進行故障轉移，以下是故障轉移的執行步驟：

（1）複製下線主節點的所有從節點裡面，會有一個從節點被選中。

（2）被選中的從節點會執行SLAVEOF no one命令，成為新的主節點。

（3）新的主節點會撤銷所有對已下線主節點的槽指派，並將這些槽全部指派給自己。

（4）新的主節點向集群廣播一條PONG消息，這條PONG消息可以讓集群中的其他節點立即知道這個節點已經由從節點變成了主節點，並且這個主節點已經接管了原本由已下線節點負責處理的槽。

（5）新的主節點開始接收和自己負責處理的槽有關的命令請求，故障轉移完成。

選舉新的主節點

以下是集群選舉新的主節點的方法：

（1）集群的配置紀元是一個自增計數器，它的初始值為0。

（2）當集群里的某個節點開始一次故障轉移操作時，集群配置紀元的值會被增一。

（3）對於每個配置紀元，集群里每個負責處理槽的主節點都有一次投票的機會，而第一個向主節點要求投票的從節點將獲得主節點的投票。

（4）當從節點發現自己正在複製的主節點進入已下線狀態時，從節點會向集群廣播一條CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息，要求所有收到這條消息、並且具有投票權的主節點向這個從節點投票。

（5）如果一個主節點具有投票權（它正在負責處理槽），並且這個主節點尚未投票給其他從節點，那麼主節點將向要求投票的從節點返回一條CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，表示這個主節點支持從節點成為新的主節點。

（6）每個參與選舉的從節點都會接收CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息，並根據自己收到了多少條這種消息來統計自己獲得了多少主節點的支持。

（7）如果集群里有N個具有投票權的主節點，那麼當一個從節點收集到大於等於N/2+1張支持票時，這個從節點就會當選為新的主節點。

（8）因為在每一個配置紀元裡面，每個具有投票權的主節點只能投一次票，所以如果有N個主節點進行投票，那麼具有大於等於N/2+1張支持票的從節點只會有一個，這確保了新的主節點只會有一個。

（9）如果在一個配置紀元裡面沒有從節點能收集到足夠多的支持票，那麼集群進入一個新的配置紀元，並再次進行選舉，直到選出新的主節點為止。

這個選舉方法是基於Raft演算法實現的。

設置從節點

向一個節點發送命令：

CLUSTER REPLICATE <node_id>

可以讓接收命令的節點成為node_id所指定節點的從節點，並開始對主節點進行複製。

一個節點成為從節點，並開始複製某個主節點這一信息會通過消息發送給集群中的其他節點，最終集群中的所有節點都會知道某個從節點正在複製某個主節點。

集群中使用的消息

消息類型

消息體

MEET、PING、PONG消息的實現

Redis集群中的各個節點通過Gossip協議來交換各自關於不同節點的狀態信息，其中Gossip協議由MEET、PING、PONG三種信息來實現，這三種消息的正文都由clusterMsgDataGossip結構組成的。

每次發送MEET、PONG、PING消息時，發送者都從自己的已知節點列表中隨機選出兩個節點（可以是主節點也可以是從節點），並將這兩個被選中節點的信息分別保存到兩個clusterMsgDataGossip結構裡面。

clusterMsgDataGossip結構記錄了被選中節點的名字，發送者與被選中節點最後一次發送和接收PING消息和PONG消息的時間戳，被選中節點的IP地址和埠號，以及被選中節點的標識值。

當接收者收到MEET、PING、PONG消息時，接收者會訪問消息正文中的兩個clusterMsgDataGossip結構，並根據自己是否認識clusterMsgDataGossip結構中記錄的被選中節點來選擇進行哪種操作：

如果被選中節點不存在於接收者的已知節點列表，那麼說明接收者是第一次接觸到被選中節點，接收者將根據結構中記錄的IP地址和埠號等信息，與被選中節點進行握手。

如果被選中節點已經存在於接收者的已知節點列表，那麼說明接收者之前已經與被選中的節點進行過接觸，接收者將根據clusterMsgDataGossip結構記錄的信息，對被選中節點所對應的clusterNode結構進行更新。

舉個發送PING消息和返回PONG消息的例子，假設在一個包含A、B、C、D、E、F六個節點的集群里:

節點A向節點D發送PING消息，並且消息裡面包含了節點B和節點C的信息，當節點D收到這條PING消息時，它將更新自己對節點B和節點C的認識。

之後，節點D將向節點A返回一條PONG消息，並且消息裡面包含了節點E和節點F的消息，當節點A收到這條PONG消息時，它將更新自己對節點E和節點F的認識。

整個通信過程如下圖所示

FAIL消息的實現