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

This article introduces why RedisCluster is designed into 16384 slots, the content is very detailed, interested friends can use for reference, I hope it can be helpful to you.

Dear students, have you ever used Redis clusters? So what is the principle of Redis clustering? Remember the following two sentences:

Redis Sentinal focuses on high availability and automatically promotes slave to master in case of master downtime and continues to provide services.

Redis Cluster focuses on scalability and uses Cluster for sharding storage when a single redis runs out of memory.

I. data slicing strategy

The most important point in the distributed data storage scheme is data fragmentation, which is called Sharding. In order to make the cluster scale horizontally, the first problem to be solved is how to allocate the whole data set to multiple nodes according to certain rules. The commonly used data slicing methods are: range slicing, hash slicing, consistent hash algorithm and virtual hash slot.

Range slicing assumes that the dataset is ordered, and putting the adjacent data together can well support traversal operations. The disadvantage of range slicing is that there are hot spots in the face of sequential writing. For example, for log type writes, the order of logs is generally related to time, and time is monotonously increasing, so the hot spot of writing is always in the last shard. For relational databases, because table scans or index scans are often needed, range sharding strategies are basically used.

In order to distribute different key to different redis nodes, the usual practice is to get the hash value of key, and then calculate the module according to the number of nodes, but this approach has its obvious disadvantages. When we need to add or decrease a node, it will cause a large number of key to miss, this proportion is quite high, so someone put forward the concept of consistent hash.

There are four important characteristics of consistent hashing:

Balance: some people define it as balance, which means that the hash results can be distributed to all nodes as much as possible, so that the resources on each node can be used effectively.

Monotonicity: when the number of nodes changes, the result of the hash should protect as much as possible that the allocated content will not be reassigned to the new node.

Dispersion and load: these two actually mean the same thing, which requires that the consistent hash algorithm should avoid repetition of key hashes as much as possible.

Second, the slicing mechanism of Redis

However: instead of using consistent hash, Redis clusters introduce the concept of hash slots.

Redis Cluster uses virtual hash slot partition, and all keys are mapped to 0-16383 integer slots according to the hash function. Each key uses the 16384 module after CRC16 verification to decide which slot to place (Slot). Each node is responsible for maintaining part of the slot and the key value data mapped by the slot.

Calculation formula: slot = CRC16 (key) & 16383.

This structure is easy to add or delete nodes, and whether you add, delete or modify a node, it will not cause the cluster to be unavailable. The advantage of using hash slots is that nodes can be easily added or removed.

When you need to add nodes, you only need to move some of the hash slots of other nodes to the new nodes.

When you need to remove a node, you just need to move the hash slot on the removed node to another node.

3. Characteristics of Redis virtual slot partition.

Decoupling the relationship between data and nodes simplifies the difficulty of node expansion and contraction.

The node itself maintains the mapping relationship of the slot, which does not require the client or agent service to maintain the slot partition metadata

Support mapping query between nodes, slots and keys for data routing, online cluster scaling and other scenarios.

Fourth, the principle of Redis cluster scaling

Redis cluster provides a flexible scheme for node expansion and contraction. Without affecting the external service of the cluster, you can add nodes to the cluster for expansion or downsize some of the offline nodes. It can be said that slots are the basic unit of Redis cluster management data, and cluster scaling is the movement of slots and data between nodes.

1. Cluster expansion

When a new Redis node runs and joins the existing cluster, we need to migrate slots and data for it. First of all, the migration plan of slots should be specified for the new nodes to ensure that each node is responsible for a similar number of slots after migration, so as to ensure that the data of these nodes is uniform.

First start a Redis node, marked M4.

Use the cluster meet command to add the new Redis node to the cluster. At the beginning, the new node is in the state of the master node, and since there is no responsible > slot, it cannot accept any read and write operations. Later, we will migrate the slot and fill it with data.

Send the cluster setslot {slot} importing {sourceNodeId} command to the M4 node and have the target node prepare the data for the import slot. > 4) send the cluster setslot {slot} migrating {targetNodeId} command to the source node, that is, M1 node, M2 node, M3 node, and let the source node > point prepare the data of the migration slot.

The source node executes the command cluster getkeysinslot {slot} {count} to obtain count keys belonging to slot {slot}, and then performs the operation of step > 6 to migrate the key data.

