Redis 集群規范?

Note

本文檔翻譯自 http://redis.io/topics/cluster-spec

引言?

這個文檔是正在開發中的 Redis 集群功能的規范(specification)文檔, 文檔分為兩個部分:

  • 第一部分介紹目前已經在 unstable 分支中實現了的那些功能。
  • 第二部分介紹目前仍未實現的那些功能。

文檔各個部分的內容可能會隨著集群功能的設計修改而發生改變, 其中, 未實現功能發生修改的幾率比已實現功能發生修改的幾率要高。

這個規范包含了編寫客戶端庫(client library)所需的全部知識, 不過請注意, 這里列出的一部分細節可能會在未來發生變化。

什么是 Redis 集群??

Redis 集群是一個分布式(distributed)、容錯(fault-tolerant)的 Redis 實現, 集群可以使用的功能是普通單機 Redis 所能使用的功能的一個子集(subset)。

Redis 集群中不存在中心(central)節點或者代理(proxy)節點, 集群的其中一個主要設計目標是達到線性可擴展性(linear scalability)。

Redis 集群為了保證一致性(consistency)而犧牲了一部分容錯性: 系統會在保證對網絡斷線(net split)和節點失效(node failure)具有有限(limited)抵抗力的前提下, 盡可能地保持數據的一致性。

Note

集群將節點失效視為網絡斷線的其中一種特殊情況。

集群的容錯功能是通過使用主節點(master)和從節點(slave)兩種角色(role)的節點(node)來實現的:

  • 主節點和從節點使用完全相同的服務器實現, 它們的功能(functionally)也完全一樣, 但從節點通常僅用于替換失效的主節點。
  • 不過, 如果不需要保證“先寫入,后讀取”操作的一致性(read-after-write consistency), 那么可以使用從節點來執行只讀查詢。

Redis 集群實現的功能子集?

Redis 集群實現了單機 Redis 中, 所有處理單個數據庫鍵的命令。

針對多個數據庫鍵的復雜計算操作, 比如集合的并集操作、合集操作沒有被實現, 那些理論上需要使用多個節點的多個數據庫鍵才能完成的命令也沒有被實現。

在將來, 用戶也許可以通過 MIGRATE COPY 命令, 在集群的計算節點(computation node)中執行針對多個數據庫鍵的只讀操作, 但集群本身不會去實現那些需要將多個數據庫鍵在多個節點中移來移去的復雜多鍵命令。

Redis 集群不像單機 Redis 那樣支持多數據庫功能, 集群只使用默認的 0 號數據庫, 并且不能使用 SELECT 命令。

Redis 集群協議中的客戶端和服務器?

Redis 集群中的節點有以下責任:

  • 持有鍵值對數據。
  • 記錄集群的狀態,包括鍵到正確節點的映射(mapping keys to right nodes)。
  • 自動發現其他節點,識別工作不正常的節點,并在有需要時,在從節點中選舉出新的主節點。

為了執行以上列出的任務, 集群中的每個節點都與其他節點建立起了“集群連接(cluster bus)”, 該連接是一個 TCP 連接, 使用二進制協議進行通訊。

節點之間使用 Gossip 協議 來進行以下工作:

  • 傳播(propagate)關于集群的信息,以此來發現新的節點。
  • 向其他節點發送 PING 數據包,以此來檢查目標節點是否正常運作。
  • 在特定事件發生時,發送集群信息。

除此之外, 集群連接還用于在集群中發布或訂閱信息。

因為集群節點不能代理(proxy)命令請求, 所以客戶端應該在節點返回 -MOVED 或者 -ASK 轉向(redirection)錯誤時, 自行將命令請求轉發至其他節點。

因為客戶端可以自由地向集群中的任何一個節點發送命令請求, 并可以在有需要時, 根據轉向錯誤所提供的信息, 將命令轉發至正確的節點, 所以在理論上來說, 客戶端是無須保存集群狀態信息的。

