Principle of redis cluster mode

One 、Redis Distributed extension Redis Cluster programme

Data will be lost during master-slave switching , Because there's only one master, You can only do single points , There is no solution to the problem of horizontal expansion . And each node holds all the data , One is that the memory occupation rate is high , In addition, if data recovery , Very slow . And the amount of data is too large IO The performance of the operation will also have an impact . So we are also right Redis The need for data fragmentation , The so-called fragmentation is to split a piece of big data into multiple pieces of small data , stay 3.0 Before , We can only build multiple redis Master slave node cluster , Split different business data into different clusters , This method requires a lot of code in the business layer to complete data fragmentation 、 Routing and so on , Resulting in high maintenance costs 、 increase 、 Removing nodes is cumbersome .Redis3.0 And then introduced Redis Cluster Cluster solution , It is used to solve the needs of distributed expansion , At the same time, it also realizes the high availability mechanism .

1.Redis Cluster framework

One Redis Cluster By multiple Redis Node structure , There is no intersection of data served by different node groups , That is, each node group corresponds to data sharding A slice of . Some nodes in the node group are primary and standby nodes , Corresponding master and slave node . The two data are consistent in quasi real time , The asynchronous active / standby replication mechanism ensures that . A node group has and has only one master node , At the same time, there can be 0 To more than one slave node , In this node group, there are only master Nodes provide some services to users , The reading service can be provided by master perhaps slave Provide .
As shown in figure, , Contains three master Nodes and three master Corresponding slave node , Generally, a group of clusters should at least 6 Only nodes can ensure complete high availability . Three of them master Will assign different slot（ Represents the data partition interval ）, When master Failure time ,slave Will automatically elect to become master Continue to provide services instead of the primary node .

2. About gossip agreement

Throughout redis cluster Architecture , If

1. New join node
2. slot transfer
3. The node is down
4. slave The election became master

We hope that these changes will enable each node in the whole cluster to discover as soon as possible , Propagate to the whole cluster and all nodes in the cluster agree , Then each node needs to be connected with each other and carry relevant state data for propagation , The normal logic is to send messages to all nodes in the cluster by broadcasting , The point is that the data synchronization in the cluster is faster , But every message needs to be sent to all nodes , Yes CPU And bandwidth consumption is too high , So it's used here gossip agreement .Gossip protocol Also called Epidemic Protocol （ Epidemic protocol ）, There are many aliases, such as ：“ Rumor algorithm ”、“ Epidemic spread algorithm ” etc. . It is characterized by , In a network with a limited number of nodes , Every node will “ Random ”（ Not really random , Instead, the communication node is selected according to the rules ） Communicate with some nodes , After a messy correspondence , The state of each node will be agreed within a certain period of time , As shown in the figure .
Suppose we set the following rules in advance ：

1. Gossip It's a periodic spread of messages , Limit the period to 1 second
2. Random selection of infected nodes k Adjacency nodes （fan-out） Disseminate messages , Here is the fan-out Set to 3, At most every time 3 Node spread .
3. Each time the message is spread, the node that has not been sent is selected for spreading
4. The node receiving the message no longer spreads to the sending node , such as A -> B, that B When it's on the air , No longer issued A. There's a total of 16 Nodes , node 1 Is the initial infected node , adopt Gossip The process , Eventually, all nodes are infected ：
   

3.gossip Agreement message

gossip Protocol contains multiple messages , Include ping,pong,meet,fail wait .
ping： Each node will send to other nodes frequently ping, It contains its own state and cluster metadata maintained by itself , Through each other ping Exchange metadata ;
pong: return ping and meet, Include your own status and other information , It can also be used for information broadcast and update ;
fail: One node judges another fail after , Is sent fail To other nodes , Notify other nodes , The specified node is down .
meet： Sent by a node meet To add new nodes , Add new nodes to the cluster , Then the new node will start to communicate with other nodes , You don't need to send all that's needed to form a network CLUSTER MEET command . send out CLUSTER MEET Message so that each node can reach each other, just through a known node chain . Because it's swapped in heartbeat packets gossip Information , Missing links between nodes will be built .

4.gossip Advantages and disadvantages

advantage ： gossip The advantage of the protocol is that the update of metadata is scattered , Not in one place , Renewal requests will continue , There is a certain delay in updating all nodes , It reduces the pressure ; De centralization 、 Scalable 、 Fault tolerance 、 Uniform convergence 、 Simple . Because there is no guarantee that all nodes will receive messages at a certain time , But in theory, eventually all nodes will receive messages , So it's a final agreement .
shortcoming ： Metadata update may delay some operations of the cluster . Delay of message , Message redundancy .

