Why is rediscluster designed with 16384 slots?

Dear students , Have you ever used Redis Cluster ？ that Redis What is the principle of clustering ？ Remember the following two sentences ：

• Redis Sentinal Focus on high availability , stay master It will automatically slave Upgrade to master, Continued provision of services .
• Redis Cluster Focus on scalability , In a single redis When there is not enough memory , Use Cluster For fragmentation storage .

One 、 Data fragmentation strategy

The most important point in the distributed data storage scheme is data fragmentation , It's called Sharding. To enable the cluster to 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 methods of data fragmentation are ： Range fragmentation , Hash fragmentation , Consistency hash algorithm and virtual hash slot etc .

Range fragmentation assumes that the data set is ordered , Put the data in close sequence together , It can support traversal operation very well . The disadvantage of range fragmentation is that when writing in sequence , There will be hot spots . For example, log type writing , In general, the order of logs is time related , Time is monotonously increasing , So the hotspot of writing is always in the last fragment . For relational databases , Because of the frequent need for table scanning or index scanning , Basically, we use the range segmentation strategy .

We want to make different key Spread out to different redis node , The usual practice is to get key Hash value of , And then find the module according to the number of nodes , But this approach has its obvious disadvantages , When we need to add or subtract a node , Will cause a lot of key Can't hit , The proportion is quite high , So someone put forward the concept of consistent hashing .

Consistent hashing has four important characteristics ：

• Equilibrium ： Others define it as balance , It means that the result of hash can be distributed to all nodes as far as possible , This can effectively use the resources on each node .
• monotonicity ： When the number of nodes changes, the hash result should protect the allocated content from being reassigned to new nodes as much as possible .
• Dispersion and load ： These two actually mean the same thing , It requires a consistent hash algorithm to key Hashing should avoid duplication as much as possible .

Two 、Redis The fragmentation mechanism of

however ：Redis Cluster does not use consistency hash, It introduces the concept of hash slot .

Redis Cluster Partition with virtual hash slot , All keys map to by hash function 0 ~ 16383 Integer slot , Every key adopt CRC16 Check pair 16384 Take the mold to decide which slot to place (Slot), Each node is responsible for maintaining a 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 remove nodes , And whether it's adding, deleting or modifying a node , The cluster will not be unavailable . The advantage of using hash slots is that you can easily add or remove nodes .

• When you need to add nodes , Just move some hash slots of other nodes to the new node ;
• When a node needs to be removed , Just move the hash slot on the removed node to another node .

3、 ... and 、Redis Features of virtual slot partition

• Decouple the relationship between data and nodes , It simplifies the difficulty of node expansion and contraction .
• The nodes themselves maintain the mapping relationship of slots , There is no need for client or agent service to maintain slot partition metadata
• Support nodes 、 Mapping query between slot and key , For data routing , Online cluster scaling and other scenarios .

Four 、 Redis The principle of cluster scaling

Redis Cluster provides flexible node expansion and contraction scheme . Without affecting the external services of the cluster , You can add nodes to the cluster to expand capacity, or you can downsize some nodes offline . so to speak , Slot is Redis The basic unit of cluster management data , Cluster scaling is the movement of slots and data between nodes .

1. The cluster expansion

When one Redis After the new node runs and joins the existing cluster , We need to migrate slots and data for it . First, you need to specify the migration plan for the new node , Ensure that each node is responsible for a similar number of slots... After migration , So that the data of these nodes is even .