不過, 如果客戶端可以將鍵和節點之間的映射信息保存起來, 可以有效地減少可能出現的轉向次數, 籍此提升命令執行的效率。

鍵分布模型?

Redis 集群的鍵空間被分割為 16384 個槽(slot), 集群的最大節點數量也是 16384 個。

Note

推薦的最大節點數量為 1000 個左右。

每個主節點都負責處理 16384 個哈希槽的其中一部分。

當我們說一個集群處于“穩定”(stable)狀態時, 指的是集群沒有在執行重配置(reconfiguration)操作, 每個哈希槽都只由一個節點進行處理。

Note

重配置指的是將某個/某些槽從一個節點移動到另一個節點。

Note

一個主節點可以有任意多個從節點, 這些從節點用于在主節點發生網絡斷線或者節點失效時, 對主節點進行替換。

以下是負責將鍵映射到槽的算法:

HASH_SLOT = CRC16(key) mod 16384

以下是該算法所使用的參數:

  • 算法的名稱: XMODEM (又稱 ZMODEM 或者 CRC-16/ACORN)
  • 結果的長度: 16 位
  • 多項數(poly): 1021 (也即是 x16 + x12 + x5 + 1)
  • 初始化值: 0000
  • 反射輸入字節(Reflect Input byte): False
  • 發射輸出 CRC (Reflect Output CRC): False
  • 用于 CRC 輸出值的異或常量(Xor constant to output CRC): 0000
  • 該算法對于輸入 "123456789" 的輸出: 31C3

附錄 A 中給出了集群所使用的 CRC16 算法的實現。

CRC16 算法所產生的 16 位輸出中的 14 位會被用到。

在我們的測試中, CRC16 算法可以很好地將各種不同類型的鍵平穩地分布到 16384 個槽里面。

集群節點屬性?

每個節點在集群中都有一個獨一無二的 ID , 該 ID 是一個十六進制表示的 160 位隨機數, 在節點第一次啟動時由 /dev/urandom 生成。

節點會將它的 ID 保存到配置文件, 只要這個配置文件不被刪除, 節點就會一直沿用這個 ID 。

節點 ID 用于標識集群中的每個節點。 一個節點可以改變它的 IP 和端口號, 而不改變節點 ID 。 集群可以自動識別出 IP/端口號的變化, 并將這一信息通過 Gossip 協議廣播給其他節點知道。

以下是每個節點都有的關聯信息, 并且節點會將這些信息發送給其他節點:

  • 節點所使用的 IP 地址和 TCP 端口號。
  • 節點的標志(flags)。
  • 節點負責處理的哈希槽。
  • 節點最近一次使用集群連接發送 PING 數據包(packet)的時間。
  • 節點最近一次在回復中接收到 PONG 數據包的時間。
  • 集群將該節點標記為下線的時間。
  • 該節點的從節點數量。
  • 如果該節點是從節點的話,那么它會記錄主節點的節點 ID 。 如果這是一個主節點的話,那么主節點 ID 這一欄的值為 0000000

以上信息的其中一部分可以通過向集群中的任意節點(主節點或者從節點都可以)發送 CLUSTER NODES 命令來獲得。

以下是一個向集群中的主節點發送 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 connected 2730-4095

在上面列出的三行信息中, 從左到右的各個域分別是: 節點 ID , IP 地址和端口號, 標志(flag), 最后發送 PING 的時間, 最后接收 PONG 的時間, 連接狀態, 節點負責處理的槽。

節點握手(已實現)?

節點總是應答(accept)來自集群連接端口的連接請求, 并對接收到的 PING 數據包進行回復, 即使這個 PING 數據包來自不可信的節點。

然而, 除了 PING 之外, 節點會拒絕其他所有并非來自集群節點的數據包。

