3.2.1 CLUSTER SETSLOT命令

• MIGRATING
  • CLUSTER SETSLOT <slot> MIGRATING <destination-node-id>
  • 將一個hash slot設置為migrating狀態(tài)
  • 當一個slot處于migrating狀態(tài)時，
    • 如果一個命令的key存在，則執(zhí)行該命令
    • 如果一個命令的key不存在，則產(chǎn)生一個ASK重定向
    • 如果一個命令包含多個key
      • 如果所有key都存在，則執(zhí)行
      • 如果只有部分key存在，則產(chǎn)生一個TRYAGAIN錯誤提示等遷移完成后再試 (在筆者4.0本地測試環(huán)境中，只會產(chǎn)生ASK錯誤，留待繼續(xù)研究)
• IMPORTING
  • CLUSTER SETSLOT <slot> IMPORTING <source-node-id>
  • 將一個hash slot設置為importing狀態(tài)
  • 當一個hash slot處于importing狀態(tài)時，
    • 對所有命令，都會產(chǎn)生一個 MOVED 重定向
    • 如果命令緊跟在ASKING命令之后的命令，則會被按照如下規(guī)則執(zhí)行：
      • 如果在某個key遷移前，在importing方通過asking插入該key，則會造成后續(xù)migrating失敗
      • 新key只能在target(imporing一方)創(chuàng)建
      • 對于已經(jīng)完成遷移的key，命令可以背正確執(zhí)行并保證一致性
• STABLE
  • CLUSTER SETSLOT <slot> STABLE
  • 清除當前hash slot的migrating/importing狀態(tài)。
  • 所有已經(jīng)通過MIGRATE命令轉(zhuǎn)移過的key無法恢復
• NODE
  • 該子命令的語法最為復雜。它將hash slot與特定節(jié)點相關聯(lián)，但是該命令只能在特定條件下才會被執(zhí)行并且根據(jù)slot狀態(tài)會產(chǎn)生不同的結(jié)果：
    • 如果當前hash slot的owner是接受命令的節(jié)點，此時嘗試通過本命令將slot分配給一個不同的節(jié)點，則
      • 如果該slot為空，執(zhí)行成功
      • 如果該slot含有任何key，澤返回錯誤
    • 如果slot處于migrating狀態(tài)的節(jié)點接收到該命令，當該slot被assign給其他key之后，清除migrating狀態(tài)
    • 如果slot處于importing狀態(tài)的節(jié)點接收到該命令，則并且將這個slotassign給自己（通常發(fā)生在針對某個hash slot的resharding結(jié)束時），則該命令產(chǎn)生如下影響：
      • 清除imporing狀態(tài)
      • 如果本節(jié)點的config epoch在及群眾不是最大的，澤產(chǎn)生一個心的值并將這個config epoch分配給自己。這樣相對之前由failover或slot遷移產(chǎn)生的配置，本節(jié)點能確保它贏得這個新hash slot的擁有權(quán)。
• Redis Cluster live resharding過程
  • 在source node上把該hash slot設置為IMPORTING狀態(tài)
    CLUSTER SETSLOT <slot> IMPORTING <source-node-id>
  • 在destination node上把該hash slot設置為IMPORTING狀態(tài)
    CLUSTER SETSLOT <slot> MIGRATING <destination-node-id>
  • 在source node上通過以下命令遷移所有key
    • CLUSTER GETKEYSINSLOT <slot> <count>
    • MIGRATE host port "" destination-db timeout [KEYS key [key ...]]
  • 在source或destination節(jié)點執(zhí)行以下命令assign slot到指定節(jié)點
    • CLUSTER SETSLOT <slot> NODE <destination-node-id>

3.3 ASK重定向

• 在過去的章節(jié)，我們已經(jīng)提及了 ASK 重定向。為何我們不能簡單地使用 MOVED 重定向？因為使用 MOVED 意味著我們認為hash slot已經(jīng)永久的服務于一個不同的節(jié)點，并且下一次查詢應該嘗試那個指定節(jié)點，而 AKS 意味著只是下一次查詢需要發(fā)往指定的節(jié)點。
• 這是有必要的，因為下一次我們可能會對一個屬于hash slot 8但目前仍然在"A"上的key進行操作，因此我們總是希望client先嘗試訪問"A"然后在必要的時候再訪問"B"。因為這只會偶爾(resharding或reconfiguring期間)發(fā)生在16384個hash slot中的一個上，因此對cluster的性能影響是可以接受的。
• 我們需要強制規(guī)定client的行為，以確保client只有在A已經(jīng)嘗試過之后再嘗試B。如果client在查詢前發(fā)送了ASKING命令，節(jié)點B只有在該key所屬的slot處于IMPORTING狀態(tài)時才會接受改命令。
• 一般來說，ASKING命令會為client設置一個單次標簽(one-time flag)，以允許該client可以訪問一個IMPORTING的slot一次。
• 從client視角，ASK重定向的語義如下：
  • 如果收到了 ASK 重定向命令，僅僅將這條查詢重定向到某個節(jié)點的命令發(fā)送到指定的新節(jié)點，之后的命令還是繼續(xù)發(fā)送給老的節(jié)點。
  • 重定向查詢必須以一條ASKING命令開始
  • (目前)不要在本地將hash slot 8對應的服務節(jié)點指向B。
• 一旦hash slot 8的遷移完成，A會發(fā)送一個MOVED消息，而client會永久更新hash slot 8的映射到新的IP:port。逐一，如果一個有bug的client提前修改了本地映射，這也不會成為問題，因為這個client不會在查詢前帶上ASKING命令，這樣B會通過MOVED將client重定向回A節(jié)點。

3.4 客戶端首次連接和對重定向的處理

• 一個Redis Cluster client是可以不將slots配置（slot號到服務節(jié)點的地址的映射）記錄在本地內(nèi)存中的，這樣它只需要隨機找一個節(jié)點訪問，并根據(jù)回復的重定向找到正確的服務節(jié)點，當然這樣的client是非常沒有效率的。

