redis 集群规范

Redis 集群的目标

Redis 集群是 Redis 的一个分布式实现，主要是为了实现以下这些目标（按在设计中的重要性排序）：

在1000个节点的时候仍能表现得很好并且可扩展性（scalability）是线性的。
没有合并操作，这样在 Redis 的数据模型中最典型的大数据值中也能有很好的表现。
写入安全（Write safety）：那些与大多数节点相连的客户端所做的写入操作，系统尝试全部都保存下来。不过公认的，还是会有小部分（small windows?）写入会丢失。
可用性（Availability）：在绝大多数的主节点（master node）是可达的，并且对于每一个不可达的主节点都至少有一个它的从节点（slave）可达的情况下，Redis 集群仍能进行分区（partitions）操作。

这篇文档要讲的是，在 Redis 仓库（放在Github上）中的 unstable 分支中实现的功能。

实现的功能子集

Redis 集群实现了所有在非分布式 Redis 版本中出现的处理单一键值（key）的命令。那些使用多个键值的复杂操作，比如 set 里的并集（unions）和交集（intersections）操作，就没有实现。通常来说，那些处理命令的节点获取不到键值的所有操作都不会被实现。在将来，用户或许可以通过使用 MIGRATE COPY 命令，在集群上用计算节点（Computation Nodes）来执行多键值的只读操作，但 Redis 集群本身不会执行复杂的多键值操作来把键值在节点间移来移去。 Redis 集群不像单机版本的 Redis 那样支持多个数据库，集群只有数据库 0，而且也不支持 SELECT 命令。

Redis 集群协议中的客户端和服务器端

在 Redis 集群中，节点负责存储数据、记录集群的状态（包括键值到正确节点的映射）。集群节点同样能自动发现其他节点，检测出没正常工作的节点，并且在需要的时候在从节点中推选出主节点。

为了执行这些任务，所有的集群节点都通过TCP连接（TCP bus？）和一个二进制协议（集群连接，cluster bus）建立通信。每一个节点都通过集群连接（cluster bus）与集群上的其余每个节点连接起来。节点们使用一个 gossip 协议来传播集群的信息，这样可以：发现新的节点、发送ping包（用来确保所有节点都在正常工作中）、在特定情况发生时发送集群消息。集群连接也用于在集群中发布或订阅消息。

由于集群节点不能代理（proxy）请求，所以客户端在接收到重定向错误（redirections errors） -MOVED 和 -ASK 的时候，将命令重定向到其他节点。理论上来说，客户端是可以自由地向集群中的所有节点发送请求，在需要的时候把请求重定向到其他节点，所以客户端是不需要保存集群状态。不过客户端可以缓存键值和节点之间的映射关系，这样能明显提高命令执行的效率。

安全写入

Redis 集群节点间使用异步冗余备份（asynchronous replication），所以在分区过程中总是存在一些时间段（windows？），在这些时间段里容易丢失写入数据。但是一个连接到绝大部分主节点的客户端的时间段，与一个连接到极小部分主节点的客户端的时间段是相当不同的。 Redis 集群会努力尝试保存所有与大多数主节点连接的客户端执行的写入，但以下两种情况除外： 1) 一个写入操作能到达一个主节点，但当主节点要回复客户端的时候，这个写入有可能没有通过主从节点间的异步冗余备份传播到从节点那里。如果在某个写入操作没有到达从节点的时候主节点已经宕机了，那么该写入会永远地丢失掉，以防主节点长时间不可达而它的一个从节点已经被提升为主节点。 2) 另一个理论上可能会丢失写入操作的模式是：

因为分区使一个主节点变得不可达。
故障转移（fail over）到主节点的一个从节点。（即从节点被提升为主节点）
过一段时间之后主节点再次变得可达。
一个没有更新路由表（routing table）的客户端或许会在集群把这个主节点变成一个从节点（新主节点的从节点）之前对它进行写入操作。

实际上这是极小概率事件，这是因为，那些由于长时间无法被大多数主节点访问到的节点会被故障转移掉，不再接受任何写入操作，当其分区修复好以后仍然会在一小段时间内拒绝写入操作好让其他节点有时间被告知配置信息的变更。通常所有节点都会尝试通过非阻塞连接尝试（non-blocking connection attempt）尽快去访问一个再次加入到集群里的节点，一旦跟该节点建立一个新的连接就会发送一个ping包过去（这足够升级节点配置信息）。这就使得一个节点很难在恢复可写入状态之前没被告知配置信息更改。 Redis 集群在拥有少数主节点和至少一个客户端的分区上容易丢失为数不少的写入操作，这是因为如果主节点被故障转移到集群中多数节点那边的节点上，那么所有发送到这些主节点的写入操作都会永久性丢失。

一个主节点要被故障转移，必须是大多数主节点在至少 NODE_TIMEOUT 这么长时间里无法访问该节点，所以如果分区在这段时间之前修复好了，就没有写入操作会丢失。当分区故障持续超过 NODE_TIMEOUT，集群的多数节点这边会在一超过 NODE_TIMEOUT 这个时间段后开始拒绝往受损分区进行写入，所以在少数节点这边（指分区）变得不再可用后，会有一个写入操作最大损失范围（因为在指定时间段后将不会再有写入操作被接收或丢失）。

可用性

Redis 集群在分区的少数节点那边不可用。集群假设在分区的多数节点这边至少有大多数可达的主节点，并且对于每个不可达主节点都至少有一个从节点可达，在经过了差不多 NODE_TIMEOUT 这么长时间后，有个从节点被推选出来并故障转移掉它的主节点，这时集群又再恢复可用。

这意味着 Redis 集群的设计是能容忍集群中少数节点的出错，但对于要求大量网络分块（large net splits）的可用性的应用来说，这并不是一个合适的解决方案。