要讓一個節點承認另一個節點同屬于一個集群, 只有以下兩種方法:

  • 一個節點可以通過向另一個節點發送 MEET 信息, 來強制讓接收信息的節點承認發送信息的節點為集群中的一份子。 一個節點僅在管理員顯式地向它發送 CLUSTER MEET ip port 命令時, 才會向另一個節點發送 MEET 信息。
  • 另外, 如果一個可信節點向另一個節點傳播第三者節點的信息, 那么接收信息的那個節點也會將第三者節點識別為集群中的一份子。 也即是說, 如果 A 認識 B , B 認識 C , 并且 B 向 A 傳播關于 C 的信息, 那么 A 也會將 C 識別為集群中的一份子, 并嘗試連接 C 。

這意味著如果我們將一個/一些新節點添加到一個集群中, 那么這個/這些新節點最終會和集群中已有的其他所有節點連接起來。

這說明只要管理員使用 CLUSTER MEET 命令顯式地指定了可信關系, 集群就可以自動發現其他節點。

這種節點識別機制通過防止不同的 Redis 集群因為 IP 地址變更或者其他網絡事件的發生而產生意料之外的聯合(mix), 從而使得集群更具健壯性。

當節點的網絡連接斷開時, 它會主動連接其他已知的節點。

MOVED 轉向?

一個 Redis 客戶端可以向集群中的任意節點(包括從節點)發送命令請求。 節點會對命令請求進行分析, 如果該命令是集群可以執行的命令, 那么節點會查找這個命令所要處理的鍵所在的槽。

如果要查找的哈希槽正好就由接收到命令的節點負責處理, 那么節點就直接執行這個命令。

另一方面, 如果所查找的槽不是由該節點處理的話, 節點將查看自身內部所保存的哈希槽到節點 ID 的映射記錄, 并向客戶端回復一個 MOVED 錯誤。

以下是一個 MOVED 錯誤的例子:

GET x

-MOVED 3999 127.0.0.1:6381

錯誤信息包含鍵 x 所屬的哈希槽 3999 , 以及負責處理這個槽的節點的 IP 和端口號 127.0.0.1:6381 。 客戶端需要根據這個 IP 和端口號, 向所屬的節點重新發送一次 GET 命令請求。

注意, 即使客戶端在重新發送 GET 命令之前, 等待了非常久的時間, 以至于集群又再次更改了配置, 使得節點 127.0.0.1:6381 已經不再處理槽 3999 , 那么當客戶端向節點 127.0.0.1:6381 發送 GET 命令的時候, 節點將再次向客戶端返回 MOVED 錯誤, 指示現在負責處理槽 3999 的節點。

雖然我們用 ID 來標識集群中的節點, 但是為了讓客戶端的轉向操作盡可能地簡單, 節點在 MOVED 錯誤中直接返回目標節點的 IP 和端口號, 而不是目標節點的 ID 。

雖然不是必須的, 但一個客戶端應該記錄(memorize)下“槽 3999 由節點 127.0.0.1:6381 負責處理“這一信息, 這樣當再次有命令需要對槽 3999 執行時, 客戶端就可以加快尋找正確節點的速度。

注意, 當集群處于穩定狀態時, 所有客戶端最終都會保存有一個哈希槽至節點的映射記錄(map of hash slots to nodes), 使得集群非常高效: 客戶端可以直接向正確的節點發送命令請求, 無須轉向、代理或者其他任何可能發生單點故障(single point failure)的實體(entiy)。

除了 MOVED 轉向錯誤之外, 一個客戶端還應該可以處理稍后介紹的 ASK 轉向錯誤。

集群在線重配置(live reconfiguration)?

Redis 集群支持在集群運行的過程中添加或者移除節點。

實際上, 節點的添加操作和節點的刪除操作可以抽象成同一個操作, 那就是, 將哈希槽從一個節點移動到另一個節點:

  • 添加一個新節點到集群, 等于將其他已存在節點的槽移動到一個空白的新節點里面。
  • 從集群中移除一個節點, 等于將被移除節點的所有槽移動到集群的其他節點上面去。

