I have encountered a requirement to store 50 million key pairs in Redis, each of which is approximately 512 BYTES. For rapid deployment and external service, we use cloud host to run Redis instances. Then, how to choose the memory capacity of cloud host?

My rough calculations show that these key-value pairs take up about 25GB of memory (50 million by 512B). So, the first solution THAT came to my mind was to choose a 32GB cloud host to deploy Redis. Because 32GB of memory can hold all the data, and there is still 7GB left, you can keep the system running properly. I also persisted the data using THE RDB to ensure that the data could be recovered from the RDB if the Redis instance failed.

However, in the process of using it, I found that Redis is sometimes very slow to respond. Later, using the INFO command, we looked at Redis’ latest_fork_usec index, which indicates the length of the last fork, and found that the index was extremely high, reaching the second level.

This has to do with Redis’ persistence mechanism. When using RDB for persistence, Redis forks the child process. The time taken for forking is positively correlated with the amount of Redis data, and forking blocks the main thread. The larger the amount of data, the longer the main thread is blocked by forking. Therefore, when using RDB to persist 25GB of data, the amount of data is large, and the child process running in the background blocks the main thread during fork creation, resulting in slow Redis response.

It seems obvious that the first plan is not feasible, and we have to look for other plans. At this point, we noticed the Redis slice cluster. Although the slicing cluster is cumbersome, it can hold a large amount of data and has less impact on the blocking of the Redis main thread.

Sliced cluster, also known as sliced cluster, means to start multiple Redis instances to form a cluster, and then divide the received data into multiple copies according to certain rules, and each copy is saved by an instance. Going back to our previous scenario, if you split 25GB of data into five equally (although you can avoid splitting) and use five instances to save, each instance only needs to store 5GB of data. As shown below:

Thus, in a sliced cluster, when the instance generates an RDB for 5GB of data, the amount of data is much smaller, and the fork child process generally does not block the main thread for a long time. By using multiple instances to save data slices, we were able to save 25GB of data without the sudden slow response caused by fork blocking the main thread.

When using Redis in practice, it is often unavoidable to save large amounts of data as users or businesses grow in size. The sliced cluster is a very good solution. In this lesson, we will study it.

How do I save more data?

In the example above, we used two approaches, large memory cloud hosting and sliced clustering, to store large amounts of data. In fact, these two methods correspond to Redis’s two solutions to increasing data volume: Scale up and Scale out.

  • Vertical scaling: Upgrade the resource configuration of a single Redis instance, including increasing memory capacity, disk capacity, and CPU configuration. As shown in the figure below, the original instance had 8GB of RAM and 50GB of hard disk, and the vertical scaling increased the memory to 24GB and the hard disk to 150GB.
  • Scale-out: Scale-out increases the number of current Redis instances, as shown in the figure below, from one instance with 8GB memory and 50GB disk to three instances with the same configuration.

So, what are the pros and cons of these two approaches?

First, vertical scaling has the advantage of being simple and straightforward to implement. But there are two potential problems with the scheme.

The first problem is that when using RDB to persist data, if the amount of data increases and the amount of memory required increases, the main thread may block when forking children (as in the example above). However, if you don’t require Redis data to be persisted, vertical scaling can be a good choice.

However, there is a second problem: vertical scaling is limited by hardware and cost. This makes sense, after all, scaling from 32GB to 64GB is easy, but scaling to 1TB is limited by hardware capacity and cost.

Horizontal scaling is a more scalable solution than vertical scaling. This is because if you want to store more data, you can simply increase the number of instances of Redis without worrying about the hardware and cost constraints of a single instance. Scale-out Redis slice clusters can be a great choice for millions and tens of millions of users.

However, when using only a single instance, it is very clear where the data resides and where the client accesses, but sliced clustering inevitably involves the issue of distributed management of multiple instances. To make slice clustering work, we need to solve two major problems:

  • How is the data distributed across multiple instances after it has been sliced?
  • How does the client determine on which instance it wants to access data?

So let’s take it one at a time.

The corresponding distribution of data slices and instances

In a sliced cluster, the data needs to be distributed across different instances, so how does the data correspond to the instances? This is related to the Redis Cluster solution that I’m going to talk about next. However, we need to understand the relationship and difference between sliced Cluster and Redis Cluster.

