Nosql，作為程序員在當下不了解點兒，還真不行，出去聊起來別人就會說你土。那么就聊聊其中一個比較火的redis。redis單機版沒得說，但是一直沒有集群版，有也是山寨的。前段時間對redis的實現(xiàn)進行了一些學習，明天就要發(fā)布redis集群的穩(wěn)定版，作為紀念以及學習，發(fā)一下redis集群實現(xiàn)的細節(jié)，英文好的就看原文吧。

redis集群實現(xiàn)一個高性能、線性可擴展的1000節(jié)點的集群。

Redis集群沒有最重要或者說中心節(jié)點，這個版本最主要的一個目標是設計一個線性可伸縮（可隨意增刪節(jié)點？）的功能。

Redis集群沒有任何的數(shù)據(jù)合并動作。寫，直接是與主節(jié)點通信，但同步到slave也有一個時間窗口。在可用性方面，除了master以及所有slave失效，不然一直可用。

Redis集群為了數(shù)據(jù)的一致性可能犧牲部分允許單點故障的功能，所以當網(wǎng)絡故障和節(jié)點發(fā)生故障時這個系統(tǒng)會盡力去保證數(shù)據(jù)的一致性和有效性。（這里我們認為節(jié)點故障是網(wǎng)絡故障的一種特殊情況）

為了解決單點故障的問題，我們同時需要masters 和 slaves。 即使主節(jié)點(master)和從節(jié)點(slave)在功能上是一致的，甚至說他們部署在同一臺服務器上，從節(jié)點也僅用以替代故障的主節(jié)點。 實際上應該說 如果對從節(jié)點沒有read-after-write（寫并立即讀取數(shù)據(jù) 以免在數(shù)據(jù)同步過程中無法獲取數(shù)據(jù)）的需求，那么從節(jié)點僅接受只讀操作。

已實現(xiàn)的子集

Redis集群實現(xiàn)單一key在非分布式版本的Redis中的所有功能。對于復合操作比如求并集求交集之類則只實現(xiàn)在單個節(jié)點的操作。

增加了hash tags的概念，主要用來強制把某些multi-key分配在一個節(jié)點。但是在resharding中，這些multi-key可能找不到。

Redis集群版本將不再像獨立版本一樣支持多數(shù)據(jù)庫，在集群版本中只有database 0，并且SELECT命令是不可用的。

客戶端與服務端在Redis集群版中的約定

在Redis集群版本中，節(jié)點有責任/義務保存數(shù)據(jù)和自身狀態(tài)，這其中包括把數(shù)據(jù)（key）映射到正確的節(jié)點。所有節(jié)點都應該自動探測集群中的其他節(jié)點，并且在發(fā)現(xiàn)故障節(jié)點之后把故障節(jié)點的從節(jié)點更改為主節(jié)點（原文這里有“如果有需要” 可能是指需要設置或者說存在從節(jié)點）。

集群節(jié)點使用TCP bus和二進制協(xié)議進行互聯(lián)并對任務進行分派。各節(jié)點使用gossip 協(xié)議發(fā)送ping packets給集群其他節(jié)點以確定其他節(jié)點是否正常工作。Cluster bus也可以用來在節(jié)點間執(zhí)行PUB/SUB命令。

當發(fā)現(xiàn)集群節(jié)點無應答的時候則會使用redirections errors -MOVED and -ASK命令并且會重定向至可用節(jié)點。理論上客戶端可隨意向集群中任意節(jié)點發(fā)送請求并獲得重定向，也就是說客戶端實際上并不用關心集群的狀態(tài)。然而，客戶端也可以緩存數(shù)據(jù)對應的節(jié)點這樣可以免去服務端進行重定向的工作，這在一定程度上可以提高效率。

安全寫

Redis cluster節(jié)點之間通過異步復制，這樣總會存在丟數(shù)據(jù)的窗口。但是client在連接master多的分區(qū)和少的分區(qū)的窗口是不一樣的。

Redis cluster在連接master多的分區(qū)的時候，盡量保證不丟寫操作。除了下面兩種情況：

1）當一個寫到達master，master已經(jīng)回復client，但是master還沒來的及復制到slave就宕機了，那么這個寫操作就會丟失。直到其中一個slave被提拔為master。