举个例子，一个由 N 个主节点组成的集群，每个主节点都只有一个从节点。当有一个节点（因为故障）被分割出去后，集群的多数节点这边仍然是可访问的。当有两个节点（因故障）被分割出去后集群仍可用的概率是 1-(1/(N2-1))（在第一个节点故障出错后总共剩下 N2-1 个节点，那么失去冗余备份（即失去从节点）的那个主节点也故障出错的概率是 1/(N*2-1))）。

比如一个拥有5个节点的集群，每个节点都只有一个从节点，那么在两个节点从多数节点这边分割出去后集群不再可用的概率是 1/(5*2-1) = 0.1111，即有大约 11% 的概率。

表现

在 Redis 集群中节点并不是把命令转发到管理所给出的键值的正确节点上，而是把客户端重定向到服务一定范围内的键值的节点上。最终客户端获得一份最新的集群表示，里面有写着哪些节点服务哪些键值子集，所以在正常操作中客户端是直接联系到对应的节点并把给定的命令发过去。

由于使用了异步冗余备份，节点不会等待其他节点对写入操作的承认。（目前正在开发可选同步冗余备份，极有可能会添加入将来的代码发布中）

同样，由于一些命令不支持操作多个键值，如果不是碎片重整（resharding），那么数据是永远不会在节点间移动的。

所以普通操作是可以被处理得跟在单一 Redis 上一样的。这意味着，在一个拥有 N 个主节点的 Redis 集群中，由于 Redis 的设计是支持线性扩展的，所以你可以认为同样的操作在集群上的表现会跟在单一 Redis 上的表现乘以 N 一样。同时，询问（query）通常在一次循环中被执行，客户端会保持跟节点持续不断的连接，所以延迟数据跟在单一 Reids 上是一样的。

为什么要避免使用合并操作

Redis 集群的设计是避免在多个节点中存在同个键值对的冲突版本，这是因为 Redis 数据模型并不提倡这么做：Redis 中的值通常都是比较大的，经常可以看到列表或者排序好的集合中有数以百万计的元素。数据类型也是语义复杂的。传输和合并这样的值将会变成一个主要的性能瓶颈。

Overview of Redis Cluster main components

键分布模型

键空间被分割为 16384 槽（slot），事实上集群的最大节点数量是 16384 个。（然而建议最大节点数量设置在1000这个数量级上）

所有的主节点都负责 16384 个哈希槽中的一部分。当集群处于稳定状态时，集群中没有在执行重配置（reconfiguration）操作，每个哈希槽都只由一个节点进行处理（不过主节点可以有一个或多个从节点，可以在网络断线或节点失效时替换掉主节点）。

以下是用来把键映射到哈希槽的算法（下一段哈希标签例外就是按照这个规则）：

HASH_SLOT = CRC16(key) mod 16384

其中，CRC16的定义如下：

名称：XMODEM（也可以称为 ZMODEM 或 CRC-16/ACORN）
输出长度：16 bit
多项数（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

CRC16的16位输出中的14位会被使用（这也是为什么上面的式子中有一个对 16384 取余的操作）。在我们的测试中，CRC16能相当好地把不同的键均匀地分配到 16384 个槽中。

注意： 在本文档的附录A中有CRC16算法的实现。

键哈希标签（Keys hash tags）

计算哈希槽可以实现哈希标签（hash tags），但这有一个例外。哈希标签是确保两个键都在同一个哈希槽里的一种方式。将来也许会使用到哈希标签，例如为了在集群稳定的情况下（没有在做碎片重组操作）允许某些多键操作。

为了实现哈希标签，哈希槽是用另一种不同的方式计算的。基本来说，如果一个键包含一个 “{…}” 这样的模式，只有 { 和 } 之间的字符串会被用来做哈希以获取哈希槽。但是由于可能出现多个 { 或 }，计算的算法如下：