In fact, slicing clustering is a general mechanism for storing large amounts of data, which can be implemented in different ways. Prior to Redis 3.0, there was no official solution for slicing clusters. Since 3.0, a solution called Redis Cluster has been officially provided to implement sliced clustering. The Redis Cluster solution provides corresponding rules for data and instances.

Specifically, the Redis Cluster solution uses Hash slots (I’ll just call them slots) to handle the mapping between data and instances. In the Redis Cluster scheme, a slice Cluster has a total of 16,384 hash slots, which are similar to data partitions. Each key-value pair is mapped to a hash slot according to its key.

The specific mapping process is divided into two steps: first, according to the key of the key-value pair, a 16-bit value is calculated according to the CRC16 algorithm; Then, the 16-bit value is used to obtain modules in the range of 0 to 16383, and each module represents a corresponding numbered hash slot. For the CRC16 algorithm, which is not the focus of this lecture, you can simply look at the resources in the link.

So how are these hash slots mapped to specific Redis instances?

When we deploy the Redis Cluster solution, we can use the Cluster create command to create a Cluster, and Redis will automatically distribute the slots evenly across the Cluster instances. For example, if there are N instances in the cluster, the number of slots on each instance is 16384/N.

Of course, we can also use the Cluster meet command to manually establish connections between instances to form clusters, and use the Cluster addslots command to specify the number of hash slots on each instance.

For example, if different Redis instances in the cluster are configured with different memory sizes, if the hash slots are evenly divided among each instance, the instance with small memory will have greater capacity pressure than the instance with large memory when holding the same number of key-value pairs. When this happens, you can use the Cluster addslots command to manually allocate hash slots based on the resource configuration of each instance.

So just to make it easier for you to understand, let me draw a diagram to illustrate the mapping of data, hash slots, and instances.

The slice cluster in the diagram has three instances in total, and assuming five hash slots, we can first manually allocate hash slots by using the following command: Instance 1 stores hash slots 0 and 1, instance 2 stores hash slots 2 and 3, and Instance 3 stores hash slot 4.

Redis -cli -h 172.16.19.3 -p 6379 cluster addslots 0,1 redis-cli -h 172.16.19.4 -p 6379 cluster addslots 2,3 redis-cli -h 172.16.19.5 -P 6379 cluster addslots 4Copy the code

In the cluster running process, key1 and KEY2 calculate the CRC16 value, take the modulus of the total number of hash slots 5, and then according to their modulus results, can be mapped to the corresponding instance 1 and instance 3.

In addition, I will give you a small reminder that when assigning hash slots manually, you need to allocate all 16,384 slots, otherwise the Redis cluster will not work properly.

Ok, through the hash slot, the slice cluster realizes the allocation of data to the hash slot, hash slot and then to the instance. But even if the instance has hash slot mapping information, how does the client know which instance the data to access is on? Next thing I know, I’ll talk to you.

How does the client locate the data?

The hash slot in which key-value pair data is located can be computed, and this calculation can be performed when the client sends the request. However, to further locate the instance, you also need to know on which instance the hash slot is distributed.

Typically, once a client has established a connection with a cluster instance, the instance sends the hash slot assignment information to the client. However, when the cluster is first created, each instance only knows which hash slots it has been assigned, not the hash slots owned by other instances.

So why can a client get all the hash slot information when accessing any instance? This is because the Redis instance sends its hash slot information to other instances connected to it, completing the diffusion of hash slot allocation information. When instances are connected to each other, each instance has a mapping of all the hash slots.

After receiving the hash slot information, the client caches the hash slot information locally. When a client requests a key-value pair, the hash slot corresponding to the key is computed, and then the request can be sent to the corresponding instance.

However, the mapping between instances and hash slots is not constant in a cluster, with two common variations:

  • In the cluster, instances are added or deleted, and Redis needs to reassign hash slots;
  • For load balancing, Redis needs to redistribute hash slots across all instances.

At this point, instances can also pass messages to each other to get the latest hash slot allocation information, but clients are not actively aware of these changes. As a result, its cache of allocation information is inconsistent with the latest allocation information, so what to do?

The Redis Cluster solution provides a redirection mechanism. The so-called “redirection” means that when a client sends a data read/write operation to an instance, but there is no corresponding data on the instance, the client needs to send operation commands to a new instance.

How does the client know where to access the new instance when it redirects? When a client requests an operation on a key-value pair to an instance that does not have a hash slot for the key-value pair mapping, the instance will return to the client the result of the ‘MOVED’ command below, which contains the address for the new instance.