2）另外一種理論上可能丟失寫操作的情況如下，

一個master因為partition不可到達

其中一個slave獲取master失敗

一會兒后master可以重新到達

一個client沒用更新路由表，還在向舊的master寫

實際上，這是不太可能發(fā)生，因為節(jié)點無法到達其他大多數(shù)master故障切換，不再接收寫操作需要足夠的時間，并當分區(qū)固定后，一段時間內(nèi)寫操作仍然是拒絕的，讓其他節(jié)點通知有關配置更改。

Redis cluster會丟失很多寫操作，當一個或多個客戶端連接到一個少master分區(qū)時。因為如果這些master不可以到達多master的分區(qū)，這些寫操作就會丟失。

如果在NODE_TIMEOUT前不可到達，不會丟消息，如果在NODE_TIMEOUT后，會有消息丟失。（暫時不理解為啥不丟消息）。

可用性

少master分區(qū)是不開用的，假設多master分區(qū)至少有一個不開到達master的slave，那么在NODE_TIMEOUT后，slave就會被選舉為相應的master。假設一個master有一個slave，那么可用性為1-(1/(2*n-1))。

性能

在Redis中不在通過代理命令來確定給定鍵的節(jié)點，而是它們將客戶端重定向到服務密鑰空間的給定部分的節(jié)點。

最終客戶保存著集群和那個節(jié)點提供密鑰的時間標識符，所以在正常操作期間，client直接聯(lián)系合適的節(jié)點，以便發(fā)送給定的命令。

因為使用異步復制的，節(jié)點不等待寫入的其他節(jié)點的確認。

此外，由于限制多個鍵執(zhí)行操作命令的子集，如果不rsharding，數(shù)據(jù)從來不在節(jié)點之間移動。

所以在單個Redis的實例下，正常操作處理可以完成的，在N個主節(jié)點Redis的集群，可以期望以單一的Redis實例相同的性能乘以N作為設計的線性擴展。在同一時間，通常在單次往返執(zhí)行查詢，因為客戶通常保持與節(jié)點持久連接，以便和單個獨立的Redis節(jié)點延遲性也是一樣的。

非常高的性能和弱（非CAP）的可擴展性，但合理的形式一致性和可用性是主要目標。

為什么避免合并操作

Redis集群設計避免了版本沖突的相同鍵值在多個節(jié)點，因為在Redis的數(shù)據(jù)模型下，這并不總是可取的：在Redis的值通常都非常大，這是經(jīng)常可以看到的，列表或數(shù)百萬元素的sorted set。另外，數(shù)據(jù)類型在語義上是復雜的。轉移和合并這些類型的值，可能需要的應用程序端邏輯實現(xiàn)。

Keys分配模式

Key分為16384，這樣最多可以有16384個節(jié)點，但是建議最多有1000個節(jié)點。

所有的主節(jié)點會控制16384個key空間的百分比。當集群穩(wěn)定之后，也就是說不會再更改集群配置（hash slot不在節(jié)點之間移動），那么一個節(jié)點將只為一個hash slot服務。（但是服務節(jié)點（主節(jié)點）可以擁有多個從節(jié)點用來防止單點故障）

用來計算key屬于哪個hash slot的算法如下：

HASH_SLOT = CRC16(key) mod 16384

Name: XMODEM (also known as ZMODEM or CRC-16/ACORN)

Width: 16 bit

Poly: 1021 (That is actually x^16 + x^12 + x^5 + 1)

Initialization: 0000

Reflect Input byte: False

Reflect Output CRC: False

Xor constant to output CRC: 0000

Output for "123456789": 31C3

這里我們會取CRC16后的14個字節(jié)。在我們的測試中，對于16384個slots， CRC16算法最合適。

Keys散列tags

有一個計算hash slots的例外是使用hash tags。Hash tags以確保兩個鍵被分配在相同的hash slot。這是用在為了實現(xiàn)多鍵在Redis集群中操作。

為了實現(xiàn)hash tags，hash時使用了不同的算法。基本上如果關鍵字包含“{...}”，那么在{和}之間的字符串被hash，然而可能有多個匹配的{或}該算法由以下規(guī)則規(guī)定：