如果键包含一个 { 字符。
那么在 { 的右边就会有一个 }。
在 { 和 } 之间会有一个或多个字符，第一个 } 一定是出现在第一个 { 之后。

然后不是直接计算键的哈希，只有在第一个 { 和它右边第一个 } 之间的内容会被用来计算哈希值。

例子：

比如这两个键 {user1000}.following 和 {user1000}.followers 会被哈希到同一个哈希槽里，因为只有 user1000 这个子串会被用来计算哈希值。
对于 foo{}{bar} 这个键，整个键都会被用来计算哈希值，因为第一个出现的 { 和它右边第一个出现的 } 之间没有任何字符。
对于 foozap 这个键，用来计算哈希值的是 {bar 这个子串，因为它是第一个 { 及其右边第一个 } 之间的内容。
对于 foo{bar}{zap} 这个键，用来计算哈希值的是 bar 这个子串，因为算法会在第一次有效或无效（比如中间没有任何字节）地匹配到 { 和 } 的时候停止。
按照这个算法，如果一个键是以 {} 开头的话，那么就当作整个键会被用来计算哈希值。当使用二进制数据做为键名称的时候，这是非常有用的。

下面是用 Ruby 和 C 语言实现的 HASH_SLOT 函数，有加上哈希标签例外。

Ruby 样例代码：

def HASH_SLOT(key)
s = key.index "{"
if s
e = key.index "}",s+1
if e && e != s+1
key = key[s+1..e-1]
end
end
crc16(key) % 16384
end

C 样例代码：

unsigned int HASH_SLOT(char *key, int keylen) {
int s, e; /* start-end indexes of { and } */

/* Search the first occurrence of '{'. */
for (s = 0; s < keylen; s++)
if (key[s] == '{') break;

/* No '{' ? Hash the whole key. This is the base case. */
if (s == keylen) return crc16(key,keylen) & 16383;

/* '{' found? Check if we have the corresponding '}'. */
for (e = s+1; e < keylen; e++)
if (key[e] == '}') break;

/* No '}' or nothing between {} ? Hash the whole key. */
if (e == keylen || e == s+1) return crc16(key,keylen) & 16383;

/* If we are here there is both a { and a } on its right. Hash
* what is in the middle between { and }. */
return crc16(key+s+1,e-s-1) & 16383;
}

集群节点属性

在集群中，每个节点都有一个唯一的名字。节点名字是一个十六进制表示的160 bit 随机数，这个随机数是节点第一次启动时获得的（通常是用 /dev/urandom）。节点会把它的ID保存在配置文件里，以后永远使用这个ID，只要这个节点配置文件没有被系统管理员删除掉。

节点ID是用于在整个集群中标识每个节点。一个给定的节点可以在不改变节点ID的情况下改变 IP 和地址。集群能检测到 IP 或端口的变化，然后使用在集群连接（cluster bus）上的 gossip 协议来发布广播消息，通知配置变更。

每个节点都有其他相关信息是所有节点都知道的：

节点的 IP 地址和 TCP 端口号。
各种标识。
节点使用的哈希槽。
最近一次用集群连接发送 ping 包的时间。
最近一次在回复中收到一个 pong 包的时间。
最近一次标识节点失效的时间。
该节点的从节点个数。
如果该节点是从节点，会有主节点ID信息。（如果它是个主节点则该信息置为0000000…）

使用 CLUSTER NODES 命令可以获得以上的一些信息，这个命令可以发送到集群中的所有节点，无论主节点还是从节点。下面的例子是在一个只有三个节点的小集群中发送 CLUSTER NODES 命令到一个主节点得到的输出。

$ redis-cli cluster nodes
d1861060fe6a534d42d8a19aeb36600e18785e04 myself - 0 1318428930 1 connected 0-1364
3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 2 connected 1365-2729
d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 3 connected 2730-4095

在上面罗列出来的信息中，各个域依次表示的是：节点ID，IP地址：端口号，标识，上一次发送 ping 包的时间，上一次收到 pong 包的时间，连接状态，节点使用的哈希槽。

集群拓扑结构

Redis 集群是一个网状结构，每个节点都通过 TCP 连接跟其他每个节点连接。

在一个有 N 个节点的集群中，每个节点都有 N-1 个流出的 TCP 连接，和 N-1 个流入的连接。这些 TCP 连接会永久保持，并不是按需创建的。

节点握手

节点总是在集群连接端口接受连接，甚至会回复接收到的 ping 包，即使发送 ping 包的节点是不可信的。然而如果某个节点不被认为是在集群中，那么所有它发出的数据包都会被丢弃掉。

只有在两种方式下，一个节点才会认为另一个节点是集群中的一部分：

If a node presents itself with a MEET message. A meet message is exactly like a PING message, but forces the receiver to accept the node as part of the cluster. Nodes will send MEET messages to other nodes only if the system administrator requests this via the following command:
CLUSTER MEET ip port
当一个节点使用 MEET 消息介绍自己。一个 meet 消息跟一个 PING 消息完全一样，但它会强制让接收者接受发送者为集群中的一部分。只有在系统管理员使用以下命令要求的时候，节点才会发送 MEET 消息给其他节点：
一个已被信任的节点能通过传播gossip消息让另一个节点被注册为集群中的一部分。也就是说，如果 A 知道 B，B 知道 C，那么 B 会向 A 发送 C 的gossip消息。A 收到后就会把 C 当作是网络中的一部分，并且尝试连接 C。这意味着，只要我们往任何连接图中加入节点，它们最终会自动形成一个完全连接图。从根本上来说，这表示集群能自动发现其他节点，但前提是有一个由系统管理员强制创建的信任关系。这个机制能防止不同的 Redis 集群因为 IP 地址变更或者其他网络事件而意外混合起来，从而使集群更具健壮性。当节点的网络连接断掉时，它会积极尝试连接所有其他已知节点。

MOVED 重定向

一个 Redis 客户端可以自由地向集群中的任意节点（包括从节点）发送查询。接收的节点会分析查询，如果这个命令是集群可以执行的（就是查询中只涉及一个键），那么节点会找这个键所属的哈希槽对应的节点。

如果刚好这个节点就是对应这个哈希槽，那么这个查询就直接被节点处理掉。否则这个节点会查看它内部的哈希槽 -> 节点ID 映射，然后给客户端返回一个 MOVED 错误。

一个 MOVED 错误如下：

GET x
-MOVED 3999 127.0.0.1:6381

这个错误包括键（3999）的哈希槽和能处理这个查询的节点的 ip：端口号（127.0.0.1:6381）。客户端需要重新发送查询到给定 ip 地址和端口号的节点。注意，即使客户端在重发查询之前等待了很长一段时间，与此同时集群的配置信息发生改变，如果哈希槽 3999 现在是为其他节点服务，那么目标节点会再向客户端回复一个 MOVED 错误。

从集群的角度看，节点是以 ID 来标识的。我们尝试简化接口，所以只向客户端暴露哈希槽和用“ip:端口号”标识的 Redis 节点之间的映射。

虽然并没有要求，但是客户端应该尝试记住哈希槽 3999 是服务于 127.0.0.1:6381。这样的话一旦有一个新的命令需要发送，它能计算出目标键的哈希槽，提高找到正确节点的机率。

注意，当集群是稳定的时候，所有客户端最终都会得到一份哈希槽 -> 节点的映射表，这样能使得集群效率非常高：客户端直接定位目标节点，不用重定向、或代理或发生其他单点故障（single point of failure entities）。

一个客户端也应该能处理本文后面将提到的 -ASK 重定向错误。

集群在线重配置（live reconfiguration）

Redis 集群支持在集群运行过程中添加或移除节点。实际上，添加或移除节点都被抽象为同一个操作，那就是把哈希槽从一个节点移到另一个节点。

向集群添加一个新节点，就是把一个空节点加入到集群中并把某些哈希槽从已存在的节点移到新节点上。
从集群中移除一个节点，就是把该节点上的哈希槽移到其他已存在的节点上。
所以实现这个的核心是能把哈希槽移来移去。从实际角度看，哈希槽就只是一堆键，所以 Redis 集群在重组碎片（reshard）时做的就是把键从一个节点移到另一个节点。

为了理解这是怎么工作的，我们需要介绍 CLUSTER 的子命令，这些命令是用来操作 Redis 集群节点上的哈希槽转换表（slots translation table）。

以下是可用的子命令：

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 节点指派（assign）或移除哈希槽。在哈希槽被指派后，节点会将这个消息通过 gossip 协议向整个集群传播。ADDSLOTS 命令通常是用于在一个集群刚建立的时候快速给所有节点指派哈希槽。

当 SETSLOT 子命令使用 NODE 形式的时候，用来给指定 ID 的节点指派哈希槽。除此之外哈希槽能通过两个特殊的状态来设定，MIGRATING 和 IMPORTING：

当一个槽被设置为 MIGRATING，原来持有该哈希槽的节点仍会接受所有跟这个哈希槽有关的请求，但只有当查询的键还存在原节点时，原节点会处理该请求，否则这个查询会通过一个 -ASK 重定向（-ASK redirection）转发到迁移的目标节点。
当一个槽被设置为 IMPORTING，只有在接受到 ASKING 命令之后节点才会接受所有查询这个哈希槽的请求。如果客户端一直没有发送 ASKING 命令，那么查询都会通过 -MOVED 重定向错误转发到真正处理这个哈希槽的节点那里。

这么讲可能显得有点奇怪，现在我们用实例让它更清晰些。假设我们有两个 Redis 节点，称为 A 和 B。我们想要把哈希槽 8 从节点A 移到节点B，所以我们发送了这样的命令：

我们向节点B 发送：CLUSTER SETSLOT 8 IMPORTING A
我们向节点A 发送：CLUSTER SETSLOT 8 MIGRATING B

其他所有节点在每次被询问到的一个键是属于哈希槽 8 的时候，都会把客户端引向节点”A”。具体如下：

所有关于已存在的键的查询都由节点”A”处理。
所有关于不存在于节点 A 的键都由节点”B”处理。

这种方式让我们可以不用在节点 A 中创建新的键。同时，一个叫做 redis-trib 的特殊客户端，它也是 Redis 集群的配置程序（configuration utility），会确保把已存在的键从节点 A 移到节点 B。这通过以下命令实现：

CLUSTER GETKEYSINSLOT slot count

上面这个命令会返回指定的哈希槽中 count 个键。对于每个返回的键，redis-trib 向节点 A 发送一个 MIGRATE 命令，这样会以原子性的方式（在移动键的过程中两个节点都被锁住，以免出现竞争状况）把指定的键从节点 A 移到节点 B。以下是 MIGRATE 的工作原理：

MIGRATE target_host target_port key target_database id timeout

执行 MIGRATE 命令的节点会连接到目标节点，把序列化后的 key 发送过去，一旦收到 OK 回复就会从它自己的数据集中删除老的 key。所以从一个外部客户端看来，在某个时间点，一个 key 要不就存在于节点 A 中要不就存在于节点 B 中。

在 Redis 集群中，不需要指定一个除了 0 号之外的数据库，但 MIGRATE 命令能用于其他跟 Redis 集群无关的的任务，所以它是一个足够通用的命令。MIGRATE 命令被优化了，使得即使在移动像长列表这样的复杂键仍然能做到快速。不过当在重配置一个拥有很多键且键的数据量都很大的集群的时候，这个过程就并不那么好了，对于使用数据库的应用程序来说就会有延时这个限制。

ASK 重定向

在前面的章节中，我们简短地提到了 ASK 重定向（ASK redirection），为什么我们不能单纯地使用 MOVED 重定向呢？因为当我们使用 MOVED 的时候，意味着我们认为哈希槽永久地被另一个不同的节点处理，并且希望接下来的所有查询都尝试发到这个指定的节点上去。而 ASK 意味着我们只要下一个查询发送到指定节点上去。

这个命令是必要的，因为下一个关于哈希槽 8 的查询需要的键或许还在节点 A 中，所以我们希望客户端尝试在节点 A 中查找，如果需要的话也在节点 B 中查找。由于这是发生在 16384 个槽的其中一个槽，所以对于集群的性能影响是在可接受的范围。

然而我们需要强制客户端的行为，以确保客户端会在尝试 A 中查找后去尝试在 B 中查找。如果客户端在发送查询前发送了 ASKING 命令，那么节点 B 只会接受被设为 IMPORTING 的槽的查询。本质上来说，ASKING 命令在客户端设置了一个一次性标识（one-time flag），强制一个节点可以执行一次关于带有 IMPORTING 状态的槽的查询。

所以从客户端看来，ASK 重定向的完整语义如下：

如果接受到 ASK 重定向，那么把查询的对象调整为指定的节点。
先发送 ASKING 命令，再开始发送查询。
现在不要更新本地客户端的映射表把哈希槽 8 映射到节点 B。

一旦完成了哈希槽 8 的转移，节点 A 会发送一个 MOVED 消息，客户端也许会永久地把哈希槽 8 映射到新的 ip:端口号上。注意，即使客户端出现bug，过早地执行这个映射更新，也是没有问题的，因为它不会在查询前发送 ASKING 命令，节点 B 会用 MOVED 重定向错误把客户端重定向到节点 A 上。

失效检测（Failure detection）

Redis 集群失效检测是用来识别出大多数节点何时无法访问某一个主节点或从节点。当这个事件发生时，就提升一个从节点来做主节点；若如果无法提升从节点来做主节点的话，那么整个集群就置为错误状态并停止接收客户端的查询。

每个节点都有一份跟其他已知节点相关的标识列表。其中有两个标识是用于失效检测，分别是 PFAIL 和 FAIL。PFAIL 表示可能失效（Possible failure），这是一个非公认的（non acknowledged）失效类型。FAIL 表示一个节点已经失效，而且这个情况已经被大多数主节点在某段固定时间内确认过的了。

PFAIL 标识:

当一个节点在超过 NODE_TIMEOUT 时间后仍无法访问某个节点，那么它会用 PFAIL 来标识这个不可达的节点。无论节点类型是什么，主节点和从节点都能标识其他的节点为 PFAIL。

Redis 集群节点的不可达性（non reachability）是指，发送给某个节点的一个活跃的 ping 包（active ping）(一个我们发送后要等待其回复的 ping 包)已经等待了超过 NODE_TIMEOUT 时间，那么我们认为这个节点具有不可达性。为了让这个机制能正常工作，NODE_TIMEOUT 必须比网络往返时间（network round trip time）大。节点为了在普通操作中增加可达性，当在经过一半 NODE_TIMEOUT 时间还没收到目标节点对于 ping 包的回复的时候，就会马上尝试重连接该节点。这个机制能保证连接都保持有效，所以节点间的失效连接通常都不会导致错误的失效报告。

FAIL 标识:

单独一个 PFAIL 标识只是每个节点的一些关于其他节点的本地信息，它不是为了起作用而使用的，也不足够触发从节点的提升。要让一个节点真正被认为失效了，那需要让 PFAIL 状态上升为 FAIL 状态。在本文的节点心跳章节有提到的，每个节点向其他每个节点发送的 gossip 消息中有包含一些随机的已知节点的状态。最终每个节点都能收到一份其他每个节点的节点标识。使用这种方法，每个节点都有一套机制去标记他们检查到的关于其他节点的失效状态。

当下面的条件满足的时候，会使用这个机制来让 PFAIL 状态升级为 FAIL 状态：

某个节点，我们称为节点 A，标记另一个节点 B 为 PFAIL。
节点 A 通过 gossip 字段收集到集群中大部分主节点标识的节点 B 的状态信息。
大部分主节点标记节点 B 为 PFAIL 状态，或者在 NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT 这个时间内是处于 PFAIL 状态。

如果以上所有条件都满足了，那么节点 A 会：

标记节点 B 为 FAIL。
向所有可达节点发送一个 FAIL 消息。

FAIL 消息会强制每个接收到这消息的节点把节点 B 标记为 FAIL 状态。

注意，FAIL 标识基本都是单向的，也就是说，一个节点能从 PFAIL 状态升级到 FAIL 状态，但要清除 FAIL 标识只有以下两种可能方法：

节点已经恢复可达的，并且它是一个从节点。在这种情况下，FAIL 标识可以清除掉，因为从节点并没有被故障转移。
节点已经恢复可达的，而且它是一个主节点，但经过了很长时间（N * NODE_TIMEOUT）后也没有检测到任何从节点被提升了。

PFAIL -> FAIL 的转变使用一种弱协议（agreement）：

1) 节点是在一段时间内收集其他节点的信息，所以即使大多数主节点要去”同意”标记某节点为 FAIL，实际上这只是表明说我们在不同时间里从不同节点收集了信息，得出当前的状态不一定是稳定的结论。 2) 当每个节点检测到 FAIL 节点的时候会强迫集群里的其他节点把各自对该节点的记录更新为 FAIL，但没有一种方式能保证这个消息能到达所有节点。比如有个节点可能检测到了 FAIL 的节点，但是因为分区，这个节点无法到达其他任何一个节点。