GET hello:key
(error) MOVED 13320 172.16.19.5:6379
Copy the code

The MOVED command indicates that the hash slot 13320 where the key-value pair requested by the client resides is actually on the instance 172.16.19.5. By returning the MOVED command, you tell the client information about the new instance where the hash slot is. In this way, the client can connect directly to 172.16.19.5 and send operation requests.

Let me draw a diagram to illustrate how the MOVED redirection command works. As you can see, the data in Slot 2 has been migrated from instance 2 to instance 3 due to load balancing, but the client cache still records “Slot 2 is in instance 2”, so it sends commands to instance 2. Instance 2 returns a MOVED command to the client to return the latest location of Slot 2 (that is, on instance 3), and the client will send the request to instance 3 again and update the local cache to update the mapping between Slot 2 and the instance.

Note that in the figure above, when the client sends commands to instance 2, all data in Slot 2 has been migrated to instance 3. In practice, if there is a lot of data in Slot 2, the client may send a request to instance 2, but only part of the data in Slot 2 is migrated to instance 3, and some data is not migrated. In this case, the client will receive an ASK error message as follows:

GET hello:key
(error) ASK 13320 172.16.19.5:6379
Copy the code

The ASK command in this result indicates that the hash slot 13320 where the key-value pair requested by the client resides is on instance 172.16.19.5, but the hash slot is being migrated. In this case, the client needs to send an ASKING command to 172.16.19.5. What this command means is that it allows the instance to execute the next command sent by the client. The client then sends the GET command to the instance to read the data.

It looks a little bit complicated, but let me illustrate it with a picture.

In the figure below, Slot 2 is being migrated from instance 2 to instance 3, key1 and key2 have been migrated, and key3 and key4 are still in instance 2. When a client requests key2 from Instance 2, it receives the ASK command from instance 2.

The ASK command has two meanings. First, it indicates that Slot data is still being migrated. Second, the ASK command returns the address of the latest instance of the data requested by the client. In this case, the client needs to send the ASKING command to instance 3 and then the action command.

Unlike the MOVED command, the ASK command does not update the client cache hash slot allocation information. So, in the figure above, if the client requests data in Slot 2 again, it will still send the request to instance 2. That is, the ASK command simply allows the client to send a request to the new instance, rather than changing the local cache so that all subsequent commands are sent to the new instance, as the MOVED command did.

summary

In this lesson, we learned about the advantages of slicing clusters for holding large amounts of data, as well as the hash slot based data distribution mechanism and the client-side approach to locating key-value pairs.

To cope with data volume expansion, adding memory is simple and straightforward, but the database memory is too large, which slows down performance. Redis slice cluster provides a scale-out mode, that is, multiple instances are used and each instance is configured with a certain number of hash slots. Data can be mapped to hash slots through the hash values of keys, and then distributed to different instances through hash slots. The advantage of this is that it scales well, and the sliced cluster can handle no matter how much data there is.

In addition, instances are added or removed from the cluster or data is redistributed to achieve load balancing. As a result, the mapping between hash slots and instances changes. When a client sends a request, it receives an error message. With the MOVED and ASK commands, you won’t have to worry about this type of error.

I just said that before Redis 3.0, there were no sliced cluster solutions officially provided by Redis. However, there were already some sliced cluster solutions in the industry at that time, such as ShardedJedis based on client partition, Codis based on proxy, Twemproxy, etc. The application of these solutions is earlier than Redis Cluster solution, and they have their own advantages in supporting Cluster instance size, Cluster stability, and client friendliness. I will talk to you about the implementation mechanism and practical experience of these solutions in later courses. In this way, when you encounter the problem of large amount of data brought by business development, you can choose the appropriate solution to implement the sliced cluster according to the characteristics of these solutions to meet the business needs.

Each lesson asking

As usual, here’s a quick question for you: The Redis Cluster solution allocates key-value pairs to different instances by hash slots. This process requires CRC calculation of the key of the key-value pair and then mapping to the hash slot. Is there any benefit to doing this? If you use a table to directly record the key-value pair relationships between instances (e.g., key-value pair 1 on instance 2, key-value pair 2 on instance 1), then you don’t need to calculate the key-value relationship between the hash slot, just look up the table, why not Redis?

You are welcome to speak freely in the comments area. If you feel that you have gained something, I hope you can help me share today’s content with your friends and help more people solve the problem of slicing cluster.