如果key包含｛，在｛的右邊有一個｝，并在第一次出現(xiàn)｛與第一次出現(xiàn)｝之間有一個或者多個字符串，那么就作為key進行hash。例如，{user1000}.following和{user1000}.followed就在同一個hash slot；foo{}{bar}整個字符被hash，foo{{bar}},{bar被hash；foo{bar}{zap},bar被hash。

集群節(jié)點特性

在集群中每個節(jié)點都擁有唯一的名字。節(jié)點名為16進制的160 bit隨機數(shù)，當節(jié)點獲取到名字后將被立即啟用。節(jié)點名將被永久保存到節(jié)點配置文件中，除非系統(tǒng)管理員手動刪除節(jié)點配置文件。

節(jié)點名是集群中每個節(jié)點的身份證明。在不更改節(jié)點ID的情況下是允許修改節(jié)點IP和地址的。cluster bus會自動通過gossip協(xié)議獲取更改后的節(jié)點設置。

每個節(jié)點可獲知其他節(jié)點的信息包括：

IP 端口

狀態(tài)

管理的hash slots

cluster bus最后發(fā)送PING的時間

最后接收到PONG的時間

標記節(jié)點失敗的時間

從節(jié)點數(shù)量

如果是slave，那么還包含master節(jié)點ID

無論是主節(jié)點還是從節(jié)點都可以通過CLUSTER NODES命令來獲取以上信息
示例如下：

$ redis-cli cluster nodes

d1861060fe6a534d42d8a19aeb36600e18785e04 :0 myself - 0 1318428930 connected 0-1364

3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 connected 1365-2729

d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931

集群拓撲結構

Redis的集群是一個全網(wǎng)狀的，通過TCP，每一個節(jié)點都與其他每個節(jié)點連接。在N個節(jié)點的集群中，每個節(jié)點有N-1個對外TCP連接，和N-1的傳入連接。這些TCP連接一直保持著，不需要的時候才創(chuàng)建。

節(jié)點握手

節(jié)點永遠接受集群總線端口的連接，即使ping命令的節(jié)點不被信任，當收到ping時也回復。但是，如果該節(jié)點不是集群中的，所有的其他數(shù)據(jù)包將被丟棄。

一個節(jié)點被另一個視為集群的一部分，只能通過下面兩種方式：

1）如果一個節(jié)點的MEET消息。和ping消息相似，但強制把該節(jié)點做為集群的一部分。只有系統(tǒng)管理員通過以下的命令，節(jié)點才發(fā)送MEET消息給其他節(jié)點。

CLUSTER MEET ip port

2）節(jié)點也將注冊另一個信任的節(jié)點作為集群的一部分。如果A知道B和B知道C，最終B就發(fā)送C相關的gossip消息到A。當發(fā)生這種情況，A將C作為網(wǎng)絡的一部分，并會嘗試連接C。

這意味著，只要我們加入的節(jié)點在連通圖中，他們最終會自動形成一個完全連通圖。基本上集群能夠自動發(fā)現(xiàn)其他節(jié)點，但僅當由系統(tǒng)管理員確定。這種機制使得集群更加健壯，但可防止意外地混合不同的Redis集群將IP地址或其它變化后的網(wǎng)絡相關事件。如果鏈接斷開，所有節(jié)點積極嘗試連接到所有其他已知的節(jié)點。

MOVED重定向

客戶端發(fā)送查詢到集群中的隨便一個節(jié)點，甚至是slave，該節(jié)點分析查詢，看key在那個節(jié)點hash slot中，如果hash slot在本節(jié)點，處理非常簡單，否則檢查hash slot和節(jié)點ID對應關系，方式MOVED error。

一個MOVED error如下：

GET x

-MOVED 3999 127.0.0.1:6381

錯誤包含key的hash slot和IP：port，客戶端需要重新發(fā)出查詢到指定的ip和port，在重新發(fā)送前，需要很長一段時間，那么在這期間，配置文件可能發(fā)生了變化，但是目的節(jié)點仍然回復MOVED error。

盡管集群節(jié)點由id來確定，但是我們只給客戶端暴漏hash slot和IP：port的對應關系。客戶端盡量記住，hash slot（3999）和27.0.0.1:6381對應。這樣計算出目標key的hash slot，非常有機會直接找到相應的node。

當集群穩(wěn)定，那么所有客戶端有hash slot和node的對應關系，這樣集群效率非常高，就不存在重定向代理和單節(jié)點故障。

集群實時重新配置

Redis的集群支持在群集運行時添加和刪除節(jié)點。實際上添加或刪除一個節(jié)點被抽象成相同的操作，即移動hash slot從一個節(jié)點到另一個節(jié)點。

若要將新節(jié)點添加到集群中的空節(jié)點，即hash slot從現(xiàn)有節(jié)點移動到新的節(jié)點。

從群集中刪除一個節(jié)點，即分配給該節(jié)點的hash slot移動到其他現(xiàn)有節(jié)點。

因此，實施的核心是圍繞移動hash slot。其實從實用的角度出發(fā)hash slot僅僅是一組key。因此Redis集群resharding是keys從一個實例鍵移動到另一個實例。

要理解這是如何工作，那么必須知道集群的slots轉化的子命令。如下：

CLUSTER ADDSLOTS slot1 [slot2] ... [slotN]

CLUSTER DELSLOTS slot1 [slot2] ... [slotN]

CLUSTER SETSLOT slot NODE node

CLUSTER SETSLOT slot MIGRATING node

CLUSTER SETSLOT slot IMPORTING node

前兩個命令ADDSLOTS和DELSLOTS，只是用來分配（或刪除）一個Redis的節(jié)點slots。分配后，將使用gossip協(xié)議在集群傳播。該ADDSLOTS命令通常用于一個新的集群為所有節(jié)點從頭配置slots的一個快速的方式。

SETSLOT子命令用于將slots指定給特定節(jié)點的ID，除了該節(jié)點的形式被使用。否則，該slot可指定兩個特殊的狀態(tài)MIGRATING和IMPORTING：

1）當一個slot被設置為MIGRATING時，該節(jié)點將接受的是關于這個哈希位置查詢的所有請求，但前提是鍵存在。否則查詢使用-ASK重定向目標節(jié)點。

2）當一個slot被設置為IMPORTING，該節(jié)點將接受的是關于這個哈希位置查詢的所有請求，但只有請求被前面ASKING。否則，查詢MOVED到真正的hash slot所有者。

起初這看起來很奇怪，但現(xiàn)在我們會更清楚。假設我們有兩個Redis的節(jié)點，稱為A和B。我們想要移動的hash slot8從A到B，所以我們發(fā)出的命令是這樣的：

We send B: CLUSTER SETSLOT 8 IMPORTING A

We send A: CLUSTER SETSLOT 8 MIGRATING B

所有節(jié)點都指向A，每次都查詢屬于8的key，會發(fā)生：

All the queries about already existing keys are processed by "A".

All the queries about non existing keys in A are processed by "B".

在A就不再建立新的keys，集群配置管理工具redis－trib可以查看：

CLUSTER GETKEYSINSLOT slot count

上述命令將返回該slot中key的個數(shù)，從A遷移到B的每一個key（是原子的）都會顯示，如：

MIGRATE target_host target_port key target_database id timeout

MIGRATE將連接到目標實例，發(fā)送鍵的序列化版本，一旦接收到ok，會刪除key的舊數(shù)據(jù)集。因此在一定時間段，從外部客戶端看來key存在于A或B。

在Redis的集群沒有必要指定除0以外的數(shù)據(jù)庫，但MIGRATE可用于不涉及Redis集群的其他任務。即使是復雜的key如lists，MIGRATE優(yōu)化的也非常快。但如果有等待時間約束的應用，在重新配置redis集群，使用big keys是不明智的。

ASK重定向

在上一節(jié)中，我們簡要地談到了ASK重定向，為什么我們不能簡單地用MOVED重定向？MOVED重定向意味著hash slot永久在那個節(jié)點，下一個查詢應該嘗試對指定的節(jié)點，ASK只表明到指定節(jié)點查詢。

ASK表明hash slot8下的key仍然在A中，所以我們總是希望client將嘗試A，如果需要然后B。由于這種情況只有hash slot超出16384時發(fā)生，性能損失是可以接受的。

然而，我們需要強制該客戶端的行為，所以為了確保客戶端將只嘗試hash slotB，A嘗試后，節(jié)點B就只能接受客戶端發(fā)送ASK并被設置為IMPORTING hash slot的查詢。

對于client，ASK語義如下：

1)如果收到ASK重定向，只把這次查詢發(fā)向指定的節(jié)點