• Redis Cluster client應該通過緩存slots配置而變得盡可能聰明。當然，這個配置并非必須總是最新的。因為跟錯誤的節(jié)點通信后會簡單地獲得一個重定向，并且這會出發(fā)一次客戶端視圖的更新。

• Clients通常需要在下面兩個場景中獲取一次全量的slots/nodes映射信息：

  • 在啟動階段為了生成slots配置的初始化信息
  • 在接收到一個MOVED重定向信息時

• 逐一client在接收到MOVED重定向時，可以只更新單個slot，當然這通常不是很有效率，因為一般來說，每次配置變動通常會設計多個slots(比如發(fā)生了一次slave晉升，則所有該節(jié)點服務的slots都會被重新映射)。而在收到MOVED重定向時重新獲取所有slots的映射處理起來更為簡單。

• 為了獲取slots配置，Redis Cluster除了提供了CLUSTER NODES命令外，還提供了一個新選擇，這個新的命令只提供了client需要的信息，并且不需要client(對接收到的數(shù)據(jù))進行解析。

• 這個新命令就是CLUSTER SLOTS，它提供了一個slots范圍數(shù)組，并關聯(lián)了服務于對應范圍的master和slave節(jié)點。

• 下面是CLUSTER SLOTS輸出的例子：

  127.0.0.1:7000> cluster slots
  1)　1)　(integer) 5461
  　　2)　(integer) 10922
  　　3)　1) "127.0.0.1"

  2) (integer) 7001
  　　4)　1) "127.0.0.1"
  　　　　2) (integer) 7004
  2)　1)　(integer) 0
  　　2)　(integer) 5460
  　　3)　1) "127.0.0.1"
  　　　　2) (integer) 7000
  　　4)　1) "127.0.0.1"
  　　　　2) (integer) 7003
  3)　1)　(integer) 10923
  　　2)　(integer) 16383
  　　3)　1) "127.0.0.1"
  　　　　2) (integer) 7002
  　　4)　1) "127.0.0.1"
  　　　　2) (integer) 7005 d

• 更多對該命令的解釋請參考 CLUSTER SLOTS

• 該命令(CLUSTER SLOTS)不保證可以反悔16384 slots中的所有信息，如果slots配置缺失，clients應該將其初始化未NULL，并在用戶嘗試在這些未分配slots上執(zhí)行命令式上報錯誤。

• 在返回一個錯誤給調(diào)用者之前，當一個slot被發(fā)現(xiàn)沒有分配，client應該再次嘗試獲取slots配置以檢查當前cluster已經(jīng)正確地配置了。

3.5 多key操作

• 對擁有相同hash tag的key，總是可以使用multi-key操作
• 當resharding時：
  • 如果此時所有的key都正好處于相同的節(jié)點，則可以成功進行multi-key操作
  • 否則，multi-key操作不可用，產(chǎn)生一個 "-TRYAGAIN" 錯誤。

3.6 用slave節(jié)點擴展讀操作

• slave節(jié)點默認不可讀，對slave的讀操作將產(chǎn)生 MOVED 錯誤
• 通過READONLY命令，可以將slave節(jié)點設置為可讀
• 通過READWRITE命令，可以清除該節(jié)點的只讀flags值

4 容錯

4.1 心跳包和gossip消息

• Redis Cluster節(jié)點持續(xù)地交換ping和pong包。這兩種包擁有相同的結(jié)構(gòu)，并且都會攜帶重要的配置信息。它們唯一的不同就是消息的類型字段。我們通常把ping和pong包統(tǒng)稱為心跳包(heartbeat packets)。
• 通常節(jié)點發(fā)送的ping包將會觸發(fā)接收者回復一個pong包。當然這并不總是必須的。也有可能節(jié)點會向其他節(jié)點直接發(fā)送包含重要配置信息的pong包，而不需要觸發(fā)回復。這是有用的，例如，在將自己的心配置盡可能快地廣播出去。
• 通常，每一秒里，一個節(jié)點會隨機挑選一些節(jié)點并發(fā)送ping包，因此每個節(jié)點(指定時間內(nèi))發(fā)送的ping包(以及接收到的pong包)的總是是一個常熟，不管集群中有多少節(jié)點。
• 當然，每個節(jié)點一定會主動ping那些自己在NODE_TIMEOUT/2時間內(nèi)沒有發(fā)送過ping或從之接收過pong的節(jié)點。在NODE_TIMEOUT耗盡之前，節(jié)點同樣會嘗試重新連接哪個節(jié)點，以確保這不是由于當前TCP連接問題造成的。
• 如果NODE_TIMEOUT被設置為一個較小的數(shù)字，同時節(jié)點數(shù)目又很大，從全局看，交換的消息數(shù)目會是很可觀的，因為在NODE_TIMEOUT一半的時間內(nèi)，每個節(jié)點會嘗試ping其他所有節(jié)點。
• 例如，在一個擁有100個節(jié)點的集群里，如果把節(jié)點過期設置為60秒，那么每個節(jié)點在30秒內(nèi)將會發(fā)送99個ping，也就是每秒3.3個ping?？紤]到有100個節(jié)點，也就是集群內(nèi)部每秒會生成330個ping包。
• 還是有一些辦法來降低消息總數(shù)的，然而到目前為止還沒有人報告因為Redis Cluster故障檢測而導致的帶寬問題。也必須注意，即使在上面的例子中，每秒330個包交換也是被平分到100個不同的節(jié)點上的，因此對每個節(jié)點來說接收到的流量是可以接受的。

4.2 心跳包內(nèi)容

