The last article “consistent hash algorithm in distributed data cache” article describes the basic principle and implementation of consistent hash algorithm, today to Redis Cluster as an example, in detail to explain the distributed data cache data sharding, online and offline data migration and request redirection and other operations.

Introduction to the Redis cluster

Redis Cluster is a distributed solution of Redis, which is officially launched in version 3.0 and effectively solves the requirements of Redis distributed.

A Redis Cluster consists of at least six nodes, including three active nodes and three slave nodes, to ensure a complete high availability Cluster. The three master nodes allocate slots to handle client command requests, while the slave nodes can be used to replace the master node if it fails.

As shown in the figure above, this cluster contains 6 Redis nodes, 3 primary and 3 secondary, respectively M1, M2, M3, S1, S2 and S3. In addition to data replication between master and slave Redis nodes, all Redis nodes communicate with each other using the Gossip protocol to exchange maintenance node metadata information.

In general, the primary Redis node handles reads and writes for Clients, while the secondary node handles only reads.

Data Sharding strategy

The most important aspect of distributed data storage is data Sharding, also known as Sharding.

In order to make the cluster can expand horizontally, the primary problem to be solved is how to allocate the whole data set to multiple nodes according to certain rules. The commonly used data sharding methods are: range sharding, hash sharding, consistent hash algorithm, hash slot and so on.

Range sharding assumes that the data set is ordered, and it can support the traversal operation well by putting the data in the same order together. The disadvantage of range sharding is that there are hot spots when facing sequential writes. For example, log writes, the order of logs is time dependent, and time is monotonically increasing. Therefore, the hot spot of writing is always in the last fragment.

For relational databases, the scope sharding strategy is generally used because of frequent table or index scans.

Hash sharding and consistent hashing were covered in the previous article, but those interested should check out “Consistent Hashing algorithms in Distributed Data Caching.” Let’s focus on Redis’s virtual hash slot strategy.

Redis Cluster uses virtual hash slot partitioning. All keys are mapped to integer slots 0 to 16383 based on the hash function. Slot = CRC16(key) & 16383. Each node is responsible for maintaining a portion of slots and the key data mapped to the slots.

Redis virtual slot partitioning features:

  • Decoupling the relationship between data and nodes simplifies node expansion and contraction.
  • The node maintains slot mapping, and does not require the client or proxy service to maintain slot partition metadata
  • Supports query of mappings between nodes, slots, and keys for data routing and online cluster scaling.

The Redis cluster provides flexible node expansion and contraction solutions. If external cluster services are not affected, you can add nodes to the cluster for capacity expansion or go offline for capacity reduction. A slot is the basic unit of Redis cluster management data, and cluster scaling is the movement of slots and data between nodes.

Let’s take a look at the principle of Redis cluster scaling. Then learn how to ensure that the cluster is available during Redis node data migration or during fault recovery.

Increase the cluster

In order to make readers better understand the capacity expansion operation when the nodes go online, we simulate the whole process by Redis Cluster command.

When a new Redis node runs and joins the existing cluster, we need to migrate slots and data for it. You need to specify a slot migration plan for new nodes to ensure that each node is responsible for a similar number of slots after the migration to ensure that data on these nodes is evenly distributed.

  1. Start a Redis node, named M4.
  2. Use the cluster meet command to add a new Redis node to the cluster. The new node is the master node at the beginning. Since there is no responsible slot, it cannot accept any read and write operation. Subsequently, we will migrate slots and fill data for it.
  3. Send cluster setslot {slot} {sourceNodeId} to the M4 nodes to prepare the data for importing the slot.
  4. Migrating {targetNodeId} Can be performed on the M1, M2, or M3 nodes by sending cluster setslot {slot} migrating {targetNodeId}.
  5. Run cluster getKeysinslot {slot} {count} to obtain count keys belonging to slot {slot} on the source node, and perform Step 6 to migrate key data.
  6. Migrate {targetNodeIp} “” 0 {timeout} keys {key… } command to migrate the obtained keys to target nodes in batches through pipeline mechanism. The migrate command is provided in Redis 3.0.6 and above.
  7. Repeat Step 5 and Step 6 until all key data in the slot is migrated to the target node.
  8. Send the cluster setslot {slot} node {targetNodeId} command to all primary nodes in the cluster to inform them of slot allocation to the target node. To ensure that slot node mapping changes are propagated in a timely manner, new nodes need to be executed by traversing the slots that are sent to all primary nodes to update the migrated nodes.