2）伴隨ASK，開始查詢

3）不更新hash slot 8 到B的映射

如果hash slot 8遷移完成，那么就會發(fā)送MOVED消息，client會永久保存hash slot 8到新IP：port的映射。如果有客戶端提前映射，也是沒有問題的，那么查詢的時候沒有ASK消息，那么會發(fā)送MOVED消息，重定向到A。

多key操作

使用hash tags操作多key，下面的操作是有有效的：

MSET {user:1000}.name Angela {user:1000}.surname White

當hash slot正在從一個節(jié)點移動到另一個節(jié)點，由于人工resharding，多健操作不可用。

更具體地講，即使在resharding，多鍵操作key所有位于同一節(jié)點（源或目的節(jié)點），key仍然可用。

在resharding，源和目的分開，多健操作將產(chǎn)生TRYAGAIN error，client在稍后嘗試操作，或匯報錯誤。

容錯

節(jié)點心跳和gossip消息

每一秒，通常一個節(jié)點將ping幾個隨機節(jié)點，這樣ping的數(shù)據(jù)包的總數(shù)量（和接收的pong包???? ）是一個恒定的量，無論集群中節(jié)點的數(shù)量。

但是每個節(jié)點可確保ping通，ping或pong不超過一半NODE_TIMEOUT。前NODE_TIMEOUT已過，節(jié)點也嘗試重新與另一個節(jié)點的TCP鏈接，節(jié)點不相信因為當前TCP鏈接，是不可達的。

