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

redis集群實(shí)現(xiàn)一個(gè)高性能、線性可擴(kuò)展的1000節(jié)點(diǎn)的集群。

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

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

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

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

已實(shí)現(xiàn)的子集

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

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

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

客戶端與服務(wù)端在Redis集群版中的約定

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

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

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

安全寫

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

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

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

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

一個(gè)master因?yàn)閜artition不可到達(dá)

其中一個(gè)slave獲取master失敗

一會(huì)兒后master可以重新到達(dá)

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

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

Redis cluster會(huì)丟失很多寫操作，當(dāng)一個(gè)或多個(gè)客戶端連接到一個(gè)少master分區(qū)時(shí)。因?yàn)槿绻@些master不可以到達(dá)多master的分區(qū)，這些寫操作就會(huì)丟失。

如果在NODE_TIMEOUT前不可到達(dá)，不會(huì)丟消息，如果在NODE_TIMEOUT后，會(huì)有消息丟失。（暫時(shí)不理解為啥不丟消息）。

可用性

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

性能

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

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

因?yàn)槭褂卯惒綇?fù)制的，節(jié)點(diǎn)不等待寫入的其他節(jié)點(diǎn)的確認(rèn)。

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

所以在單個(gè)Redis的實(shí)例下，正常操作處理可以完成的，在N個(gè)主節(jié)點(diǎn)Redis的集群，可以期望以單一的Redis實(shí)例相同的性能乘以N作為設(shè)計(jì)的線性擴(kuò)展。在同一時(shí)間，通常在單次往返執(zhí)行查詢，因?yàn)榭蛻敉ǔ１３峙c節(jié)點(diǎn)持久連接，以便和單個(gè)獨(dú)立的Redis節(jié)點(diǎn)延遲性也是一樣的。

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

為什么避免合并操作

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

Keys分配模式

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

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

用來計(jì)算key屬于哪個(gè)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

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

Keys散列tags

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

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

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

集群節(jié)點(diǎn)特性

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

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

每個(gè)節(jié)點(diǎn)可獲知其他節(jié)點(diǎn)的信息包括：

IP 端口

狀態(tài)

管理的hash slots

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

最后接收到PONG的時(shí)間

標(biāo)記節(jié)點(diǎn)失敗的時(shí)間

從節(jié)點(diǎn)數(shù)量

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

無論是主節(jié)點(diǎn)還是從節(jié)點(diǎn)都可以通過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

集群拓?fù)浣Y(jié)構(gòu)

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

節(jié)點(diǎn)握手

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

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

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

CLUSTER MEET ip port

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

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

MOVED重定向

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

一個(gè)MOVED error如下：

GET x

-MOVED 3999 127.0.0.1:6381

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

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

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

集群實(shí)時(shí)重新配置

Redis的集群支持在群集運(yùn)行時(shí)添加和刪除節(jié)點(diǎn)。實(shí)際上添加或刪除一個(gè)節(jié)點(diǎn)被抽象成相同的操作，即移動(dòng)hash slot從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

We send B: CLUSTER SETSLOT 8 IMPORTING A

We send A: CLUSTER SETSLOT 8 MIGRATING B

所有節(jié)點(diǎn)都指向A，每次都查詢屬于8的key，會(huì)發(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的個(gè)數(shù)，從A遷移到B的每一個(gè)key（是原子的）都會(huì)顯示，如：

MIGRATE target_host target_port key target_database id timeout

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

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

ASK重定向

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

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

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

對于client，ASK語義如下：

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

2）伴隨ASK，開始查詢

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

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

多key操作

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

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

當(dāng)hash slot正在從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)，由于人工resharding，多健操作不可用。

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

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

容錯(cuò)

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

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

但是每個(gè)節(jié)點(diǎn)可確保ping通，ping或pong不超過一半NODE_TIMEOUT。前NODE_TIMEOUT已過，節(jié)點(diǎn)也嘗試重新與另一個(gè)節(jié)點(diǎn)的TCP鏈接，節(jié)點(diǎn)不相信因?yàn)楫?dāng)前TCP鏈接，是不可達(dá)的。

信息的交換量大于O（N） ，NODE_TIMEOUT設(shè)置為一個(gè)小的數(shù)字，但節(jié)點(diǎn)的數(shù)量（N）是非常大的，因?yàn)槊總€(gè)節(jié)點(diǎn)將嘗試ping ，如果配置信息在NODE_TIMEOUT一半的時(shí)間沒有更新。

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

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

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

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

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

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

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

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

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

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

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

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

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

gossip節(jié)中，每個(gè)節(jié)點(diǎn)的信息如下：

ID

ip和port

節(jié)點(diǎn)狀態(tài)

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

故障檢測

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

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

PFAIL flag

如果一個(gè)節(jié)點(diǎn)在超過NODE_TIMEOUT時(shí)間不可到達(dá)一個(gè)節(jié)點(diǎn)，那么master和slave標(biāo)志這個(gè)節(jié)點(diǎn)為PFAIL。

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

FAIL flag

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

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

遇到以下情況，就會(huì)由PFAIL過度到FAIL：

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

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

1）一個(gè)節(jié)點(diǎn)為slave并可以到達(dá)，那么FAIL flag被清除。

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

3）一個(gè)節(jié)點(diǎn)為master可以到達(dá)，但很長一段時(shí)間（NODE_TIMEOUT＊ N），沒有檢測到slave可以提為master。

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

1）收集其他節(jié)點(diǎn)的意見，因?yàn)檫@一段時(shí)間，不可以確定狀態(tài)是穩(wěn)定的。

2）當(dāng)一個(gè)節(jié)點(diǎn)檢測到FAIL條件，強(qiáng)制其他節(jié)點(diǎn)使用FAIL消息，但是不可以確定是否可以到達(dá)所有節(jié)點(diǎn)。

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

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

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

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

Cluster epoch

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

config epoch

每一個(gè)master，在ping或pong消息中都包含他的configEpoch。當(dāng)一個(gè)新的節(jié)點(diǎn)建立時(shí)，master的configEpoch設(shè)置為0。

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

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

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

slave選舉和推廣

一個(gè)slave在滿足以下條件會(huì)進(jìn)行選舉：

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

2）master有服務(wù)的hash slot

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

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

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

如果slave在2倍的NODE_TIMEOUT沒有收到master的回復(fù)，那么另一個(gè)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)。隨機(jī)時(shí)間，為了不同的選舉在不同的時(shí)間。SLAVE_RANK，最新更新的slave為0，一次上漲。

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

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

master回復(fù)slave選舉請求

回復(fù)必須滿足以下條件：

1）一個(gè)給定的epoch只回復(fù)一次，不回復(fù)低于lastVoteEpoch的currentEpoch。

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

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

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

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

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

7）還不太理解

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

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

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

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

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

UPDATE消息

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

副本遷移算法

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

configEpoch沖突解決算法

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

廣播和訂閱

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

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

Redis 集群實(shí)現(xiàn)