Redis集群實現原理探討

Redis集群是一個distribute、fault-tolerant的Redis實現，主要設計目標是達到線性可擴展性、可用性、數據一致性。

線性拓展官方推薦最大的節點數量為1000，由於Cluster架構中無Proxy層，Master與Slave之間使用非同步replication。

數據一致性客戶端容忍一定程度的數據丟失，集群儘可能保存Client write操作的數據，保證數據一致性。

可用性Redis集群通過partition來提供一定程度的可用性，當集群中的一部分節點失效或者無法進行通訊時，集群仍可以繼續提供服務。這裡有兩點補充:

只要集群中大多數Master可達、且失效的Master至少有一個Slave可達，即集群非Fail狀態，集群都是可用的，如下圖：

Redis集群的replicas migration機制可以將擁有多個Slave的Master的某個Slave，遷移到沒有Slave的Master下，即Slave分布相對平衡，確保Master都有一定數量的Slave備份。

Redis集群設計

總體架構

集群節點屬性集群中每個Master node負責存儲數據、集群狀態，包括slots與nodes對應關係。Master nodes能夠自動發現其他nodes，檢測failure節點，當某個Master節點失效時，集群能將核實的Slave提升為Master。下圖是節點的關聯信息，節點定時會將這些信息發送給其他節點：

1fc2412b7429e4ab5d8704fcd39520815ea2727b 10.9.42.37:6103 master - 0 1494082584680 9 connected 10923-13652 08e70bb3edd7d3cabda7a2ab220f2f3610db38cd 10.9.33.204:6202 slave ad1334bd09ee73fdeb7b8f16194550fc2bf3a038 0 1494082586686 8 connected edaafc250f616e9e12c5182f0322445ea9a89085 10.9.33.204:6203 slave 1fc2412b7429e4ab5d8704fcd39520815ea2727b 0 1494082586184 9 connected 06cd6f24caf98a1c1df0862eadac2b05254f909d 10.9.33.204:6201 slave d458c22ccced2f29358b6e6814a206d08285374e 0 1494082584179 7 connected 3892b7fb410a4d6339364dbdda2ebc666ffee843 10.9.42.37:6203 slave 73f7d44c03ada58bf5adaeb340359e2c043ecfa0 0 1494082582679 12 connected 73f7d44c03ada58bf5adaeb340359e2c043ecfa0 10.9.33.204:6103 master - 0 1494082585181 3 connected 13653-16383 4004a64211bea5050a8f46b8436564d40380cd60 10.9.33.204:6101 master - 0 1494082583678 1 connected 2731-5460 d458c22ccced2f29358b6e6814a206d08285374e 10.9.42.37:6101 master - 0 1494082588189 7 connected 0-2730 f8868d59c0f3d935d3dbe35601506039520f7107 10.9.42.37:6201 slave 4004a64211bea5050a8f46b8436564d40380cd60 0 1494082587187 10 connected 45ba0d6fc3d48a43ff72e10bcc17d2d8b2592cdf 10.9.33.204:6102 master - 0 1494082583179 2 connected 8192-10922 007d7e17bfd26a3c1e21992bb5b656a92eb65686 10.9.42.37:6202 slave 45ba0d6fc3d48a43ff72e10bcc17d2d8b2592cdf 0 1494082588189 11 connected ad1334bd09ee73fdeb7b8f16194550fc2bf3a038 10.9.42.37:6102 myself,master - 0 0 8 connected 5461-8191

從左至右分別是：節點ID、IP地址和埠，節點角色標誌、最後發送ping時間、最後接收到pong時間、連接狀態、節點負責處理的hash slot。集群可以自動識別出ip/port的變化，並通過Gossip（最終一致性，分布式服務數據同步演算法）協議廣播給其他節點知道。Gossip也稱「病毒感染演算法」、「謠言傳播演算法」（附錄一）。

Keys分布模型集群的鍵空間被分割為16384個slots（即hash槽），slot是數據映射的基本單位，即集群的最大節點數量是16384（官方推薦最大節點數量為1000個左右）。集群中的每個Master節點負責處理16384個hash槽其中的一部分，當集群處於「stable」狀態時（無slots在節點間遷移），任意一個hash slot只會被單個node所服務。以下是鍵映射到hash槽的演算法：

HASH_SLOT = CRC16(key) mod 16384

