Detailed explanation of redis cluster specification knowledge-PHP Tutorial-php.cn

This article mainly introduces the detailed explanation of redis cluster specifications. We will explain from the most basic what is redis cluster and the functions of redis cluster, involving node failure detection, cluster status detection, slave node election and other related contents. It is more detailed and needs Friends can refer to it, I hope it can help everyone.

Introduction

This document is a specification document for the Redis cluster function under development. The document is divided into two parts:

The first part introduces those functions that have been implemented in the unstable branch.
The second part introduces those features that are not yet implemented.

The content of each part of the document may change as the design of the cluster function is modified. Among them, the probability of modification of unimplemented functions is higher than that of implemented functions.

This specification contains all the knowledge needed to write a client library, but please note that some of the details listed here may change in the future.

What is Redis cluster?

Redis cluster is a distributed, fault-tolerant Redis implementation. The functions that can be used by the cluster are a subset of the functions that can be used by ordinary stand-alone Redis. (subset).

There is no central node or proxy node in the Redis cluster. One of the main design goals of the cluster is to achieve linear scalability.

Redis cluster sacrifices some fault tolerance in order to ensure consistency: the system will ensure limited resistance to network disconnection (net split) and node failure (node failure) Maintain data consistency as much as possible under the premise of strength.

The cluster treats node failure as one of the special cases of network disconnection.

The fault tolerance function of the cluster is achieved by using nodes with two roles: master node (master) and slave node (slave):

The master node and the slave node use exactly the same server implementation, and their functions are exactly the same, but the slave node is usually only used to replace the failed master node.
However, if you do not need to ensure the consistency of the "write first, read later" operation (read-after-write consistency), you can use the slave node to execute read-only queries.

Redis cluster implements a subset of functions

Redis cluster implements all commands that process a single database key in stand-alone Redis.

Complex calculation operations for multiple database keys, such as union operations and collection operations of sets, are not implemented. Those commands that theoretically require the use of multiple database keys from multiple nodes are also not implemented. Not implemented.

In the future, users may be able to use the MIGRATE COPY command to perform read-only operations on multiple database keys in the cluster's computation node, but the cluster itself will not implement those needs. Complex multi-key commands that move multiple database keys around multiple nodes.

Redis cluster does not support multiple database functions like stand-alone Redis. The cluster only uses the default database No. 0, and the SELECT command cannot be used.

Clients and servers in the Redis cluster protocol

Nodes in the Redis cluster have the following responsibilities:

Holding key-value pairs data.
Record the status of the cluster, including mapping keys to right nodes.
Automatically discover other nodes, identify nodes that are not working properly, and elect a new master node from the slave nodes when necessary.

In order to perform the tasks listed above, each node in the cluster establishes a "cluster bus" with other nodes. This connection is a TCP connection using the binary protocol. communication.

The Gossip protocol is used between nodes to perform the following work:

Propagate (propagate) information about the cluster to discover new nodes.
Send PING packets to other nodes to check whether the target node is functioning normally.
Send cluster information when a specific event occurs.

In addition, cluster connections are also used to publish or subscribe to information in the cluster.

Because cluster nodes cannot proxy command requests, the client should forward the command request to other nodes by itself when the node returns a -MOVED or -ASK redirection error.

Because the client is free to send command requests to any node in the cluster, and when necessary, can forward the command to the correct node based on the information provided by the steering error, so In theory, the client does not need to save cluster status information.

However, if the client can save the mapping information between keys and nodes, it can effectively reduce the number of possible redirections, thereby improving the efficiency of command execution.

Key distribution model

The key space of the Redis cluster is divided into 16384 slots, and the maximum number of nodes in the cluster is also 16384.

The recommended maximum number of nodes is about 1,000.

Each masternode is responsible for processing a portion of the 16384 hash slots.

When we say that a cluster is in a "stable" state, we mean that the cluster is not performing reconfiguration operations and each hash slot is processed by only one node. .

Reconfiguration refers to moving certain/certain slots from one node to another.

A master node can have any number of slave nodes. These slave nodes are used to replace the master node when the master node is disconnected or the node fails.