信息的交換量大于O（N） ，NODE_TIMEOUT設置為一個小的數(shù)字，但節(jié)點的數(shù)量（N）是非常大的，因為每個節(jié)點將嘗試ping ，如果配置信息在NODE_TIMEOUT一半的時間沒有更新。

例如，NODE_TIMEOUT設置為60秒的100個節(jié)點集群，每個節(jié)點會嘗試發(fā)送99 ping每30秒，那么每秒3.3個ping，即乘以100個節(jié)點是每秒330個ping。

有一些方法可以使用已經(jīng)通過交換的Redis集群的gossip信息，以減少交換的消息的數(shù)量。例如，我們可以ping那些一半NODE_TIMEOUT內(nèi)“可能的失敗”狀態(tài)的節(jié)點，然后每秒ping幾個包到那些工作的節(jié)點。然而，在現(xiàn)實世界中，設置非常小的NODE_TIMEOUT的大型集群可靠地工作，將在未來作為大型集群實際部署測試。

ping和pong消息內(nèi)容

ping和pong都包含一個通用的header和一個gossip消息節(jié)。

通用的header內(nèi)容如下：

1）節(jié)點ID，在創(chuàng)建節(jié)點的時候分配的一個160位的偽隨機數(shù)，并在集群中保持不變。

2）currentEpoch和configEpoch字段，這是為了安裝Redis集群的分布式算法使用。如果節(jié)點是一個slave，那么configEpoch是master最后版本的configEpoch。

3）節(jié)點的標志，表明該節(jié)點是slave、master和其他單位節(jié)點的信息。

4）給定節(jié)點的hash slot位圖，如果該節(jié)點是slave，那么是master hash slot的位圖。

5）端口：發(fā)送方的TCP基本端口（也就是，使用Redis的接受客戶端的命令，加10000，得到集群的端口）。

6）狀態(tài)：發(fā)送者的狀態(tài)（down或OK）。

7）主節(jié)點的ID，如果是slave。

ping和pong都包含一個gossip節(jié)，給接受者提供集群中其他節(jié)點的信息，只是sender知道的隨機幾個節(jié)點的信息。

gossip節(jié)中，每個節(jié)點的信息如下：

ID

ip和port

節(jié)點狀態(tài)

receiver從sender獲得其他節(jié)點信息，這在故障檢測和節(jié)點發(fā)現(xiàn)是非常有用的。

故障檢測

故障檢測用于失敗master或slave不可達，提一個slave為master，如果失敗，那么集群阻止clients的查詢。