Redis集群是在多個Redis節點之間進行數據共享，它不支持「multi-key」操作（即執行的命令需要在多個Redis節點之間移動數據，比如Set類型的並集、交集等（除非這些key屬於同一個node），即Cluster不能進行跨Nodes操作。如下：

10.9.42.37:6102> smembers set1 -> Redirected to slot [3037] located at 10.9.33.204:6101 1) "d" 2) "b" 3) "g" 4) "c" 5) "a" 6) "f" 7) "e" (1.08s) 10.9.33.204:6101> smembers set2 -> Redirected to slot [15294] located at 10.9.33.204:6103 1) "b" 2) "c" 3) "f" 4) "g" 5) "h" 6) "i" 7) "a" 10.9.33.204:6103> sunion set1 set2 (error) CROSSSLOT Keys in request don t hash to the same slot

Redis為了兼容multi-key操作，提供了「hash tags」操作，每個key可以包含自定義的「tags」，在存儲的時候根據tags計算此key應該映射到哪個node上。通過「hash tags」可以強制某些keys被保存到同一個節點上，便於進行「multi key」操作。基本上如果關鍵字包含「{...}」，那麼在之間的字元串被hash，然而可能有多個匹配的該演算法由以下規則規定：如果key包含｛，在｛的右邊有一個｝，並在第一次出現｛與第一次出現｝之間有一個或者多個字元串，那麼就作為key進行hash。例如，.following和.followed就在同一個hash slot；foo{}整個字元被hash，foo{},,bar被hash。如下所示：

10.9.33.204:6103> set .following 1000 10.9.33.204:6101> set .followed 1000 10.9.33.204:6101> keys * 4) .following 6) .followed

特殊說明一點，在resharding期間，原來同一個slot的keys被遷移到不同的node中，multi-key操作可能不可用。

數據一致性保證Redis集群儘可能保證數據的強一致性，但在特定條件下會丟失數據，原因有兩點：非同步replication機制以及network partition。

Master以及對應的Slaves之間使用非同步的機制，在節點failover後，新的Master將會最終替代其他的replicas：

write命令提交到Master，Master執行完畢後向Client返回「OK」，但由於一部分replication，此時數據還沒傳播給Slave；如果此時Master不可達的時間超過閥值，此時集群將觸發對應的slave選舉為新的Master，此時沒有replication同步到slave的數據將丟失。

在network partition時，總有一個窗口期（node timeout）可能會導致數據丟失：

由於網路分區，此時master不可達，且Client與Master處於一個分區，且此時集群處於「OK」。此時Failover機制，將其中一個Slave提升為新的Master，等待網路分區消除後，老的Master再次可達，此時節點被切換為Slave，而在這段期間，處於網路分區期間，Client仍然將write提交到老的Master，因為該Master被認為是仍然有效的。當老的Master再次加入集群，被切換成Slave後，這些數據將永遠丟失。

集群可用性上述談到多次集群狀態的概念，那集群什麼時候處於「OK」，什麼時候處於「FAIL」，節點什麼時候可用等，詳見下面的解釋：當NODE_TIMEOUT時，觸發failover，此時集群仍然可用的前提是：「大分區」（相對發生網路分區的Client-Master小分區端而言）端必須持有大部份Masters，且每個不可達的Master至少有一個Slave也在「大分區」端，且集群在小部分Nodes失效後仍然可以恢復有效性。舉個例子：

集群有N個Master，且每個Master都有一個Slave，那麼集群的可用性只能容忍一個Master節點被分區隔離，也就是說只有一個Master處於小分區端，當第二個Master節點被分區隔離之前扔保持可用性的概率為1-(1 /(N*2-1))，這裡的意思是：當第一個節點失效後，剩餘N*2-1節點，此時沒有Slave的Master失效的概率為1 /(N*2-1)。比如有10個節點，每個Master有一個Slave，當2個nodes被隔離或失效後，集群可用性的概率是：1/(10*2-1)=5.26%，此時集群不再可用。

為了避免上述情況發生，Redis Cluster提供了「replicas migration」機制，當Master節點發生failover後，集群會動態重新分配、平衡Slaves的分布，有效地提高了集群的可用性。

從節點選舉邏輯

節點是已下線Master對應的Slave

FAIL狀態的Master負責的hash slot 非空

主從節點之間的replication link斷線的時長不能超過

Nodes handshakeNodes通過埠發送Ping、Pong，除了Ping之外，節點會拒絕其他所有非本集群節點的packets，一個節點註冊成為集群的新成員有2中方法：