因此, 實現 Redis 集群在線重配置的核心就是將槽從一個節點移動到另一個節點的能力。 因為一個哈希槽實際上就是一些鍵的集合, 所以 Redis 集群在重哈希(rehash)時真正要做的, 就是將一些鍵從一個節點移動到另一個節點。

要理解 Redis 集群如何將槽從一個節點移動到另一個節點, 我們需要對 CLUSTER 命令的各個子命令進行介紹, 這些命理負責管理集群節點的槽轉換表(slots translation table)。

以下是 CLUSTER 命令可用的子命令:

  • 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

最開頭的兩條命令 ADDSLOTSDELSLOTS 分別用于向節點指派(assign)或者移除節點, 當槽被指派或者移除之后, 節點會將這一信息通過 Gossip 協議傳播到整個集群。 ADDSLOTS 命令通常在新創建集群時, 作為一種快速地將各個槽指派給各個節點的手段來使用。

CLUSTER SETSLOT slot NODE node 子命令可以將指定的槽 slot 指派給節點 node

至于 CLUSTER SETSLOT slot MIGRATING node 命令和 CLUSTER SETSLOT slot IMPORTING node 命令, 前者用于將給定節點 node 中的槽 slot 遷移出節點, 而后者用于將給定槽 slot 導入到節點 node

  • 當一個槽被設置為 MIGRATING 狀態時, 原來持有這個槽的節點仍然會繼續接受關于這個槽的命令請求, 但只有命令所處理的鍵仍然存在于節點時, 節點才會處理這個命令請求。

    如果命令所使用的鍵不存在與該節點, 那么節點將向客戶端返回一個 -ASK 轉向(redirection)錯誤, 告知客戶端, 要將命令請求發送到槽的遷移目標節點。

  • 當一個槽被設置為 IMPORTING 狀態時, 節點僅在接收到 ASKING 命令之后, 才會接受關于這個槽的命令請求。

    如果客戶端沒有向節點發送 ASKING 命令, 那么節點會使用 -MOVED 轉向錯誤將命令請求轉向至真正負責處理這個槽的節點。

上面關于 MIGRATINGIMPORTING 的說明有些難懂, 讓我們用一個實際的實例來說明一下。

假設現在, 我們有 A 和 B 兩個節點, 并且我們想將槽 8 從節點 A 移動到節點 B , 于是我們:

  • 向節點 B 發送命令 CLUSTER SETSLOT 8 IMPORTING A
  • 向節點 A 發送命令 CLUSTER SETSLOT 8 MIGRATING B

每當客戶端向其他節點發送關于哈希槽 8 的命令請求時, 這些節點都會向客戶端返回指向節點 A 的轉向信息:

  • 如果命令要處理的鍵已經存在于槽 8 里面, 那么這個命令將由節點 A 處理。
  • 如果命令要處理的鍵未存在于槽 8 里面(比如說,要向槽添加一個新的鍵), 那么這個命令由節點 B 處理。

這種機制將使得節點 A 不再創建關于槽 8 的任何新鍵。

與此同時, 一個特殊的客戶端 redis-trib 以及 Redis 集群配置程序(configuration utility)會將節點 A 中槽 8 里面的鍵移動到節點 B 。

鍵的移動操作由以下兩個命令執行:

CLUSTER GETKEYSINSLOT slot count

上面的命令會讓節點返回 countslot 槽中的鍵, 對于命令所返回的每個鍵, redis-trib 都會向節點 A 發送一條 MIGRATE 命令, 該命令會將所指定的鍵原子地(atomic)從節點 A 移動到節點 B (在移動鍵期間,兩個節點都會處于阻塞狀態,以免出現競爭條件)。

以下為 MIGRATE 命令的運作原理:

MIGRATE target_host target_port key target_database id timeout

執行 MIGRATE 命令的節點會連接到 target 節點, 并將序列化后的 key 數據發送給 target , 一旦 target 返回 OK , 節點就將自己的 key 從數據庫中刪除。

從一個外部客戶端的視角來看, 在某個時間點上, 鍵 key 要么存在于節點 A , 要么存在于節點 B , 但不會同時存在于節點 A 和節點 B 。

