Shulou(Shulou.com)06/01 Report--

This article is to share with you about the implementation principle of Cluster partition in Redis, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Abstract

Redis Cluster itself provides the ability to automatically distribute data to different nodes of Redis Cluster. The key issues of partitioning include: how to automatically scatter data to different nodes to make the data stored in different nodes relatively uniform; how to ensure that the client can access the correct nodes and data; and how to ensure that the normal service will not be affected in the process of re-slicing. This article understands the principles of Redis Cluster partition implementation by understanding these problems.

Get to know Redis Cluster

Redis Cluster is a whole composed of multiple Redis instances that serve a data set at the same time. For users, users only focus on this data set, and it is transparent to users that a subset of the whole data set is stored in which node. Redis Cluster not only has the characteristics of a distributed system, but also has the difficulty of how to achieve high availability and data consistency in a distributed system. The Redis Cluster structure composed of multiple Redis instances is usually as follows:

Redis Cluster

Redis Cluster has the following characteristics:

All nodes are connected to each other

The cluster message communication communicates through the cluster bus. The cluster bus port size is the client service port + 10000, and this 10000 is a fixed value.

Nodes communicate with each other through binary protocol

The communication between the client and the cluster node is carried out through the text protocol as usual.

Cluster nodes do not act as agents to query

Redis Cluster Partition implementation principle slot (slot) concept

There is the concept of a 16384-length slot in Redis Cluster, and their numbers are 0, 1, 2, 3... 16382 、 16383 . This slot is a virtual slot and does not really exist. During normal operation, each Master node in the Redis Cluster is responsible for a part of the slot. When a key is mapped to a slot responsible for a Master, then the Master is responsible for providing services for the key. As for which Master node is responsible for which slot, it can be specified by the user or automatically generated during initialization (redis-trib.rb script). It is worth mentioning that in Redis Cluster, only Master owns the slot. If it is the slave of a Master, this slave is only responsible for the use of the slot, but has no ownership. How does Redis Cluster know which slots are responsible for which nodes? How does a certain Master know whether it owns a slot or not?

Bit sequence structure

The Master node maintains a sequence of 16384and8 bytes of bits, and the Master node uses bit to identify whether it owns or not for a slot. For example, for slots numbered 1, Master only needs to determine whether the second bit of the sequence (the index starts at 0) is 1.

Bit sequence

Such as the sequence above, indicates that the current Master has a slot numbered 1134. The cluster also maintains the mapping of slots to cluster nodes, which is implemented by an array of 16384 types of nodes, the slot number is the subscript of the array, and the contents of the array are cluster nodes. in this way, the node responsible for the slot can be quickly found through the slot number. The structure of bit sequence is very exquisite, that is, it does not waste storage space and is easy to operate.

Basic algorithm of bond space distribution

What we're talking about here is how Redis Cluster distributes the key space among different nodes. The key space means the range of keys in all the data sets owned by Redis Cluster, which is called the key space. When it comes to spatial distribution, you will inevitably think of the hashing algorithm. Yes, through the hashing algorithm and modular operation, a value can be permanently mapped to an interval, where the interval is called slots, and the interval is composed of continuous slot. In Redis Cluster, we have 16384 slot, and this number is fixed, and all the keys we store in Redis Cluster are mapped to these slot. Here's how Redis Cluster maps.

The basic key-to-slot mapping algorithm is as follows:

HASH_SLOT = CRC16 (key) mod 16384

This is represented by the code in Redis (this code has been slightly modified and will be restored later):

Crc16 (key) & 0x3FFF

After a simple calculation to get the current key should be stored in which slot, it is worth noting that the specified key will be stored in which slot, this relationship is immutable. If I submit a batch of commands to store a batch of keys in Redis, then these keys will generally be mapped to different slot, and different slot may be served by different nodes in Redis Cluster, which is a little different from what I expected. Is there any way to map these keys to the same slot? The answer is yes.

Principle of key hash label

Key hash tag is an implementation method that allows users to specify that a batch of keys can be stored in the same slot. The only thing a user needs to do is to generate key according to the established rules. This rule goes like this. If I have two pieces of data that have two different meanings for the same user, I just need to set their keys to the following:

Abc {userId} def and ghi {userId} jkl

When calculating the slot number, redis will only get the string between {} to calculate the slot number, so that because the above two different keys, the string in {} is the same, so they can be calculated into the same slot. The related code is as follows:

Unsigned int keyHashSlot (char * key, int keylen) {

Int s, e

For (s = 0; s < keylen; slots +)

If (key [s] ='{') break

If (s = = keylen) return crc16 (key,keylen) & 0x3FFF

For (e = keylen; 1; e < eBay +)

If (key [e] = ='}') break

If (e = = keylen | | e = = keylen 1) return crc16 (key,keylen) & 0x3FFF

Return crc16 (key+s+1,e-s-1) & 0x3FFF

}

How does the client find the right node in Redis Cluster? Let's take a look.

Redirect client

At the beginning of the article, Redis Cluster does not act as a query agent, so what if the client accesses a node where key does not exist? For example, if I want to get the value of key as msg, and the slot number calculated by msg is 254, and the current node is not responsible for the slot number 254, the following information will be returned from the client:

GET msg

-MOVED 254127.0.0.1purl 6381

Indicates that the 254th slot desired by the client is served by a Master instance running on IP 127.0.0.1 and port 6381. If the slot calculated according to key happens to be the responsibility of the current node, the current node returns the result immediately. To make it clear here, a Redis Cluster without a proxy may cause the client to connect to the nodes in the emergency group twice to find the correct service. It is recommended that the client cache the connection, so the worst-case scenario is two round-trip communications.

Re-sharding (Resharding)

Rescheduling means that the mapping relationship from slot to cluster node needs to be changed, and what remains unchanged is the key-to-slot mapping relationship, so when re-slicing, if there is a key in the slot, the key will also be moved to the new node. Let's see how resharding is done, if we have a batch of slots that need to be moved from one Master node to another Master node:

Schematic diagram of slot migration

The model is simplified here, assuming that the slots to be migrated are numbered 1, 2, 3, and that the node on the left is a MasterA node and the node on the right is a MasterB node.

The process of slot migration

There is an unstable state in the process of slot migration, and there will be some rules that define the behavior of the client, so that Redis Cluster can perform slot migration without downtime. The following figure depicts the state of slots numbered 1, 2, and 3 in the MasterA node and Master node during our migration. The state of slots 1, 2, and 3 is MIGRATING in the MasterA node and IMPORTING in the MasterB node.

Slot migration intermediate state

MIGRATING statu

In this example, the MIGRATING state is a slot state that occurs in the MasterA node. When the slot is prepared to migrate, the slot state will first change to the MIGRATING state. What is the actual effect of the slot in this state? When the slot to which a Key is requested by the client is in the state of MIGRATING, the effects are as follows:

If Key exists, it is processed successfully

If Key does not exist, the client ASK is returned. Only if this request is directed to another node, the mapping of the node in the client will not be refreshed, that is, the MasterA node will be selected the next time the client requests the Key.

If Key contains multiple commands, it will be processed successfully if all of them exist. If none of them exist, the client ASK will be returned. If some of them exist, the client TRYAGAIN will be returned, and the client will be informed to retry later. In this way, the client will get ASK when the retry request is completed when all Key are migrated, and then the keys can be obtained after a redirection.

IMPORTING statu

The IMPORTING state in this example is the state of a slot that occurs in the MasterB node. When preparing to migrate the slot from the MasterA node to the MasterB node, the state of the slot will first change to IMPORTING. Slots in IMPORTING state have the following effects on client behavior:

The normal command will be redirected by MOVED, and if it is an ASKING command, the command will be executed, so that Key can not be processed smoothly if the old node has been migrated to the new node

If Key does not exist, create a new

Requests without ASKING are MOVED like normal requests, which ensures that client-side node mapping is off

In the case of a system error, there will be no writing error.

Key space migration

Key space migration means that when the premise of slot migration is satisfied, we can transfer the key space in slot 1, 2, 3 from the MasterA node to the MasterB node through the relevant commands, which can really realize the data transfer. Related commands:

MIGRATE

DUMP

RESTORE

DEL

These are the principles of the implementation of Cluster partition in Redis. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.