通過「Cluster meet」指令引入，即將指定的node加入集群，集群將認為指定的node為「可信任」。

當其他nodes通過gossip引入了新的nodes，這些nodes也是被認為是「可信任的」。即：如果A信任B，B信任C，且B向A傳播關於C的信息，那麼A也信任C，並嘗試連接C。

重定向與resharding

MOVED重定向Client可以將請求發給任意一個Node，包含Slaves，Node解析命令，檢查語法，multiple keys是否在同一個slot。如果當前node持有該slot，那麼命令直接執行並返回，否則當前Node向Client返回「MOVED」錯誤。

905指test8對應的slot，10.9.42.37:6101指slot所在的Node的ip:port，Client根據返回信息，重定向至指定的Node。若此過程中集群發生變更（配置調整、failover、resharding等），原來返回到Client可能已失真，重新發送命令時，可能會再次發生MOVED錯誤。

Redis集群提供集群模式的客戶端，在跳轉時會自動進行節點轉向，以下是常用的：

Shell終端：redis-cli -c -h 10.9.33.204 -p 6101，集群提示重定向至Key所在的Slot:

Java：JedisCluster，需要配置集群信息，其他API如Jedis差異不大

private static String configLocation = "classpath*:config-spring.xml"; private static ApplicationContext ctx = new ClassPathXmlApplicationContext(configLocation); private void testCluster() { JedisCluster jedisCluster = ctx.getBean("jedisClusterRaw", JedisCluster.class); String v = jedisCluster.get("test6"); System.out.println("v:" + v); }

ASK重定向ASK重定向與MOVED重定向非常相似，兩者最大的區別在於在resharding期間，當前的Client發送的命令暫時與指定的Node交互，在遷移期間，slot原來的keys仍有可能在原來的節點上，所以Client的命令仍然先經過原來的節點，對於不存的節點，再到新的節點進行嘗試獲取，一旦完成slot的遷移，原來slot接收到Client命令請求，則節點向客戶端返回MOVED轉向。對比ASK重定向，MOVED重定向指hash slots已經永久地被另一個node接管，後續Client的命令都是與該Node交互。ASK是Redis集群非阻塞的表現，即Redis集群不會因slot resharding而導致整個集群不可用。

容錯

節點失效檢測跟大部份分布式框架一樣，Redis Cluster節點間通過持續的心跳來保持信息同步，不過Redis Cluster節點信息同步是內部實現的，不依賴第三方組件，如zk。集群中的nodes持續交換ping、pong數據，消息協議使用Gossip，這兩種packet數據結構一樣，它們之間通過type欄位區分。

節點定時向其他節點發送ping命令，它會隨機選擇存儲的其他集群節點的其中三個進行信息「廣播」，例如廣播的信息包含一項是節點是否被標記為PFAIL/FAIL。PFAIL表示「可能已失效」，是尚未完全確認的失效狀態（即可能是某個節點或少數Master認為其不可達）；FAIL表示Node被集群大多數的Masters認定為失效（即大多數Master已認定為不可達，且不可達的時間已經超過配置的NODE_TIMEOUT）。

當節點收到其他節點廣播的信息，它會記錄被其他節點標記為失效的節點。舉個例子，如果節點被某個節點標記為PFAIL，集群中大部份其他主節點也認為該節點進入了失效狀態，那麼該節點的狀態會被標誌為FAIL。當節點被標誌為FAIL，這個節點已失效的信息會被廣播至整個集群，所有集群中的節點都會將失效的節點標誌為FAIL。

集群失效檢測當某個Master或者Slave不能被大多數Nodes可達時，用於故障遷移並將合適Slave提升為Master。當Slave提升未能成功，集群不能正常工作。即集群不能處理Client的命令的請求，當Client發出命令請求時，集群節點都將返回錯誤內容的respone。

集群正常工作時，負責處理16384個slots的節點中，全部節點均正常。反之，若集群中有一部分hash slot不能正常使用，集群亦將停止工作，即集群進入了FAIL狀態。對於集群進入FAIL狀態，會有以下兩種情況：

至少有一個hash slot不可用。

集群中大部份Master都進入了PFAIL狀態。

上述為Redis集群原理概述，下面我們對比一下其他的Redis集群方案。

Redis集群方案對比

客戶端分片

邏輯都是可控的，不依賴第三方分布式中間件

靜態的數據分片，需要增加或減少Redis實例的數量，需要手工調整分片的程序