因為 Redis 集群只使用 0 號數據庫, 所以當 MIGRATE 命令被用于執行集群操作時, target_database 的值總是 0

target_database 參數的存在是為了讓 MIGRATE 命令成為一個通用命令, 從而可以作用于集群以外的其他功能。

我們對 MIGRATE 命令做了優化, 使得它即使在傳輸包含多個元素的列表鍵這樣的復雜數據時, 也可以保持高效。

不過, 盡管 MIGRATE 非常高效, 對一個鍵非常多、并且鍵的數據量非常大的集群來說, 集群重配置還是會占用大量的時間, 可能會導致集群沒辦法適應那些對于響應時間有嚴格要求的應用程序。

ASK 轉向?

在之前介紹 MOVED 轉向的時候, 我們說除了 MOVED 轉向之外, 還有另一種 ASK 轉向。

當節點需要讓一個客戶端長期地(permanently)將針對某個槽的命令請求發送至另一個節點時, 節點向客戶端返回 MOVED 轉向。

另一方面, 當節點需要讓客戶端僅僅在下一個命令請求中轉向至另一個節點時, 節點向客戶端返回 ASK 轉向。

比如說, 在我們上一節列舉的槽 8 的例子中, 因為槽 8 所包含的各個鍵分散在節點 A 和節點 B 中, 所以當客戶端在節點 A 中沒找到某個鍵時, 它應該轉向到節點 B 中去尋找, 但是這種轉向應該僅僅影響一次命令查詢, 而不是讓客戶端每次都直接去查找節點 B : 在節點 A 所持有的屬于槽 8 的鍵沒有全部被遷移到節點 B 之前, 客戶端應該先訪問節點 A , 然后再訪問節點 B 。

因為這種轉向只針對 16384 個槽中的其中一個槽, 所以轉向對集群造成的性能損耗屬于可接受的范圍。

因為上述原因, 如果我們要在查找節點 A 之后, 繼續查找節點 B , 那么客戶端在向節點 B 發送命令請求之前, 應該先發送一個 ASKING 命令, 否則這個針對帶有 IMPORTING 狀態的槽的命令請求將被節點 B 拒絕執行。

接收到客戶端 ASKING 命令的節點將為客戶端設置一個一次性的標志(flag), 使得客戶端可以執行一次針對 IMPORTING 狀態的槽的命令請求。

從客戶端的角度來看, ASK 轉向的完整語義(semantics)如下:

  • 如果客戶端接收到 ASK 轉向, 那么將命令請求的發送對象調整為轉向所指定的節點。
  • 先發送一個 ASKING 命令,然后再發送真正的命令請求。
  • 不必更新客戶端所記錄的槽 8 至節點的映射: 槽 8 應該仍然映射到節點 A , 而不是節點 B 。

一旦節點 A 針對槽 8 的遷移工作完成, 節點 A 在再次收到針對槽 8 的命令請求時, 就會向客戶端返回 MOVED 轉向, 將關于槽 8 的命令請求長期地轉向到節點 B 。

注意, 即使客戶端出現 Bug , 過早地將槽 8 映射到了節點 B 上面, 但只要這個客戶端不發送 ASKING 命令, 客戶端發送命令請求的時候就會遇上 MOVED 錯誤, 并將它轉向回節點 A 。

容錯?

節點失效檢測?

以下是節點失效檢查的實現方法:

  • 當一個節點向另一個節點發送 PING 命令, 但是目標節點未能在給定的時限內返回 PING 命令的回復時, 那么發送命令的節點會將目標節點標記為 PFAIL (possible failure,可能已失效)。

    等待 PING 命令回復的時限稱為“節點超時時限(node timeout)”, 是一個節點選項(node-wise setting)。

  • 每次當節點對其他節點發送 PING 命令的時候, 它都會隨機地廣播三個它所知道的節點的信息, 這些信息里面的其中一項就是說明節點是否已經被標記為 PFAIL 或者 FAIL

  • 當節點接收到其他節點發來的信息時, 它會記下那些被其他節點標記為失效的節點。 這稱為失效報告(failure report)。

  • 如果節點已經將某個節點標記為 PFAIL , 并且根據節點所收到的失效報告顯式, 集群中的大部分其他主節點也認為那個節點進入了失效狀態, 那么節點會將那個失效節點的狀態標記為 FAIL

  • 一旦某個節點被標記為 FAIL , 關于這個節點已失效的信息就會被廣播到整個集群, 所有接收到這條信息的節點都會將失效節點標記為 FAIL