The following is the algorithm responsible for mapping keys to slots:

HASH_SLOT = CRC16(key) mod 16384

Copy after login

The following is Parameters used by this algorithm:

Name of the algorithm: XMODEM (also known as ZMODEM or CRC-16/ACORN)
Length of the result: 16 bits
Poly : 1021 (that is, x16 + x12 + x5 + 1)
Initialization value: 0000
Reflect Input byte: False
Reflect Output CRC: False
Xor constant to output CRC: 0000
The output of this algorithm for the input "123456789": 31C3

The cluster information is given in Appendix A Implementation of the CRC16 algorithm used.

14 of the 16-bit output produced by the CRC16 algorithm are used.
In our tests, the CRC16 algorithm can smoothly distribute various types of keys into 16384 slots.

Cluster node attributes

Each node has a unique ID in the cluster. The ID is a 160-bit random number represented in hexadecimal. Generated from /dev/urandom when the node is first started.

The node will save its ID to the configuration file. As long as the configuration file is not deleted, the node will always use this ID.

The node ID is used to identify each node in the cluster. A node can change its IP and port number without changing the node ID. The cluster can automatically identify changes in IP/port numbers and broadcast this information to other nodes through the Gossip protocol.

The following is the associated information that each node has, and the node will send this information to other nodes:

The IP address and TCP port number used by the node .
Node flags (flags).
The hash slot that the node is responsible for processing.
The last time a node sent a PING packet using a cluster connection.
The last time the node received a PONG packet in a reply.
The time when the cluster marks the node as offline.
The number of slave nodes of this node.
If the node is a slave node, it will record the node ID of the master node. If this is a master node, the value in the Master Node ID column is 0000000.

Part of the above information can be obtained by sending the CLUSTER NODES command to any node in the cluster (either the master node or the slave node).

The following is an example of sending the CLUSTER NODES command to the master node in a cluster. The cluster consists of three 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

Copy after login

In the three lines of information listed above, the fields from left to right are: node ID, IP address and port number, flag, the last time to send PING, the last time to receive PONG, connection status , the slot that the node is responsible for processing.

Node handshake (implemented)

The node always accepts the connection request from the cluster connection port and replies to the received PING packet. Even if this PING packet comes from an untrusted node.

However, except for PING, the node will reject all other packets that do not come from the cluster node.

To allow a node to recognize that another node belongs to the same cluster, there are only two methods:

A node can send a MEET message to another node. Force the node receiving the message to recognize the node sending the message as a member of the cluster. A node will send MEET information to another node only if the administrator explicitly sends it the CLUSTER MEET ip port command.
In addition, if a trusted node disseminates the information of a third-party node to another node, the node receiving the information will also identify the third-party node as a member of the cluster. That is, if A knows B, B knows C, and B spreads information about C to A, then A will also recognize C as a member of the cluster and try to connect to C.

This means that if we add a new node/nodes to a cluster, then this/these new nodes will eventually be connected to all other nodes already in the cluster.

This means that as long as the administrator explicitly specifies the trust relationship using the CLUSTER MEET command, the cluster can automatically discover other nodes.

This node identification mechanism makes the cluster more robust by preventing unexpected combinations (mixes) of different Redis clusters due to IP address changes or other network events.

When a node's network connection is disconnected, it will actively connect to other known nodes.

MOVED Turn

一个 Redis 客户端可以向集群中的任意节点（包括从节点）发送命令请求。节点会对命令请求进行分析，如果该命令是集群可以执行的命令，那么节点会查找这个命令所要处理的键所在的槽。

如果要查找的哈希槽正好就由接收到命令的节点负责处理，那么节点就直接执行这个命令。
另一方面，如果所查找的槽不是由该节点处理的话，节点将查看自身内部所保存的哈希槽到节点 ID 的映射记录，并向客户

端回复一个 MOVED 错误。

以下是一个 MOVED 错误的例子：

GET x
-MOVED 3999 127.0.0.1:6381

Copy after login

错误信息包含键 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

Copy after login

最开头的两条命令 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

Copy after login