然而 Redis 集群的失效检测有一个要求：最终所有节点都应该同意给定节点的状态是 FAIL，哪怕它处于分区。有两种情况是来源于脑裂情况（？），或者是小部分节点相信该节点处于 FAIL 状态，或者是相信节点不处于 FAIL 状态。在这两种情况中，最后集群都会认为给定的节点只有一个状态：

**第 1 种情况: **如果大多数节点都标记了某个节点为 FAIL，由于链条反应，这个主节点最终会被标记为 FAIL。

第 2 种情况: 当只有小部分的主节点标记某个节点为 FAIL 的时候，从节点的提升并不会发生（它是使用一个更正式的算法来保证每个节点最终都会知道节点的提升。），并且每个节点都会根据上面的清除规则（在经过了一段时间 > N * NODE_TIMEOUT 后仍没有从节点提升操作）来清除 FAIL 状态。

本质上来说，FAIL 标识只是用来触发从节点提升（slave promotion）算法的安全部分。理论上一个从节点会在它的主节点不可达的时候独立起作用并且启动从节点提升程序，然后等待主节点来拒绝认可该提升（如果主节点对大部分节点恢复连接）。PFAIL -> FAIL 的状态变化、弱协议、强制在集群的可达部分用最短的时间传播状态变更的 FAIL 消息，这些东西增加的复杂性有实际的好处。由于这种机制，如果集群处于错误状态的时候，所有节点都会在同一时间停止接收写入操作，这从使用 Redis 集群的应用的角度来看是个很好的特性。还有非必要的选举，是从节点在无法访问主节点的时候发起的，若该主节点能被其他大多数主节点访问的话，这个选举会被拒绝掉。