Contraction of the cluster

To shrink the node is to take the Redis node offline. The whole process needs the following operation process.

  1. Check whether the offline node has a responsible slot. If yes, migrate the slot to another node to ensure the integrity of slot node mapping after the offline node.
  2. When the offline node is no longer in charge of the slot or is itself a subordinate node, other nodes in the cluster can be notified to forget the offline node. When all nodes forget to change nodes, they can be shut down normally.

A node that goes offline needs to migrate its own slot to another node. The procedure is the same as the procedure for migrating slots for node expansion.

After the slot migration is complete, all nodes in the cluster need to be notified of the node that forgot to go offline. That is, other nodes need to stop exchanging Gossip messages with the node that is going offline.

Redis Cluster use the cluster forget {downNodeId} command to add a specified node to the forbidden list. Nodes in the forbidden list will not send Gossip messages.

Client routing

In cluster mode, when the Redis node receives any key-related command, it first calculates the slot corresponding to the key, and then finds the corresponding node according to the slot. If the node is itself, the key command is processed. Otherwise reply MOVED redirection error notifying client to request the correct node. This process is called MOVED redirection.

*** Note that Redis does not simply calculate the contents of the key value. When the contents of the key value include braces, it only calculates the contents of the parentheses. *** For example, if the key is user:{10000}:books, only 10000 will be computed.

MOVED The following is an example of an error: the hash slot 3999 that key X belongs to, and the IP address and port number of the node responsible for handling the slot 127.0.0.1:6381. The client needs to send a GET command request to the node based on the IP address and port number.

GET X-Moved 3999 127.0.0.1:6381Copy the code

Since request redirection adds IO overhead, this is not an efficient way to use a Redis cluster, but a Smart cluster client. The Smart client maintains the slot-to-Redis node mapping internally so that key-to-node lookups can be performed locally to maximize I/O efficiency. The MOVED redirection assists the client in updating the mapping.

The Redis cluster supports online slot and data migration to achieve horizontal scaling. When data corresponding to slots is migrated from the source node to the target node, clients need to perform intelligent migration to ensure that key commands can be executed properly. For example, when slot data is migrated from a source node to a target node, part of the data may be on the source node and part of the data on the target node.

Therefore, the client command execution process is as follows:

  • The client sends commands to the source node based on the local slot cache, and executes them if there is a key mapping and returns the result to the client.
  • If the node returns a MOVED error, update the mapping between the local slot and the Redis node, and re-initiate the request.
  • If data is being migrated, the node responds with an ASK redirection exception. (error) ASK {slot} {targetIP} : {targetPort}
  • The client extracts the target node information from the ASK redirection exception, sends the asking command to the target node to open the client connection identifier, and then executes the key command.

ASK and MOVED are both redirected control of the client, but they are fundamentally different. ASK redirection indicates that the cluster is migrating slot data, and the client cannot know when the migration is complete. Therefore, the redirection is only temporary, and the client does not update the cache mapped from slot to Redis node. But the MOVED redirection means that the slot corresponding to the key has been explicitly assigned to the new node, so the slot mapping cache to the Redis node needs to be updated.

failover

When a small number of nodes in the Redis cluster fail, automatic failover ensures that the cluster can provide services normally.

When a Redis node goes offline objectively, the Redis cluster will select one of its nodes to replace it through primary selection to ensure the high availability of the cluster. This is not the core content of this article, interested students can learn on their own.

There is, however, a caveat. By default, the entire cluster is unavailable when any of the 16384 slots in the cluster are not assigned to a node. Execute any key command to return the CLUSTERDOWN Hash Slot not served command. When the primary node that holds the slot goes offline, the whole cluster is unavailable during the period from fault discovery to automatic completion, which is unacceptable for most services. Therefore, it is recommended to set parameter cluster-require-full-coverage to no. When the primary node fails, only the commands related to the slot are affected. The availability of other primary nodes is not affected.

reference

  • Redis Development and Operation
  • Juejin. Cn/post / 684490…
  • Phachon.com/redis/redis…
  • Kdf5000.com/2017/04/17/…