• ping和pong除了包含一個同樣會被用于所有其他類型的包(例如請求failover選票的包)的包頭(header)外，還有一個特別的Gossip Section。Gossip Section只存在于Ping和Pong包中。
• 通用包頭包含了以下信息：
  • 發(fā)送者的Node ID——這是一個160bit隨機字符串它在一個節(jié)點第一次被創(chuàng)建時生成，并在該Redis Cluster節(jié)點的整個生命周期中保持不變。
  • 發(fā)送者的currentEpoch和configEpoch字段——由Redis Cluster用來加載分布式算法（下一節(jié)中會詳細描述）。對slave，configEpoch就是它的master的configEpoch。
  • 發(fā)送者的node flags——用來表明節(jié)點是slave，還是master，以及其他一些由單bit表示的信息。
  • 發(fā)送者的hash slots的bitmap——如果是一個slave，則代表其master的hash slots的bitmap
  • 發(fā)送者的TCP和port——（port指的是接收普通命令的端口，即+10000就是redis cluster bus端口）
  • 發(fā)送者視角下的集群狀態(tài)——down或者ok
  • 發(fā)送者的master節(jié)點ID（如果這是一個slave）
• ping和pong包同樣包含一個gossip段。該段為接收方提供了這樣一個視圖——發(fā)送方節(jié)點視角的集群中其他節(jié)點的狀態(tài)。Gossip段只包含了發(fā)送方知道的一系列其他節(jié)點中的隨機幾個節(jié)點的信息。Gossip段中包含的節(jié)點的數(shù)目與集群大小成正比。
• 每個被放入gossip段的節(jié)點包含了如下字段：
  - Node ID
  - 該節(jié)點的IP和port
  - 該節(jié)點的Node flags
• Gossip段允許接收方可以得到發(fā)送方視角的集群狀態(tài)。這在故障檢測和節(jié)點發(fā)現(xiàn)時很有用處。

4.3 故障檢測

• Redisu Cluster故障檢測用來識別合適一個master或slave節(jié)點對集群中多數(shù)節(jié)點來說不再可達(no longer reachable)并在之后提升一個slave節(jié)點為master。當無法進行slave晉升時，集群將會被設置為error狀態(tài)，并停止接受客戶端的命令。
• 之前已經(jīng)提及，每個節(jié)點持有每個已知的其他節(jié)點的一系列標簽。有兩個標簽用于故障檢測，他們是PFAIL和FAIL。PFAIL標簽意味著 可能故障 ，是一個不需要確認的故障類型。FAIL意味著一個節(jié)點已經(jīng)失敗，他必須在一段固定的時間內(nèi)由多數(shù)master進行確認。
• PFAIL flag (possible failure)
  • 當節(jié)點發(fā)現(xiàn)某個節(jié)點失聯(lián)超過NODE_TIMEOUT時間后，就會將該節(jié)點標記為PFAIL。無論master還是slave都可以姜其他節(jié)點標記為PFAIL，而不管對方的類型。
  • 對一個Redis Cluster節(jié)點來說，不可達概念的定義為，我們有一個 活躍的ping（指的是我們發(fā)送出但是沒有接收到對方回復的ping）掛起超過了 NODE_TIMEOUT。為了讓這一機制正確工作，NODE_TIMEOUT必須大于一個網(wǎng)絡正常往返的時間。為了增加可靠性，在NODE_TIMEOUT時間過去一半時，如果節(jié)點還沒有得到回復，它會嘗試重新連接其他節(jié)點。這一機制確保了連接保持活躍，因此損壞的鏈接通常不會到之錯誤的在節(jié)點間報告失敗。
• FAIL flag
  • PFAIL flag只是每個節(jié)點針對其他節(jié)點狀態(tài)的本地信息，它不足以被用來觸發(fā)slave晉升。為了確認一個節(jié)點確實down了，PFAIL條件必須升級為FAIL條件。
  • 每個節(jié)點發(fā)出的gossip消息中會隨機包含一部分自己已知的其他節(jié)點的狀態(tài)信息，每一個節(jié)點最終會接收到每個其他節(jié)點的一系列node flags。這為每個節(jié)點提供了一種機制來向其他節(jié)點發(fā)送自己檢測到的節(jié)點失效事件。
• 當如下一系列條件滿足時，PFAIL條件就會升級稱為FAIL條件：
  • 某個節(jié)點(我們稱之為A)，已經(jīng)將另一個節(jié)點B標識為PFAIL
  • 節(jié)點A通過gossip段收集集群中多數(shù)master(majority master)對該節(jié)點的標注
  • 多數(shù)master在 NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT (在當前redis實現(xiàn)中，FAIL_REPORT_VALIDITY_MULTI被設置為2且不可配置) 這段時間內(nèi)將節(jié)點A標注為 PFAIL 或 FAIL。
• 如果上述條件滿足，則節(jié)點A將：
  • 把失聯(lián)節(jié)點標記為FAIL
  • 發(fā)送一個FAIL消息給所有可達節(jié)點
• FAIL消息將會強制所有接收到的節(jié)點將失聯(lián)節(jié)點（節(jié)點B）標記為FAIL，而不管當前自己是否已將其標記為PFAIL
• 【注意】FAIL flag總是單向的，即一個節(jié)點可以從PFAIL變?yōu)?code>FAIL，但是不能反向轉(zhuǎn)變。FLAG標簽只有在以下情況下才會被清除：
  • 節(jié)點是slave，并且重新可達。這種情況下 FAIL 標簽可以清除因為slave節(jié)點不會發(fā)生故障轉(zhuǎn)移。
  • 節(jié)點是master且沒有服務于任何slot，重新可達。這種情況下，FAIL標簽可以被清除，該master繼續(xù)等待被配置后加入集群
  • 節(jié)點是master，重新可達，且在一段較長時間 (N倍NODE_TIMEOUT) 內(nèi) 沒有被檢測到有slave節(jié)點被晉升。顯然此時它應該被作為master將重新加入集群。
• 在從 PFAIL -> FAIL 轉(zhuǎn)變的過程中，使用了弱一致機制(weak agreeement)：
  1. 節(jié)點在一段時間內(nèi)收集其他節(jié)點的視圖(views)，所以即使多數(shù)派master需要達成一致，事實上這只是說明我們在不同的時間，從不同的節(jié)點收集到了這一結(jié)果，我們既無法確定，也無法要求，在什么時刻獲得了多數(shù)master的一致結(jié)果。然而，因為我們會拋棄老舊（過期）的失敗報告，所以多數(shù)派master一定是在某個時間窗內(nèi)對某個節(jié)點的失敗達成了一致。
  2. 即使每個節(jié)點檢測到了 FAIL 條件并通過 FAIL 消息強制集群中其他節(jié)點接受該條件，還是無法保證消息可以倍所有節(jié)點接收到，因為此時可能因為分區(qū)問題導致某些節(jié)點不可達。