集群阶段（Cluster epoch）

Redis 集群使用一个类似于木筏算法（Raft algorithm）”术语”的概念。在 Redis 集群中这个术语叫做阶段（epoch），它是用来记录事件的版本号，所以当有多个节点提供了冲突的信息的时候，另外的节点就可以通过这个状态来了解哪个是最新的。 currentEpoch 是一个 64bit 的 unsigned 数。

Redis 集群中的每个节点，包括主节点和从节点，都在创建的时候设置了 currentEpoch 为0。

当节点接收到来自其他节点的 ping 包或 pong 包的时候，如果发送者的 epoch（集群连接消息头部的一部分）大于该节点的 epoch，那么更新发送者的 epoch 为 currentEpoch。

由于这个语义，最终所有节点都会支持集群中较大的 epoch。

这个信息在此处是用于，当一个节点的状态发生改变的时候为了执行一些动作寻求其他节点的同意（agreement）。

目前这个只发生在从节点的提升过程，这个将在下一节中详述。本质上说，epoch 是一个集群里的逻辑时钟，并决定一个给定的消息赢了另一个带着更小 epoch 的消息。

配置阶段（Configuration epoch）

每一个主节点总是通过发送 ping 包和 pong 包向别人宣传它的 configEpoch 和一份表示它负责的哈希槽的位图。