• Start a Redis node , Write it down as M4.
• Use cluster meet command , Make the new Redis Nodes join the cluster . At the beginning, new nodes are all primary nodes , Because there is no responsible > Slot , So I can't accept any read or write operations , Then we will migrate the slot and fill in the data for him .
• Yes M4 The node sends cluster setslot { slot } importing { sourceNodeId } command , Let the target node prepare the data of the import slot . >4) To the source node , That is to say M1,M2,M3 The node sends cluster setslot { slot } migrating { targetNodeId } command , Let the source Festival > Point ready to move out of the slot data .
• Source node execution cluster getkeysinslot { slot } { count } command , obtain count One belongs to the slot { slot } Key , Then follow the steps > Six operations to migrate key data .
• Execute... On the source node migrate { targetNodeIp} " " 0 { timeout } keys { key… } command , Pass the acquired key through pipeline Mechanism > Bulk migration to target nodes , Bulk migration version of migrate Command in Redis 3.0.6 The above version provides .
• Repeat steps 5 And steps 6 Until all the key value data under the slot is migrated to the target node .
• Send... To all primary nodes in the cluster cluster setslot { slot } node { targetNodeId } command , The notification slot is assigned to the target node . in order to > Ensure that slot node mapping changes are propagated in time , It is necessary to traverse the slot sent to all the master nodes to update the migrated nodes .

2. Cluster shrinkage

The shrink node is going to be Redis Node offline , The whole process needs the following operation process .

• First, you need to confirm whether the offline node has a responsible slot , If it is , You need to move the slots to other nodes , Ensure the integrity of the whole cluster slot node mapping after the node is offline .
• When the downline node is no longer responsible for the slot or is itself a slave node , You can notify other nodes in the cluster to forget the offline nodes , When all nodes forget to change nodes, they can be shut down normally .

Offline nodes need to migrate their own slots to other nodes , The principle is consistent with the previous migration slot process of node expansion .

After the migration of the tank , You also need to notify all nodes in the cluster that they have forgotten to log off , That is to say, other nodes are no longer connected with the nodes to be offline Gossip The message exchange .

Redis Cluster use cluster forget { downNodeId } Command to add the specified node to the disable list , Nodes in the disabled list will no longer send Gossip news .

5、 ... and 、 summary

Redis Cluster yes Redis Cluster implementation of , Built in data auto segmentation mechanism , Inside the cluster, all the key Mapping to 16384 individual Slot in , Each of the clusters Redis Instance Responsible for a part of it Slot Read and write . Cluster clients connect to any of the clusters Redis Instance You can send commands , When Redis Instance Receive what you are not responsible for Slot The request of , Will be responsible for the request Key Where Slot Of Redis Instance Address returned to client , The client automatically resends the original request to this address after receiving it , Transparent to the outside . One Key Which is it Slot from crc16(key) % 16384 decision .

Interview questions ： Why? RedisCluster It will be designed as 16384 A slot ?

This problem , The author gives an answer ！

The address is as follows :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 with16k 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, Send heartbeat message header to 8k, The heartbeat packet sent is too large .

As mentioned above , In the header , What takes up the most space is myslots[CLUSTER_SLOTS/8]. When the slot is 65536 when , The size of this piece is :65536÷8÷1024=8kb Because every second ,redis The node needs to send a certain number of ping Messages as heartbeat packets , If the slot is 65536, This ping The message header is too big , Waste bandwidth .

2. redis The number of cluster primary nodes of cannot exceed 1000 individual .

As mentioned above , More cluster nodes , The more data the heartbeat packet carries in its message body . If the node passes 1000 individual , It can also lead to network congestion . therefore redis author , Don't suggest redis cluster The number of nodes exceeds 1000 individual . that , For the number of nodes in 1000 Inside redis cluster colony ,16384 There are enough slots . There is no need to expand to 65536 individual .

3. The smaller the slot , With fewer nodes , High compression ratio

Redis In the configuration information of the master node , The hash slot it is responsible for is through a bitmap In the form of , During transmission , Would be right bitmap Compress , But if bitmap The filling rate of slots / N High words (N Represents the number of nodes ),bitmap The compression rate is very low . If the number of nodes is small , If there are many hash slots ,bitmap The compression rate is very low .

and 16384÷8÷1024=2kb, What about? , Magic is not ！ in summary , take 16384 Slot , No less , It is just fine ！