上面的命令会让节点返回 count 个 slot 槽中的键，对于命令所返回的每个键， redis-trib 都会向节点 A 发送一条 MIGRATE 命令，该命令会将所指定的键原子地（atomic）从节点 A 移动到节点 B （在移动键期间，两个节点都会处于阻塞状态，以免出现竞争条件）。

以下为 MIGRATE 命令的运作原理：

MIGRATE target_host target_port key target_database id timeout

Copy after login

执行 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 。

Note that even if a bug occurs on the client and slot 8 is mapped to node B prematurely, as long as the client does not send the ASKING command, the client will encounter a MOVED error when sending a command request and will Turn back to node A.

Fault tolerance

Node failure detection

The following is the implementation method of node failure detection:

When When a node sends a PING command to another node, but the target node fails to return a reply to the PING command within a given time limit, the node sending the command will mark the target node as PFAIL (possible failure).
The time limit for waiting for the PING command reply is called "node timeout" and is a node option (node-wise setting).
Every time a node sends a PING command to other nodes, it will randomly broadcast three pieces of information about the nodes it knows. One of the pieces of information is whether the node has been marked as PFAIL or FAIL.
When a node receives information from other nodes, it will record those nodes marked as failed by other nodes. This is called a failure report.
If a node has marked a node as PFAIL, and based on the failure report received by the node, most other master nodes in the cluster also believe that the node has entered a failed state, then the node will delete the failed node. The status is marked FAIL.
Once a node is marked as FAIL, the information about the node's failure will be broadcast to the entire cluster, and all nodes that receive this information will mark the failed node as FAIL.

Simply put, if a node wants to mark another node as invalid, it must first ask other nodes for their opinions and obtain the consent of the majority of master nodes.

Because expired failure reports will be removed, if the master node wants to mark a node as FAIL, it must be based on the most recently received failure report.

In the following two situations, the FAIL status of the node will be removed:

If the node marked as FAIL is a slave node, then when the node comes back online , the FAIL mark will be removed.
It is meaningless to maintain (retaning) the FAIL state of the slave node, because it does not handle any slots. Whether a slave node is in the FAIL state determines whether the slave node can be promoted to the master node when needed.
If after a master node is marked as FAIL, four times the node timeout period, plus ten seconds, the failover operation for the master node's slot has not been completed, and the master node has If it comes back online, remove the FAIL mark on this node.

In the second case, if the failover fails to complete successfully and the master node comes back online, the cluster will continue to use the original master node, thus eliminating the need for administrator intervention.

Cluster status detection (partially implemented)

Whenever a configuration change occurs in the cluster (it may be a hash slot update, or a node may enter a failed state ), each node in the cluster will scan the nodes it knows.

Once the configuration is processed, the cluster will enter one of the following two states:

FAIL: The cluster cannot work properly. When a node in the cluster enters a failed state, the cluster cannot process any command requests. For each command request, the cluster node returns an error reply.
OK: The cluster can work normally, and none of the nodes responsible for processing all 16384 slots are marked as FAIL.

This means that even if only a part of the hash slots in the cluster cannot be used properly, the entire cluster will stop processing any commands.

However, the cluster will still operate normally during the period from when a node has a problem to being marked as FAIL, so at some point, the cluster may still be able to handle only 16384 slots. A subset of the command requests.

The following are two situations in which the cluster enters the FAIL state:

At least one hash slot is unavailable because the node responsible for processing this slot entered the FAIL state.
Most of the master nodes in the cluster have gone offline. When most master nodes enter the PFAIL state, the cluster will also enter the FAIL state.

The second check is necessary because to change a node from PFAIL state to FAIL state, a majority of master nodes must vote. However, when most master nodes in the cluster When the nodes all enter the failure state, there is no way to mark a node as FAIL state by just one or two nodes.

Therefore, with the second check condition, as long as most of the master nodes in the cluster enter the offline state, the cluster can change a certain master node without requesting the opinions of these master nodes. The node is judged to be in FAIL status, causing the entire cluster to stop processing command requests.

Slave node election

一旦某个主节点进入 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;
}

Copy after login