• 當然，redis cluster的失敗檢測還有一個活性需求(liveness requirement)：最終所有的節(jié)點需要(should)對一個給定節(jié)點的狀態(tài)達成一致。下面是兩個可能由(集群)腦裂引起的場景(case)：一些少數(shù)派節(jié)點認為某個節(jié)點已經(jīng) FAIL，或是一些少數(shù)派節(jié)點認定某個節(jié)點不在FAIL狀態(tài)。這兩種狀態(tài)下集群對某個節(jié)點最終一定會(在集群全局)有一個唯一的視圖(view)。
  • 場景1： 如果多數(shù)派masters通過失敗檢測及其產(chǎn)生的影響鏈，最終將一個節(jié)點標記為FAIL，所有其他節(jié)點將最終將會把這個master標記為FAIL，因為在指定的時間窗內(nèi)，集群里會有足夠多的失敗被報告。
  • 場景2： 如果只是少數(shù)派master將一個節(jié)點標記為FAIL，slave晉升將不會發(fā)生，所有節(jié)點將會根據(jù)上述的FAIL狀態(tài)清除規(guī)則清除該節(jié)點的FAIL狀態(tài)（例如通過"在N倍NODE_TIMEOUT內(nèi)沒有晉升動作"這一條規(guī)則）。
• FAIL flag只是用來作為一個觸發(fā)機制，它將觸發(fā)執(zhí)行slave晉升算法的安全部分，以便將slave晉升。理論上slave獨立地運作并在發(fā)現(xiàn)它的master不可達后啟動一次晉升，并在多數(shù)masters可以觸達該master時等待其他master拒絕認可。然而，PFAIL -> FAIL 狀態(tài)變遷、弱一致、 在cluster可達節(jié)點間通過FAIL消息強制狀態(tài)的生成，這些額外的復雜度的引入，在實踐上是有它的優(yōu)勢的。因為這些機制的引入，使得集群(可以意識到自己)在處于一個error狀態(tài)下，所有節(jié)點可以拒絕寫入操作。從從使用redis cluster的應用的角度看，這是一個必要的特性。同時這樣也可以避免由于slave自己的問題導致無法連接master，進而導致錯誤的選舉嘗試。

5 配置執(zhí)行，傳播，和故障轉(zhuǎn)移 (Configuration handling,propagation, and failovers)

5.1 集群當前代(cluster current epoch)

• Redis Cluster使用了一個類似Raft算法的"term"的概念，稱為"epoch"(代)。它用來為事件提供遞增的版本號。當多個節(jié)點提供了相互沖突的信息，它讓其他節(jié)點可以正確的理解哪一個狀態(tài)是最新的。
• currentEpoch是一個64bit無符號整數(shù)。
• 在節(jié)點創(chuàng)建時，所有的Redis Cluster節(jié)點，包括slave和master節(jié)點，都把自己的currentEpoch設置為0。
• 每當從其他節(jié)點接收到一個包時，如果發(fā)送方的epoch(包含在cluster總線消息頭中)大于本地節(jié)點的epoch，則本地節(jié)點將自己的currentEpoch更新為發(fā)送方的epoch。
• 因為這一語義，最終所有節(jié)點將會認同集群中擁有最大configEpoch的節(jié)點(提出的主張)。（【譯注】current epoch是用來標識集群epoch的，集群epoch取自所有節(jié)點中configEpoch最大的那個節(jié)點的configEpoch）
• 該信息被用在：當集群狀態(tài)發(fā)生變化，并且一個節(jié)點正在請求其他節(jié)點的同意來執(zhí)行一些操作時(比如slave晉升)。
• 當前的實現(xiàn)里，currentEpoch僅僅被用在slave晉升。簡單來說，epoch是集群的一個本地時鐘，擁有大epoch的消息總是能贏得擁有相對小的epoch的消息。

5.2 配置代(Configuration epoch)

• 每個master總是在ping和pong包中向它的slave廣播自己的configEpoch，和其服務的hash slots的bitmap信息。
• 當一個新master節(jié)點被創(chuàng)建時，configEpoch被設置為0.
• 一個新的configEpoch將會在slave選舉中被創(chuàng)建。在嘗試替代失敗的master時，slave會增加他的epoch并嘗試得到多數(shù)masters的授權(quán)。當一個slave被選中，一個新的唯一的configEpoch會被創(chuàng)建，同時該slave會使用這個新的configEpoch并轉(zhuǎn)變?yōu)橐粋€master。
• 后續(xù)章節(jié)將會解釋，當不同的節(jié)點主張存在分歧時（可能由于網(wǎng)絡分區(qū)或節(jié)點失敗導致），configEpoch時如何幫助解決沖突的。
• slave節(jié)點同樣會在ping和pong包中聲明configEpoch，此時的configEpoch是他的master在上一次包交換中攜帶的configEpoch。這允許其他實例檢測到這個slave有一個老的配置并且需要更新（master節(jié)點將不會向一個擁有舊配置的slave授權(quán)選票）。
• 每當一些已知節(jié)點的configEpoch發(fā)生變化，它就會被所有收到這條信息的節(jié)點永久地保存在各自的node.conf文件里。同理，currentEpoch也會被保存。Redis保證會在執(zhí)行下一個操作前保存這兩個變量并同步到磁盤。
• configEpoch的值在failover時使用一個簡單的算法來保證產(chǎn)生一個新的、遞增的、唯一的值。

5.3 Slave選舉和晉升