5. The data distribution

Redis Cluster in ,Sharding use slot( Slot ) The concept of , In all 16384 Slot , It's kind of like pre sharding Ideas . For each entry Redis The key/value pair , according to key To hash , Assigned here 16384 individual slot One of them . The use of hash The algorithm is also relatively simple , Namely CRC16 after 16384 modulus [crc16(key)%16384].Redis Each of the clusters node( node ) Be responsible for sharing this 16384 individual slot Part of , in other words , Every slot They all correspond to one node Responsible for handling .
Pictured 5 Shown , Suppose we are now three master nodes, which are ：A, B, C Three nodes , They can be three ports on a machine , It can also be three different servers . that , Using the Hashimoto trough (hash slot) How to allocate 16384 individual slot Words , The three nodes are responsible for slot The interval is

6. Client redirection

Pictured 5-6 Shown , hypothesis k This key It should be stored in node3 On , At this time, the user is node1 perhaps node2 On the call set k v Instructions , This is the time redis cluster How to deal with it ？

127.0.0.1:7291> set qs 1
(error) MOVED 13724 127.0.0.1:7293

Server return MOVED, That is to say, according to key Calculated slot Not managed by the current node , Server return MOVED Tell the client to go 7293 Port operation .
Change the port at this time , use redis-cli –p 7293 operation , Will return OK. Or use ./redis-cli -c -p port The order of . But the problem is , The client needs to connect twice to complete the operation . So most of the redis The client will maintain a copy locally slot and node Correspondence of , The current is calculated before the instruction is executed key The target node that should be stored , Then connect to the target node for data operation . stay redis The following commands are provided in the cluster to calculate the current key Which should it belong to slot

redis> cluster keyslot key1

6. High availability master-slave switching principle

If the master node does not have a slave node , So when it breaks down , The cluster will be unavailable .
Once a master The node enters FAIL state , Then the whole cluster will become FAIL state , Trigger at the same time failover Mechanism ,failover The aim is to start with slave Select a new master node from the node , So that the cluster can return to normal , This process is implemented as follows ：

When slave self-discovering master Turn into FAIL In the state of , Then try to do Failover, With a view to becoming a new master. Because of the hang up 、master There may be more than one slave, So there are many slave Competition becomes master Node process , The process is as follows ：

1. slave self-discovering master Turn into FAIL
2. Record your own clusters currentEpoch Add 1, And broadcast FAILOVER_AUTH_REQUEST Information
3. Other nodes receive this message , Only master Respond to , Judge the legitimacy of the requester , And send the FAILOVER_AUTH_ACK, For each epoch Send only once ack
4. Try failover Of slave collect master Back to FAILOVER_AUTH_ACK
5. slave More than half received master Of ack Become new after Master ( This explains why clusters need at least three primary nodes , If there are only two , When one of them hangs up , Only one primary node can't be elected successfully )
6. radio broadcast Pong Message notification to other cluster nodes .
   The slave node is not in the primary node FAIL We'll try to start an election right away , It's a delay , A certain delay ensures that we wait FAIL The state propagates in the cluster ,slave If you try to vote now , Other masters Maybe not FAIL state , May refuse to vote .
   Delay calculation formula ： DELAY = 500ms + random(0 ~ 500ms) + SLAVE_RANK * 1000ms
   SLAVE_RANK It means this slave Has gone from master The total amount of replicated data is rank.Rank The smaller the data, the newer the copied data . In this way , With the latest data slave There will be elections first

7. When is the cluster unavailable

1. No master-slave backup , A node goes down
2. The master and slave of a node are all down
3. More than half of the primary nodes are down

Two 、codis The architecture of

Pictured 5-7 Shown , Express Codis The overall architecture diagram .
Codis Proxy： Client connected Redis Agency service , Realized Redis agreement . Except that some commands are not supported ( Unsupported command list ), Expressive and original Redis There is no difference between （ It's like Twemproxy）.
For the same business cluster , You can deploy multiple codis-proxy example ; Different codis-proxy Between by codis-dashboard Ensure that the status is the same as
codis-redisgroup: Representing one redis Service cluster nodes , One RedisGroup There's one in it Master, And multiple Slave
Zookeeper：Codis rely on ZooKeeper To store data routing tables and codis-proxy Meta information of node , codis-config All orders issued will pass ZooKeeper Synced to each living codis-proxy.