運維成本高，拓展需要手工操作

跨系統、平台維護相同的分片邏輯成本高，例如一個終端是PHP、另一個終端是JAVA，需要實現兩套不同的分片邏輯

Twemproxy

Redis客戶端把請求發送到Twemproxy，路由規則發送到正確的Redis實例

LVS集群：實現twemproxy的負載均衡，提高proxy的可用性和擴容能力，使得twemproxy對應用透明

Sentinel集群：檢測Redis主從的存活狀態，當redis master失效，把slave提升為新的master

支持無效Redis實例的自動刪除

減少客戶端與Redis實例的連接數

但由於需要依賴組件較多和Redis請求都需要經過代理，在這過程中會造成性能損失，Twemproxy單節點的吞吐量對比Redis單實例，吞吐量要低不少，另外Twemproxy無法支持平滑支持Redis節點。

Codis

支持平滑增加/減少Reids實例

Codis Proxy：客戶端連接的Redis代理服務

Codis Manager：Codis的管理工具

Codis Redis：維護Redis分支，基於2.8.13開發

Zookeeper：存放數據路由表和codis-proxy節點的元信息

附幾張CodisManager的使用截圖：

概覽Dashboard

Slots分布

Slot遷移操作

當然Codis也有自身的一些缺陷，例如主從同步需要用戶自身實現。

Redis Cluster

Redis集群根據上述說明，可以了解到，框架是採用P2P的模式，完全去中心化，數據存儲模塊和分布式的邏輯模塊耦合在一起。這樣帶來的好處是部署非常簡單，一體式部署，相對Codis而言，沒有太多的其他概念、組件和依賴。但缺點也是比較明顯，譬如分布式邏輯出現bug，只能回滾重啟整個集群。

同時，我們通過上述可以了解到，Redis集群對協議進行了較大的修改，對客戶端的交互升級不少，見上述「MOVED重定向」的客戶端實現。由於歷史原因，歷史的應用均使用傳統的Redis API，若業務更換Redis Client，存在不少問題，例如升級工作、數據遷移及測試，所以業內暫未被大規模使用。

總結

綜上所述，回答了以下問題：

Redis集群為了解決什麼問題而存在的？解決線性可擴展性。

Redis集群誕生以前怎麼解決這個問題？客戶端分片、代理協助分片(Twemproxy)、查詢路由、預分片、一致性哈希、客戶端代理/轉發等。

Redis集群採用什麼方式保證線性可擴展性、可用性、數據一致性？Hash槽、查詢路由、節點互聯的混合模式。

Redis集群化面臨的問題是什麼？Redis集群本身要解決的是可伸縮問題，同時數據一致、集群可用等一系列問題。前者涉及到了節點的哈希槽的分配(含重分配)，節點的增刪，主從關係指定與變更(含自動遷移)這些具體的交互過程；後者則是故障發現，故障轉移，選舉過程等詳細的過程。

Redis集群實現的核心思想和思路是什麼？通過消息的交互（Gossip）實現去中心化(指的是集群自身的實現，不是指數據)，通過Hash槽分配，實現集群線性可拓展。

寫在最後

以上是在研究/使用Redis集群過程中的一點思考與總結，好記性不如爛筆頭，多多積累，以開闊思路，更好解決工作中遇到的問題。

參考資料

附錄一

Gossip協議Gossip也稱「病毒感染演算法」、「謠言傳播演算法」，Redis集群節點間使用Gossip協議交互。以下是Gossip演算法的描述：

在總數為n+1的人群中，被感染的人數初始化為1，並向周圍傳播。（一個節點狀態發生變化，並向鄰近節點發送更新信息）

在每個周期內總有未被感染的人轉變為被感染的人，方式為每個被感染的人隨機感染b個人。（對於節點狀態變化的信息隨機發送給b個節點，下圖b值為2，Redis Cluster中默認值為3）

經過足夠的時間，所有人都會被感染。（隨著時間推移，信息能夠傳遞到所有節點）

對於Redis Cluster而言，node首先需要知道集群中至少一個seed node，此node向seed發送ping請求，接收到seed節點pong返回自身節點已知的所有nodes列表，然後與node解析返回的nodes列表並與之建立連接，同時也會向每個nodes發送ping，並從pong結果中merge出全局的nodes列表，並與之逐步建立連接。另數據傳輸的方式也是類似，如上述gossip協議。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！