• 選舉和晉升總是由slave節(jié)點發(fā)起和處理，在這期間，master節(jié)點會提供一些幫助，它們會為晉升哪個slave而進行投票。當一個master在至少一個slave的視圖中處于FAIL狀態(tài)，并且該slave已經(jīng)要求晉升為master時，slave選舉就會發(fā)生。
• 為了將自己晉升為master，slave需要開啟一個選舉并贏得該選舉。如果一個master處于FAIL狀態(tài)，那么它的所有slave都可以開始一個選舉，但是只有一個slave會贏得最終的選舉并晉升為master。
• 當以下條件符合時，slave將開始一個選舉：
  • 該slave的master處于FAIL狀態(tài)
  • master正在為至少一個以上slot服務
  • slave與master的復制連接斷開時間少于一個給定值，這用來保證晉升的slave的數(shù)據(jù)是盡可能新的。這個值可以由用戶配置。
• 為了被選中，一個slave首先要做的就是增加自己的currentEpoch計數(shù)，并向master實例請求選票。
• Slave通過向集群的每一個master節(jié)點廣播一個 FAILOVER_AUTH_REQUEST 包請求選票。然后它會在不超過2倍NODE_TIMEOUT時間內(nèi)等待所有master的回復（一般至少等2秒）。
• 一旦一個master將選票投給了某個slave，主動回復了 FAILOVER_AUTH_ACK，在時間窗 NODE_TIMEOUT * 2 以內(nèi)，它就再也不能向該master的任何其他slave投票了。從安全性保證上來說，這一規(guī)則不是必須的，但是它有助于避免多個slave在幾乎相同的時間內(nèi)同時被選中（哪怕它們的configEpoch是不同的），而這顯然不是期望得到的結(jié)果。
• slave拋棄那些epoch比自己在發(fā)送選票請求時的currentEpoch小的AUTH_ACK。這保證了它不會計算用于上一次選舉的選票。
• 一旦slave受到了多數(shù)master的ACK，它就贏得了選舉。否則如果在 2 * NODE_TIMEOUT 時間窗（至少2s）內(nèi)沒有得到多數(shù)的回復，選舉就會中止，而一次新的嘗試將在 NODE_TIMEOUT * 4 (至少4s)之后嘗試。

5.4 Slave排序

• 一旦一個master處于FAIL狀態(tài)，一個slave會在嘗試選舉前等待一小段時間。等待的時間按照如下公式計算：
  DELAY = 500 milliseconds + random delay between 0 and 500 milliseconds + SLAVE_RANK * 1000 milliseconds
• 固定的DELAY用來保證FAIL狀態(tài)擴散到整個集群，否則slave可能會在多數(shù)master不知道該FAIL時請求選舉并被拒絕投票。
• 隨機的DELAY用來使slave之間異步，避免在同一時間同時發(fā)起選舉。
• SLAVE_RANK是該slave針對它從master獲得的備份數(shù)據(jù)的總量的排序。在master失敗之后，slave之間通過交換消息來創(chuàng)建一個（最大努力）排序：擁有最新備份offset的slave獲得排序0，第二個更新為1，以此類推。這樣最新的slave會嘗試最先開始選舉。
• 排序的順序并沒有嚴格強制。如果一個擁有最高排序的slave再選劇終失敗了，其他slave會很快進行重試。
• 一旦某個slave贏得了選舉，它就獲得了一個新的唯一的遞增的configEPoch，這個configEpoch會比所有其他現(xiàn)存的master更大。它會在ping和pong包中作為master廣播自己，同時提供自己的服務slot和比之前的master更大的configEpoch。
• 為了加速重配置，新master會向集群內(nèi)所有節(jié)點直接發(fā)送pong包。
• 當前不可達的節(jié)點，最終也將會被重新配置，比如它重新連接后接收到了其他節(jié)點發(fā)來的ping和pong包，或者通過它自己發(fā)送的心跳包被其他節(jié)點檢測到已過期并回復了UPDATE包之后。
• 其他節(jié)點會檢測到有一個新的master服務于之前master相同的slots，但是擁有一個更大的configEpoch，之后它們會更新自己的配置。舊master的其他slave（包括重新接入的舊master自己），不但會更新配置，而且會重新從新的master同步所有數(shù)據(jù)。

5.5 Masters回復slave選舉請求

• Master接收到slave的FAILOVER_AUTH_REQUEST后就會開始一次選舉。
• 只有符合如下條件，master才會授予選票：
  • master針對每一個epoch只會投票一次，一旦投票后就會拒絕所有更小的epoch：每個master有一個lastVoteEpoch字段，并且會拒絕對currentEpoch小于該值的請求投票。一旦master對投票請求回復確認，lasterVoteEpoch就會同步更新并安全地保存到磁盤。
  • 只有當slave所屬的master被標記為FAIL時，master才會投票給該slave
  • 如果一個FAIL_AUTH_REQUEST的cureentEpoch的值小于master的currentEpoch，那么該選舉請求將被忽略。因此，master的回復總是與FAIL_AUTH_REQUEST擁有相同的currentEpoch。如果同樣的slave再次請求選票，并增加了currentEpoch，這可以保證針對舊請求的DELAY的投票不會在新投票請求中被接受。

1. 如果一個master在上一輪選舉中投票過，那么它在NODE_TIMEOUT*2時間窗內(nèi)，不會為該master的任意slave再次投票。這不是嚴格的需求，因為兩個slave不可能在一個相同的epoch中同時獲勝。然而，在實踐中，它保證了當一個slave被選舉后，它擁有足夠的時間通知其他slave并避免其他slave贏得新一輪選舉的可能性，否則這會造成有一次沒有必要的failover。
2. master不會做任何嘗試來保證選出最好的slave。如果slave的master處于FAIL狀態(tài)，且master沒有在當前的term(任期，代?)中投票過，那么它一定會將授予自己的投票。最好的slave總是更可能啟動一次選舉并在其他slave之前贏得選舉，因為由于它擁有更高的排名，它總是會先于其他slave發(fā)起選舉。
3. 當一個master拒絕為某個slave投票，那么它會簡單地忽略該請求，而不會發(fā)出一個負面的響應。
4. master不會投票給這樣的slaves，它們發(fā)送的configEpoch小于master表中為slave宣稱的slot服務的master的configEpoch。記得之前提起過，slave發(fā)送的消息中使用它的master的configEpoch，以及它的master服務的slots。這意味著請求選票的slave必須擁有它打算failover的master的slot配置，并且這個配置需要比授權(quán)選票的master更新或至少相等。