簡單來說, 一個節點要將另一個節點標記為失效, 必須先詢問其他節點的意見, 并且得到大部分主節點的同意才行。

因為過期的失效報告會被移除, 所以主節點要將某個節點標記為 FAIL 的話, 必須以最近接收到的失效報告作為根據。

在以下兩種情況中, 節點的 FAIL 狀態會被移除:

  • 如果被標記為 FAIL 的是從節點, 那么當這個節點重新上線時, FAIL 標記就會被移除。

    保持(retaning)從節點的 FAIL 狀態是沒有意義的, 因為它不處理任何槽, 一個從節點是否處于 FAIL 狀態, 決定了這個從節點在有需要時能否被提升為主節點。

  • 如果一個主節點被打上 FAIL 標記之后, 經過了節點超時時限的四倍時間, 再加上十秒鐘之后, 針對這個主節點的槽的故障轉移操作仍未完成, 并且這個主節點已經重新上線的話, 那么移除對這個節點的 FAIL 標記。

在第二種情況中, 如果故障轉移未能順利完成, 并且主節點重新上線, 那么集群就繼續使用原來的主節點, 從而免去管理員介入的必要。

集群狀態檢測(已部分實現)?

每當集群發生配置變化時(可能是哈希槽更新,也可能是某個節點進入失效狀態), 集群中的每個節點都會對它所知道的節點進行掃描(scan)。

一旦配置處理完畢, 集群會進入以下兩種狀態的其中一種:

  • FAIL : 集群不能正常工作。 當集群中有某個節點進入失效狀態時, 集群不能處理任何命令請求, 對于每個命令請求, 集群節點都返回錯誤回復。
  • OK : 集群可以正常工作, 負責處理全部 16384 個槽的節點中, 沒有一個節點被標記為 FAIL 狀態。

這說明即使集群中只有一部分哈希槽不能正常使用, 整個集群也會停止處理任何命令。

不過節點從出現問題到被標記為 FAIL 狀態的這段時間里, 集群仍然會正常運作, 所以集群在某些時候, 仍然有可能只能處理針對 16384 個槽的其中一個子集的命令請求。

以下是集群進入 FAIL 狀態的兩種情況:

  1. 至少有一個哈希槽不可用,因為負責處理這個槽的節點進入了 FAIL 狀態。
  2. 集群中的大部分主節點都進入下線狀態。當大部分主節點都進入 PFAIL 狀態時,集群也會進入 FAIL 狀態。

第二個檢查是必須的, 因為要將一個節點從 PFAIL 狀態改變為 FAIL 狀態, 必須要有大部分主節點進行投票表決, 但是, 當集群中的大部分主節點都進入失效狀態時, 單憑一個兩個節點是沒有辦法將一個節點標記為 FAIL 狀態的。

因此, 有了第二個檢查條件, 只要集群中的大部分主節點進入了下線狀態, 那么集群就可以在不請求這些主節點的意見下, 將某個節點判斷為 FAIL 狀態, 從而讓整個集群停止處理命令請求。

從節點選舉?

一旦某個主節點進入 FAIL 狀態, 如果這個主節點有一個或多個從節點存在, 那么其中一個從節點會被升級為新的主節點, 而其他從節點則會開始對這個新的主節點進行復制。