当一个新节点被创建的时候，主节点中的 configEpoch 设为零。

从节点由于故障转移事件被提升为主节点时，为了取代它那失效的主节点，会把 configEpoch 设置为它赢得选举的时候的 configEpoch 值。

configEpoch 用于在不同节点提出不同的配置信息的时候（这种情况或许会在分区之后发生）解决冲突，这将在下一节解释。

从节点也会在 ping 包和 pong 包中向别人宣传它的 configEpoch 域，不过从节点的这个域表示的是上一次跟它的主节点交换数据的时候主节点的 configEpoch 值。这能让其他个体检测出从节点的配置信息是不是需要更新了（主节点不会给一个配置信息过时的从节点投票）。

每次由于一些已知节点的值比自己的值大而更新 configEpoch 值，它都会永久性地存储在 nodes.conf 文件中。

当一个节点重启，它的 configEpoch 值被设为所有已知节点中最大的那个 configEpoch 值。

丛节点的选举和提升

从节点的选举和提升都是由从节点处理的，主节点会投票要提升哪个从节点。一个从节点的选举是在主节点被至少一个具有成为主节点必备条件的从节点标记为 FAIL 的状态的时候发生的。

当以下条件满足时，一个从节点可以发起选举：

该从节点的主节点处于 FAIL 状态。
这个主节点负责的哈希槽数目不为零。
从节点和主节点之间的重复连接（replication link）断线不超过一段给定的时间，这是为了确保从节点的数据是可靠的。
一个从节点想要被推选出来，那么第一步应该是提高它的 currentEpoch 计数，并且向主节点们请求投票。

从节点通过广播一个 FAILOVER_AUTH_REQUEST 数据包给集群里的每个主节点来请求选票。然后等待回复（最多等 NODE_TIMEOUT 这么长时间）。一旦一个主节点给这个从节点投票，会回复一个 FAILOVER_AUTH_ACK，并且在 NODE_TIMEOUT * 2 这段时间内不能再给同个主节点的其他从节点投票。在这段时间内它完全不能回复其他授权请求。

从节点会忽视所有带有的时期（epoch）参数比 currentEpoch 小的回应（ACKs），这样能避免把之前的投票的算为当前的合理投票。

一旦某个从节点收到了大多数主节点的回应，那么它就赢得了选举。否则，如果无法在 NODE_TIMEOUT 时间内访问到大多数主节点，那么当前选举会被中断并在 NODE_TIMEOUT * 4 这段时间后由另一个从节点尝试发起选举。

从节点并不是在主节点一进入 FAIL 状态就马上尝试发起选举，而是有一点点延迟，这段延迟是这么计算的：

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

固定延时（fixed delay）确保我们会等到 FAIL 状态在集群内广播后，否则若从节点尝试发起选举，主节点们仍然不知道那个主节点已经 FAIL，就会拒绝投票。

data_age / 10 参数是用来让从节点有时间去获得新鲜数据（在与主节点断线的这一小段时间内）。随机延时（random delay）是用来添加一些不确定因素以减少多个从节点在同一时间发起选举的可能性，因为若同时多个从节点发起选举或许会导致没有任何节点赢得选举，要再次发起另一个选举的话会使集群在当时变得不可用。

一旦有从节点赢得选举，它就会开始用 ping 和 pong 数据包向其他节点宣布自己已经是主节点，并提供它负责的哈希槽，设置 configEpoch 为 currentEpoch（选举开始时生成的）。

为了加速其他节点的重新配置，该节点会广播一个 pong 包给集群里的所有节点（那些现在访问不到的节点最终也会收到一个 ping 包或 pong 包，并且进行重新配置）。

其他节点会检测到有一个新的主节点（带着更大的configEpoch）在负责处理之前一个旧的主节点负责的哈希槽，然后就升级自己的配置信息。旧主节点的从节点，或者是经过故障转移后重新加入集群的该旧主节点，不仅会升级配置信息，还会配置新主节点的备份。

主节点回复从节点的投票请求

在上一节中我们讨论了从节点是如何被选举上的，这一节我们将从主节点的角度解释在为给定从节点投票的时候发生了什么。

主节点接收到来自于从节点、要求以 FAILOVER_AUTH_REQUEST 请求的形式投票的请求。要授予一个投票，必须要满足以下条件：

1) 在一个给定的时段（epoch）里，一个主节点只能投一次票，并且拒绝给以前时段投票：每个主节点都有一个 lastVoteEpoch 域，一旦认证请求数据包（auth request packet）里的 currentEpoch 小于 lastVoteEpoch，那么主节点就会拒绝再次投票。当一个主节点积极响应一个投票请求，那么 lastVoteEpoch 会相应地进行更新。
2) 一个主节点投票给某个从节点当且仅当该从节点的主节点被标记为 FAIL。
3) 如果认证请求里的 currentEpoch 小于主节点里的 currentEpoch 的话，那么该请求会被忽视掉。因此，主节点的回应总是带着和认证请求一致的 currentEpoch。如果同一个从节点在增加 currentEpoch 后再次请求投票，那么保证一个来自于主节点的、旧的延迟回复不会被新一轮选举接受。