5.6 一個分區(qū)問題中epoch配置有效性實際例子

• 本節(jié)解釋了epoch概念如何使slave在晉升過程中更加能夠容忍分區(qū)(partitions)錯誤
  • 一個master無限期失聯(lián)。它擁有三個slave：A，B，C
  • Slave A贏得了選舉并晉升為master
  • 一個網(wǎng)絡分區(qū)問題導致A對集群的多數(shù)節(jié)點不可用
  • SLave B贏得了選舉并晉升為master
  • 一個分區(qū)問題導致B對集群多數(shù)節(jié)點不可用
  • 網(wǎng)絡問題修復，并且A也恢復可用。
• 此時，B忽然down機并且A恰好以master身份恢復可用(實際上UPDATE消息會及時重新配置它，但我們假設所有的UPDATE消息也丟失了)。這時，slave C嘗試選圖來替代B。接下來：
  1. C嘗試選舉并成功，因為對多數(shù)master來說，它的master的確掛了。它將獲得一個新的增加了的configEpoch。
  2. A不能生成自己時這些hash slots的master，因為其他服務于相同hash slots的節(jié)點已經(jīng)有了一個更大的configuration epoch。
  3. 所以，所有的節(jié)點將會更新它們的配置表并將這些hash slots分配給C，集群可以繼續(xù)運行。
• 在下一節(jié)中，你會看到，一個舊節(jié)點重新加入cluster，它將立刻被通知到配置的變更，因為一旦它主動ping其他節(jié)點，接收方就會檢測到它有一個陳舊的集群信息，并向它發(fā)送一條UPDATE消息。

5.7 Hash slots配置傳播

• Redis Cluster中很重要的部分就是提供一種機制，用來傳播集群中哪個節(jié)點服務于哪些hash slot信息。這無論是在集群啟動還是在slave晉升時都非常重要。

• 同樣的機制保證了節(jié)點在不限期遇到分區(qū)問題后能以一種明智的方式重新加入集群。

• 有兩種生成hash slots配置的方式：

  • heartbeat消息。ping和pong消息的發(fā)送者總是添加自己或自己的master所服務的hash slots信息。
  • UPDATE消息。因為每個heartbeat包都有發(fā)送方的configEpoch和其服務的hash slots，如果接收方發(fā)現(xiàn)發(fā)送方的信息過期，它姜發(fā)送一個包含了新信息的包，強制過期節(jié)點更新自己的信息。

• 心跳包消息或UPDATE消息的接收方使用一種簡單的規(guī)則來更新表映射中的hash slots到對應的節(jié)點。當一個新的Redis Cluster 節(jié)點被創(chuàng)建，它的本地hash slot表被初始化為NULL，這樣每個hash slot就不會被綁定到任何節(jié)點。它看上去就像這樣：

  0 -> NULL
  1 -> NULL
  ...
  16383 -> NULL

• 配置傳播的規(guī)則如下：

  • Rule 1: 如果一個hash slot沒有被分配(NULL)，這時如果有一個已知節(jié)點聲明了該slot，則修改本地hash slot table并將聲明的hash slots關聯(lián)到該節(jié)點。
    • 當一個新的cluster被創(chuàng)建，系統(tǒng)管理員需要手動分配(使用命令CLUSTER ADDSLOTS，一般通過redis-trib命令行工具，或其它類似的工具)所有的slots給它的master，這一信息會很快在整個集群中傳播。
  • Rule 2: 如果一個hash slot已經(jīng)被分配，并且一個已知節(jié)點廣播消息中的configEpoch比當前擁有該slot的master的configEpoch更大，則重新綁定hash slot到新節(jié)點。
  • 因為rule 2，最終所有節(jié)點一定會通過節(jié)點間的消息廣播就configEpoch最大的節(jié)點獲得slot的擁有權(quán)達成一致。
  • 這一機制被稱為 last failover wins(最后故障轉(zhuǎn)移者勝)
  • 同樣的情況也發(fā)生在resharding(重分片)。當一個節(jié)點importing一個hash slot并完成，它的configuration epoch將被增加以確保改動會被擴散到整個集群。

5.8 UPDATE消息，a closer look

• Node A在一段時間后重新加入集群。它將發(fā)送heartbeat包并聲明自己服務于hash slots1和2，而configuration epoch為3。所有更新了最新集群信息的接收者卻看到相同的hash slots已經(jīng)被關聯(lián)到了節(jié)點B，并且節(jié)點B擁有更高的configuration epoch。因此它們會發(fā)送一條UPDATE消息給A，同時帶上這些slots的心配置。A將會根據(jù)rule2更新自己的配置。

5.9 節(jié)點如何重新加入集群

• 同樣的機制也被用于一個節(jié)點重新加入集群。繼續(xù)上面的例子，節(jié)點A會被通知hash slots1和2現(xiàn)在被節(jié)點B服務。假設A之前只服務這兩個hash slots，那么目前A服務的slots數(shù)目就會將為0。因此A將會重新配置為新master的slave。
• 實際上遵循的規(guī)則比上述場景更復雜一些。同上這在A經(jīng)過很長時間的斷開后重新加入集群時更容易發(fā)生，這時A發(fā)現(xiàn)它之前服務的hash slots目前被多個節(jié)點服務，例如hash slot 1由節(jié)點B服務，而hash slot 2被節(jié)點C服務。
• 所以真是場景中Redis Cluster節(jié)點角色切換的規(guī)則是：
  • 一個master節(jié)點(在重新加入集群后)將會修改自己的配置為：自動從屬于(be slave of)之前該master服務的最后一個hash slot的新master