每個節(jié)點保存已知節(jié)點的狀態(tài)列表，包括兩種狀態(tài)PFAIL和FAIL，PFAIL意思是可能失敗，不確信。FAIL的意思是，大部分master在固定的時間，確定是失敗的。

PFAIL flag

如果一個節(jié)點在超過NODE_TIMEOUT時間不可到達一個節(jié)點，那么master和slave標志這個節(jié)點為PFAIL。

不可到達的意思是，ping在經(jīng)過NODE_TIMEOUT還沒有回復，因此NODE_TIMEOUT必須大于網(wǎng)絡往返的時間。為了可用性，節(jié)點在超過一半NODE_TIMEOUT后，進行重連，這樣一直保持著連接，不至于誤報故障。

FAIL flag

PFAIL只是一個節(jié)點本地的信息，不足把slave提為master。認為一個節(jié)點down，那么必須是FAIL。

每個節(jié)點發(fā)送的gossip消息都包含一些隨機節(jié)點的狀態(tài)，這樣每個節(jié)點都會收到其他節(jié)點的狀態(tài)，可以標志其他節(jié)點已經(jīng)檢測到的故障。

遇到以下情況，就會由PFAIL過度到FAIL：

一些節(jié)點標識B為PFAIL，并且調(diào)用A，那么A收集其他master對B標識的狀態(tài)，在NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT時間范圍內(nèi)，標識為PFAIL。A將會標識B為FAIL，發(fā)送B的標識FAIL到其他節(jié)點。強制其他節(jié)點標識B為FAIL。

如果要清除FAIL flag，有以下兩種情況：

1）一個節(jié)點為slave并可以到達，那么FAIL flag被清除。

2）一個節(jié)點為master并可以到達，沒有hash slot，可以清除FAIL flag，等待加入集群。

3）一個節(jié)點為master可以到達，但很長一段時間（NODE_TIMEOUT＊ N），沒有檢測到slave可以提為master。

但從PFAIL轉化為FAIL過程中，使用的協(xié)議非常弱：

1）收集其他節(jié)點的意見，因為這一段時間，不可以確定狀態(tài)是穩(wěn)定的。

2）當一個節(jié)點檢測到FAIL條件，強制其他節(jié)點使用FAIL消息，但是不可以確定是否可以到達所有節(jié)點。

然而，Redis的集群故障檢測具有活躍性要求：最終所有節(jié)點即使在分區(qū)都應該同意有關給定節(jié)點的狀態(tài)。一旦分區(qū)愈合，一些少數(shù)節(jié)點認為節(jié)點是在故障狀態(tài)，或相信該節(jié)點是不在故障狀態(tài)。在這兩種情況下，最終給定節(jié)點的狀態(tài)只有一個。

案例1：如果多數(shù)masters標記一個節(jié)點失敗，那么其他節(jié)點最終也標志為失敗。

案例2：只有少數(shù)masters標記一個節(jié)點發(fā)生故障，slave提為master失敗，那么就會清除FAIL flag。

基本上FAIL flag只是為了提slave為master算法的安全執(zhí)行。在理論上slave是獨立運行的，當一個master不可到達時，開始提slave，但實際上，大多master是可以訪問該master的，這樣PFAIL轉化為FAIL就太復雜，這樣FAIL消息就可以強制執(zhí)行，阻止寫操作，其實是由于slave到達不了master引起，不需要slave提為msater。

Cluster epoch

currentEpoch是一個64位無符號整數(shù)，節(jié)點新建立時，設置currentEpoch為0。一個節(jié)點收到一個消息，currentEpoch比本地的大，那么更新本地的currentEpoch。通過這種策略，集群中節(jié)點接受比較大的currentEpoch。在slave升級為master中起重要作用。

config epoch

每一個master，在ping或pong消息中都包含他的configEpoch。當一個新的節(jié)點建立時，master的configEpoch設置為0。

slave選舉時，建立一個新的configEpoch，slave增加Epoch取代失敗的master，得到大部分masters的認證。若slave認證了，建立一個新的configEpoch，slave就變?yōu)閙aster了。configEpoch有助于解決不同節(jié)點分散的配置沖突。

slave在ping或pong消息中都包含他的master的configEpoch，這使得其他實例來檢測一個slave有一個舊的配置需要被更新。每次configEpoch改變都存儲在nodes conf文件。