下面的例子是没有依据这个规则引发的事件：

主节点的 currentEpoch 是 5， lastVoteEpoch 是 1（在几次失败的选举后这也许会发生的）

从节点的 currentEpoch 是 3。
从节点尝试用 epoch 值为 4（3+1）来赢得选票，主节点回复 ok，里面的 currentEpoch 是 5，可是这个回复延迟了。
从节点尝试用 epoch 值为 5（4+1）来再次赢得选票，收到的是带着 currentEpoch 值为 5 的延迟回复，这个回复会被当作有效的来接收。
4) 主节点若已经为某个失效主节点的一个从节点投票后，在经过 NODE_TIMEOUT * 2 时间之前不会为同个失效主节点的另一个从节点投票。这并不是严格要求的，因为两个从节点用同个 epoch 来赢得选举的可能性很低，不过在实际中，系统确保正常情况当一个从节点被选举上，那么它有足够的时间来通知其他从节点，以避免另一个从节点发起另一个新的选举。
5) 主节点不会用任何方式来尝试选出最好的从节点，只要从节点的主节点处于 FAIL 状态并且投票主节点在这一轮中还没投票，主节点就能进行积极投票。
6) 若一个主节点拒绝为给定从节点投票，它不会给任何负面的回应，只是单纯忽略掉这个投票请求。
7) 主节点不会授予投票给那些 configEpoch 值比主节点哈希槽表里的 configEpoch 更小的从节点。记住，从节点发送了它的主节点的 configEpoch 值，还有它的主节点负责的哈希槽对应的位图。本质上来说，这意味着，请求投票的从节点必须拥有它想要进行故障转移的哈希槽的配置信息，而且信息应该比它请求投票的主节点的配置信息更新或者一致。

从节点选举的竞争情况

这一节解释如何使用 epoch 概念来使得从节点提升过程对分区操作更有抵抗力。

主节点不是无限期地可达。它拥有三个从节点 A，B，C。
从节点 A 赢得了选举并且被推选为主节点。
一个分区操作使得集群中的大多数节点无法访问节点 A。
节点 B 赢得了选举并且被推选为主节点。
一个分区操作使得集群中大多数节点无法访问节点 B。
之前分区操作的问题被修复了，节点 A 又恢复可访问状态。

此刻，节点 B 仍然失效，节点 A 恢复可访问，会与节点 C 竞选去获得选票对节点 B 进行故障转移。

这两个有同样的哈希槽的从节点最终都会请求被提升，然而由于它们发布的 configEpoch 是不一样的，而且节点 C 的 epoch 比较大，所以所有的节点都会把它们的配置更新为节点 C 的。

节点 A 会从来源于节点 C（负责同样哈希槽的节点）的 ping 包中检测出节点 C 的 epoch 是更大的，所以它会重新设置自己为节点 C 的一个从节点。

服务器哈希槽信息的传播规则

Redis 集群很重要的一个部分是用来传播关于集群节点负责哪些哈希槽的信息的机制。这对于新集群的启动和提升从节点来负责处理哈希槽（它那失效的主节点本该处理的槽）的能力来说是必不可少的。

个体持续交流使用的 ping 包和 pong 包都包含着一个头部，这个头部是给发送者使用的，为了向别的节点宣传它负责的哈希槽。这是主要用来传播变更的机制，不过集群管理员手动进行重新配置是例外（比如为了在主节点间移动哈希槽，通过 redis-trib 来进行手动碎片整理）。

当一个新的 Redis 集群节点创建的时候，它的本地哈希槽表（表示给定哈希槽和给定节点 ID 的映射关系表）被初始化，每个哈希槽被置为 nil，也就是，每个哈希槽都是没赋值的。

一个节点要更新它的哈希槽表所要遵守的第一个规则如下：

规则 1：如果一个哈希槽是没有赋值的，然后有个已知节点认领它，那么我就会修改我的哈希槽表，把这个哈希槽和这个节点关联起来。

由于这个规则，当一个新集群被创建的时候，只需要手动给哈希槽赋值上（通常是通过 redis-trib 命令行工具使用 CLUSTER 命令来实现）负责它的主节点，然后这些信息就会迅速在集群中传播开来。

然而，当一个配置更新的发生是因为一个从节点在其主节点失效后被提升为主节点的时候，这个规则显然还不足够。新的主节点会宣传之前它做从节点的时候负责的哈希槽，但从其他节点看来这些哈希槽并没有被重新赋值，所以如果它们只遵守第一个规则的话就不会升级配置信息。

由于这个原因就有第二个规则，是用来把一个已赋值给以前节点的哈希槽重新绑定到一个新的认领它的节点上。规则如下：

规则 2：如果一个哈希槽已经被赋值了，有个节点它的 configEpoch 比哈希槽当前拥有者的值更大，并且该节点宣称正在负责该哈希槽，那么我们会把这个哈希槽重新绑定到这个新节点上。

因为有这第二个规则，所以集群中的所有节点最终都会同意哈希槽的拥有者是所有声称拥有它的节点中 configEpoch 值最大的那个。

UPDATE 消息

上面描述的传播哈希槽配置信息的系统只使用节点间交换信息的普通 ping 包和 pong 包。这要求存在一个节点（可以是负责给定哈希槽的主节点或从节点）拥有更新后的配置信息，因为节点是在 ping 包和 pong 包头部中发送它们自己的配置信息。

然而也存在例外。当有一个节点，它是唯一一个负责处理给定哈希槽的节点，有可能在分区操作后它恢复正常，但拥有的配置信息是过时的。