Execute migrate {targetNodeIp} "0 {timeout} keys {key... on the source node } command to batch migrate the acquired keys to the target node through the pipeline mechanism. The batch migration version of the migrate command is provided in Redis version 3.0.6 and above.

Repeat steps 5 and 6 until all the key data under the slot is migrated to the target node.

Send the cluster setslot {slot} node {targetNodeId} command to all master nodes in the cluster to notify that the slot is assigned to the target node. In order to ensure that slot node mapping changes propagate in time, it is necessary to traverse and send to all master nodes to update the migrated slots to execute the new node.

two。 Cluster contraction

To shrink a node is to take the Redis node offline, and the whole process requires the following operation flow.

First of all, you need to confirm whether the offline node has a responsible slot. If so, you need to migrate the slot to other nodes to ensure the integrity of the mapping of the entire cluster slot node after the node is offline.

When the offline node is no longer responsible for the slot or is a slave node, it can notify other nodes in the cluster to forget the offline node, and when all nodes forget to change the node, they can shut down normally.

Offline nodes need to migrate their own slots to other nodes, which is consistent with the previous process of node capacity expansion.

After the migration slot is completed, all nodes in the cluster need to be notified that they have forgotten to go offline, that is, other nodes will no longer exchange Gossip messages with the nodes to be offline.

The Redis cluster uses the cluster forget {downNodeId} command to add the specified node to the disabled list, and the nodes in the disabled list no longer send Gossip messages.

V. Summary

Redis Cluster is the cluster implementation of Redis, with built-in automatic data slicing mechanism. All key in the cluster is mapped to 16384 Slot, and each Redis Instance in the cluster is responsible for reading and writing a part of the Slot. The cluster client can send commands when connecting to any Redis Instance in the cluster. When the Redis Instance receives a request from a Slot that it is not responsible for, it will return the Redis Instance address of the Slot in charge of the request Key to the client. After receiving it, the client will automatically resend the original request to this address, which is transparent to the outside world. Which Slot a Key belongs to is determined by crc16 (key)% 16384.

Interview question: why is RedisCluster designed with 16384 slots?

The author gives an answer to this question!

The address is: https://github.com/antirez/redis/issues/2576

The author's original answer is as follows: The reason is:

Normal heartbeat packets carry the full configuration of a node, that can be replaced in an idempotent way with the old in order to update an old config. This means they contain the slots configuration for a node, in raw form, that uses 2k of space with26k slots, but would use a prohibitive 8k of space using 65k slots.At the same time it is unlikely that Redis Cluster would scale to more than 1000 mater nodes because of other design tradeoffs.

So 16k was in the right range to ensure enough slots per master with a max of 1000 maters, but a small enough number to propagate the slot configuration as a raw bitmap easily. Note that in small clusters the bitmap would be hard to compress because when N is small the bitmap would have slots/N bits set that is a large percentage of bits set.

1. If the slot is 65536, the message header for sending heartbeat information reaches 8k, and the heartbeat packet sent is too large.

As mentioned above, the one that takes up the most space in the header is myslots [cluster _ SLOTS/8]. When the slot is 65536, the size of this block is: 65536 / 8 / 1024=8kb because every second, the redis node needs to send a certain number of ping messages as heartbeats. If the slot is 65536, the header of this ping message is too large and a waste of bandwidth.

It is almost impossible for the number of cluster master nodes of 2.redis to exceed 1000.

As mentioned above, the more nodes in the cluster, the more data in the message body of the heartbeat packet. If there are more than 1000 nodes, it will also cause network congestion. Therefore, the redis author does not recommend that the number of redis cluster nodes exceed 1000. Then, for redis cluster clusters with less than 1000 nodes, 16384 slots will be sufficient. There is no need to expand to 65536.

3. The smaller the slot and fewer nodes, the higher the compression ratio.

In the configuration information of the master node of Redis, the hash slot it is responsible for is saved in the form of a bitmap. In the process of transmission, bitmap will be compressed, but if the filling ratio of bitmap slots / N is very high (N represents the number of nodes), the compression ratio of bitmap is very low. If the number of nodes is small and the number of hash slots is large, the compression ratio of bitmap is very low.

And 16384 / 8 / 1024=2kb, how about, magic no!

To sum up, the author decided to take 16384 slots, no more, no less, just right!

About why the RedisCluster is designed to 16384 slots to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.