目前，當一個節(jié)點被重新啟動其currentEpoch被設定為已知的節(jié)點的最大configEpoch 。這是不安全的崩潰恢復系統(tǒng)模型，為了持久保存currentEpoch，系統(tǒng)將會被修改。

slave選舉和推廣

一個slave在滿足以下條件會進行選舉：

1）master處在FAIL狀態(tài)

2）master有服務的hash slot

3）slave和master斷開連接沒有超過給定的時間，為了保證slave上的數(shù)據(jù)有意義

開始選舉前，增加currentEpoch，發(fā)送FAILOVER_AUTH_REQUEST消息，等待回包的最大時間為2倍的NODE_TIMEOUT，一個master回復了FAILOVER_AUTH_ACK，在2倍的NODE_TIMEOUT時間內(nèi)，不再回復相同master的slave選舉。不能保證安全，但是在同一時間可避免多個slave選舉。

slave忽略currentEpoch小于發(fā)送的AUTH_ACK。

如果slave在2倍的NODE_TIMEOUT沒有收到master的回復，那么另一個slave在經(jīng)過4陪的NODE_TIMEOUT后，重新選舉。

選舉不是在master一處于FAIL狀態(tài)就開始的，需要經(jīng)過DELAY，

DELAY = 500 milliseconds + random delay between 0 and 500 milliseconds +SLAVE_RANK * 1000 milliseconds.

DELAY為了使masters知道該master的FAIL狀態(tài)。隨機時間，為了不同的選舉在不同的時間。SLAVE_RANK，最新更新的slave為0，一次上漲。

如果一個slave成為master，那么在ping和pong包中包括服務的hash slot、為currentEpoch的configEpoch。為了快速傳播新的配置，可以廣播pong包。

如果其他節(jié)點檢測到新的master在服務原來的hash slot，那么更新配置，如果舊的master或slave加入，需要從新master復制配置。

master回復slave選舉請求

回復必須滿足以下條件：

1）一個給定的epoch只回復一次，不回復低于lastVoteEpoch的currentEpoch。

2）master處在FAIL狀態(tài)

3）小于master currentEpoch的請求被忽略。例如master currentEpoch為5，lastVoteEpoch為1，slave currentEpoch為3，那么elect currentEpoch為4，不回復。slave重試，currentEpoch為5，那么認為是有效的。

4）在兩倍的NODE_TIMEOUT時間內(nèi)，不回復相同master的slave選舉。

5）master不嘗試選擇最好的slave。

6）master拒絕支持給定的slave，這個請求被簡單忽略。

7）還不太理解

slave選舉中的競態(tài)條件

一個master有A、B、C三個slave，master處在FAIL狀態(tài)，A選舉為master，但是產(chǎn)生了partition，選舉B為master，隨后B處在FAIL狀態(tài)，A也可達了，那么A和C爭當master，但是C的currentEpoch大，那么C就作為master。

服務器slots信息傳播規(guī)則

規(guī)則一：如果一個節(jié)點聲明，沒有hash slots，那么修改hash slots，關聯(lián)到這個節(jié)點。

規(guī)則二：如果一個節(jié)點有hash slots，那么他廣播的configEpoch大于slot擁有者的configEpoch，那么新節(jié)點重構hash slot。

UPDATE消息

例如特定的hash slot在master A和slave B，一段時間A被partition，B作為master，隨后A又可以連接，但是他的配置是舊的，沒有節(jié)點可復制，這樣UPDATE消息就可起作用。當一個節(jié)點檢測到一個廣播的是舊的config，那么他給這個節(jié)點發(fā)送一個UPDATE消息，包含這個hash slot的節(jié)點ID和這個節(jié)點服務的hash slots。

副本遷移算法

觸發(fā)的條件是，一個master沒有slave，選擇好的slave，并且ID最小。

configEpoch沖突解決算法

最小ID節(jié)點的configEpoch加1.

廣播和訂閱

現(xiàn)在這是節(jié)點廣播所有訂閱的消息到其他所有的節(jié)點，后面實現(xiàn)bloomfilter。

http://redis.io/topics/cluster-spec

Redis 集群實現(xiàn)