新的主節點由已下線主節點屬下的所有從節點中自行選舉產生, 以下是選舉的條件:

  • 這個節點是已下線主節點的從節點。
  • 已下線主節點負責處理的槽數量非空。
  • 從節點的數據被認為是可靠的, 也即是, 主從節點之間的復制連接(replication link)的斷線時長不能超過節點超時時限(node timeout)乘以 REDIS_CLUSTER_SLAVE_VALIDITY_MULT 常量得出的積。

如果一個從節點滿足了以上的所有條件, 那么這個從節點將向集群中的其他主節點發送授權請求, 詢問它們, 是否允許自己(從節點)升級為新的主節點。

如果發送授權請求的從節點滿足以下屬性, 那么主節點將向從節點返回 FAILOVER_AUTH_GRANTED 授權, 同意從節點的升級要求:

  • 發送授權請求的是一個從節點, 并且它所屬的主節點處于 FAIL 狀態。
  • 在已下線主節點的所有從節點中, 這個從節點的節點 ID 在排序中是最小的。
  • 這個從節點處于正常的運行狀態: 它沒有被標記為 FAIL 狀態, 也沒有被標記為 PFAIL 狀態。

一旦某個從節點在給定的時限內得到大部分主節點的授權, 它就會開始執行以下故障轉移操作:

  • 通過 PONG 數據包(packet)告知其他節點, 這個節點現在是主節點了。
  • 通過 PONG 數據包告知其他節點, 這個節點是一個已升級的從節點(promoted slave)。
  • 接管(claiming)所有由已下線主節點負責處理的哈希槽。
  • 顯式地向所有節點廣播一個 PONG 數據包, 加速其他節點識別這個節點的進度, 而不是等待定時的 PING / PONG 數據包。

所有其他節點都會根據新的主節點對配置進行相應的更新,特別地:

  • 所有被新的主節點接管的槽會被更新。
  • 已下線主節點的所有從節點會察覺到 PROMOTED 標志, 并開始對新的主節點進行復制。
  • 如果已下線的主節點重新回到上線狀態, 那么它會察覺到 PROMOTED 標志, 并將自身調整為現任主節點的從節點。

在集群的生命周期中, 如果一個帶有 PROMOTED 標識的主節點因為某些原因轉變成了從節點, 那么該節點將丟失它所帶有的 PROMOTED 標識。

發布/訂閱(已實現,但仍然需要改善)?

在一個 Redis 集群中, 客戶端可以訂閱任意一個節點, 也可以向任意一個節點發送信息, 節點會對客戶端所發送的信息進行轉發。

在目前的實現中, 節點會將接收到的信息廣播至集群中的其他所有節點, 在將來的實現中, 可能會使用 bloom filter 或者其他算法來優化這一操作。

附錄 A: CRC16 算法的 ANSI 實現參考?

/*
 * Copyright 2001-2010 Georges Menie (www.menie.org)
 * Copyright 2010 Salvatore Sanfilippo (adapted to Redis coding style)
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the University of California, Berkeley nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/* CRC16 implementation acording to CCITT standards.
 *
 * Note by @antirez: this is actually the XMODEM CRC 16 algorithm, using the
 * following parameters:
 *
 * Name                       : "XMODEM", also known as "ZMODEM", "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
 */

static const uint16_t crc16tab[256]= {
    0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
    0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
    0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,
    0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,
    0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,
    0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,
    0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4,
    0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,
    0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,
    0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b,
    0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,
    0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,
    0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,
    0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49,
    0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,
    0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,
    0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f,
    0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067,
    0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,
    0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,
    0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d,
    0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,
    0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,
    0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,
    0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab,
    0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,
    0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,
    0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92,
    0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9,
    0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,
    0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,
    0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0
};

uint16_t crc16(const char *buf, int len) {
    int counter;
    uint16_t crc = 0;
    for (counter = 0; counter < len; counter++)
            crc = (crc<<8) ^ crc16tab[((crc>>8) ^ *buf++)&0x00FF];
    return crc;
}

討論 ?

comments powered by Disqus
四川快乐12开奖时间