• 通過重新配置，最終該節(jié)點服務的所有hash slots將會被丟棄，且該節(jié)點會被重新配置。
• 對slave而言也是一樣的：它們會將自己配置為之前master的最后一個hash slot的新master的備份節(jié)點。

5.10 備份遷移(Replica migration)

• Redis Cluster實現(xiàn)了一個稱為備份遷移(replica migration)的概念(特性)，用來提升系統(tǒng)可用性。在一個由master-slave組成的集群中，如果slaves和masters之間的映射關系是固定的，那么集群的可用性隨著時間的推移，姜會因為單個節(jié)點的失敗而變得越來越差。
• 例如，在一個每個master擁有一個slave的集群中，集群在任意一個master或slave失敗后還能繼續(xù)運作，但是如果master和slave同時失敗，則集群就無法繼續(xù)使用了。不幸的是，由于硬件或軟件的問題，總是會有一類錯誤造成但個節(jié)點的失敗，并且隨著時間而積累。比如：
  • Master A只有一個slave A1
  • Master A發(fā)生了故障了，A1被晉升為新的master
  • 三小時后，由于各種問題，A1也發(fā)生了故障。此時已經(jīng)沒有其他slave可以被晉升了，因為A和A1已經(jīng)全部宕機。Cluster這時會進入error狀態(tài)而不能繼續(xù)提供服務。
• 如果masters和slaves之間的映射關系是固定的，那么唯一能保證集群更穩(wěn)定的方法就是為每個master添加更多的slave，然而這樣做的成本非常昂貴，因為它需要添加更多的Redis實例，以及更多的內(nèi)存等。
• 另一個可用方案是在集群中創(chuàng)建不對稱(slave)，并允許集群布局隨著時間自動發(fā)生變化。例如，集群可以擁有三個masters：A，B，C。A和B分別有一個slave，A1和B1。而master C與之不同，它擁有兩個slaves：C1和C2。
• 備份遷移是一種slave自動重配的過程，它用來將備份節(jié)點遷移到當前已經(jīng)沒有可用slave的master上。通過備份遷移，上述場景變?yōu)椋?
  • Master A發(fā)生故障。A1被晉升。
  • C2遷移為A1的slave，否則A1將會沒有任何slave。
  • 三小時后A1也發(fā)生了故障
  • C2被晉升為新的master以替代A1
  • 此時，集群還能正常提供服務。

5.11 備份遷移算法

• 歉意算法不需要使用任何的協(xié)商(agreement)，因為在Redis Cluster中，slave布局不是集群配置的一部分，他不需要通過config epoch提供任何的一致性和/或版本化保證。相反，在master沒有回歸之前，它使用了一種避免slave塊遷移(mass-migration)的算法。這種算法保證了最終(一旦集群配置變得穩(wěn)定后)每個master至少可以擁有一個slave。
• 這就是該算法的工作方式。我們先從『什么是一個好的slve(a good slave)』的定義開始：一個好的slave指的是，從某個節(jié)點角度，處于非FAIL狀態(tài)的slave節(jié)點。
• 每個slave一旦檢測到目前至少有一個master沒有好的slave，就會觸發(fā)該算法。然而，在所有檢測到這一情況的slave中，只有一個子集會真正行動(act)。這個子集實際上通常只有一個slave，除非不同的slaves在特定時刻對其他節(jié)點的失敗狀態(tài)有一個略微不同的視圖。
• 行動slave(acting slave) 是一個這樣的slave：它是集群中擁有最多slave的master的一個ID最小的slave。
• 例如，對于這樣的一個集群，集群中有10個masters每個擁有1個slave，有2個masters每個擁有5個slaves，那么即將發(fā)生遷移的slave是 —— 在2個擁有5個slaves的master中 - 擁有最小節(jié)點ID的那個。確認這點不需要使用任何協(xié)商，只是有可能在集群配置不穩(wěn)定的時候，發(fā)生競爭條件，這時多個slave會認為自己是擁有更小節(jié)點ID的非失敗節(jié)點 (實際上這很難發(fā)生)。如果發(fā)生了，結(jié)果就是會有多個slaves被遷移到同一master，這本身并沒有害處。如果競爭導致失去slave的master變成孤節(jié)點，一旦集群穩(wěn)定后，該算法會再次被執(zhí)行并轉(zhuǎn)移一個可用slave給該節(jié)點。
• 最終每個master將會擁有至少一個slave。然而，通常行為都會是，只有一個slave從其擁有多個slaves的master遷移到另一個孤master上。
• 算法會被一個稱為cluster-migration-barrier的用戶配置參數(shù)控制，該參數(shù)指定了在發(fā)生備份遷移之前，一個master必須擁有的好slave的數(shù)目。例如，如果該參數(shù)被設置為2，那么只有在某個master擁有2個可工作slaves時，其中一個slave才能嘗試遷移(【譯注】通過檢查代碼，應該是擁有2個或2個以上可工作slaves時，其中一個可以發(fā)生遷移)。

5.12 configEpoch沖突解決算法

• 在failover階段，slave晉升中會產(chǎn)生一個新的configEpoch值，并且這個值被保證是唯一的。
• 然而如果有兩個不同的events通過不安全的方式分別生成新的configEpoch值，它們將會僅僅把本地的currentEpoch自增并寄希望于同一時間內(nèi)不會有沖突。比如，系統(tǒng)管理員同時觸發(fā)了兩個events：
  1. 帶TAKEOVER選項的CLUSTER FAILOVER會手動晉升一個slave節(jié)點到master，并且不需要多數(shù)master的同意。這是個有用的操作，比如，在多數(shù)據(jù)中心創(chuàng)建時
  2. 為集群rebalancing而遷移slots，為了性能考慮，這同樣會在節(jié)點內(nèi)產(chǎn)生新的configuration epochs而不需要其他節(jié)點的同意。
