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

redis集群實現一個高性能、線性可擴展的1000節點的集群。

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

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

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

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

已實現的子集

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

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

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

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

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

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

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

安全寫

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

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

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

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

一個master因為partition不可到達

其中一個slave獲取master失敗

一會兒后master可以重新到達

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

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

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

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

可用性

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

性能

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

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

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

此外，由于限制多個鍵執行操作命令的子集，如果不rsharding，數據從來不在節點之間移動。

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

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

為什么避免合并操作

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

Keys分配模式

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

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

用來計算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個字節。在我們的測試中，對于16384個slots， CRC16算法最合適。

Keys散列tags

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

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

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

集群節點特性

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

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

每個節點可獲知其他節點的信息包括：

IP 端口

狀態

管理的hash slots

cluster bus最后發送PING的時間

最后接收到PONG的時間

標記節點失敗的時間

從節點數量

如果是slave，那么還包含master節點ID

無論是主節點還是從節點都可以通過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的集群是一個全網狀的，通過TCP，每一個節點都與其他每個節點連接。在N個節點的集群中，每個節點有N-1個對外TCP連接，和N-1的傳入連接。這些TCP連接一直保持著，不需要的時候才創建。

節點握手

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

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

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

CLUSTER MEET ip port

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

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

MOVED重定向

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

一個MOVED error如下：

GET x

-MOVED 3999 127.0.0.1:6381

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

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

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

集群實時重新配置

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

若要將新節點添加到集群中的空節點，即hash slot從現有節點移動到新的節點。

從群集中刪除一個節點，即分配給該節點的hash slot移動到其他現有節點。

因此，實施的核心是圍繞移動hash slot。其實從實用的角度出發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的節點slots。分配后，將使用gossip協議在集群傳播。該ADDSLOTS命令通常用于一個新的集群為所有節點從頭配置slots的一個快速的方式。

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

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

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

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

We send B: CLUSTER SETSLOT 8 IMPORTING A

We send A: CLUSTER SETSLOT 8 MIGRATING B

所有節點都指向A，每次都查詢屬于8的key，會發生：

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的個數，從A遷移到B的每一個key（是原子的）都會顯示，如：

MIGRATE target_host target_port key target_database id timeout

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

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

ASK重定向

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

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

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

對于client，ASK語義如下：

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

2）伴隨ASK，開始查詢

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

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

多key操作

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

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

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

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

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

容錯

節點心跳和gossip消息

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

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

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

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

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

ping和pong消息內容

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

通用的header內容如下：

1）節點ID，在創建節點的時候分配的一個160位的偽隨機數，并在集群中保持不變。

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

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

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

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

6）狀態：發送者的狀態（down或OK）。

7）主節點的ID，如果是slave。

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

gossip節中，每個節點的信息如下：

ID

ip和port

節點狀態

receiver從sender獲得其他節點信息，這在故障檢測和節點發現是非常有用的。

故障檢測

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

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

PFAIL flag

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

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

FAIL flag

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

每個節點發送的gossip消息都包含一些隨機節點的狀態，這樣每個節點都會收到其他節點的狀態，可以標志其他節點已經檢測到的故障。

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

一些節點標識B為PFAIL，并且調用A，那么A收集其他master對B標識的狀態，在NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT時間范圍內，標識為PFAIL。A將會標識B為FAIL，發送B的標識FAIL到其他節點。強制其他節點標識B為FAIL。

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

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

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

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

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

1）收集其他節點的意見，因為這一段時間，不可以確定狀態是穩定的。

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

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

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

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

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

Cluster epoch

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

config epoch

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

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

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

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

slave選舉和推廣

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

1）master處在FAIL狀態

2）master有服務的hash slot

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

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

slave忽略currentEpoch小于發送的AUTH_ACK。

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

選舉不是在master一處于FAIL狀態就開始的，需要經過DELAY，

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

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

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

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

master回復slave選舉請求

回復必須滿足以下條件：

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

2）master處在FAIL狀態

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

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

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

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

7）還不太理解

slave選舉中的競態條件

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

服務器slots信息傳播規則

規則一：如果一個節點聲明，沒有hash slots，那么修改hash slots，關聯到這個節點。

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

UPDATE消息

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

副本遷移算法

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

configEpoch沖突解決算法

最小ID節點的configEpoch加1.

廣播和訂閱

現在這是節點廣播所有訂閱的消息到其他所有的節點，后面實現bloomfilter。

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

Redis 集群實現