例子：一个给定的哈希槽是由节点 A 和 B 负责的。节点 A 是一个主节点，然后它在某个时刻失效了，所以节点 B 被提升为主节点。过了一段时间节点 B 也失效了，集群没有其他备份节点可以来处理这个哈希槽，所以只能开始修复操作。

在一段时间过后节点 A 恢复正常了，并且作为一个可写入的主节点重新加入集群，但它的配置信息是过时的。此时没有任何备份节点能更新它的配置信息。这就是 UPDATE 消息存在的目的：当一个节点检测到其他节点在宣传它的哈希槽的时候是用一份过时的配置信息，那么它就会向这个节点发送一个 UPDATE 消息，这个消息包含新节点的 ID 和它负责的哈希槽（以 bitmap 形式发送）。

注意：目前更新配置信息可以用 ping 包/ pong 包，也可以用 UPDATE 消息，这两种方法是共享同一个代码路径（code path）。这两者在更新一个带有老旧信息的节点的配置信息时会有功能上的重复。然而这两种机制都是非常有用的，因为 ping / pong 包在一段时间后能填充（populate）新节点的哈希槽路由表，而 UPDATE 消息只是在一个过时配置信息被检测出来时才被发送出去，并且只覆盖那些需要修复的错误配置信息。

备份迁移

Redis 集群实现了一个叫做备份迁移（replica migration）的概念，以提高系统的可用性。在集群中有主节点-从节点的设定，如果主从节点间的映射关系是固定的，那么久而久之，当发生多个单一节点独立故障的时候，系统可用性会变得很有限。

例如有一个每个主节点都只有一个从节点的集群，当主节点或者从节点故障失效的时候集群能让操作继续执行下去，但如果主从节点都失效的话就没法让操作继续执行下去。然而这样长期会积累很多由硬件或软件问题引起的单一节点独立故障。例如：

主节点 A 有且只有一个从节点 A1。
主节点 A 失效了。A1 被提升为新的主节点。
三个小时后，A1 因为一个独立事件（跟节点 A 的失效无关）失效了。由于没有其他从节点可以提升为主节点（因为节点 A 仍未恢复正常），集群没法继续进行正常操作。

如果主从节点间的映射关系是固定的，那要让集群更有抵抗力地面对上面的情况的唯一方法就是为每个主节点添加从节点。然而这要付出的代价也更昂贵，因为要求 Redis 执行更多的实例、更多的内存等等。

一个候选方案就是在集群中创建不对称性，然后让集群布局时不时地自动变化。例如，假设集群有三个主节点 A，B，C。节点 A 和 B 都各有一个从节点，A1 和 B1。节点 C 有两个从节点：C1 和 C2。

备份迁移是从节点自动重构的过程，为了迁移到一个没有可工作从节点的主节点上。在上面提到的例子中，备份迁移过程如下：

主节点 A 失效。A1 被提升为主节点。
节点 C2 迁移成为节点 A1 的从节点，要不然 A1 就没有任何从节点。
三个小时后节点 A1 也失效了。
节点 C2 被提升为取代 A1 的新主节点。
集群仍然能继续正常工作。

备份迁移算法

迁移算法不用任何形式的协议，因为 Redis 集群中的从节点布局不是集群配置信息（配置信息要求前后一致并且/或者用 config epochs 来标记版本号）的一部分。它使用的是一个避免在主节点没有备份时从节点大批迁移的算法。这个算法保证，一旦集群配置信息稳定下来，最终每个主节点都至少会有一个从节点作为备份。

接下来讲这个算法是如何工作的。在开始之前我们需要定义清楚在这个上下文中什么才算是一个好的从节点：一个好的从节点是指从给定节点的角度看，该从节点不处于 FAIL 状态。

每个从节点若检测出存在至少一个没有好的从节点的单一主节点，那么就会触发这个算法的执行。然而在所有检测出这种情况的从节点中，只有一部分从节点会采取行动。通常这“一部分从节点”都只有一个，除非有不同的从节点在给定时间间隔里对其他节点的失效状态有稍微不同的视角。

采取行动的从节点是属于那些拥有最多从节点的主节点，并且不处于 FAIL 状态及拥有最小的节点 ID。

例如，如果有 10 个主节点，它们各有 1 个从节点，另外还有 2 个主节点，它们各有 5 个从节点。会尝试迁移的从节点是在那 2 个拥有 5 个从节点的主节点中的所有从节点里，节点 ID 最小的那个。已知不需要用到任何协议，在集群配置信息不稳定的情况下，有可能发生一种竞争情况：多个从节点都认为自己是不处于 FAIL 状态并且拥有较小节点 ID（实际上这是一种比较难出现的状况）。如果这种情况发生的话，结果是多个从节点都会迁移到同个主节点下，不过这种结局是无害的。这种竞争发生的话，有时候会使得割让出从节点的主节点变成没有任何备份节点，当集群再次达到稳定状态的时候，本算法会再次执行，然后把从节点迁移回它原来的主节点。

最终每个主节点都会至少有一个从节点作为备份节点。通常表现出来的行为是，一个从节点从一个拥有多个从节点的主节点迁移到一个孤立的主节点。

这个算法能通过一个用户可配置的参数 cluster-migration-barrier 进行控制。这个参数表示的是，一个主节点在拥有多少个好的从节点的时候就要割让一个从节点出来。例如这个参数若被设为 2，那么只有当一个主节点拥有 2 个可工作的从节点时，它的一个从节点会尝试迁移。

发布/订阅（Publish/Subscribe）

在一个 Redis 集群中，客户端能订阅任何一个节点，也能发布消息给任何一个节点。集群会确保发布的消息都会按需进行转发。目前的实现方式是单纯地向所有节点广播所有的发布消息，在将来的实现中会用 bloom filters 或其他算法来优化。

附录

附录 A：CRC16算法的 ANSI C 版本的参考实现

/*
* 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 according 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;
}