• 特別的，在手動重分片(reshardings)期間，當一個hash slot被從節(jié)點A遷移到節(jié)點B時，重分片程序?qū)娭埔驜更新它的configuration epoch為集群中的最大值加1（除非此時B的configuration epoch已經(jīng)是集群中最大的），而不需要請求其他節(jié)點的同意。
• 通常一次真實世界的resharding會設計數(shù)百hash slot的遷移（尤其在較小的集群里）。在resharding期間，如果每一個slot遷移都需要為生成新的configuration epoch而請求其他節(jié)點的同意，這將會很沒有效率。而且，這回要求集群中的節(jié)點每次都通過fsync來保存這一新的配置（configuration epoch）。因為這些原因，我們采用如下行為處理reshardings時的configEpoch：我們只需要在第一個hash slot遷移時生成一個新的configEpoch，這在生產(chǎn)環(huán)境中會更加有效率。
• 然而，因為上述兩種情況，有可能發(fā)生（雖然很難）多個節(jié)點擁有相同的configuration epoch的情況。一個resharding操作有管理員發(fā)起，同時一次failover恰巧發(fā)生，外加一點壞運氣，如果各自的epoch沒有在足夠短的時間內(nèi)擴散開，這將會會導致currentEpoch沖突。
• 更進一步來說，軟件bug和文件系統(tǒng)破壞，這同樣可能導致多個節(jié)點擁有相同的configuration epoch。
• 當服務于不同hash slots的master擁有相同的configEpoch時，這不會有什么問題。相對而言，更重要的是，當slave故障恢復一個master時，它需要擁有唯一的configuration epoch。
  也就是說，手動干預或resharding會用一種不同的方式改變集群配置。Redis Cluster主要的liveness property要求，slot配置總是匯聚的，因此我們總是期望所有場景下，所有的master節(jié)點總是擁有不同的configEpoch。
• 為了強制達到上述目的，當兩個節(jié)點以相同的configEpoch結(jié)束某個操作時， 沖突解決算法 將會被用來處理這一場景。
  • 如果一個master節(jié)點檢測到其他master節(jié)點正在廣播一個像同的configEpoch
  • 并且 如果本節(jié)點擁有一個按字典排序更小的節(jié)點ID
  • 那么 它會將自己的currentEpoch增加1，并用這一新值作為自己的configEpoch。
• 如果還有任意數(shù)目的節(jié)點擁有相同的configEpoch，那么除了擁有最大ID的節(jié)點，所有其他節(jié)點都將被前移，來保證最終每個節(jié)點都擁有一個唯一的configEpoch。
  這一機制同樣也保證了，在一個新的集群被創(chuàng)建后，所有的節(jié)點都會以一個不同的configEpoch開始，盡管它們并沒有被用到，因為redis-trib會保證使用CONFIG SET-CONFIG-EPOCH為每一個節(jié)點設置不同的ID。
• 然而，如果因為某些原因一個節(jié)點沒有被配置，它還是會自動地更新自己的配置到一個不同的configuration epoch（因為有沖突解決算法的保證）。

5.13 節(jié)點reset

• 節(jié)點可以被軟件重置(software reset)，而不需要重啟，以便用于不同的role或不同的cluster。
• CLUSTER RESET命令包含連個變種：
  • CLUSTER RESET SOFT
  • CLUSTER RESET HARD
• 命令必須被直接發(fā)送給待reset的節(jié)點。默認使用soft reset。
• 下面是一個reset命令所做的操作：
  1. SOFT/HARD: 如果節(jié)點是slave，將其轉(zhuǎn)化為master，刪除所有數(shù)據(jù)。如果節(jié)點是master且包含keys，則reset失敗
  2. SOFT/HARD: 釋放所有的slots，重置手動failover狀態(tài)
  3. SOFT/HARD: 刪除該節(jié)點上node table中所有其他節(jié)點，即該節(jié)點不再知道任何其他節(jié)點的信息
  4. HARD only: 重置currentEpoch，configEpoch，和lastVoteEpoch為0
  5. HARD only: Node ID變更為一個新的隨機ID。
• 擁有非空數(shù)據(jù)集的master節(jié)點不能被reset，因為一般而言你可能希望先reshard數(shù)據(jù)到其他分片?；蛘撸谀承┨囟▓鼍跋?，比如當一個cluster已經(jīng)完全被破壞而需要創(chuàng)建一個新cluster時，可以用FLUSHALl先清空數(shù)據(jù)，然后再reset。

5.14 從集群移除節(jié)點

• 如果希望移除一個節(jié)點，從實踐上來說，resharding它的所有數(shù)據(jù)到其他節(jié)點（如果這是一個master），然后關閉它，這樣是可行的。但是，其他節(jié)點姜還會技術該節(jié)點的node ID和地址，并會嘗試連接它。
  因此，當一個節(jié)點需要被移除時，我們希望把它徹底從其他節(jié)點的node table中一并移除。這可以通過CLUSTER FORGET <node-id>命令來實現(xiàn)。
• 該命令做了兩件事情：
  1. 它把該節(jié)點從其他節(jié)點的nodes table中移除
  2. 它設置了一個60秒的禁用期，來防止一個節(jié)點使用相同的node id重新加入集群。
• 上述第二條時必要的，因為Redis Cluster使用gossip來自動發(fā)現(xiàn)節(jié)點，因此從節(jié)點A刪除節(jié)點X，會導致節(jié)點B從節(jié)點A處通過gossip重新發(fā)現(xiàn)該節(jié)點（X）。而通過引入60秒禁用期，Redis Cluster管理工具就可以有60秒的時間來逐一在所有節(jié)點刪除X，并防止它被重新發(fā)現(xiàn)。

6. Publish/Subscribe

• 在Redis Cluster集群中，client可以在任何節(jié)點上訂閱(subscribe)消息，也可以向任何節(jié)點發(fā)布(publish)消息。如果需要，集群會保證發(fā)布的消息被正確轉(zhuǎn)發(fā)。
• 當前的實現(xiàn)中，發(fā)布的消息將會被簡單地廣播到所有節(jié)點，但有時候他是可以使用Bloom過濾器或其他算法進行優(yōu)化的。