Redis Cluster - the underlying principle of slot assignment

Redis The cluster saves the key value pairs of the database by partitioning ： The entire database of the cluster is divided into 16384 Slot , Enter this for each key in the database 16384 One of the slots , Every node in the cluster can handle 0-16384 Slot .

When in the database 16384 There are nodes in each slot , The cluster is online ; If any of the slots are not handled , So the cluster is offline .

// By sending to the node CLUSTER ADDSLOTS  command , One or more slots can be assigned to a node 
CLUSTER ADDSLOTS <slot><slot...>

Record the slot assignment information of the node

clausterNode Structural slouts Properties and numslot Property records which slots the node is responsible for processing ：

struct clusterNode{
	//....
    unsigned char slots[16384/8];
    // The cluster node is responsible for processing the number of slots  
    int numslots;
}

slots Property is a binary array , The array length is 16384/8=2048 position , contain 16384 Binary bits .

Redis With 0 Bit start index ,16383 Terminate index for , Yes slots Array 16384 Number in binary digits , And according to the index i To determine whether the node is responsible for processing i：

• • If you are responsible for processing the tank i, that slots The array is indexed i The binary value on is 1
  • If you are not responsible for processing the tank i, that slots The array is indexed i The binary value on is 0

Propagate the slot assignment information of the node

A node records the slots it is responsible for processing in the clusterNode Structural slots Properties and numslots Beyond attribute , And it's going to take its own slots The array is sent by message to the other nodes in the cluster , This is used to tell other nodes which slots they are currently responsible for , Other nodes will make corresponding changes .

for example ： When node A Slave node via message B There the node is received B Of slots Array time , node A It will be on its own clusterState.node A node is found in the dictionary B Corresponding clusterNode structure , And in the structure slots Array to save or update .

Because each node in the cluster will have its own slots The array is sent by message to the other nodes in the cluster , And each receives slots The nodes of the array will save the nodes of the array to the corresponding nodes clusterNode Inside the structure , therefore , Every node in the cluster will know the information in the database 16384 The slots are assigned to which points in the cluster .

Record the assignment information of all slots in the cluster

clusterState The structure of the slots The array records all the data in the cluster 16384 Slot assignment information ：

typedef struct clusterstate{
		
    clusterNode * slots[16384];
}

slots The array contains 16384 The item , Each array item is a pointer to clusterNode Pointer to structure ：

• If slots[i] Pointer to null, So, slot i Not assigned to any node
• If slots[i] The pointer points to a clusterNode structure , So, slot i Has been assigned to clusterNode The node represented by the structure .

If only the slot assignment information is saved in the clusterNode.slots In the array , There will be some problems that can't be solved funny , and clusterState.slots The existence of arrays solves these problems

• If the node only uses clusterNode.slots Array to record slot assignment information , So in order to know i Has been assigned , Or slot i Which node is assigned to , The program needs to traverse ClusterState.Node Everything in it clusterNode structure , Check these ClusterNode Structural slots Array , Until you find the tank responsible for processing i The node of .
• By saving the assignment information of all slots to clusterState.node In an array , The program checks the slot i Assigned , Or get responsible for handling i The node of , Just the scope clusterState.slots[i] The value of the can , The operation is only complicated O(1)

although clusterState.slots The array records the assignment information of all slots in the cluster , But use clusterNode Structural slots Array to record the slot assignment information of a single node is still necessary ：

• If not used clusterNode.slots Array , And use it alone clusterState.slots Array words , Each time a node A When the slot assignment information of is propagated to other nodes , The program must first traverse the entire clusterState.slots Array , Record nodes A Which slots are responsible for processing , Then the node can be sent A Slot assignment information for , This is better than sending directly clusterNode.slots Arrays are much more inefficient and cumbersome .

summary ：clusterState.slots The array records the assignment information of all slots in the cluster , and clusterNode.slots The array only records clusterNode The node slot assignment information represented by the structure .

CLUSTER ADDSLOTS Implementation of commands

CLUSTER ADDSLOTS The command takes one or more slots as arguments , And assign all input slots to the node receiving the command

CLUSTER ADDSLOTS <SLOT>[slot ........]

CLUSTER ADDSLOTS The basic logic of the command

• First, traverse the input slot of the search , Check if they are all unassigned slots , If a slot is assigned a node , It terminates the command and returns an error message
• If all slots are unassigned , Then traverse all input slots again , Assign these slots to the current node

• • take clusterState.slots[i] Pointer to the current node clusterNode structure
  • The array is indexed i The binary bits on are all set to 1

clusterState[i] = clusterState.myself
setSlotBit(clusterState.myself.slots,i);

Last , stay CLUSTER ADDSLOTS After the command is executed , The node will send a message to inform other nodes in the cluster , Which slots are you currently dealing with