詳解redis集群規範知識-php教程-PHP中文網

本文主要介紹了redis群集規範詳解，我們將從最基礎的什麼是redis群集和redis群集的功能來講解，涉及節點失效檢測、群集狀態檢測、從節點選舉等相關內容，比較詳細，需要的朋友可以參考，希望能幫助大家。

引言

這個文檔是正在開發中的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）抵抗力的前提下，盡可能保持數據的一致性。

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

叢集的容錯功能是透過使用主節點（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 個。

建議的最大節點數量為 1000 個左右。

每個主節點負責處理 16384 個雜湊槽的其中一部分。

當我們說一個叢集處於「穩定」（stable）狀態時，指的是叢集沒有在執行重配置（reconfiguration）操作，每個雜湊槽都只由一個節點處理。

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

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

以下是負責將鍵對應到插槽的演算法：

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

登入後複製

最开头的两条命令 ADDSLOTS 和 DELSLOTS 分别用于向节点指派（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 转向错误将命令请求转向至真正负责处理这个槽的节点。

上面关于 MIGRATING 和 IMPORTING 的说明有些难懂，让我们用一个实际的实例来说明一下。

假设现在，我们有 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

登入後複製

上面的命令会让节点返回 count 个 slot 槽中的键，对于命令所返回的每个键， 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 狀態的情況：

至少有一個雜湊槽不可用，因為負責處理這個槽的節點進入了 FAIL 狀態。
叢集中的大部分主節點都進入下線狀態。當大部分主節點都進入 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;
}

登入後複製